Conflict-based search for optimal multi-agent pathfinding

MAPF에서 유명한 알고리즘인 Conflict-Based Search 줄여서 CBS 알고리즘에 대해 정리해보려고 한다. 논문 저자를 보니까 ICTS 저자와 동일하신 분이시던데 정말 대단하신것 같다. 아무튼 CBS알고리즘은 파생 알고리즘도 많고, 범용적으로 쓰이기 쉬운 구조를 갖고있는데, 자세하게 정리해보자. 참고 자료는 Conflict-based search for optimal multi-agent pathfinding 논문이다.

간단한 소개

Conflict Based Search알고리즘은 MAPF 문제를 optimal 하게 해결하기 위한 알고리즘이다. 즉 해당 검색 알고리즘의 비용함수를 최소화하는 solution을 찾아내는 함수인데, 앞서 다뤘던 ICTS와는 다른 접근방식을 통해 문제를 해결한다. ICTS는 모든 비용 조합에 따른 경로 조합을 모두 비교해보는 방식으로 솔루션을 찾아내지만, CBS는 감지된 충돌을 기반으로 제약조건을 생성하고, 제약조건의 조합을 찾아내는 방식으로 솔루션을 찾아낸다. 즉 이전의 방식들과 달리 MAPF를 CBS는 MAPF를 제약된 다수의 single agent path finding 문제로 분해하여 해결한다. 이러한 방법은 기존의 경로조합이나, 경로 비용조합을 탐색하는 것과 다른 상태공간을 탐색하기 때문에 기존의 알고리즘보다 보편적으로 더 우수하다고 한다.

CBS 알고리즘은 이렇게 MAPF를 다수의 single agent path finding문제로 분해하여 solution을 계산하기 위해 single agent path finding에서 충돌을 회피하는 $constraint$를 생성한다. 그렇기 때문에 CBS알고리즘은 ICTS와 마찬가지로 $constraint$의 조합을 탐색하는 High level Search와 single agent path finding을 탐색하는 Low level Search로 구성된 구조를 갖는다.

1. 정의

CBS의 정의부터 간단하게 정리하고 넘어가자. 일단 CBS에서의 입력과 출력은 classical MAPF의 정의를 따른다.

먼저 $path$는 단일 agent의 경로인 $\pi_i$를 나타낸다. 또한 $solution$은 주어진 $k$개의 agent에 대한 $k$개의 경로로 구성된 집합을 의미한다. 즉 Classical MAPF에서의 정의를 그대로 사용한다.

CBS에서 가장 중요한 개념은 $conflict$와 $constraint$이다. 우선 $conflict$는 아래 식과 같은 튜플로 나타내지는 특정 agent간의 충돌을 나타내는 값이다.

\[\begin{aligned} vertex\ conflict &= (a_i, a_j, v, t) \\ edge\ conflict &= (a_i, a_j, v_1. v_2, t)\\ \end{aligned}\]

하나의 $solution$안에서 각 $path$를 비교하여 $conflict$를 찾고, $conflict$가 발견되면 그 $solution$은 무효화 된다.

$constraint$는 single agent path finding 연산에서 $conflict$를 회피하기 위해 사용되는 값이다. $conflict$에서 파생되는 값이며, 아래 식과 같이 튜플로써 정의된다.

\[\begin{aligned} vertex\ constraint &= (a_i, v, t) \\ edge\ constraint &= (a_i, v_1. v_2, t)\\ \end{aligned}\]

$conflict$는 특정 $solution$에서 두 agent $a_i$와 $a_j$가 부딫치는 시간과 장소에 대한 정보이고, $constraint$는 $conflict$에서 파생되어 agent $a_i$가 특정 시간 및 장소에서 충돌을 할 수 있다는 제약조건이다. 즉 하나의 $conflict$에 두개의 $constraint$가 파생될 수 있는 것이다.

2. High-level Search

