Meta-agent CBS - CBS의 한계를 개선해보자! (1)

안녕하세요. 오늘은 CBS를 개선한 알고리즘 중 하나인 Meta-agent CBS에 대해서 공부해보려고 합니다.

• SHARON, Guni, et al. Meta-agent conflict-based search for optimal multi-agent path finding. In: International symposium on combinatorial search. 2012.

 

Meta-agent에 관한 내용은 CBS 논문의 Discussion 부분에서 짧게 언급되었는데 ICTS+3E 알고리즘에서 영감을 받았다고 하네요.

• ICTS도 공부해봐야겠습니다... 경로 계획 알고리즘 공부할 게 참 많네요 ㅎㅎ

MACBS가 CBS의 어떤 문제점을 어떻게 해결했는지 같이 살펴볼까요?

 

---

MACBS가 해결한 문제와 방법

MACBS가 해결하려는 문제부터 살펴볼까요?

CBS 알고리즘은 다음과 같은 경우에 비효율적인 양상을 보입니다.

 

문제의 상황!

• 검은 색의 노드는 이동할 수 없는 곳입니다.

위의 문제에서 valid solution은 어떤게 있을까요?

가장 간단한 solution으로는 S1에서 출발하는 에이전트가 S1에서 한번 기다리고 움직이는 것입니다.

 

하지만 SIC(Sum Of Cost) 기준으로 다음 탐색 노드를 찾는 기존 CBS 알고리즘은

가운데 회색 공간에서 conflict가 나오는 High Level 노드를 무수히 많이 탐색한 후에야 정답을 찾을 수 있습니다.

 

MACBS는 이런 문제를 해결하고자 두 에이전트를 하나의 Meta Agent로 합치는 방법을 제안합니다.

구체적인 알고리즘을 살펴볼까요?

MACBS 알고리즘

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

(CBS랑 비교했을 때 달라진 것이 거의 없죠?)

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 만약 Ai, Aj 가 합쳐져야 한다면, Ai, Aj를 합친 Ai_j를 만들고 P.constraint, P.solution을 갱신한 뒤 2로 돌아갑니다.
    5.2 P1 = {constraint:P.constraint + {Ai, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
    5.3 P2 = {constraint:P.constraint + {Aj, v, t}, solution: 다시 계산, total cost: 다시 계산}을 OPEN에 추가합니다.
6. 2로 돌아갑니다.

 

CBS와 비교하면 단순히 에이전트들을 합치는 부분이 추가되었을 뿐입니다.

5.1 만약 Ai, Aj 가 합쳐져야 한다면, Ai, Aj를 합친 Ai_j를 만들고 P.constraint, P.solution을 갱신한 뒤 2로 돌아갑니다.

 

이제 언제 에이전트들을 합치고, 합친 후에 constraint와 solution은 어떻게 계산되는지 알아보러 가겠습니다.

 

에이전트들을 언제 합칠거야?

논문에서는 두 에이전트 간의 conflict가 B(설정 가능한 파라미터)보다 큰 경우에 합치는 방법을 제안합니다.

• 실험적으로 이 방법의 효율이 괜찮다드라구요👍

이렇게 보면 CBS는 B=∞ 인 경우이고, Independence Detection은 B=0인 경우로 볼 수 있습니다.

 

constraint와 solution은 어떻게 계산되는거야?

constraint는 High Level에서 solution은 Low Level에서 계산됩니다.

 

constraint부터 살펴보겠습니다.

일단 표현 방식이 달라져야겠죠? 기존에 존재하던 constraint들을 메타 에이전트에 대한 constraint로 바꿔줍니다.

예시)
에이전트 a1, a2가 있고 constraint (a1, v1, t0), (a2, v1, t0) 있습니다.
a1, a2가 메타 에이전트 a3으로 합쳐지면 위의 constraint들이 다음과 같이 변합니다.

기존 constraint
- (a1, v1, t0), (a2, v1, t0)

변경된 constraint
- (a3, v1, t0), (a3, v1, t0)

 

이제 low level에서 constraint를 이용해서 solution을 찾아볼까요?

사실 달라지는 것은 크게 없습니다. 메타 에이전트로 합쳐진 에이전트들이 constraint를 공유한다고 보면 됩니다.

 

위의 예시를 그대로 가져와보겠습니다.

예시)
에이전트 a1, a2가 있고 constraint (a1, v1, t0), (a2, v1, t0) 있습니다.
a1, a2가 메타 에이전트 a3으로 합쳐졌습니다.

합쳐지기 전의 a1이 고려하는 constraint
- (a1, v1, t0)

합쳐지고 난 후에 a1이 고려하는 constraint
- (a3, v1, t0), (a3, v1, t0)

---

짜잔! MACBS는 어떠셨나요?

 

저는 처음 봤을 때 너무 간단해서 놀랐습니다 ㅋㅋㅋ

그래도 어떤 CBS에도 적용될 수 있는 프레임워크적인 아이디어라서 의미가 컸던 것 같습니다.

 

혹시 제가 잘못 설명한 부분이 있으면 댓글로 공유 부탁드립니다 :)