Comparacion de planificadores de caminos basados en muestropara un robot aereo equipado con brazo manipulador

Francisco Jose Marquez, Ivan Maza y Anıbal OlleroGrupo de Robotica, Vision y Control, Universidad de Sevilla

fran 2 14@hotmail.com,imaza@us.es,aollero@us.es

Resumen

Este trabajo es parte del proyecto europeo ARCASen el que uno de los objetivos es la construccion deinfraestructuras mediante equipos de robots aereosequipados con brazos manipuladores. Dentro de es-te contexto supone un gran reto la planificacionde caminos para un robot que se puede mover entres dimensiones provisto de un brazo robotico conmultiples grados de libertad. La dificultad del pro-blema de planificacion asociado escapa al alcan-ce de los metodos deterministas clasicos. Por esemotivo, este trabajo se centra en los algoritmos deplanificacion basados en muestreo. En particularse comparan los resultados de dichos planificado-res en el entorno industrial complejo considera-do en el proyecto. En primer lugar se evalua lamejora que se consigue mediante la inclusion defunciones de coste para el robot aereo sin el ma-nipulador. Finalmente se compara una baterıa deplanificadores basados en muestreo para el siste-ma completo compuesto por el robot aereo con elmanipulador.

Palabras clave: Planificacion de caminos, plani-ficadores basados en muestreo, robotica aerea.

1. INTRODUCCION Y ESTADODEL ARTE

El trabajo presentado en este artıculo es parte delproyecto europeo ARCAS financiado por la Comi-sion Europea. En este proyecto se han desarrolla-do los primeros robots manipuladores aereos (he-licopteros y multi-rotores) del mundo con brazosroboticos de 6 y 7 grados de libertad. Uno de losobjetivos del proyecto es la construccion de in-fraestructuras mediante equipos de robots aereosequipados con dichos brazos manipuladores. El in-teres practico de estos sistemas se encuentra ensituaciones en las que las tareas de manipulacionse deben llevar a cabo en lugares de difıcil accesopor medios convencionales (ver figura 1). Dentrode este contexto supone un gran reto la planifica-cion de caminos para un robot que se puede moveren tres dimensiones, provisto de un brazo roboticocon multiples grados de libertad.

Figura 1: Dos robots aereos equipados con bra-zos LWR del fabricante KUKA manipulando unabarra con destreza para su colocacion en una in-fraestructura danada en un lugar de difıcil acceso.

Existen multitud de estrategias de planificacion decaminos publicadas en la literatura [3, 12]. Los al-goritmos basados en muestreo han adquirido unagran importancia en los ultimos anos. En parti-cular los planificadores de camino probabilısticosse basan en la generacion aleatoria de los esta-dos para calcular el camino, mediante el muestreodel espacio de configuracion. Esto permite a di-chos planificadores abordar problemas complejoscon muchos grados de libertad manteniendo tiem-pos de calculo bajos [3].

La idea fundamental de los planificadores basadosen muestreo es la de aproximar la conectividad delespacio de configuraciones mediante una estructu-ra de grafos. El espacio a explorar es muestreado,generando estados que formaran los vertices de di-cho grafo. Las lıneas que unen los vertices del grafodenotan segmentos de camino validos. Planifica-dores basados muestreo no garantizan encontraruna solucion, si es que existe, y esta es una pro-piedad que es referida como exhaustividad. Losplanificadores basados en muestreo aseguran unanocion mas debil denominada exhaustividad pro-babilıstica: la solucion sera encontrada, si es queexiste, si se da el tiempo de ejecucion suficiente alalgoritmo, el cual puede ser infinito.

Algunos de los planificadores basados en muestreo[15] mas extendidos y que se compararan poste-riormente son:

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 379

Rapidly-exploring Random Trees(RRT): Se generan estados aleatorios,qrand, en el espacio de estado, tras ello, seencuentra el estado del arbol mas cercano,qnearest al generado aleatoriamente y seexpande el arbol desde qc hacia qrand, hastaque el estado qnew es alcanzado, siendo dichoestado qnew anadido al arbol de exploracion[10].

Probabilistic Roadmap Method(PRM): Se construye una hoja de rutagenerando los estados de forma aleatoria,reduciendo considerablemente el tiempo decalculo. El movimiento que conecta dosestados dados se reduce a una busquedadiscreta (por ejemplo usando A* o Dijkstra)en la hoja de ruta [8].

