Corridor Reasoning - conflict가 가장 많이 발생하는 요인 중 하나인 좁은 통로를 어떻게 공략할 수 있을까?

안녕하세요. 이제 낮에도 햇빛이 뜨거운 것이 아니라 따뜻하다고 느껴질 만큼 날씨가 쌀쌀해졌습니다.

이번에는 Corridor Reasoning에 대해 공부한 내용을 정리해보려고 합니다.
사실 Anytime Lifelong Multi-Agent Pathfinding in Topological Maps 논문을 공부하고 있었는데 Corridor conflict 해소하는 내용을 잘 모르겠어서 인용된 논문을 또 공부하게 되었습니다.

인용된 논문은 다음 2편이 있었는데 하나씩 알아보겠습니다.

• COHEN, Liron; URAS, Tansel; KOENIG, Sven. Feasibility study: Using highways for bounded-suboptimal multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search. 2015. p. 2-8.
• LI, Jiaoyang, et al. New techniques for pairwise symmetry breaking in multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2020. p. 193-201.

---

1. 고속도로 컨셉으로 충돌 줄이기

1.1. 고속도로 컨셉이란?

Feasibility study: Using highways for bounded-suboptimal multi-agent path finding  논문에서는 highway라는 edge와 vertex들의 집합(graph)을 정의합니다.

highway에 대한 간단한 설명

 
 
운전해서 여행가는 것과 비슷한데 거리가 짧더라도 국도를 이용하는 것보다는 고속도로로 가는 것이 훨씬 빨리 도착하는 경우가 많잖아요?
 
신호도 안 막히고 차들이 모두 한 방향으로 가기 때문에 병목이 발생할 일도 적기 때문이죠!
 
논문에서 제안한 highway도 비슷합니다.
agent들이 highway라는 통제된 경로로 많이 가게 된다면 괜히 서로 마주보는 경로가 계획되어 conflict가 발생하는 경우가 줄어들 것이라는 생각이죠.

• 물론 최적의 경로는 아니겠지만 탐색 속도는 빨라질 수 있습니다.

highway를 사용하는 예시

 
 

1.2. 그래서 고속도로를 어떻게 만들어?

이제 대충 highway가 뭔지는 알겠는데 그래서 어떻게 만드는 걸까요?
 
방법은 생각보다 매우 단순합니다. 휴리스틱 값을 계산할 때 highway 이외의 엣지들의 비용을 늘려버리는 것이죠.

highway 내의 엣지들의 heuristic 값을 올리는 방법

 

1.3. 실제로 효과가 있었어?

저는 이 단순한 아이디어가 얼마나 효과가 있을지 궁금해서 바로 결과 부분으로 갔습니다...!
 
하지만 결과가 썩 좋지는 않더라고요... 한번 해볼까? 하는 정도의 결과였습니다.
 
사실 저희들은 이미 비슷한 방식으로 로봇의 경로를 제어한 경험이 있기에 이 방식의 효과를 수치적으로 보고 싶은 마음이 컸습니다.
아쉽게도 결과는 별로였지만요...

결과 비교 1

결과 비교 2

그래도 로봇의 경로를 어느 정도 제어할 수 있다는 점에서는 꽤 의미가 있습니다.
 
'로봇이 반시계 방향으로 움직이도록 해주세요', '왠만하면 로봇이 통로 좌측으로 이동하게 해주세요' 같은 현장 요구사항이 많은데 엣지의 비용을 조절하는 것은 꽤나 효과적인 방법입니다.
 

2. 실제로 좁은 통로(corridor)를 인지하고 constraint 추가하기

New techniques for pairwise symmetry breaking in multi-agent path finding 논문에서는 corridor conflict를 식별하고 해소하는 방법을 제안합니다.
 
 

2.1. Corridor Conflict란?

일단 논문에서는 corridor를 degree가 2인 vertex들과 연결된 edge들의 집합이라고 정의합니다.

corridor 정의하는 부분

 
간단한 예시를 드리면 다음과 같은 일자 통로가 있습니다.

