Bewegingsplanning

Laagdimensionale problemen kunnen worden opgelost met rastergebaseerde algoritmen die een raster bovenop de configuratieruimte leggen, of geometrische algoritmen die de vorm en connectiviteit van Cfree berekenen.

exacte bewegingsplanning voor hoogdimensionale systemen onder complexe beperkingen is rekenkundig onhandelbaar. Potentiaal-veld algoritmen zijn efficiënt, maar vallen ten prooi aan lokale minima (een uitzondering is de harmonische potentiele velden). Sampling-gebaseerde algoritmen vermijden het probleem van lokale minima en lossen veel problemen vrij snel op.Ze zijn niet in staat om vast te stellen dat er geen pad bestaat, maar ze hebben een kans op mislukking die afneemt tot nul als meer tijd wordt besteed.

Sampling-based algoritmes worden momenteel beschouwd als state-of-the-art voor bewegingsplanning in hoogdimensionale ruimtes, en zijn toegepast op problemen met tientallen of zelfs honderden dimensies (robotmanipulatoren, biologische moleculen, geanimeerde digitale karakters en robots met benen).

er is het parallelle algoritme voor bewegingsplanning (A1-A2) voor manipulatie van objecten (voor het vangen van het vliegende object).

rastergebaseerde zoekopdracht

Rastergebaseerde benaderingen overlappen een raster op configuratieruimte, en veronderstellen dat elke configuratie wordt geïdentificeerd met een rasterpunt. Op elk rasterpunt mag de robot naar aangrenzende rasterpunten bewegen zolang de lijn ertussen volledig binnen Cfree is (dit wordt getest met botsingsdetectie). Dit maakt de reeks acties discreet, en zoekalgoritmen (zoals een*) worden gebruikt om een pad te vinden van het begin tot het doel.

deze benaderingen vereisen het instellen van een rasterresolutie. Zoeken is sneller met grovere grids, maar het algoritme zal er niet in slagen om paden te vinden door smalle delen van Cfree. Bovendien neemt het aantal punten op het raster exponentieel toe in de configuratie-ruimtedimensie, waardoor ze ongeschikt zijn voor hoogdimensionale problemen.

traditionele rastergebaseerde benaderingen produceren paden waarvan de koerswijzigingen beperkt zijn tot veelvouden van een gegeven basishoek, wat vaak resulteert in suboptimale paden. Any-angle path planning benaderingen vinden kortere paden door informatie langs rasterranden te verspreiden (om snel te zoeken) zonder hun paden te beperken tot rasterranden (om korte paden te vinden).

Rastergebaseerde benaderingen moeten vaak herhaaldelijk zoeken, bijvoorbeeld wanneer de kennis van de robot over de configuratieruimte verandert of de configuratieruimte zelf verandert tijdens het volgen van het pad. Incrementele heuristische zoekalgoritmen replan snel met behulp van ervaring met de vorige soortgelijke pad-planning problemen te versnellen hun zoektocht naar de huidige.

Interval-based searchEdit

deze benaderingen zijn vergelijkbaar met raster-based zoekbenaderingen, behalve dat ze een bestrating genereren die volledig de configuratieruimte beslaat in plaats van een raster. De bestrating wordt ontbonden in twee subpavings X -, X + gemaakt met dozen zodanig dat X-cf Cfrree ⊂ X+. Het karakteriseren van Cfree bedraagt om een bepaald inversieprobleem op te lossen. De intervalanalyse zou aldus kunnen worden gebruikt wanneer Cfree niet door lineaire ongelijkheden kan worden beschreven om een gewaarborgde bijlage te hebben.

de robot mag zich dus vrij bewegen in X− en mag niet buiten X+gaan. Voor beide subpavings wordt een buurgrafiek gebouwd en kunnen paden worden gevonden met behulp van algoritmen zoals Dijkstra of een*. Wanneer een pad haalbaar is in X -, is het ook haalbaar in Cfree. Als er geen pad bestaat in X+ van de ene initiële configuratie naar het doel, hebben we de garantie dat er geen haalbaar pad bestaat in Cfree. Wat de rastergebaseerde benadering betreft, is de intervalbenadering niet geschikt voor hoogdimensionale problemen, omdat het aantal te genereren dozen exponentieel groeit ten opzichte van de dimensie van de configuratieruimte.

een illustratie wordt gegeven door de drie figuren rechts waar een haak met twee vrijheidsgraden van links naar rechts moet bewegen, waarbij twee horizontale kleine segmenten moeten worden vermeden.

de ontleding met subpavings die intervalanalyse gebruiken maakt het ook mogelijk om de topologie van Cfree zoals het tellen van zijn Aantal verbonden componenten te karakteriseren.

Geometrische algorithmsEdit

Punt robots onder veelhoekige obstakels

• Zichtbaarheid grafiek
• Cel afbraak

