Planificarea mișcării

problemele cu dimensiuni reduse pot fi rezolvate cu algoritmi bazați pe grilă care suprapun o grilă deasupra spațiului de configurare sau algoritmi geometrici care calculează forma și conectivitatea Cfree.

planificarea exactă a mișcării pentru sistemele de înaltă Dimensiune sub constrângeri complexe este dificil de calculat. Algoritmii de câmp potențial sunt eficienți, dar cad pradă minimelor locale (o excepție este câmpurile potențiale armonice). Algoritmii bazați pe eșantionare evită problema minimelor locale și rezolvă multe probleme destul de repede.Ei nu sunt capabili să determine că nu există nicio cale, dar au o probabilitate de eșec care scade la zero pe măsură ce se petrece mai mult timp.

algoritmii bazați pe eșantionare sunt considerați în prezent de ultimă generație pentru planificarea mișcării în spații cu dimensiuni înalte și au fost aplicați problemelor care au zeci sau chiar sute de dimensiuni (manipulatori robotici, molecule biologice, personaje digitale animate și roboți cu picioare).

există algoritmul paralel de planificare a mișcării (A1-A2) pentru manipularea obiectelor (pentru prinderea obiectului zburător).

căutare bazată pe Gridedit

abordările bazate pe Grid suprapun o grilă pe spațiul de configurare și presupun că fiecare configurație este identificată cu un punct de rețea. La fiecare punct de rețea, robotului i se permite să se deplaseze în punctele de rețea adiacente, atâta timp cât linia dintre ele este complet conținută în Cfree (aceasta este testată cu detectarea coliziunilor). Acest lucru discretizează setul de acțiuni, iar algoritmii de căutare (cum ar fi A*) sunt folosiți pentru a găsi o cale de la început până la obiectiv.

aceste abordări necesită setarea unei rezoluții a grilei. Căutarea este mai rapidă cu grile mai grosiere, dar algoritmul nu va reuși să găsească căi prin porțiuni înguste de Cfree. Mai mult, numărul de puncte de pe grilă crește exponențial în dimensiunea spațiului de configurare, ceea ce le face inadecvate pentru probleme de înaltă Dimensiune.

abordările tradiționale bazate pe rețea produc căi ale căror schimbări de direcție sunt constrânse la multipli ai unui unghi de bază dat, rezultând adesea căi suboptime. Abordările de planificare a căilor în orice unghi găsiți căi mai scurte prin propagarea informațiilor de-a lungul marginilor grilei (pentru a căuta rapid) fără a-și constrânge căile către marginile grilei (pentru a găsi căi scurte).

abordările bazate pe rețea trebuie adesea să caute în mod repetat, de exemplu, atunci când cunoștințele robotului despre spațiul de configurare se schimbă sau spațiul de configurare în sine se schimbă în timpul urmăririi căii. Algoritmii de căutare euristică incrementală replanează rapid folosind experiența cu problemele anterioare similare de planificare a căii pentru a accelera căutarea lor pentru cea actuală.

căutare bazată pe intervale

aceste abordări sunt similare cu abordările de căutare bazate pe rețea, cu excepția faptului că generează un pavaj care acoperă în întregime spațiul de configurare în loc de o rețea. Pavajul este descompus în două subpavaje X -, X + realizate cu cutii astfel încât X-Xxfree X X+. Caracterizarea Cfree se ridică pentru a rezolva o problemă de inversiune setată. Analiza intervalului ar putea fi astfel utilizată atunci când Cfree nu poate fi descrisă prin inegalități liniare pentru a avea o incintă garantată.

robotul este astfel permis să se miște liber în X− și nu poate ieși în afara X+. Pentru ambele subpavings, un grafic vecin este construit și căi pot fi găsite folosind algoritmi, cum ar fi Dijkstra sau a*. Atunci când o cale este fezabilă în X−, este, de asemenea, fezabilă în Cfree. Când nu există nicio cale în X + de la o configurație inițială la obiectiv, avem garanția că nu există nicio cale fezabilă în Cfree. În ceea ce privește abordarea bazată pe rețea, abordarea pe intervale este inadecvată pentru problemele cu dimensiuni ridicate, datorită faptului că numărul de cutii care urmează să fie generate crește exponențial în raport cu dimensiunea spațiului de configurare.

o ilustrare este oferită de cele trei figuri din dreapta unde un cârlig cu două grade de libertate trebuie să se deplaseze de la stânga la dreapta, evitând două segmente orizontale mici.

descompunerea cu subpavings folosind analiza intervalului face, de asemenea, posibilă caracterizarea topologiei Cfree, cum ar fi numărarea numărului său de componente conectate.

algoritmi Geometriciedit

roboți punctuali printre obstacole poligonale

• Grafic de vizibilitate
• descompunere celulară

traducerea obiectelor printre obstacole