Expansive Space Trees (EST): Planifica-dor con estructura de arbol que trata de de-tectar regiones menos exploradas descompo-niendo el espacio en areas de visibilidad. Elplanificador construye dos arboles, uno des-de la configuracion inicial y el otro desde laconfiguracion final, los cuales iran creciendohasta que la region de visibilidad de un arbolintersecte con la del otro [4].

Single-query Bi-directional Lazy colli-sion checking planner (SBL): Version bi-direccional de EST con una estrategia decomprobacion de colisiones “lazy”, lo que sig-nifica que se pospone la comprobacion de co-lisiones hasta la obtencion de un camino paracomprobar si es valido [13].

Kinematic Planning by Interior-exterior Cell exploration (KPIECE):Planificador con estructura de arbol queusa una discretizacion basada en celdas amultiples niveles para estimar la coberturadel espacio de estado. La estimacion de lacobertura ayuda al planificador a detectarareas menos exploradas del espacio de es-tados. Esta especıficamente disenado parasistemas con dinamicas complejas, donde esnecesario una simulacion basada en la fısica[14].

Path-Directed Subdivision Trees(PDST): Se basa en un arbol que intentadetectar la zona menos explorada del espacioa traves del uso de una particion binariade una proyeccion del espacio de estado.Esta exploracion esta sesgada hacia celulasgrandes con pocos segmentos. A diferenciade la mayorıa de los planificadores basadosen arboles que se expanden desde el puntofinal aleatoriamente seleccionado de unsegmento del camino, PDST expande desde

un punto seleccionado al azar a lo largo de unsegmento del camino seleccionado de formadeterminista [9].

En los ultimos anos se han empezado a emplear di-chos algoritmos de planificacion en el contexto dela manipulacion con robots aereos [2, 11]. En esteartıculo se comparan mediante simulacion los re-sultados de dichos planificadores en el entorno in-dustrial complejo considerado en el proyecto AR-CAS. El entorno de simulacion empleado se basaen la Open Motion Planning Library (OMPL) [15](Open Motion Planning Library). En la seccion 2se describen los algoritmos basados en funcionesde coste que han sido implementados. A continua-cion, en la seccion 3, se compara una baterıa deplanificadores basados en muestreo para el robotaereo independiente y para el sistema completocompuesto con el robot aereo con el manipulador.Finalmente la seccion 4 presenta algunas conclu-siones y lıneas de desarrollo futuras.

2. PLANIFICACION DECAMINOS CON FUNCIONESDE COSTE

A pesar de que los algoritmos basados en mues-treo pueden calcular una solucion a un problemacomplejo a un coste computacional relativamentebajo, dicha solucion puede estar bastante alejadadel optimo. En muchas aplicaciones obtener unade las muchas posibles soluciones de un problemano es suficiente, ya que puede ser necesario consi-derar factores como la distancia a los obstaculoscircundantes, la longitud del camino a recorrer,las areas de cobertura, etc. Si estos factores no setienen en cuenta en la generacion del camino, lassoluciones pueden ser poco eficientes o incluso novalidas.

Para este tipo de problemas deberemos de teneren cuenta un objetivo de planificacion en el ge-nerador de caminos para obtener una solucion lomas cercana posible a la optima. El camino opti-mo estara determinado por una funcion de costeque traducira el objetivo que se desea maximizaren un mapa de costes en el espacio de configu-raciones tal y como se ilustra en la figura 2. Acontinuacion se explican dos de los algoritmos deplanificacion basados en funciones de coste masconocidos.

2.1. Algoritmo RRT*

El algoritmo RRT* [7] es una variante del algorit-mo RRT con algunas diferencias que le permitenel uso de funciones de coste. El algoritmo 1 mues-tra el pseudocodigo del mismo en el que se observa

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 380

Figura 2: Representacion de un mapa de coste deun algoritmo Transition-based RRT (T-RRT) en2D (la elevacion representa el coste)

que genera estados aleatorios y, de ser validos, seanade el nuevo estado al conjunto de vertices exis-tente conectando con el mas cercano. La primeradiferencia entre ambos algoritmos es la conexiondel nuevo vertice. En lugar de conectar con el nodomas cercano, primero se obtienen los nodos cerca-nos al nuevo estado utilizando la formula emplea-da en el algoritmo 1 en la lınea 7. Tras ello secalcula cual de dichos nodos minimiza el coste delcamino hasta el nuevo estado. El coste de un nodoconsiste en el coste del nodo anterior (o nodo pa-dre) mas el coste que supone el paso entre ambosnodos. El coste del nodo inicial serıa cero. De estaforma la expansion del arbol tendera a zonas conun menor coste, mejorando la calidad del camino.

