이전 포스트에서 MAPF의 기본적인 내용에 대해 간단하게 정리해보았다. 하지만 Classical MAPF는 실제 현실에서 사용하기 좀 힘든 부분이 많다. 이러한 한계점을 극복하기위해 더 고도화되고 변형된 MAPF가 많이 나왔는데, 간단하게 알아보자.


Classical MAPF의 한계점

Classical MAPF는 추상적인 환경을 기반으로하기 때문에 현실에 적용하기 힘든데, 이는 아래와 같은 가정을 사용하기 때문이다.

  1. 이산시간 기반
  2. 한 time step에 한가지 action만 수행
  3. 각 agent는 time step마다 하나의 정점만 점유

하지만 현실에서는 로봇이 이렇게 움직일 수 없기 때문에, 위와같은 가정을 완화하는 여러 아이디어들이 나왔다. 이번 포스트에서는 Classical MAPF와 현실 사이의 간극은 무었이 있고, 어떤식으로 이러한 차이를 극복하려고 했던 시도에 대해 정리해보려고 한다.


MAPF on Weighted Graph

실제 로봇은 주행 환경, 주행 모드, 외부 요소등에 따라 같은 길을 가더라도 이동시간이 조금씩 다를 수 있다. 자율주행 로봇의 경우 환경에 따라 서로 다른 Motion을 통해 움직이기 때문이다. 이러한 점 때문에 하나의 액션이 무조건 한 timestep동안 수행된다는 가정을 할 경우, 복잡한 Motion을 가지는 로봇에 적용하기가 힘들다. 이렇게 추상화된 실행 시간에서 오는 에러를 고려하기위해 edge가 가중치로 행동에 걸리는 시간을 갖는 Weighted Graph를 이용한 MAPF가 제안되었다고 한다.

$2^k$-neighbor grids

해당 방식은 2차원 그리드 맵에서 기본 이동 외에 k에 따라 이동가능한 이웃노드를 확장하는 방식으로 맵을 구성한다. 각 노드에서 이웃노드는 아래 사진과 같이 정의되고, 이웃노드까지의 가중치는 노드간 Euclidean Distance로 정의된다.

2^k neighbor

MAPF in Euclidean space

해당 방식은 위의 방식과 달리 Euclidean Space상의 정점으로 이루어진 Graph를 맵으로 사용한다. 또한 Graph에서 가중치는 해당 정점에서 정점을 이동 할 때 걸리는 시간으로 정의한다. 해당 논문에서는 대표적인 예시로 Khatib 1986; Wagner, Kang, and Choset 2012를 소개했다. 이렇게 계산하는 경우 넓은 맵을 RRT등의 랜덤샘플링 기반 탐색방식으로 빠르게 계산 할 수 있다는 장점이 있다.


Feasibility Rules

단순 예측 실패, 미식별 장애물 등에 따라 로봇의 움직임은 MAPF를 통한 예측과 다르게 움직일 수 있디. 이러한 상황에 대해 정의하고자 해당 논문에서는 실현가능성feasibility이라는 새로운 MAPF의 전제조건을 제시한다. 말 그대로 MAPF의 결과를 실제로 로봇들이 정확히 이행 할 수 있는지 여부에 대한 전제조건이다.

Robustness rules: MAPF Solution을 발생 가능한 action 수행 오차를 고려하여 계산하는 방법이다. 이 방법은 실제 수행 오차에 따라 각 agent가 다르게 action을 수행하는 execution policies가 결합 될 수 있다.

Formation rules: Agent의 움직임을 주변 다른 로봇을 고려하여 특정한 포메이션을 만들어 수행하는 방식으로 작동한다. 이 경우 로봇의 각 움직임이 다른 로봇의 움직임에 대해 상대적으로 움직이기 때문에 예측 실패에 대한 충돌 리스크를 배제 할 수 있다.

이러한 방식으로 통해 로봇이 MAPF알고리즘에서 제공한 경로를 실제 움직임으로 변환하여 현실에서의 Multi Robot에 대한 제어를 할 수 있게 된다.


From Pathfinding to Motion Planning

Classical MAPF는 “각 agent는 time step마다 하나의 정점만 점유”라는 전제조건이 있다. 하지만 이런 가정은 실제 로봇의 움직임을 계산할 때 필요한 로봇의 부피, 모양, 제한 속도등을 고려할 수 없게 한다. 이러한 문제를 해결하기 위해 실제 로봇의 볼륨에 따라 다른 정점까지 점유하여 충돌을 고라하는 Multi-Agent Path Finding for Large Agents, 로봇의 주행 속도, 방향등을 고려하여 진행 할 수 있는 edge룰 재헌하여 경로를 탐색하는 Multi-Agent Path Finding with Kinematic Constraints등이 제한되었다.


마치며

이전 포스트부터 간단하게 MAPF의 정의와 한계점 그리고 고도화 방향과 그 예시에 대해 간략하게 정리해 보았다. 참고한 논문에는 추가적으로 단순 source to goal 구조에서 확장된 task를 갖는 MAPF, 실제 작업환경을 고려한 Lifelong MAPF등의 개념이 등장한다. 이런점은 사용 로봇, 환경에 따라 다를 것 같아 다음에 필요할 때 관련 내용을 정리하려고 한다. 그리고 다음 포스트로는 해당 내용을 정리하면서 중요해 보였던 논문들에 대해 자세히 알아보려고 한다.