High level Search에서 CBS알고리즘은 $constraint\ tree$(이하 CT)라는 2진 트리를 탐색한다. CT의 노드 $N$은 다음과 같은 요소로 구성된다.

1. $N.constraints$ : $constraint$의 집합으로 각각의 $constraint$는 하나의 agent에 귀속되어있다. Root CT Node는 해당 집합이 공집합이고, 각 child CT Node는 부모의 $N.constraints$에 추가로 새로운 $constraint$ 하나를 상속받는다.

2. $N.solution$ : 각 CT Node마다 갖는 $solution$으로 모든 $path$가 $N.constraints$에 만족하는 경로이다. 각 $path$는 $N.constraints$를 parent node로 부터 상속 받을 때 Low-level Search를 통해 계산된다.

3. $N.cost$ : $N.solution$의 전체 비용이다. 탐색 알고리즘 조건 중 $f$-value에 해당한다.

CT는 Best fit Search로 검색을 하고, $f$-value가 낮은 노드부터 검색한다. 그렇다면 CT는 어떤방식으로 전개되며 상태공간을 탐색할 수 있을까? 아래부터 자세히 알아보도록 하자.

위 사진은 CT가 어떻게 전개되고, 탐색되는지 보여주는 간단한 그림이다. 우선 처음에 CT의 Root Node는 Con(=$N.constraints$)를 공집합으로 갖는다. 이렇게 $N.constraints$가 정해지면, Low-level Search를 통해 각 agent마다 제약조건에 맞는 $\pi_i$를 계산하여 Sol(=$N.solution$)을 구한다. 위 사진에서는 Root Node에서 경로가 아래 식과 같은 값이 나온 것이다.

\[\begin{aligned} \pi_1 &= (S1, A1, D, G1) \\ \pi_2 &= (S2, B1, D, G2)\\ \end{aligned}\]

이제 제약 조건에 따른 모든 agent의 경로가 구해졌으니 충돌을 검사한다. 각 충돌은 위에서 정의한 바와 같이 vertex, edge conflict를 사용하여 계산한다. 위 경로에 대해 충돌은 아래 식과 같이 검출된다.

\[\begin{aligned} confs &= \{(1, 2, D, 2)\} \\ \end{aligned}\]

$\pi_1$과 $\pi_2$의 사이의 충돌은 2번째 timestep에서 D위치에서 서로 같은 노드 D를 점유하게 되기 때문에 위 식과 같이 나타낼 수 있다. 하나에 $N.solution$에는 여러 conflict가 존재 할 수 있다. 위에서 정의한 충돌 $confs[0]$은 다시 아래 식과 같이 constraint 2개로 나눠질 수 있다.

\[\begin{aligned} const_{0-1} &= (1, D, 2) \\ const_{0-2} &= (2, D, 2)\\ \end{aligned}\]

위의 식과 같이 파생된 $constraint$ 쌍은 각각 child node에 parent node의 Con(=$N.constraints$)에 더해져 상속되며 CT가 전개된다. 하나의 $solution$에서 검출된 충돌이 여러개일 경우 2개 이상의 $conflict$가 여러개의 $constraint$가 생성 될 수 있다. 이 경우 해당 논문에서는 가장 첫번째로 발생하는 $conflict$에 대해서만 $constraint$를 전개하거나, 모든 $conflict$에 대해 $constraint$를 전개하여 충돌의 갯수에 따라 child를 많이 생성하는 방식으로 총 두가지 방식을 제안하는데, 최초로 발생하는 $conflict$만 $constraint$로 전개하는 방식이 더 좋아보인다. constraint가 걸린 시점 이후 경로는 모두 바뀔 수 있기 때문이다.

이렇게 Parent Node에서 Child Node로 $constraint$가 상속된 이후 다시 Low-level Search를 통해 새로운 $N.constraints$에 만족하는 $N.solution$을 계산하고 $conflict$ 검출, $constraint$ 전개를 통해 child node에서 다시 CT를 전개해 나간다.

