MAPF

[CBS] Optimality & Completeness 정리

안녕하세요. 오늘은 CBS 알고리즘을 공부할 때 제대로 짚고 넘어가지 않았던 CBS 알고리즘의 최적성과 완전성에 대해서 공부하려고 합니다! Conflict Based Scheduling(CBS) 논문 정리 - MAPF 알고리즘은 CBS가 기본인 것 같기두 하구... CBS 알고리즘 최적성 증명 증명에 앞서서 필요한 개념들을 간단하게 설명드리겠습니다. 정의 1. Constraint Tree에 있는 노드 N에 대해서 모든 consistent valid solution의 집합을 CV(N)이라고 합니다. 2. Solution p가 p ∈ CV(N) 이라고 한다면 N이 p를 허용한다고 표현합니다. 3. OPEN 리스트의 노드 중에서 valid solution p를 허용하는 노드들의 집합을 N(p)라고 합니다. 이..

MAPF 알고리즘들에서 사용되는 지표 - 만들었으면 얼마나 좋은지 봐야겠죠?

안녕하세요. 오늘은 MAPF 알고리즘들에서 널리 사용되는 지표들에 대해서 알아보려고 합니다. 알고리즘을 고안하는 것만큼이나 중요하는 것이 바로 성능을 측정하는 것입니다. 알고리즘을 평가할 때 사용되는 지표는 일반적으로 실행 시간과 메모리 사용량입니다. 하지만 MAPF 알고리즘들은 NP-hard 문제를 풀기 때문에 실행 시간을 O 표기법으로 표현하는 것이 큰 의미가 없습니다. 그러면 그 많은 연구들은 어떤 지표들을 사용하고 있을까요? 0. 테스트 환경 테스트 환경을 명시하는 것이 굉장히 중요합니다. 모든 환경에서 최적의 성능을 보여주는 MAPF 알고리즘은 없기 때문인데요. 지도가 어떻게 구성되어 있는지, 얼마나 개방되었는지, 통로가 좁은지, 에이전트 수 등 다양한 요소가 알고리즘의 성능에 영향을 줄 수 있..

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 Conflic..

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 ..

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

안녕하세요. 오늘은 CBS를 개선한 알고리즘 중 하나인 Meta-agent CBS에 대해서 공부해보려고 합니다. SHARON, Guni, et al. Meta-agent conflict-based search for optimal multi-agent path finding. In: International symposium on combinatorial search. 2012. Meta-agent에 관한 내용은 CBS 논문의 Discussion 부분에서 짧게 언급되었는데 ICTS+3E 알고리즘에서 영감을 받았다고 하네요. ICTS도 공부해봐야겠습니다... 경로 계획 알고리즘 공부할 게 참 많네요 ㅎㅎ MACBS가 CBS의 어떤 문제점을 어떻게 해결했는지 같이 살펴볼까요? MACBS가 해결한 문제와 방법..

FAR - Flow Annotation Replanning이 decoupled 에서는 꽤 먹어주는 것 같습니다!

안녕하세요. 오늘은 Flow Annotation Replanning에 대해서 공부하려고 합니다. WANG, Ko-Hsin Cindy, et al. Fast and Memory-Efficient Multi-Agent Pathfinding. In: ICAPS. 2008. p. 380-387. MAPF를 해결할 수 있는 방법으로 decoupled 알고리즘은 포기하려고 했는데 생각보다 좋은 결과에 decoupled 알고리즘 공부도 멈추면 안되겠다는 생각을 가졌습니다! 공부할 알고리즘 가짓 수 좀 줄여보려고 했는데 쉽지 않네요...ㅋㅋㅋㅋ;; 논문 내용 그대로 번역하는 것이 아닌 이해한 내용을 토대로 최대한 정리해보겠습니다! FAR Flow Annotation Replanning(FAR)은 다음 3가지 방법으로 ..