Parallel Multi-speed Pursuit-Evasion Game Algorithms
Resumo
O Jogo de Perseguição-Fuga (PEG) é importante no campo da robótica. Determinar a estratégia ótima, como o número mínimo de perseguidores necessário, frequentemente exigindo tempo exponencial. Propomos um novo algoritmo paralelo que reduz significativamente o tempo de computação para PEG, tornando possível analisar jogos com um grande número de estados e transições. O algoritmo também se estende aos jogadores heterogêneos/multi-velocidade e incorpora estratégias avançadas Além disso, introduzimos um algoritmo de alocação de recursos para equipes multi-agentes heterogêneas, garantindo o compartilhamento eficiente de recursos e a substituição em tempo real de agentes para manter a tolerância a falhas. Nossas simulações demonstram que nosso algoritmo paralelo supera significativamente as abordagens existentes, alcançando até 8,13 vezes mais velocidade em comparação com o estado da arte. Além disso, nossos algoritmos melhoram a escalabilidade e a aplicabilidade prática na resolução de PEGs.
Palavras-chave:
Jogo de Perseguição e Fuga, Algoritmo Paralelo, Sistemas Multi-agentes, Robôs Heterogêneos, Alocação de Recursos para Multi-Times
Referências
Abbas, W. and Egerstedt, M. (2014). Characterizing heterogeneity in cooperative networks from a resource distribution view-point. Commun. Inf. Syst., 14(1):1–22.
Bopardikar, S. D., Bullo, F., and Hespanha, J. P. (2008). On discrete-time pursuit-evasion games with sensing limitations. IEEE Transactions on Robotics, 24(6):1429–1439.
Chung, T. H., Hollinger, G. A., and Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous robots, 31(4):299.
Huang, H., Zhang, W., Ding, J., Stipanović, D. M., and Tomlin, C. J. (2011). Guaranteed decentralized pursuit-evasion in the plane with multiple pursuers. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pages 4835–4840.
Isaacs, R. (1999). Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover books on mathematics. Dover Publications.
Krishnamoorthy, K., Darbha, S., Khargonekar, P. P., Casbeer, D., Chandler, P., and Pachter, M. (2013). Optimal minimax pursuit evasion on a manhattan grid. In 2013 American Control Conference, pages 3421–3428.
Makkapati, V. R. and Tsiotras, P. (2019). Optimal evading strategies and task allocation in multi-player pursuit–evasion problems. Dynamic Games and Applications, 9(4):1168–1187.
Makkapati, V. R. and Tsiotras, P. (2020). Apollonius allocation algorithm for heterogeneous pursuers to capture multiple evaders. CoRR, abs/2006.10253.
Notomista, G., Mayya, S., Hutchinson, S., and Egerstedt, M. (2019). An optimal task allocation strategy for heterogeneous multi-robot systems. In 2019 18th European Control Conference (ECC), pages 2071–2076.
Pan, S., Huang, H., Ding, J., Zhang, W., Tomlin, C. J., et al. (2012). Pursuit, evasion and defense in the plane. In 2012 American Control Conference (ACC), pages 4167–4173. IEEE.
Parsons, T. D. (1978). Pursuit-evasion in a graph. In Theory and applications of graphs, pages 426–441. Springer.
Pferschy, U. (1997). Solution methods and computational investigations for the linear bottleneck assignment problem. Computing, 59(3):237–258.
Ramachandran, R. K., Pierpaoli, P., Egerstedt, M., and Sukhatme, G. (2020). Resilient monitoring in heterogeneous multi-robot systems through network reconfiguration. IEEE Transactions on Robotics. Submitted to.
Russell, S. and Norvig, P. (2009). Artificial Intelligence: A Modern Approach. Prentice Hall Press, Upper Saddle River, NJ, USA, 3rd edition.
Tekdas, O., Yang, W., and Isler, V. (2010). Robotic routers: Algorithms and implementation. The International Journal of Robotics Research, 29(1):110–126.
Varadharajan, V., Adams, B., and Beltrame, G. (2019). Failure-tolerant connectivity maintenance for robot swarms. ArXiv, abs/1905.04771.
Vieira, M. A. M., Govindan, R., and Sukhatme, G. S. (2009). Scalable and practical pursuit-evasion with networked robots. Intelligent Service Robotics, 2(4):247.
Yamaguchi, H. (1999). A Cooperative Hunting Behavior by Mobile-Robot Troops. The International Journal of Robotics Research, 18(9):931–940.
Yan, F. and Jiang, Y. (2017). Pursuing a faster evader based on an agent team with unstable speeds. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’17, page 1766–1768, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
Zhang, Z., Lee, J., Smereka, J. M., Sung, Y., Zhou, L., and Tokekar, P. (2019). Tree search techniques for minimizing detectability and maximizing visibility. In 2019 International Conference on Robotics and Automation (ICRA), pages 8791–8797.
Bopardikar, S. D., Bullo, F., and Hespanha, J. P. (2008). On discrete-time pursuit-evasion games with sensing limitations. IEEE Transactions on Robotics, 24(6):1429–1439.
Chung, T. H., Hollinger, G. A., and Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous robots, 31(4):299.
Huang, H., Zhang, W., Ding, J., Stipanović, D. M., and Tomlin, C. J. (2011). Guaranteed decentralized pursuit-evasion in the plane with multiple pursuers. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pages 4835–4840.
Isaacs, R. (1999). Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover books on mathematics. Dover Publications.
Krishnamoorthy, K., Darbha, S., Khargonekar, P. P., Casbeer, D., Chandler, P., and Pachter, M. (2013). Optimal minimax pursuit evasion on a manhattan grid. In 2013 American Control Conference, pages 3421–3428.
Makkapati, V. R. and Tsiotras, P. (2019). Optimal evading strategies and task allocation in multi-player pursuit–evasion problems. Dynamic Games and Applications, 9(4):1168–1187.
Makkapati, V. R. and Tsiotras, P. (2020). Apollonius allocation algorithm for heterogeneous pursuers to capture multiple evaders. CoRR, abs/2006.10253.
Notomista, G., Mayya, S., Hutchinson, S., and Egerstedt, M. (2019). An optimal task allocation strategy for heterogeneous multi-robot systems. In 2019 18th European Control Conference (ECC), pages 2071–2076.
Pan, S., Huang, H., Ding, J., Zhang, W., Tomlin, C. J., et al. (2012). Pursuit, evasion and defense in the plane. In 2012 American Control Conference (ACC), pages 4167–4173. IEEE.
Parsons, T. D. (1978). Pursuit-evasion in a graph. In Theory and applications of graphs, pages 426–441. Springer.
Pferschy, U. (1997). Solution methods and computational investigations for the linear bottleneck assignment problem. Computing, 59(3):237–258.
Ramachandran, R. K., Pierpaoli, P., Egerstedt, M., and Sukhatme, G. (2020). Resilient monitoring in heterogeneous multi-robot systems through network reconfiguration. IEEE Transactions on Robotics. Submitted to.
Russell, S. and Norvig, P. (2009). Artificial Intelligence: A Modern Approach. Prentice Hall Press, Upper Saddle River, NJ, USA, 3rd edition.
Tekdas, O., Yang, W., and Isler, V. (2010). Robotic routers: Algorithms and implementation. The International Journal of Robotics Research, 29(1):110–126.
Varadharajan, V., Adams, B., and Beltrame, G. (2019). Failure-tolerant connectivity maintenance for robot swarms. ArXiv, abs/1905.04771.
Vieira, M. A. M., Govindan, R., and Sukhatme, G. S. (2009). Scalable and practical pursuit-evasion with networked robots. Intelligent Service Robotics, 2(4):247.
Yamaguchi, H. (1999). A Cooperative Hunting Behavior by Mobile-Robot Troops. The International Journal of Robotics Research, 18(9):931–940.
Yan, F. and Jiang, Y. (2017). Pursuing a faster evader based on an agent team with unstable speeds. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’17, page 1766–1768, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
Zhang, Z., Lee, J., Smereka, J. M., Sung, Y., Zhou, L., and Tokekar, P. (2019). Tree search techniques for minimizing detectability and maximizing visibility. In 2019 International Conference on Robotics and Automation (ICRA), pages 8791–8797.
Publicado
13/11/2024
Como Citar
SANTOS, Renato Fernando dos; VIEIRA, Marcos Augusto Menezes.
Parallel Multi-speed Pursuit-Evasion Game Algorithms. In: CONCURSO DE TESES E DISSERTAÇÕES EM ROBÓTICA - CTDR (DOUTORADO) - SIMPÓSIO BRASILEIRO DE ROBÓTICA E SIMPÓSIO LATINO-AMERICANO DE ROBÓTICA (SBR/LARS), 16. , 2024, Goiânia/GO.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 37-48.
DOI: https://doi.org/10.5753/sbrlars_estendido.2024.244560.
