[CBS] Optimality & Completeness 정리

안녕하세요.
오늘은 CBS 알고리즘을 공부할 때 제대로 짚고 넘어가지 않았던 CBS 알고리즘의 최적성과 완전성에 대해서 공부하려고 합니다!

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

---

CBS 알고리즘 최적성 증명

증명에 앞서서 필요한 개념들을 간단하게 설명드리겠습니다.
 
정의
1. Constraint Tree에 있는 노드 N에 대해서 모든 consistent valid solution의 집합을 CV(N)이라고 합니다.
2. Solution p가 p ∈ CV(N) 이라고 한다면 N이 p를 허용한다고 표현합니다.
3. OPEN 리스트의 노드 중에서 valid solution p를 허용하는 노드들의 집합을 N(p)라고 합니다.
 
이제 최적성을 증명하기 위해 필요한 보조 정리를 증명해보겠습니다.
 
Lemma
1. N의 cost는 CV(N)의 최소 비용보다 작습니다.  =  N.cost ≤ minCost(CV(N))

증명)
N의 cost는 N이 가지고 있는 constraint에 대해서 consistent 하고 optimal 한 solution의 cost입니다.
CV(N)은 consistent 하고 valid 한 solution들의 집합이기 때문에 N.cost 보다 클 수 밖에 없습니다.

 
2. 주어진 MAPF 문제(agent들과 시작 노드, 목적지 노드)에 대해서 valid한 solution p는 항상 OPEN 리스트에 있는 노드 중 최소한 하나의 노드에 허용된다.

증명)
수학적 귀납법을 이용해서 증명해보겠습니다.

1. 루트 노드 R은 constraint이 하나도 없기 때문에 모든 valid solution들은 CV(R)에 포함됩니다.
2. i-1 번의 확장까지 Lemma2가 성립하고, 노드 N이 확장되었다고 가정합니다.
3. i 번의 확장으로 생성된 노드를 N1, N2 라고 합니다.
    - constraint으로 추가된 conflict는 (A1, A2, v, t)로 표현할 수 있고, 이를 서로 다른 constraint 2개로 만들어서 N1, N2에 추가한 것이죠.
4. 모든 valid solution들은 충돌이 없는 경로를 계획하기 때문에 t 시간의 v 노드에는 에이전트 A1만 있거나 A2만 있습니다. 따라서 모든 valid solution들은 CV(N1) 혹은 CV(N2)에 포함됩니다.

=> Lemma2에서 조금 더 나아가면 OPEN 리스트에 있는 노드 중 최소한 하나의 노드는 optimal valid solution을 허용한다.
 
최적성 증명

CBS 알고리즘을 실행하면서 GOAL 노드가 처음으로 나왔을 때(consitent 하고 valid한 solution이 처음으로 나왔을 때)를 가정해봅시다.

Lemma1에 의해서 모든 valid solution p에 대하여 N(p).cost ≤ p.cost 가 성립합니다.
그런데 CBS 알고리즘은 OPEN 리스트에서 노드를 고를 때, cost가 낮은 순으로 고르므로 G.cost ≤ N(p).cost 가 성립합니다.

따라서 모든 valid solution p에 대하셔 G.cost ≤ p.cost 가 성립하게 되므로 CBS 알고리즘은 최적해를 구합니다.

 

CBS 알고리즘 완전성 증명

Contraint Tree에 있는 노드 N의 cost가 C라고 가정합시다.
C 시간 이내에 모든 에이전트가 목적지에 도착했다는 뜻이므로 새롭게 추가될 constraint도 C시간 이내에서만 존재할 수 있습니다.
그리고 Constraint Tree 노드들의 비용은 단조적으로 증가하므로 노드N의 부모 노드들의 비용도 C보다 작거나 같습니다.

비용이 C인 노드는 constraint을 최대 k × | V | × C 개수만큼만 가질 수 있다는 뜻이고 이는 비용이 C인 노드의 개수도 저만큼만 존재할 수 있다는 뜻입니다.

비용이 유한하다면(해가 존재한다면) 확장 가능한 노드의 최대 개수도 유한하다는 결론을 내릴 수 있습니다.

따라서 CBS 알고리즘은 해가 존재한다면 해를 구할 수 있습니다.

---

CBS 알고리즘의 최적성, 완전성에 대한 증명은 어떠셨나요? 생각보다 간단하죠?
 
처음에는 "똑똑한 분들이 최적성과 완전성을 증명했는데 내가 굳이 이해해야 할까...?"라고 생각하면서 넘겼습니다.
 
하지만 MAPF 문제 해결의 기본이 되는 CBS 알고리즘 최적성, 완전성의 증명을 이해하지 않고 넘어간다면
미지의 영역을 마주쳤을 때, 해결책을 제시하기보다는 뜬구름 잡는 소리만 하게 될 것이라고 생각하여
이번에 짚고 넘어가게 되었습니다.

 

혹시 이해가 되지 않는 부분이나 설명이 미흡한 부분이 있다면 말씀해주세요! 같이 이해해봐요 👍