Pohybové plánování - Motion planning

Plánování pohybu , také plánování cesty (také známé jako problém s navigací nebo problém s pohybem piana ) je výpočetní problém najít posloupnost platných konfigurací, které přesouvají objekt ze zdroje do cíle. Termín se používá ve výpočetní geometrii , počítačové animaci , robotice a počítačových hrách .

Zvažte například navigaci mobilního robota uvnitř budovy na vzdálený trasový bod. Měl by provést tento úkol a přitom se vyhýbat zdem a nespadat ze schodů. Algoritmus plánování pohybu by vzal popis těchto úkolů jako vstup a vytvořil příkazy pro rychlost a otáčení zaslané na kola robota. Algoritmy plánování pohybu mohou řešit roboty s větším počtem kloubů (např. Průmyslové manipulátory), složitější úkoly (např. Manipulace s objekty), různá omezení (např. Auto, které může jet pouze vpřed) a nejistotu (např. Nedokonalé modely prostředí nebo robot).

Plánování pohybu má několik robotických aplikací, jako je autonomie , automatizace a návrh robotů v CAD softwaru , stejně jako aplikace v jiných oblastech, jako jsou animace digitálních postav , videohry , architektonický design , robotická chirurgie a studium biologických molekul .

Pojmy

Příklad pracovního prostoru.
Konfigurační prostor bodového robota. Bílá = C volná , šedá = C obs .
Konfigurační prostor pro obdélníkového překládacího robota (na obrázku červeně). Bílá = C volná , šedá = C obs , kde tmavě šedá = objekty, světle šedá = konfigurace, kde by se robot dotýkal předmětu nebo opouštěl pracovní prostor.
Příklad platné cesty.
Příklad neplatné cesty.
Příklad cestovní mapy.

Základním problémem plánování pohybu je vypočítat souvislou cestu, která spojuje počáteční konfiguraci S a cílovou konfiguraci G, přičemž se vyhýbá kolizi se známými překážkami. Geometrie robota a překážek je popsána ve 2D nebo 3D pracovním prostoru , zatímco pohyb je znázorněn jako dráha v (případně vyšší dimenzionálním) konfiguračním prostoru .

Konfigurační prostor

Konfigurace popisuje pózu robota a konfigurační prostor C je sada všech možných konfigurací. Například:

  • Pokud je robot jednobodový (nulové velikosti) překládající se ve 2rozměrné rovině (pracovní prostor), C je rovina a konfiguraci lze znázornit pomocí dvou parametrů (x, y).
  • Pokud je robot 2D tvar, který se může překládat a otáčet, pracovní prostor je stále 2-dimenzionální. Nicméně C je speciální euklidovská skupina SE (2) = R 2 SO (2) (kde SO (2) je zvláštní ortogonální skupina 2D rotací), a konfigurace mohou být reprezentovány pomocí 3 parametrů (x, y, θ ).
  • Pokud je robot pevným 3D tvarem, který se může překládat a otáčet, je pracovní prostor trojrozměrný, ale C je speciální euklidovská skupina SE (3) = R 3 SO (3) a konfigurace vyžaduje 6 parametrů: (x, y, z) pro překlad a Eulerovy úhly (α, β, γ).
  • Pokud je robot manipulátor s pevnou základnou s N otočnými klouby (a bez uzavřených smyček), C je N-dimenzionální.

Volný prostor

Soubor konfigurací, které zabraňují kolizi s překážkami, se nazývá volný prostor C volný . Doplněk C zdarma v C se nazývá překážková nebo zakázaná oblast.

Často je neúměrně obtížné explicitně vypočítat tvar C zdarma . Efektivní je však testování, zda je daná konfigurace v C free . Nejprve kinematika vpřed určuje polohu geometrie robota a testy detekce kolize, pokud geometrie robota koliduje s geometrií prostředí.

Cílový prostor

Cílový prostor je podprostor volného prostoru, který označuje, kam se má robot přesunout. V globálním plánování pohybu je cílový prostor pozorovatelný senzory robota. V místním plánování pohybu však robot v některých stavech nemůže pozorovat cílový prostor. Aby tento problém vyřešil, robot prochází několika virtuálními cílovými prostory, z nichž každý se nachází v pozorovatelné oblasti (kolem robota). Virtuální cílový prostor se nazývá dílčí cíl.

Překážkový prostor

Překážkový prostor je prostor, do kterého se robot nemůže přesunout. Překážkový prostor není opakem volného prostoru.

Algoritmy

Nízkorozměrné problémy lze vyřešit pomocí algoritmů založených na mřížce, které překrývají mřížku nad konfiguračním prostorem, nebo geometrických algoritmů, které vypočítávají tvar a konektivitu C free .

