Padvindingsproblemen

Padvindingsproblemen zijn problemen in wiskunde en robotica waarbij een agent een route vindt van een beginpositie naar een doelpositie in een omgeving met obstakels, met inachtneming van eventuele bewegingsbeperkingen. Het doel kan bestaan uit het vinden van een route met minimale lengte, minimale reistijd of een andere kostenfunctie, of eenvoudigweg een haalbare route zonder obstakels.

De omgeving wordt doorgaans gemodelleerd als een graf, waarbij knopen locaties voorstellen en randen haalbare overgangen met bijbehorende kosten representeren. In continue ruimtes wordt vaak gesproken van configuratie- of C-space, waarin obstakels en bewegingsbeperkingen worden omgezet in een meetkundige ruimte waarop planning kan plaatsvinden.

Traditionele benaderingen zijn kaartgebaseerde zoekalgoritmen zoals Dijkstra's algoritme en A, die in grafen korte paden vinden. Voor dynamische of grote ruimtes worden vaak incrementele of heuristische methoden toegepast, zoals Dijkstra/A met een heuristieke functie of D Lite voor replanning in veranderende omgevingen. Voor continue ruimtes bestaan probabilistische planningsalgoritmen zoals PRM (Probabilistische Roadmap) en RRT (Rapidly-exploring Random Tree). Daarnaast zijn kinodynamische planners en optimalisatiegebaseerde benaderingen relevant wanneer bewegingsbeperkingen niet eenvoudig in een graf kunnen worden neergelegd.

Padvindingsproblemen spelen een cruciale rol in robotica, videogames, logistieke routeplanning en autonome systemen. Belangrijke afwegingen bij padplanning zijn obstakels en grootte van de robot, bewegingsbeperkingen, kostenfuncties en de noodzaak tot realtime replanning.