Introduzione all'ingegneria del controllo: pianificazione del percorso — A*, Dijkstra, RRT, RRT* e PRM

Spostare un robot dal punto di partenza a quello di arrivo raramente significa tracciare una linea retta. Un piano utilizzabile deve tenere conto di muri, larghezza del passaggio, ingombro del robot, limiti di sterzata, incertezza di localizzazione, mappe obsolete, persone in movimento e distanza di arresto. La pianificazione del percorso sceglie dove andare; la generazione e il controllo della traiettoria decidono come seguire quel percorso in condizioni dinamiche. Uno stack sicuro mantiene distinte queste responsabilità, pur condividendone i limiti.

Questa introduzione confronta gli algoritmi Grid Dijkstra e A con RRT, RRT e PRM in spazio continuo. Spiega l'inflazione degli ostacoli, le euristiche, il campionamento, la complessità, l'integrazione SLAM/Nav2, i controlli di implementazione e il comportamento di sicurezza indipendente. Per i livelli correlati, consultare Introduzione a Visual SLAM, Introduzione a ROS 2 e Introduzione alla fusione di sensori.

Conclusioni pratiche

• L'algoritmo di Dijkstra garantisce il percorso più breve su un grafo con pesi non negativi, ma si espande in direzioni non correlate all'obiettivo. L'algoritmo A* dirige l'espansione con un'euristica ammissibile, mantenendo la stessa ottimalità.

• L'algoritmo RRT tende a trovare rapidamente un percorso fattibile in spazi continui ad alta dimensionalità. L'algoritmo RRT* si avvicina a un percorso ottimale con l'aumentare del numero di campioni, considerando i costi aggiuntivi relativi ai vicini e al rifacimento del percorso. L'algoritmo PRM ammortizza la costruzione della roadmap su molte query in uno spazio sufficientemente statico.

• Il percorso più breve attraverso una mappa non inflazionata rappresenta un percorso di collisione per un robot con raggio, errore di localizzazione e distanza di arresto.

• Un percorso restituito non è una prova di sicurezza. L'aggiornamento della mappa, il rilevamento locale, l'errore di tracciamento, gli ostacoli dinamici, la latenza di ripianificazione e l'arresto di emergenza richiedono un trattamento indipendente.

Definire lo spazio libero prima di selezionare un algoritmo

Sia \mathcal X lo spazio degli stati, \mathcal X_{obs} lo spazio degli ostacoli e \mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs} lo spazio libero. Un percorso \sigma:[0,1]\to\mathcal X_{free} collega x_s a x_g, passando per \sigma(0)=x_s,\sigma(1)=x_g. Un robot puntiforme in 2D utilizza x=(x,y); un veicolo aggiunge direzione \theta, velocità e sterzata; un manipolatore include tutti gli angoli delle articolazioni. Semplificare lo stato riduce i costi di ricerca, ma può generare curve che il veicolo a valle non è in grado di realizzare.

L'espansione degli ostacoli trasforma un robot finito in una ricerca puntiforme espandendo gli ostacoli. Qui r_{loc} dovrebbe essere un termine di incertezza specificato, come ad esempio un raggio scelto per un livello di confidenza definito, piuttosto che un errore medio non specificato. Un minimo concettuale è

dove r_{robot} è il raggio del corpo, l'incertezza di localizzazione è rappresentata dal termine precedente e r_{safe} è il margine di tracciamento/arresto. In realtà, il margine varia in base alla risoluzione della mappa, ai punti ciechi dei sensori, alla velocità dell'oggetto in avvicinamento e alla capacità di frenata. Un margine troppo piccolo provoca una collisione; un margine troppo ampio rende impossibili i passaggi.

Ricerca a griglia: Dijkstra e A*

Per il grafo G=(V,E) con costo degli archi non negativo c(u,v)\ge0, Dijkstra risolve ripetutamente il problema. Nodo non ancora definito con il costo iniziale più basso conosciuto g(n) e rilassa i vicini. Una volta definito, il suo valore g è il più basso. Con un heap binario, una complessità rappresentativa è O((|V|+|E|)\log|V|). Garantisce la distanza più breve nel grafo ma, senza conoscenza dell'obiettivo, tende ad espandersi ampiamente.

A* ordina i nodi in base a

dove h(n) è un limite inferiore per il costo rimanente. Un'euristica ammissibile non sovrastima mai il costo rimanente reale; quindi A* rimane ottimale. La distanza di Manhattan è adatta a griglie 4-connesse, mentre la distanza euclidea o correlata a Chebyshev può essere adatta a movimenti 8-connessi. Un'euristica coerente soddisfa inoltre h(n)\le c(n,n')+h(n') e riduce la riespansione.

A* ponderato scala l'euristica di w>1 cerca un percorso fattibile più velocemente a costo dell'ottimalità. Questo può essere un compromesso operativo valido se esplicitato. Il costo del bordo può codificare non solo la lunghezza, ma anche il rischio di ostacoli gonfiati, l'altezza libera, la manovrabilità, l'energia o il terreno. L'output è quindi il costo minimo definito, non necessariamente la lunghezza geometrica minima.

