The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

첫번째로 알아볼 MAPF는 ICTS로 정했다. 물론 이전부터 여러가지 방식의 MAPF가 있었지만, 대부분 Decoupled 방식이거나 A*기반의 방법이었다. ICTS를 부터 정리하기로 한 이유는 크게 두가지가 있었는데, 첫번째는 Centralized 기반의 MAPF 알고리즘에 대해 명확하게 정의한것이었고, 두번째로는 ICTS뿐 아니라 이전에 소개되었던 각 타입들의 MAPF 알고리즘에 대해서도 자세히 정리가 되어있었기 때문이다.

추가적으로 해당 논문을 읽으면서 MDD(Multi-Valued Decision Diagram)라는 개념이 나온다. 이 개념에 대해서는 다음에 알고리즘 최적화를 할때 두고두고 유용하게 사용하게 될 것 같아 이 논문에서는 간단하게 짚고 넘어가고 이후 다른 논문을 읽어보며 자세히 정리해보려 한다.

간단한 소개

이전까지의 MAPF와 ICTS 알고리즘을 소개하기 전 해당 논문에서는 MAPF기법을 distributed와 centralized 방식으로 나눈다. 간단히 말해 각 agent의 경로를 구하는 시스템이 각 agent마다 독립적으로 존재하는지, 하나의 시스템에서 총괄해서 계산하는지의 여부이다. 해당 논문에서는 centralized방식만을 다룬다. 이는 중앙의 시스템에서 모든 로봇의 정보를 고려하여 MAPF의 결과로 최적의 해를 구하기 위한 방법만을 다루기 때문으로 보인다.

이전까지의 최적의 경로를 생성하기 위한 MAPF방식은 주로 A*를 기반으로한 방식으로, 특정 시간에서의 모든 agent의 위치를 갖는 상태공간을 탐색하는 알고리즘이었다고 한다. 이러한 방식은 $k$개의 agent가 각 timestep마다 상, 하, 좌, 우, 대기 총 5가지 움직임을 할 수 있을 때, 특정 timestep $t$에서 가능한 상태의 갯수는 이론상 ${5^k}^t$이다. 즉 최적의 경로를 구하기 위한 시간복잡도가 최악의 경우 $O({5^k}^t)$이기 때문에 너무 많은 시간을 사용하게 된다는 것이다. 이러한 문제를 해결하기 위해 저자들은 각 agent마다 걸리는 시간 조합을 탐색하는 High-Level 탐색과, 실제로 조합을 통해 결정된 시간에 goal에 도착하는 경로를 탐색하는 Low-Level 탐색으로 나누어 알고리즘을 설계하였다.

추가로 해당 논문에서는 Centralized한 여러가지 MAPF 방식에 대해 설명하고, 이를 새롭게 제안한 알고리즘인 ICTS와 비교하여 장 단점에 대해 서술하였다.

1. Decoupled MAPF

가장 먼저 Decoupled MAPF에 대해 알아보자. Decoupled MAPF는 각 agent의 경로와 충돌을 별도로 계산하는 방식의 MAPF를 말한다. 이 방법의 경우 주로 빠른시간내에 결과가 나오는 대신 최적의 솔루션을 기대하기 어렵다고 한다. 또한 복잡한 환경에서 Deadlock이 발생할 가능성이 존재해 Centralized 방식으로 한 의미가 없을 것 같아 별도로 정리하지 않고 바로 Coupled-approach로 넘어가도록 하겠다.

2. A*-based search

K개의 agent가 존재하는 기본적인 A*기반의 MAPF에서 상태 $state$에 대한 평가 함수 $SIC$^{$Sum\ of\ Individual\ Costs\ heuristic$}는 다음과 같이 정리된다.

\[\begin{aligned} state &= (loc_1, loc_2, ... , loc_k)\\ loc_i &= agent_i의\ 상태\ state에서의\ 위치\\ \\ SIC(state) &= h(state) + g(state) \\ h(state) &= h(loc_1) + h(loc_2) + ... + h(loc_k) \\ g(state) &= g(loc_1) + g(loc_2) + ... + g_(loc_k) \\ h_i &= 현재\ 상태에서\ agent_i가\ 골까지\ 거리 \\ g_i &= 현재\ 상태에서\ agent_i가\ 시작점부터\ 움직인\ 거리 \end{aligned}\]

