Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes

Methodology for the Synthesis of Automata in the Planning of Movements for Autonomous Systems with Multiple Agents

Autores/as

Palabras clave:

Büchi automata, formal languages, linear temporal logic (LTL), motion planning, Petri networks (en).

Palabras clave:

autómatas de Büchi, lenguajes formales, lógica temporal lineal (LTL), , planificación de movimientos, redes de Petri, sistemas cooperativos de múltiples agentes (es).

Descargas

Resumen (es)

Objetivo: Presentar una metodología para la planificación de movimientos de sistemas autónomos con múltiples agentes.

 

Metodología: Se define y parametriza el comportamiento físico de un equipo de sistemas de navegación autónoma, luego se describe e implementa un algoritmo de síntesis de políticas de control que interpreta estas descripciones convertidas a fórmulas LTL y se genera un modelo que permite hacer abstracciones automáticas. A partir de configuraciones genéricas de solución, se deriva en el caso de múltiples robots con una única tarea en un entorno con obstáculos fijos. La metodología se valida en diferentes escenarios y se analizan los resultados.

 

Resultados: La metodología propuesta para planificación de movimientos en sistemas con múltiples agentes, combina dos técnicas del estado del arte, permitiendo mitigar la explosión combinacional de estados presente en los enfoques tradicionales.

 

Conclusiones: La metodología que se presenta resuelve el problema de síntesis de autómatas para el control de alto nivel, con cambio de tareas durante la ejecución. Bajo ciertos criterios, se mitiga el problema de explosión combinacional de estados asociado a estos sistemas. La solución es óptima respecto al número de transiciones seguidas por los miembros del equipo.

 

Financiamiento: Universidad Tecnológica de Pereira

 

Resumen (en)

Objective: To develop a methodology for motion planning in autonomous systems with multiple agents.

 

Methodology: In the first place, a parametric definition of the behavior of a team of autonomous navigation systems is established. Then, the control policies are interpreted by a synthesis algorithm by converting the task description into LTL formulas and therefore generating a model that allows for automatic abstractions.  Starting from configurations of generic solutions, we derive the case of multiple robots with a unique task, assuming an environment with stationary obstacles. The methodology is validated in all the aforementioned scenarios, and results are then analyzed and discussed.

 

Results: Our proposed methodology, for motion planning in autonomous systems with multiple agents, combines two state-of-the-art techniques, mitigating the combinatorial explosion of states in traditional approaches.

 

Conclusions: Our proposed methodology solves the automaton synthesis for multiple agents with high-level control, and even with task changes during the execution. The problem of combinatorial explosion of states is mitigated. The solution is optimized vis-a-vis the number of transactions performed by the team members.

 

Financing: Universidad Tecnológica de Pereira

 

Biografía del autor/a

Jorge Luis Martínez Valencia, Universidad Tecnológica de Pereira

Maestría en Ingeniería Eléctrica, ingeniero electrónico. Profesor de la Universidad Tecnológica de Pereira. Pereira, Colombia.

 

Mauricio Holguín Londoño, Universidad Tecnológica de Pereira

Doctorado en Ingeniería, Máster en Ingeniería Eléctrica, Ingeniería Eléctrica. Profesor de la Universidad Tecnológica de Pereira. Pereira, Colombia

carlos alberto ramirez vanegas, universidad tecnologica de pereira

 

Maestría en Ingeniería Eléctrica, ingeniero eléctrico. Profesor de la Universidad Tecnológica de Pereira. Pereira, Colombia.

Referencias

Aksaray, D., Jones, A., Kong, Z., Schwager, M., & Belta, C. (2016). Q-learning for robust satisfaction of signal temporal logic specifications. 2016 IEEE 55th Conference on Decision and Control (CDC), 6565-6570. https://doi.org/10.1109/ACC.2012.6315110

Aragues, R., Shi, G., Dimarogonas, D. V, Sagues, C., & Johansson, K. H. (2012). Distributed algebraic connectivity estimation for adaptive event-triggered consensus. American Control Conference (ACC), 2012, 32-37.

