NEAT-NC: NEAT guided Navigation Cells for Robot Path Planning

Probleemstelling

Autonome robots moeten in staat zijn om een omgeving te navigeren en obstakels te vermijden, zowel statisch als dynamisch. Dit vereist een robuuste padplanning (path planning). Traditionele deterministische methoden en zelfs geavanceerde metaheuristische algoritmen (zoals GA, PSO) en Deep Reinforcement Learning (DRL) hebben moeite met de complexiteit en onvoorspelbaarheid van dynamische omgevingen. Ze missen vaak de adaptiviteit en het vermogen om ruimtelijke relaties en tijdsafhankelijke patronen (zoals bewegende obstakels) effectief te modelleren, zoals het biologische brein dit doet.

Het paper richt zich op het verbeteren van het NEAT-algoritme (NeuroEvolution of Augmenting Topology) voor padplanning in dynamische omgevingen door biologische principes van ruimtelijke cognitie te integreren.

Methodologie: NEAT-NC

De auteurs stellen NEAT-NC voor, een algoritme dat NEAT combineert met "Navigatiecellen" (Navigation Cells) die zijn geïnspireerd op de hippocampus van het brein. Het systeem evolueert een Recurrent Neural Network (RNN) dat fungeert als een ruimtelijk geheugen.

1. Invoer-Encodering (Biologische Cellen)

In plaats van ruwe sensorgegevens te gebruiken, worden de inputs van het neurale netwerk gemodelleerd naar vier soorten biologische cellen:

• Border Cells (Randcellen): Een $3 \times 3$ rooster rondom de agent dat detecteert of er statische muren of dynamische obstakels binnen een sensorstraal $R$ aanwezig zijn. De waarden worden berekend door obstakelcoördinaten te transformeren naar het referentiekader van de agent.
• Place Cells (Plaatscellen): Een vergelijkbaar $3 \times 3$ rooster dat de relatieve positie van het doelwit (goal) ten opzichte van de agent encodeert.
• Head-Direction Cells (Hoofdrichtingscellen): Encodeert de hoek tussen de huidige oriëntatie van de agent en de richting naar het doelwit ($\Delta\theta$), weergegeven als $\sin(\Delta\theta)$ en $\cos(\Delta\theta)$.
• Speed Cell (Snelheidscel): Representeert de genormaliseerde lineaire snelheid van de agent ($v_{agent} / v_{max}$).

Deze inputs worden samengevoegd tot een inputvector die wordt verwerkt door de RNN. De recurrente structuur van de RNN stelt de agent in staat om tijdsafhankelijke informatie te onthouden, wat cruciaal is voor het voorspellen van de beweging van dynamische obstakels.

2. Genetische Operatoren

Het NEAT-algoritme evolueert de topologie en de gewichten van het neurale netwerk via selectie, kruising (crossover) en mutatie. Mutaties omvatten het toevoegen van knopen en verbindingen, evenals het aanpassen van gewichten, waardoor het netwerk complexer kan worden naarmate de omgeving complexer wordt.

3. Fitnessfunctie

De fitnessfunctie is ontworpen om efficiënte, biologisch geïnspireerde navigatie te belonen:

• Doelbereiking: Een grote beloning voor het bereiken van het doel, met een bonus voor snelle aankomst.
• Vermijding van botsingen: Een zware straf voor het raken van obstakels (wat de episode beëindigt).
• Smoothness (Rustigheid): Een straf voor te scherpe draaiingen (angular velocity), om rechte, efficiënte paden te bevorderen.
• Displacement (Verplaatsing): Een beloning gebaseerd op de projectie van de beweging in de richting van het doel.
• See Goal: Een extra beloning wanneer de agent het doel visueel "kan zien" (binnen een specifiek gebied), om de agent te helpen de juiste route te vinden in doolhoven.

Belangrijkste Bijdragen

1. Biologisch geïnspireerde Input Representatie: De eerste integratie van place cells, border cells, head-direction cells en speed cells als input voor een NEAT-gebaseerd neuroevolutie-algoritme.
2. Evolutionair Navigatiesysteem met Geheugen: Een systeem dat dynamische obstakels aankan door gebruik te maken van een RNN die de geheugenstructuren van de hippocampus simuleert.
3. Hippocampus-geïnspireerde Fitnessfunctie: Een functie die niet alleen succes belooft, maar ook efficiëntie en soepelheid van het pad optimaliseert, wat leidt tot meer natuurlijke navigatie.

Resultaten

Het algoritme werd getest in drie scenario's (van een simpel doolhof tot complexe omgevingen met dynamische obstakels) en vergeleken met:

• Vanilla NEAT: Een standaard NEAT implementatie met een feedforward netwerk.
• PPO (Proximal Policy Optimization): Een Deep Reinforcement Learning baseline.

Kernbevindingen:

• Success Rate: NEAT-NC behaalde een aanzienlijk hogere succesratio (tot 100% in complexe scenario's) vergeleken met Vanilla NEAT (47-66%) en PPO (6-63%).
• Padlengte en Efficiëntie: NEAT-NC genereerde kortere paden en had een hogere gemiddelde fitnesswaarde dan de andere methoden.
• Rekenkracht: Hoewel DRL (PPO) lange trainingstijden vereist, was NEAT-NC computatie-efficiënter dan Vanilla NEAT in termen van uitvoeringstijd per episode.
• Statistische Significantie: De resultaten werden gevalideerd met de Kruskal-Wallis test en Dunn post-hoc test. De lage p-waarden (<0.05) bevestigen dat de prestatieverbeteringen van NEAT-NC statistisch significant zijn ten opzichte van de benchmarks.

Betekenis en Conclusie

Het paper demonstreert dat het integreren van biologische principes (specifiek de werking van de hippocampus en ruimtelijke cellen) in evolutionaire algoritmen de prestaties van autonome robots in dynamische omgevingen drastisch kan verbeteren. NEAT-NC overtreft zowel traditionele evolutionaire methoden als moderne Deep Reinforcement Learning benaderingen in termen van robuustheid, succesratio en padkwaliteit.

De studie onderstreept het potentieel van "neuromorfische" of biologisch geïnspireerde benaderingen voor robotica en suggereert dat dit een veelbelovende richting is voor real-time padplanning, niet alleen voor robots maar ook voor games en andere autonome systemen. Toekomstig werk richt zich op het uitbreiden naar 3D-omgevingen en het integreren van manipulatie (grijpen) met navigatie.