Lacam2의 핵심 내용
Lacam2라고도 불리는 Improving Lacam입니다.
대규모 로봇의 경로계산을 위한 MAPF알고리즘이며, PIBT와 Lacam논문을 읽어야 이해할 수 있습니다.
왜냐면 Lacam2의 컨트리뷰션은
1. Lacam을 Anytime형식으로 개량
2. PIBT결과물인 Configuration 초기 산출속도 개선
이거든요.
사실상 기존 Lacam의 성능과 편의성을 끌어올린 기술적 논문이라고 보면 될것같습니다.
Lacam2의 원리
자 그럼 어떻게 Lacam를 Anytime으로 개량할 수 있었을까요
(Lacam과 PIBT에 대한 내용은 생략하겠습니다.. 이전포스트에서 다뤄졌기도 하고 내용이많아서.)
Lacam2가 Lacam과 다른 두가지 요소는 아래와 같습니다.
1. Lacam2는 목표 Configuration을 찾아도 계속 진행됩니다.
2. Lacam2는 필요에 따라 탐색 노드 사이의 부모관계를 재정의합니다.
목표 Config를 찾으면 종료되는 Lacam과는 다르게, Lacam2는 high-level에 노드가 전부 사라질때까지 진행됩니다.
그렇기때문에 목표 config가 찾아진 이후라면 사용자는 언제든지 Lacam2를 종료해서 경로를 획득할 수 있습니다.
우선 초기해를 찾아놓은 다음, 시간을 많이줄수록 고품질의 경로를 반환하는 형식이죠.
사실 이부분은 간단한 편의개선의 문제이고, 복잡하거나 어려운 내용은 아닙니다.
2번인 부모관계 재정의입니다. 위에서 하나의 원은 하나의 Configuration을 의미합니다. Lacam과는 다르게 Configuration이 단순히 high-level의 스택에 담겨있지 않고, neighbor 정보를 가지고있습니다. 그래서 새로운 Configuration이 등장하면 이것이 기존에 탐색되었던 Configuration인지 검사하고, 탐색된 Config라면, neighbor에 추가하는거죠.
빨간색 숫자는 코스트인데, neighbor정보가 바뀌며 코스트도 갱신해주는 것을 확인할 수 있습니다.
위 두가지 방법을 통해 Anytime으로 변환했다고 할 수 있습니다.
목표 지점을 찾아도 종료하지 않고 high-level의 남은 configuration에 대해서 연산을 수행하고,
configuration을 탐색할 때마다 기존의 최소비용과 비교하며 코스트 감소가능한 configuration을 찾아 cost를 낮춰주죠.
가장 cost가 낮은 goal configuration은 들고있다가 사용자가 프로그램을 종료하면 반환합니다.
그렇다면 두번째 컨트리뷰션인 Configuration 초기 산출속도 개선 부분을 보겠습니다.
Lacam2에서는 CG(Configuration generator)를 이것저것 바꿨습니다.
Lacam시리즈 내내 등장하는 CG는 로봇의 다음스텝을 결정하는 핵심 알고리즘이기 때문에 역할이 매우 크죠.
Lacam에서는 PIBT를 CG로 사용했습니다. 하지만 PIBT는 문제가 하나 있었는데, 매번 로봇의 우선순위가 바뀌기때문에 위와같은 상황에서 라이블록에 빠져버릴 수 있다는거죠.
* 라이블록 : 로봇이 동일한 경로를 반복하지만 실제로는 아무 진전이 없는 상황. Deadlock(교착)의 움직이는버젼
저자는 위 문제를 Configuration을 역전시켜 해결했습니다.
3번째줄처럼 만약 두 로봇이 위치를 바꿔야한다면, 코스트 순서대로 정렬되어있던 Configuration을 역전시켜 오히려 Goal에서 멀어지는 Configuration을 반환하도록 한것이죠.
기존에는Fig5처럼 1번과 2번로봇이 서로 우선순위를 번갈아 획득하며 코스트를 줄이려 같은 경로를 반복했다면,
Swap PIBT에서는 가장 높은 우선순위를획득한 로봇이 위치바꿈상태가 아닐때까지 멀어지는 경로를 반환해서, 멀어지면 우선순위를 뺏기는 방식으로 자연스럽게 해결되는거죠.
아니 그러면 어떻게 위치바꿈이 필요한 상태를 파악하냐!!
이건 룰베이스로 구현했다고 합니다. 대략적인 설명이 있긴한데, 내가 갈곳이 한군데밖에 없으면서 누군가 내위치를 필요로할때 내 차수가 1이면서....등등 규칙이 있고 해당 규칙에 맞는 애들은 위치바꿈이 필요하다고 판단합니다. 이것저것 복잡해요.
저자는 완벽한 알고리즘을 짤 계획은 아니었다고 합니다. Swap은 보조기능으로 반복상태만 적절하게 해결해주면, 이 과정에서 발생하는 비효율적인 과정들은 Lacam에 의해 최적화가 되니까요.
Lacam2의 결과
CG의 성능을 개선시킨 만큼 매우 어려운 예제를 들고왔네요. 최적성 중심의 알고리즘들조차 풀어내지 못하는 어려운 상황들을 해결하는것이 인상적입니다.
4번째 창고 케이스의 경우만 제외하면 Lacam의 결과 그래프와 크게 다른게 없습니다.
사실 이전 논문인 Lacam을 읽어보신 분들은 알겠지만, 4번째 창고케이스는 논문에서 특별히 약점이라고 다뤘던 만큼이나 신경을 쓰신것같아요.
좁은 공간에서 발생하는 PIBT의 한계를 Configuration Reverse를 통해 해결해서 성능을 끌어올린게 가장 큰 의의가 아닌가 생각됩니다.
