Planificació de moviment

El terme planificació de moviment (de l'anglés motion planning) és aplicat per a descriure un conjunt de problemes que estan relacionats en moure un objecte (robot) d'un punt inicial a un punt final evitant colisionar en els possibles obstàculs de l'entorn.

Per a l'anàlisis d'estos problemes sol utilisar-se l'espai euclidiano en dos dimensions i en ocasions es considera que la colisió en un obstàcul només ocorre en els punts interns d'este (assumint als obstàculs com a polígons simples) i no en la frontera, encara que en térmens pràctics pugues no resultar segur que un robot passe tan prop d'un obstàcul.

Algoritmes

Basats en trayectòria

Grafo de visibilitat

Este algoritme es recolza en l'us del grafo de visibilitat per a obtindre totes les trayectòries possibles que passen pels vèrtiços dels polígons (obstàculs). Una volta que es té el grafo de visibilitat s'aplica un algoritme per a trobar el camí més curt, dit algoritme pot ser el de Dijkstra.

Complexitat

La complexitat de calcular el grafo de visibilitat és $O(n^{2}log(n))$, i la complexitat de l'algoritme de Dijkstra és $O(n^2)$, per lo tant la complexitat de l'algoritme ObtenerCamino queda acotada per $O(n^{2}log(n))$.

Basats en celes

Descomposició en celes exactes

La descomposició en celes exactes és utilisada per a representar l'espai lliure d'obstàculs, una volta que es coneix n'hi ha prou en calcular una ruta a través d'este espai. Per a generar les celes s'usa un mapa trapezoidal. La construcció d'un mapa trapezoidal es realisa prenent un conjunt de polígons disjuntos, estos són tancats en una caixa per a delimitar l'espai en que es crearan els trapezoides. A continuació es tracen llínees verticals en els vèrtiços de cada polígon fins que la llínea alcança algun obstàcul, ya siga la frontera d'algun polígon o la «caixa». Una volta que es té el mapa trapezoidal es deuen calcular les celes que representen a l'espai lliure, açò es pot fer simplement removent els trapezoides que es troben en l'interior dels polígons.

Archiu:Descomposición en celdas exactas usando mapa trapezoidal.png

Descomposició en celes exactes usant mapa trapezoidal

Per a trobar una trayectòria lliure d'obstàculs des del punt inicial del robot fins a la meta es construïx un grafo de trayectòria utilisant com a nodos els punts ubicats en els centres dels trapezoides i de les llínees verticals que constituïxen el mapa, les arestes seran les semirrecta que conecten tals punts únicament en els casos en que un punt estiga en el centre d'un trapezoide i l'atre en el centre d'una llínea vertical que constituïxca la frontera de dit trapezoide.

Una volta que es té el grafo descrit anteriorment la construcció d'un camí lliure d'obstàculs es pot fer d'acort al següent algoritme.

Descomposició en celes aproximades

En este algoritme les celes corresponen als elements formats per una reixeta de tamany fix, en este cas els obstàculs són representats com a celes completament ocupades.

Depenent del tamany de la reixeta pot passar que alguns camins lliures siguen marcats com ocupats, en estos casos una opció pot ser disminuir el tamany de les celes de la reixeta per a aumentar la precisió.