Priority inheritance with backtracking for iterative multi-agent path finding

이번에 소개할 알고리즘 Priority inheritance with backtracking for iterative multi-agent path finding(이하 PIBT)에서는 기존에 소개되었던 CBS계열 알고리즘과 다르게 여러 에이전트의 인접한 움직임에 초점을 맞추어 단기적인 솔루션을 만들어내는 방법이다. 이때 PIBT를 통해 얻어진 단기적인 솔루션을 반복적으로 수행하면 유한시간내에 모든 agent들이 도착할 수 있다는것을 보장할 수 있다.

이번 논문을 읽으면서 들었던 생각은 각 로봇은 process, thread이고, 로봇이 움직일 수 있는 맵들은 공유자원이라고 가정하여, 운영체제에서 각 프로세스간의 공유자원 데드락 문제를 해결하는 알고리즘과 비슷하다는 생각이 들었다. 과연 어떤 방식으로 계산하고 동작하길래, 단기솔루션만으로 데드락에 빠지지 않고, 항상 모든 로봇이 목적지에 도달 할 수 있다는 보장을 할 수 있을까? 한번 논문을 정리하고 알아보겠다.


PIBT

Priority Inheritance with Backtracking (PIBT)는 다중 에이전트가 충돌 없이 경로를 계획하도록 돕는 MAPF 알고리즘의 일종으로, 우선순위를 기반으로 경로를 탐색한다. 이때 우선순위 순서대로 경로를 탐색하고, 길이 막히면 낮은 우선순위 에이전트에게 자신의 우선순위를 일시적으로 넘겨주어 길을 양보하게 한다. 이때 재귀적인 알고리즘을 통해 교착을 방지하고, 유한시간 내에 도착함을 보장하는데, 어떻게 하는건지 간단히 알아보자.

Priority Based Planning

우선 PIBT는 MAPF문제를 해결하기위해 반복적으로 one-timestep에서 각 로봇이 어떻게 움직여야 할지 계산한다. 이때 각 에이전트간의 우선순위를 지정하고, 우선순위가 높은 에이전트부터 다음 timestep에서 도달할 경로를 이웃 노드를 선택하고, 그런 다음 에이전트는 우선순위가 높은 에이전트가 요청한 노드를 피하면서 우선순위가 낮은 순서대로 다음 위치를 순차적으로 결정한다.

Stuck Agent

하지만 이러한 우선순위 기반 경로탐색의 경우 위의 그림과 같이 우선순위가 높은 순서대로 에이전트가 $a_3, a_2, a_1$이 있다고 해보자. 이 상황에서 $a_1$은 자신보다 우선순위가 높은 $a_1, a_2$에 의해 현재 위치와 다음 timestep에서 갈 수 있는 모든 위치가 모두 선점되어 stuck agent가 된다. 결론적으로 위 그림의 예시와 같이 stuck agent는 다른 에이전트와의 충돌 없이는 어디에도 갈 수 없으므로 이러한 상황은 일종의 교착 상태로 간주할 수 있다.


Priority Inheritance

앞선 우선순위 기반의 경로탐색에서 stuck agent가 발생한 이유를 우선순위의 역전 현상으로 볼 수 있다. 이는 우선순위가 높은 $a_3$이 주장하는 자원을 보유한 $a_1$이 중간 우선순위를 가진 $a_2$가 보유한 자원을 얻지 못한다는 의미이다. 이러한 우선순위 역전문제를 처리하는 고전적인 방법은 우선순위 상속을 이용하는 것이다. 우선순위 상속은 우선순위가 높은 에이전트가 우선순위가 낮은 에이전트가 소유한 자원을 필요로 할 때, 자원을 요청한 에이전트의 우선순위를 자원을 소유한 에이전트에 상속하여 빠르게 일시적으로 우선순위 레벨을 조정하는 방법이다.

Priority Inheritance

위 그림은 그 이유는 우선순위가 낮은 $a_1$이 보유한 자원을 주장하는 $a_3$의 우선순위를 일시적으로 상속을 받기 때문에 일시적으로 $a_1$의 우선순위가 $a_2$보다 높아져 결과적으로 오른쪽 그림과 같이 움직이게 되어 교착을 회피하여 모든 에이전트가 움직일 수 있게 된다.


Backtracking

