Mozgástervezés

az alacsony dimenziós problémák megoldhatók rácsalapú algoritmusokkal, amelyek rácsot fednek le a konfigurációs tér tetején, vagy geometriai algoritmusokkal, amelyek kiszámítják a Cfree alakját és összekapcsolhatóságát.

a nagy dimenziós rendszerek pontos mozgástervezése összetett korlátok mellett számítási szempontból megoldhatatlan. A potenciális mező algoritmusok hatékonyak, de a helyi minimumok áldozatává válnak (kivétel a harmonikus potenciális mezők). A mintavételezésen alapuló algoritmusok elkerülik a helyi minimumok problémáját, és sok problémát elég gyorsan megoldanak.Nem tudják megállapítani, hogy nincs út, de a kudarc valószínűsége nullára csökken, mivel több időt töltenek.

a mintavételezésen alapuló algoritmusokat jelenleg a legmodernebb mozgástervezésnek tekintik a nagy dimenziós terekben, és több tucat vagy akár több száz dimenzióval rendelkező problémákra alkalmazták (robot manipulátorok, biológiai molekulák, animált digitális karakterek és lábú robotok).

létezik a mozgástervezési párhuzamos algoritmus (A1-A2) az objektumok manipulálásához (a repülő tárgy elfogásához).

Grid-based searchEdit

Grid-based megközelítések átfedik a rácsot a konfigurációs térben, és feltételezik, hogy minden konfiguráció egy rácsponttal van azonosítva. Minden rácspontnál a robot a szomszédos rácspontokra mozoghat, mindaddig, amíg a köztük lévő vonal teljesen a Cfree-n belül van (ezt ütközésérzékeléssel tesztelik). Ez diszkretizálja a műveletek halmazát, és keresési algoritmusokat (például a*) használnak, hogy megtalálják az utat a kezdetektől a célig.

ezek a megközelítések rácsfelbontás beállítását igénylik. A keresés durvább rácsokkal gyorsabb, de az algoritmus nem fogja megtalálni az utakat a Cfree szűk részein keresztül. Ezenkívül a rácson lévő pontok száma exponenciálisan növekszik a konfigurációs tér dimenziójában, ami alkalmatlanná teszi őket nagy dimenziós problémákra.

a hagyományos rácsalapú megközelítések olyan útvonalakat eredményeznek, amelyek irányváltozása egy adott alapszög többszörösére korlátozódik, gyakran nem optimális útvonalakat eredményezve. Bármely szögű útvonaltervezési megközelítések rövidebb utakat találnak azáltal, hogy információkat terjesztenek a rács élek mentén (a gyors kereséshez) anélkül, hogy korlátoznák útjukat a rács széleire (rövid utak megtalálásához).

a rácsalapú megközelítéseknek gyakran ismételten keresniük kell, például amikor a robot tudása megváltozik a konfigurációs térről, vagy maga a konfigurációs tér megváltozik az útvonal követése során. Az inkrementális heurisztikus keresési algoritmusok gyorsan újratervezik a korábbi hasonló útvonaltervezési problémák tapasztalatait, hogy felgyorsítsák a jelenlegi keresést.

Intervallumalapú keresésszerkeszt

ezek a megközelítések hasonlóak a rácsalapú Keresési megközelítésekhez, azzal a különbséggel, hogy a rács helyett teljes egészében a konfigurációs helyet fedik le. A burkolatot két X−,X + alborításra bontják, olyan dobozokkal, hogy X-6cfree ~ X+. A Cfree leírása egy meghatározott inverziós probléma megoldására szolgál. Az intervallumanalízist tehát akkor lehet alkalmazni, ha a Cfree nem írható le lineáris egyenlőtlenségekkel annak érdekében, hogy garantált legyen a burkolat.

a robot így szabadon mozoghat az X− – ben, és nem mehet ki az X+ – on kívülre. Mindkét alpavinghez egy szomszédos gráf épül fel, és az útvonalak megtalálhatók olyan algoritmusok segítségével, mint a Dijkstra vagy az A*. Ha egy út megvalósítható X− ben, akkor a Cfree-ben is megvalósítható. Ha nincs útvonal az X+ – ban az egyik kezdeti konfigurációtól a célig, akkor garantáljuk, hogy a Cfree-ben nincs megvalósítható út. Ami a rácsalapú megközelítést illeti, az intervallum megközelítés nem megfelelő nagy dimenziós problémák esetén, mivel a létrehozandó dobozok száma exponenciálisan növekszik a konfigurációs tér dimenziójához képest.

illusztrációt nyújt a jobb oldali három ábra, ahol a két szabadságfokú horognak balról jobbra kell mozognia, elkerülve két vízszintes kis szegmenst.

az intervallumanalízissel végzett subpavingekkel történő bomlás lehetővé teszi a Cfree topológiájának jellemzését is, például a csatlakoztatott komponensek számának megszámlálását.

Geometriai algoritmusokszerkesztés

Pontrobotok a sokszögű akadályok között