La segunda diferencia consiste en la reconexion delos nodos cercanos con cada nuevo estado que seanade. Cuando un nuevo vertice es conectado alarbol, se comprueba si el coste para alcanzar losnodos cercanos mencionados es menor a traves delnuevo estado que por medio de sus nodos padre.

De ser ası se conecta, tal como vemos en la fi-gura 4, el nuevo estado con los estados cercanosque cumplen dicho criterio, eliminando el antiguovınculo entre estos nodos y sus antiguos nodos pa-dre de cara a preservar la estructura del arbol. Es-tas diferencias le otorgan al arbol de estados delalgoritmo RRT* su caracterıstico aspecto que po-demos observar en la figura 3.

2.2. Algoritmo T-RRT

El algoritmo T-RRT se vale del mapa de coste pa-ra la tarea de aceptar o rechazar nuevos estados[5]y su pseudocodigo se muestra en el algoritmo 2. Latecnica usada para evaluar la calidad del caminose basa en el criterio de trabajo mınimo, MinimalWork (MW), el cual es una alternativa al clasicocriterio de Integral de Coste (IC). La diferenciaprincipal entre estos dos metodos es que IC tratade minimizar el coste total del camino, mientras

Algoritmo 1 Algoritmo RRT*

1: V ←− xinit; e←− ∅;2: for i = 1,...,n do3: qrand ←− SampleFreei;4: qnearest ←− Nearest(G = (V ,e), qrand);5: qnew ←− Steer(qnearest,qrand);6: if ObstacleFree(qnearest,xnew) then7: Qnear ←− Near(G = (V, e), qnew,

mın γRRT∗( log(card(V ))c ard(V ))

1d ,eta);

8: V ←− V ∪ qnew;9: qmin ←− qnearest; cmin ←−Cost(qnearest) + c(Line(qnearest, qnew));

10: for each qnear ∈ Qnear do11: if CollisionFree(qnear,qnew) ∧

Cost(qnear) + c(Line(qnear,qnew)) < cminthen

12: qmin ←− qnearest; cmin ←−Cost(qnearest) + c(Line(qnearest, qnew));

13: end if14: end for15: e←− e∪ (qmin;qnew);16: for each qnear ∈ Qnear do17: if CollisionFree(qnear,qnew) ∧

Cost(qnew) + c(Line(qnear,qnew)) <Cost(qnear) then

18: qparent ←− Parent(qnear);19: end if20: end for21: e←− (e\qparent,qnear)∪(qnew;qnear);22: end if23: end for24: return G = (V ,e);

Figura 3: Camino obtenido con algoritmo RRT*

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 381

(a) (b)

(c) (d)

Figura 4: Generacion de un nuevo estado en elalgoritmo RRT*

(a) Camino segun MW (b) Camino segun IC

Figura 5: Problema con barrera de alto coste

que MW minimiza las variaciones de coste entreestados. Una de las mayores ventajas del crite-rio MW frente al IC es la reduccion de los maxi-mos locales; es decir, evitar variaciones abruptasen el mapa de coste, lo cual resulta muy impor-tante en diversas aplicaciones. Dicha diferencia sepuede apreciar en la figura 5 en la que la IC esmınima a costa de atravesar un maximo local nodeseado.

Algoritmo 2 Algoritmo T-RRT

1: T ←− InitTree(qinit);2: while not StopCondition(T ,qgoal) do3: qrand ←− SampleConf(mathcalC);4: qnear ←− NearestNeighbor(qrand,T );5: qnew ←− extend(T ,qnearest,qrand);6: if qnew 6= NULL ANDTransitionTest(c(qnear),c(qnew),dnear−new)AND MinexpandControl(T ,qnear,qrand)then

7: AddNewNode(T ,qnew);8: AddNewNode(T ,qnear ,qnew);9: end if

10: end while11: return G = (V ,e);

Para la exploracion del mapa y la validacion de losnuevos estados se usan dos funciones en la lınea 6del algoritmo 2. Estas funciones se describen enlos algoritmos 3 y 4, y se explican a continuacion.

2.2.1. Funcion de transicion

