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

Resumo

Algoritmos de aprendizado de caminhos ótimos estão presentes em diversos cenários. Diante disso, o LRTA* (learning real time A*) surge como uma opção que concilia planejamento e ação. O presente artigo estuda como a variação da quantidade de agentes impacta nas distâncias percorridas por eles para encontrar o caminho ótimo utilizando o LRTA* em ambientes estáticos. Através de experimentos, observou-se a existência de uma relação de que ao aumentar o número de agentes, a quantidade de movimentos totais e per capita tendem a curvas matemáticas, sendo elas uma linear e uma exponencial decrescente, respectivamente. Por meio dessa relação, é possível definir a melhor quantidade de agentes na busca do caminho ótimo em termos de desempenho.

Referências

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.