Brown, F. M. (2012). Boolean reasoning: the logic of Boolean equations. Springer Science & Business Media.

Chen, Y., Ding, X. C., Stefanescu, A., & Belta, C. (2012). Formal approach to the deployment of distributed robotic teams. IEEE Transactions on Robotics, 28(1), 158-171. https://doi.org/10.1109/TRO.2011.2163434

Choset, H. M. (2005). Principles of robot motion: theory, algorithms, and implementation. MIT press.

Clarke, E. M., Grumberg, O., & Peled, D. (1999). Model checking. MIT press.

Costelha, H., & Lima, P. (2012). Robot task plan representation by Petri nets: modelling, identification, analysis and execution. Autonomous Robots, 33(4), 337-360. https://doi.org/10.1007/s10514-012-9288-x

Ding, X. C., Kloetzer, M., Chen, Y., & Belta, C. (2011). Automatic deployment of robotic teams. IEEE Robotics & Automation Magazine, 18(3), 75-86. https://doi.org/10.1109/MRA.2011.942117

Ding, X. C., Smith, S. L., Belta, C., & Rus, D. (2014). Optimal Control of Markov Decision Processes With Linear Temporal Logic Constraints. IEEE Transactions on Automatic Control, 59(5), 1244-1257. https://doi.org/10.1109/TAC.2014.2298143

Emerson, E. A. (1990). Temporal and modal logic. In J. van Leeuwen (Ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) (pp. 995, 997-1072). Elsevier. https://doi.org/10.1016/B978-0-444-88074-1.50021-4

Franceschelli, M., Giua, A., & Pisano, A. (2014, June 4-6). Finite-time consensus on the median value by discontinuous control [Conference presentation]. American Control Conference (ACC), 2014, Portland, OR, USA. https://doi.org/10.1109/ACC.2014.6859201

Franceschelli, M., Rosa, D., Seatzu, C., & Bullo, F. (2013). Gossip algorithms for heterogeneous multi-vehicle routing problems. Nonlinear Analysis: Hybrid Systems, 10, 156-174. https://doi.org/10.1016/j.nahs.2013.03.001

Garrido, S., Moreno, L., Gómez, J. V, & Lima, P. U. (2013). General path planning methodology for leader-follower robot formations. International Journal of Advanced Robotic Systems, 10(1), 64. https://doi.org/10.5772/53999

Gastin, P., & Oddoux, D. (2001). Fast LTL to Büchi automata translation. In G. Berry, H. Comon, & A. Finkel (Eds.) Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science (vol. 2102, pp. 53-65). Springer. https://doi.org/10.1007/3-540-44585-4_6

Guo, M., & Dimarogonas, D. V. (2015a). Multi-agent plan reconfiguration under local LTL specifications. The International Journal of Robotics Research, 34(2), 218-235. https://doi.org/10.1177/0278364914546174

Guo, M., & Dimarogonas, D. V. (2015b, August 24-28). Bottom-up motion and task coordination for loosely-coupled multi-agent systems with dependent local tasks [Conference presentation]. 2015 IEEE International Conference on Automation Science and Engineering (CASE), Gothenburg, Sweden. https://doi.org/10.1109/CoASE.2015.7294103

Holzmann, G. (2003). Spin model checker, the: primer and reference manual. Addison-Wesley Professional.

Martínez-Valencia, J. L., Holguín-Londoño, M., & Escobar-Mejía, A. (2017, October 18-20). A methodology to evaluate combinatorial explosion using LTL in autonomous ground navigation applications [Conference presentation]. 2017 IEEE 3rd Colombian Conference on Automatic Control (CCAC), Cartagena, Colombia. https://doi.org/10.1109/CCAC.2017.8276430

