1
Sommario
L’intento di questa tesi è lo sviluppo di un path planner (pianificatore di percorsi) per
robot mobili situati in un ambiente marziano o lunare. Il path planner sviluppato è basato
su A-star, algoritmo in grado di pianificare percorsi discreti a partire da un punto di start
per arrivare ad un punto di goal prescelti su una mappa. La mappe utilizzate sono delle
DEM (Digital Elevation Map), ovvero indicanti le altezze del terreno rispetto ad un
riferimento fisso.
Il path planner realizzato non è un puro e semplice pianificatore: per la scelta del percorso
non si tiene in considerazione la sola distanza dal nodo obiettivo, ma si considereranno
anche fattori come i dislivelli da superare, i fattori di pericolo e l’esposizione solare. Il
pianificatore garantisce inoltre una certa libertà di scelta sulla tipologia di pianificazione da
effettuare fornendo la possibilità all’utente di variare il grado di autonomia assegnata al
sistema (concetto di Sliding Autonomy).
L’obiettivo della prima parte della tesi è un’analisi teorica del problema e dello stato
dell’arte sulla pianificazione discreta, in seguito si passerà alla descrizione dell’algoritmo
utilizzato.
Si sono sviluppate, a partire dal classico A-star, un certo numero di varianti dell’algoritmo
utili a diminuire i tempi di calcolo. Inoltre ci si è concentrati sulla generazione di percorsi
che prediligano caratteristiche differenti (ad es. assetti attesi, traversabilità di un terreno,
ecc.), consentendoci quindi di ottenere più percorsi che, a partire da un punto di partenza
fisso, raggiungano lo stesso punto obiettivo.
Successivamente si descriveranno dei metodi di analisi focalizzati sui percorsi ottenuti. In
primis verranno presentati i dati che possono essere estrapolati da un percorso e che lo
caratterizzano (lunghezza, consumi, grafici sugli assetti, ecc.). In seguito verranno illustrati
metodi di validazione statica dei path per l’introduzione di perturbazioni nei percorsi
individuati. Metodi che permettono la verifica di fattibilità del path in condizioni
d’incertezza in modo da individuare eventuali pericolosità.
In appendice alla tesi vi è inoltre uno studio sulla valutazione dell’esposizione solare su
Marte utile a determinare l’illuminazione delle celle solari a bordo del rover.
Capitolo 2 - Definizione del problema e stato dell’arte
11
2.3. Pianificazione discreta
La pianificazione che vogliamo ottenere, come già detto, è una pianificazione di alto
livello. Le informazioni a nostra disposizione sono quelle che un ipotetico satellite può
fornire, ovvero una DEM (Digital Elevetion Map) della zona limitrofe alla posizione del
rover. Non abbiamo ulteriori informazioni forniteci dai sensori a bordo del rover.
Per questo motivo possiamo fare l’ipotesi che gli stati assumibili dal sistema siano finiti e
numerabili, di conseguenza è possibile utilizzare algoritmi di pianificazione discreta. Non
sono necessari modelli geometrici o equazioni differenziali per descrivere il problema e
tantomeno vengono considerati problemi di incertezza.
Il risultato restituito dal pianificatore sarà un elenco di punti componenti un ipotetico
tracciato da percorrere. Non si otterrà un percorso continuo, ma una sequenza di azioni che
spostino il robot tra i punti appartenenti alla DEM. Per approfondimenti sulla
pianificazione discreta vedere [1] e [4].
2.3.1. Formulazione del problema
Si può rappresentare ogni singolo stato raggiungibile dal sistema con e l’insieme di tutti
gli stati con . Per passare da uno stato all’altro è necessario applicare un azione
rappresentata dalla funzione . Possiamo quindi esprimere il passaggio dallo stato x allo
stato successivo
nel modo seguente:
Per ogni stato esiste un determinato numero di azioni applicabili rappresentabile come
U(x). Tale insieme non è detto che sia differente da quello di un secondo stato
in quanto
le stesse azioni possono essere applicate a più di uno stato. Lo stato di partenza è
mentre quello desiderato, ovvero quello di arrivo, con
. Alcuni algoritmi accettano
più di un nodo possibile di arrivo.
L’obiettivo del planning è trovare una determinata sequenza di azioni che applicate allo
stato iniziale portino il sistema nello stato finale.
I problemi di ricerca sono spesso formulati in termini di alberi (o più generalmente di
grafi). Ogni nodo rappresenta uno stato del sistema, dove il nodo iniziale è la radice
dell’albero e il nodo goal una delle foglie. Le azioni sono rappresentate dagli archi
connettenti due nodi. Ogni nodo può essere classificato secondo la sua profondità, ovvero
il numero di nodi che occorre attraversare dallo stato di partenza per raggiungerlo.
Capitolo 2 - Definizione del problema e stato dell’arte
12
Nel caso specifico di nostro interesse possiamo supporre che il robot si muova su una
griglia, ogni punto di questa griglia è individuabile da coordinate intere nella forma .
Il robot compie passi discreti in una della 8 direzioni, incrementando o decrementando le
due coordinate (avanti, avanti-sinistra, sinistra, indietro-sinistra, indietro, indietro-destra,
destra, avanti-destra).
Un requisito importante per gli algoritmi di ricerca è che siano sistematici. Se così non
fosse si rischierebbe di incorrere in cicli che impedirebbero di trovare una soluzione al
problema.
2.4. Algoritmi di ricerca in avanti
Gli algoritmi di ricerca in avanti (forward) mirano alla costruzione di un percorso a partire
dal nodo di partenza avvicinandosi, fino a raggiungere, il nodo di arrivo. Durante lo
svolgimento dell’algoritmo, possiamo suddividere gli stati in 3 categorie:
non visitati: tutti i nodi non ancora visitati. Inizialmente questo insieme comprende
tutti gli stati del sistema ad eccezione del nodo di partenza;
aperti (o vivi): nodi già visitati e quindi già raggiunti dalla ricerca ma i cui nodi
adiacenti non sono ancora stati tutti visitati;
chiusi (o morti): nodi già visitati i cui vicini sono stati tutti visitati.
I nodi aperti sono memorizzati in una coda prioritaria che chiameremo Open. Ciò che
distingue i vari algoritmi è la funzione utilizzata per ordinare questa lista di nodi. Di
seguito riporto un pseudo codice rappresentante uno schema generale per un algoritmo di
ricerca in avanti.
G
S
Profondità = 0
Profondità = 1
Profondità = 2
Profondità = 3
Figura 2-2: Un esempio di albero (grafo) per un problema di ricerca di
percorso, con indicazione sui rispettivi livelli di profondità.
Capitolo 2 - Definizione del problema e stato dell’arte
13
RICERCA_IN_AVANTI
Open.insert(x
s
)
Mark x
s
as visited
while (Open not empty) do
x = Open.GetFirst()
if (x == x
g
)
return SUCCESS
forall u in U(x)
x
i
= f(x,u)
if x
i
not visited
Mark x
i
as visited
Open.insert(x
i
)
else
resolve duplicate x
i
return FAILURE
Per semplicità possiamo inizialmente assumere la lista Open come una coda FIFO (First In
First Out). Un ciclo esegue continuamente il corpo del programma fino a quando vi è
almeno un elemento all’interno della lista dei nodi Open. Ad ogni iterazione viene
prelevato un elemento dalla lista Open, se questo corrisponde al nodo
l’algoritmo ha
trovato una soluzione è termina con successo. Al contrario, se la lista è vuota e non si è
individuata una soluzione e l’algoritmo restituisce come risultato fallimento. Come si può
evincere dallo pseudocodice (Codice 1) occorre tener traccia dei nodi visitati. Vi sono
molteplici strutture dati che possono assolvere questo compito, come tabelle di hash,
alberi, matrici, ecc.. A seconda del tipo di problema si andrà a scegliere la struttura più
adatta a tale rappresentazione.
Alcuni algoritmi necessitano il calcolo di uno, o più, costi da associare ad ogni stato. Se
uno nodo è raggiunto più di una volta da percorsi differenti, il costo deve essere
aggiornato. Questo costo può essere usato, mediante una qualche euristica, per ordinare la
lista dei nodi Open. Solitamente tali costi devono avere la proprietà di monotonicità: man
mano che ci si avvicina al risultato desiderato il costo deve aumentare e mai diminuire.
Tale accorgimento evita il crearsi di fastidiosi cicli.
Possiamo dare una visione unificata del generico funzionamento degli algoritmi di ricerca
in avanti:
1. Inizializzazione: vengono inizializzate le strutture dati ed inserita nella lista Open
il nodo di partenza;
2. Selezione di un vertice: selezione di un vertice da espandere (secondo una qualche
euristica) dalla lista Open;
3. Applicare un azione: selezione di un azione in modo da generare un nuovo stato;
Codice 1: Pseudo codice di un generico algoritmo di ricerca in avanti trato da [1].
Capitolo 2 - Definizione del problema e stato dell’arte
14
4. Inserire un arco di congiunzione sull’albero di ricerca: generazione di un arco di
congiunzione tra il nodo corrente ed il nuovo nodo trovato. Se il nodo non è
presente nella lista dei nodi Open verrà inserito;
5. Controllare la soluzione: si verifica se il nodo trovato corrisponde al nodo goal. In
caso affermativo l’algoritmo termina con successo;
6. Ritornare a 2: itera l’algoritmo fin quando non si trova una soluzione. Quando la
lista Open risulta essere vuota l’algoritmo termina restituendo fallimento.
2.5. Ricerca indietro e ricerca bilaterale
Vi sono altre tecniche di ricerca, che non sono algoritmi in avanti, più o meno performanti
a seconda dei problemi analizzati.
Come è facilmente intuibile un primo approccio può essere quello di ribaltare il problema,
partire dal nodo goal per cercare una strada verso il nodo di partenza, una ricerca
all’indietro (backward). Gli algoritmi applicabili a tale scopo sono i medesimi del caso in
avanti. Ovviamente gli obiettivi da cercare saranno invertiti, i nodi goal diventeranno di
start e viceversa. Algoritmi di questo genere possono essere vantaggiosi in termini di tempi
di ricerca, ma le performance variano da problema a problema.
Un altro approccio è quello della ricerca bilaterale (bidirectional), ovvero un unione tra
ricerca in avanti e ricerca all’indietro. Due alberi di ricerca vengono creati, uno con radice
il nodo iniziale e uno con radice il nodo finale. La ricerca termina con successo non
appena i due alberi si incontrano, ovvero non appena si identifica un nodo in comune. Si
possono creare versioni della maggior parte degli algoritmi che analizzeremo in seguito per
sfruttare la ricerca bidirezionale. Nel caso si utilizzino algoritmi di ricerca ottimi il risultato
ottenuto è l’unione di due percorsi ottimi, generando un path globale teoricamente sub-
ottimo, a vantaggio di tempi di ricerca inferiori.
2.6. Algoritmi di pianificazione discreta
Riportiamo di seguito alcuni dei più famosi algoritmi di ricerca discreta. Esistono molte
varianti ai casi proposti, frequentemente queste nascono dalla fusione di 2 approcci ad
algoritmi differenti.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.