Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

Immagina di giocare a una partita ad alto rischio di nascondino, ma la persona che stai cercando sta scappando, la mappa è enorme e hai solo un paio di binocoli che diventano sfocati se il sole è troppo luminoso o il vento è troppo forte. Questa è la realtà quotidiana dei team di ricerca e soccorso che cercano di trovare escursionisti dispersi o sopravvissuti in zone colpite da disastri. Nel mondo della scienza, questo è noto come "ricerca ottimale", un puzzle in cui i computer cercano di capire il percorso migliore da seguire per non sprecare tempo prezioso. L'idea chiave qui è che il tempo è il nemico; più a lungo si cerca, più diventa difficile trovare qualcuno perché la sua posizione diventa un'ipotesi piuttosto che un fatto. Per risolvere questo problema, gli scienziati usano i "droni" (robot volanti) dotati di telecamere, ma programmare questi droni per volare il percorso perfetto è incredibilmente difficile perché i droni hanno limiti fisici: non possono girare istantaneamente, hanno una velocità massima e non possono volare per sempre.

Questo articolo presenta un nuovo e intelligente modo per insegnare ai droni come dare la caccia a bersagli in movimento, come una persona dispersa o un sopravvissuto che galleggia. Gli autori, un team di ricercatori provenienti dal Vietnam e dalla Corea, hanno creato un nuovo algoritmo chiamato "Evoluzione Differenziale basata su coordinate polari" (o PDE, per brevità). Pensatelo come un coach super intelligente che non si limita a dire al drone dove andare, ma come muovere il proprio corpo per arrivarci. Inveve di usare le coordinate standard della mappa (come "vai 10 metri a destra, poi 5 metri su"), l'algoritmo PDE parla la lingua nativa del drone: "ruota di questo angolo e vola di questa distanza". In questo modo, il drone evita di incastrarsi in vicoli ciechi o di tentare manovre impossibili. I ricercatori hanno testato questo metodo in simulazioni al computer e con un vero drone in un campo, e hanno scoperto che il PDE era più bravo a trovare il bersaglio più velocemente rispetto ad altri metodi popolari, specialmente quando il bersaglio era in movimento e l'area di ricerca era vasta.

Il Problema: La corsa contro il "Tempo d'Oro"

Nella ricerca e nel soccorso, esiste un concetto chiamato "tempo d'oro". Questa è la breve finestra temporale subito dopo che qualcuno è scomparso, in cui le possibilità di trovarlo in vita sono più alte. Man mano che il tempo scorre, le probabilità diminuiscono. Perché? Perché la persona potrebbe muoversi, il vento potrebbe spingerla o il terreno potrebbe nasconderla. I metodi di ricerca tradizionali spesso si affidano a squadre a terra o a aerei pilotati, che possono essere lenti o pericolosi. Entra in gioco il drone (UAV). I droni possono sfrecciare su terreni pericolosi e vedere cose che gli umani non possono vedere. Ma ecco il problema: se istruite un drone a volare casualmente, potrebbe mancare il bersaglio. Se gli dite di volare in una griglia perfetta, potrebbe perdere tempo volando sopra punti vuoti. L'obiettivo è trovare il percorso di volo perfetto che massimizzi la probabilità di individuare il bersaglio il più rapidamente possibile.

Il Cervello: Come "pensa" il drone

Per trovare il percorso migliore, il drone ha bisogno di un cervello capace di prevedere dove potrebbe trovarsi il bersaglio. Gli autori hanno modellato il movimento del bersaglio come un "processo di Markov". In termini semplici, questo significa che il prossimo movimento del bersaglio dipende principalmente da dove si trova in questo momento e da come si sta muovendo, non da dove si trovava un'ora fa. È come prevedere il movimento di una foglia che galleggia in un fiume; conosci la direzione della corrente, quindi puoi ipotizzare dove sarà tra pochi secondi.

Il drone deve anche sapere quanto sono buoni i suoi "occhi". Il documento utilizza un modello chiamato NVESD per calcolare la probabilità di individuare il bersaglio. Non si tratta solo di quanto sia lontano il bersaglio; si tratta della qualità dell'immagine. Se il sole è accecante o il bersaglio è piccolo e sfocato, la probabilità di vederlo scende. L'algoritmo combina queste due cose — dove il bersaglio potrebbe essere e quanto è probabile che la telecamera lo veda — per creare una "mappa di credenza" (belief map). Questa mappa è come una mappa termica dove i punti più luminosi mostrano la più alta probabilità che il bersaglio si trovi lì.

La Soluzione: Il trucco delle coordinate polari

