Planificación de trayectorias en sistemas multirobot utilizando redes de Petri. Resultados y problemas abiertos

Autores/as

DOI:

https://doi.org/10.4995/riai.2020.13785

Palabras clave:

Planificación de trayectorias, sistemas multirobot, sistemas de eventos discretos, redes de Petri

Resumen

Este trabajo presenta una estrategia de planificacón de trayectorias en equipos de robots moviles basada en el uso de modelos definidos con redes de Petri. Estos tipos de modelos son muy útiles para especificaciones de alto nivel ya que, en este caso, los métodos clásicos de planificación (funciones potenciales, algoritmos RRT, RRT*) no se pueden utilizar, siendo difícil determinar a priori la secuencia de configuraciones para cada robot. Este trabajo presenta la definición formal de la Red de Petri de Movimiento de Robots que se obtiene a partir de una partición del entorno en celdas. Utilizando la estructura de la red de Petri, en caso de especificaciones definidas como fórmulas Booleanas o fórmulas en lógica temporal lineal (LTL), se presentan diferentes problemas de optimización que se pueden utilizar para obtener trayectorias para los robots. La principal ventaja de los modelos basados en redes de Petri es su escalabilidad con respecto al número de robots. Ello permite resolver con eficiencia problemas de planificación de equipos con un número grande de robots. En la segunda parte del trabajo, se presentan algunas extensiones y resultados nuevos para la planificación distribuida en entornos desconocidos y con comunicaciones parciales entre los robots.

Descargas

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

Biografía del autor/a

C. Mahulea, Universidad de Zaragoza

Cristian Mahuleais an Associate Professor (Profesor Titular de Universidad) at theUniversity of Zaragoza(Spain) with theDepartment of Computer Science and Systems Engineering.

He received the Laurea and M.S. degrees in control engineering from the"Gheorghe Asachi" Technical University of Iasi(Romania), in 2001 and 2002, respectively, and Ph.D. degree in systems engineering from the University of Zaragoza (Spain) in 2007. He joined the University of Zaragoza in 2008 as assistant professor, becoming associate professor in 2017. He was visiting professor at theUniversity of Cagliari(Italy) with theDepartment of Electrical and Electronic Engineeringduring five months in 2008 and 2010.

His research interests include discrete event systems, hybrid systems, automated manufacturing, Petri nets, mobile robotics and healthcare systems. He co-authored, with Mihaela Matcovschi and Octavian Pastravanu the bookApplications of Petri Nets in Studying Discrete Event Systems, Iasi, Romania in 2002 and co-authored with Marius Kloetzer and Ramon Gonzalez the bookPath Planning of Cooperative Mobile Robots Using Discrete Event Models, Wiley-IEEE Press, January 2020. He participated and was the main developer of one MATLAB toolbox calledPetri Net Toolboxfor the simulation, analysis and synthesis of discrete-event systems modeled with discrete Petri nets and one Matlab toolbox calledRMToolfor path planning and motion control of mobile robots.

He has been a Visiting Researcher at theUniversity of Sheffield(U.K.),University of Cagliari(Italy),Boston University(USA) andENS Paris-Saclay(France).

He is a Senior Member of IEEE.

R. González, Robonity

Ramon Gonzalez is an authority on robotics and engineering whose skills have been demonstrated in some of the most important engineering centers in the world including a 3-year research position atMIT. Ramon,Gold Medal of Andalucia 2017(first in the history in robotics), is the founder and CEO of the worldwide tech startuprobonity. He holds a PhD in robotics and an engineering degree in computer science. Dr. Gonzalez's primary research interests are in the areas of design, sensing, motion planning, and control of unmanned vehicles and mobile robots in outdoor terrain, including artificial intelligence, computer vision, and geostatistics. Ramon has recently participated in research programs for agencies including NASA, NATO, the US Army, and the Canadian Space Agency, among others. He has been finalist of the NATO Innovation Challenge. He currently serves on the editorial board of theJournal of Terramechanics.

E. Montijano, Universidad de Zaragoza

Desde que era estudiante universitario he enfocado mi carrera profesional al ámbito de la investigación y la docencia universitaria. Antes de empezar los estudios de doctorado ya colaboré en tareas de investigación con el centro internacional de investigación CIMNE en la Universidad Politécnica de Cataluña y con dos departamentos de la Universidad de Zaragoza. Al finalizar mis estudios de Ingeniería Informática, obtuve una beca FPU para realizar la tesis doctoral en el campo de la robótica. Durante el disfrute de dicha beca realicé 3 estancias de investigación en centros internacionales (University of California San Diego, KTH en Estocolmo y University of California Berkeley). Defendí la tesis en 2012 en la Universidad de Zaragoza, obteniendo el Premio Extraordinario de Doctorado 2012-2013.

