 Trovare un percorso su una piantina
|
Creazione della piantina
|
Check-point candidati
|
Aggiunta degli archi
|
Percorso + aree di lavoro
|
Il progetto è stato ideato per risolvere un problema molto comune nel campo della robotica: tracciare un percorso
minimo fra due punti all'interno di una mappa. In particolare è stato affrontato il problema di posizionare il minor
numero di punti intermedi (check-point), sufficiente per permettere ad un robot di raggiungere un determinato
goal, cercando di rimanere il più possibile lontano dalle pareti e dagli spigoli.
Il robot potrebbe trovare degli ostacoli temporanei lungo il suo cammino (ad es. passaggio di persone) e una delle possibili
alternative è quella di variare leggermente il percorso per aggirare l'ostacolo.
Il problema che nasce da questa libertà è che se il robot si allontana troppo dalla linea retta e finisce dietro ad uno spigolo che gli oscura
la posizione del successivo check-point, potrebbe non essere in grado di ritrovare il percorso originale.
Negli algoritmi si sfrutta quindi il concetto di "area di lavoro": il robot non è obbligato a muoversi sulla linea retta che unisce
due check-point, ma può muoversi in un'area più ampia (definita matematicamente) che ovviamente non deve contenere spigoli vivi.
Il programma (sviluppato in C++) carica un file che specifica come costruire la piantina e le posizioni iniziali/finali del percorso da cercare.
Sfruttando i concetti di Voronoi e alcuni accorgimenti si riesce a costruire una mappa intermedia, costituita da tutti i possibili punti di passaggio (check point candidati),
che si trovano solitamente nella parte centrale dell'area disponibile.
A questo punto si crea un grafo con l'insieme degli archi che unisce tutti i check-point, avendo l'accortezza di scartare gli archi inutili
(gli archi che collegano due punti ai lati opposti di un muro o i percorsi la cui area di lavoro include degli spigoli).
Risulta facile a questo punto applicare un qualsiasi algoritmo di routing per trovare il percorso minimo.
Nel caso specifico è stato scelto l'ottimo algoritmo di Dijsktra, che come risultato fornisce tutti i punti intermedi per compiere il percorso voluto.
Variando il peso di ciascun arco è possibile scegliere se trovare il percorso minimo (peso proporzionale alla lunghezza dell'arco) o se ottenere il minor numero di check-point (peso uguale per tutti gli archi).
Collegamenti:
Sezione download
|
|