Conflict Based Search(CBS) 논문 정리 - MAPF 알고리즘은 CBS가 기본인 것 같기두 하구...

안녕하세요. 오늘은 MAPF 알고리즘 중 coupled approach에서 유명한 알고리즘인 CBS에 대해서 공부하려고 합니다.

• Sharon, Guni, et al. "Conflict-based search for optimal multi-agent pathfinding." Artificial Intelligence 219 (2015): 40-66.

Introduction에서 MAPF의 여러가지 정보를 설명해줘서 정말 재밌었습니다.

뒷부분에 CBS의 optimality를 증명하는 부분이 있었는데 과감하게(?) 스킵했습니다!

---

Introduction

요약

• MAPF가 무엇인지, 어떤 알고리즘들이 있는지 알려줍니다.
  • MAPF 공부 - Multi-Agent Pathfinding 문제 정리한 논문을 다시 정리하기 에서 다루지 않은 내용들을 정리하겠습니다.
• CBS가 무엇인지, 기존 알고리즘들보다 어떤 점에서 뛰어나고 어떤 상황에서 안 좋은지 설명합니다.

 

NP-complete

MAPF는 일반화된 슬라이딩 타일 퍼즐과 동치이기 때문에 NP-complete입니다.

• 어떤 논문에서는 NP-hard라고 소개하는데 각각의 문제 영역이 조금씩 다른 것 같습니다. 더 공부하면서 정리해보겠습니다.

centralized computing VS decentralized computing

논문에서는 decentralized computing이더라도 모든 에이전트들이 소통할 수 있고, 모든 정보가 공유된다면 centralized computing과 다를 것이 없다고 설명하고 있습니다.

• time step 내에 모든 agent들이 모든 정보를 공유할 수 있으려면 네트워크 환경이 그만큼 좋아야 하는데 매우 통제된 환경이 아니면 달성하기 어렵다고 생각합니다.

coupled approach VS decoupled approach

centralized computing 환경에서 MAPF를 푸는 알고리즘들은 크게 coupled, decoupled 알고리즘들로 나뉘게 됩니다.

decoupled 알고리즘은 경로를 계획할 때, 모든 에이전트들을 한번에 고려하지 않고, 각 에이전트 별 경로를 계획합니다.
대체로 빠르지만, 최적성과 완전성이 보장되지 않습니다.

대표적인 decoupled 알고리즘으로 Hirearchical Cooperative A*(HCA)가 있습니다.

• HCA*는 주어진 에이전트 순서대로 경로를 계획하며, 계획된 경로는 global reservation table에 저장합니다.
• 다음 에이전트는 이전 에이전트에 의해서 계획된 경로와의 충돌을 피하면서 경로를 계획합니다.

또 다른 decoupled 알고리즘으로는 Flowing Annotation Replanning(FAR) 알고리즘이 있습니다.

• Local Replanning A*(LRA*)의 변형으로 cycle conflict가 발생했을 때, 무작위로 경로재계획이 이뤄지는 것이 아닌 node density를 이용해서 경로재계획할 로봇을 선택합니다(나중에 FAR 알고리즘에 대해서 다시 다뤄보겠습니다).

본 논문에서는 MAPF 문제의 최적해를 구하는 것을 목적으로 하기에 coupled 알고리즘을 선택했다고 합니다.

coupled 알고리즘의 경우, MAPF 문제를 global, single-agent search 문제의 형태로 바꿀 수 있고,
이렇게 되면 A* 기반의 검색 알고리즘으로 해결할 수 있지만 엄청난 연상량을 요구합니다.

No universally dominant algorithm on MAPF

정말 아쉽게도 모든 환경에 대해서 좋은 성능을 뽐내는 MAPF 알고리즘은 없다고 합니다.
ㅜㅠㅜㅠㅜ...

Conflict Based Search(CBS)란

CBS는 coupled와 decoupled의 특성을 동시에 가지고 있어서, 최적의 해를 보장하지만 경로 계획은 single agent 검색입니다.

CBS는 2단계(high level, low level)의 검색으로 진행됩니다.
high level 검색은 constraint tree(CT)에서 진행되며, 이 트리의 노드에는 에이전트 별 시간, 위치에 대한 조건이 포함되어 있습니다.
각 노드에서는 제한 사항을 지키면서 모든 에이전트의 경로를 계획하게 됩니다.

