Abstract
The lifelong multiagent pickup-and-delivery problem has been studied for autonomous carrier robots that perform tasks continuously generated on demand in warehouses. It is an extension of continuous multiagent pathfinding problems, and a set of move paths along which agents simultaneously travel without collision is continuously solved for dynamically updated source and destination locations. Fundamental solution methods employ endpoints (EPs) that can be either beginning or end locations of agents’ move paths. EPs are used to consider the situations where some paths are locked by reservation, and deadlocks among reserved paths need to be avoided. While several heuristic techniques have been proposed to improve the solution method, there have been opportunities to investigate their effect and influence in order to integrate these techniques. As an analysis of solution techniques with endpoints for lifelong MAPD problems, we integrated several solution techniques in stages and experimentally investigated their effects and influence. Here, we experimentally present the effect of the proposed approach and generally consider the possibilities of integrated efficient methods. Our results show how the redundancies of problems and move paths can be reduced by the integrated techniques. On the other hand, there are several trade-offs among the heuristics combined for the concurrency of tasks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Barer, M., Sharon, G., Stern, R., Felner, A.: Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In: Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014), vol. 5, no. 1, pp. 19–27 (2014). https://ojs.aaai.org/index.php/SOCS/article/view/18315
Grenouilleau, F., van Hoeve, W.J., Hooker, J.: A multi-label A* algorithm for multi-agent pathfinding. In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, pp. 181–185 (2019)
Hart, P., N.N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Hart, P., N.N., Raphael, B.: Correction to a formal basis for the heuristic determination of minimum-cost paths. SIGART Newsl. (37), 28–29 (1972). https://dl.acm.org/doi/10.1145/1056777.1056779
Li, J., Tinka, A., Kiesel, S., Durham, J.W., Kumar, T.K.S., Koenig, S.: Lifelong multi-agent path finding in large-scale warehouses. In: Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, pp. 11272–11281 (2021)
Liu, M., Ma, H., Li, J., Koenig, S.: Task and path planning for multi-agent pickup and delivery. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 1152–1160 (2019)
Ma, H., Harabor, D., Stuckey, P.J., Li, J., Koenig, S.: Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, pp. 7643–7650 (2019)
Ma, H., Li, J., Kumar, T.S., Koenig, S.: Lifelong multi-agent path finding for online pickup and delivery tasks. In: Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, pp. 837–845 (2017)
Okumura, K., Machida, M., Défago, X., Tamura, Y.: Priority inheritance with backtracking for iterative multi-agent path finding. Artif. Intell. 310, 103752 (2022). https://www.sciencedirect.com/science/article/pii/S0004370222000923?via%3Dihub
Okumura, K., Tamura, Y., Défago, X.: winPIBT: expanded prioritized algorithm for iterative multi-agent path finding. CoRR abs/1905.10149 (2019). http://arxiv.org/abs/1905.10149
Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015)
Shimokawa, M., Matsui, T.: Improvement of task allocation in TP algorithm for MAPD problem by relaxation of movement limitation and estimation of pickup time. Trans. Jpn. Soc. Artif. Intell. 37(3), A-L84 1–13 (2022)
Silver, D.: Cooperative Pathfinding, pp. 117–122 (2005)
Čáp, M., Vokřínek, J., Kleiner, A.: Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures. In: Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, pp. 324–332 (2015)
Yamauchi, T., Miyashita, Y., Sugawara, T.: Standby-based deadlock avoidance method for multi-agent pickup and delivery tasks. In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 1427–1435 (2022)
Acknowledgements
This study was supported in part by The Public Foundation of Chubu Science and Technology Center (the thirty-third grant for artificial intelligence research).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Matsui, T. (2023). Investigation of Integrating Solution Techniques for Lifelong MAPD Problem Considering Endpoints. In: Mathieu, P., Dignum, F., Novais, P., De la Prieta, F. (eds) Advances in Practical Applications of Agents, Multi-Agent Systems, and Cognitive Mimetics. The PAAMS Collection. PAAMS 2023. Lecture Notes in Computer Science(), vol 13955. Springer, Cham. https://doi.org/10.1007/978-3-031-37616-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-37616-0_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-37615-3
Online ISBN: 978-3-031-37616-0
eBook Packages: Computer ScienceComputer Science (R0)