Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2755| Diseño de algoritmos para el problema de coordinación de movimiento de múltiples robots a lo largo de trayectorias pre-especificadas Design of algorithms for the coordination of multiple moving robots along pre-specified trajectories | |
| Julio Antonio Juárez Jiménez | |
| Carlos Alberto Brizuela Rodriguez | |
| Acceso Abierto | |
| Atribución | |
| Coordinacion de rutas de robots, Job Shop Scheduling, Diagramas de coordinación, NP-difìcil. | |
| El problema de la coordinación de rutas de robots (RPC) y el problema conocido como Job Shop Scheduling (JSP) se han estudiado ampliamente de manera independiente a lo largo de los años. A pesar de que la similitud entre estos dos problemas se ha señalado (O’Donnell y Lozano-Pérez, 1989; Peng y Akella, 2005), hasta el momento se desconoce de algún trabajo que enuncie de manera formal la estrecha similitud entre éstos. La importancia de la similitud entre estos problemas radica en que el problema JSP pertenece a la clase de problemas conocidos como NP-difícil, por lo que hasta hoy en día se considera intratable bajo el modelo de cómputo convencional.En el presente trabajo, se explora formalmente la semejanza entre ambos problemas y se propone una técnica de agrupamiento de robots basada en diagramas de coordinación n-dimensionales (originalmente propuestos para el RPC (Siméon et al., 2002)) para encontrar soluciones para casos del JSP. Se proponen tres algoritmos determinísticos de calendarización implementando la técnica de agrupamiento de robots: el GANTT, el GANTT-T y el GANTT-T+. Los tres algoritmos realizan un procedimiento iterativo de agrupamiento y calendarización de un número constante (k) de robots, con diferencias particulares entre cada algoritmo. El GANTT busca maximizar el recorrido paralelo de segmentos de ruta que no pertenezcan a una misma región, en un mismo intervalo de tiempo. El GANTT-T implementa un adelgazador que permite calcular el tiempo de inicio de recorrido de un segmento de ruta; que inicie (el recorrido) tan pronto como el segmento que lo precede, en su misma ruta, haya sido recorrido y la región a recorrer se haya liberado. El GANTT-T+ implementa un adelgazador mejorado y calcula el mínimo tiempo de inicio de un segmento de ruta; permite iniciar el recorrido tan pronto como sea posible, respetando la restricción de precedencia de los segmentos de ruta.Los resultados experimentales muestran que: i) El algoritmo GANTT-T+ es superior (calidad de solución) a los algoritmos GANTT y GANTT-T. ii) El algoritmo GANTT-T+ muestra un error relativo (ER) promedio del 5.48% con k = 3 y del 6.84% con k = 2, sobre 82 casos de prueba conocidos del JSP. iii) La evidencia teórica y experimental muestran que el algoritmo GANTT-T+ se comporta como un algoritmo exacto de tiempo exponencial, cuando k = n. The Robot Path Coordination problem (RPC) and the Job Shop Scheduling problem (JSP) have been widely studied over the years. Despite the similarity between these two problems has been pointed out (O’Donnell y Lozano-P´erez, 1989; Peng y Akella, 2005), we do not know of any work that formally states the close relation between them. The importance of this similarity lies on the computational complexity of the JSP. The JSP belongs to a set of problems known as NP −hard, which are considered to be intractable under the conventional computing model.In the present work, the formal similitude between the RPC and the JSP is explored. Also, a robot grouping technique, based on n-dimensional coordination diagrams (originally proposed for the RPC (Sim´eon et al., 2002)) to find solutions for JSP instances, is proposed. Three deterministic scheduling algorithms implementing the grouping technique are proposed: GANTT, GANTT-T and GANTT-T+. The three algorithms perform an iterative procedure of grouping and scheduling of a constant number (k) of robots, with specific differences between each pair of algorithms. GANTT seeks to maximize the parallel execution of path segments that do not belong to the same region, in the same time interval. GANTT-T implements a trimming procedure which computes the starting execution time of apath segment; to start as soon as the segment which precedes it, in its same path, has been executed and the region to be executed has been freed. GANTT-T+ implements an improved trimming procedure which computes the minimum starting execution time of a path segment; to start as soon as possible, as long as the segment precedence constraints are met.The experimental results, show that: i) The GANTT-T+ algorithm is superior (in quality of solution) with respect to the GANTT and GANTT-T algorithms. ii) The algorithm GANTTT+ shows an average relative error of 5.48% with k = 3 and of 6.84% with k = 2, over 82 known instances of the JSP. iii) Theoretical and experimental evidence suggests that, when k = n, the GANTT-T+ algorithm behaves as an exponential time exact algorithm. | |
| CICESE | |
| 2015 | |
| Tesis de maestría | |
| Español | |
| Juárez Jiménez, J.A.2015.Diseño de algoritmos para el problema de coordinación de movimiento de múltiples robots a lo largo de trayectorias pre-especificadas.Tesis de Maestría en Ciencias.Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.94 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 240521.pdf | 1.06 MB | Adobe PDF | Visualizar/Abrir |