이렇게 CT를 탐색하다가 $conflict$가 검출되지 않으면 해당 노드의 $N.solution$이 output으로 반환된다.

CT 탐색 알고리즘은 Best-fit Search 알고리즘을 통해 이뤄지는 데 이는 Priority-Queue인 Open-List와 Close-List로 구현된다. 간단한 설명으로는 먼저 Open-List에서 $f$-value가 가장 낮은 Node $N$을 선택하여 꺼내고, $N.conflict$를 이용해 child Node $N_1$과 $N_2$를 전개한다. 이후 $N_1$과 $N_2$를 Open-List에 넣고 앞선 과정을 반복하게 된다. 해당 로직은 아래 pseudo-code이다. 해당 예시 코드는 CBS뿐 아니라 이후에 소개할 Meta Agent CBS의 로직도 담고있는데, 11~18 Line을 제외하고 보면 된다.

3. Low-level Search

이번 섹션에서는 CT를 탐색하며 구한 $N.constraints$에 맞는 경로는 어떻게 계산하는지 정리해보려고 한다. 사실 별 내용이 없긴 하다.

가장 먼저 Low-level Search의 입력은 경로를 찾을 특정 agent, $a_i$ 그리고 $a_i$에 걸려있는 $constraint$들로 이루어진다. 이때 Low-level Search에서는 주어진 agent가 시작점부터 끝점까지 가는 경로를 구하게 되는데, 이때 구해진 경로는 주어진 제약조건을 모두 만족하는 경로이다. 제약조건은 특정시간에 특정 위치에 대한 접근을 제한하기 때문에, 경로를 구하기 위해 탐색하는 search space는 공간차원과 시간차원으로 이루어진 2개 차원을 갖게 된다^{충돌이 발생하기 위해서는 같은시간에 같은공간을 지나야 되기 때문}. 물론 내가 회사에서 개발할때는 실제 로봇의 움직임을 근사하기 위해서 더 많은 상태정보를 추가하여 계산했지만 일단 간단하게 생각해보자. 그렇기 때문에 SIPP과 같은 알고리즘을 사용해서 구현하게 된다.

conflict avoidance table (CAT)

위의 설명만 읽어보면 low-level search에서는 해당하는 에이전트 $a_i$에 걸린 제약조건만 만족하는 경로를 짜는 것 같아 보이지만, 사실 다른 에이전트의 경로도 참고하여 충돌을 미리 회피하기도 한다. 이는 conflict avoidance table이라는 정보를 통해 이루어지는데, 이에 대해 간단히 알아보려한다.

CAT(Conflict Avoidance Table)은 해당 high level search state에 해당하는 각 agent의 경로들이 저장되어있는 자료구조이다. 이 정보는 Low level Search를 진행할때 사용한다.

위 그림과 같이 low-level search에서 생성된 state의 $f$-value가 같은 경우가 있을 수 있다. 이때 CAT를 이용하여 기존의 다른 Agent의 경로와 충돌이 적은 state의 우선순위를 더 높게 책정한다. 그 결과 Low-level Search에서 계산된 경로가 다른 에이전트와 충돌이 존재할 가능성이 낮아지고, 연산속도를 높일 수 있다. 이러한 tie-break 정책은 랜덤한 확장 정책에 비해 연산속도를 2배 가량 빠르게 할 수 있다고 한다.

4. Optimality of CBS

그렇다면 CBS알고리즘의 결과가 최적임은 어떻게 증명할까? 우선 선행되는 정의 몇가지를 짚고 넘어가자

Definition 1

특정 입력에 대한 Constraint Tree의 노드 $N$이 있을 때, 노드 $N$의 모든 제약조건을 만족하는 솔루션 집합을 $CV(N)$이라고 한다. 예를들어 $CV(root)$는 제약조건이 없는상태에서 가능한 모든 솔루션의 집합이 된다. 물론 실제로 $CV(root)$를 구하기 위해서는 CT를 탐색하며 완성해야 한다.