우선순위 상속으로도 완벽하게 해결할 수 없다. 아래 그림과 같이 복잡한 상황에서의 우선순위 상속에 대해 간단하게 예를 들어보자. 먼저 $a_7$은 우선순위가 최상위, $a_3$는 최하위의 우선순위를 갖는다고 생각해보자. 아래 그림은 우선순위가 연속적으로 상속되어 $a_7 \rightarrow a_6 \rightarrow a_5 \rightarrow a_4 \rightarrow a_3$ 순서로 상속됨을 의미한다. 이때 $a_3$는 같은 우선순위를 상속한 $a_6$, $a_4$에 의해 갈 수 있는 모든 공간이 점유되어있는 상태이고, 이미 해당 에이전트들은 우선순위를 상속받았기 때문에 추가로 상속할 수 없다. 그렇기 때문에 $a_3$는 연속적인 우선순위 상속에 의해 움직일 수 없는 상태가 된다고 볼 수 있다.

Complex Priority Inheritance

이런 문제를 해결할 수 있는 방법은 Backtracking 알고리즘을 사용하여 cycle을 발생시키지 않는 우선순위 순서를 찾아내는 것이다. 우선순위 상속을 실행하는 모든 에이전트는 상속 가능 여부(cycle을 포함하지 않는 상속이 가능한지) 결과를 재귀적으로 판단한다. 만약 가능하다면 해당 노드로 이동을 시키고, 그렇지 않으면 다른 노드에 대해 상속가능 여부를 판단해야 한다. 즉 재귀적으로 해당 노드로 이동이 가능한지 여부를 확인하는 것이다.

Backtracking기법은 에이전트 $a_i$를 움직이기 위해 필요한 노드에 $a_j$가 있을 때, $a_j$에 우선순위를 상속하여 움직임의 우선권을 주기 전에 정말로 $a_j$가 해당 노드를 제공하기 위해 피하는 움직임을 만들 수 있는지 여부를 확인하고 상속을 진행하는 것이다. 만약 위 그림에서의 $a_3$, $a_4$ 처럼 우선순위 상속을 통해 $a_6$가 요구하는 자원(현재 각 에이전트가 점유중인 셀)을 제공할 수 없다면, $a_5$는 $a_3$, $a_4$에 상속을 하지 않고 다른 에이전트에 상속을 하는 방법으로 문제를 해결하는 것이다. 다음은 우선순위 상속 리스트를 재귀적으로 구하는 로직이다.

우선순위 상속을 위한 재귀연산

우선 위 그림의 (a)항목에서 재귀적으로 $a_7 \rightarrow a_6 \rightarrow a_5 \rightarrow a_4 \rightarrow a_3$ 순으로 우선순위를 상속하는것을 탐색했다고 생각해보자. 이때 $a_3$는 연속적인 우선순위 상속에 의해 움직일 수 없는 상태가 되고, 상속이 실패함을 반환한다.$a_4$도 $a_3$의 위치를 제외하고는 추가로 탐색할 수 있는 곳이 없기 때문에 상속이 실패함을 반환환다. 이렇게 상속 실패 여부 반환을 나타내는것은 위 그림 (b)에서 속이 빈 화살표로 나타내어진다. $a_5$는 현재 위치에서 상속을 할 수 있는 이웃 에이전트 혹은 빈 셀이 상속에 실패한 $a_4$말고도 $a_1$이 있기 때문에 상속 실패를 반환하지 않고, 재귀적으로 탐색을 이어 나간다. 그 결과 그림 (c)와 같이 $a_7 \rightarrow a_6 \rightarrow a_5 \rightarrow a_1 \rightarrow a_2$ 순서로 우선순위를 상속하여 가장 우선순위가 높은 $a_7$ 목적지까지 가는데 비용이 가장 많이 줄어드는 $a_6$의 현재 점유중인 셀로 움직일 수 있게 된다. 이렇게 모든 에이전트 별 우선순위 순서대로 위와같은 로직을 진행하면, 적어도 가장 우선순위가 높은 에이전트는 그림 (d)와 같이 목적지로 가까워지는 결과를 얻을 수 있다.


Pseudo Code

PIBT의 로직은 아래 그림과 같은 pseudo code와 같다. 알고리즘이 단순하고, 직관적인 만큼 간단하게 설명만 하고 넘어가려고 한다.

PIBT 수도 코드

