caa a22 4500 605514712 CHVBK 20210128100705.0 cr unu---uuuuu 210128e20150501xx s 000 0 eng 10.1007/s10458-014-9259-z doi (NATIONALLICENCE)springer-10.1007/s10458-014-9259-z An iterative approach for makespan-minimized multi-agent path planning in discrete space [Elektronische Daten] [Wenjie Wang, Wooi Goh] Makespan-minimized multi-agent path planning (MAPP) seeks to minimize the time taken by the slowest of n agents 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. The Author(s), 2014 Path planning nationallicence Multiple agents nationallicence Guided local search nationallicence Wang Wenjie Nanyang Technological University, Singapore, Singapore aut Goh Wooi Nanyang Technological University, Singapore, Singapore aut Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/3(2015-05-01), 335-363 1387-2532 29:3<335 2015 29 10458 https://doi.org/10.1007/s10458-014-9259-z text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10458-014-9259-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Wang Wenjie Nanyang Technological University, Singapore, Singapore aut NATIONALLICENCE 700 1- Goh Wooi Nanyang Technological University, Singapore, Singapore aut NATIONALLICENCE 773 0- Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/3(2015-05-01), 335-363 1387-2532 29:3<335 2015 29 10458