Vertalen van objecten onder obstakels

• Minkowski-som

het Vinden van de uitweg van een gebouw

• verst ray trace

Gegeven een bundel van stralen rond de huidige positie wordt toegeschreven die met hun lengte van het raken van een muur, de robot beweegt in de richting van de langste ray tenzij een deur is geïdentificeerd. Een dergelijk algoritme werd gebruikt voor het modelleren van nooduitgang uit gebouwen.

Artificial potential fieldsEdit

een benadering is om de configuratie van de robot te behandelen als een punt in een potentiaal veld dat aantrekking tot het doel combineert met afstoting van obstakels. Het resulterende traject wordt uitgevoerd als het pad. Deze aanpak heeft voordelen in die zin dat het traject wordt geproduceerd met weinig berekening. Ze kunnen echter gevangen raken in lokale minima van het potentiële veld en er niet in slagen een pad te vinden, of kunnen een niet-optimaal pad vinden. De kunstmatige potentiaalvelden kunnen worden behandeld als continuümvergelijkingen vergelijkbaar met elektrostatische potentiaalvelden (het behandelen van de robot als een puntlading), of beweging door het veld kan worden discreet gemaakt met behulp van een set van linguïstische regels.Een navigatiefunctie of een probabilistische navigatiefunctie zijn soorten kunstmatige potentiële functies die de kwaliteit hebben dat ze geen minimumpunten hebben, behalve het doelpunt.

Sampling-based algorithmsEdit

Sampling-based algorithms representeren de configuratieruimte met een routekaart van bemonsterde configuraties.Een basisalgoritme samples n configuraties in C, en behoudt die in Cfree te gebruiken als mijlpalen. Een roadmap wordt dan gebouwd die twee mijlpalen P en Q verbindt als het lijnsegment PQ volledig in Cfre is. Opnieuw, wordt de botsingsopsporing gebruikt om opneming in Cfree te testen. Om een pad te vinden dat S en G verbindt, worden ze toegevoegd aan de routekaart. Als een pad in de roadmap links S en G, de planner slaagt, en geeft dat pad. Zo niet, dan is de reden niet definitief: of er is geen pad in Cfree, of de planner heeft niet genoeg mijlpalen bemonsterd.

deze algoritmen werken goed voor hoogdimensionale configuratieruimtes, omdat in tegenstelling tot combinatorische algoritmen hun looptijd niet (expliciet) exponentieel afhankelijk is van de dimensie van C. Ze zijn ook (over het algemeen) aanzienlijk gemakkelijker te implementeren. Ze zijn probabilistisch compleet, wat betekent dat de kans dat ze een oplossing zal produceren benadert 1 als meer tijd wordt besteed. Ze kunnen echter niet bepalen of er geen oplossing bestaat.

gegeven de basis zichtbaarheidsomstandigheden op Cfree, is bewezen dat naarmate het aantal configuraties N groter wordt, de kans dat het bovenstaande algoritme een oplossing vindt exponentieel 1 benadert. Zichtbaarheid is niet expliciet afhankelijk van de dimensie van C; Het is mogelijk om een hoogdimensionale ruimte met “goed” zicht of een laagdimensionale ruimte met “slecht” zicht te hebben. Het experimentele succes van op monsters gebaseerde methoden suggereert dat de meest voorkomende ruimtes goed zichtbaar zijn.

er zijn vele varianten van dit basisschema:

• het is doorgaans veel sneller om alleen segmenten te testen tussen nabijgelegen paren van mijlpalen, in plaats van alle paren.
• nonuniform sampling distributies proberen meer mijlpalen te plaatsen in gebieden die de connectiviteit van de roadmap verbeteren.Quasirandom-samples produceren doorgaans een betere afdekking van configuratieruimte dan pseudorandom-samples, hoewel recent werk stelt dat het effect van de bron van willekeur minimaal is in vergelijking met het effect van de samplingdistributie.
• maakt gebruik van lokale bemonstering door het uitvoeren van een directionele Markov keten Monte Carlo random walk met enige lokale voorstel distributie.
• het is mogelijk om het aantal mijlpalen dat nodig is om een bepaald probleem op te lossen aanzienlijk te verminderen door gebogen ogen toe te staan (bijvoorbeeld door over de obstakels te kruipen die de weg tussen twee mijlpalen blokkeren).
• indien slechts één of enkele planningsvragen nodig zijn, is het niet altijd nodig om een routekaart van de gehele ruimte op te stellen. Boom-groeiende varianten zijn meestal sneller voor dit geval (single-query planning). Roadmaps zijn nog steeds nuttig als veel query ‘ s moeten worden gemaakt op dezelfde ruimte (multi-query planning)

List of notable algorithmsEdit

• A*
• D*
• snelverkennende willekeurige boom
• probabilistische routekaart