WikiEdge:ArXiv-2409.06486v1/summary

編輯

這篇論文研究了在簡單多邊形內部為標記代理安排的多智能體路徑尋找（Multi-Agent Path Finding, MAPF）問題。目標是找到一系列並行、無衝突的代理動作序列，以最小化所有代理達到各自目標位置所需的總時間（即makespan）。研究集中在特別具有挑戰性的場景，即代理密集排列，每個單元格一個代理，這嚴重限制了代理的移動性，並要求精心協調動作。論文提供了多種新的結果，包括：

1. 多邊形的全面可重構性：描述了簡單多邊形P，其中保證存在重配置計劃；證明了當且僅當P能被2×2正方形覆蓋且具有連通的交叉圖時，這種情況才會發生。
2. 形狀參數對makespan的影響：基於多邊形的形狀參數，提供了makespan和拉伸因子的精細上下界。
3. 算法性能：對於嚴重限制機動性的案例，提供了一套算法，以實現與可實現的拉伸因子相關的漸近最壞情況最優性能。這對應於將獲得的makespan與任何代理的起始和目標位置之間的最大最小距離以及我們的形狀參數所提供的下界之間的比率進行限制。

論文還擴展了Demaine等人的研究結果，他們調查了實體矩形域中的該問題，並與Alpert等人在凸網格圖的片段中提出的排列路由領域密切相關。