Bypassing Conflicts in MAPF - CBS의 한계를 개선해보자! (2)

안녕하세요. 오늘은 CBS를 개선한 알고리즘 중 하나인 Bypassing Conflicts in MAPF에 대해서 공부해보려고 합니다.

• BOYRASKY, Eli, et al. Don't split, try to work it out: Bypassing conflicts in multi-agent pathfinding. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2015. p. 47-51.

 

이전에 공부한 MACBS 기억나시나요?

Low level에서 찾은 경로의 연관성이 높은 에이전트끼리 묶어서 메타 에이전트를 만들어 High level의 탐색 수를 줄이는 알고리즘이었습니다!

• Meta-agent CBS - CBS의 한계를 개선해보자! (1)

오늘 공부할 Bypassing Conflicts(BC)는 MACBS와는 또 다른 방법으로 CBS의 성능을 개선했는데요.

BC는 High level의 탐색 수를 줄이는 방법으로 Low level의 경로를 치환하는 방법을 제안합니다.

 

어떤 방법인지 한번 자세히 알아볼까요?

---

CBS의 한계 - Sensitivity of CBS

CBS의 High level의 탐색 수는 low level에서 찾은 경로에 굉장히 민감하다는 특징을 가지고 있습니다.

논문에서는 다음 그래프를 통해 low level에서 찾은 경로가 좋을 때와 안 좋을 때를 비교하며 예시를 보여줍니다.

논문에서 제시했던 바로 그 예시!

1. High level의 Root 노드에서 얻어진 solution이 좋을 때

1. {a1:[S1, A, C, E, G1], a2:[S2, B, D, E, G2]}, constraints = {}, cost = 8
2. {a1:[S1, A, C, C, E, G1], a2:[S2, B, D, E, G2]}, constraints = {(a1, E, 3)}, cost = 9

단 2번의 High level 노드 탐색으로 valid solution을 찾아냈습니다.

 

2. High level의 Root 노드에서 얻어진 solution이 안 좋을 때

1. {a1:[S1, B, D, E, G1], a2:[S2, B, D, E, G2]}, constraints = {}, cost = 8
2. {a1:[S1, A, D, E, G1], a2:[S2, B, D, E, G2]}, constraints = {(a1, B, 1)}, cost = 8
3. {a1:[S1, A, C, E, G1], a2:[S2, B, D, E, G2]}, constraints = {(a1, B, 1), (a1, D, 2)}, cost = 8
4. {a1:[S1, A, C, C, E, G1], a2:[S2, B, D, E, G2]}, constraints = {(a1, B, 1), (a1, D, 2), (a1, E, 3)}, cost = 9

4번의 High level 노드 탐색으로 valid solution을 찾아냈습니다.

 

1, 2 경우는 단순히 low level에서 얻어진 solution이 달랐을 뿐인데 전체 실행 시간에 많은 차이가 나게 됩니다.

 

위에서 보여준 예시에서는 그래프가 작아서 차이가 크게 나지 않지만

그래프가 커지고 에이전트가 많아질수록 전체 실행 시간에 끼치는 영향은 커질 수 있습니다.

 

BC는 이를 개선하고자 High level에서 자식 노드의 cost가 부모 노드의 cost와 같을 때, 발생한 conflict의 수가 적으면 노드를 치환하는 알고리즘을 제안합니다.

 

BC 알고리즘

BC의 구체적인 알고리즘은 다음과 같습니다.

(MACBS 때와 비슷한데 5.1을 제외하면 CBS와 똑같습니다)

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들을 C_list, C_list의 첫번째 conflict C = (Ai, Aj, v, t)라고 하자.
    5.1 만약 P의 코스트와 P의 부모 노드의 코스트가 같고, C_list의 크기가 P의 부모 노드에서 발생한 conflict 개수보다 작으면, P의 부모 노드를 P로 치환하고 2로 돌아갑니다.
    5.2 P1 = {constraint:P.constraint + {Ai, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
    5.3 P2 = {constraint:P.constraint + {Aj, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
6. 2로 돌아갑니다.

 

조건이 너무나도 명확해서 크게 설명할 것은 없을 것 같습니다 👍

---

Bypassing Conflicts는 어떠셨나요?

저는 MACBS에 이어서 한번 더 놀랐습니다. 너무 간단해서요! ㅋㅋㅋ

 

사실 BC를 처음 접한 것은 EECBS 알고리즘에서였습니다.

CBS 논문을 읽고 나서, 바로 EECBS 논문을 읽었더니 처음 보는 알고리즘들이 산더미처럼 나왔고, BC도 그 중 하나였습니다.

 

EECBS를 잘 이해하기 위해서 MAPF 알고리즘들을 기본부터 공부한 것이었는데 한번 시작하니 끝이 안 보이네요 ㅋㅋㅋ;;

얼른 정진해서 부족한 부분들 채워나가겠습니다 :)