An iterative approach for makespan-minimized multi-agent path planning in discrete space
An iterative approach for makespan-minimized multi-agent path planning in discrete space
复制标题
DOI：
10.1007/s10458-014-9259-z
复制
发表时间：
2014-04
影响因子：
1.9
通讯作者：
Wenjie Wang;Wooi-Boon Goh
中科院分区：
文献类型：
--
作者：
Wenjie Wang;Wooi-Boon Goh
Makespan最小化多智能体路径规划（MAPP）的目标是使最慢的智能体到达目的地所需的时间最小化，本质上是一个极小极大约束优化问题。在这项工作中，提出了一种迭代最大最小改进（IMMI）算法来近似最优解的最大完工时间最小化MAPP问题。在每次迭代中，线性最大化问题使用单纯形法求解，然后使用局部搜索方法求解计算困难的MAPP最小化问题。为了避免局部搜索陷入不可行解，提出了一种引导局部搜索技术。与其他MAPP算法的比较结果表明，所提出的IMMI算法罢工之间的能力，找到可行的解决方案，可以快速遍历和计算时间在确定这些路径产生了很好的权衡。
Makespan-minimized multi-agent path planning (MAPP) seeks to minimize the time taken by the slowest ofnagents to reach its destination and this is essentially a minimax-constrained optimization problem. In this work, an iterative max-min improvement (IMMI) algorithm is proposed to approximate the optimal solution of the makespan-minimized MAPP problem. At each iteration, a linear maximization problem is solved using a simplex method followed by a computationally hard MAPP minimization problem that is solved using a local search approach. To keep the local search from being trapped in an unfeasible solution, a Guided Local Search technique is proposed. Comparative results with other MAPP algorithms suggest that the proposed IMMI algorithm strikes a good tradeoff between the ability to find feasible solutions that can be traversed quickly and the computational time incurred in determining these paths.