Desde enero de 2012 hasta septiembre de 2016 fui profesor en el Centro Universitario de la Defensa en Zaragoza, momento en el que me incorporé a mi puesto actual de Profesor Ayudante Doctor en el Departamento de Informática e Ingeniería de Sistemas de la Universidad de Zaragoza. Dispongo de las acreditaciones de Profesor Contratado Doctor desde mayo de 2014 y de Profesor Titular de Universidad desde octubre de 2016.

En relación con la investigación, soy autor de un libro internacional publicado por la editorial Springer y 20 artículos en revistas internacionales indexadas en el JCR, todas ellas situadas en el primer tercil de algún área (18Q1 y 2Q2). También soy autor de 28 artículos presentados en conferencias nacionales e internacionales, incluyendo dos en Robotics: Science and Systems (2010 y 2018), conferencia con tasa de aceptación inferior al 20%.

Tengo una trayectoria continuada de participación en proyectos de investigación competitivos, siendo IP en varios, incluyendo uno nacional (DPI2015-69376) y coordinador de un proyecto internacional (ONRG-NICOP N62909-19-1-2027) en colaboración con TU Delft, Stanford y MIT. He colaborado con investigadores de diferentes centros de gran prestigio internacional, con los que tengo publicaciones en revistas y conferencias internacionales de primer nivel. Tengo dos estancias post-doctorales en Boston University, la segunda de ellas obteniendo una beca José Castillejo competitiva del Ministerio. También desarrollo mi investigación en el marco de colaboración con empresas, participando en proyectos de transferencia, siendo inventor de dos patentes y habiendo recibido 3 premios de innovación en la empresa.

Tengo 8 años completos de experiencia docente, impartiendo docencia en todos los niveles. He sido director de 1 tesis doctoral (3 actualmente en desarrollo) y 20 proyectos final de grado y máster. He participado en varios cursos y proyectos de innovación docente multi-disciplinares, siendo el coordinador de dos de ellos.

En tareas de gestión, soy miembro del Editorial Board de IEEE Control Systems Society desde 2015, en calidad de editor asociado de las principales conferencias de esta sociedad (ACC y CDC). He formado parte del comité organizador de la conferencia RSS en el 2010 y he sido tesorero en IEEE ETFA 2019. He sido organizador principal de dos workshops de investigación internacionales y miembro del comité de programa de otros 3.

Soy revisor de forma regular en revistas internacionales (TRO, TAC, TSP, Automatica, CSM, IJRR, etc.) y conferencias internacionales (ICRA, IROS, CDC, ACC).

M. Silva, Universidad de Zaragoza