A*와 CBS의 가장 큰 차이점은 실행시간입니다.
A*는 에이전트 수의 지수적으로 탐색해야 할 트리가 증가하지만 CBS는 문제 해결 중 마주치는 conflict 수의 지수적으로 탐색해야 할 트리가 증가합니다.

마지막으로 CBS가 어떤 환경에서 성능이 좋고 나쁜지 분석하였다고 합니다.

Previous Optimal Solvers

요약

• 기존 연구들 중에서 CBS가 차용한 부분을 정리하고 있습니다.

MAPF 문제를 해결하는 가장 기본적인 방법은 문제를 전역 탐색 문제로 변환하고 A* 알고리즘을 해결하는 것입니다.

MAPF에서 많이 사용되는 휴리스틱 함수로는 Sum Of Individual Costs(SIC) 가 있습니다.

• 각 에이전트들에 대해서 다른 에이전트가 없다고 가정하고 최적 경로 거리를 계산하고 이를 합한 것입니다.
• 장애물이 없는 grid 맵에서는 맨해튼 거리와 정확히 일치합니다.
• SIC의 경우, 미리 계산하여 k look up 테이블에 저장해서 사용하곤 합니다.

여러 연구들에서 이런 기본적인 방법을 개선하고 있는데, CBS가 차용한 부분들을 정리해보겠습니다.

Independence Detection (ID)

ID는 일반적인 방법론으로 어떤 MAPF 알고리즘에서도 사용할 수 있습니다.
만약 서로 다른 두 그룹에 포함된 에이전트들의 해끼리 conflict가 없다면 두 그룹은 independent 하다고 합니다.

ID의 기본적인 개념은 에이전트들을 독립적인 그룹으로 나눠서, 즉 MAPF를 작은 문제로 나누어서 해결하자는 것입니다.
간략하게 방법을 소개하면 다음과 같습니다.

1. OPEN = {1, 2, ..., k}, CLOSE = {}
2. OPEN에 속한 모든 에이전트에 대해 경로를 찾습니다.
3. conflict가 발생하지 않은 에이전트들을 OPEN에서 제외하고 CLOSE에 추가합니다.
4. OPEN이 공집합이 될 때 까지 2, 3을 반복합니다.

Conflict Avoidance Table (CAT)

CAT에는 각 에이전트들의 시간 별 위치가 저장되어 있고,
이를 이용해서 주어진 해가 얼마나 많은 conflict가 발생할지 계산할 수 있습니다.

주로 f-value가 똑같은 해가 존재할 때, 타이브레이커로 conflict가 적게 발생하는 해를 선택하기 위해 CAT을 활용합니다.

Operator Decomposition (OD)

ID와 CAT이 모든 MAPF 알고리즘에 대해서 범용적으로 사용될 수 있다면, OD는 A* 기반의 MAPF 알고리즘에만 적용될 수 있습니다.

state 사이에 intermediate state를 추가함으로써 에이전트가 취할 수 있는 행동의 수(branch factor)의 지수적으로 증가하는 문제 영역을 축소시킬 수 있습니다.

예를 들어, 에이전트 A1, A2가 각각 (0, 0), (1, 0) 에 있는 것을 다음과 같이 표현해보겠습니다.

s1 = {A1: (0, 0), A2: (1, 0)}

에이전트가 상, 하, 좌, 우 방향으로 1씩 움직일 수 있다고 가정하면, s1 다음으로 나올 수 있는 상태는 4 x 4 = 16가지의 상태입니다.

s2 ∈ {
{A1: (1, 0), A2: (0, 0)},
{A1: (-1, 0), A2: (0, 0)},
{A1: (0, 1), A2: (0, 0)},
{A1: (0, -1), A2: (0, 0)},
...
}

그런데 A1이 오른쪽으로 1칸, A2가 왼쪽으로 1칸 움직이는 것은 불가능하죠?
A1을 이동시키고, A2를 이동시키려고 했는데 아뿔싸 A2 때문에 A1의 이동이 불가능한 것이죠.

이렇게 state 간 전이의 중간 단계를 살펴보면서 잘못된 이동을 제거하는 것이 OD 입니다.

Increasing Cost Tree Search (ICTS)

ICTS는 MAPF 문제를 high, low 2단계로 나눠서 해결합니다.

high 레벨에서는 각 에이전트들의 코스트를 벡터로 가지는 노드에서 최적의 노드를 찾으며,
low 레벨에서는 각 노드의 해가 conflict가 없는지 혹은 실제로 존재하는지 확인합니다.

