000061099 001__ 61099 000061099 005__ 20170510132216.0 000061099 037__ $$aTAZ-TFG-2016-4398 000061099 041__ $$aspa 000061099 1001_ $$aOroz Joven, Javier 000061099 24200 $$aDesign and implementation of a method to avoid collisions in multi-robot systems 000061099 24500 $$aDiseño e implementación de un método para evitar colisiones en un sistema multi-robot 000061099 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2016 000061099 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000061099 520__ $$aEste trabajo fin de grado se centra en el estudio del comportamiento y modelado de un sistema compuesto por varios robots que tienen que seguir cada uno una trayectoria de un conjunto de trayectorias posibles calculadas previamente utilizando algoritmos de planificación (por ejemplo utilizando descomposición en celdas (cell decomposition en inglés). En este trabajo no se va a ahondar en los métodos de cálculo de estas trayectorias sino en la implementación de un método para evitar los problemas inherentes en los sistemas multi-robot: las colisiones entre los distintos robots y los bloqueos del sistema que hace que algunos robots no acaben las trayectorias que han empezado. Partiendo de un conjunto de trayectorias prefijadas para cada robot, se modelará el sistema mediante el uso de las Redes de Petri, que no es más que una representación matemática con una representación gráfica de un sistema de eventos discretos. En concreto se va a usar un subconjunto de este tipo de redes, las llamadas redes S4PR. El entorno en el cual se mueven los robots se considera particionado en regiones y cada región del mapa se modela como un lugar en la red de Petri. Para evitar colisiones, se establecen regiones con capacidad finita (lugares de recurso), es decir, no pueden pasar por ellas más de un robot al mismo tiempo, de modo que si un segundo robot quiere pasar por esa misma región deberá esperar. Así que habrá que añadir lugares de espera, pero estos lugares de espera pueden conducir a bloqueos en la red, ocasionando que los robots no lleguen a su destino. Estos bloqueos se pueden caracterizar en este tipo de red de Petri utilizando algunos elementos estructurales de la red que se llaman sifones o cerrojos. Controlando que estos elementos no se vacíen, la red de Petri no se bloquea. Por tanto el objetivo principal y más laborioso de este trabajo es la implementación de un algoritmo para el cálculo de sifones en Redes de Petri S4PR, para así hallar los posibles estados de bloqueo. Existen otros métodos en la actualidad para su cálculo, pero no son tan potentes como el algoritmo que se va a desarrollar, en términos de tiempo de cálculo y necesidades de memoria. Una vez hallados los sifones se añadirán lugares monitor que evitarán que se vacíen y que se produzcan bloqueos. De este modo los robots podrán alcanzar su destino sin colisionar con los obstáculos del mapa, sin colisionar con otros robots y sin que se produzcan bloqueos que no los permitan seguir con su trayectoria. Por último, mencionar que este método de evitación de bloqueos que se va a desarrollar tiene muchas más aplicaciones. Cualquier sistema modelado con una red de Petri de la clase S4PR podría utilizar esta técnica aquí presentada. En la literatura hay ejemplos de sistemas flexibles de fabricación, sistemas de salud o sistemas de transporte modelados con redes de Petri pertenecientes a esta clase. 000061099 521__ $$aGraduado en Ingeniería de Tecnologías Industriales 000061099 540__ $$aDerechos regulados por licencia Creative Commons 000061099 700__ $$aMahulea, Cristian$$edir. 000061099 7102_ $$aUniversidad de Zaragoza$$bInformática e Ingeniería de Sistemas$$cIngeniería de Sistemas y Automática 000061099 8560_ $$f555449@celes.unizar.es 000061099 8564_ $$s4194728$$uhttps://zaguan.unizar.es/record/61099/files/TAZ-TFG-2016-4398.pdf$$yMemoria (spa) 000061099 909CO $$ooai:zaguan.unizar.es:61099$$pdriver$$ptrabajos-fin-grado 000061099 950__ $$a 000061099 951__ $$adeposita:2017-05-10 000061099 980__ $$aTAZ$$bTFG$$cEINA