Bewegingsplanning: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
uitbreiding |
uitbreiding |
||
Regel 23:
{{hoofdartikel|Configuratieruimte}}
De omgeving van een robot wordt de ''werkruimte'' (Engels: ''workspace'') genoemd, bijvoorbeeld een tweedimensionaal vlak of een driedimensionale ruimte. Om een pad te vinden wordt een [[configuratieruimte]] gebruikt, een [[Ruimte (wiskunde)|ruimte]] waarin alle mogelijke locaties en oriëntaties van de robot (of het te bewegen voorwerp) worden gerepresenteerd. Een mogelijke toestand (een locatie of oriëntatie) wordt een ''configuratie'' genoemd.
Een robot die zich over een tweedimensionaal vlak kan voortbewegen heeft bijvoorbeeld een configuratie die bestaat uit twee variabelen, ''(x, y)''. Als de robot zich ook kan ronddraaien dan bestaat de configuratie uit drie variabelen ''(x, y, θ)''. De bijbehorende configuratieruimten bestaan dus uit alle toegestane waarden voor deze variabelen. Het aantal dimensies van de configuratieruimte hangt dus af van de kenmerken van de werkruimte en van de robot.
Regel 30:
Het vinden van een pad in werkruimte ''W'' bestaat nu uit het vinden van een startconfiguratie ''s'' naar een doelconfiguratie ''g'' in ''C<sub>free</sub>'', het vrije deel van configuratieruimte ''C''.
===Algoritmen===
Er bestaan allerlei algoritmen om een pad te vinden in het toegankelijke deel van de configuratieruimte.
====Met een rooster====
Deze groep algoritmen delen ''C<sub>free</sub>'' op met een [[Rooster (meetkunde)|rooster]] en trachten een pad te vinden door van cel naar cel (of van punt naar punt) een pad te vinden. Het aantal punten [[Exponentiële groei|groeit echter exponentieel]] wanneer het aantal dimensies van de configuratieruimte groter wordt. Deze aanpak is dus niet geschikt voor configuratieruimten met hoge dimensionaliteit.
====Met sampling====
Deze groep algoritmen maakt gebruik van [[sample]]s: er worden configuraties uitgekozen (willekeurig of volgens een bepaald criterium) die als knoop worden toegevoegd aan een [[Grafentheorie|graaf]]. In deze graaf worden twee knopen met elkaar verbonden als er een (eenvoudig) pad bestaat tussen de bijbehorende configuraties. Door telkens configuraties te kiezen en deze, indien mogelijk, te verbinden met andere configuraties wordt een graaf opgebouwd die verbindingen tussen de configuraties weergeeft. Deze graaf wordt ook de ''routekaart'' (Engels: ''road map'') genoemd.
Deze routekaart dient als een snelwegnetwerk in een land waarbij men overal kan komen door eerst naar de snelweg te reizen, vervolgens via de snelweg te reizen tot een plek dicht bij de bestemming en vervolgens nog een laatste stuk om bij de bestemming te komen. Bij dit soort sampling-algoritmen kan men van een startconfiguratie naar een doelconfiguratie komen door eerst een pad te vinden naar de routekaart, vervolgens de configuraties van de routekaart te volgen en vervolgens via een pad naar de doelconfiguratie te komen. Om een pad te vinden in de routekaart kan men algoritmen als het [[A*-algoritme]] of het [[kortstepadalgoritme]] gebruiken.
Deze algoritmen werken goed voor configuratieruimten met hoge dimensionaliteit aangezien de [[Looptijd (algoritme)|looptijd van het algoritme]] niet (expliciet) afhangt van het aantal dimensies van de configuratieruimte.
Hoe meer configuraties gekozen worden, hoe groter de graaf wordt en hoe groter het deel van ''C<sub>free</sub>'' dat men kan bereiken via de routekaart (en eenvoudige paden van en naar deze routekaart). De kans dat een pad gevonden wordt, nadert 1 als er meer samples gekozen worden. Deze algoritmen kunnen niet garanderen dat een pad gevonden wordt als het bestaat: als er geen pad gevonden wordt dan kan het zijn dat het niet bestaat maar het kan ook zijn dat er niet voldoende samples gekozen zijn.
In [[computerspel]]len wordt ook gebruik gemaakt van een routekaart voor het verplaatsen van de voertuigen of personages. In dit geval worden de samples niet gekozen maar aangegeven in het [[Level (computerspel)|level]] door de [[level design]]er in de [[leveleditor]]. In deze context wordt geen gebruik gemaakt van een configuratieruimte maar alleen van een graaf met knopen die bepaalde punten in het level voorstellen. Deze punten worden ook ''waypoints'' genoemd. Een graafalgoritme wordt nu gebruikt om een pad te vinden van de ene plek naar een andere plek in het level. Om te voorkomen dat voertuigen of personages elkaar raken wordt [[botsingdetectie]] gebruikt.
====Geometrische algoritmen====
Deze groep algoritmen maakt gebruik van geometrische technieken om een pad te vinden, zoals de [[Minkowski-som]] en decomposeren in cellen van ''C<sub>free</sub>''
====Virtual force field====
{{hoofdartikel|Virtual force field-algoritme}}
Het virtual force field-algoritme creërt een krachtenveld waarbij de doelconfiguratie de robot 'aantrekt' en de objecten een repulsieve kracht uitoefenen op de robot. Op deze manier wordt de robot gestuurd naar de doelconfiguratie, indien mogelijk.
==Externe links==
| |||