Přesné plánování pohybu pro vysoce dimenzionální systémy pod komplexními omezeními je výpočetně neřešitelné . Algoritmy potenciálního pole jsou účinné, ale jsou kořistí místních minim (výjimkou jsou pole harmonického potenciálu). Algoritmy založené na vzorkování se vyhýbají problémům s lokálními minimy a řeší mnoho problémů poměrně rychle. Nejsou schopni určit, že neexistuje žádná cesta, ale mají pravděpodobnost selhání, která klesá, když se tráví více času, klesá na nulu.

Algoritmy založené na vzorkování jsou v současné době považovány za nejmodernější pro plánování pohybu ve vysoce dimenzionálních prostorech a byly aplikovány na problémy, které mají desítky nebo dokonce stovky dimenzí (robotické manipulátory, biologické molekuly, animované digitální postavy a legíny roboti ).

Existuje paralelní algoritmus plánování pohybu (A1-A2) pro manipulaci s objekty (pro zachycení létajícího objektu).

Vyhledávání na základě mřížky

Přístupy založené na mřížce překrývají mřížku v konfiguračním prostoru a předpokládají, že každá konfigurace je označena bodem mřížky. V každém bodě mřížky se robot může přesunout do sousedních bodů mřížky, pokud je čára mezi nimi zcela obsažena v C free (toto je testováno s detekcí kolize). To diskretizuje sadu akcí a vyhledávací cesty (jako A* ) se používají k nalezení cesty od začátku do cíle.

Tyto přístupy vyžadují nastavení rozlišení mřížky. Hledání je rychlejší s hrubšími mřížkami, ale algoritmus nedokáže najít cesty přes úzké části C zdarma . Kromě toho počet bodů na mřížce exponenciálně roste v dimenzi konfiguračního prostoru, což je činí nevhodnými pro vysoce dimenzionální problémy.

Tradiční přístupy založené na mřížce vytvářejí cesty, jejichž změny záhlaví jsou omezeny na násobky daného základního úhlu, což často vede k neoptimálním cestám. Přístupy pro plánování cest z libovolného úhlu nacházejí kratší cesty šířením informací podél okrajů mřížky (pro rychlé vyhledávání), aniž by omezovaly jejich cesty k okrajům mřížky (pro hledání krátkých cest).

Přístupy založené na mřížce často potřebují hledat opakovaně, například když se mění znalosti robota o konfiguračním prostoru nebo se samotný konfigurační prostor během sledování cesty mění. Inkrementální heuristické vyhledávací algoritmy se rychle přeplánují pomocí zkušeností s předchozími podobnými problémy s plánováním cesty, aby se urychlilo hledání toho aktuálního.

Intervalové vyhledávání

Tyto přístupy jsou podobné přístupům k vyhledávání založeným na mřížce, kromě toho, že generují dlažbu, která místo mřížky pokrývá celý konfigurační prostor. Dlažba se rozloží na dvě dílčí dlažby X - , X + vyrobené z krabic tak, aby X - ⊂ C zdarma ⊂ X + . Charakterizace C volných částek k vyřešení nastaveného problému s inverzí . Intervalová analýza by tedy mohla být použita, pokud C free nelze popsat lineárními nerovnostmi, aby bylo zajištěno ohraničení.

Robot se tak může volně pohybovat v X - a nemůže jít mimo X + . Pro obě dílčí dlažby je vytvořen sousední graf a cesty lze najít pomocí algoritmů, jako je Dijkstra nebo A* . Když je cesta proveditelná v X - , je také proveditelná v C zdarma . Pokud v X + neexistuje žádná cesta od jedné počáteční konfigurace k cíli, máme záruku, že v C free neexistuje žádná realizovatelná cesta . Pokud jde o přístup založený na mřížce, intervalový přístup je nevhodný pro problémy s vysokými rozměry, vzhledem k tomu, že počet generovaných boxů exponenciálně roste s ohledem na rozměr konfiguračního prostoru.

Ilustraci poskytují tři obrázky vpravo, kde se háček se dvěma stupni volnosti musí pohybovat zleva doprava, přičemž se vyhýbá dvěma horizontálním malým segmentům.

Pohyb z počáteční konfigurace (modrá) do konečné konfigurace háku, vyhýbání se dvěma překážkám (červené segmenty). Levý dolní roh háčku musí zůstat na vodorovné čáře, což činí háček dvěma stupni volnosti.
Rozklad s rámečky pokrývajícími konfigurační prostor: Podkladová dlažba X - je sjednocením všech červených polí a dílčí dlažba X + je spojením červených a zelených políček. Dráha odpovídá pohybu znázorněnému výše.
Tento obrázek odpovídá stejné cestě jako výše, ale je získán s mnohem menším počtem políček. Algoritmus se vyhýbá půlení polí v částech konfiguračního prostoru, které nemají vliv na konečný výsledek.