우선 매 timestep의 시작전에 각 에이전트별로 우선순위를 할당하고 정렬한다[Line 3~4]. 이때 골노드에 도착하지 않는 에이전트의 우선순위는 1씩 계속 증가하여 기아상태를 방지한다. 그리고 동일한 우선순위를 방지하고자 각 에이전트마다 서로 다른 $\epsilon$값을 추가하여 tie-breaking을 한다.

이렇게 각 에이전트별 우선순위가 정해졌다면, 높은 우선순위를 가진 에이전트부터 재귀적으로 다음 timestep에 도달할 위치를 찾는 procedure PIBT를 실행한다[Line 5~7].

procedure PIBT 함수는 재귀함수로써 우선순위를 상속해주는 에이전트 $a$와 우선순위를 상속해주는 에이전트 $b$를 인자로 받는다. 이때 만약 $a$에 상속해주는 에이전트가 없는 경우(재귀함수의 시작) $b=⊥$이다. 함수의 반환은 $valid$, $invalid$ 둘 중 하나로, 에이전트 $b$가 $a$의 위치로 이동할때 $a$가 stuck agent가 되는 경우 $invalid$, 아니면 $valid$를 반환한다.

우선 $C$를 $a$의 현재 위치와 이웃 노드들의 합집합으로 정의하고, 목표위치까지 거리 기준으로 오름차순 정렬을 한다[Line 9~10]. 그 후 가까운 노드 $v$부터 하나씩 유효성 검증($v$가 다른 에이전트의 다음 목적지로 고정된 경우, 상속한 에이전트 위치인경우)을 진행한다[Line 12~13]. 만약 두 검사를 모두 통과하면 노드 $v$에 다른 에이전트가 있는 경우 procedure PIBT를 통해 해당 에이전트에 대해 다시 유효성 검사를 진행한다[Line 15~16]. 만약 모든 검사를 통과하고나면 $valid$를 반환[Line 18]하고 그 위치를 해당 에이전트의 다음 목적지로 고정한다[Line 14]. 유효한 노드가 없으면 $invalid$를 반환한다[Line 21].


Theoretical analysis

사실 운영체제, 커널을 공부해봤다면 앞에서 언급한 priority inheritance, 기아를 방지하기 위한 aging등 이번 논문에서 제안한 아이디어들이 그렇게 새로운 아이디어는 아니라고 볼 수도 있다. 그렇기 때문에 내가 생각 했을 때 이번 논문에서의 키 아이디어는 “어떻게 MAPF도메인에서도 스케줄링 알고리즘이 문제를 해결할 수 있는지”에 대한 고찰이라고 생각한다. 이번 단락에서는 어떻게 MAPF 도메인에 스케줄링 알고리즘이 적용될 수 있고, 알고리즘에 대한 증명은 어떻게 되는지 한번 알아보려고 한다.

최우선순위 agent가 최단거리로 목적지에 도달 가능(Reachability)함

PIBT에서는 적절한 속성을 가진 그래프(예: 이중 연결 그래프)에서 결국 각자의 목적지에 도달한다는 것을 보장한다. 하지만 이런 Reachability를 보장하기 위해선 해당 논문에서 Lemma 1이라고 부르는, 아래와 같은 조건들이 모두 보장되어야 한다.

  1. $a^t$은 t 시점에서 가장 높은 우선순위를 가진 에이전트

  2. $v^*$은 $\pi^t[t]$(t 시점에서 $a^t$의 위치)의 이웃노드 중 $g^t$($a^t$의 목표 지점)로 가는 가장 가까운 노드

  3. $(\pi^t[t], v^*)$를 포함하는 간단한 사이클 $C = (\pi_1 [t], v^*, …)$가 항상 존재 (즉, 아래 그림과 같이 $a^t$가 이 순환을 따라 이동 가능)한다.

cycle_of_pibt

위 그림에서는 $t$시점에서 최우선순위 에이전트를 $a_1$이라고 정의한다.

그렇다면 어떻게 PIBT가 항상 Reachability를 보장하는지 알아보자. 우선 가장 높은 우선순위를 가진 에이전트 $a^t$를 위해 $PIBT(a^t, ⊥)$가 호출된다고 해보자. 이때, 아직 최상위 에이전트 $a^t$의 다음 경로를 찾는 단계기 때문에 아직 어떤 노드도 어떠한 에이전트에 의해서 점유되지 않은 상태이다. 결과적으로 $PIBT(a^t, ⊥)$는 $v^*$을 반환한다.

