Searching with Consistent Prioritization for Multi-Agent Path Finding - 일할 때 우선순위 관리만큼 중요한 것이 없죠!

안녕하세요. 무더운 날씨와 연이은 출장이 이어지면서 몸은 고되지만 보람찬 나날을 보내고 있습니다.

• 주중에 와이프와 떨어져 지내는 것은 정말 아쉽네요 흑흑

이번에는 PBS 논문을 공부하려고 합니다!

• MA, Hang, et al. Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the AAAI conference on artificial intelligence. 2019. p. 7643-7650.

 

저번에 공부했던 논문은 PBS를 Lifelong MAPF 문제에 맞게 변형한 알고리즘을 제안했는데

PBS를 몰라서 세부적인 내용을 잘 이해하지 못했던 것 같습니다.

• 참고: Leveraging Experience in Lifelong Multi-Agent Pathfinding -과거의 경험을 이용해서 더 나은 미래를 만들어야죠!

PBS 논문을 공부하면 더 많은 것들이 보이겠죠?

---

1. 논문 내용 간단 요약

Prioritized MAPF 알고리즘들은 MAPF 문제를 빠르고 효율적으로 해결할 수 있습니다.

Prioritized MAPF 알고리즘이란?
- agent들에게 우선 순위(priority)를 할당하고, priority 순으로 agent들의 경로를 계획합니다.
- agent들은 자신보다 priority가 높은 agent들을(이미 계획된 경로)를 피해가면서 경로를 계획합니다.

 

Prioritized MAPF 알고리즘은 MAPF 문제를 빠르게 해결할 수 있지만 ✅

priority를 어떻게 할당하는지에 따라 계획된 경로의 효율이 나쁘거나 아예 MAPF 문제를 해결하지 못할 수도 있다는 단점이 있습니다 ❌

 

즉 "priority를 어떻게 할당하는지"가 결국 Prioritized MAPF 알고리즘의 핵심입니다.

 

논문에서는 Prioritized Planning 알고리즘의 한계를 이론적으로 분석하고

분석된 한계 안에서 좋은 결과를 보여주는 CBS with Priority, Priority Based Search를 제안합니다.

 

2. 기존 Prioritized Planning 알고리즘에서 우선 순위를 할당하는 방식

Prioritized MAPF, Prioritized Planning 알고리즘은 오래 전부터 연구되었습니다.

그렇다면 기존 연구들은 어떻게 priority를 할당했을까요?

 

논문에서는 다음 연구들을 소개합니다.

• 그냥 랜덤하게 priority 할당하기

• WARREN, Charles W. Multiple robot path coordination using artificial potential fields. In: Proceedings., IEEE International Conference on Robotics and Automation. IEEE, 1990. p. 500-505.
• BENNEWITZ, Maren; BURGARD, Wolfram. Finding solvable priority schemes for decoupled path planning techniques for teams of mobile robots. In: Proc. of the International Symposium on Intelligent Robotic Systems (SIRS). Citeseer. 2001.
  • + 랜덤하게 priority를 할당하는 방식 이외에도 agent i의 목적지가 agent j의 최적 경로를 방해하면 j의 priority를 i의 priority보다 높게 설정하는 방식을 제안함
• SILVER, David. Cooperative pathfinding. In: Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment. 2005. p. 117-122.

• heuristic 함수를 이용해서 priority 할당하기

• VAN DEN BERG, Jur P.; OVERMARS, Mark H. Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2005. p. 430-435.
  • agent 별 목적지까지의 거리
• FERRARI, Carlo, et al. Multirobot motion coordination in space and time. Robotics and autonomous systems, 1998, 25.3-4: 219-229.

• 실시간, 지역적으로 priority를 할당하기

• O'DONNELL, Patrick A.; LOZANO-PÉREZ, Tomás. Deadlock-free and collision-free coordination of two robot manipulators. In: 1989 IEEE International Conference on Robotics and Automation. IEEE Computer Society, 1989. p. 484-489.
  • agent의 proirity를 스케줄링 알고리즘처럼 관리함
• AZARM, Kianoush; SCHMIDT, Günther. Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation. In: Proceedings of international conference on robotics and automation. IEEE, 1997. p. 3526-3533.
  • agent 간 통신을 통해서 서로 간의 conflict를 감지하고 최적의 priority를 찾음
  • conflict가 감지된 agent가 3개보다 많을 시, 먼저 conflict를 감지한 세 agent까지만 priority를 찾고, 이외의  agent들은 가장 낮은 priority로 할당함

• 가능한 모든 priority 조합을 전부 확인하기

3. Prioritized Planning 알고리즘의 한계를 이론적으로 분석하기

다양한 방식으로 priority를 할당했지만 MAPF 문제를 푸는데에는 한계가 있었습니다.

왜 그런 것일까요?

 

PP는 일반적으로 MAPF 문제에 대해서 완전성을 보장하지 못합니다.

PP가 MAPF 문제에 대해서 완전성을 보장하지 못한다는 예시

 

그러면 어디까지 완전성을 보장하지 못하는 것일까요?

 

논문에서는 MAPF 문제의 유형을 PP 알고리즘으로 풀 수는 있는 P-solvable과 PP 알고리즘으로 풀 수 있고, 그것이 최적해인 OP-solvable로 나눴습니다.

 

