时间复杂性
运动规划
计算机科学
路径(计算)
多项式的
机器人
数学优化
数学
算法
人工智能
数学分析
程序设计语言
标识
DOI:10.15607/rss.2022.xviii.057
摘要
It is well-known that graph-based multi-robot path planning (MRPP) is NP-hard to optimally solve.In this work, we propose the first low polynomial-time algorithm for MRPP achieving 1-1.5 asymptotic optimality guarantees on solution makespan (i.e., the time it takes to complete a reconfiguration of the robots) for random instances under very high robot density, with high probability.The dual guarantee on computational efficiency and solution optimality suggests our proposed general method is promising in significantly scaling up multi-robot applications for logistics, e.g., at large robotic warehouses.Specifically, on an m1 × m2 gird, m1 ≥ m2, our RTH (Rubik Table with Highways) algorithm computes solutions for routing up to m 1 m 2 3 robots with uniformly randomly distributed start and goal configurations with a makespan of m1 + 2m2 + o(m1), with high probability.Because the minimum makespan for such instances is m1 + m2 -o(m1), also with high probability, RTH guarantees m 1 +2m 2 m 1 +m 2 optimality as m1 → ∞ for random instances with up to 1 3 robot density, with high probability.Alongside this key result, we also establish a series of related results supporting even higher robot densities and environments with regularly distributed obstacles, which directly map to real-world parcel sorting scenarios.Building on the baseline methods with provable guarantees, we have developed effective, principled heuristics that further improve the computed optimality of the RTH algorithms.In extensive numerical evaluations, RTH and its variants demonstrate exceptional scalability as compared with methods including ECBS and DDM, scaling to over 450 × 300 grids with 45, 000 robots, and consistently achieves makespan around 1.5 optimal or better, as predicted by our theoretical analysis.
科研通智能强力驱动
Strongly Powered by AbleSci AI