이 경우 하나의 $state$마다 분기되는 새로운 상태의 갯수는 상술했다시피 수행할 수 있는 action의 갯수를 $a$라고 했을 때 $a^k$개이다. 물론 MAPF는 충돌을 고려해야 하기 때문에 실제로 분기 가능한 상태는 graph상의 로봇의 밀도가 높으면 높을 수록 더 적어진다.

Operator Decomposition(OD)

OD는 상태공간을 한 timestep에 따라 분기 할 때 모든 agent를 따로따로 분기하는방식이다. 아래 사진과 같은 방식으로 상태공간이 분화되는데, 이렇게 할 경우 한번에 16개를 하는게 아니라, heuristic함수에 의해 각 에이전트가 가까워진 상태부터 우선적으로 분기하게 되기 때문에 생성되는 상태의 갯수가 확 줄어든다고 한다.

Independence Detection(ID)

보통 MAPF problem을 계산하는데 걸리는 시간은 agent의 갯수에 따라 지수적으로 증가한다. 이 점에서 착안하여 ID는 직접적으로 관련있는 Agent만 묶어서 sub-problem으로 만들어 따로 계산하는 방식의 알고리즘이다.알고리즘의 순서도는 아래 사진과 같다.

알고리즘의 개요가 마치 Union Find와 유사한데, 한줄씩 설명하면 다음과 같다.

• (line 1) 각 에이전트를 포함하는 각각의 Sub-problem을 생성
• (line 2) 각 Sub-problem마다 A* 기반의 MAPF 계산
• (line 4) 모든 agent 경로를 기반으로 충돌검사
• (line 6) 충돌이 있을경우 간단하게 충돌을 해결
• (line 8-9) 충돌이 있을 경우 충돌이 발생한 두 Sub-problem을 병합후 line 3으로 이동

이런식으로 충돌이 없어질 때 까지 sub-problem을 병합하며 A를 반복해서 수행한다. 이때 line 6의 경우 생략 가능한데, 너무 무차별적으로 Sub-problem이 합쳐지는것을 경계한 것 같다. ID는 A자체를 변형한게 아닌, 그 아래서 계산되는 base Algorithm이기 때문에 뒤에서 소개할 ICTS에서도 사용가능하다고 한다.

이때까지 ICTS이전의 MAPF 알고리즘에 대해 정리해봤는데, 별로 중요해보이지 않거나 간단한 내용은 생략된 내용이 있으니 필요한 사람은 해당 논문을 보고 자세히 확인하면 될 것 같다.

3. ICTS

드디어 대망의 ICTS에 대해 설명할 차례가 되었다. ICTS는 MAPF를 두가지 문제로 나눠서 해석했다.

1. 최적의 솔루션에서 각 agent별 경로비용을 구하는 문제
2. 주어진 경로비용을 만족하면서 각 agent별 충돌 없는 경로를 생성하는 문제

이렇게 정의된 문제를 해결하기 위해 ICTS는 두 레벨로 나눠 설계되었는데, 각 레벨에 대해 자세히 알아보자.

High-level Search

가장 먼저 High-level Search에서는 각 에이전트에 경로의 cost를 정한다. 이 cost를 만족하는 경로가 실제로 있는지 없는지 여부는 신경쓰지 않는다. 즉 k개의 agent가 있을 때 $[C_1, C_2, … , C_k]$로 표현되는 $k$-vector를 정하게 된다.

이러한 이러한 $k$-vector 공간을 탐색하기 위해 ICT(Increasing Cost Tree)의 루트 노드부터 너비우선탐색을 통해 탐색하게 된다. ICT의 Root Node는 $[opt_1, opt_2, … , opt_k]$로 정의되고 $opt_i$는 $i$번째 agent의 시작 정점부터 끝 정점까지의 최단거리이다. 또한 부모노드가 $[C_1, C_2, … , C_k]$으로 정의될 때 자식노드는 $[C_1, C_2, … , C_i+1 , … , C_k]$로 정의 된다. 즉 depth가 1씩 내려갈때 마다 vector의 합은 1씩 증가하는 것이다. agent가 3개인 ICT는 아래 그림과 같다.