그리고 PP 알고리즘은 P-solvable에 대해서 완전성과 최적성을 보장하지 못하고,

전순서 집합(total order)을 제안하는 PP 알고리즘은 OP-solvable에 대해서 완전성과 최적성을 보장하지 못한다는 것을 증명합니다.

 

4. CBS with Priority

total order를 이용해서는 OP-solvable 문제도 풀기 어렵다는 사실을 밝혀냈으니 부분 순서 집합(parital order)을 찾는 알고리즘을 제안합니다.

 

논문에서는 2가지 해결책을 제안했는데 첫번째는 CBS with Priority(CBSw/P)입니다!

 

CBS는 conflict가 발생할 때마다 constraint를 추가하면서 올바른 해를 찾아간다면 CBSw/P는 priority order도 추가합니다.

(CBS랑 다른 부분은 빨간색으로 표시했습니다)

1. R = {constraint:{}, priority order: {}, 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 = (Ai, Aj, v, t)라고 합시다.
    5.1. {j > i} 가 P.priority order에 포함되어 있지 않다면, P1 = {constraint:P.constraint + {Ai, v, t}, priority order:P.priority order + {i > j}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
    5.2. {i > j} 가 P.priority order에 포함되어 있지 않다면, P2 = {constraint:P.constraint + {Aj, v, t}, priority order:P.priority order + {j > i}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
6. 2로 돌아갑니다.

 

5. Priority Based Search

이제 두번째 해결책 Priority Based Search(PBS)입니다! PBS는 CBSw/P와는 다르게 온전히 priority order 만 사용합니다.

1. R = {priority order: {}, solution: s, total cost: SIC(s)} 이라고 하고 R에 대해서 경로를 계획합니다.
    1.1. 1에서 경로가 계획된다면 공집합 STACK에 R을 추가합니다.
    1.2. 경로가 계획되지 않았다면 알고리즘은 경로를 찾지 못한채로 종료합니다.
2. 가장 최근에 STACK에 추가된 노드를 선택하여 추출한 뒤 N이라고 합니다.
3. N의 solution에 충돌이 있는지 확인한다. 충돌이 없다면 N이 goal node이고 N을 반환합니다.
4. N의 solution에 충돌이다면 발생한 첫번째 conflict를 C = (Ai, Aj, ...)라고 합니다.
5. N의 child를 만들고 STACK에 total cost 순서대로 추가합니다(N의 child만 total cost 순서대로 추가하는 것이지 STACK을 정렬하는 것이 아닙니다!).
    5.1. N1 = {priority order:P.priority order + {i > j}, solution: 다시 계산, total cost: 다시 계산}을 STACK에 추가합니다.
    5.2. N2 = {priority order:P.priority order + {j > i}, solution: 다시 계산, total cost: 다시 계산}을 STACK에 추가합니다.
6. STACK에 남은 노드가 있다면 2로 돌아갑니다. 남은 노드가 없다면 경로를 찾지 못한채로 종료합니다.

 

그리고 PBS는 각 agent들의 경로를 계획할 때, Low-Level에서 경로를 계획할 때 CBS와 큰 차이점이 있습니다.

 

바로 자신보다 높은 priority의 agent 중 경로가 가장 긴 agent의 도착시간까지만 충돌을 고려한다는 것입니다!

Low Level의 특징

 

아마 이 부분이 RHCR 논문에 영감을 주지 않았을까 생각됩니다.

 

+ 2024/12/02 추가 정리

1. PBS에서 BFS를 사용하지 않고 DFS를 사용한 이유

- BFS를 사용한다면 partial priority ordering 기반의 최적해를 찾을 수 있었을 것 같은데 왜 DFS를 사용했을까?
- 내 생각
- PBS는 애초에 최적성을 원하는 알고리즘이 아님
- 빠르게 priority를 추가해보면서 solution을 찾을 수 있는지 확인하는 것이 중요함

 

2. CBSwP와 CBS의 차이는 high level 노드의 탐색만 제한시키는 것

- CBSwP에서도 priority를 이용해서 경로를 계획하는 줄 알았는데 그게 아니었음
- 어떤 high level 노드에서 두 agent 간의 priority가 생기면 child 노드들에서는 priority 낮은 agent가 priority 높은 agent를 피하는 conflict만 생성됨

 

3. PBS의 low level 탐색이 유독 많았던 지도 유형

- PBS는 conflict가 발생했을 때 경로가 수정되어야 할 agent 뿐만 아니라 해당 agent보다 priority가 낮은 agent들의 경로도 수정되어야 함
- Corridor가 많은 지도에서 priority에 의한 경로 변경이 잦았음

---

PBS 논문은 어떠셨나요?

 

저는 MAPF 문제를 분류하여 PP의 한계를 이론적으로 증명하고, 실험을 통해 다양한 케이스를 분석하여 해결책의 장단점이 분석된 것이 매우 유익했습니다.

• 논문의 Conclusion 부분이 빈약하다고 생각하지만 앞의 장점이 너무 컸던 것 같습니다.

다음으로는 어떤 논문을 공부해볼까요!