Waarom is dit belangrijk?
Met pathfinding kunnen veel voertuigen en robots tegelijk een botsvrije route naar hun doel volgen, ook als hun taken elkaar overlappen. In magazijnen en op luchthavens sturen systemen zo rijdende machines die goederen of vliegtuigen verplaatsen. Medewerkers in die sectoren rekenen op die planning voor hun dagelijkse werk, maar bij grote drukte is een optimale oplossing soms te zwaar om tijdig te berekenen.
Zo werkt het in de praktijk
In computerspellen zit pathfinding in titels met bewegende objecten of NPC’s, niet-speelbare personages. Chris Crawford beschreef in 1982 hoe tanks in Tanktics vastliepen op land in U-vormige meren. Spelmakers plannen routes ook met een navigation mesh, een net van loopvlakken.
Onderzoekers zoeken snelle planning op grote kaarten met weinig processortijd. In 2004 stelden Botea en collega’s Hierarchical Path-Finding A* (HPA*) voor. HPA* deelt de kaart in clusters, zoekt een grove route en vult die per cluster aan.
In praktische reissystemen versnellen contraction hierarchies de routeberekening door het netwerk vooraf te vereenvoudigen. Bij een veranderende omgeving verfijnt Partial-Refinement A* (PRA*) alleen de eerste stappen. De rest van de route werkt het programma tijdens de uitvoering verder uit.