L'innovazione centrale di questo articolo è il modo in cui il drone pianifica il suo percorso di volo. La maggior parte degli algoriti informatici usa le "coordinate cartesiane", che sono come una griglia su un foglio di carta millimetrata (valori x e y). Sebbene questo funzioni per la matematica, è terribile per i droni. Se un drone sta volando e deve curvare, un algoritmo cartesiano potrebbe calcolare un percorso che richiede al drone di ruotare in cerchio istantaneamente o di volare più velocemente di quanto il suo motore consenta. È come dire a un'auto di "muoversi 5 metri a nord e 5 metri a est" senza preoccuparsi del fatto che l'auto abbia un raggio di sterzata minimo.

Gli autori hanno proposto l'uso delle "coordinate polari" invece. Invece di dire "vai al punto (x, y)", l'algoritmo dice al drone: "Vola a questa distanza ($\rho$) con questo angolo ($\psi$)." Questo corrisponde a come si muove realmente il drone. Usando questo metodo, l'algoritmo rispetta naturalmente i limiti fisici del drone. Non può suggerire una curva troppo stretta o una velocità troppo elevata perché la matematica è costruita attorno a quei limiti fin dall'inizio.

Hanno racchiuso questa idea all'interno di un algoritmo di "Evoluzione Differenziale" (DE). La DE è un tipo di "intelligenza di sciame" che funziona come un team di esploratori. Immaginate un gruppo di escursionisti che cercano di trovare la vetta più alta in una catena montuosa avvolta dalla nebbia. Non conoscono l'intera mappa, ma condividono appunti. Se un escursionista trova un punto elevato, gli altri si muovono verso quell'area, ma provano anche direzioni leggermente diverse per vedere se possono trovare qualcosa di ancora più alto. La parte "Differenziale" significa che osservano la differenza tra la posizione di due escursionisti per decidere verso quale direzione saltare successivamente.

Gli autori hanno combinato questa intelligenza di sciame con il loro sistema di coordinate polari. Lo chiamano PDE. Nelle loro simulazioni, questo team di droni virtuali ha esplorato l'area di ricerca in modo molto più efficiente rispetto ai team che utilizzavano metodi standard.

I Risultati: Simulazioni e voli reali

I ricercatori hanno testato il loro algoritmo PDE in sei diversi scenari, che vanno da aree piccole di 600m x 600m a zone massicce di 2000m x 2000m. Hanno confrontato il PDE con altri algoritmi famosi come l'Ottimizzazione a Sciame di Particelle (PSO), gli Algoritmi Genetici (GA) e la standard Evoluzione Differenziale (DE).

Nelle simulazioni al computer, il PDE ha costantemente trovato il bersaglio con una probabilità maggiore e lo ha fatto più velocemente. Ad esempio, in uno scenario, il PDE ha raggiunto una probabilità di rilevamento di circa 0,529, mentre l'algoritmo DE standard è riuscito solo a 0,410. Il documento nota che la DE standard spesso rimaneva "intrappolata" in ottimi locali — il che significa che trovava un buon punto ma non riusciva a vedere il punto migliore perché era bloccata in un loop. Il PDE, grazie alle sue coordinate polari, è stato più bravo a uscire da questi loop e a trovare il percorso migliore globale.

Non si sono fermati solo ai giochi al computer. Hanno portato un vero drone 3DR Solo in un campo per testare la teoria. Il drone è stato programmato con il percorso PDE ed è stato fatto volare su un'area di 80m x 80m. Una persona (il bersaglio) camminava a una velocità di 1,5 m/s. Il drone ha seguito il percorso generato dall'algoritmo e il percorso effettivamente volato corrispondeva molto da vicino al piano. Il drone è riuscito a volare sopra l'area in cui si prevedeva fosse il bersaglio e la telecamera ha catturato la persona. Gli autori sottolineano che, sebbene il test nel mondo reale sia stato un successo, esso dipendeva dal fatto che il bersaglio si muovesse esattamente come previsto. In un disastro reale, le cose sono più disordinate, ma il test ha dimostrato che l'algoritamente genera percorsi che i veri droni possono effettivamente volare.

Perché è importante

L'articolo suggerisce che, parlando la lingua del drone (coordinate polari) e utilizzando una strategia di ricerca intelligente basata sul team, possiamo rendere più efficaci le operazioni di ricerca e soccorso. L'algoritmo PDE non trova solo un percorso; trova un percorso fattibile che rispetta i limiti del drone pur massimizzando la possibilità di un salvataggio. Sebbene gli autori ammettano che un singolo drone può coprire un'area limitata a causa della durata della batteria, suggeriscono che questo metodo potrebbe essere la base per una flotta di droni che lavorano insieme in futuro. Per ora, è un passo significativo verso il rendere i nostri robot volanti più intelligenti, più veloci e più utili quando ogni secondo conta.