Multi-Marginal Optimal Transport와 Schrödinger Bridges를 이용한 최적 및 확장 가능한 MAPF
요약
본 기사는 익명 다중 에이전트 경로 찾기(MAPF) 문제를 Multi-Marginal Optimal Transport (MMOT) 문제로 재구성하고, 이를 선형 계획법(LP)으로 축소하는 방법을 제시합니다. 특히 익명 환경에 초점을 맞추어, 이 LP가 실현 가능하고 완전 단일 모듈러 조건을 만족함을 증명함으로써 공간 및 시간적으로 충돌이 없는 최소 비용의 정수 수송 경로를 효율적으로 산출할 수 있음을 보여줍니다.
핵심 포인트
- MAPF 문제를 Multi-Marginal Optimal Transport (MMOT) 문제로 모델링함.
- 기하급수적으로 큰 MMOT 문제를 선형 계획법(LP)으로 축소하여 계산 가능하게 만듦.
- 익명 환경에 대한 LP의 실현 가능성 및 완전 단일 모듈러 조건을 확립함.
- 최종적으로 공간과 시간 모두에서 충돌이 없는 최소 비용의 정수 수송 경로를 산출하는 방법을 제시함.
우리는 익명 다중 에이전트 경로 찾기(MAPF)를 고려하는데, 여기서 일련의 로봇들이 유한하고 연결된 그래프 상의 목표 지점들로 이동하는 임무를 받습니다. 우리는 MAPF가 근본적인 마르코프 구조를 가진 특수한 종류의 다중 주변 최적 수송 (Multi-Marginal Optimal Transport, MMOT) 문제로 구성될 수 있음을 보여줍니다. 이 경우, 기하급수적으로 큰 MMOT는 크기가 선형 계획법(LP)으로 축소됩니다. 익명 환경에 초점을 맞춰, 우리는 해당 LP가 실현 가능하고(feasible), 완전 단일 모듈러(totally unimodular)인 조건을 확립하며, 그 결과 공간과 시간 모두에서 겹치지 않는 최소 비용의 정수 $( ext{ extbraceleft}0,1 ext{ extbraceright})$ 수송을 산출합니다. 이 접근 방식을 적용하기 위해
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기