The Conflict Based Search Algorithm (CBS)

요약

• CBS에서 사용되는 용어를 정리합니다.
• high, low 2 단계에서 실행되는 탐색 알고리즘을 설명합니다.

용어 정리

path(경로)
단일 에이전트를 논할 때에만 사용한다.

solution(해)
k개의 에이전트에 대한 k개의 경로를 의미한다.

constraint
(Ai, v, t)로 표현되며 에이전트 Ai가 시간 t에서 v 노드에 위치하지 못한다는 것을 의미한다.

consistent path
만약 에이전트 Ai의 path가 모든 constraint를 만족한다면 consistent path라고 한다.

consistent solution
만약 solution의 모든 path가 consistent path라면 consistent solution이라고 한다.

conflict
(Ai, Aj, v, t)로 표현되며 서로 다른 에이전트가 같은 시간에 같은 노드를 점유하는 경우를 의미한다.

valid
만약 solution의 모든 path가 conflict가 없다면 그 solution은 valid하다고 한다. consistent solution도 invalid 할 수 있다.

constraint tree (CT)
CT는 이진 트리로 1) constraint set, 2) solution, 3) total cost(f-value) 를 가지고 있는 노드로 구성되어 있습니다.

goal node
만약 노드 N의 solution이 valid 하다면 노드 N은 goal node 라고 합니다.


CBS의 핵심은 CT를 탐색해나가면서(high level) valid solution을 찾는 것(low level)입니다.

High-level: Search the Constraint Tree (CT)

high level에서는 CT를 best-first 검색 알고리즘으로 goal node를 찾습니다.
만약 탐색 중 cost가 같은 노드가 있다면 CAT를 이용해서 타이브레이크 합니다.

알고리즘은 다음과 같습니다.

1. R = {constraint:{}, solution: s, total cost: SIC(s)}, OPEN = {R}
2. OPEN에서 가장 total cost가 낮은 노드를 선택하여 P라고 하자.
3. P의 solution이 valid한지 확인한다.
4. P의 solution이 valid 하다면 P가 goal node이고, P를 반환하는 것으로 알고리즘을 종료한다.
5. P의 solution이 valid 하지 않다면 발생한 conflict를 C = (Ai, Aj, v, t)라고 합시다.
    5.1 P1 = {constraint:P.constraint + {Ai, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
    5.2 P2 = {constraint:P.constraint + {Aj, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
6. 2로 돌아갑니다.

5에서 conflict가 k(k>1)개라면 CT가 이진 트리인 것과 상충되는 것 같은데 어떻게 해야 하죠?

두 가지 방법이 있고, 둘다 동일한 결과를 보여줍니다.
1. CT를 이진 트리가 아닌 다원 탐색 트리로 구성하고 k-1개의 constraint이 추가된 노드를 OPEN에 추가합니다.
2. 발견된 conflict 중에서 1개만 선택하여 5.1, 5.2 과정을 진행합니다.

• 결국에는 트리가 깊어지면서 1에서 나온 노드들을 발견하게 됩니다.

Low-level: Find Paths for CT Nodes

low level에서는 decoupled 방법으로 에이전트들의 경로를 찾습니다.
주어진 노드 N의 conflict를 만족하게끔 에이전트들의 경로를 찾습니다.

만약 cost가 같은 solution들이 있다면 CAT을 이용해서 conflict 수가 가장 적은 solution을 선택합니다.

Theoritical Analysis: Optimality of CBS

스킵!

Comparison with other algorithms

요약

• 병목 구간이 있는 환경에서 A*보다 성능이 좋다.
• 개방된 환경에서는 A*가 성능이 더 좋다.

Experimental results

요약

• A*, A* with OD, ICTS, ICTS+3E와 CBS 알고리즘을 비교했다.
• 특별한 휴리스틱 함수 없이 CBS가 많은 경우에서 좋은 성능을 보여줬다.

Discussion and future work

요약

• meta-agent 개념을 적용해보려고 한다.
  • 이 부분에 대해서는 "Meta-Agent CBS"에서 더 다뤄집니다.
• CT의 노드에 대해서 independent detection을 적용해보려고 한다.
• CT에 적용가능한 휴리스틱 함수를 찾아볼 것이다.
• constraint와 탐색을 연관짓는 것에 대해서 더 깊은 연구를 진행하려고 한다.
  • 이 부분에 대해서는 "Don't Split, Try to Work It Out"에서 더 다뤄집니다.