Rörelseplanering

lågdimensionella problem kan lösas med nätbaserade algoritmer som överlagrar ett rutnät ovanpå konfigurationsutrymmet eller geometriska algoritmer som beräknar Cfree-formen och anslutningen.

exakt rörelseplanering för högdimensionella system under komplexa begränsningar är beräkningsmässigt otänkbart. Potentialfältalgoritmer är effektiva, men faller offer för lokala minima (ett undantag är de harmoniska potentiella fälten). Samplingsbaserade algoritmer undviker problemet med lokala minima och löser många problem ganska snabbt.De kan inte bestämma att ingen väg finns, men de har en sannolikhet för misslyckande som minskar till noll när mer tid spenderas.

Samplingsbaserade algoritmer anses för närvarande vara toppmoderna för rörelseplanering i högdimensionella utrymmen och har tillämpats på problem som har dussintals eller till och med hundratals dimensioner (robotmanipulatorer, biologiska molekyler, animerade digitala tecken och benrobotar).

det finns den parallella algoritmen för rörelseplanering (A1-A2) för objektmanipulation (för att fånga det flygande objektet).

Grid-based searchEdit

Grid-baserade tillvägagångssätt överlappar ett rutnät på konfigurationsutrymme och antar att varje konfiguration identifieras med en rutnätpunkt. Vid varje Nätpunkt får roboten flytta till intilliggande nätpunkter så länge linjen mellan dem är helt innesluten i Cfree (detta testas med kollisionsdetektering). Detta diskretiserar uppsättningen åtgärder, och sökalgoritmer (som A*) används för att hitta en väg från början till målet.

dessa tillvägagångssätt kräver inställning av en rutnätupplösning. Sökningen går snabbare med grovare nät, men algoritmen kommer inte att hitta vägar genom smala delar av Cfree. Dessutom växer antalet punkter på nätet exponentiellt i konfigurationsrymddimensionen, vilket gör dem olämpliga för högdimensionella problem.

traditionella nätbaserade tillvägagångssätt producerar banor vars kursändringar är begränsade till multiplar av en given basvinkel, vilket ofta resulterar i suboptimala vägar. Any-angle path planning approaches hitta kortare vägar genom att sprida information längs rutnätets kanter (för att söka snabbt) utan att begränsa sina vägar till rutnätets kanter (för att hitta korta vägar).

Gridbaserade tillvägagångssätt behöver ofta söka upprepade gånger, till exempel när robotens kunskap om konfigurationsutrymmet ändras eller själva konfigurationsutrymmet ändras under sökvägen. Inkrementella heuristiska sökalgoritmer replan snabbt genom att använda erfarenhet med tidigare liknande väg-planeringsproblem för att påskynda sitt sökande efter den nuvarande.

intervallbaserad sökningredigera

dessa tillvägagångssätt liknar gridbaserade sökmetoder förutom att de genererar en beläggning som helt täcker konfigurationsutrymmet istället för ett rutnät. Beläggnings sönderdelas i två subpavings X -, X + gjord med lådor så att X-megapixlar Cfree megapixlar X+. Karakterisera Cfree uppgår till lösa en uppsättning inversion problem. Intervallanalys kan således användas när Cfree inte kan beskrivas med linjära ojämlikheter för att få en garanterad inneslutning.

roboten får således röra sig fritt i X− och kan inte gå utanför X+. Till båda delpavingarna byggs en granndiagram och banor kan hittas med hjälp av algoritmer som Dijkstra eller A*. När en väg är möjlig i X -, Det är också möjligt i Cfree. När det inte finns någon sökväg i X + från en initial konfiguration till målet, har vi garanti för att ingen möjlig sökväg finns i Cfree. När det gäller det nätbaserade tillvägagångssättet är intervallmetoden olämplig för högdimensionella problem på grund av att antalet lådor som ska genereras växer exponentiellt med avseende på dimensionen av konfigurationsutrymmet.

en illustration tillhandahålls av de tre figurerna till höger där en krok med två frihetsgrader måste röra sig från vänster till höger och undvika två horisontella små segment.

nedbrytningen med subpavings med intervallanalys gör det också möjligt att karakterisera Cfree-topologin, såsom att räkna antalet anslutna komponenter.

geometrisk algoritmredigera

peka robotar bland polygonala hinder

• Synlighetsgraf
• cellnedbrytning

översätta objekt bland hinder

