최근에 로봇 관제 업무를 담당하게 되었는데, 그중 다수의 로봇을 부딫치지 않고 각자의 목적지까지 보내야 하는 미션이 있었다. 이번 Article에서는 여러 접근 방식중 MAPF라는 분야에 대해 우선 공부하고 정리하는 글을 쓰고자 한다. 해당 내용은 내 생각 + MAPF 정리 논문인 Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks을 참고하여 작성해보려고 한다.

일단 문제 정의부터

우선 MAPF가 주로 연구되는 도메인은 Warehouse, autonomous vehicle등이 있다. 이러한 도메인의 특징은 다수의 agent, 로봇이 존재하는 환경에서 각 agent마다 경로탐색시 다른 agent를 고려해야 한다는 것이다. 이러한 제약조건을 가지고 각각의 로봇의 경로는 효율적이면서 충돌이 없어야 하는데, 이러한 조건을 충족하는 경로를 생성하는 알고리즘이 바로 MAPF(Multi Agent Path Finding)이다.

즉 MAPF란 복수의 Agent가 충돌없이 각각의 goal까지 가는데 필요한 효율적인 경로를 탐색하는 알고리즘인 것이다.

Classical MAPF란?

우선 가장 기본적인 MAPF의 정의와 지금까지 문제 사항과 MAPF에 대해 간단하게 알아보았다. 이제 가장 기본적인 MAPF인 Classical MAPF에 대해 수학적으로 정의해보면서 정리해보려고 한다. 앞서 언급한 논문 Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks에 따르면 K개의 Agent가 있을 때 Classical MAPF 문제의 제약조건은 다음과 같다.

이산시간을 기반으로 계산
각 시간마다 agent는 하나의 그래프 상 정점 위에 존재
각 시간마다 agent는 단일 action을 수행(이웃노드 이동, 대기)

위의 제약조건은 다음 영상에서 잘 확인 할 수 있다. 해당 영상은 MAPF 논문중 하나인 PIBT의 구현 영상인데, 나중에 다시한번 다뤄보려고 한다.

이러한 제약조건 안에서 MAPF 함수의 input은 아래 식과 같이 정의한다고 한다.

\[\begin{aligned} & input = \langle G, s, t \rangle \\ G &= (V, E) \\ s &: [s_1, s_2, ... , s_k], s_i \in V \\ e &: [e_1, e_2, ... , e_k], e_i \in E \end{aligned}\]

위 튜플의 각각의 요소는 각각 $G$는 단방향 그래프, $s$는 agent별 시작 정점 집합, $e$는 agent별 목표 정점 집합이다. Classical MAPF에서는 각각의 에이전트가 단위시간마다 하나의 action $a$를 할 수 있다. action은 아래 식과 같이 vertex에서 이웃 vertex로 이동 혹은 현재 위치에 대기하는것으로 정의된다.

\[\begin{aligned} a : V \rightarrow V \\ a(v) = v' \\ (v, v') \in E \end{aligned}\]

마지막으로 Classical MAPF에서 output은 모든 에이전트가 source로부터 goal까지 가는데 필요한 경로를 일련의 action인 $\pi$로 정의하고 식은 아래와 같다.

\[\begin{aligned} output &= (\pi_1, \pi_2, ..., \pi_k)\\ \pi &= (a_1, a_2, ..., a_n) \end{aligned}\]

즉 i번째 에이전트의 경로를 $\pi_i$라고 할 때 $x$시간 뒤의 i번째 agent의 위치를 $\pi_i[x] = a_x(a_{x-1}(…a_1(s_i)))$로 나타낼 수 있는 것이다.

Types of Conflicts

MAPF는 다중 agent에 대해 충돌이 없는 각 agent별 경로를 구하기 위한 알고리즘이다. 그렇기 때문에 과연 충돌을 어떻게 정의할 것 인지 먼저 짚고 넘어가자. Classical MAPF에서는 아래 내용과 같은 충돌이 있다고 한다. 해당 내용은 읽고 어느정도 중복이나 불필요한 부분을 제거한 내용이다. 자세한 정의에 대해선 논문을 참고하도록 하자

(a) Vertex conflict

i번째와 j번째 agent의 경로 $\pi_i, \pi_j$가 있을 때 특정 시간 $x$에서 $\pi_i[x] = \pi_j[x]$인 경우를 의미한다. Vertex 충돌은 아래 그림과 같이 서로 다른 두 agent가 같은 시간에 같은 정점에 도착하는 경우를 의미한다.

Vertex Conflict

(a) Edge conflict

i번째와 j번째 agent의 경로 $\pi_i, \pi_j$가 있을 때 특정 시간 $x$와 $x+1$에서 $\pi_i[x] = \pi_j[x]$와 $\pi_i[x+1] = \pi_j[x+1]$인 경우를 의미한다. 해당 경우는 단방향 그래프에서 복수의 agent 가 같은 시간에 같은 edge를 지나는 경우인데, 같은시간에 다른방향에서의 edge를 타는 경우도 존재한다. $\pi_i[x] = \pi_j[x+1]$와 $\pi_i[x+1] = \pi_j[x]$이와 같은 경우인데, 이 경우는 Swapping conflict라고 부르기도 한다.

Edge Conflict

(c) Etc Conflict

그 외에도 여러 agent가 꼬리를 물고 움직이는 Following Conflict, Cycle Conflict등이 존재한다. 이러한 충돌들은 해당 MAPF알고리즘이 사용되는 현장, 목적으로 하는 로봇의 구조 등에 따라 모두 다르게 정의되고 사용되기 때문에 MAPF솔루션을 개발 할 때는 허용되지 않는 충돌 유형을 잘 정의해야 한다.

기타 사항

그 외에 MAPF에서 필요로 하는 룰이 몇가지 더 있는데, 해당 내용들에 대해서는 그렇게 복잡한 내용은 아니기 때문에 간단하게 정리하겠다.

가장 먼저 다룰 규칙은 “타겟에 도착한 agent를 어떻게 처리 할 것인가?”에 대한 내용이다. 보통 두가지 룰이 있는데 첫번째는 그냥 도착하자마자 agent가 사라지는 것이다. 이 경우 해당 agent는 도착 직후 conflict가 생기지 않게 된다.

두번째는 어찌보면 가장 중요한 내용인데, MAPF는 기본 전제조건은 충돌이 없다는 것이다. 그렇다면 MAPF 알고리즘간의 우위를 평가하는 지표는 어떻게 될까? 이를 MAPF의 Objective Function으로 정의하고 Classical MAPF에서는 두가지를 주로 사용하는데, 해당 내용은 아래와 같다.

1. Makespan : 모든 에이전트가 목적지에 도달하는데 걸리는 시간을 의미한다. 즉 도착하는데 걸리는 시간이 가장 긴 에이전트의 경로의 길이가 Makespan이 된다.

2. Sum of Cost : 모든 에이전트의 경로 길이의 합$(=\sum length(\pi_i))$이다.

이 외에도 다양한 목적함수가 있지만 해당 내용에 대해서는 관련 논문을 리뷰해보면서 자세하게 설명하면 될 것 같다.

마치며

지금까지 Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks의 내용을 기반으로 MAPF의 정의와 Classical MAPF에 대해 알아보았다. 그 뒤에도 이제 발전된 MAPF에 대한 내용이나 벤치마크에 대한 내용이 추가로 있는데, 해당 내용은 다음 포스트에서 추가로 내 생각과 함께 정리해보려고 한다.