An iterative approach for makespan-minimized multi-agent path planning in discrete space
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605514712 | ||
| 003 | CHVBK | ||
| 005 | 20210128100705.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150501xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s10458-014-9259-z |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s10458-014-9259-z | ||
| 245 | 0 | 3 | |a An iterative approach for makespan-minimized multi-agent path planning in discrete space |h [Elektronische Daten] |c [Wenjie Wang, Wooi Goh] |
| 520 | 3 | |a 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. | |
| 540 | |a The Author(s), 2014 | ||
| 690 | 7 | |a Path planning |2 nationallicence | |
| 690 | 7 | |a Multiple agents |2 nationallicence | |
| 690 | 7 | |a Guided local search |2 nationallicence | |
| 700 | 1 | |a Wang |D Wenjie |u Nanyang Technological University, Singapore, Singapore |4 aut | |
| 700 | 1 | |a Goh |D Wooi |u Nanyang Technological University, Singapore, Singapore |4 aut | |
| 773 | 0 | |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/3(2015-05-01), 335-363 |x 1387-2532 |q 29:3<335 |1 2015 |2 29 |o 10458 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10458-014-9259-z |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s10458-014-9259-z |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Wang |D Wenjie |u Nanyang Technological University, Singapore, Singapore |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Goh |D Wooi |u Nanyang Technological University, Singapore, Singapore |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/3(2015-05-01), 335-363 |x 1387-2532 |q 29:3<335 |1 2015 |2 29 |o 10458 | ||