🤖 AI

HiRAD: A Flexible Large-Scale AGV Routing System

Dit artikel introduceert HiRAD, een hiërarchisch reinforcement learning-framework dat de schaalbaarheids- en realtime-beperkingen van klassieke en bestaande RL-gebaseerde AGV-routingsystemen overwint door gebruik te maken van continuüm-ruimte-representaties, een gedecoupleerde controlestrategie en een asynchrone event-gestuurde pipeline om de maaktijd en inferentielatentie aanzienlijk te verminderen.

Oorspronkelijke auteurs: Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law, Lei Li

Gepubliceerd 2026-09-10

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law, Lei Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de enorme, zoemende magazijnen die de moderne e-commerce aandrijven, zoeven duizenden kleine, autonome voertuigen over de vloer om pakketten van opslagplanken naar pakstations te vervoeren. Deze machines, bekend als automated guided vehicles, zijn de stille werkpaarden van de wereldwijde logistiek, in staat om dagelijks miljarden artikelen te verplaatsen. Het laten samenwerken zonder botsingen is echter een probleem dat ingenieurs al lang voor een raadsel stelt. Traditionele methoden behandelen de magazijnvloer als een gigantisch schaakbord, waarbij voertuigen van vakje naar vakje springen in rigide, instant stappen. Hoewel dit de wiskunde vereenvoudigt, negeert het de realiteit van de fysica: echte voertuigen kunnen niet direct stoppen, noch kunnen ze op een stuivertje draaien. Ze hebben ruimte nodig om op te trekken, af te remmen en te sturen. Wanneer software deze fysieke beperkingen negeert, botsen de voertuigen vaak in de echte wereld, of doet de computer er zo lang over om een veilig pad te berekenen dat de voertuigen stilstaan terwijl ze wachten op instructies. Deze kloof tussen de geïdealiseerde digitale kaart en de rommelige, continue beweging van echte machines heeft het moeilijk gemaakt om grote vloten van deze robots efficiënt in te zetten.

Een team van onderzoekers heeft deze kloof nu overbrugd met een nieuw systeem genaamd HiRAD, ontworpen om massale groepen van deze voertuigen in real time door complexe magazijnen te leiden. In plaats van de robots te dwingen te doen alsof ze tussen rastervakjes springen, hebben de onderzoekers een model gebouwd dat de continue stroom van beweging respecteert. Ze realiseerden zich dat om beslissingen snel genoeg te nemen voor honderden gelijktijdig bewegende voertuigen, het systeem moest stoppen met proberen elke kleine detail tegelijkertijd te controleren. Hun oplossing houdt in dat de rijtaak wordt opgesplitst in twee afzonderlijke lagen. De eerste laag fungeert als een navigator op hoog niveau, die naar een brede, vereenvoudigde kaart kijkt om te bepalen in welke algemene richting een voertuig moet gaan. De tweede laag is een lokale controller die de eigenlijke fysica afhandelt, waarbij wordt beheerd hoe het voertuig versnelt, kruist en remt om die richting soepel te bereiken. Door het "waarheen gaan" te scheiden van het "hoe te bewegen", vermindert het systeem drastisch het aantal berekeningen dat het op enig moment moet uitvoeren.

De onderzoekers testten deze aanpak in simulaties met tot wel tweeduizend voertuigen die zich over verschillende magazijnlay-outs bewogen. Ze ontdekten dat hun systeem taken aanzienlijk sneller kon voltooien dan eerdere methoden, waarbij de totale tijd die nodig is om een batch bestellingen af te ronden in sommige scenario's met bijna de helft werd verminderd. Cruciaal was dat het systeem de veiligheid handhaafde zonder snelheid op te offeren; het voorkwam botsingen, zelfs wanneer voertuigen met hoge snelheden bewogen en door nauwe ruimtes navigeerden. In tegen tegenstelling tot oudere systemen die zouden bevriezen en alles opnieuw zouden berekenen als één enkel voertuig een vertraging opliep, staat dit nieuwe framework de rest van de vloot in staat om door te gaan met bewegen, waarbij alleen de specifieke voertuigen die bij het conflict betrokken zijn worden aangepast. Deze flexibiliteit betekent dat het systeem onverwachte haperingen kan afhandelen, zoals een voertuig dat vertraagt of een tijdelijke blokkade, zonder de gehele operatie tot stilstand te brengen.