Manuel Silva (https://webdiis.unizar.es/GISED/?q=member/manuel-silva), Catedrático de Ingeniería de Sistemas y Automática en la Universidad de Zaragoza, es coautor de más de trescientas publicaciones, una proporción significativa dedicada a los sistemas de eventos discretos. Fue Decano del Centro Politécnico Superior, Universidad de Zaragoza ('86 –'92), y Presidente del Consejo de Investigación Aragonés y del Comité de Investigación e Innovación de la Comisión de Trabajo de los Pirineos de Francia y España (93-95). Es miembro o ha colaborado con los consejos editoriales de varias revistas (IEEE Transactions on Robotics and Automation, European Journal of Control, Discrete Event Dynamic Systems, etc.). El Prof. Silva es miembro asesor de las Transacciones de IEICE sobre Fundamentos de Electrónica, Comunicaciones y Ciencias de la Computación y del Journal of Discrete Event Systems. Participó en los Comités del Programa Internacional de más de 200 conferencias. Manuel Silva ha sido coeditor junto con Carla Seatzu y J.H. van Schuppen del libro "Control de sistemas de eventos discretos. Perspectivas de autómatas y redes de Petri", publicado por Springer en 2012. Distinguido con una medalla de Lille, por la Asociación de Ingenieros de Telecomunicación de Aragón, Premio Comité Español de Automática (CEA-IFAC) es Doctor Honoris Causa por la Université de Reims-Champagne-Ardennes. Es miembro de la Real Academia de Ingeniería de España y miembro de la Real Academia de Ciencias de Zaragoza. Ha (co)dirigido veinte tesis doctorales, de las cuales dos fueron presentadas en universidades extranjeras (RPI, Troy, Nueva York, EE. UU. Y Friedrich-Alexander Universität Erlangen-Nürnberg). Dos de las tesis doctorales de Zaragoza fueron defendidas en la Facultad de Ciencias, seis obtuvieron el Premio Extraordinario de Doctorado de la Universidad de Zaragoza y una fue finalista. Además, otra tesis doctoral ha sido distinguida con el "Reconocimiento a la mejor tesis doctoral en Modelado, Simulación y Optimización" por el Grupo temático correspondiente del Comité Español de Automática (CEA). Manuel Silva se involucrará en tareas de los objetivos (O1) y (O3) en particular en tareas de modelado con redes de Petri de las especificaciones con incertidumbre.

Citas

Baier, C., Katoen, J.P., 2008. Principles of model checking. MIT Press.

Belta, C., Bicchi, A., Egerstedt, M., Frazzoli, E., Klavins, E., Pappas, G.-J., 2007. Symbolic planning and control of robot motion. IEEE Robotics and Automation Magazine 14 (1), 61-71. https://doi.org/10.1109/MRA.2007.339624

Belta, C., Habets, L., 2006. Controlling a class of nonlinear systems on rectangles. IEEE Transactions on Automatic Control 51 (11), 1749-1759. https://doi.org/10.1109/TAC.2006.884957

Brown, F., 2012. Boolean Reasoning: The Logic of Boolean Equations, 2nd Edition. Dover Publications.

Castellanos, J. G., Cervantes, M. V., Santana, J. S., Martínez, S. R., 2014. Seguimiento de trayectorias de un robot movil (3,0) mediante control acotado. Rev. Iberoamericana de Automatica e Informática industrial 11 (4), 426-434. https://doi.org/10.1016/j.riai.2014.09.005

Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., Thrun, S., 2005. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Boston.

Clarke, E.-M.-M., Peled, D., Grumberg, O., 1999. Model checking. MIT Press.

DeCastro, J., Ehlers, R., Runggers, M., Balkan, A., Kress-Gazit, H., 2016. Automated generation of dynamics-based runtime certificates for high-level control. Discrete Event Dynamic Systems 27 (2), 371-405. https://doi.org/10.1007/s10626-016-0232-7

Ding, X., 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

Duret-Lutz, A., Lewkowicz, A., Fauchille, A., Michaud, T., Renault, E., Xu, L., 2016. Spot 2.0 - a framework for ltl and ω-automata manipulation. In: Proc. of ATVA'16. pp. 122-129. https://doi.org/10.1007/978-3-319-46520-3_8

Fainekos, G. E., Girard, A., Kress-Gazit, H., Pappas, G. J., 2009. Temporal logic motion planning for dynamic robots. Automatica 45 (2), 343-352. https://doi.org/10.1016/j.automatica.2008.08.008

Garrido, S., Moreno, L., Gomez, J.-V., Lima, P.-U., 2013. International Journal ' of Advanced Robotic Systems 10 (1), 64. https://doi.org/10.5772/53999

Gastin, P., Oddoux, D., 2001. Fast ltl to buchi automata translation. In: Proc. of the 13th Conference on Computer Aided Verification (CAV). pp. 53-65. https://doi.org/10.1007/3-540-44585-4_6

Gonzalez, R., Mahulea, C., Kloetzer, M., 2015. A Matlab-Based Interactive Simulator for Mobile Robotics. In: IEEE CASE'2015: Int. Conf. on Autom. Science and Engineering. Gothenburg, Sweden, pp. 310-315. https://doi.org/10.1109/CoASE.2015.7294097

Gonzalez, R., Rodriguez, F., Guzman, J. L., 2014. Autonomous Tracked Robots in Planar Off-Road Conditions. Modelling, Localization and Motion Control. Series: Studies in Systems, Decision and Control. Springer. https://doi.org/10.1007/978-3-319-06038-5

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

Habets, L. C. G. J. M., Collins, P. J., van Schuppen, J. H., 2006. Reachability and control synthesis for piecewise-affine hybrid systems on simplices. IEEE Transactions on Automatic Control 51, 938-948. https://doi.org/10.1109/TAC.2006.876952

Julian, B.-J., Angermann, M., Schwager, M., Rus, D., 2012. Distributed robotic sensor networks: An information-theoretic approach. The International Journal of Robotics Research 31 (10), 1134-1154. https://doi.org/10.1177/0278364912452675

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

Kloetzer, M., Mahulea, C., 2014. An assembly problem with mobile robots. In: ETFA'2014: IEEE Emerging Technology and Factory Automation. pp. 1-7. https://doi.org/10.1109/ETFA.2014.7005116

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., 2020. Path planning for robotic teams based on LTL specifications and Petri net models. Discrete Event Dynamic Systems: Theory and Applications 30 (1), 55-79. https://doi.org/10.1007/s10626-019-00300-1

Lacerda, B., Lima, P. U., 2019. Petri net based multi-robot task coordination from temporal logic specifications. Robotics and Autonomous Systems 122, 343-352. https://doi.org/10.1016/j.robot.2019.103289

LaValle, S. M., 2006. Planning Algorithms. Cambridge, available at http://planning.cs.uiuc.edu. https://doi.org/10.1017/CBO9780511546877

Leahy, K., Cristofalo, E., Vasile, C.-I., Jones, A., Montijano, E., Schwager, M., Belta, C., 2019. Control in belief space with temporal logic specifications using vision-based localization. The International Journal of Robotics Research 38 (6), 702-722. https://doi.org/10.1177/0278364919846340

Mahulea, C., Kloetzer, M., 2018. Robot Planning based on Boolean Specifications using Petri Net Models. IEEE Trans. on Automatic Control 63 (7), 2218-2225. https://doi.org/10.1109/TAC.2017.2760249

Mahulea, C., Kloetzer, M., Gonzalez, R., 2020a. Path Planning of Cooperative ' Mobile Robots Using Discrete Event Models. IEEE Wiley. https://doi.org/10.1002/9781119486305

Mahulea, C., Kloetzer, M., Lesage, J.-J., 2020b. Multi-robot path planning with boolean specifications and collision avoidance. In: WODES'2020: 15th Workshop on Discrete Event Systems.

Mahulea, C., Montijano, E., Kloetzer, M., 2020c. Distributed Multirobot Path Planning in Unknown Maps Using Petri Net Models. IFACPapersOnLine21th IFAC World Congress.

Mesbahi, M., Egerstedt, M., 2010. Graph theoretic methods in multiagent networks. Princeton University Press. https://doi.org/10.1515/9781400835355

Montijano, E., Montijano, J.-I., Sagues, C., Feb 2013. Chebyshev polynomials in distributed consensus applications. IEEE Transactions on Signal Processing 61 (3), 693-706. https://doi.org/10.1109/TSP.2012.2226173

Montijano, E., Sagües, C., 2015. Distributed consensus with visual perception ' in multi-robot systems. Springer. https://doi.org/10.1007/978-3-319-15699-6

Parrilla, L., Mahulea, C., Kloetzer, M., 2017. RMTool: Recent Enhancements. IFAC-PapersOnLine 50 (1), 5824 - 5830, 20th IFAC World Congress. https://doi.org/10.1016/j.ifacol.2017.08.539

Schillinger, P., Burger, M., Dimarogonas, D., 2018. Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. The International Journal of Robotics Research 37 (7), 818-838. https://doi.org/10.1177/0278364918774135

Siegwart, R., Nourbakhsh, I., 2004. Introduction to Autonomous Mobile Robots, First Edition. A Bradford book. The MIT Press, USA. Silva, M., 1985. Las Redes de Petri : en la Automatica y la Informática; 1a ed. Editorial AC Madrid.

Silva, M., Colom, J.-M., 1988. On the Computation of Structural Synchronic Invariants in P/T Nets. Advances in Petri Nets'87 340, 386-417. https://doi.org/10.1007/3-540-50580-6_39

Silva, M., Teruel, E., Colom, J.-M., 1998. Linear Algebraic and Linear Programming Techniques for the Analysis of P/T Net Systems. Lecture on Petri Nets I: Basic Models 1491, 309-373. https://doi.org/10.1007/3-540-65306-6_19

Tumova, J., Dimarogonas, D., 2016. Multi-agent planning under local LTL specifications and event-based synchronization. Automatica 70, 239-248. https://doi.org/10.1016/j.automatica.2016.04.006

Ulusoy, A., Smith, S., Ding, X., Belta, C., 2012. Robust multi-robot optimal path planning with temporal logic constraints. In: ICRA 2012: IEEE Conference on Robotics and Automation. pp. 4693-4698. https://doi.org/10.1109/ICRA.2012.6224792

Wolper, P., Vardi, M., Sistla, A., 1983. Reasoning about infinite computation paths. In: Proc. of the 24th IEEE Symposium on Foundations of Computer Science. pp. 185-194. https://doi.org/10.1109/SFCS.1983.51

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

Descargas

Publicado

23-12-2020

Cómo citar

Mahulea, C., González, R., Montijano, E. y Silva, M. (2020) «Planificación de trayectorias en sistemas multirobot utilizando redes de Petri. Resultados y problemas abiertos», Revista Iberoamericana de Automática e Informática industrial, 18(1), pp. 19–31. doi: 10.4995/riai.2020.13785.

Número

Sección

Tutoriales