An iterative approach for makespan-minimized multi-agent path planning in discrete space
Tóm tắt
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.
Tài liệu tham khảo
Zhou, J. L., & Tits, A. L. (1993). Nonmonotone line search for minimax problems. Journal of Optimization Theory and Applications, 76(3), 455–476.
Ye, F., Liu, H., Zhou, S., & Liu, S. (2008). A smoothing trust-region Newton-CG method for minimax problem. Journal of Applied Mathematics and Computation, 199(2), 581–589.
Wang, F., & Wang, Y. (2011). Nonmonotone algorithm for minimax optimization problems. Applied Mathematics and Computation, 217(13), 6296–6308.
Polak, E., Mayne, D. Q., & Higgins, J. E. (1991). Superlinearly convergent algorithm for min-max problems. Journal of Optimization Theory and Applications, 69(3), 407–439.
Li, J., & Huo, J. (2011). Inexact smoothing method for large scale minimax optimization. Journal of Applied Mathematics and Computation, 218, 2750–2760.
He, S., & Zhou, S. (2011). A nonlinear augmented lagrangian for constrained minimax problems. Journal of Applied Mathematics and Computation, 218, 4567–4579.
Hopcroft, J. E., Schwartz, J. T., & Sharir, M. (1984). On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the Warehouseman’s problem. IJRR, 3(4), 76–88.
Ratner, D., & Warmuth, M. (1990). The (\(n^2\)-1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10, 111–137.
Svestka, P., & Overmars, M. H. (1998). Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3), 125–152.
Mors, A. T., Witteveen, C., Zutt, J. & Kuipers, F. A. (2010). Context-aware route planning. In 8th German Conference, MATES 2010, Leipzig, Germany (pp. 138–149).
van den Berg, J., Snoeyink, J., Lin, M. & Manocha, D. (2009). Centralized path planning for multiple agents: Optimal decoupling into sequential plans. In Proceedings of Agentics: Science and Systems, Seattle, USA.
Wang, W. & Goh, W. B. (2011). Spatio-temporal A* algorithms for offline multiple mobile robot path planning. In Proceedings of 10th International Conference on Autonomous Agents and Multi-Agent Systems (pp. 1091–1092).
Bennewitz, M., Burgard, W., & Thrun, S. (2001). Optimizing schedules for prioritized path planning of multi-robot systems. In Proceedings of IEEE International Conference on Robotics and Automation (vol.1, pp. 271–276).
Silver, D. (2005). Cooperative pathfinding. In Proceedings of AIIDE (pp. 117–122).
Sturtevant, N. & Buro, M. (2006). Improving collaborative pathfinding using map abstraction. In Proceedings of the Second Artificial Intelligence and Interactive Digital Entertainment Conference (pp. 80–85).
Røger, G. & Helmert, M. (2012). Non-optimal multi-agent pathfinding is solved (since 1984). In Proceedings of the Fifth Annual Symposium on Combinatorial Search (pp. 173–174).
Ryan, M. (2006). Multi-robot path planning with subgraphs. In Proceedings of the 19th Australasian Conference Robotics and Automation.
Ryan, M. (2007). Graph decomposition for efficient multi-robot path planning. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (pp. 2003–2008).
Wang, K.-H. C. & Botea, A. (2008). Fast and memory-efficient multi-agent pathfinding. In Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling.
Wang, K.-H. C. & Botea, A. (2009). Tractable multi-agent path planning on grid maps. In Proceedings of the International Joint Conference on Artificial Intelligence.
Wang, K.-H. C., & Botea, A. (2011). MAPP: A scalable multi-agent path planning algorithm with tractability and completeness guarantees. Journal of Artificial Intelligence Research, 42, 55–90.
Peasgood, M., Clark, C.M. & McPhee, J. (2008). A complete and scalable strategy for coordinating multiple agents within roadmaps. In IEEE Transaction on Agentics (vol. 24, no. 2).
Masehian, E. & Nejad, A. H. (2009). Solvability of multi agent motion planning problems on trees. In IEEE International Conference on Intelligent Agents and Systems.
Khorshid, M. M., Holte, R. C. & Sturtevant, N. (2011). A polynomial-time algorithm for non-optimal multi-agent pathfinding. In Proceedings of the Fourth International Symposium on Combinatorial Search.
Surynek, P. (2009). A novel approach to path planning for multiple robots in bi-connected graphs. In IEEE International Conference on Robotics and Automation (pp. 3613–3619).
Surynek, P. (2009). An application of pebble motion on graphs to abstract multi-robot path planning. In IEEE International Conference on Tools with Artificial Intelligence (pp. 151–158).
Luna, R. & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (pp. 294–300).
Sajid, Q., Luna, R. & Bekris, K. E. (2012). Multi-agent pathfinding with simultaneous execution of single-agent primitives. In Proceedings of Fifth Symposium on Combinatorial Search.
Krontiris, A., Luna, R. & Bekris, K. E. (2013). From feasibility tests to path planners for multi-agent pathfinding. In Symposium on Combinatorial Search.
Ratner, D. & Warmuth, M. K. (1986). Finding a shortest solution for the N N extension of the 15-PUZZLE is intractable. In National Conference on Artificial Intelligence.
Wilde, B. D. (2012). Cooperative multi-agent path planning. Master Thesis, Delft University of Technology.
Standley, T. (2010). Finding optimal solutions to cooperative pathfinding problems. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (pp. 173–178).
Standley, T. & Korf, R. (2011). Complete algorithms for cooperative pathfinding problems. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (pp. 668–673).
Wagner, G. & Choset, H. (2011). M*: A complete multirobot path planning algorithm with performance bounds. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 3260–3267).
Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2011). The increasing cost tree search for optimal multi-agent pathfinding. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (vol. 1, pp. 662–667).
Sharon, G., Stern, R., Felner, A. & Sturtevant, N. (2012). Conflict-based search for optimal multi-agent path finding. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
Yu, J. & LaValle, S. M. (2013). Planning optimal paths for multiple robots on graphs. In 2013 IEEE International Conference on Robotics and Automation.
Geramifard, A., Chubak, P. & Bulitko, V. (2006). Biased cost pathfinding. In Proceedings of AIIDE (pp. 112–114).
Nocedal, J., & Wright, S. J. (1999). Line search methods. In J. Nocedal & S. J. Wright (Eds.), Numerical optimization (2nd ed., pp. 34–63). New York: Springer.
Boyd, S., & Vandenberghe, L. (2004). Duality (chapter 5). In S. Boyd & L. Vandenberghe (Eds.), Convex Optimization (pp. 215–273). Cambridge: Cambridge University Press.
Vanderbei, R. J. (2008). Simplex method (chapter 2). In R. J. Vanderbei (Ed.), Linear programming: Foundations and extensions (3rd ed., pp. 13–27). Boston: Springer.
Watson, J.-P. (2010). An introduction to fitness landscape analysis and cost models for local search. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of metaheuristics (pp. 599–623). Boston: Springer.
Voudouris, C. (1997). Guided Local Search for combinatorial optimisation problems. Ph.D. thesis, Department of Computer Science, University of Essex.
Yu, J., & LaValle, S. M. (2013). Planning optimal paths for multiple robots on graphs. Retrieved from http://msl.cs.uiuc.edu/jyu18/_mapp.html. Accessed 15 Nov 2013.