Multi-Agent Path Finding

• 다른 이름: MAPF, multi-agent pathfinding, multi-robot path planning
• 카테고리: Learning & autonomy › Multi-robot
• 태그: multi-robot, path-planning, warehouse-automation, coordination, graph-search

창고 로봇이 격자 위를 움직이는 경우처럼 공유 그래프 위에서 동시에 움직이는 많은 에이전트에 대해 충돌 없는 경로를 계산하여, 모든 에이전트가 충돌 없이 목표에 도달하게 하는 문제.

정의

다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF)은 환경을 공유하는 에이전트 집단의 경로를 계획하여, 두 에이전트가 같은 시각에 같은 장소를 차지하거나 같은 간선을 따라 서로 자리를 바꾸는 일 없이 각 에이전트가 출발점에서 목표점까지 가도록 하는 문제이다. 환경은 보통 그래프, 흔히 격자로 모델링되며, 시간은 이산적인 단계로 나뉘어 각 단계에서 각 에이전트는 이웃 정점으로 이동하거나 대기한다.

MAPF 해는 보통 모든 에이전트가 목표에 도달하는 데 걸리는 시간의 총합인 비용 합(sum of costs), 또는 마지막 에이전트가 도착할 때까지의 시간인 메이크스팬(makespan)으로 평가한다. 이러한 목표 아래에서 최적해를 찾는 것은 일반적으로 NP-난해이므로, 이 분야는 최적성을 속도와 맞바꾸는 알고리즘들을 발전시켜 왔다. 최적 방법으로는 각 에이전트를 독립적으로 계획한 뒤 탐색 트리에서 제약을 추가해 충돌을 해소하는 Conflict-Based Search(CBS)가 있다. 에이전트가 한 번에 하나씩 계획하고 앞서 계획한 에이전트를 움직이는 장애물로 취급하는 우선순위 계획(prioritized planning) 같은 준최적 방법은 훨씬 큰 팀으로 확장된다.

평생(lifelong) MAPF는 에이전트가 이전 목표에 도달하자마자 새 목표를 받는 변형으로, 창고 로봇과 분류 로봇이 실제로 일하는 방식과 맞아떨어진다. 이 경우 계획은 흔히 제한된 시간 창에 걸쳐 계속 실행되며, 처리량이 주된 척도가 된다.

실제 로봇은 교과서적 가정도 깨뜨린다. 로봇에는 크기, 가속도 한계, 실행 지연이 있으므로, MAPF 계획은 보통 일부 로봇이 일정보다 늦어질 때 로봇들을 안전하게 지키는 추가 조정 계층과 함께 실행된다. 탐색 기반 플래너로부터의 모방 학습을 포함한 학습 기반 방법은 매우 큰 플릿으로 확장하기 위한 활발한 연구 방향이다.

중요한 이유

창고, 공장, 분류 센터는 공유 바닥 위에서 점점 커지는 모바일 로봇 플릿을 운영하며, 그 처리량은 로봇들이 얼마나 잘 조정되는지에 달려 있다. MAPF는 플릿이 커져도 로봇들이 충돌이나 교착 상태 없이 계속 움직이게 하는 알고리즘을 제공한다.

주요 응용

• 창고 및 풀필먼트 센터의 로봇 플릿
• 다수의 모바일 로봇을 사용하는 소포 분류 시스템
• 공장의 무인 운반차(AGV) 조정
• 다중 드론 및 공항 지상 교통 조정
• 비디오 게임의 캐릭터 이동과 군중 시뮬레이션

실제 사례

창고 플릿을 운영하는 팀은 보통 바닥을 격자나 로드맵 그래프로 모델링하며, 각 셀은 로봇 한 대가 들어갈 크기로 정한다. 중앙 플래너는 주문 시스템에서 목표를 받아 조정된 경로를 계산하는데, 전체 문제를 최적으로 푸는 대신 몇 초마다 다시 계획하는 우선순위 기반 탐색이나 시간 창 탐색을 쓰는 경우가 많다. 경로는 시각이 붙은 웨이포인트로 변환되어 로봇에 전송되며, 행동 의존성 그래프(action dependency graph) 같은 실행 계층이 앞선 로봇이 셀을 비우기 전에는 로봇이 그 셀에 들어가지 않도록 보장한다. 엔지니어는 실제 시스템의 바닥 배치나 알고리즘을 바꾸기 전에 전체 플릿 규모의 시뮬레이션에서 처리량, 대기 시간, 교착 상태 빈도를 측정한다.

흔한 오해

• 각 로봇은 자신의 최단 경로를 독립적으로 계획할 수 있다 — 독립적인 경로는 서로 충돌하므로, 로봇은 공간뿐 아니라 시간에서도 조정되어야 한다
• 최적 MAPF는 어떤 플릿 규모로도 확장된다 — 최적해 풀이는 NP-난해이므로, 큰 플릿은 준최적 방법이나 시간 창 방법에 의존한다
• MAPF 계획은 계산된 그대로 정확히 실행될 수 있다 — 실제 로봇은 일정보다 빠르거나 늦게 움직이므로, 실행에는 자체적인 안전 및 조정 계층이 필요하다

알아야 할 사람

• 창고 자동화 및 플릿 관리 엔지니어
• 다중 로봇 계획 연구자
• AMR 및 AGV 시스템 통합 업체
• 물류를 다루는 운영 연구자

관련 기술

• Conflict-Based Search
• 우선순위 계획(Prioritized Planning)
• A 탐색(A Search)
• 플릿 관리 시스템(Fleet Management Systems)
• 모방 학습(Imitation Learning)

관련 용어

• Swarm Robotics
• Motion Planning
• AMR

관련 프로젝트

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
• IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
• Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots