Impact of the variation of the number of agents in the cooperative learning of optimal paths using LRTA-star

• Luan C. Klein UTFPR
• Cesar A. Tacla UTFPR
• Mariela Morveli-Espinoza UTFPR

DOI: https://doi.org/10.5753/eniac.2021.18242

Abstract

Algorithms for learning optimal paths are present in several scenarios. Given this, LRTA* (learning real time A*) appears as an option for reconciling planning and action. This article investigate how the variation of the number of agents impacts on the distances traveled by them to find optimal path using the LRTA* in static environments. Experiments show the existence of a relationship that the grater number of agents, the total quantity and per capita movements behave like mathematical curves, the first one like a linear and the second as a decreasing exponential. Through the relationship, it is possible to define the best number of agents in the search for the optimal path in terms of performance.

References

Bordini, R. H., Hübner, J. F., and Wolldridge, M. (2007). Programming multi-agent systems in AgentSpeak using jason, volume 1. John Wiley & Sons ltd.

Edelkamp, S. and Schroedl, S. (2011). Heuristic search: theory and applications. Elsevier.

Felner, A., Stern, R., Shimony, S. E., Boyarski, E., Goldenberg, M., Sharon, G., Sturtevant, N., Wagner, G., and Surynek, P. (2017). Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In Tenth Annual Symposium on Combinatorial Search.

Georgeff, M., Pell, B., Pollack, M., Tambe, M., and Wooldridge, M. (1998). The beliefdesire-intention model of agency. In International workshop on agent theories, architectures, and languages, pages 1–10. Springer-Verlag, London, UK.

Hönig, W., Kiesel, S., Tinka, A., Durham, J. W., and Ayanian, N. (2019). Persistent and IEEE Robotics and Automation robust execution of mapf schedules in warehouses. Letters, 4(2):1125–1131.

Ishida, T. (1998). Real-time search for autonomous agents and multiagent systems. Autonomous Agents and Multi-Agent Systems, 1(2):139–167.

Korf, R. E. (1990). Real-time heuristic search. Atificial Intelligence, 42:189–211.

Ma, H., Koenig, S., Ayanian, N., Cohen, L., Hönig, W., Kumar, T., Uras, T., Xu, H., Tovey, C., and Sharon, G. (2016). Overview: Generalizations of multi-agent path finding to real-world scenarios. arXiv preprint arXiv:1702.05515.

Sharon, G., Stern, R., Felner, A., and Sturtevant, N. R. (2015). Conict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40–66.

Sigurdson, D. (2018). Automatic algorithm selection in videogame pathfinding. Master’s thesis, University of Alberta, Department of Computing Science, Master of Science, Edmonton, Alberta, CA.

Standley, T. S. (2010). Finding optimal solutions to cooperative pathfinding problems. In Twenty-Fourth AAAI Conference on Artificial Intelligence.

Stern, R. (2019). Multi-agent path finding an overview. In Artificial Intelligence, pages 96–115. Springer.

Stern, R., Sturtevant, N. R., Felner, A., Koenig, S., Ma, H., Walker, T. T., Li, J., Atzmon, D., Cohen, L., Kumar, T. S., et al. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Twelfth Annual Symposium on Combinatorial Search.

Sturtevant, N. R. (2012). Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 4(2):144–148.

Vidal, J. M. (2007). Fundamentals of multiagent systems with NetLogo examples. Citeseer.

Wooldridge, M. (2009). An introduction to multiagent systems. John Wiley & Sons.

Zafar, K. and Baig, A. R. (2012). Optimization of route planning and exploration using multi agent system. Multimedia Tools and Applications, 56(2):245–265.