Esta funcion es la encargada de rechazar estadoscon un elevado gradiente del coste. Para ello, laecuacion que podemos ver en la lınea 8 del algo-ritmo 3 asigna una probabilidad a dicho gradiente,siendo menor cuanto mayor sea dicha diferencia decoste.

Algoritmo 3 Funcion TransitionTest(ci,cj ,dij)

1: nFail = GetCurrentNFail();2: if cj > cmax then3: return False;4: end if5: if cj < ci then6: return True;7: end if

8: p = exp(−

(cj−ci)

dij

K·Temp );

9: if Rand(0,1) ¡p then10: Temp = Temp

α ;11: nFail = 0;12: return True;13: else14: if nFail > nFailmax then15: Temp = Temp · α;16: nFail = 0;17: else18: nFail = nFail + 1;19: end if20: return False;21: end if

A continuacion se explican algunos de los parame-tros de la misma:

p simboliza la probabilidad de aceptacion delnuevo estado.

(cj − ci)/d es la rampa del coste.

K es una constante para normalizar la ecua-cion.

Temp permite la auto-regulacion del algorit-mo. Un valor alto de este parametro permitesubir abruptas rampas de coste, mientras queun valor mas pequeno mantiene los nuevos es-tados en areas mas llanas.

Notese la capacidad de auto-regulacion del algo-ritmo. Al subir pendientes en el mapa de coste,Temp baja para disminuir la probabilidad de quedichos estados sean aceptados evitando caminosmenos optimos. Por contra, cuando el numero defallos alcance un maximo, Temp se incrementa yesto permite al algoritmo salir de mınimos localeso valles.

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 382

2.2.2. Control de expansion

Esta funcion del algoritmo tiene el proposito demantener una relacion mınima de expansion delplanificador. Esto se consigue rechazando los es-tados en zonas ya exploradas, llamados nodos derefinamiento, de cara a incrementar el numero denuevos estados en la frontera (nodos de explora-cion).

Algoritmo 4 MinexpandControl(T ,qnear,qrand)

1: if Distance(qnear,qrand) > δ then2: UpdateNbNodeTree(T );3: return True;4: else5: if NbRefineNodeTree(T )+1

NbNodeTree(T )+1 > ρ then

6: return False;7: else8: UpdateNbRefineNodeTree(T );9: UpdateNbNodeTree(T );

10: return True;11: end if12: end if

3. COMPARATIVA DETECNICAS BASADAS ENMUESTREO PARA ELROBOT AEREO CON ELBRAZO MANIPULADOR

Para el estudio de los algoritmos se ha usado unaherramienta de evaluacion comparativa, bench-marking en ingles, empleando un modelo de multi-rotor generico sin manipulador y un modelo delentorno facilitado por el Centro Avanzado de Tec-nologıas Aeroespaciales (CATEC) en el proyectoARCAS que se muestra en la figura 6. De esta for-ma se podra evaluar el camino calculado usandodistintas versiones del algoritmo RRT y, a su vez,comprobar el efecto producido por la modificacionde los parametros de dichos algoritmos.

Para la evaluacion comparativa de los algoritmosRRT con funciones de coste se usara la herramien-ta de benchmarking de la OMPL 1 en el escena-rio descrito. Dicha librerıa se ha configurado pararealizar planificacion geometrica con restriccionessobre las velocidades y acelaraciones maximas ad-misibles en el vehıculo.

Se han aplicado los algoritmos RRT* y T-RRTalternando entre tres diferentes objetivos para laplanificacion que se van a denominar Length, Me-chanicalwork y Maxminclearance. El primer obje-tivo trata de reducir la longitud del camino gene-rado, mientras que el segundo, como ya se ha expli-

1http://ompl.kavrakilab.org/

Figura 6: Modelo 3D del escenario industrial depruebas construido en las instalaciones del CA-TEC en el que se muestran las configuracionesinicial (abajo a la derecha) y final (en el centro)empleadas en todas las simulaciones

cado anteriormente, trata de reducir los gradientesde coste durante la generacion del camino, esto es,reducir los maximos locales. El tercer objetivo si-gue una idea similar al objetivo Mechanicalwork.En lugar de intentar maximizar la distancia to-tal a objetos, lo cual podrıa incrementar mucho lalongitud del camino e incluso los mınimos localesque degradaran la solucion encontrada, Maxmin-Clearance trata de maximizar los mınimos localesque se dan en la funcion de distancia a obstaculos.

