MAPF를 마르코프 구조의 멀티 주변 최적 수송(MMOT)으로 환원하고, Schrödinger bridge로 확장한다. 지수적 문제가 다항 크기 선형계획으로 붕괴한다.
익명 MAPF는 유한·연결 그래프 위에서 N개의 로봇을 N개의 목표로 충돌 없이 이동시키는 문제다. 할당·경로 계획·스케줄링이 결합되어 본질적으로 조합적이다. 이 논문은 MAPF를 경로 공간 위의 멀티 주변 최적 수송으로 캐스팅한다.
경로 공간 텐서 P는 전체 시공간 궤적에 직접 질량을 할당한다. 로봇 운동은 시간상 인과적이므로 과정 (Xt)는 마르코프적이다. 이 마르코프 인수분해가 자유 변수를 K^(T+1) (T에 지수적)에서 K²T (T에 다항적)로 줄인다. 동시에 일반 MMOT의 T+1개 주변 고정 제약이 두 경계 주변 — 시작 분포 q₀=μ와 종료 분포 q_T=ν — 만으로 완화된다.
파이프라인은 정확 최적 LP에서 출발해, 확률적 완화로 빠른 그림자를 얻고, 그 그림자를 틀로 삼아 정수해를 회복한다. 세 상수 ε, λ, η가 최적성과 확장성의 스펙트럼을 가른다.
전송 계획 {Πₜ}를 실수 비음 변수로 두는 선형계획이다. 접착 제약(마르코프성), 종단 제약(경계 위치 고정), 정점 용량 제약(각 정점당 로봇 최대 하나)을 부과한다.
참조 분포를 Gibbs 커널로 택하면 Schrödinger bridge가 MMOT의 엔트로피 정규화로 환원된다. Sinkhorn 유형 반복이 분수적 그림자 전송 — 로봇에서 목표로 향하는 유력 경로 집합 — 을 산출한다.
엔트로피 전송을 완전 유니모듈러 다면체 F 위로 되투영한다. 그림자가 큰 간선에 질량을 편향시키는 수정 비용으로, 가지치기된 축소 그래프 위에서 LP를 푼다.
시간 확장 그래프에 Ford–Fulkerson 정점 분할을 적용하면 제약 행렬이 유향 그래프의 노드-호 접속 행렬 형태가 된다. 접속 행렬은 완전 유니모듈러(TU)이며, 따라서 실현 가능 다면체의 모든 극점이 정수가 된다. 정수계획이나 분기 한정 없이 연속 LP에서 실행 가능한 로봇 경로가 나온다.
펩블 운동 이론에 따라 익명 로봇의 구성 공간은 연결되어 있다. 그래프가 유한·연결이면 종단 구성 ν가 μ에서 유한 스텝 T̄ 내에 확률 1로 도달 가능하다.
P1은 정수 최적해 Π*ₜ ∈ {0,1}를 가지며, 최소 비용을 달성하고, K와 T̄에 다항인 복잡도를 갖는다. 제약 행렬의 TU가 이를 첫 원리에서 보장한다.
어떤 시각에도 두 로봇이 충돌하지 않고, 궤적이 공간·시간 양쪽에서 겹치지 않으며, 모든 로봇이 서로 다른 목표에 도달한다. 양방향 교환과 순환 흐름은 대기 이동으로 치환되어 비용이 감소하므로 최적해에 나타나지 않는다.
지수 증가 비용 구조로 makespan 최적성을 목적함수에 암묵적으로 인코딩하거나, 최소 makespan T* ≤ N+K−1에 대해 O(log K)회 P1 호출로 이진 탐색하여 명시적으로 찾는다.
Gibbs 매개변수 ε는 그림자 전송의 응집도를 결정한다. ε → 0에서 Schrödinger bridge는 최소 비용 지오데식 회랑으로 질량을 집중시켜 공격적 가지치기를 낮은 비용 격차로 가능케 한다. ε가 커지면 그림자가 확산되어 가지치기된 그래프가 덜 판별적인 간선을 더 많이 남긴다. 아래 슬라이더로 이 전이를 직접 확인한다.
실측값 출처: Table 3 (K=10,000, T=30, λ=0, 13개 인스턴스 평균). 슬라이더는 논문의 이산 측정점 ε ∈ {0.1, 0.2, 0.5, 1.0, 5.0} 사이를 보간한다.
K = 2,500에서 22,500 정점까지(369K–3.4M LP 변수) 5% 로봇 밀도, T=30에서 측정한다. P1 solve 시간은 O(K^1.68)로 증가하는 반면 P2+P3 파이프라인은 거의 선형 O(K^1.15)로 확장되어, 10% 미만의 비용 격차로 3.6×에서 7.1× 가속을 얻는다. 모든 실행의 해가 정수임이 검증된다.
| K | N | P1 변수 | P1 (s) | P2+P3 (s) | 가속 | 격차 (%) | 유지 (%) |
|---|---|---|---|---|---|---|---|
| 2,500 | 125 | 369K | 15 | 4 | 3.6× | 8.0 | 32 |
| 5,625 | 281 | 835K | 55 | 11 | 5.0× | 8.7 | 35 |
| 8,100 | 405 | 1.2M | 103 | 18 | 5.7× | 9.0 | 37 |
| 10,000 | 500 | 1.5M | 132 | 26 | 5.1× | 5.9 | 41 |
| 13,225 | 661 | 2.0M | 193 | 33 | 5.8× | 8.1 | 39 |
| 15,625 | 781 | 2.3M | 257 | 48 | 5.3× | 5.9 | 43 |
| 19,600 | 980 | 2.9M | 364 | 62 | 5.8× | 7.2 | 42 |
| 22,500 | 1,125 | 3.4M | 478 | 67 | 7.1× | 6.5 | 40 |
K=10,000에서 ε ∈ {0.1, …, 5.0}, λ ∈ {0, …, 5.0}를 20개 조합으로 스윕한다. 작은 ε(≤0.2)는 P1 최적에 근접한 응집 그림자를 만들어 2–5% 격차로 공격적 가지치기를 가능케 하고, 큰 ε는 그림자를 평활화하여 격차를 17–20%로 키운다. λ는 ε에 따라 1–6%를 더하는 완만한 효과를 낸다.
| ε＼λ | 0 | 0.5 | 1.0 | 5.0 |
|---|---|---|---|---|
| 0.1 | 2.3 | 2.5 | 2.7 | 3.0 |
| 0.2 | 4.3 | 5.0 | 5.8 | 7.3 |
| 0.5 | 11.1 | 12.7 | 14.0 | 16.5 |
| 1.0 | 17.3 | 18.9 | 20.1 | 23.1 |
| 5.0 | 17.1 | 18.0 | 18.7 | 19.9 |
P1 대비 평균 비용 격차(%). 강건한 기본값은 ε=0.2, λ=0 — 5× 가속에서 4.3% 격차.
30×30 그리드, 10% 장애물, 4-근접 연결에서 비교한다. 선행 CBM은 min-cost max-flow와 충돌 기반 탐색을 결합하지만 제약 행렬의 완전 유니모듈러성을 확립하지 못해, 단일 팀에서도 정수해를 보장하려면 ILP나 계층적 탐색에 의존해야 한다. 반면 P1은 TU를 통해 연속 LP에서 정수해를 보장한다.
| Method | Agents | Time (s) | Success |
|---|---|---|---|
| CBM (Ma & Koenig, 2016) | 50 | 5.32 | 100% |
| ILP (Ma & Koenig, 2016) | 50 | 162 | 4% |
| ILP (Ma & Koenig, 2016) | 40 | 153 | 14% |
| P1 (ours) | 300 | 0.54 | 100% |
| P2+P3 (ours) | 300 | 0.49 | 100% |