Rozklad pomocí dílčích dlažeb pomocí intervalové analýzy také umožňuje charakterizovat topologii C free , například počítat její počet připojených komponent.

Geometrické algoritmy

Namiřte roboty mezi polygonální překážky

Překládání předmětů mezi překážkami

Hledání cesty ven z budovy

  • nejvzdálenější paprsková stopa

Vzhledem k tomu, že svazek paprsků kolem aktuální polohy je přičítán jejich délce dopadající na zeď, robot se pohybuje směrem k nejdelšímu paprsku, pokud nejsou identifikovány dveře. Takový algoritmus byl použit pro modelování nouzových východů z budov.

Pole umělého potenciálu

Jedním z přístupů je považovat konfiguraci robota za bod v potenciálním poli, který kombinuje přitažlivost k cíli a odpuzování od překážek. Výsledná trajektorie je vydána jako dráha. Tento přístup má výhody v tom, že trajektorie je vytvářena s malým výpočtem. Mohou se však zachytit v lokálních minimech potenciálního pole a nepodaří se jim najít cestu, nebo mohou najít neoptimální cestu. Pole umělého potenciálu lze považovat za rovnice kontinua podobné polím elektrostatického potenciálu (zacházení s robotem jako bodový náboj), nebo pohyb polem lze diskretizovat pomocí sady lingvistických pravidel. Navigační funkce nebo funkce pravděpodobnostní Navigation jsou druhy umělých možných funkcí, které mají kvalitu nemají minimální body s výjimkou cílového bodu.

Algoritmy založené na vzorkování

Algoritmy založené na vzorkování představují konfigurační prostor s plánem vzorkovaných konfigurací. Základní algoritmus vzorkuje N konfigurací v C a ponechává ty v C volně použitelné jako milníky . Poté je vytvořen plán, který spojuje dva milníky P a Q, pokud je úsečka PQ zcela v C volná . Detekce kolizí se opět používá k testování zahrnutí do C free . Chcete -li najít cestu, která spojuje S a G, jsou přidány do plánu. Pokud cesta v plánu spojuje S a G, plánovač uspěje a vrátí tuto cestu. Pokud ne, důvod není definitivní: buď v C free neexistuje žádná cesta , nebo plánovač nevyzkoušel dostatek milníků.

Tyto algoritmy fungují dobře pro vysoce dimenzionální konfigurační prostory, protože na rozdíl od kombinatorických algoritmů jejich doba běhu není (výslovně) exponenciálně závislá na rozměru C. Jejich implementace je také (obecně) podstatně jednodušší. Jsou pravděpodobnostně úplné, což znamená, že pravděpodobnost, že vytvoří řešení, se blíží 1, protože se tráví více času. Nemohou však určit, zda neexistuje žádné řešení.

Vzhledem k základním podmínkám viditelnosti na C free bylo prokázáno, že jak roste počet konfigurací N, pravděpodobnost, že výše uvedený algoritmus najde řešení, se exponenciálně blíží 1. Viditelnost není výslovně závislá na dimenzi C; je možné mít vysoce dimenzionální prostor s „dobrou“ viditelností nebo nízko dimenzionální prostor s „špatnou“ viditelností. Experimentální úspěch metod založených na vzorcích naznačuje, že většina běžně viděných prostorů má dobrou viditelnost.

Existuje mnoho variant tohoto základního schématu:

  • Obvykle je mnohem rychlejší testovat pouze segmenty mezi blízkými páry milníků, spíše než všechny páry.
  • Nerovnoměrné distribuce vzorkování se pokoušejí umístit více milníků do oblastí, které zlepšují konektivitu plánu.
  • Kvazirandomové vzorky typicky produkují lepší pokrytí konfiguračního prostoru než pseudonáhodné , i když některé nedávné práce tvrdí, že účinek zdroje náhodnosti je minimální ve srovnání s účinkem distribuce vzorkování.
  • Využívá místní vzorkování prováděním náhodné procházky směrovým řetězcem Markovského řetězce Monte Carlo s nějakou místní distribucí návrhů.
  • Je možné podstatně snížit počet milníků potřebných k vyřešení daného problému tím, že povolíte zakřivené oční mířidla (například plazením po překážkách, které blokují cestu mezi dvěma milníky).
  • Pokud je potřeba pouze jeden nebo několik plánovacích dotazů, není vždy nutné sestavit plán celého prostoru. Varianty pěstování stromů jsou v tomto případě obvykle rychlejší (plánování jedním dotazem). Plány jsou stále užitečné, pokud má být na stejném prostoru zadáno mnoho dotazů (plánování více dotazů)

