Diseño e implementación de un método para evitar colisiones en un sistema multi-robot

Oroz Joven, Javier
Mahulea, Cristian (dir.)

Universidad de Zaragoza, EINA, 2016
Informática e Ingeniería de Sistemas department, Ingeniería de Sistemas y Automática area

Graduado en Ingeniería de Tecnologías Industriales

Abstract: Este 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.

Tipo de Trabajo Académico: Trabajo Fin de Grado