corridor 예시

 
이러한 corridor에서 conflict가 발생하면 어느 하나의 agent가 corridor를 전부 지나갈 때까지 다른 agent가 해당 corridor에 못 들어오도록 constraint가 생성되어야 합니다.
 
하지만 agent가 우선 순위가 없는 CBS는 이 과정이 매우 험난할 수 밖에 없죠...ㅜ
 
논문에서는 이 어려움을 수치로 분석했는데요. corridor의 길이에 따라서 필요한 constraint을 만들기까지 필요한 노드 확장 수를 보여줍니다.

corridor 길이에 따른 노드 확장 수

 

2.2. Corridor Conflict를 식별하는 방법

논문에서는 다음으로 구체적으로 corridor conflict를 식별하는 방법을 제안합니다.
 
1. conflict가 발생하면 해당 conflict가 corridor에서 발생했는지 확인합니다.
    - conflict가 발생한 edge와 연결된 vertex의 degree가 2인지 혹은 vertex의 degree가 2인지 확인합니다.
2. 만약 conflict가 corridor에서 발생했다면 각 agent들의 경로를 확인해서 서로 마주보는 방향으로 이동하는지 확인합니다.
    - 두 agent가 corridor의 다른 방향에서 들어오는 것을 corridor conflict라고 합니다.
    - 만약 agent가 corridor의 같은 방향에서 들어온 것이라면 corridor conflict가 아닙니다.
 

이런 경우만 corridor conflict!

 

2.3. Corridor Conflict를 해소하는 방법

corridor conflict를 식별했으면 당연히 해소해야겠죠?
 
해소하는 방법도 생각보다 간단했습니다. 각 agent들을 corridor가 끝나는 vertex에 못 오게 하는 것입니다.

논문에서 제안하는 corridor conflict 해소 방법

각 agent가 corridor의 끝에 못 오도록 constraint을 추가하는 예시

 
사실 이해가 되지 않았습니다.
'corridor의 끝을 막을 것이 아니라 corridor의 입구를 막아야 하는 거 아닌가?' 라는 질문이 바로 들었거든요.

• 심지어 예시로 들어준 경로 계획의 결과가 각 agent들이 corridor 입구에서 기다릴 것이다 라고 하니 더 이해가 안되더라고요 ㅋㅋㅋ

corridor 입구에서 기다린다고...?

 
여기서 이해가 안되서 corridor reasoning에 관한 자료를 더 찾다보니 Jiaoyang-Li 님의 CBSH2-RTC 레포지토리를 찾게 되었습니다.
이 레포지토리가 위의 논문을 구현한 것 같더라고요!

본 논문과

• 참고: https://github.com/Jiaoyang-Li/CBSH2-RTC

 
그런데 구현을 보니 corridor의 입구부터 막습니다. 오잉?

논문과 다른 구현...?

 
edge 변수가 getCorridorLength라는 함수에서 값이 정해지는데 getCorridorLength 함수를 보면
edge 변수에는는 corridor의 첫번째 엣지가 저장됩니다.

edge 변수를 저장하는 부분

 

3. 실제로 적용할 수 있을까?

두 논문을 읽어보고 나서 실제 로봇 관제에 적용할 때에 발생할 수 있는 어려움들이 없는지 생각해봤습니다.
 
제일 먼저 'Corridor 안에 목적지가 있으면 어떡하지?' 라는 질문이 떠오르더라고요.
Corridor Conflict 식별 및 해소 방법으로 아무런 문제가 없는지 검토해봤습니다.
 

3.1. Corridor 내에 멈춰 있는 로봇이 막는 경우

Corridor 안에 목적지가 있다면 해당 목적지에 도착한 로봇이 예상보다 오래 머무를 수 있습니다.
예를 들어서 다음과 같이 a2가 오래 머무르고 있고 a1이 이를 지나가야 되는 경우에는 경로가 어떻게 계획되어야 할까요?

corridor에 멈춰있는 a2가 a1에 경로를 막은 상황

 
제가 생각하는 이상적인 경로는 a2의 경로가 정해지기 전까지는 a1이 corridor 밖에서 대기하는 것입니다.
a2가 좁은 통로를 막아버리는 것이죠.
 
