RL&Opt

📦 MAPF-CBS 최단 경로 알고리즘

CBS(Conflict-Based Search)는 여러 에이전트(로봇/ AGV/ AMR 등)가 하나의 지도 위에서 충돌 없이 각자의 목적지까지 최단경로로 이동할 수 있도록 경로를 찾는 대표적인 경로 최적화(MAPF, Multi-Agent Path Finding) 알고리즘입니다.

---

⚙️ 기본 구조 및 동작 방식

1. 경로 계획 (Path Planning)
   • 각 에이전트에 대해 독립적으로 최단경로 탐색(A* 등 사용)
2. 충돌 탐지 (Conflict Detection)
   • 전체 경로를 시뮬레이션하며, 시간별 위치가 겹치는(=충돌) 상황을 찾음
3. 충돌 해결 (Conflict Resolution)
   • 충돌이 발생한 경우, 해당 에이전트 중 하나 이상에게 제약(constraint: 특정 위치/시간대 출입 불가 등)을 부여하여 새로운 경로를 재탐색
   • 이 과정을 conflict tree(CT)를 생성해 재귀적으로 탐색
4. 반복
   • 모든 충돌이 해소될 때까지 위 과정을 반복하여 충돌 없는 최적 경로 집합을 도출

🧩 주요 특징

• 최적성: CBS는 각 에이전트의 경로가 최단이면서, 전체적으로도 가능한 한 효율적인 경로 집합을 산출
• 확장성: 에이전트 수가 늘어나도, 각 에이전트의 독립 탐색과 충돌 분기 방식 덕분에 복잡도 증가를 억제
• 적용 분야: 물류창고, 공장, 자동화창고 등 멀티로봇 경로 최적화에 다양하게 사용됨

⚙️ 작동 플로우

• AGV 3대가 창고 입구에서 각각 다른 랙으로 이동해야 하는 상황
  1. 각 AGV별로 A* 알고리즘으로 개별 최단경로 탐색
  2. 만약 특정 통로나 랙 앞에서 시간이 겹쳐 충돌 발생 시, CBS가 한 AGV에 시간제약을 걸고 경로를 재계산
  3. 충돌이 완전히 해소된 경로 조합이 나오면 종료

📚 참고 자료

• Conflict-Based Search for Optimal Multi-Agent Path Finding (AAAI 2012 논문)

---

📦 PPO 강화학습 알고리즘