논문 정리
[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)라고 합니다. 이..
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가 해결한 문제와 방법..
A* 알고리즘 - 경로 계획 알고리즘 공부한다면 기본이죠...?
안녕하세요. 오늘은 A* 알고리즘에 대해서 공부하려고 합니다. HART, Peter E.; NILSSON, Nils J.; RAPHAEL, Bertram. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 1968, 4.2: 100-107. A* 알고리즘은 경로 계획 알고리즘이 필요한 경우에는 게임, 로봇, 항공 등 분야를 가리지 않고 사용됩니다. 저는 휴리스틱 함수를 마음대로 갈아끼울 수 있는 강점이 그 이유라고 생각합니다. 상황에 따라서 적절한 휴리스틱 함수를 고를 수 있다는 점에서 A*알고리즘은 단순한 경로 계획 알고리즘이라기보다..
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가지 방법으로 ..