이 경우는 엣지케이스로 다뤄야 할 것 같습니다.
만약 Dummy Endpoint를 사용하고 있다면 a2가 corridor 내의 목적지를 Dummy Endpoint로 사용하지 않아야 하겠죠?
 

3.2. Corridor 내에 로봇이 멈춰 있지만 길을 막지 않는 경우

그렇다면 a1도 corridor에 있는 목적지에 가야하는 경우에는 경로가 어떻게 계획되어야 할까요?

a1도 corridor에 멈추는 상황

 
제가 생각하는 이상적인 경로는 a1이 corridor에 도착하는 것입니다.
애초에 conflict가 발생하지 않기 때문에 경로도 문제 없이 계획될 것입니다.
 

3.3. Corridor 내에서 멈춰있던 로봇이 Corridor 내에서 멈춰있는 다른 로봇의 위치로 이동하고 싶은 경우

3.2. 의 상황을 거쳐서 a1과 a2가 모두 corridor 내에 멈춰 있습니다.
 
이 때, a1이 a2의 위치로 이동하고 싶으면 어떻게 해야 할까요?

corridor 내에 멈춰 있던 a1이 a2의 위치로 이동하고 싶은 경우

 
제가 생각하는 방법은 2가지가 있습니다.
1. a1이 corridor 내에서 a2가 이동하기를 기다린다.
2. a1이 corridor 밖에서 a2가 이동하기를 기다린다.
 
1 같은 경우에는 a2가 a1가 같은 방향으로 움직일 수 있다는 가능성을 믿고 a1을 그 자리에 위치시키는 것이고
2는 a2가 a1가 반대 방향으로 움직일 수도 있으니 a1을 미리 corridor 밖으로 빼두자 라는 생각입니다.
 
1, 2 둘다 합리적인 방법이지만 '로봇이 corridor 안에 있을 때 다른 로봇은 corridor 밖에서 기다린다'는 일관성 있는 정책을 가져갈 수 있는 것은 2인 것 같습니다.

3.4. Corridor 내에서 멈춰있던 로봇들이 서로의 위치로 이동하고 싶은 경우

3.2. 의 상황을 거쳐서 a1과 a2가 모두 corridor 내에 멈춰 있습니다.
 
이 때, a1과 a2가 서로의 위치로 이동하고 싶으면 어떻게 해야 할까요?

Corridor 내의 두 로봇의 위치를 바꾸고 싶은 경우

 
a1 혹은 a2가 corridor 밖으로 나가야 합니다.
이러한 경로가 빨리 탐색되기 위해서는 a1 혹은 a2가 corridor를 나가야만 하도록 constraint이 추가되어야 합니다.
 
위의 지도를 아래 그림과 같이 표시할 때 a1과 a2에게 추가되어야 하는 constraint은 다음과 같습니다.

• a1: {(1-4, (4, 1)), (1-4, (3, 1)), (2-4, (2, 1)}
• a2: {(1-4, (3, 1)), (1-4, (4, 1)), (2-4, (5, 1)}

지도에 좌표를 부여한 예시

 
이러한 constraint을 만들기 위해서는 corridor conflict가 처음 발생한 edge부터 corridor가 끝날 때까지 로봇의 이동방향의 반대 방향으로 edge constraint을 추가해나가면 됩니다.

• 시간 범위의 시작점을 1씩 증가시켜야 corridor를 빠져나갈 수 있습니다.

3.5. Corridor가 너무 긴 경우

만약 corridor가 너무 긴 경우에는 어떻게 해야 할까요?

Corridor가 너무 긴 예시

 
개인적인 의견이지만 이런 경우에는 로봇이 한 방향으로만 움직이는 단순한 방법이 더 효율적인 것 같습니다.
대신에 agent들의 다음 목적지가 그 방향에 맞게끔 정해져야겠죠...!

---

이렇게 Corridor Reasoning에 대해서 공부해봤습니다.

이제 다시 Anytime Lifelong Multi-Agent Pathfinding in Topological Maps 논문 공부하러 가야겠습니다!!!

오래 걸렸네용 ㅋㅋㅋㅋ