Navigatiealgoritme: hoe machines hun weg vinden
Een navigatiealgoritme is een set rekenregels waarmee een computer, robot of voertuig zelfstandig een route bepaalt van punt A naar punt B. Denk aan de routeplanner in je auto of telefoon: je typt een bestemming in, en binnen een fractie van een seconde rolt daar de snelste of kortste weg uit, inclusief rekening houdend met files, wegwerkzaamheden en verkeerslichten. Achter dat ene groene lijntje op je scherm gaat een wiskundig proces schuil dat duizenden mogelijke routes tegen elkaar afweegt.
Hetzelfde principe zit achter veel meer dan alleen je navigatiesysteem in de auto. Een stofzuigerrobot die zonder tegen de bank te botsen zijn weg door de woonkamer vindt, een pakketrobot in een Amazon-magazijn die tussen duizenden stellingen door laveert, en zelfs een Mars-rover die zelfstandig over rotsachtig terrein rijdt, gebruiken allemaal varianten van navigatiealgoritmes. Het verschil zit vooral in de complexiteit: van een vaste kaart met wegen tot een wereld die het systeem al rijdend of rollend zelf in kaart moet brengen.
Wat is het precies?
In de kern lost een navigatiealgoritme een zogeheten pathfinding-probleem op: gegeven een startpunt, een doel en een omgeving met obstakels of paden, wat is de beste route? "Beste" kan daarbij van alles betekenen: kortste afstand, snelste tijd, minste energieverbruik, of veiligste weg.
De omgeving wordt eerst omgezet in een graaf: een netwerk van knooppunten (bijvoorbeeld kruispunten) verbonden door lijnen (wegen), elk met een "gewicht" zoals afstand of reistijd. Het algoritme doorzoekt dit netwerk om de goedkoopste route te vinden.
Een van de oudste en invloedrijkste oplossingen is het Dijkstra-algoritme, in 1959 gepubliceerd door de Nederlandse informaticus Edsger Dijkstra. Het onderzoekt stap voor stap alle mogelijke routes vanaf het startpunt, in volgorde van oplopende afstand, tot het de bestemming bereikt. Het is gegarandeerd correct, maar kan traag zijn omdat het weinig onderscheid maakt tussen veelbelovende en kansloze richtingen.
Daarom wordt in de praktijk vaak het A*-algoritme (uitgesproken "A-ster") gebruikt, ontwikkeld in 1968 door Peter Hart, Nils Nilsson en Bertram Raphael bij het Stanford Research Institute. A* voegt een "heuristiek" toe: een slimme schatting van hoe ver een tussenpunt nog van de bestemming af ligt, bijvoorbeeld de hemelsbrede afstand. Daardoor verkent het algoritme vooral routes die richting het doel bewegen, wat het aanzienlijk sneller maakt dan Dijkstra zonder de garantie van de beste route te verliezen.
Bij zelfrijdende voertuigen en robots komt er een extra laag bij: SLAM (Simultaneous Localization and Mapping, oftewel gelijktijdig lokaliseren en in kaart brengen). Dit is nodig omdat zo'n systeem vaak geen vooraf beschikbare plattegrond heeft. Met sensoren zoals camera's, lidar (laser-afstandmeting) of radar bouwt het voertuig tegelijkertijd een kaart van de omgeving op én bepaalt het zijn eigen positie daarin, tientallen keren per seconde. Pas op basis van die actuele kaart kan een pathfinding-algoritme zoals A* een route uitstippelen, die vervolgens continu wordt bijgewerkt zodra er nieuwe obstakels opduiken.
Wat wil men ermee bereiken?
Het overkoepelende doel is simpel te formuleren: machines in staat stellen zelfstandig, veilig en efficiënt door een omgeving te bewegen, zonder dat een mens voortdurend moet bijsturen. De concrete beloften verschillen per toepassingsgebied.
Voor consumentennavigatie draait het om tijdwinst en gemak: minder tijd in de file, minder brandstof- of energieverbruik, en routes die realtime meebewegen met de actuele verkeerssituatie. Voor autonome voertuigen is de inzet groter: de belofte is minder verkeersongevallen (het overgrote deel van ongelukken wordt veroorzaakt door menselijke fouten), meer mobiliteit voor mensen die zelf niet kunnen rijden, en efficiënter gebruik van wegcapaciteit.
In de logistiek en robotica gaat het vooral om schaal en snelheid: magazijnrobots die duizenden bestellingen per uur verwerken, of drones die pakketten afleveren zonder een menselijke piloot per vlucht. En in de ruimtevaart is autonome navigatie soms de enige optie: een Mars-rover kan niet in realtime worden bestuurd vanaf de Aarde, omdat een radiosignaal er, afhankelijk van de onderlinge afstand, tussen de 4 en 24 minuten over doet.
Voorbeelden uit de praktijk
DARPA Grand Challenge (2004-2007). Het Amerikaanse defensie-onderzoeksbureau DARPA organiseerde wedstrijden om autonome voertuignavigatie te versnellen. In 2004 haalde geen enkel voertuig de finish in de woestijn van Nevada; het team van Carnegie Mellon University kwam het verst voordat het vastliep. In 2005 won het Stanford Racing Team, onder leiding van Sebastian Thrun, met voertuig "Stanley" de wedstrijd over 212 kilometer onverhard terrein. De Urban Challenge van 2007, gehouden in een nagebouwde stadsomgeving, werd gewonnen door Carnegie Mellon met voertuig "Boss".
Waymo (voorheen Google Self-Driving Car Project). Google startte dit project in 2009, mede onder leiding van diezelfde Sebastian Thrun. In december 2016 werd het een zelfstandig bedrijf onder moederbedrijf Alphabet, met de naam Waymo. Het bedrijf combineert lidar, camera's en radar met SLAM- en pathfinding-technieken en biedt inmiddels in meerdere Amerikaanse steden een betaalde robotaxidienst zonder chauffeur aan.
Waze. Deze routeplanner-app werd in 2006 in Israël opgericht (aanvankelijk onder de naam FreeMap Israel) en gebruikt, naast klassieke routealgoritmes, ook realtime meldingen van gebruikers over files, ongelukken en flitsers om routes dynamisch aan te passen. Google nam Waze in 2013 over voor ongeveer 966 miljoen dollar.
Mars-rovers Curiosity en Perseverance. De Curiosity-rover, geland in augustus 2012, en de Perseverance-rover, geland in februari 2021, gebruiken beide een systeem genaamd AutoNav van NASA's Jet Propulsion Laboratory (JPL). Hiermee kunnen de rovers zelfstandig obstakels detecteren en een veilige route bepalen zonder dat elke meter vanaf de Aarde moet worden voorgeprogrammeerd. Perseverance beschikt over een sneller, verbeterd AutoNav-systeem dat sneller over Mars kan rijden dan zijn voorganger, doordat het onboard-computersysteem sneller camerabeelden verwerkt.
Amazon Robotics (voorheen Kiva Systems). Amazon nam het robotica-bedrijf Kiva Systems in 2012 over voor 775 miljoen dollar en hernoemde het later tot Amazon Robotics. De oranje magazijnrobots verplaatsen hele stellingen door het magazijn en gebruiken navigatiealgoritmes om botsingen te vermijden en de snelste route naar het volgende pakket te bepalen, tussen duizenden andere robots door.
Hoe ver is de techniek?
Klassieke routenavigatie voor auto's en voetgangers, zoals in Google Maps of Waze, is inmiddels volwassen technologie: betrouwbaar, wereldwijd beschikbaar en met realtime verkeersdata. De grootste vooruitgang zit hier tegenwoordig in details, zoals betere voorspellingen van reistijd of energiezuinige routes voor elektrische auto's.
Volledig autonome voertuignavigatie is aanmerkelijk minder ver. Waymo en concurrenten als Cruise (dat na veiligheidsincidenten in 2023-2024 zijn activiteiten fors terugschroefde) rijden weliswaar zonder chauffeur in afgebakende gebieden, maar worstelen nog met zeldzame, onvoorspelbare situaties: extreem weer, ongebruikelijk wegwerk of chaotisch verkeersgedrag. Tesla's "Full Self-Driving"-systeem gebruikt een andere aanpak, vooral gebaseerd op camerabeelden in plaats van lidar, en vereist in de meeste landen nog altijd voortdurend menselijk toezicht.
In de robotica is SLAM-navigatie in gecontroleerde omgevingen, zoals magazijnen en fabriekshallen, praktisch opgelost. Navigatie in open, onvoorspelbare buitenomgevingen (denk aan een bezorgrobot op een drukke stoep) blijft een actief onderzoeksgebied. In de ruimtevaart is autonome navigatie noodzaak gebleken: elke nieuwe Mars-missie verbetert het AutoNav-systeem verder, maar de rovers rijden nog altijd voorzichtig, vaak niet meer dan enkele tientallen tot honderden meters per dag.
Wie werken eraan?
Aan de commerciële kant zijn Google/Alphabet (met Waymo en Google Maps), Amazon (met Amazon Robotics), Tesla, en kaartenbedrijven als TomTom (Nederland) en HERE Technologies (voortgekomen uit Nokia, nu deels in Duits-Amerikaans eigendom) grote spelers. Ook Chinese bedrijven zoals Baidu (met zijn Apollo-platform voor autonoom rijden) en WeRide investeren fors in dit veld.
Op onderzoeksgebied lopen Amerikaanse universiteiten voorop, met name Stanford University, Carnegie Mellon University (met zijn gerenommeerde Robotics Institute) en MIT, mede dankzij hun rol in de DARPA-wedstrijden. NASA's Jet Propulsion Laboratory (JPL) in Californië is toonaangevend op het gebied van autonome navigatie in de ruimtevaart. In Europa doet het Duitse ruimtevaartinstituut DLR onderzoek naar robotnavigatie, en werken diverse Nederlandse kennisinstellingen, waaronder de TU Delft, aan onderdelen van autonome navigatiesystemen voor voertuigen en drones.