Improved CBS - CBS의 한계를 개선해보자! (3)

안녕하세요. 오늘은 Improved CBS(ICBS)에 대해서 공부하려고 합니다.

• BOYARSKI, Eli, et al. ICBS: Improved conflict-based search algorithm for multi-agent pathfinding. In: Twenty-Fourth International Joint Conference on Artificial Intelligence. 2015.

 

개인적인 감상으로는 ICBS 는 CBS에 좋다는 것들을 전부 섞은 느낌이 드네요 ㅋㅋㅋㅋ

 

Merge and Restart(MR), Prioritizing Conflicts(PC) 라는 새로운 개선 방법들도 제안되었는데요!

한번 자세히 살펴볼까요?

---

Meta Agent(MA), Bypassing Conflicts(BC) 그 다음은?

논문에서는 MA와 CBS의 한계를 밝히면서 MR, PC를 제안합니다.

MR부터 살펴보도록 하겠습니다.

 

MA의 한계 그리고 개선책 MR

MA는 Low level에서 찾은 경로의 연관성이 높은 에이전트끼리 묶어서 메타 에이전트를 만들어 High level의 탐색 수를 줄이는 방식입니다.

그런데 MA가 장점만 있는 것은 아닙니다. 바로 추가적인 연산이 필요하다는 단점이 있는데요.

 

에이전트가 2개 있고ㅡ boundary 값인 B 만큼 conflict가 발생한 상황을 가정해봅시다.

High level의 OPEN 리스트에는 B개만큼의 CT 노드가 추가되고, merge가 일어나겠죠?

그런데 추가된 B개의 노드는 모두 동일한 메타 에이전트를 가지고 있습니다. 이러면 merge한 의미가 없죵!

 

MR은 이를 해결하기 위해서 agent merge가 일어나면 Constraint Tree를 초기화하고 high level 노드의 탐색을 처음부터 다시 실행합니다.

 

이렇게 동일한 Meta Agent의 중복 생성을 막을 수 있었습니다.

CBS의 한계 - Sensitivity of Choosing Split 그리고 개선책 PC

MA를 적용하던 BC를 적용하던 개선되지 않는 한계가 있습니다.

바로 Split 단계에서 선택하는 conflict가 임의로 선택된다는 것입니다.

 

어떤 conflict를 constraint에 추가하느냐에 따라서 high level 노드의 탐색 수에 지대한 영향을 끼칠 수 있는데요.

 

PC는 conflict들의 타입을 나눠서 각 타입 별로 우선 순위를 정해서 어떤 conflict를 먼저 선택할지 정했습니다.

논문에서는 1) Cardinal conflict, 2) Semi-cardinal conflict, 3) Non-cardinal conflict 세 타입으로 나눴고, 각 타입에 대한 설명은 다음과 같습니다.

1. Cardinal conflict
conflict를 해결하기 위해서 두 에이전트 모두 cost를 증가시킬 수 밖에 없다면 Cardinal conflict라고 합니다.

2. Semi-cardinal conflict
conflict를 해결하기 위해서 한 에이전트만 cost를 증가시면 되는 경우에 이를 Semi-cardinal conflict라고 합니다.

3. Non-cardinal conflict
conflict를 해결하기 위해서 어떤 에이전트도 cost를 증가시킬 필요가 없다면 Non-cardinal conflict라고 합니다.

 

ICBS 알고리즘

CBS에 MA, BC, MR, PC까지 섞은 알고리즘은 다음과 같습니다.

1. R = {constraint:{}, solution: s, total cost: SIC(s)}, OPEN = {R}
2. OPEN에서 가장 total cost가 낮은 노드를 선택하여 P라고 하자.
3. P의 solution이 valid한지 확인한다.
4. P의 solution이 valid 하다면 P가 goal node이고, P를 반환하는 것으로 알고리즘을 종료한다.
5. P의 solution이 valid 하지 않다면 발생한 conflict들 중에서 cardinal/semi-cardinal/non-cardinal 순으로 conflict를 찾고, 찾은 conflict를 C라고 한다.
6. 만약 C가 cardinal이 아니고, Bypass를 찾았다면 BC를 적용하고 2로 돌아간다.
7. 만약 Ai, Aj 가 합쳐져야 한다면, Ai, Aj를 합친 Ai_j를 만다.
    7.1. 만약 MR 기능이 활성화되어 있다면 1로 돌아간다.
    7.2. 메타 에이전트를 넣은채로 P.constraint, P.solution을 갱신하고 2로 돌아간다.
8. P1 = {constraint:P.constraint + {Ai, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
9. P2 = {constraint:P.constraint + {Aj, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
10. 2로 돌아갑니다.

---

ICBS는 어떠셨나요?

MACBS, BC를 읽은 후에 보니 서사가 보여서 재밌었습니다 ^^

이제 EECBS 공부하면 CBS 쪽은 어느 정도 정리가 될 것 같습니다!

물론 연구는 계속해서 나오고, 공부할 거리도 계속 추가되겠지만... ㅎ