Om ervoor te zorgen dat het systeem snel genoeg kon draaien voor echt gebruik, introduceerde het team een methode van asynchrone besluitvorming. In een traditionele opstelling zou elk voertuig wachten tot de computer zijn pad heeft gecontroleerd tegenover elk ander voertuig voordat het beweegt, een proces dat onmogelijk traag wordt naarmate de vloot groeit. Het nieuwe systeem slaat deze controles over voor voertuigen die al soepel bewegen, en pauzeert pas om complexe beslissingen te nemen wanneer een voertuig moet stoppen of van richting moet veranderen. Deze optimalisatie verminderde de computationele belasting zo effectief dat de tijd die nodig is om een beslissing te nemen korter werd dan de tijd die een voertuig nodig heeft om fysiek te bewegen. Het resultaat is een systeem dat grootschalige vloten met dezelfde gemak kan beheren als een kleine, wat bewijst dat het mogelijk is om de aanpasbaarheid van kunstmatige intelligentie te combineren met de strikte natuurwetten die de real-world machines beheersen.

De studie onderzocht ook hoe de kunstmatige intelligentie die de navigatie op hoog niveau aanstuurt, getraind kon worden. De onderzoekers ontdekten dat het de AI trainen op eenvoudige, lege kaarten niet genoeg was; de AI moest leren op kaarten gevuld met obstakels en variërende niveaus van moeilijkheid om goed te kunnen generaliseren. Door de complexiteit van de trainingsomgeving geleidelijk te vergroten, leerde het systeem efficiënte paden te vinden, zelfs in drukke, chaotische magazijnen. Bij tests tegen andere vooraanstaande methoden presteerde de nieuwe aanpak consequent beter in zowel snelheid als betrouwbaarheid. Terwijl andere systemen moeite hadden om meer dan een paar honderd voertuigen te verwerken of faalden wanneer de omgeving veranderde, schaalde dit framework naadloos op naar duizenden agenten. De bevindingen suggereren dat de toekomst van magazijnautomatisering niet ligt in rigide, vooraf geplande routes, maar in flexibele, continue systemen die kunnen reageren op de wereld zoals deze zich daadwerkelijk beweegt.

Technische Samenvatting: HiRAD: Een Flexibel Grootschalig AGV-Routing Systeem

1. Probleemstelling