• Minkowski sum

hitta vägen ut ur en byggnad

• längst Ray Trace

med tanke på en bunt strålar runt den aktuella positionen som tillskrivs med deras längd som träffar en vägg, rör sig roboten i riktning mot den längsta strålen om inte en dörr identifieras. En sådan algoritm användes för modellering av nödutgång från byggnader.

artificiell potential fieldsEdit

en metod är att behandla robotens konfiguration som en punkt i ett potentiellt fält som kombinerar attraktion till målet, och repulsion från hinder. Den resulterande banan matas ut som banan. Detta tillvägagångssätt har fördelar genom att banan produceras med liten beräkning. De kan dock fastna i lokala minima för det potentiella fältet och misslyckas med att hitta en väg, eller kan hitta en icke-optimal väg. De artificiella potentiella fälten kan behandlas som kontinuumekvationer som liknar elektrostatiska potentiella fält (behandlar roboten som en punktladdning), eller rörelse genom fältet kan diskretiseras med hjälp av en uppsättning språkliga regler.En navigationsfunktion eller en probabilistisk Navigationsfunktion är typer av artificiella potentiella funktioner som har kvaliteten att inte ha minsta poäng utom målpunkten.

Samplingsbaserad algoritmredigera

Samplingsbaserade algoritmer representerar konfigurationsutrymmet med en färdplan för samplade konfigurationer.En grundläggande algoritm samplar n konfigurationer i C, och behåller de i Cfree att använda som milstolpar. En färdplan konstrueras sedan som förbinder två milstolpar P och Q om linjesegmentet PQ är helt i Cfree. Återigen används kollisionsdetektering för att testa inkludering i Cfree. För att hitta en väg som förbinder S och G läggs de till i färdplanen. Om en sökväg i färdplanen länkar S och G lyckas planeraren och returnerar den sökvägen. Om inte, är orsaken inte definitiv: antingen finns det ingen väg i Cfree, eller planeraren samplade inte tillräckligt med milstolpar.

dessa algoritmer fungerar bra för högdimensionella konfigurationsutrymmen, eftersom till skillnad från kombinatoriska algoritmer är deras körtid inte (explicit) exponentiellt beroende av dimensionen av C. De är också (generellt) väsentligt lättare att implementera. De är probabilistiskt kompletta, vilket innebär att sannolikheten för att de kommer att producera en lösning närmar sig 1 när mer tid spenderas. De kan dock inte avgöra om det inte finns någon lösning.

med tanke på grundläggande siktförhållanden på Cfree har det bevisats att när antalet konfigurationer N växer högre, sannolikheten att ovanstående algoritm hittar en lösning närmar sig 1 exponentiellt. Synlighet är inte uttryckligen beroende av dimensionen av C; det är möjligt att ha ETT högdimensionellt utrymme med ”god” synlighet eller ett lågdimensionellt utrymme med ”dålig” synlighet. Den experimentella framgången med provbaserade metoder antyder att de vanligaste utrymmena har god synlighet.

det finns många varianter av detta grundläggande schema:

• det är vanligtvis mycket snabbare att bara testa segment mellan närliggande par av milstolpar, snarare än alla par.
• icke-enhetliga provtagningsfördelningar försöker placera fler milstolpar i områden som förbättrar färdplanens anslutning.
• Kvasirandomprover ger vanligtvis en bättre täckning av konfigurationsutrymme än pseudorandom, även om vissa senaste arbeten hävdar att effekten av källan till slumpmässighet är minimal jämfört med effekten av provtagningsfördelningen.
• använder lokal-provtagning genom att utföra en riktad Markov kedja Monte Carlo random promenad med några lokala förslag distribution.
• det är möjligt att avsevärt minska antalet milstolpar som behövs för att lösa ett givet problem genom att tillåta böjda ögonsikt (till exempel genom att krypa på de hinder som blockerar vägen mellan två milstolpar).
• om bara en eller några få planeringsfrågor behövs är det inte alltid nödvändigt att konstruera en färdplan för hela utrymmet. Trädodlingsvarianter är vanligtvis snabbare för detta fall (planering med en fråga). Färdplaner är fortfarande användbara om många frågor ska göras på samma utrymme (planering av flera frågor)

lista över anmärkningsvärda algoritmerredigera

• A *
• D *
• snabbt utforska slumpmässigt träd
• probabilistisk färdplan