WikiEdge:ArXiv-2409.06486v1/abs

編輯

• 標題：Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain
• 中文標題：多機器人路徑規劃：在密集填充、有限域中的多智能體路徑尋找
• 發布日期：2024-09-10T13:15:32+00:00
• 作者：Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Jonas Neutzner, Christian Rieck, Christian Scheffer
• 分類：cs.CG, cs.DS, F.2.2
• 原文鏈接：http://arxiv.org/abs/2409.06486v1

摘要：我們研究了在一個簡單連通域內部的標記代理的多智能體路徑規劃問題：給定每個代理的唯一起始位置和目標位置，目標是找到一系列平行的、無碰撞的代理運動，以最小化所有代理到達各自目標所需的總時間（即完工時間）。一個自然的情況是簡單連通的多邊形域，具有軸平行的邊界和整數坐標，即簡單多米諾，這相當於一個簡單連通的格子單位方塊或單元的併集。我們專注於密集打包代理的特別具有挑戰性的設置，即每個單元一個代理，這極大地限制了代理的機動性，並需要複雜的運動協調。我們為這個問題提供了一系列新結果，包括（1）對保證存在重新配置計劃的多米諾的特徵描述；（2）對導致完工時間最壞情況界限的形狀參數的特徵描述；（3）一套算法，以在機動性嚴重受限的情況下實現漸近最壞情況的最優性能。這對應於界定獲得的完工時間與任何代理的起始位置和目標位置之間的最大最小距離所提供的下界及我們的形狀參數之間的比率。我們的結果擴展了Demaine等人（SIAM計算雜誌，2019年）對固體矩形域問題的研究，以及Alpert等人（計算幾何，2022年）在與之密切相關的排列路由領域的研究。