Definition 2

$p \in CV(N)$을 만족할 때 노드 $N$은 솔루션 $p$를 허용한다고 한다. 그리고 $minCost(CV(N))$은 $CV(N)$이 허용하는 솔루션들중 가장 cost가 낮은 솔루션의 cost이고, $CV(N) = \varnothing$일때 $minCost(CV(N)) = \infty$ 이다.

이제 CBS의 최적성을 증명하기 위해 부명제 두개를 증명해보자.

Lemma 1 : $N.cost \le minCost(CV(N))$

$N.cost$는 모든 최적의 단일 에이전트 솔루션의 합으로, N의 제약조건을 만족하는 모든 솔루션 중 최소 비용이다. 반대로 $minCost(CV(N))$은 N의 제약조건을 만족하면서 유효한 모든 솔루션 $p$ 중 최소 비용이다. 후자는 전자의 부분집합이기 때문에, 항상 $N.cost \le minCost(CV(N))$은 만족하고, N.cost는 $CV(N)$의 하한값이 된다.

Lemma 2 : CT를 탐색하는 중에 모든 p에 대해 OPEN list에는 p를 허용하는 노드 N이 적어도 하나는 존재한다.

이를 귀납법으로 정의하면 다음과 같이 나타낼 수 있다.
    i. 모든 솔루션 $p$에 대해 $p \in CV(root)$를 만족
    ii. 특정 노드 $N$에 의해 확장된 새로운 CT Node $N_1$, $N_2$가 있을때 $CV(N) = CV(N_1) \cup CV(N_2)$
전제 i는 Definition 2에 의해 항상 참이된다. 또한 N이 허용하는 솔루션 $p$에 제약 조건의 위치에 에이전트 $a_1$이 있다고 가정해보자. 에이전트 $a_1$은 $N_1$과 $N_2$ 중 하나에서만 제약될 수 있어 자식노드 중 하나는 $p$를 허용하기 때문에 전제 ii역시 참이 된다.

이제 CBS가 항상 최적의 해를 구한다는 명제를 증명해보자.

Theorem 1 : CBS는 최적의 solution을 반환한다.

High-level Search를 통해 Goal CT Node $G$가 계산된 시점에 모든 유효한 솔루션은 적어도 OPEN list에 있는 노드중 하나에 의해 허용된다(Lemma 2). 그리고 $p$를 허용하는 임의의 노드를 $N(p)$라고 할 때 모든 솔루션 $p$에 대해 $N(p).cost \le p.cost$가 성립한다(Lemma 1). $G$는 Goal 노드이기 때문에 $G.solution$은 유효한 솔루션이고, $G.cost$는 유효한 솔루션의 cost가 된다. 이때 High-level Search는 best-first Search이기 때문에 G.cost는 OPEN list에 있는 모든 노드중 가장 최저값을 가진다. 그렇기 때문에 임의의 유효한 솔루션 $p$에 대해 $G.cost \le N(p).cost \le p.cost$를 항상 만족한다.

후기

최근 MAPF분야에서 가장 널리쓰이는(?) Conflict Based Search에 대해 알아보았다. 다른분야에서도 자주 나오는 상태공간 탐색을 기반으로 하는 알고리즘이라 그런지 변형하기도 쉽고, single agent path planning 알고리즘을 거의 그대로 사용하여 직관적이라 자주 사용되는게 아닐까 싶다. 해당 논문을 읽으면서 CBS알고리즘의 완전성이나, MACBS같은 부분은 간단하고, 앞서 설명한 ICTS에서도 간단하게 설명하여 따로 설명하지 않고 넘어갔다. 최근에는 현실에서 MAPF를 사용하는데 중점이 맞춰진 Life-long MAPF에 대해 관련 자료를 찾아보고있는데, 시간이 될때 다시 블로그에 내 생각과 함께 정리해보려 한다.