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: 주요 변형 알고리즘