Het artikel behandelt de uitdaging van het routeren van grootschalige vloten van Automated Guided Vehicles (AGV's) in realistische magazijnomgevingen. Hoewel AGV's cruciaal zijn voor moderne logistiek, kampen bestaande routingoplossingen met een fundamentele afruil tussen flexibiliteit (aanpassen aan dynamische veranderingen en defecten) en kinematische beperkingen (het naleven van fysieke bewegingswetten in een continue ruimte).

Klassieke Multi-Agent Pathfinding (MAPF): Solvers zoals CBS of ODrM* lijden onder een exploderende combinatorische complexiteit en een superkwadratische runtime. Ze vertrouwen vaak op geïdealiseerde rooster- of stuksgewijs lineaire bewegingsmodellen die er niet in slagen de realistische kinematica te vatten, wat potentieel kan leiden tot botsingen in continue omgevingen.
Reinforcement Learning (RL) Benaderingen: Recente gedecentraliseerde RL-oplossingen bieden flexibiliteit, maar hebben moeite met schaalbaarheid en realisme. Ze zijn doorgaans afhankelijk van gediscretiseerde spatiotemporele representaties, vereisen miljoenen trainingsepisoden en veroorzaken hoge inferentielatentie door volledige kaartobservaties bij elke stap. Dit schendt vaak de real-time industriële besturingsbeperkingen.
De Kernkloof: Er is een gebrek aan een systeem dat gelijktijdig grootschalige vloten, continue kinematische beperkingen en real-time besluitvorming ondersteunt zonder in te boeten op veiligheid of efficiëntie.

2. Methodologie: Het HiRAD-framework

De auteurs stellen HiRAD voor (High-Resolution and Hierarchical Routing with Asynchronous Decision Framework), een hiërarchisch RL-framework dat is ontworpen om de kloof tussen discrete RL-algoritmen en continue fysieke uitvoering te overbruggen. Het framework bestaat uit drie kerncomponenten:

A. High-Resolution Spatiotemporal (HRS) Modellering

Om de stap-gebaseerde aard van RL te verzoenen met continue beweging, introduceert HiRAD een high-resolution modelleringsbenadering:

HR-Map: Het ruimtelijke rooster wordt onderverdeeld in kleinere cellen (bijv. $c \times c$ ), wat een fijnere ruimtelijke resolutie creëert.
HR-Step: Tijdintervallen worden verdeeld in kleinere stappen ( $\Delta t$ ), waardoor AGV's beslissingen kunnen nemen met een hogere temporele resolutie.
Velocity Integratie: In tegenstelling tot standaard MAPF waarbij agenten één rooster per stap bewegen, associeert HRS elke stap met een scalaire snelheid. Dit maakt het modelleren van acceleratie, constante snelheid en deceleratie mogelijk, waardoor continue dynamiek effectief wordt gesimuleerd binnen een discreet RL-framework.

B. Hierarchical Alternating Decision-Velocity Control (Alt-DVC)

Om de complexiteit van de uitgebreide actieruimte te beheren, ontkoppelt HiRAD navigatie in twee lagen:

Macro-RL-Routing Laag: Werkt op een grof roosterkaart. Het gebruikt een getraind single-agent beleid (hergebruikt voor de vloot) om botsingsvrije richtingen uit te voeren. Het behandelt andere AGV's als dynamische obstakels binnen gedefinieerde "Exclusion Zones" (een gebied van 5 grids rondom een AGV) om botsingen proactief te voorkomen.
Micro Velocity-Control Laag: Werkt op de fijnmazige HR-Map. Het voert veilige, continue bewegingen uit door de macro-richting te mappen naar vooraf gedefinieerde snelheidsmodi (bijv. Bewegen naar Volgende Grid, Continu Cruisen, Decelereren tot Stoppen). Deze modi volgen een driefasig profiel: Acceleratie $\to$ (Max) Snelheid $\to$ Deceleratie, wat ervoor zorgt dat AGV's precies in het midden van de grids stoppen.

Botsingsresolutie: Het systeem hanteert prioriteitsplanning gebaseerd op snelheid en obstakelendichtheid. AGV's met een hogere prioriteit gaan door, terwijl AGV's met een lagere prioriteit de exclusion zones van agenten met een hogere prioriteit als obstakels behandelen en stoppen voordat ze deze betreden.

C. Asynchronous Decision-Velocity Control (Asy-DVC)

Om de latentie-bottleneck aan te pakken waarbij de besluitvormingstijd de fysieke uitvoeringstijd overschrijdt, introduceert HiRAD een asynchrone optimalisatie:

Observatie Pruning: Omdat kinematische beperkingen onmiddellijke koerswijzigingen verhinderen, slaat het systeem de macro-policy inferentie over voor AGV's die al in beweging zijn. Inferentie wordt alleen getriggerd wanneer een AGV stationair is ( $v=0$ ) en moet heroriënteren. Dit vermindert de observatiecomplexiteit van $O(n)$ naar ongeveer $O(n/4)$ .
Map-Oriented Priority: In plaats van pairwise botsingscontroles uit te voeren tussen alle AGV's ( $O(n^2)$ ), gebruikt het systeem een grid-geïndexeerde prioriteitsstructuur op de grove kaart. Een AGV controleert alleen de agent met de hoogste prioriteit in zijn bestemmingsgrid, waardoor de complexiteit van prioriteitsafhandeling wordt teruggebracht van $O(n^2)$ naar $O(n)$ .
Resultaat: Deze optimalisatie verlaagt de totale inferentiecomplexiteit van $O(n^2)$ naar $O(n)$ , waardoor de per-stap latentie met wel 71% wordt verminderd.

3. Belangrijkste Bijdragen

Het artikel claimt de volgende bijdragen:

HiRAD Framework: Een nieuw systeem dat grootschalige, botsingsvrije AGV-routing in kinematisch beperkte omgevingen mogelijk maakt met real-time garanties.
High-Resolution Spatiotemporal Model: Een aanpassing van stap-gebaseerde RL voor continue omgevingen door integratie van fijnmazige ruimtelijke cellen en snelheidsstatussen.
Hierarchical Control (Alt-DVC): Een ontkoppelde strategie die richting- en snelheidsbeslissingen scheidt om de zoekruimte te verkleinen en botsingsvermijding af te dwingen via exclusion zones en prioriteitsplanning.
Asynchronous Optimization (Asy-DVC): Een methode die gebruikmaakt van observatie pruning en map-oriented priority om de besluitvormingscomplexiteit van kwadratisch naar lineair te reduceren, wat real-world implementatie mogelijk maakt.
Empirische Validatie: Uitgebreide experimenten die superieure prestaties aantonen ten opzichte van state-of-the-art oplossingen.

4. Experimentele Resultaten

De auteurs evalueerden HiRAD op willekeurige grafen en twee real-world magazijnlay-outs (Layout-A en Layout-B) met vlootgroottes variërend van 64 tot 2.048 AGV's.

Schaalbaarheid: Klassieke methoden (ICBS, ODrM*) faalden om resultaten te leveren voor vloten groter dan 64 AGV's. PRIMAL (een grootschalige RL-baseline) kon tot 2.048 AGV's aan, maar leed onder hoge latentie en verminderde succespercentages in dichte scenario's. HiRAD slaagde erin te schalen naar 2.048 AGV's.
Efficiëntie (Makespan): HiRAD verminderde de makespan (tijd voor de laatste agent om het doel te bereiken) met 45%–63% vergeleken met de baselines. Op een kaart van grootte 40 was HiRAD 3–4 keer sneller dan PRIMAL; op grootte 160 was het ongeveer 2 keer sneller.
Runtime: HiRAD behaalde aanzienlijk lagere end-to-end runtime vergeleken met zowel klassieke als andere RL-gebaseerde methoden, waarmee aan real-time beperkingen werd voldaan.
Flexibiliteit: In "lifelong" taaksimulaties met dynamische defecten (bijv. 10% van de AGV's die problemen ondervinden), behield HiRAD zijn prestaties zonder systeembrede herplanning. In contrast hiermee vereisten gecentraliseerde planners zoals OHSMD het stilleggen en herplannen van de gehele vloot, wat leidde tot aanzienlijke vertragingen.
Training: Het gebruik van curriculum learning (beginnen met kleine, obstakelvrije kaarten en de moeilijkheid geleidelijk verhogen) en Invalid Action Masking (IAM) verbeterde de convergentiesnelheid en succespercentages op grote, complexe kaarten aanzienlijk.

5. Betekenis en Claims

Het artikel positioneert HiRAD als een brug tussen theoretische RL-gebaseerde routing en praktische industriële toepassing. De auteurs beweren dat:

Eerdere oplossingen onpraktisch waren vanwege ofwel discrete aannames (die kinematische beperkingen schenden) ofwel gecentraliseerde planning (die een gebrek aan flexibiliteit vertoont).
HiRAD de eerste RL-gebaseerde oplossing is die grootschalige vloten (tot 2.048 agenten) ondersteunt, terwijl strikt aan kinematische beperkingen wordt voldaan en botsingsvrije operaties in een continue ruimte worden gegarandeerd.
De asynchrone optimalisatie (Asy-DVC) cruciaal is voor real-time toepasbaarheid, door te garanderen dat de beslissingslatentie korter is dan de fysieke uitvoeringstijd.
Het systeem een robuuste, aanpasbare oplossing biedt voor lifelong multi-AGV pathfinding in dynamische magazijnomgevingen, waarbij het state-of-the-art methoden overtreft in zowel efficiëntie als schaalbaarheid.