• láthatósági grafikon
• Sejtbontás

objektumok fordítása az akadályok között

• Minkowski összeg

megtalálni a kiutat egy épületből

• legtávolabbi sugárnyaláb nyom

mivel a sugarak egy kötegét veszik körül az aktuális pozíció körül, amelynek hossza falnak ütközik, a robot a leghosszabb sugár irányába mozog, hacsak nem azonosítanak ajtót. Egy ilyen algoritmust használtak az épületekből történő vészkijárat modellezésére.

mesterséges potenciálmezők

az egyik megközelítés az, hogy a robot konfigurációját úgy kezeljük, mint egy pontot egy potenciális mezőben, amely egyesíti a célhoz való vonzódást és az akadályoktól való taszítást. A kapott pálya kimenetként jelenik meg. Ennek a megközelítésnek előnyei vannak abban, hogy a pályát kevés számítással állítják elő. Azonban csapdába eshetnek a potenciális mező helyi minimumaiban, és nem találnak utat, vagy találhatnak egy nem optimális utat. A mesterséges potenciálmezők úgy kezelhetők kontinuum egyenletek hasonló elektrosztatikus potenciálmezők (a robotot ponttöltésként kezelik), vagy a mezőn keresztüli mozgás diszkretizálható egy sor nyelvi szabály segítségével.A navigációs funkció vagy a valószínűségi navigációs funkció olyan mesterséges potenciális funkciók, amelyek minősége nem rendelkezik minimális pontokkal, kivéve a célpontot.

Sampling-based algorithmsEdit

a Sampling-based algoritmusok a konfigurációs teret képviselik a mintavételezett konfigurációk ütemtervével.Egy alap algoritmus mintákat n konfigurációk C, és megtartja azokat Cfree használni, mint mérföldkövek. Ezután elkészül egy útiterv, amely két P és Q mérföldkövet kapcsol össze, ha a PQ vonalszakasz teljesen Cfree-ben van. Ismét az ütközésérzékelést használják a Cfree-be való felvétel tesztelésére. Az S-t és G-T összekötő útvonal megtalálásához hozzáadódnak az ütemtervhez. Ha az útiterv egyik útvonala összekapcsolja az S – t és a G-t, a tervező sikerrel jár, és visszaadja azt az utat. Ha nem, az ok nem végleges: vagy nincs út a Cfree-ben, vagy a tervező nem vett mintát elegendő mérföldkövekből.

ezek az algoritmusok jól működnek a nagy dimenziós konfigurációs tereknél, mert a kombinatorikus algoritmusokkal ellentétben futási idejük (kifejezetten) nem függ exponenciálisan a C dimenziójától. Valószínűség szerint teljesek, vagyis annak valószínűsége, hogy megoldást fognak előállítani, megközelíti az 1-et, mivel több időt töltenek. Nem tudják azonban meghatározni, hogy nincs-e megoldás.

tekintettel a Cfree alapvető láthatósági feltételeire, bebizonyosodott, hogy az n konfigurációk számának növekedésével annak valószínűsége, hogy a fenti algoritmus megoldást talál, exponenciálisan megközelíti az 1-et. A láthatóság nem függ kifejezetten a C dimenziójától; lehetséges egy nagy dimenziós tér “jó” láthatósággal vagy egy alacsony dimenziós tér “rossz” láthatósággal. A mintaalapú módszerek kísérleti sikere azt sugallja, hogy a leggyakrabban látott terek jól láthatók.

ennek az alaprendszernek számos változata létezik:

• általában sokkal gyorsabb, ha csak a közeli mérföldkövek közötti szegmenseket teszteljük, nem pedig az összes párot.
• a nem egységes mintavételi disztribúciók további mérföldköveket próbálnak elhelyezni azokon a területeken, amelyek javítják az ütemterv összekapcsolhatóságát.
• a Kvazirandom minták általában jobban lefedik a konfigurációs teret, mint az álvéletlenségek, bár néhány újabb munka azt állítja, hogy a véletlenszerűség forrásának hatása minimális a mintavételi Eloszlás hatásához képest.
• helyi mintavételt alkalmaz egy irányított Markov lánc Monte Carlo véletlenszerű séta végrehajtásával, néhány helyi javaslat terjesztésével.
• egy adott probléma megoldásához szükséges mérföldkövek számát jelentősen csökkenteni lehet ívelt szemlátomások engedélyezésével (például a két mérföldkő közötti utat elzáró akadályokon való mászással).
• ha csak egy vagy néhány tervezési lekérdezésre van szükség, nem mindig szükséges a teljes tér ütemtervének elkészítése. A fa-termesztési változatok általában gyorsabbak ebben az esetben (egy lekérdezéses tervezés). Az ütemtervek továbbra is hasznosak, ha sok lekérdezést kell végrehajtani ugyanazon a téren (több lekérdezés tervezése)

nevezetes algoritmusok listájaSzerkesztés

• A *
• D *
• gyorsfeltáró véletlenszerű fa
• valószínűségi ütemterv