• suma Minkowski

găsirea unei ieșiri dintr-o clădire

• cea mai îndepărtată urmă de raze

având în vedere un pachet de raze în jurul poziției actuale atribuite cu lungimea lor lovind un perete, robotul se deplasează în direcția celei mai lungi raze, cu excepția cazului în care este identificată o ușă. Un astfel de algoritm a fost utilizat pentru modelarea ieșirii de urgență din clădiri.

câmpuri potențiale Artificialeedit

o abordare este de a trata configurația robotului ca un punct într-un câmp potențial care combină atracția față de obiectiv și repulsia față de obstacole. Traiectoria rezultată este de ieșire ca cale. Această abordare are avantaje prin faptul că traiectoria este produsă cu puțin calcul. Cu toate acestea, ei pot deveni prinși în minimele locale ale câmpului potențial și nu reușesc să găsească o cale sau pot găsi o cale non-optimă. Câmpurile potențiale artificiale pot fi tratate ca ecuații continuum similare câmpurilor potențiale electrostatice (tratând robotul ca o sarcină punctuală), sau mișcarea prin câmp poate fi discretizată folosind un set de reguli lingvistice.O funcție de navigație sau o funcție de navigație probabilistică sunt tipuri de funcții potențiale artificiale care au calitatea de a nu avea puncte minime, cu excepția punctului țintă.

algoritmi pe bază de Eșantionareedit

algoritmii pe bază de eșantionare reprezintă spațiul de configurare cu o foaie de parcurs a configurațiilor eșantionate.Un algoritm de bază eșantionează n configurații în C și le păstrează pe cele din Cfree pentru a le folosi ca repere. Apoi se construiește o foaie de parcurs care conectează două repere P și Q dacă segmentul de linie PQ este complet în Cfree. Din nou, detectarea coliziunilor este utilizată pentru a testa includerea în Cfree. Pentru a găsi o cale care leagă S și G, acestea sunt adăugate la foaia de parcurs. Dacă o cale din foaia de parcurs leagă s și G, Planificatorul reușește și returnează acea cale. Dacă nu, motivul nu este definitiv: fie nu există nicio cale în Cfree, fie Planificatorul nu a eșantionat suficiente repere.

acești algoritmi funcționează bine pentru spațiile de configurare de înaltă dimensiune, deoarece, spre deosebire de algoritmii combinatori, timpul lor de funcționare nu depinde (Explicit) exponențial de dimensiunea lui C. De asemenea, sunt (în general) substanțial mai ușor de implementat. Acestea sunt probabilistic complete, ceea ce înseamnă că probabilitatea ca acestea vor produce o soluție se apropie 1 ca mai mult timp este petrecut. Cu toate acestea, ei nu pot determina dacă nu există nicio soluție.

având în vedere condițiile de vizibilitate de bază pe Cfree, s-a dovedit că, pe măsură ce numărul de configurații N crește, probabilitatea ca algoritmul de mai sus să găsească o soluție se apropie de 1 exponențial. Vizibilitatea nu depinde în mod explicit de dimensiunea lui C; este posibil să existe un spațiu de dimensiuni mari cu vizibilitate „bună” sau un spațiu de dimensiuni reduse cu vizibilitate „slabă”. Succesul experimental al metodelor bazate pe eșantioane sugerează că spațiile cele mai frecvent văzute au o vizibilitate bună.

există multe variante ale acestei scheme de bază:

• este de obicei mult mai rapid să testați doar segmente între perechile de repere din apropiere, mai degrabă decât toate perechile.
• distribuțiile de eșantionare neuniforme încearcă să plaseze mai multe repere în domenii care îmbunătățesc conectivitatea foii de parcurs.
• eșantioanele Quasirandom produc de obicei o acoperire mai bună a spațiului de configurare decât cele pseudorandomice, deși unele lucrări recente susțin că efectul sursei de aleatorie este minim în comparație cu efectul distribuției eșantionării.
• folosește eșantionarea locală prin efectuarea unui lanț Markov direcțional Monte Carlo plimbare aleatorie cu o distribuție locală de propuneri.
• este posibil să se reducă substanțial numărul de repere necesare pentru a rezolva o problemă dată, permițând vederea curbată a ochilor (de exemplu, prin accesarea cu crawlere a obstacolelor care blochează calea dintre două repere).
• dacă sunt necesare doar una sau câteva întrebări de planificare, nu este întotdeauna necesar să se construiască o foaie de parcurs a întregului spațiu. Variantele de creștere a copacilor sunt de obicei mai rapide pentru acest caz (planificare cu o singură interogare). Foile de parcurs sunt încă utile dacă se vor face multe interogări în același spațiu (planificare multi-interogare)

lista algoritmilor notabiliedit

• A *
• D *
• explorarea rapidă a arborelui aleatoriu
• foaie de parcurs probabilistică