Di seguito un semplice esempio di creazione del secondo grafo.
Figura 62: Grafo 1
Figura 63: Grafo 2
Come si può vedere in g. 62 e g. 63 nel secondo grafo i pedici dei nodi indicano il genitore del nodo nel grafo 1. Quindi per esempio il nodo 2 in G1 ha una stella entrante di dimensione
2, i nodi entranti sono 1 e 3, allora in G2 si avranno due nodi: 21 e 23. Gli archi invece vengono
denominati come gli angoli, dove ad esempio (4, 1, 2)◦è l'angolo che in G
1porta dall'arco 4-1 all'arco
1-2. Applicando questo stesso procedimento a tutti i nodi e archi di G1 si ottiene G2.
7.4 Applicazione su mrfert
Si è quindi provato ad applicare tale idea al nostro caso speci co. Bisogna ricordare che il nostro codice è strutturato su due livelli come spiegato in 5.3( g. 19): la parte di piani cazione e la parte di comunicazione con gli altri agenti e di controllo.
Viene sottolineata questa distinzione perché l'utilizzo del grafo è dierente sui due livelli. Nella parte di comunicazione e controllo è possibile lavorare direttamente sul grafo originale, questo perché essa riceve dal livello sottostante la traiettoria (sequenza di nodi con i rispettivi tempi) e questa viene utilizzata sfruttando le coordinate spaziali. Quindi siamo in una situazione di spazio reale dove ogni nodo è unico (un punto sul piano) e si hanno strade (archi) unici che collegano, ognuno, due punti distinti (nodi).
Al livello di piani cazione invece si trova l'algoritmo di ricerca del cammino minimo sul grafo vero e proprio. Tale grafo non deve avere necessariamente una connotazione sica quindi è stato possibile utilizzare il grafo ampliato. Durante la creazione del secondo grafo sono stati fatti degli accorgimenti: - i nodi duplicati hanno le stesse coordinate del nodo originale (queste sono necessarie per il calcolo della distanza tra nodi), ciò esempli ca perfettamente come questo grafo si discosti dalla realtà sica. Avere più nodi con le stesse coordinate non crea problemi perchè, per come è stato concepito l'ampliamento, questi non potranno mai essere collegati tra di loro, cioè non ci sarà mai un arco a distanza nulla.
- il costo di rotazione non viene aggiunto per il primo motion cioè per il passaggio dal nodo iniziale a quello successivo in quanto l'agente non ha eettuato nessuna rotazione dall'arco di provenienza (non esistente).
7.4.1 Test
Per veri care, a questo punto, che l'algoritmo funzioni anche con il grafo ampliato e che l'aggiunta del costo di rotazione alla funzione di costo possa indurre a una diversa scelta di traiettoria, si è immaginato un semplicissimo scenario ( g. 64)
.
Figura 64: Scenario con due possibili strade
In tale scenario l'agente, che parte da nodo 0 e deve raggiungere il nodo 4, ha due possibili strade percorribili: il tragitto 1 (in rosso) è la strada evidentemente più corta ma con angoli più stretti che quindi necessitano di una rotazione maggiore, il tragitto 2 (in blu) è più lungo ma con costo di rotazione inferiore.
Si sono fatte quindi due diverse prove: nella prima, facendo riferimento all'eq.(13), si è posto µ = 0 in modo da eliminare il costo di rotazione dal computo del costo totale; in altre parole si è utilizzata la funzione di costo originaria. Tenendo conto che l'agente è da solo sulla mappa, esso potrà sfrut- tare la massima velocità senza eventuali rallentamenti dovuti ad altri veicoli. Ci si aspetta quindi che la piani cazione scelga il tragitto 1 che è evidentemente il più corto. Realizzando quindi una simulazione il risultato è proprio quello previsto ( g. 65).
Figura 65: Scelta del tragitto 1
Quando invece si inizia ad aumentare µ e quindi a tenere conto anche del costo di rotazione si ottengono risultati dierenti. Considerando quindi il parametro µ come un coe ciente di pe- so il cui aumento indica una via via maggiore importanza assegnata alla rotazione, nella seconda prova lo si è posto pari a σ = 100. Si ottiene che in questo caso il costo totale del tragitto 2 risul- ta minore di quello del tragitto 1 e l'agente tende a sceglierlo proprio come ci si aspetterebbe( g. 66).
Può essere interessante osservare le velocità del robot nei due casi ( g. 67):
(a) Velocità lineare
(b) Velocità angolare
Figura 67
Si può vedere come il tragitto 1 (caso 1 in gura) sia evidentemente più breve infatti il robot raggiunge il suo obiettivo circa 5 s più velocemente, ma evidentemente necessità di maggiore velocità angolare (b).
7.5 Osservazioni
Quanto visto in questo capitolo si può considerare come una analisi preliminare su come inserire il costo di rotazione nella ricerca su grafo del cammino minimo. Come già accennato andando sem- plicemente ad ampliare il grafo si riesce a non modi care l'algoritmo di ricerca. Può però sorgere il problema della dimensione del nuovo grafo.
Nell'esempio di g. 63 abbiamo visto che l'ampliamento ha portato a:
dim(N1) = 7 ⇒ dim(N2) = 11
dim(E1) = 11 ⇒ dim(E2) = 16
Il numero di nodi nale dipende dalla quantità di archi (come detto in 7.2 si considerano le varie stelle entranti dei nodi). In particolare vale che:
dim(N2) = dim(E1) + γ (16)
dove γ è il numero di nodi in G1che non hanno una stella entrante.
Si evince che la dimensione del nuovo grafo è direttamente legata al grado di connettività del grafo iniziale. Si può quindi assumere che per capire se vi sia o meno la possibilità di applicare questo metodo bisogna studiare caso per caso. L'aspetto problematico potrebbe essere che l'agente non riesca a completare la piani cazione nei limiti temporali imposti (TA). Ove possibile, in caso di
necessità, si potrebbe aumentare il tempo assegnato per la piani cazione, in tal caso bisogna però ricordarsi di veri care i rapporti tra tale tempo, la velocità massima e la distanza minima tra i nodi (5.1).
Un altro aspetto da tenere in considerazione è il signi cato da attribuire a µ. Tale valore può essere considerato, come fatto nora, un coe ciente di peso al pari di hte hc nell'eq.6. Sarà quindi neces-
sario eettuare un tuning basato sulle caratteristiche del veicolo e sul problema speci co.
Un'altra possibilità ci viene presentata in [14]. Qui si suppone che il tempo di trasferimento del robot da un nodo ad un altro sia composto da due tempi distinti: tM tempo di avanzamento e tR
tempo di rotazione. t = tM + tR (17) dove si assume: tM(ni, nj) = dist(ni, nj) ¯ v tM(ni, nj) = θ(nj) − θ(ni) ¯ ω
in cui in particolare ¯ω è la velocità angolare media la cui scelta anche in questo caso dipende dalle caratteristiche dell'agente nello scenario in questione. Scegliere questa strada però imporrebbe ulteriori modi che dell'algoritmo, bisognerebbe infatti riuscire ad incorporare il tempo di rotazione nel campionamento del tempo di arrivo sul nodo.
8 Conclusioni
Nel presente lavoro è stato proposto un nuovo approccio per la coordinazione di multi robot in mo- dalità distribuita utilizzando un modello spazio-tempo ibrido. Tale approccio permette di generare cammini liberi da collisioni sfruttando la possibilità di aggiustare la velocità e di realizzare nuove piani cazioni in base alla dinamica del sistema. L'introduzione della con gurazione treno permette, tra le altre cose, di evitare tamponamenti (scontri lungo gli archi del grafo). Inoltre la formazione dei treni riesce a gestire particolari situazioni di congestione del tra co in prossimità degli incroci favorendo lo svuotamento delle strade con molti veicoli in coda.
Sono state realizzate diverse simulazioni per determinare la bontà dell'approccio proposto e i migliori scenari per la sua applicazione. Si è osservato che una condizione necessaria per l'applicabilità di tale metodo è che il grafo rispetti particolari condizioni spaziali (distanze tra nodi, etc...). Per questo uno spunto per lavori futuri potrebbe essere cercare di modellare anche lo spazio in modo continuo (e non discreto come fatto no ad ora).
In ne è stato proposto un metodo per introdurre il costo di rotazione nella valutazione del tragitto migliore da percorrere che va a modi care il grafo originario all'interno dell'algoritmo di piani ca- zione. Tale metodo può essere sviluppato più dettagliatamente nel caso di utilizzo di veicoli dalla dinamica più complessa.
A APPENDICE
Di seguito le tabelle contenenti i dati delle simulazioni della con gurazione treno nel caso in cui gli agenti non abbiano tutti la stessa velocità massima come anticipato in 6.4.
CASO 1
(a) Agente 1 (b) Agente 2
(c) Agente 3 (d) Agente 4
(e) Agente 5 (f) Agente 6
CASO 2
(a) Agente 1 (b) Agente 2
(c) Agente 3 (d) Agente 4
(e) Agente 5 (f) Agente 6
CASO 3
(a) Agente 1 (b) Agente 2
(c) Agente 3 (d) Agente 4
(e) Agente 5 (f) Agente 6
CASO 4
(a) Agente 1 (b) Agente 2
(c) Agente 3 (d) Agente 4
(e) Agente 5 (f) Agente 6
Bibliogra a
[1] M. Bennewitz, W. Burgard e S Thrun. Optimizing Schedules for Prioritized Path Planning of Multi-Robot Systems. In: In Proceedings of ICRA'02 (2002).
[2] Y. Cao et al. An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination. In: IEEE Transaction on Industrial Informatics (2013).
[3] V. Digani et al. Towards Decentralized Coordination of Multi Robot Systems in Industrial Environments: a Hierarchical Tra c Control Strategy. In: 2013 IEEE 9th International Con- ference on Intelligent Computer Communication and Processing (ICCP) (2013).
[4] M. Ferrati e L Pallottino. A time expanded network based algorithm for safe and e cient distributed multi-agent coordination. In: Decision and Control (CDC) (2013).
[5] M. Ferrati et al. Distributed Trajectory Planning for Mobile Robots in Space-Time Graph. 2016. [6] J. Huang et al. An Overview of Distributed High-order Multi-agent Coordination. In: IEEE/CAA
Journal of automatica sinica (2014).
[7] L. Janson et al. Fast marching tree: A fast marchingsampling-based method for optimal motion planning in many dimensions. In: The International Journal of Robotics Research (2015).
[8] L. Kavraki, M. Kolountzakis e J Latombe. Analysis of Probabilistic Roadmaps for Path Planning. In: International Journal of Advanced Robotic Systems (1996).
[9] A. Khaliq, F. Pecora e A Sa otti. Inexpensive, Reliable and Localization-free Navigation using an RFID Floor. In: 2015 European Conference on Mobile Robots (ECMR) (2015). [10] S LaValle. Rapidly-exploring random trees: A new tool for path planning. In: Technical
Report TR 98-11 (1998).
[11] L. Pallottino. Dispense per il corso di Robotica: Sistemi Robotici Distribuiti. 2014. [12] B. Siciliano et al. Robotica: Modellistica, piani cazione e controllo. McGraw Hill, 2008. [13] T. Siméon, S. Leroy e J Laumond. Path Coordination for Multiple Mobile Robots: A Resolution-
Complete Algorithm. In: IEEE Transaction on Robotics and Automation (2002).
[14] P. ˇSkrabanek, M Mariˇska e P Doleˇzel. The time optimal path-planning of mobile robots motion respecting the time cost of rotation. In: International Conference on Process Control (2015).
[15] K. Wurm, C. Stachniss e W Burgard. Coordinated multi-robot exploration using a segmen- tation of the environment. In: n Proceedings of IROS'08 (2008).
[16] Z. Yan, N. Jouandeau e A Cherif. A Survey and Analysis of Multi-Robot Coordination. In: International Journal of Advanced Robotic Systems (2013).