Spazi continui e ad alta dimensionalità: RRT, RRT*, PRM

Le griglie fini esplodono in uno spazio di configurazione di bracci a sei giunti o in uno spazio di posa del veicolo. RRT campiona x_{rand} dallo spazio libero, trova il nodo dell'albero più vicino x_{near}, si dirige verso di esso per una distanza limitata, verifica le collisioni e aggiunge x_{new}. È probabilisticamente completo: con un numero sufficiente di campioni, la probabilità di trovare un percorso fattibile si avvicina a uno quando esiste. Non garantisce un primo percorso breve.

RRT* sceglie il genitore a costo minimo tra i vertici vicini e ricollega I nodi vicini vengono individuati tramite un nuovo vertice quando l'operazione risulta più economica. La soluzione è asintoticamente ottimale, non ottimale in termini di tempo finito; la ricerca dei nodi vicini, i test di collisione e il rifacimento delle connessioni consumano risorse computazionali. È preferibile valutare la qualità al raggiungimento della scadenza operativa piuttosto che promettere risultati "ottimali".

PRM campiona configurazioni libere e collega coppie vicine senza collisioni in una roadmap riutilizzabile. È interessante in un ambiente di fabbrica statico o in un contesto di query ripetute su bracci robotici perché la preelaborazione può essere ammortizzata. Gli ostacoli dinamici invalidano i collegamenti. I passaggi stretti sono difficili da campionare uniformemente, quindi potrebbero essere necessari campionamenti basati sui limiti degli ostacoli, sui percorsi o sulle attività.

SLAM, Nav2 e pianificazione locale

SLAM fornisce una mappa e una stima della posizione, ma un pianificatore necessita di trasformazioni allineate al timestamp e di un chiaro significato di occupazione/costo. La chiusura del ciclo o la rilocalizzazione possono spostare la posizione di un frame della mappa; continuare a seguire un vecchio percorso può essere pericoloso. È necessario integrare l'incertezza, il ripristino della localizzazione e gli eventi di aggiornamento della mappa nelle regole di ripianificazione; vedere Visual SLAM Primer.

In un'architettura ROS 2 simile a Nav2, una mappa dei costi globale e un pianificatore scelgono un percorso su larga scala, mentre una mappa dei costi locale e un controllore gestiscono gli ostacoli vicini e la velocità. Un algoritmo A* globale può selezionare un corridoio; il livello locale deve dare la precedenza, fermarsi o deviare per evitare una persona. Un livello puramente locale può rimanere intrappolato in un vicolo cieco. Definisci esplicitamente pianificatore, controllore, ripristino, frequenza di aggiornamento della mappa, scadenze e priorità. Il trasporto ROS 2 descritto in ROS 2 Primer non garantisce il funzionamento in tempo reale né la sicurezza.

Prima del dispiegamento, misura l'ingombro, inclusi il carico utile, il campo visivo dei sensori, la velocità/decelerazione massima, l'errore di localizzazione e la risoluzione della mappa. Verifica lo spazio libero effettivo in passaggi stretti. Controlla le collisioni dei percorsi pianificati rispetto al movimento continuo e alla cinematica: un percorso a griglia può effettuare svolte tra celle in modi impossibili per un sistema di trazione differenziale, un'auto o un braccio robotico.

Per gli ostacoli dinamici, misura la frequenza di rilevamento, la velocità relativa, la distanza di frenata e il tempo di ripianificazione; non continuare mai a muoverti se il pianificatore è in ritardo. Considera persone sconosciute, buche, ostacoli trasparenti e guasti ai sensori come casi di sicurezza, non come celle automaticamente libere. Rallenta, fermati o effettua il passaggio di consegne quando non esiste un percorso, il percorso locale non è sicuro, la covarianza è troppo elevata, la mappa non è aggiornata o l'errore di tracciamento supera il suo limite. L'arresto di emergenza deve funzionare indipendentemente dall'output del pianificatore.

Lista di controllo per l'implementazione e sicurezza

1. Definire lo spazio degli stati, l'ingombro, i frame, la risoluzione della mappa e il significato delle celle sconosciute.

2. Includere nell'inflazione l'errore di localizzazione, la velocità e la distanza di arresto; testare passaggi stretti reali.

3. Verificare l'ammissibilità euristica o documentare la garanzia deliberatamente attenuata.

4. Registrare la risoluzione del controllo delle collisioni, il seme casuale, la scadenza e il comportamento in caso di mancata soluzione per i pianificatori di campionamento.

5. Iniettare rilocalizzazione, modifiche alla mappa, perdita di dati dai sensori, ostacoli dinamici e ritardo di comunicazione.

6. Verificare un arresto sicuro e un percorso di log diagnosticabile per eventi di mancata rotta, mappa obsoleta e deviazione di tracciamento.

Riferimenti

• Hart, Nilsson, Raphael, 1968: A Formal Basis for A*
• LaValle: Rapidly-Exploring Random Trees
• Karaman e Frazzoli, 2011: RRT*
• Documentazione Nav2