Karaman, S., & Frazzoli, E. (2011). Linear temporal logic vehicle routing with applications to multi-UAV mission planning. International Journal of Robust and Nonlinear Control, 21(12), 1372-1395. https://doi.org/10.1002/rnc.1715

Karaman, S., & Frazzoli, E. (2009, December 15-18). Sampling-based motion planning with deterministic $μ$-calculus specifications [Conference presentation]. 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, Shanghai, China. https://doi.org/10.1109/CDC.2009.5400278

Kloetzer, M., & Mahulea, C. (2014). A Petri net based approach for multi-robot path planning. Discrete Event Dynamic Systems, 24(4), 417-445. https://doi.org/10.1007/s10626-013-0162-6

Kloetzer, M., & Mahulea, C. (2015). Ltl-based planning in environments with probabilistic observations. IEEE Transactions on Automation Science and Engineering, 12(4), 1407-1420. https://doi.org/10.1109/TASE.2015.2454299

Kloetzer, M., & Mahulea, C. (2016, May 30-June 1). Multi-robot path planning for syntactically co-safe LTL specifications [Conference presentation]. 13th International Workshop On Discrete Event Systems (WODES), Xi'an, China. https://doi.org/10.1109/WODES.2016.7497887

Kupferman, O., & Vardi, M. Y. (2001). Model checking of safety properties. Formal Methods in System Design, 19(3), 291-314. https://doi.org/10.1023/A:1011254632723

LaValle, S. M. (2006). Planning algorithms. Cambridge university press.

Ma, X., Jiao, Z., Wang, Z., & Panagou, D. (2016, June 7-10). Decentralized prioritized motion planning for multiple autonomous UAVs in 3D polygonal obstacle environments [Conference presentation]. 2016 International Conference on Unmanned Aircraft Systems (ICUAS), Arlington, VA, USA. https://doi.org/10.1109/ICUAS.2016.7502596

Mahulea, C., & Kloetzer, M. (2014, December 15-17). Planning mobile robots with Boolean-based specifications [Conference presentation]. 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), Los Angeles, CA, USA. https://doi.org/10.1109/CDC.2014.7040192

Martínez, J. L., Holguín, G. A., & Holguín, M. (2018, November 1-3). A Methodology for Movement Planning in Autonomous Systems with Multiple Agents [Conference presentation]. 2018 IEEE 2nd Colombian Conference on Robotics and Automation (CCRA), Barranquilla, Colombia. https://doi.org/10.1109/CCRA.2018.8588140

Piterman, N., Pnueli, A., & Sa’ar, Y. (2006, January 8-10). Synthesis of reactive (1) designs [Conference presentation]. International Workshop on Verification, Model Checking, and Abstract Interpretation, Charleston, SC, USA. https://doi.org/10.1007/11609773_24

Pnueli, A., & Rosner, R. (1989, January 11-13). On the synthesis of a reactive module [Conference presentation]. 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Austin, TX, USA. https://doi.org/10.1145/75277.75293

Saha, I., Ramaithitima, R., Kumar, V., Pappas, G. J., & Seshia, S. A. (2014, September 14-18). Automated composition of motion primitives for multi-robot systems from safe LTL specifications [Conference presentation]. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA. https://doi.org/10.1109/IROS.2014.6942758

Schillinger, P., Bürger, M., & Dimarogonas, D. (2016, November 6-9). Decomposition of Finite LTL Specifications for Efficient Multi-Agent Planning [Conference presentation]. 13th International Symposium on Distributed Autonomous Robotic Systems, London, UK.

Smaus, J.-G. (2007, May 23-26). On Boolean functions encodable as a single linear pseudo-Boolean constraint [Conference presentation]. International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Brussels, Belgium. https://doi.org/10.1007/978-3-540-72397-4_21

Tumova, J., & Dimarogonas, D. V. (2015, December 15-18). Decomposition of multi-agent planning under distributed motion and task LTL specifications [Conference presentation]. IEEE 54th Annual Conference on Decision and Control (CDC), Osaka, Japan. https://doi.org/10.1109/CDC.2015.7403396

