PIBT란 무엇인가
PIBT는 대규모 에이전트의 실시간 경로생성을 위해 설계된 알고리즘입니다.
기존 알고리즘들은 연산량의 한계때문에 대규모&실시간 경로생성이 불가능했는데,
PIBT는 최적성을 포기하고 연산량을 크게 낮춰 수천대의 로봇경로를 실시간으로 생성가능합니다.
결국 최적성과 연산량의 trade-off인데, 줄어든 최적성에 비해 엄청난 연산량을 감소시켜 주목받았습니다.
PIBT가 지적한 한계
PIBT는 논문의 첫장부터 "one-shot" 알고리즘들의 한계를 서술했는데요, 원샷알고리즘은
* 모든 로봇이 동시에 움직임을 시작
* 모든 로봇이 각자의 목적지를 동시에 입력받음
을 전제로 수행되는 알고리즘입니다.
하지만 실제로 MAPF를 사용하는 현장에서는, 모든 로봇들의 상태도 다르고 명령이 입력되는 시간도 다르며, 로봇마다 목적지가 할당될수도 쉬고있을수도 있습니다. 이런 상황에선 수백대 로봇의 경로를 수시로 계획해야하는데, 기존 알고리즘들에는 한계가 있었습니다. 왜냐하면 기존의 CBS같은 알고리즘들은 최적성을 중시하여 완벽한 경로를 설계하기 위해서 연산소모가 심했기 때문이죠.
최적성이 높은 알고리즘들은 원샷 상태를 해결하는 완벽한 경로를 출력하는 작업에 뛰어나지만,
연속적인 시간의 흐름에서 발생하는 문제를 실시간으로 처리하는 환경에서는 사용이 불가능합니다.
너무오래걸려요.
그래서 저자는 수백대 로봇 규모에서도 합리적인 시간 안에 모든 로봇의 도착을 보장하는 MAPF인 PIBT를 통해 이 한계를 해결합니다.
PIBT 알고리즘 설명
pibt는 우선 모든 로봇에게 우선순위를 매깁니다.
고정된 ID, 거리, 목표에 대한 중요도 etc...... 그럴듯해보이는 기준이면 뭐든지 ok입니다.
사실 무작위로 우선순위 매겨도 문제없어요.
이후 각 로봇한테 자신이 가고싶은 노드를 선택하게 합니다.
각 로봇들은 자신이 이동가능한 모든 위치의 휴리스틱을 계산해서, 비용이 낮은 순서대로 정렬하죠.
모든 로봇에게 우선순위를 부여한 후, 해당 우선순위에 따라 자신이 가고싶은 노드를 선택하는 과정을 거칩니다.
이 때 모든 로봇이 자신이 가고싶은 노드에 간다면 문제가 없겠으나.....
당연하게도 이 과정에서 교착이나 충돌이 발생합니다. 다른 로봇이 위치한 곳으로 이동하고싶을수도있고, 서로다른 로봇끼리 같은 위치로 이동하고싶을수도 있죠.
이 문제를 해결하는것이 본 논문의 핵심 알고리즘입니다.
벌써 머리가 아프죠.
저는 머리가 나빠서 이해하는데 오래걸렸는데...... 저와같은 지능을 지닌 사람들을 돕기위해 Fig1을 통해쉽게 풀어서 써볼게요.
우선 a7~1의 로봇이 순서대로 Line5 for문에서 PIBT로 호출됩니다.
Fig1, a에서 보시면
1. 가장 높은 우선순위인 a7에게 PIBT(a7,ㅗ) 호출 (Line 6)
2. a7는 오른쪽 자리를 예약하며 PIBT(a6, a7)호출
3. a6은 자신이 가고싶은 위치 (아래) 예약하고 PIBT(a5,a6)호출.
a5, 4도 마찬가지로 각각 PIBT호출(각각 pibt(a4,a5), pibt(a3,a4) 호출)
4. a3은 갈곳이 없으므로 Invalid 신호를 반환
이 때 a7654는 가고싶은 위치를 예약하고, 해당 위치에 있는 로봇에게 pibt를 호출했는데, a3은 Invalid를 반환했죠.
a7654와 a3의 차이점은 a3에게는 선택권이 없다는 것입니다....
왜냐하면 로봇은
"내가 가고싶은곳에 다른 로봇이 있는 상태" and "해당 로봇은 예약이 없는 상태"
일 때 차례를 넘겨 PIBT를 재귀적으로 호출할 수 있기 때문입니다. (Algorithm1, Line15)
a6이 예약할 시점에는 a5는 아무것도 예약하지 않았으며,
a5가 예약할 시점에는 a4도 마찬가지로 예약하지 않은 상태입니다. pibt호출 가능하죠.
하지만 a3의 경우는 왼쪽은 a7에게 예약되었으며, 아래는 a5에게 예약되었습니다.
이런 경우 16번째 라인과 같이 Invaild 상태가 됩니다.
그러면 이제 invalid발생 전 가장 마지막으로 호출된 a4의 for문이 돌겠죠. 16번라인 continue를 슥 지나면서요.
하지만 윗방향 선택지를 continue로 넘긴 a4에게는 왼쪽방향 선택지밖에 없습니다. 왼쪽방향은 a6에게 예약되었군요.
for문 종료되고 invalid 반환하며 종료합니다.
다음순서는 a5입니다. a5는 오른쪽방향의 선택지가 실패했으니 왼쪽과 위쪽 남았는데요, 어느걸 먼저하던 결과는 같습니다. 위쪽은 a7의 예약지점이고, 왼쪽이 남았네요. 그러면 이 때 a5는 PIBT(a1, a5)를 호출하게됩니다.
그러면 a1에게는 3개의 선택지를 가지게 됩니다. 오른쪽, 위, 왼쪽.
위와 오른쪽은 각각 a7, a5로 이미 자신이 가고싶은 곳을 예약한 상급자입니다. a2밖에 선택지가 없군요.
a1은 a2에게 비켜줄수 있냐며 PIBT(a2, a1)을 호출합니다.
핵심입니다핵심핵심.
a1이 자신보다 우선순위가 높은 a2에게 비킬수 있냐며 pibt를 호출했어요. 이건 a1이 a5에게 명령받아서, a2보다 빠르게 호출되었기 때문입니다.
이후에는 a2는 위쪽에 아무것도 없으니 위쪽을 예약하고, valid를 반환합니다.
그러면 자연스럽게 모든 재귀문이 다 끝나게됩니다.
{예약을 성공한 a2, a1, a5, a6, a7은 자신의 예약 위치로 이동,
예약에 실패한 a3, a4는 자신의 위치에서 대기}
가 한 스텝의 결과가 되는 것입니다.
다음스텝에서도 위 과정을 반복하고요.
모든 로봇이 자신의 목적지에 도달할때까지 반복반복...끝!
이젠 논문의 제목을 이해할 수 있어요.
PIBT는 Priority inheritance with backtracking의 약자입니다.
평소같았으면 우선순위가 높은 a2가 a1보다 빨리 호출되지만, a1은 a5에게 Priority를 inheritance 받아서, 자신보다 우선순위가 높은 a2를 움직일 수 있는 유연성을 가지게 된것입니다.
그리고 이런 과정을 재귀를 통한 backtracking방법으로 모든 로봇이 자신의 다음스텝 위치를 결정하게 하는거죠.
여기까지만 읽으셔도 PIBT 이해 끝입니다.
이후 내용들은 위 방법이 어떻게 모든 로봇의 도착을 보장하는지에 대한 증명이나,
PIBT가 실패하게되는 조건, 평가 이렇게 하고 끝나요.
PIBT 알고리즘의 도착 및 연산시간 보장 증명
PIBT 도착및 연산시간 보장은 여러 단계를 거쳐 증명됩니다.
Lemma 1. 가장높은 우선순위의 로봇은 항상 자신이 이동하고자 하는 위치로 이동가능하다. 단, 경로가 단순 사이클 구조를 지닐 경우에만.
단순 사이클구조라니.. 뭘까용. 아래그림을봅시다.
로봇 a1, a2,,,ak가 있다고 가정합시다.
낮은순서대로 우선순위가 높다고도 가정하죠. a1이 제일높음
Fig4를 보시면 a2의 위아래는 invalid를 반환했고, a3의 위아래도 invalid를 반환했습니다.
모든 로봇이 좌우로밖에 이동할수 없고, ak까지 오면 a1과 이어지는군요.
이것은 이동가능한 로봇들이 단순원형구조 위에 있다고 생각할 수 있습니다.
로봇이 하나의 원형띠 위에있는것처럼만 움직일 수 있어요.
Fig1 a)에서 a76215와 같은 상황입니다.
a3과 a4가 invalid를 반환해서, 모양이 띠처럼 변해있죠.
다시 Fig4에서 설명하면,
Lemma 1은 반드시 로봇 a1은 v*로 이동가능해야한다. 라는 뜻입니다.
이 때
a1은 반드시 v*에 도착할 수 있어야한다는 명제는
a1에 의해 PIBT호출된 a2가 반드시 invalid를 반환하지 않는다라는 명제와 동치입니다.
v*에 위치한 a2가 vaild를 반환하여 어디론가 이동한다면, a1은 반드시 v*에 도착가능하기 때문이죠.
또한 a2가 invalid를 반환하면 a1는 절대 v*에 도달할수 없습니다.
위 명제는
a2에 의해 PIBT호출된 a3가 반드시 invalid를 반환하지 않는다라는 명제와 동치입니다.
a3이 이동가능하다면, a2또한 이동가능해지고, a2가 이동가능하다면 a1은 이동가능합니다.
반복반복...
결국 MAPF의 기본 명제인 모든 로봇은 노드위에있고, 노드의 숫자는 로봇보다 많다를 생각했을 때,
마지막 호출되는 로봇은 남은장소로 이동하게되고, 이에따라 마지막 호출되는 로봇을 부른 로봇도, 그걸 부른 로봇도...로봇도로봇도... 가장 우선순위가 높은 로봇도 도착 가능하다는 것입니다.
단, 위와 같이 단순사이클 형태일때만요.
(이 형태가 아닌 경우는 실패조건에서 설명)
Theorem 2. 인접한 모든 노드쌍에 대해 단순사이클이 존재하는 상태에서 PIBT는 반드시 모든 로봇의 충돌없는 경로집합을 생성하며, diam(G) × |A| 보다 작은 스텝안에 로봇은 목표에 도착한다.
Theorem2는 1에서 확장되어, 모든 로봇의 도착을 보장합니다.
1에서는 최우선순위 로봇의 이동을 보장했습니다. 이에따라 언젠가 최우선순위 로봇은 자신의 목적지에 도달하게되죠.
그렇다면 2번째 우선순위의 로봇이 최우선순위 로봇이됩니다.
이에따라 2번째 로봇도 언젠가는 자신의 목적지에 반드시 도달...3..4...5...
이 논문은 재귀가 많네요.
단, 중요한 한계가 있는데 PIBT는 동시에 모든 로봇이 자신의 목적지에 도달한 상태를 보장하지 않는다는 것입니다.
위 내용을 자세히 보면.. 각 로봇은 언젠가 자신의 목적지에 도달하지만, 다음 우선순위를 가진 로봇이 이동을 시작하면 비켜줘야합니다.
Proposition 3. PIBT알고리즘의 한 스텝은 아래의 시간복잡도를 가진다.
1과2가 PIBT의 도착을 증명한다면, 3에서는 PIBT는 반드시 타당한 시간에 끝남을 보장해주는 원리를 증명합니다.
.....생략
PIBT 알고리즘의 실패조건
실패조건이 명료한데요... 앞서 했던 증명들의 전제인 단순사이클이 위반된 경우입니다.
a1은 오른쪽으로 가려하지만, a2는 이동가능한 단순사이클이 없습니다.
이런경우는 어떻게해결해야할까요. 해결하지 못하는걸까요
PIBT 의 한계 극복
사실 PIBT도 참 한계가 많습니다. 수백대의 로봇경로를 빠르게 생성해내지만
환경은 사이클 구조를 만족해야하며, 단순히 휴리스틱 기반으로 움직이니 최적성도 부족하구요.
위와같은 단순한 문제에서도 한계를 드러냅니다.
하지만 걱정하지 않으셔도 됩니다.
저자는 다음 논문 PIBT를 기반으로 작동하는 Lacam을 제작했고, 위 문제들을 모조리 해결했어요.
(하지만 여전히 최적성에는 한계가 있지만요)
다음번에는 Lacam 논문을 정리해보겠습니다.
마무리
이런 알고리즘은 어떻게 생각해내는걸까요?
22장분량으로 상세하게 설명해주신 논문을 읽어도 겨우 이해했는데,
백지에서 이런 알고리즘을 떠올리는 사람들을 보면 천재인가 싶네요.
똑똑하다똑똑해