En la figura 7 puede verse una comparacion entrelos algoritmos RRT* con los tres diferentes objeti-vos de optimizacion y el algoritmo T-RRT. En ellase puede ver la principal diferencia entre ambos al-goritmos, el RRT* buscara el camino mas optimohasta llegar al tiempo lımite, mientras que el algo-ritmo T-RRT devolvera el primer camino encon-trado. Aun ası, se puede apreciar la gran ventajaque presenta el algoritmo T-RRT en la suavidadde la solucion con respecto a los RRT*.

A continuacion en la figura 8 se comparan, debidoa su mayor similitud, los resultados entre el algo-ritmo T-RRT y el algoritmo RRT* con el objetivode Mechanicalwork sin la condicion de cumplir untiempo determinado. De esta forma se puede com-parar el algoritmo RRT* y el T-RRT en condicio-nes mas parecidas. Por desgracia la herramienta deevaluacion comparativa de OMPL no contempla laopcion de incluir graficas que muestren el Mecha-nicalwork. En la figura 8 se puede observar que elalgoritmo RRT* y T-RRT tienen caracterısticasmuy similares con excepcion de la suavidad de lasolucion. Por lo tanto, el algoritmo T-RRT pare-ce ser muy adecuado para problemas donde primemas la velocidad de obtencion de un camino vali-do, mientras que el algoritmo RTT* se usarıa enel caso en el que el tiempo de computo no seacrıtico, pudiendo encontrar una solucion lo mascercana posible a la optima.

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 383

(a) Suavidad de la solucion

(b) Longitud de la solucion

(c) Tiempo requerido

(d) Distancia a obstaculos

Figura 7: Comparacion de los resultados de los al-goritmos RRT* y T-RRT teniendo en cuenta dis-tintas metricas

(a) Suavidad de la solucion

(b) Longitud de la solucion

(c) Tiempo requerido

(d) Distancia a obstaculos

Figura 8: Comparacion entre los resultados de losalgoritmos T-RRT y RRT* con objetivo Mechani-calwork teniendo en cuenta distintas metricas

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 384

Figura 9: Estados inicial y final de la simulacion

A continuacion se mostraran los resultados corres-pondientes a una tarea de manipulacion para el ro-bot aereo equipado con un brazo robotico de seisgrados de libertad. Especıficamente, se ha simula-do el caso del transporte de una barra desde unextremo de una superficie hasta la opuesta evi-tando un obstaculo situado en el medio de dichasuperficie, como puede verse en la figura 9. La geo-metrıa del objeto manipulado tambien se tiene encuenta en la simulacion.

Para mayor claridad en los resultados se ha em-pleado el objetivo de planificacion de mınima lon-gitud del camino en los algoritmos que utilizanfunciones de coste. Se han ejecutado 100 simula-ciones de planificacion por cada algoritmo con untiempo lımite de 5 segundos, en las cuales todoslos algoritmos han sido capaces de obtener un al-to porcentaje de caminos validos, alcanzando el100 % la mayorıa de ellos.

Como se puede observar en la figura 10, los al-goritmos RRT obtienen una respuesta similar alos PRM, y ambos consiguen un camino mas cor-to aunque la suavidad del camino es inferior ala conseguida con otros planificadores como EST,KPIECE o SBL. Cabe una mencion especial al al-goritmo RRTConnect que ha obtenido en todas laspruebas alto porcentaje de exito empleando unostiempos de computo muy bajos.

4. CONCLUSIONES YDESARROLLOS FUTUROS

En este artıculo se han comparado mediante simu-lacion los resultados de varios planificadores basa-dos en muestreo en un entorno industrial complejoconsiderado en el proyecto ARCAS. Dichos plani-

(a) Longitud de la solucion

(b) Tiempo de computo

Figura 10: Resultados de la planificacion para elrobot aereo equipado con un brazo manipuladorde seis grados de libertad. Se comparan los dis-tintos algoritmos de planificacion explicados an-teriormente para dos metricas: la longitud de lasolucion y el tiempo de computo requerido

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 385

ficadores han demostrado ser unos algoritmos deplanificacion capaces de resolver problemas com-plejos como el propuesto. En primer lugar se haevaluado la mejora que se consigue mediante la in-clusion de funciones de coste para el robot aereosin el manipulador. Finalmente se ha comparadouna baterıa de planificadores basados en muestreopara el sistema completo compuesto por el robotaereo con el manipulador.