이제 다른 에이전트가 $v^*$을 점유하고 있는 상황 $\pi_{any}[t] = v^*$인 경우에도 $PIBT(a^t, ⊥)$가 $invalid$를 반환하지 않는다는것만 증명하면 된다. $C = (\pi^t[t], v*, …)$가 존재할 때, $PIBT(a^t, ⊥)$가 재귀적으로 $PIBT(a_{neighbor} ,a^t)$를 호출한 상황을 생각해보자. 이때 $\pi_{neighbor}[t] = v^*$이다. 이 상황에서 $PIBT(a_{neighbor} ,a^t)$가 재귀적으로 처리되면서, 점유되지 않은 하나의 노드가 하나라도 존재하면 $PIBT(a_{neighbor} ,a^t)$는 $valid$를 반환한다. 이때, 모든 노드가 agent에 의해 가득 차있더라도, $\pi^t[t]$는 최상위 우선순위 에이전트 $a^t$에 의해 다음 timestep에서 비워지는 노드이다. 그렇기 때문에 $C$의 존재로 인해 재귀적인 검색에서 항상 점유되어있지 않은 노드가 적어도 하나$(=\pi^t[t])$ 존재한다는 것을 항상 보장할 수 있고, $PIBT(a^t, ⊥)$는 항상 $valid$를 반환하여, 항상 최상위 우선순위 에이전트는 최단 경로(모든 시점에서 $v^*$은 목적지까지 가는 최단 경로에 포함되기 때문)로 목적지에 도착함을 보장할 수 있다.

모든 agent가 유한시간 안에 목적지에 도달 가능(Reachability)함

앞에서는 간단하게 최우선순위 에이전트가 최단거리로 목적지에 항상 도달 가능함을 증명하였다. 이번 단락에서는 PIBT가 모든 에이전트에 대해 유한시간안에 모든 에이전트가 목적지에 도달 가능함을 증명해보려고 한다. 먼저 최고 우선순위 에이전트는 앞에서 설명한 것과 같이 최단경로로 최대 $M$ timestep(최단 시간) 내에 목표에 도달한다. $M$ timestep이후에 해당 agent의 우선순위는 낮아져 새로운 에이전트가 최우선순위 에이전트로 설정된다. 새롭게 설정된 에이전트는 다시 최대 $M$시간동안 목적지로 이동한다. 앞의 과정을 에이전트의 갯수 $N$번만큼 반복하면 모든 에이전트는 적어도 한번 자신의 목적지에 도달할 수 있게 된다. 즉 모든 에이전트는 선형시간 $N \times M$ 내에 한번씩 목적지에 도달할 수 있게 되는것이다.


후기

이번 논문은 최적의 경로를 보장하지도, 각 에이전트가 움직이는 전체 경로가 나오지도 않는다. 오직 보장하는것은 “적어도 계속 이 알고리즘을 실행하다보면 언젠가는 모든 에이전트가 목표에 도달하게 된다”라는 전제 하나 뿐이다. 하지만 데드락이 생기지 않는다는 점에서 오히려 이 알고리즘은 Path Planning이 아니라 공유자원 스케줄링 분야와 더 비슷한것 같다. 대표적인 공유자원 문제인 식사하는 철학자 문제, 더 나아가 OS의 자원할당 문제에서도 가장 간단한 해결 방법은 우선순위를 두어 특정 자원에 대한 우선권을 갖게 만드는 것이다.

철학자 문제

철학자 문제에서는 서로 1:1로 싸워서(이때 철학자들의 전투력 서열에는 cycle이 존재하면 안된다) 이긴 사람이 진 사람의 포크를 강탈할 수 있게 하고, 운영체제에서는 Real-Time Operation System과 같이 선점형 스케줄링 알고리즘을 통해 특정 리소스를 우선순위가 높은 프로세스가 빼앗을 수 있도록 하는등의 방식으로 구현하는 것이다.

PIBT는 로봇을 일종의 프로세스, 로봇이 움직이는 그래프를 공유자원으로 생각하여 마치 공유자원을 스케줄링하듯이 경로탐색 문제를 해결한다. 물론 처음 말한것 처럼 최적의 경로도, 전체 경로도 제공하지 않기 때문에 한계점또한 명확하지만, 이번 논문에서 얻는 “MAPF가 꼭 경로탐색 도메인에 한정된 문제는 아니다.” 라는 인사이트는 유용하고, 또 잘 써먹을 수 있을 것 같다.