Ulusoy, A., Smith, S. L., Ding, X. C., & Belta, C. (2012, May 12-14). Robust multi-robot optimal path planning with temporal logic constraints [Conference presentation]. IEEE International Conference on Robotics and Automation (ICRA), Saint Paul, MN, USA. https://doi.org/10.1109/ICRA.2012.6224792

van den Berg, J. P., & Overmars, M. H. (2005, August 2-6). Prioritized motion planning for multiple robots [Conference presentation]. 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada. https://doi.org/10.1109/IROS.2005.1545306

Wolper, P., Vardi, M. Y., & Sistla, A. P. (1983, November 7-9). Reasoning about infinite computation paths [Conference presentation]. 24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, USA. https://doi.org/10.1109/SFCS.1983.51

Wongpiromsarn, T., Topcu, U., & Murray, R. M. (2009, December 15-18). Receding horizon temporal logic planning for dynamical systems [Conference presentation]. 48th IEEE Conference on Decision and Control, 2009 Held Jointly with the 2009 28th Chinese Control Conference, Shanghai, China. https://doi.org/10.1109/CDC.2009.5399536

Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. Management Science, 17(11), 712-716. https://doi.org/10.1287/mnsc.17.11.712

Cómo citar

APA

Martínez Valencia, J. L. ., Holguín Londoño, M. ., & ramirez vanegas, carlos alberto. (2021). Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes. Tecnura, 25(70). https://doi.org/10.14483/22487638.17131

ACM

[1]
Martínez Valencia, J.L. , Holguín Londoño, M. y ramirez vanegas, carlos alberto 2021. Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes. Tecnura. 25, 70 (nov. 2021). DOI:https://doi.org/10.14483/22487638.17131.

ACS

(1)
Martínez Valencia, J. L. .; Holguín Londoño, M. .; ramirez vanegas, carlos alberto. Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes. Tecnura 2021, 25.

ABNT

MARTÍNEZ VALENCIA, J. L. .; HOLGUÍN LONDOÑO, M. .; RAMIREZ VANEGAS, carlos alberto. Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes. Tecnura, [S. l.], v. 25, n. 70, 2021. DOI: 10.14483/22487638.17131. Disponível em: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/17131. Acesso em: 20 ene. 2022.

Chicago

Martínez Valencia, Jorge Luis, Mauricio Holguín Londoño, y carlos alberto ramirez vanegas. 2021. «Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes». Tecnura 25 (70). https://doi.org/10.14483/22487638.17131.

Harvard

Martínez Valencia, J. L. ., Holguín Londoño, M. . y ramirez vanegas, carlos alberto (2021) «Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes», Tecnura, 25(70). doi: 10.14483/22487638.17131.

IEEE

[1]
J. L. . Martínez Valencia, M. . Holguín Londoño, y carlos alberto ramirez vanegas, «Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes», Tecnura, vol. 25, n.º 70, nov. 2021.

MLA

Martínez Valencia, J. L. ., M. . Holguín Londoño, y carlos alberto ramirez vanegas. «Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes». Tecnura, vol. 25, n.º 70, noviembre de 2021, doi:10.14483/22487638.17131.

Turabian

Martínez Valencia, Jorge Luis, Mauricio Holguín Londoño, y carlos alberto ramirez vanegas. «Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes». Tecnura 25, no. 70 (noviembre 30, 2021). Accedido enero 20, 2022. https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/17131.

Vancouver

1.
Martínez Valencia JL, Holguín Londoño M, ramirez vanegas carlos alberto. Metodología para la síntesis de autómatas en la planificación de movimientos en sistemas autónomos con múltiples agentes. Tecnura [Internet]. 30 de noviembre de 2021 [citado 20 de enero de 2022];25(70). Disponible en: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/17131

Descargar cita

Visitas

31

Dimensions


PlumX


Descargas

Los datos de descargas todavía no están disponibles.

Artículos más leídos del mismo autor/a