Como desarrollos futuros, y siguiendo la temati-ca del proyecto ARCAS, se plantea el desarrollode estrategias de planificacion conjuntas entre va-rios robots aereos, basandose en algoritmos comolos aquı empleados [6], para tareas de manipula-cion involucrando el transporte de objetos [1] y laconstruccion de estructuras.

Agradecimientos

Este trabajo ha sido financiado parcialmentepor los proyectos ARCAS (ICT-2011-287617) delseptimo Programa Marco y AEROARMS (H2020-ICT-2014-644271) del Programa Horizon 2020 dela Comision Europea y el proyecto nacional RAN-COM (P11-TIC-7066).

Referencias

[1] Markus Bernard, Konstantin Kondak, IvanMaza, and Anibal Ollero. Autonomous trans-portation and deployment with aerial robotsfor search and rescue missions. Journal ofField Robotics, 28(6):914–931, 2011.

[2] Alexandre Boeuf, Juan Cortes, Rachid Ala-mi, and Thierry Simeon. Planning agile mo-tions for quadrotors in constrained environ-ments. In Proc. of the IEEE/RSJ Interna-tional Conference on Intelligent Robots andSystems, pages 218–223, 2014.

[3] M. Elbanhawi and M. Simic. Sampling-basedrobot motion planning: A review. Access,IEEE, 2:56–77, 2014.

[4] D. Hsu, J.-C. Latombe, and R. Motwani.Path planning in expansive configuration spa-ces. In Robotics and Automation, 1997. Pro-ceedings., 1997 IEEE International Confe-rence on, volume 3, pages 2719–2726 vol.3,Apr 1997.

[5] L. Jaillet, J. Cortes, and T. Simeon.Sampling-based path planning onconfiguration-space costmaps. Robotics,IEEE Transactions on, 26(4):635–646, Aug2010.

[6] S. Kamio and H. Iba. Cooperative objecttransport with humanoid robots using RRT

path planning and re-planning. In IntelligentRobots and Systems, 2006 IEEE/RSJ In-ternational Conference on, pages 2608–2613,Oct 2006.

[7] S. Karaman and E. Frazzoli. Sampling-based algorithms for optimal motion plan-ning. International Journal of Robotics Re-search, 30(7):846–894, June 2011.

[8] L.E. Kavraki, P. Svestka, J.-C. Latombe, andM.H. Overmars. Probabilistic roadmaps forpath planning in high-dimensional configura-tion spaces. Robotics and Automation, IEEETransactions on, 12(4):566–580, Aug 1996.

[9] Andrew M. Ladd, Rice Unversity, Lydia E.Kavraki, and Rice Unversity. Motion plan-ning in the presence of drift, underactuationand discrete system changes. In In Robotics:Science and Systems I, pages 233–241. MITPress, 2005.

[10] Steven M. Lavalle. Rapidly-exploring randomtrees: A new tool for path planning. Technicalreport, 1998.

[11] Montserrat Manubens, Didier Devaurs, LluısRos, and Juan Cortes. Motion planning for 6-D manipulation with aerial towed-cable sys-tems. In Proc. of the Robotics Science andSystems Conference, 2013.

[12] N. B. Ismail S. H. Tang, W. Khaksar andM. K. A. Ariffin. A review on robot motionplanning approaches. Pertanika Journal ofScience and Technology, 20(1):15–29, 2012.

[13] Gildardo Sanchez and Jean claude Latom-be. A single-query bi-directional probabilisticroadmap planner with lazy collision checking,2001.

[14] Ioan A. Sucan and Lydia E. Kavraki. Kinody-namic motion planning by interior-exteriorcell exploration. In GregoryS. Chirikjian, Ho-wie Choset, Marco Morales, and Todd Murp-hey, editors, Algorithmic Foundation of Ro-botics VIII, volume 57 of Springer Tracts inAdvanced Robotics, pages 449–464. SpringerBerlin Heidelberg, 2010.

[15] Ioan A. Sucan, Mark Moll, and Lydia E.Kavraki. The Open Motion Planning Li-brary. IEEE Robotics & Automation Ma-gazine, 19(4):72–82, December 2012. http:

//ompl.kavrakilab.org.

Actas de las XXXVI Jornadas de Automática, 2 - 4 de septiembre de 2015. Bilbao ISBN 978-84-15914-12-9 © 2015 Comité Español de Automática de la IFAC (CEA-IFAC) 386