Seznam pozoruhodných algoritmů

Úplnost a výkon

Plánovač pohybu je prý úplný, pokud plánovač v konečném čase buď vytvoří řešení, nebo správně nahlásí, že žádné neexistuje. Většina úplných algoritmů je založena na geometrii. Výkonnost kompletního plánovače se posuzuje podle jeho výpočetní náročnosti . Při matematickém dokazování této vlastnosti je třeba zajistit, aby se to stalo v konečném čase a ne pouze v asymptotickém limitu. To je obzvláště problematické, pokud během konkrétní prokazovací techniky dojde k nekonečným sekvencím (které konvergují pouze v omezujícím případě), od té doby se algoritmus teoreticky nikdy nezastaví. Intuitivní „triky“ (často založené na indukci) jsou obvykle mylně považovány za konvergující, což dělají pouze pro nekonečný limit. Jinými slovy, řešení existuje, ale plánovač jej nikdy nenahlásí. Tato vlastnost tedy souvisí s Turingovou úplností a ve většině případů slouží jako teoretický základ/vodítko. Plánovače založené na přístupu hrubé síly jsou vždy úplné, ale jsou realizovatelné pouze pro konečná a diskrétní nastavení.

V praxi může být ukončení algoritmu vždy zaručeno použitím čítače, který umožňuje pouze maximální počet iterací a poté se vždy zastaví s řešením nebo bez něj. U systémů v reálném čase je toho obvykle dosaženo pomocí hlídacího časovače , který proces jednoduše zabije. Hlídací pes musí být nezávislý na všech procesech (obvykle realizovaných rutinami přerušení na nízké úrovni). Asymptotický případ popsaný v předchozím odstavci však nebude tímto způsobem dosažen. Bude hlásit to nejlepší, co zatím našel (což je lepší než nic), nebo žádné, ale nemůže správně nahlásit, že žádný neexistuje. Všechny realizace včetně hlídacího psa jsou vždy neúplné (kromě toho, že všechny případy lze vyhodnotit v konečném čase).

Úplnost může být poskytnuta pouze velmi přísným důkazem matematické správnosti (často s pomocí nástrojů a metod založených na grafu) a měla by být prováděna pouze specializovanými odborníky, pokud aplikace obsahuje bezpečnostní obsah. Na druhou stranu je vyvrácení úplnosti snadné, protože stačí najít jednu nekonečnou smyčku nebo jeden špatný výsledek. Formální ověřování/správnost algoritmů je samostatným výzkumným oborem. Správné nastavení těchto testovacích případů je velmi důmyslný úkol.

Úplnost rozlišení je vlastnost, že plánovač zaručeně najde cestu, pokud je rozlišení podkladové mřížky dostatečně jemné. Většina plánovačů s úplným rozlišením je založená na mřížce nebo na intervalech. Výpočetní náročnost plánovačů řešení úplných rozlišení závisí na počtu bodů v podkladové mřížce, což je O (1/h d ), kde h je rozlišení (délka jedné strany buňky mřížky) a d je konfigurace rozměr prostoru.

Pravděpodobnostní úplnost je vlastnost, že jak se provádí více „práce“, pravděpodobnost, že plánovač nedokáže najít cestu, pokud existuje, se asymptoticky blíží nule. Několik metod založených na vzorcích je pravděpodobnostně úplných. Výkon pravděpodobnostně úplného plánovače se měří mírou konvergence. Pro praktické aplikace se obvykle používá tato vlastnost, protože umožňuje nastavit časový limit pro hlídacího psa na základě průměrného času konvergence.

Neúplní plánovači ne vždy vytvářejí proveditelnou cestu, pokud existuje (viz první odstavec). Někdy neúplní plánovači v praxi fungují dobře, protože se vždy zastaví po zaručené době a nechají převzít kontrolu nad jinými rutinami.

Problémové varianty

Pro zpracování variant tohoto základního problému bylo vyvinuto mnoho algoritmů.

Diferenciální omezení

Holonom

  • Ramena manipulátoru (s dynamikou)

Nonholonomic

  • Drony
  • Auta
  • Jednokolky
  • Letadla
  • Systémy omezené zrychlením
  • Pohybující se překážky (čas nemůže jít zpět)
  • Řízitelná jehla se zkosenou špičkou
  • Roboty s diferenciálním pohonem

Omezení optimality

Hybridní systémy

Hybridní systémy jsou systémy, které kombinují diskrétní a kontinuální chování. Příklady takových systémů jsou:

Nejistota

  • Pohybová nejistota
  • Chybějící informace
  • Aktivní snímání
  • Bezsenzorové plánování

Aplikace

Viz také

Reference

Další čtení

externí odkazy