(ECBS)Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem
-> 위의 논문을 분석해보았다.
우선 지피티와 함께 한 해석이다. 영어는 어려워ㅠㅠ
요약 및 서론
💡 MAFT란?
다수의 에이전트가 주어진 환경에서 충돌 없이 각각의 목표 지점에 도달하는 경로를 찾는 것
⚠️ 근데 이제 ! MAFT의 문제
MAPF를 최적의 방식으로 해결하는 것은 NP-Complete 문제
NP-Complete 특성상 문제의 크기가 커지면 확장성이 떨어짐
이에 대한 해결책으로 CBS 기반 알고리즘을 설명하고 있다.
3가지 해법
최적 해법(Optimal Solvers)
최적의 경로를 찾기 위해 모든 가능한 경로를 탐색하고 충돌을 회피하여 에이전트를 이동시키는 방법
무한-부분 최적 해법(Unbounded Suboptimal Solvers)
- 최적해에 대한 보장 없이 빠르게 해결책을 찾으며 일부 충돌을 허용하는 방식
- 품질에 대한 보장 제공X
유한-부분 최적 해법(Bounded Suboptimal Solvers)
매개변수 w를 받아서 해결책의 비용이 최적 해결책 비용(C*)의 w배 이하가 되도록 보장하는 해결책
= 최적 비용의 일정 배수 이내에서 해결책 보장
비교
CBS 기반 알고리즘
CBS
GCBS
GCBS-LH가 GCBS-H와 GCBS-L보다 더 안정적이며, 사용하는 것을 권장
CBS의 경우 3개의 도메인에서 모두 약함
BCBS
ECBS
비교 및 결론
-
CBS 간 비교
-
타 알고리즘과의 비교
-
결론
내가 공부하고 직접 만든 자료이기 때문에 .. 그대로 첨부한다.
