[Algorithm][Path Planning] MAPF(Multi Agent Path Finding) 종류

순서

I. MAPF란?
II. 종류

 

---

I. MAPF란?

 

A*나 Dijkstra BFS등을 사용하여 경로를 찾는 Single Agent들이 여러대가 있고,
여러대가 충돌없이 경로를 계획하는 것을 목적으로 함.

MAPF/CCBS등 개념정리

 

II. 종류

 

사실 딱히 다 알 필요는 없는데... 이런 것들이 있구나, 이건 아이디어 써볼만 하겠다.
느낌으로 비교, 정리.

M*, OD+ID, ICTS, MAPF/C, CBS/C, Push

대부분 아래 방식으로 나뉜다.

탐색 : Agent별 동시 탐색 vs 독립적 탐색
충돌 : 충돌난 Agent 한 번에 해결 vs 충돌 주범만 해결

 

---

1. M* (Multi-Agent A*)

탐색 : 다수 Agent 모두 동시 탐색

충돌 : 충돌 발생시마다 전체 Agent의 경로 재탐색

기타 : 계산 복잡도가 올라가고, Agent수에 따라 충돌 발생시 크게 영향받는다.

 

---

2. OD + ID (Operator Decomposition + Independence Detection)

개인적으로 CCBS 제외 눈에 띄던 기법

탐색 : 다수 Agent 개별 독립적 탐색. (순차적으로 탐색함)

충돌 : 충돌 발생시마다 독립적으로 경로 재탐색

기타 : 독립 탐색 - 충돌 해결을 위한 재탐색을 반복함. 계층적으로 수행되는 특징.

 

---

3. ICTS (Increasing Cost Time Search)

잘 모르겠음..ㅎ

탐색 : Agent의 경로 비용을 점진적으로 증가시키며 탐색

충돌 : 충돌시 일으킨 Agent 재탐색

기타 : 비용이 점진적으로 증가하여 초기에 빠르게 근사 해 찾는다, 탐색공간을 계층적으로 확장한다.

 

---

4. MAPF / C (MAPF with Continuous Time)

탐색 : 연속 시간에서의 경로탐색. (시간 Domain 설정이 중요)

충돌 : 충돌을 일으킨 Agent의 경로수정 / 이동시간 조정을 통해 해결한다.

 

---

 

5. Push and Swap, Push and Rotate

Agent별 DeadLock을 해결하는 방법으로도 사용된다.

탐색 : 타 Agent를 고려하지 않는 단순 Search

충돌 : 타 Agent를 다른곳으로 밀어내어 해결

기타 : Swap(2개 Agent) - 나와 위치를 교환함, Rotate(3개 이상 Agent) - 서로의 위치를 회전교환한다.

 

---

6. CBS (Conflict - Based Search) 계열

탐색 : 모든 Agent의 경로를 동시에 고려함. 모든 Agent의 경로 관리를 통해 제약 조건을 추가하며 탐색

충돌 : 충돌이 발생한 경우만 경로를 분할해 재탐색 진행

6.1 ECBS (Enhanced CBS) - Huristic으로 탐색 효율성 증대
6.2 CCBS (Continuous CBS) - 연속 시간에서의 탐색
6.3 MA-CBS (Meta-Agent CBS) - Agent들을 그룹으로 묶어 CBS적용.