한눈에 보는 경로 계획 알고리즘 공부 순서

[2023.02.18] 

안녕하세요!

이번에는 제가 공부하고 있는 경로 계획 알고리즘에 대해서 간단하게 스터디 로드맵을 그려보려고 합니다.

 

블로그에 작성한 글들이 너무 산발적으로 퍼져 있는 것 같아서 이번 기회에 정리해보려고 합니다.

정리의 시작으로 가장 최근 공부하고 있는 경로 계획 알고리즘이 선정된 것인데요 ㅎㅎ

 

간단한 자료구조부터, 탐색 알고리즘, 다중 에이전트 경로 계획 등 지금 공부하고 있는 것들을 연결시켜보려고 합니다.

각 항목들을 클릭하면 포스팅으로 연결되니 같이 공부해봐요 :)

• 아직 링크가 없는 내용들은 공부를 하면서 채워나갈 예정입니다!

---

0. 경로 계획 알고리즘을 공부하는데 필요한 개념

• [자료 구조] 리스트(List)란?
• [자료 구조] 해시맵(HashMap)이란?
• [자료 구조] 그래프(Graph)란?
• 비용 함수 - f, g, h 란? 

1. 단일 에이전트 경로 계획

• 너비 우선 탐색(BFS) 알고리즘
• 깊이 우선 탐색(DFS) 알고리즘
• 다익스트라(Dijkstra) 알고리즘
• 밸먼 포드(Bellman-Ford) 알고리즘
• 플로이드 와샬(Floyd-Warshall)  알고리즘
• A* 알고리즘
• A* 알고리즘 변형 
  • Recursive Best First Search(RBFS) 알고리즘
  • Simplified Memero bounded A*(SMA*) 알고리즘
  • Iterative Deepning A*(IDA*) 알고리즘
  • Partial Expansion A*(PEA*) 알고리즘
  • Weighted A*(WA*) 알고리즘
  • Anytime Reparing A*(ARA*) 알고리즘

2. 다중 에이전트 경로 계획 (오프라인)

• Increasing Cost Tree Search(ICTS) 알고리즘
• Hirearchical A*(HA*) 알고리즘
• Hirearchical Cooperative A*(HCA*) 알고리즘
• Flow Annotation Replanning(FAR) 알고리즘
• Conflict Based Search(CBS) 알고리즘
• Meta Agent CBS(MACBS) 알고리즘
• Bypassing Conflicts in MAPF
• Improved CBS(ICBS) 알고리즘
• EECBS 알고리즘
• MAPF 알고리즘들에서 사용되는 지표

 

3. 다중 에이전트 경로 계획 (온라인)

• Lifelong Multi-Agent Path Finding In Large-Scale WareHouses
• Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
• Multi-Agent Path Finding with Delay Probabilities

 

---

제가 준비한 경로 계획 알고리즘 공부 순서는 어떠셨나요?

순서를 바꾸거나 중간 중간 보완해야할 개념이 있다면 같이 공부해봐요!