CONFLICT BASED SEARCH (ECBS)

• "Conflict-Based Search" (CBS)와 그 변형인 "Enhanced Conflict-Based Search" (ECBS)는 다중 에이전트 경로 찾기(Multi-Agent Path Finding, MAPF) 문제를 해결하기 위한 알고리즘입니다.

Conflict-Based Search (CBS)

• CBS는 '분할 정복' 전략을 사용합니다. 이는 문제를 충돌이 없는 간단한 부분 문제로 나누고, 각 부분 문제를 개별적으로 해결한 다음, 결과를 결합하여 전체 문제를 해결하는 방식
• 두 단계 프로세스
  • 첫 번째: 각 에이전트에 대해 개별적인 최적 경로를 찾음
  • 두 번째: 에이전트들 간의 충돌을 해결
• 트리 기반 구조
  • CBS는 트리 구조를 사용하여 가능한 경로를 탐색
  • 루트 노드는 초기 경로를 나타내며, 충돌이 발생하면 두 자식 노드가 생성
  • 각 자식 노드는 충돌을 해결하기 위한 제약 조건을 나타냄

4. 충돌 해결: 에이전트 간의 충돌이 감지되면, CBS는 해당 충돌을 해결하기 위한 제약 조건을 생성합니다. 이를 통해 충돌을 피하는 새로운 경로가 탐색됩니다.

Enhanced Conflict-Based Search (ECBS)

1. 부최적 솔루션: ECBS는 CBS의 변형으로, 부최적 결과를 제공합니다. 이는 완전 최적화보다는 실용적인 해결책을 찾는 데 중점을 둡니다.

2. 계산 효율성 향상: ECBS는 계산 효율성을 높이기 위해 휴리스틱과 다른 최적화 기법을 사용합니다. 이는 특히 대규모 에이전트 그룹이나 복잡한 환경에서 유용합니다.

• A 탐색의 휴리스틱: ECBS는 A 탐색 알고리즘의 변형을 사용하는 경우가 많습니다. A* 알고리즘에서 휴리스틱은 목적지까지의 예상 최소 비용(거리, 시간 등)을 추정하는 데 사용됩니다. 이러한 휴리스틱은 경로 탐색 시 각 단계에서 가장 유망한 노드(위치)를 선택하는 데 도움을 줍니다.

3. 제약 완화: ECBS는 CBS에 비해 제약 조건을 덜 엄격하게 적용합니다. 이를 통해 더 빠르게 해결책을 찾을 수 있으나, 결과적으로 경로의 최적성이 다소 감소할 수 있습니다.