1. 슬라이드 1: 발표 제목 및 개요
- 제목: 다중 로봇 경로 계획 (MAPF)에서 Conflict-Based Search (CBS) 및 그 변형 알고리즘 비교
- 발표자: 박영신
- 발표 개요: MAPF 문제의 정의, CBS와 주요 변형 알고리즘 (GCBS, BCBS, ECBS) 개요, 실험 결과 및 결론
2. 슬라이드 2: MAPF 문제 정의
- MAPF (Multi-Agent Path Finding)
- 여러 로봇이 충돌 없이 각각의 목표 위치로 이동해야 하는 문제.
- 적용 분야: 물류 로봇 경로 계획, 드론 경로 최적화 등.
- 목표: 모든 에이전트가 최단 경로를 따라 목적지로 이동하면서 충돌을 피하도록 경로를 계획.
3. 슬라이드 3: Conflict-Based Search (CBS) 소개
- CBS의 핵심 원리
- 고수준 탐색: 충돌이 발생할 때마다 충돌을 해결하기 위한 제약 조건을 추가하는 제약 트리 (CT) 를 생성.
- 저수준 탐색: 각 에이전트에 대해 최단 경로를 찾고, 제약 조건을 만족시키는 경로를 계획.
- 장점: 최적 해법이며 충돌을 단계적으로 해결하여 효율적으로 경로를 탐색.
- 단점: 충돌이 많은 상황에서는 계산 비용이 높아질 수 있음.
4. 슬라이드 4: Suboptimal CBS 변형
- 필요성: 최적 솔루션을 찾는 CBS는 시간이 오래 걸리므로 빠른 시간 내에 근사 해를 제공하는 알고리즘 필요.
- Bounded vs Unbounded Suboptimal Solvers
- Unbounded: 솔루션 품질 보장 없음. 예) GCBS.
- Bounded: 일정 품질 보장. 예) BCBS, ECBS.
- 목적: 실행 시간을 줄이면서 어느 정도 품질을 보장하는 솔루션 제공.
5. 슬라이드 5: 주요 변형 알고리즘