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

안녕하세요. 이제 장마가 시작된 것 같은데 정말 습하고 덥습니다. 에어컨을 안 켜면 잠을 못 자겠더라고요 ㅜㅠ

 

지금까지 여러 경로 계획 알고리즘들을 공부했는데 올해 초까지 조사한 내용으로도 충분히 공부한 것 같아 한동안 쉬고 있었습니다.

 

그런데 이전에 공부하기로 했던 논문이 생각나서 다시 뒤적이게 되었습니다.

• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses - RHCR 원조가 여기라던데!
• SONG, Soohwan; NA, Ki-In; YU, Wonpil. Anytime Lifelong Multi-Agent Pathfinding in Topological Maps. IEEE Access, 2023, 11: 20365-20380.

오늘 공부할 논문은 위의 논문에서 참고하는 논문으로 이전 경로 계획의 경험을 다시 사용하여 RHCR의 효율을 높이는 연구를 진행했습니다.

• MADAR, Nitzan; SOLOVEY, Kiril; SALZMAN, Oren. Leveraging experience in lifelong multi-agent pathfinding. In: Proceedings of the International Symposium on Combinatorial Search. 2022. p. 118-126.

이번에는 정말 간단하게 정리해봤습니다!

---

논문 내용 간단 요약

Lifelong MAPF 문제를 해결할 때는 주로 Windowed MAPF 알고리즘을 사용합니다.

• 대표적으로 RHCR이 있습니다.

그런데 Windowed MAPF 알고리즘들은 MAPF 문제를 무조건 처음부터 풀고 있습니다.

바로 여기서 비효율이 발생합니다.

1. Windowed MAPF 알고리즘들은 주기적으로 실행되면서 MAPF 문제를 풉니다.
2. 그런데 다음 주기에도 현재와 똑같은 문제를 풀 때가 많습니다.(agent들의 목적지가 안 바뀜)
3. 이러면 완전 손해 아닌가? 과거에 문제를 풀었던 경험(?)을 이용하면 훨씬 좋을 것 같은데

 

이런 생각에서 시작되어 exRHCR와 exPBS를 제안하게 되었다고 합니다.

exRHCR의 동작 방식은 다음과 같습니다.
1. 맨 처음에 PBS를 이용해서 문제를 풉니다.
2. 정해진 재시도 횟수만큼 다음을 반복합니다.
- 1에서 얻은 Priority Set을 이용해서 PBS에 대입하여 문제를 해결함 (exPBS)질문

- 재시도 횟수가 끝나면 1로 돌아갑니다.

저자가 실험한 결과, RHCR + PBS와 비교하여 경로계획에 걸리는 시간은 20~30% 정도 단축되었지만 경로의 비용은 1~2% 정도 밖에 차이나지 않았다고 합니다 👍👍👍

 

 

궁금한 점

• 왜 PBS일까?
  • CBS 같이 시점, agent, 위치가 정해진 알고리즘은 미래에 재사용할 정보가 적음
  • 하지만 PBS는 우선 순위라는 개념이 있어서 미래에 재사용하기 용이함
  • + 이렇게 재사용하기 좋은 정보로 우선 순위 말고 다른 것은 없을까?
• PBS와 exPBS의 차이
  
  • 재시도 횟수와 width limit이라는 파라미터가 추가적으로 존재함
  • 재시도 횟수
    • PBS로 구한 우선 순위를 몇 번이나 재사용할지 결정함
    • exPBS에서 사용하는 우선 순위를 최신의 것으로 유지하고, 현재 풀고 있는 문제와의 연관성을 유지시키는데 사용됩니다.
  • width limit
    • 는 무슨 용도인지 이해하지 못함
    • PBS 논문을 읽어보면 조금 더 이해하기 쉬울 것 같음
• 재시도 횟수는 어떻게 결정하는지?
  • 논문에서는 w(윈도우 사이즈) / h(경로재계획 주기) - 1 의 값을 권장하고 있습니다.
  • 이는 충돌이 고려되는 기간인 윈도우 사이즈 동안 이전에 계산된 우선 순위 값을 재사용하려는 의도입니다.
  • 재시도 횟수가 w / h - 1 보다 크면 경로 계획 시간이 증가하는 양상을 보입니다.
  • 그런데 w가 크고 h가 작은 경우에는 재시도 횟수가 w / h - 1 보다 작을 때 경로 계획 시간이 빨라졌습니다.