Planificación de trayectorias mediante Programación Dinámica

Planificación de trayectorias mediante
Programación Dinámica
Maikel O. Torres Piñeiro1, Valery Moreno Vega 2
1

2

Instituto Superior Politécnico José Antonio Echevarria. maikel@electrica.cujae.edu.cu
Instituto Superior Politécnico José Antonio Echevarria. valery@ electrica.cujae.edu.cu

RESUMEN / ABSTRACT
En este trabajo se realiza un análisis de dos métodos de PD utilizados en laplanificación de trayectorias de robots
móviles: uno propuesto por Kwok y Driessen (1999) y el otro el algoritmo de Bellman-Ford. A este último, se le
realizan modificaciones para incrementar aún más su velocidad de búsqueda de la solución.
Palabras claves: planificación de trayectorias, programación dinámica.

Path planning with Dynamic Programming
In this work are studied two methods ofdynamic programming that can be used in path planning of mobile robots.
The first one is proposing by Kwok and Driessen (1999) and the other one is the Bellman-Ford algorithm. The last
one will be modified to obtain better result.
Key word: path planning, dynamic programming.

INTRODUCCIÓN
La programación dinámica (PD) fue introducida por Bellman
[1] y la misma consiste en el procesomatemático de tomar una
serie de decisiones óptimas para obtener una solución global
óptima.
Este principio ha sido usado en la planificación para buscar
dentro de un conjunto de estados del espacio de configuración,
aquellos que sean óptimos según determinado criterio, para
luego conformar una trayectoria óptima.

modificaciones para incrementar aún más su velocidad de
búsqueda de la solución.MATERIALES Y MÉTODOS
Algoritmo de Bellman-Ford.
Este algoritmo determina la trayectoria más corta entre
punto inicial y todos los restantes puntos del entorno.
algoritmo propuesto por Bellman [1] se basa en
programación dinámica y su formulación recursiva es
siguiente:

Una de las principales ventajas que conlleva el uso de la PD es
que las trayectorias que se obtienen por este métodosiempre
son óptimas y se puede usar cualquier tipo de función de costo
u optimización.
Son diversos los algoritmos donde se puede encontrar la
programación dinámica, aunque en el área de la robótica
móvil, específicamente la planificación, su versión más
conocida es el llamado algoritmo de Bellman-Ford [2], no
obstante existen otros trabajos donde se aplican otras versiones
de la PD [3,4, 5].
En este trabajo se hará un análisis de dos métodos de PD
utilizados en la planificación de trayectorias de robots móviles:
uno propuesto por Kwok y Driessen (1999) y el otro el
algoritmo de Bellman-Ford [2, 6]. A este último, se le harán

0, si v = s
F (v ) = ∞, si v ≠ s


el
El
la
la

1)

0

 F k −1 (v ),



F k (v ) = min 
min
{ (w) + C vw}
 w∈ Q k −1,( w,v ) ∈ E F k −1



2)
donde:

31

Qk: Es el conjunto de estados que fueron actualizados
en la etapa k.
E : Es el conjunto de enlaces simples entre los
estados. Se considera que dos estados están enlazados
de manera simple si se puede ir de uno al otro en una
etapa.

Luego para hacer la formulación del algoritmo más completa
y acorde a las condiciones de la robótica móvillas ecuaciones
1) y 2) quedan como se muestra a continuación:

0, si v = s y v ∉ O
∞, si v ≠ s ó v ∈ O


F 0 (v ) = 

S : Estado inicial.

3)

v,w : Estados cualesquiera.
Cvw: Costo de ir del estado w al estado v.
El seudo código algoritmo puede ser definido como sigue:



 F k −1 (v ) ,



F k (v ) = min  w∈ Qminw,v ) ∈ E{F k −1 (w) + C vw}, ∀v ∉ O 
,(
k −1

∞,
∀v ∈ O 



n: Cantidad de estados.
V: Conjunto de todos los estados.

F (v ) ∀v ∈V y Q
Mientras Q ≠ 0 y k ≤ n hacer
Determinar

0

4)
donde:
0

O: Conjunto de estados ocupados por obstáculos
(estados prohibidos).

k

Calcular

Q

F k (v) ∀v ∈V y

determinar

Bellman-Ford Optimizado

k

Fin Mientras

= ∅ entonces F k (v) define la longitud de
la...