Multi-Agent Path Finding이 무엇일까. . .

2주전 즈음 multi agent의 충돌 문제와 관련된 논문을 읽다가 관심이 좀 생겼는데, 좀 더 큰 틀에서의 문제에 대해 알아보고 이후에 시간내서 알아볼 예정

AGV (Automated Guided Vehicle)은 물류/유통 센터나 공항 터미널 시설에서 많이 활용된다고 한다.

물류 분야에서 보면 Amazon Robotics가 처음 도입했던 RMFS ( Robotic Mobile Fulfillment System)이 있다.
이 시스템은 피킹을 위해 작업자가 선반까지 이동하는 대신 AGV와 함께 협업 함에 따라 소요되던 시간의 절반 이상을 절약할 수 있었는데,
이는 장애물이 없는 정해진 공간 환경에서 반복/지속적인 작업을 수행 하는 것이 매우 효과적이기 때문이다.
- 물류센터와 같은 환경에 로봇을 도입함으로써 작업자의 일을 덜어주어 작업 능률을 상승시키고 주문 처리량을 크게 향상

최근에는 AMR 로봇 도입 추세에 있는데, AGV 로봇 도입 목적과 같이 생산성, 효율성 향상에 더불어 로봇 활용에 대한 확장성과 범용성을 함께 갖추기 위함이다.

AMR은 자신의 위치와 주변 환경 변화를 인식할 수 있기 때문에 물류 센터 내의 작업장과 선반과 같은 공간 배치를 변경하지 않고 손쉽게 도입 및 운영이 가능하고 AMR 로봇과 작업자가 협업하는 형태의 물류센터 피킹 작업 역시 RMFS와 마찬가지로 작업자 대신 AMR이 선반이나 포장 위치로 이동하고, 작업자는 로봇의 적재공간에 물건을 놓거나 꺼내기만 하는 방식이다.
-AGV는 장애물이 없는 정해진 공간에서 활용할 수 있지만 AMR은 자신의 위치 그리고 주변 환경을 인지할 수 있기 때문에 AGV의 장점(생산성 효율성 향상)과 확장성과 범용성까지 갖춤

---

하지만 로봇들은 할당된 업무에 따라 각각의 목적지를 향해 잦은 빈도로 이동해야 하는데, 중간에 충돌이나 교착상태에 이를 수 있는 문제가 있기때문에 사전에 경로를 계획하고, 계획된 경로를 토대로 로봇들을 움직이는 방법을 찾아야한다.
이러한 방법을 찾는 것이 MAPF(Multi-Agent Path Finding)문제 이다.

MAPF 문제를 해결하는 대표적인 방법
Priority Planning(PP): 로봇들 간의 우선순위를 기준으로 기존에 탐색된 로봇들의 경로를 장애물로 삼아 순서대로 경로를 탐색하는 방식
Independent Detection (ID): 개별 로봇의 경로에서 충돌이 발생되는 로봇들을 그룹으로 합치고 각각의 개별 그룹에 대해 A* 탐색을 수행하는 방식
Conflict Based Search (CBS): 로봇들 각각의 경로를 기준으로 중간에 충돌되는 구간을 피할 수 있는 최적해가 도출될 때까지 탐색을 전개하는 방식

목적함수에 따라 최적 혹은 그에 준하는 경로를 찾을 수 있고, 목적함수로 대개 모든 로봇의 경로 상 이동거리/시간의 합(sum of costs) 혹은 모든 로봇들 중 최대 소요시간/거리(makespan)을 사용한다고 함

---

이론 상 MAPF 문제의 해결 방식으로 충돌 없는 경로를 찾을 수 있지만, 시뮬레이션이 아니라 실제 현장에서 로봇을 운영해보면 찾아진 경로대로 로봇이 이동하지 않는 불일치 문제가 존재하고 원인은 실제 로봇의 움직임과 공간정보를 현실적인 시간 내에 정확하게 맞출 수 없기 때문이기라고 한다.

이러한 문제를 해결하기 위한 몇 가지 시도들이 있다고한다.
1. 오류가 예측되는 시점에 로봇들의 경로를 새롭게 탐색하고 찾아진 경로를 다시 따라가도록 하는 방법

2. 로봇의 움직임에 대한 불일치를 해소하기 위해 동역학 모델링을 도입해 MAPF 문제에 적용하는 방법

3. 로봇의 동역학적인 정보를 토대로 점유된 공간정보를 비교하는 방법.

추가적으로 이러한 방법들을 이용해 경로를 구성할 때
1. 토폴로지 형태의 그래프 경우 탐색 노드 개수가 적어지기 때문에 경로 계산에 필요한 연산량을 줄일 수 있지만, 이동 중간에 재경로 계획이 필요한 경우 정확한 위치에서 경로 탐색을 하기 어려움

2. 격자형태의 맵을 활용하는 경우 경로계산의 복잡도가 배우 높아지기 때문에 높은 빈도의 알고리즘 수행이 어려움