MAPF 공부 - Multi-Agent Pathfinding 문제 정리한 논문을 다시 정리하기

안녕하세요. 오늘은 Multi-Agent Pathfinding 문제를 정리한 논문인
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks 를 정리하려고 합니다.

• Stern, Roni, et al. "Multi-agent pathfinding: Definitions, variants, and benchmarks." Twelfth Annual Symposium on Combinatorial Search. 2019.

 

MAPF가 무슨 문제이고, 사용되는 용어, 다뤄지고 있는 문제 상황, 해결책 등이 정리되어 있어서 좋았습니다.
간단하게 내용 정리해보겠습니다.

 

---

Multi Agent Path Finding(MAPF)이란?

MAPF는 multi-agent 경로 계획 주요 문제 중 하나로 각 에이전트들이 충돌하지 않아야 한다는 조건이 붙습니다.

자율 주행, 물류센터, 로보틱스 등 다양한 분야의 문제를 해결하기 위해 MAPF가 연구되면서 학계의 주목을 받게 되었다고 합니다(2019년 작성 기준).

그런데 MAPF가 "잘 정의"되지 않은 상태에서 연구가 활발해지다보니 용어의 불분명성, 서로 다른 문제 영역 등의 이유로 연구 간의 비교가 어려워졌습니다.

• 결정적으로 현업에서 어떤 연구를 참고해야 할지 어려워진다...

이 논문에서는 이런 어려움을 해소하기 위해 통일된 용어, 널리 사용되는 벤치마크, 측정 지표를 소개한다고 합니다.

Classical MAPF

MAPF 문제에 대한 일반적인 내용

k개의 에이전트가 있는 MAPF 문제는 일반적으로 <G, s, t>로 표현할 수 있습니다.

• G는 노드들의 집합 V와 엣지들의 집합 E의 쌍으로 표현할 수 있습니다. => G = (V, E)
• s는 k개의 에이전트와 각 에이전트의 초기 위치를 나타내는 관계입니다. => s : [1, 2, ..., k] -> V
• t는 k개의 에이전트와 각 에이전트의 목표 위치를 나타내는 관계입니다. => t : [1, 2, ..., k] -> V

시간은 디지털화 되어 있다고 가정합니다.

• 각 타임 스텝이 끝날 때, 에이전트들은 V의 노드 중 한 곳에 위치합니다.

각 타임 스텝마다 에이전트들은 하나의 액션(a)를 취할 수 있습니다.

• a는 노드 간의 이동으로 a(v) = v' 으로 표현할 수 있습니다.
• 액션의 종류에는 이동(move), 대기(wait)이 있습니다.

이러한 액션의 순열을 다음과 같이 표현합니다.

액션의 순열을 파이라고 하더라구요!

 

MAPF 문제의 해

k개의 에이전트가 있을 때 MAPF 문제의 해는 k개의 액션 순열입니다.

이것들이 바로 해!

하나의 액션 순열은 한 에이전트에게 타임 스탭 별로 전달할 액션들로 이루어져 있습니다.
모든 액션 순열들을 에이전트들에게 분배하여 따라갈 시, 최종적으로 모든 에이전트들이 각자의 목표 위치로 도달하게 됩니다.

그리고 k개의 액션 순열들이 모든 타임 스탭 x에 대해 conflict가 없으면 유효한 해 라고 합니다.

Conflict란

MAPF 문제는 다음과 같은 제약 조건들이 있습니다.

(i≠j, i, j ∈ {1, 2, ... ,k })

• Vertex Conflict
  • x라는 타임 스텝에서 같은 노드로 이동시키게 되는 상황을 Vertex Conflict라고 합니다.

vertex conflict 조건

• Edge Conflict
  • x와 x+1이라는 타임 스텝에서 같은 노드로 이동시키게 되는 상황을 Edge Conflict라고 합니다.

edge conflict 조건

• Following Conflict
  • 하나의 에이전트가 다른 에이전트를 바로 뒤따라 오는 상황을 Following Conflict라고 합니다.
  • "이게 무슨 말이지?" 아리송 할 수 있는데, 에이전트가 다음 목적지에 도착한다고 보장할 수 없기 때문에 이런 Conflict가 존재하는 것 같습니다.

following conflict 조건

• Cycle Conflict
  • 에이전트들이 꼬리에 꼬리를 무는 상황을 Cycle Conflict라고 합니다.

cycle conflict 조건

• Swapping Conflict
  
  • 인접한 두 에이전트가 서로의 위치를 목적지로 하는 상황을 Swapping Conflict라고 합니다.

swapping conflict 조건

위의 5가지 조건들 중 어떤 것을 용인하고, 용인하지 않느냐가 알고리즘을 나누게 됩니다.

 

목적지에 도착하고 나서 에이전트의 관리

MAPF 연구들은 목적지에 도착하고 나서 에이전트를 다르게 관리합니다.

크게 다음 2가지 종류가 있습니다.

• 목적지에 도착한 채로 남아 있는 경우
• 목적지에 도착하면 에이전트가 사라지는 경우

Objective Function

그래서 MAPF는 어떤 값을 최적화시키려는 것일까요?

MAPF 알고리즘들은 주로 다음 2가지 Objective Function을 활용합니다.

• Makespan
  • 마지막 에이전트가 목적지에 도착하기까지 걸린 시간
  • 에이전트 별로 걸린 시간의 최대값입니다.
• Sum of costs
  • 에이전트들이 걸린 시간의 총합입니다.

 

MAPF의 변형

이제 Classical MAPF에 대해서 어느정도 이해가 되죠?

연구라는 것이 똑같은 문제만 주구장창 푸는 것이 아니라서 MAPF를 조금씩 변형하여 해결하는 것들이 많습니다.

 

어떤 것들을 변형하는지 살펴볼까요?

• 그래프 구성
  • cost가 1인 엣지가 상하좌우로만 연결되어 있는 단순 grid가 아닌 weight 변경이 가능하고 엣지 연결이 자유로울 수 있음
• Objective Function의 고도화
  • 단순히 최소 Makespan, Sum of costs를 찾는 것이 아닌 리미트를 걸거나 대열 주행 같은 조건을 걸 수도 있음
• 에이전트의 물리적인 환경을 고려
  • 하나의 에이전트는 하나의 노드만 점유한다는 가정을 깨고, 여러 개의 노드를 점유할 수도 있음
  • 전진만 가능한 에이전트가 있을수도 있음
• 작업 할당 방법
  • Anonymous MAPF
    • 어떤 에이전트가 작업을 할당받는지 중요하지 않은 경우를 Anonymous MAPF 라고 합니다.
  • Colored MAPF
    • 작업의 종류에 따라서 특정 에이전트들만 사용하는 경우를 Colored MAPF 라고 합니다.
  • Online MAPF
    • MAPF 문제가 계속해서 생성되는 경우를 Online MAPF 라고 합니다.
    • 현실세계에서 푸는 문제들은 주로 Online MAPF가 될 것 같습니다.
    • 종류
      • Warehouse model
      • Intersection model
        • 새로운 에이전트가 실시간으로 추가되는 경우를 Intersection model 이라고 합니다.

MAPF에 대해 공부할 수 있는 링크

• http://mapf.info/
• https://potassco.org/asprilo/
• https://movingai.com/