[Algorithm][Path Planning] OD+ID vs CBS

순서

I. OD + ID의 동작방식
II. CBS의 동작방식
III. 일반적으로 CBS를 채택하는 이유

 

---

다양한 MAPF 종류들을 보며 OD+ID에 시선이 갔다.

현재 내가 사용중인 CBS가 몰랐던 OD+ID와 비슷해 보였고, OD+ID를 왜 안쓰지? 라는 의문점이 생겼기 때문..

결과적으로,
OD+ID
  독립적으로 각각 경로를 다 만들어 놓고 충돌이 발생하면, 그제서야 해결. 속도가 빠르다.

CBS
  개별 경로 탐색을 하며 탐색 도중 발생한 충돌에 대해 조건 세분화를 시켜 탐색을 마무리 한다.
충돌을 명확한 Constraint를 가지고 해결할 수 있고 복잡한 문제상황을 풀어낼 수 있다.

오묘하게 비슷한듯 다르다...

 

I. OD + ID의 동작방식

OD (Operator Decomposition) + ID (Independence Detection)

탐색 - ID (독립성 탐지)
  각각 Agent들을 독립적으로 관리한다. 동시에 모두를 고려하여 Planning하는 것이 아닌,
평소에 A*문제 풀듯이 개별 Agent별로 경로 Planning을 진행하여 완료한다.

충돌 - OD (연산 분해)
  다 Planning이 완료 된 후, 충돌을 감지한다면 충돌을 해결하기 위한(주로 발생시킨) Agent만 별도로 재탐색을 진행한다.

즉, 개별 경로탐색과 충돌시에도 개별로 재탐색을 진행하기에 효율적이고, 내가 현재 쓰는 방식과 유사하다고 생각했었다.

 

---

II. CBS의 동작방식

CBS (Conflict - Based Search)

Low-Level Search (탐색) 
  각 Agent의 경로를 찾는다.

High-Level Search(충돌) - 제약조건을 통한 분기
  한 Agent가 경로 탐색도중 충돌을 발견하면 Constraint를 설정해 분기를 생성하여 탐색한다.

예를 들면,충돌이 발생하는 Path에서 기다렸다가 갈 것인가(Time Constraint) 다른 경로로 우회할 것인가(Space Constraint) 조건을 통해 선택하게 함.

탐색시 결국 G값에 최종 시간이 예측되므로 나는 두 경우의 Search Node를 모두 만들어 비교하는 A*를 사용한다.

 

---

III. 일반적으로 CBS를 채택하는 이유

1. 충돌 해결의 명확성
  충돌을 위한 제약조건을 추가하는 면이 직관적으로 해결의 명확성을 제공할 수 있다.

2. 확장성
  제약조건을 조작함으로 인해 다양한 환경에서 유연하게 적용될 수 있다.

3.복잡한 충돌상황 해결
  OD+ID는 독립성을 최대한 활용하기에 효율적으로 보이지만 복잡한 충돌 상황에서는 해결이 효과적이지 못함.
(이미 경로를 다 뽑아놓고 나중에 충돌을 확인하기 때문)

4. 단순한 알고리즘
  개발 유지보수의 장점이 있다.

+ 이미 물류체계에서 검증이 많이 되었다고 한다.

다만,

1. 실시간 성능이 더 중요한 경우
2. 단순한 환경의 경우 등

환경에 따라 OD+ID가 더 적합한 알고리즘이 될 수 있다.