ICT는 하나의 노드가 k개의 자식노드를 가질 수 있기 때문에 지수적인 시간복잡도를 가질수 있지만, 같은 depth에서는 벡터 요소 합이 모두 같기 때문에 실제로는 위 그림과 같이 중복된 노드를 생략 할 수 있다.

Low-level Search

Low-level Search는 High-level Search에서 정해진 경로비용으로 충돌 없는 경로 조합을 생성할 수 있는지 여부를 판단하는 알고리즘이다. 하지만 특정 cost의 경로의 가짓수는 너무 많아서 일반적인 방법으로는 경로조합을 생성하기 힘들다. ICTS에서는 이러한 문제를 해결하기 위해 MDD(Multi-Valued Decision Diagram)를 사용하여 경로조합별 충돌여부를 빠르게 계산하였다.

4. MDD(Multi-Valued Decision Diagram)

ICTS에서는 길이가 $C_i$인 agnet $a_i$의 경로들을 저장하기 위해 MDD라는 자료구조를 사용한다. MDD는 단순하게 사이클이 없는 단방향 그래프의 일종인데, 과연 어떻게 만드는지 알아보자.

MDD는 우선 위 그림과 같이 생겼다. $MDD_i^c$는 i번째 agent $a_i$가 시작 정점부터 목표 정점까지 $c$시간에 도달하는 모든 경로를 저장하는 그래프라고 생각하면 된다. 그래프 상에서 각 node는 depth 시간에 가능한 $a_i$의 상태를 나타내고, 부모자식관계는 부모상태에서 자식상태로 이동이 가능함을 나타낸다. 써놓고 보니 단순한데 위의 MDD를 깊이우선 탐색으로 생성하는 코드를 보면 더 이해하기 쉬울 것 같다.

그렇다면 MDD를 이용해서 어떻게 충돌이 없는 경로가 있다는것을 알 수 있을까? 해당 논문에서는 2개 로봇에 대해 먼저 확인하고 $k>2$인 경우에 대해 일반화 하여 충돌 여부 검사방식에 대해 증명하였다.

우선 두 에이전트와 $a_i, a_j$ 그리고 각각 할당된 cost $[c, d]$에 대해 $MDD^c_i, MDD^d_j$가 있다고 해보자. 이때 $c$와 $d$가 다른경우 짧은쪽에 가짜 골 노드를 넣어줘서 도착 이후의 시간에도 goal노드에 있다고 가정한다. 그 경우 문제를 일반화 하여 $MDD_i, MDD_j$로 정의 할 수 있다.

$MDD_i, MDD_j$가 있다면 교차 곱을 통해 $MMD_{ij}$또한 위의 그림같이 계산 할 수 있다. 이때 교차 곱을 통해 생성된 $MMD_{ij}$의 node는 $a_i, a_j$의 depth 시간에서의 각각의 위치를 나타낸다. 그렇기 때문에 특정 노드의 값이 같으면 충돌이라는것을 알 수 있다.

이 뒤로는 단순 시간복잡도 계산, 증명같은 부분이라 핵심아이디어는 아니기 때문에 생략하겠다. 간단히 계산해보면 low level의 시간복잡도는 depth마다 교차곱을 따로 할 수 있기 때문에 timestep마다 상, 하, 좌, 우, 대기 총 5가지 움직임이 있을 때 $O(t5^k)$이다.

후기

이렇게 최적의 해를 보장하는 MAPF알고리즘인 ICTS에 대해 정리해보았다. ICTS도 결국에는 A* 기반의 알고리즘 처럼 모든 agent의 움직임을 한번에 고려하는 알고리즘이었는데, 그렇다 보니 기본적으로 시간복잡도가 얘도 만만치 않고, CBS처럼 휴리스틱하게 문제를 경량화 할 수 있는 여지가 좀 적은거 같아보인다.