La planificació del moviment , també coneguda com a problema de navegació o problema del motor del piano, és un problema computacional per trobar una seqüència de configuracions vàlides que mogui l'objecte des de l'origen fins a la destinació. El terme s'utilitza en geometria computacional, animació per ordinador, robòtica i jocs d'ordinador.
Per exemple, considereu la possibilitat de navegar amb un robot mòbil dins d'un edifici fins a un punt de referència distant. Hauria d'executar aquesta tasca evitant parets i sense caure per les escales. Un algorisme de planificació de moviment prendria una descripció d'aquestes tasques com a entrada i produiria les ordres de velocitat i gir enviades a les rodes del robot. Els algorismes de planificació de moviment podrien abordar robots amb un nombre més gran d'articulacions (per exemple, manipuladors industrials), tasques més complexes (per exemple, manipulació d'objectes), diferents restriccions (per exemple, un cotxe que només pot conduir cap endavant) i incertesa (per exemple, models imperfectes de l'entorn o del robot).
La planificació del moviment té diverses aplicacions en robòtica, com ara l'autonomia, l'automatització i el disseny de robots en programari CAD, així com aplicacions en altres camps, com ara l'animació de personatges digitals, videojocs, disseny arquitectònic, cirurgia robòtica i l'estudi de molècules biològiques.
Conceptes miniatura|Exemple d'un espai de treball miniatura|Espai de configuració d'un robot de mida puntual. Blanc = C lliure, gris = C obs. Un problema bàsic de planificació de moviment és calcular una trajectòria contínua que connecti una configuració inicial S i una configuració d'objectiu G, evitant alhora la col·lisió amb obstacles coneguts. La geometria del robot i dels obstacles es descriu en un espai de treball 2D o 3D, mentre que el moviment es representa com una trajectòria en un espai de configuració (possiblement de dimensió superior).
Espai de configuració Una configuració descriu la postura del robot, i l'espai de configuració C és el conjunt de totes les configuracions possibles. Per exemple:
Si el robot és un únic punt (de mida zero) que es trasllada en un pla bidimensional (l'espai de treball), C és un pla i una configuració es pot representar mitjançant dos paràmetres (x, y). Si el robot té una forma 2D que es pot traslladar i girar, l'espai de treball continua sent bidimensional. Tanmateix, C és el grup euclidià especial SE (2) = R 2 SO (2) (on SO (2) és el grup ortogonal especial de rotacions 2D), i una configuració es pot representar utilitzant 3 paràmetres (x, y, θ). Si el robot és una forma sòlida en 3D que es pot traslladar i girar, l'espai de treball és tridimensional, però C és el grup euclidià especial SE(3) = R 3 Així doncs (3), la configuració requereix 6 paràmetres: (x, y, z) per a la translació i angles d'Euler (α, β, γ). Si el robot és un manipulador de base fixa amb N articulacions revolutòries (i sense bucles tancats), C és N-dimensional. Si el bloqueig del cardan no és acceptable (per exemple, en R₂N on N ≥ 3 ), pot ser necessari l'ús de quaternions o altres solucions alternatives, cosa que augmentarà les dimensions rotacionals o la complexitat de la solució.
Espai lliure El conjunt de configuracions que evita la col·lisió amb obstacles s'anomena espai lliure C free. El complementari de C lliure en C s'anomena regió obstacle o prohibida.
Sovint, és prohibitivament difícil calcular explícitament la forma de C free. Tanmateix, provar si una configuració determinada és lliure de C és eficient. Primer, la cinemàtica directa determina la posició de la geometria del robot i la detecció de col·lisions comprova si la geometria del robot xoca amb la geometria de l'entorn. miniatura|Espai de configuració per a un robot rectangular de translació (imatge vermella). Blanc = C lliure, gris = C obs, on gris fosc = els objectes, gris clar = configuracions on el robot tocaria un objecte o sortiria de l'espai de treball.
Espai objectiu L'espai objectiu és un subespai de l'espai lliure que indica on volem que es mogui el robot. En la planificació de moviment global, l'espai objectiu és observable pels sensors del robot. Tanmateix, en la planificació de moviment local, el robot no pot observar l'espai objectiu en alguns estats. Per resoldre aquest problema, el robot passa per diversos espais objectiu virtuals, cadascun dels quals es troba dins de l'àrea observable (al voltant del robot). Un espai objectiu virtual s'anomena subobjectiu.
Espai d'obstacles L'espai d'obstacles és un espai al qual el robot no es pot moure. L'espai d'obstacles no és l'oposat de l'espai lliure
Algorismes Els problemes de baixa dimensió es poden resoldre amb algorismes basats en quadrícules que superposen una quadrícula a sobre de l'espai de configuració, o algorismes geomètrics que calculen la forma i la connectivitat de C free.
La planificació exacta del moviment per a sistemes d'alta dimensionalitat sota restriccions complexes és computacionalment impossible de resoldre. Els algorismes de camp potencial són eficients, però són víctimes dels mínims locals (una excepció són els camps potencials harmònics). Els algorismes basats en mostreig eviten el problema dels mínims locals i resolen molts problemes amb força rapidesa. No poden determinar que no existeix cap camí, però tenen una probabilitat de fallada que disminueix a zero a mesura que es dedica més temps.
Els algorismes basats en mostreig actualment es consideren l'última tecnologia per a la planificació del moviment en espais d'alta dimensionalitat i s'han aplicat a problemes que tenen desenes o fins i tot centenars de dimensions (manipuladors robòtics, molècules biològiques, personatges digitals animats i robots amb potes).
Cerca basada en quadrícula Els enfocaments basats en quadrícules superposen una quadrícula a l'espai de configuració i assumeixen que cada configuració s'identifica amb un punt de la quadrícula. A cada punt de la quadrícula, el robot es pot moure a punts de la quadrícula adjacents sempre que la línia entre ells estigui completament continguda dins de C lliure (això es prova amb detecció de col·lisions). Això discretitza el conjunt d'accions i s'utilitzen algorismes de cerca (com A*) per trobar un camí des de l'inici fins a l'objectiu.
Aquests mètodes requereixen establir una resolució de quadrícula. La cerca és més ràpida amb quadrícules més gruixudes, però l'algorisme no podrà trobar camins a través de porcions estretes de C free. A més, el nombre de punts de la quadrícula creix exponencialment en la dimensió de l'espai de configuració, cosa que els fa inadequats per a problemes d'alta dimensionalitat.
Els enfocaments tradicionals basats en quadrícules produeixen trajectòries els canvis de rumb de les quals estan restringits a múltiples d'un angle base determinat, cosa que sovint resulta en trajectòries subòptimes. Els enfocaments de planificació de camins des de qualsevol angle troben camins més curts propagant informació al llarg de les vores de la quadrícula (per cercar ràpidament) sense restringir els seus camins a les vores de la quadrícula (per trobar camins curts).
Els planificadors de moviment també poden optimitzar múltiples objectius més enllà de la longitud de la trajectòria, com ara el temps de recorregut, el consum d'energia o la superació d'obstacles. Per exemple, els planificadors multiobjectiu poden adaptar la importància relativa d'aquests objectius al context de la tasca i a les condicions de funcionament del robot.
Els enfocaments basats en quadrícules sovint necessiten cercar repetidament, per exemple, quan el coneixement del robot sobre l'espai de configuració canvia o el mateix espai de configuració canvia durant el seguiment de la trajectòria. Els algorismes de cerca heurística incremental replanifiquen ràpidament utilitzant l'experiència amb problemes de planificació de camins similars anteriors per accelerar la cerca de l'actual.
Cerca basada en intervals Aquests enfocaments són similars als enfocaments de cerca basats en quadrícula, excepte que generen un paviment que cobreix completament l'espai de configuració en lloc d'una quadrícula. El paviment es descompon en dos subpaviments X − ,X + fets amb caixes de manera que X − ⊂ C lliure ⊂ X +. Caracterització de quantitats lliures de C per resoldre un problema d'inversió de conjunts. Per tant, l'anàlisi d'intervals es podria utilitzar quan C lliure no es pot descriure mitjançant desigualtats lineals per tal de tenir un tancament garantit.
Per tant, el robot es pot moure lliurement en X − i no pot sortir de X +. Per a ambdós subpaviments, es construeix un graf de veïns i es poden trobar camins mitjançant algorismes com ara Dijkstra o A*. Quan un camí és factible a X −, també és factible a Clliure. Quan no existeix cap camí a X + des d'una configuració inicial fins a l'objectiu, tenim la garantia que no existeix cap camí factible a C. Pel que fa a l'enfocament basat en quadrícula, l'enfocament d'intervals no és apropiat per a problemes d'alta dimensionalitat, a causa del fet que el nombre de caixes a generar creix exponencialment respecte a la dimensió de l'espai de configuració.
Una il·lustració la proporcionen les tres figures de la dreta, on un ganxo amb dos graus de llibertat s'ha de moure d'esquerra a dreta, evitant dos petits segments horitzontals. miniatura|Moviment des de la configuració inicial (blava) fins a la configuració final del ganxo, evitant els dos obstacles (segments vermells). La cantonada inferior esquerra del ganxo ha de romandre sobre la línia horitzontal, cosa que fa que el ganxo tingui dos graus de llibertat. Nicolas Delanoue ha demostrat que la descomposició amb subpaviments mitjançant l'anàlisi d'intervals també permet caracteritzar la topologia de C lliure, com ara comptant el seu nombre de components connectats.
Algorismes geomètrics Apunta robots entre obstacles poligonals
Gràfic de visibilitat Descomposició cel·lular Diagrama de Voronoi
Trasllat d'objectes entre obstacles
Suma de Minkowski
Trobar la sortida d'un edifici
Traça de raigs més llunyanaminiatura|Exemple d'una ruta vàlidaminiatura|Exemple d'una ruta vàlidaminiatura|Exemple de mapa de carreteres
Donat un feix de raigs al voltant de la posició actual atribuït a la seva longitud que colpeja una paret, el robot es mou en la direcció del raig més llarg tret que s'identifiqui una porta. Aquest algorisme es va utilitzar per modelar la sortida d'emergència dels edificis.
Camps de potencial artificial Un enfocament és tractar la configuració del robot com un punt en un camp potencial que combina l'atracció cap a l'objectiu i la repulsió dels obstacles. La trajectòria resultant es mostra com a camí. Aquest mètode té l'avantatge que la trajectòria es produeix amb poc càlcul. Tanmateix, poden quedar atrapats en mínims locals del camp potencial i no aconsegueixen trobar un camí, o poden trobar un camí no òptim. Els camps de potencial artificials es poden tractar com a equacions contínues similars als camps de potencial electrostàtic (tractant el robot com una càrrega puntual), o el moviment a través del camp es pot discretitzar mitjançant un conjunt de regles lingüístiques. Una funció de navegacióLavalle, Steven, Planning Algorithms Chapter 8 o una funció de navegació probabilística són tipus de funcions potencials artificials que tenen la qualitat de no tenir punts mínims excepte el punt objectiu.
Algorismes basats en mostreig