[Algorithm][Path Planning] MAPF? CCBS? 등 개념 / 종류 정리

순서

I. MAPF? SAPF? A*? 
II. CBS? CCBS?

---

I. MAPF? SAPF? A*?

Path Finding을 하면서 용어가 너무 헷갈렸고, 종류가 헷갈렸다.
MAPF는 뭐고 CCBS는 뭐고 CBS는 뭐고 A*는 그럼 어디에 속하는 것이고 등등...

정리도 했던김에 글로 남기기...

가장 큰 대 분류는 아래 두 가지다.

1. SAPF (Single Agent Path Finding)
2. MAPF (Multi Agent Path Finding)

 

1. SAPF (Single Agent Path Finding)

A*, BFS, Dijkstra 등등 Path Planning 알고리즘이라고 보면 된다.

 

흔히 우리가 접하는 가장 기본적인 알고리즘들이다.
맵(미로) 격자가 있고 열심히 Queue로 길 찾아서 목표 지점으로 가는... 그런 배경이다.

보통 한 가지의 Agent만 가지고 알고리즘을 개발하고 최단 경로를 도출하는 것들이 여기에 속한다.

 

2. MAPF (Multi Agent Path Finding)

하나의 맵에서 SAPF를 사용하는 주체가 많은 것이다.

 

SAPF와 다른것은 Single Agent -> Multi Agent이다.

Multi Agent라고 특별한 알고리즘이 있지 않다.

1단계 : SAPF의 알고리즘을 사용하여 Single Agent의 최적 경로를 생성한다.
2단계 : 또 다른 Agent의 최적 경로를 생성하여 최종적으로 Multi Agent 경로를 생성한다.
            단! 2단계에선 각 Agent간 충돌을 방지하는 방법 중 한 가지를 택하여 사용한다.

여기서 말하는 1단계, 2단계가 흔히 논문들에서 말하는 MAPF의 두가지 단계이다.

예를 들면,
1. 경로탐색으로는 A*를 사용하고, 경로가 겹치지 않게 Time Table을 만들어야지!
2. 경로탐색으로는 BFS를 사용하고, 경로가 겹친 경우 각각 다시 탐색시켜야지!

등의 여러 방법, 조합이 있고 이에 따라서 다양한 MAPF가 존재한다.

 

---

II. CBS? CCBS?

 

1. 용어

CBS : Conflict Based Search
CCBS : Continuous Conflict Based Search.

MAPF를 사용하지만 각 Agent별 충돌을 무시할 수 있고, 충돌을 방지할 수 있다.

MAPF 중 충돌을 생각하여 방지하도록 하는 알고리즘이 CBS이다.

MAPF는 위에서 말한 2단계 (충돌 방지)가 핵심이긴하다...

따라서 CBS 는 MAPF를 위한 용어임을 알 수 있다. 즉, MAPF안에 CBS가 속해 있는 것이다.

 

2. Continuous CBS?

Conflict Based Search를 RealTime (ContinuousTime) Domain으로 풀어낸 것이다.

 

"충돌"을 생각해보자. 현실에서 자동차의 충돌, 혹은 Map에서의 충돌은 동일한 공간/시간에서 발생한다.

공간은 이해가 되지만 시간은 결국 내가 어떤 Time domain을 사용하느냐에 따라 다를 것이다.

따라서 여기서 말하는 Continuous는 Descrete Time - Continuous Time을 나누는 의미이고
현실 시간을 위한 개념이다.

따라서 Conflict Based Search를 어떤(Descrete? Continuous?) Time Domain을 가지고 할 것 인지에 관한 것이다.

가장 중요한 차이는

Descrete Time : 한 번에 한 격자만 이동하므로 정확히 같은 시간, 같은 공간에 있을 때 Conflict. (몸체가 충돌)
Continuous Time : 연속적이므로 격자간 이동하는 도중에 Conflict가 발생할 수 있음. (모서리로 충돌)

 

즉, 정리하면 Multi-Agent라는 것은 A*나 BFS등으로 각각 경로탐색을 하는 여러 Agent를 컨트롤 하는 것.
Continuous라는 것은 격자 맵이나 이산시간이 아닌 RealTime을 전제로 탐색한다는 것.