4. Analisi sperimentale
4.3 Metodo dei determinanti di Cayley-Menger
Questo metodo di trilaterazione è molto efficiente dal punto di vista computazionale rispetto ad entrambi i metodi precedenti, in quanto evita sia la non linearità del sistema, sia il calcolo della matrice pseudoinversa. Invece si basa su considerazioni più di tipo geometrico come viene spiegato in seguito. Nonostante questo vantaggio, va però tenuto conto anche della precisione ottenuta.
Date due sequenze di n punti [p1,…, pn] e [q1,…, qn], si definisce il bideterminante di
Cayley-Menger tra le due sequenze come
0 1 1 … 1
1 D(p1, q1) D(p1, q2) … D(p1, q2)
D(p1, ..., pn ; q1, ..., qn) = 2 (-½ )n 1 D(p2, q1) D(p2, q2) … D(p2, qn)
1 D(pn, q1) D(pn, q2) … D(pn, qn)
Dove D(pi, qi) rappresenta il quadrato della distanza euclidea tra i punti pi e qi.
D(pi, qi) = d(pi, qi)2
Siccome in molti casi di interesse (come anche in questo caso) le due sequenze di punti sono uguali, si semplifica la notazione D(p1,..., pn ; p1,..., pn) con D(p1, ..., pn) che è detto
semplicemente determinante di Cayley-Menger. In questo caso i termini sulla diagonale della matrice saranno tutti nulli.
Si nota che D(p1,..., pn) equivale a (n-1)! volte l’ipervolume compreso tra i punti (p1,..., pn)
al quadrato.
Nel caso di n = 3, chiamando con A l’area del triangolo che ha vertici nei punti [p1, p2, p3],
si ottiene che
D(p1, p2, p3) = 4A2
Allo stesso modo per n = 4, chiamando con V il volume del tetraedro con vertici nei punti [p1, p2, p3, p4], si ottiene che
Come qualsiasi altro algoritmo di trilaterazione, l’obiettivo è quello di trovare le coordinate di un punto incognito p4 date le coordinate note di 3 punti noti [p1, p2, p3] e le distanze del
punto incognito da ognuno dei punti noti [l1, l2, l3]. Nel nostro caso i punti noti sono le
posizioni delle ancore, e il punto incognito è la posizione del tag.
Figura 42: Disegno geometrico di un tetraedro. p1, p2, p3 sono i punti noti e formano il triangolo di base del tetraedro.
p4 è il punto di cui si vuole calcolare la posizione, e p è la proiezione di p4 sul triangolo di base. φijindica l’angolo del
diedro formato da due facce del tetraedro.
In Figura 42 si è indicato con p la proiezione del punto p4 sul triangolo di base, e si sono
indicate con A1, A2, A3, rispettivamente le aree dei triangoli p2p3p, p1p3p, e p1p2p.
La posizione del punto p può essere calcolata tramite nel seguente modo: p = p1 + k1 v1 + k2 v2
dove v1 è il vettore che va da p1 a p2, e v2 è il vettore che va da p1 a p3. I valori dei
Per calcolare la posizione del punto p4, bisogna muoverci anche in direzione ortogonale al
piano di base del tetraedro. Si può quindi scrivere p4 = p ±k3 (v1 x v2)
dove il segno positivo o negativo indica le due diverse soluzioni nel semispazio superiore o inferiore al piano della base. Nel nostro caso, siccome le ancore sono poste sul soffitto e il tag sarà sempre più in basso del piano della base, si sceglierà sempre la soluzione con il segno negativo.
L’espressione del coefficiente k3 è la seguente:
In conclusione, è possibile scrivere la posizione del punto p4 come
Quest’ultima formula può essere riscritta in forma matriciale nel seguente modo:
dove A, b, e c sono appropriati vettori e matrici costanti. Questa formula coincide con l’espressione di Manolakis, considerata come la formula più efficiente dal punto di vista computazionale per la trilaterazione e utilizzata nella localizzazione dei robot. Tuttavia l’espressione precedente è più semplice dal punto di vista intuitivo: infatti si nota che solamente quando D(p1, p2, p3) = 0 (ovvero quando i punti p1, p2, p3 sono allineati), la
posizione di p4 è indefinita, e solo quando D(p1, p2, p3, p4) = 0 (ovvero quando p4
appartiene allo stesso piano della base) la soluzione è unica.
Il calcolo computazionale è molto semplice in quanto si ricade sempre nel dover calcolare determinanti di matrici 4x4 o 5x5, operazione molto meno onerosa rispetto al calcolo di una matrice pseudoinversa.
4.3.1 Prestazioni per il caso di muletto fermo
Dopo aver spiegato i principi su cui si basa il metodo dei determinanti di Cayley-Menger, si implementa quest’ultimo in uno script MATLAB e si ripetono i confronti rispetto alle misure ottenute dal sistema UWB. In Figura 43 viene mostrato il risultato ottenuto nel caso di muletto fermo in un punto, che va confrontato con quello in Figura 29.
Figura 43: Posizione stimata con il metodo dei determinanti di Cayley-Menger durante alcuni secondi in cui il muletto
In Tabella 8 viene confrontata la varianza delle coordinate con metodo di Cayley-Menger rispetto alle misure l’applicazione Decawave.
Decawave Cayley-Menger Varianza X (cm2) 2.11 25.45 Varianza Y (cm2) 4.98 21.01 Varianza Z (cm2) 0.92 0* Numero di campioni 36 36 Tempo di esecuzione (ms) - 222
Tabella 8: Confronto tra la varianza del sistema Decawave e il metodo di Cayley-Menger.
Si nota che ancora gli spostamenti indesiderati sono di circa 20 cm in entrambe le coordinate. Le prestazioni in questo caso sono inferiori a quelle del sistema UWB ma paragonabili con quelle degli algoritmi visti in precedenza.
In Figura 44 viene mostrato il risultato ottenuto dopo il filtraggio
Figura 44: Posizione stimata con il metodo dei determinanti di Cayley-Menger e filtro di Kaiser durante alcuni secondi
In Tabella 9 viene confrontata la varianza delle coordinate con metodo di Cayley-Menger dopo il filtraggio rispetto alle misure l’applicazione Decawave.
Decawave Cayley-Menger con filtraggio
Varianza X (cm2) 2.11 1.06
Varianza Y (cm2) 4.98 3.81
Varianza Z (cm2) 0.92 0*
Numero di campioni 36 36
Tempo di esecuzione (ms) - 225
Tabella 9: Confronto tra la varianza del sistema Decawave e il metodo di Cayley-Menger dopo il filtraggio.
Anche in questo caso l’inserimento del filtro di Kaiser complica leggermente l’algoritmo, permettendo però di ottenere risultati molto più stabili nel calcolo del punto fisso.
Dai valori di varianza calcolati, si nota che con il metodo dei determinanti di Cayley- Menger, la varianza dei punti aumenta notevolmente rispetto alle misure del sistema UWB ed è paragonabile a quella ottenuta con il metodo fsolve. Tuttavia, è comunque inferiore a quella ottenuta con il metodo LSE riportata in Tabella 4.
L’aggiunta del filtro di Kaiser riduce di molto la varianza e lo porta a valori addirittura inferiori a quelli misurati dall’applicazione Decawave, a costo però di complicare l’algoritmo.
4.3.2 Prestazioni per il caso di traiettoria rettilinea
Dopo aver valutato la varianza della stima, si prosegue confrontando la stima della traiettoria rettilinea, come fatto coi metodi precedenti. Anche in questo caso il confronto viene fatto visivamente sovrapponendo i due grafici in Figura 45.
Figura 45: Confronto tra la traiettoria misurata tramite UWB (in blu) e la traiettoria stimata con il metodo dei
determinanti di Cayley-Menger (in rosso) per un movimento rettilineo.
Si nota che entrambe le traiettorie non sono perfettamente rettilinee, ma presentano degli spostamenti laterali inattesi di alcune decine di centimetri.
Per cercare di minimizzare questi spostamenti si aggiunge nuovamente il filtro di Kaiser e si mostra il risultato in Figura 46.
Figura 46: Confronto tra la traiettoria misurata tramite UWB (in blu) e la traiettoria stimata con il metodo dei
determinanti di Cayley-Menger e filtro di Kaiser (in rosso) per un movimento rettilineo.
Ancora una volta si nota come il filtro di Kaiser riduce notevolmente gli spostamenti indesiderati e si ottiene una traiettoria più rettilinea.
4.3.3 Prestazioni per il caso di traiettoria ad L
Come ultima prova si valuta questo metodo anche per la traiettoria ad L, e se ne confronta le prestazioni rispetto al sistema UWB in Figura 47.
Figura 47: Confronto tra la traiettoria misurata tramite UWB (in blu) e la traiettoria stimata con il metodo dei
determinanti di Cayley-Menger (in rosso) per un movimento ad L.
In questo caso si vede che entrambe le traiettorie presentano degli spostamenti laterali inattesi, e risulta ancora difficile capire quale delle due sia migliore.
In Figura 48 si mostra di nuovo il confronto dopo aver applicato il solito filtro di Kaiser.
Figura 48: Confronto tra la traiettoria misurata tramite UWB (in blu) e la traiettoria stimata con il metodo dei
determinanti di Cayley-Menger con filtro di Kaiser (in rosso) per un movimento ad L.
Si nota come il filtro riduce notevolmente gli spostamenti inattesi, risultando in una curva più dolce.
Dai risultati ottenuti in questo paragrafo si può giungere alla conclusione che il metodo dei determinanti di Cayley-Menger ha prestazioni confrontabili con il metodo della soluzione del sistema non lineare con fsolve, ma ha il vantaggio di avere un costo computazionale molto inferiore. La traiettoria ottenuta non è visibilmente migliore di quella misurata dal sistema UWB, ma ha ancora bisogno di un filtraggio, che va ad aumentare la complessità di calcolo.
Conclusioni
In questo lavoro di tesi è stato affrontato il problema del posizionamento indoor, e in particolare ci si è focalizzati sul problema del tracciamento dei muletti all’interno di magazzini di grandi dimensioni. Per fare questo si sono utilizzati dei dispositivi UWB commerciali che permettono il calcolo delle distanze reciproche tra un tag mobile, posto sul muletto stesso, e alcune ancore poste in punti fissi del magazzino. Questi dispositivi comprendono anche un proprio sistema di localizzazione in tempo reale con un algoritmo di trilaterazione specifico.
Nel capitolo 5 si sono confrontati tre diversi algoritmi di trilaterazione: uno basato sulla stima ai minimi quadrati; uno basato sulla soluzione di un sistema non lineare; e uno basato sul metodo dei determinanti di Cayley-Menger.
Il metodo più efficiente dal punto di vista della complessità dell’algoritmo si è rivelato essere quello basato sui determinanti di Cayley-Menger, in quanto si evita sia il calcolo della matrice pseudoinversa, sia la soluzione ricorsiva del sistema non lineare.
Il metodo della soluzione con il sistema non lineare, è sicuramente il più accurato, ma è anche quello con il peso computazionale più elevato.
Il metodo della stima con i minimi quadrati si è rivelato il peggiore dal punto di vista dell’accuratezza, ed ha un costo computazionale maggiore rispetto a quello dei determinanti di Cayley-Menger.
Tuttavia, tutti gli algoritmi in esame non riuscivano ad ottenere una precisione migliore di quella che si otteneva con l’algoritmo utilizzato dall’applicazione dei dispositivi UWB di Decawave. Per questo dopo la stima si è pensato di aggiungere un filtro FIR con finestra di Kaiser, per cercare di minimizzare gli spostamenti inattesi.
Dopo il filtraggio tutti e tre gli algoritmi forniscono prestazioni migliori sia nella traiettoria rettilinea, sia in quella curvilinea. Inoltre, i metodi con determinanti di Cayley-Menger e con la soluzione del sistema non lineare, dopo il filtraggio risultano avere anche una varianza inferiore rispetto a quella misurata dall’applicazione Decawave, risultando quindi in una stima più affidabile.
In conclusione quindi, i tre algoritmi presi in esame sono delle diverse alternative al problema del posizionamento indoor, ma per ottenere delle prestazioni migliori rispetto al
metodo del sistema UWB di Decawave in termini di precisione c’è bisogno di inserire anche un filtro FIR.
Il metodo migliore da utilizzare dipende quindi dall’applicazione di interesse. Se, come nel nostro caso, si ha bisogno di un metodo che possa essere implementato in tempo reale e con poca potenza di calcolo, allora il metodo dei determinanti di Cayley-Menger è sicuramente una buona alternativa; se invece si ha a disposizione molta potenza di calcolo, allora il metodo migliore dal punto di vista della precisione risulta essere quello ricorsivo con la soluzione del sistema non lineare.
In generale andrà sempre trovato un giusto trade-off tra la precisione ottenuta e la complessità di calcolo necessaria.
Questo progetto e gli algoritmi sviluppati, sono stati pensati ad hoc per l’applicazione di interesse del tracciamento di muletti all’interno di magazzini estesi, e con il tag posto sempre ad una altezza costante. In futuro potrebbe essere interessante generalizzare questi metodi senza imporre che l’altezza del tag sia costante, in modo da allargare il campo di utilizzo anche in ambienti indoor in cui sono presenti rampe in salita e/o in discesa, e quindi dove anche la coordinata z del tag può essere variabile.
Si potrebbe pensare di estendere il sistema ad ambienti più vasti, in modo da usufruire dello stesso sistema di tracciamento anche nel caso di stabilimenti costituiti da più magazzini separati da corridoi, aumentando il numero di ancore totali e tracciando il movimento di più tag contemporaneamente.
Inoltre, sarebbe interessante vedere come si comporta il sistema utilizzando antenne più grandi e con maggiore guadagno per il sistema UWB, allo scopo di diminuire la densità di ancore, e migliorare l’accuratezza della posizione
Bibliografia
[1] “DWM1001 Datasheet”, Decawave
[2] “DWM1001 Firmware User Guide”, Decawave [3] “DWM1001 System Overview”, Decawave
[4] “DWM1001 Firmware Application Programming Interface (API) Guide”, Decawave
[5] “DWM1001 DEV Product Information”, Decawave
[6] B. Van Herbruggen, B. Jooris, M. Ridolfi, N. Macoir, Q.Van den Brande, S. Lemey, E. De Poorter, “Wi-Pos: A Low-Cost, Open Source Ultra-Wideband (UWB)
Hardware Platform with Long Range Sub-GHz Backbone“, IMEC, IDLab,
Department of Information Technology, Ghent University, Belgium, 2019
[7] S. Yerpude, T. K. Singhal, “SMART Warehouse with Internet of Things supported
Inventory Management System”, Symbiosis Institute of Telecom Management,
Symbiosis International University, 2018
[8] M. Nilson, “Performance Comparison of Localization Algorithms for UWB
Measurements with Closely Spaced Anchors”, Lulea University of Technology,
Department of Computer Science, Electrical and Space Engineering, 2018
[9] L. Bononi, D. Catellani, “Una rassegna di tecnologie per posizionamento indoor”, Università di Bologna, 2017
[10] A. R. J. Ruiz, F. S. Granja, “Comparing Ubisense, BeSpoon, and Decawave UWB
Location System: Indoor Performance Analysis”, IEEE Transactions of
instrumentation and measurement, vol. 66, 2017
[11] F. Lazzari, A. Buffi, P. Nepa, S. Lazzari, “Numerical investigation of an UWB
localization tecnique for Unmanned Aerial Vehicles in outdoor scenarios”, IEEE
sensors journal, vol. 17, 2017
[12] A. Alarifi, A. M. Al-Salman, M. Alsaleh, A. Alnafessah, S. Al-Hadhrami, M. A. Al- Ammar, H. S. Al Khalifa, “Ultra Wideband Indoor Positioning Technologies:
Analysis and Recent Advances”, 2016
[13] F. Elbahhar, B. Fall, M. Heddebaut, A. Rivenq, J. M. Rouvaen, “Indoor positioning
[14] C. Zhang, M. Kuhn, B. Merkl, M. Mahfouz, A. E. Fathy, “Development of an UWB
Indoor 3D Positioning Radar with Millimeter Accuracy”, University of Tennessee,
Knoxville, 2014
[15] C. Giacomia, C. Lupascu, A. Machi, L. Minteci, A. Scianna, G. Tarantino, M. Tripiciano, “Metodologie di posizionamento indoor con tecnologia Wi-Fi”, Consiglio Nazionale delle Ricerche, Istituto di Calcolo e Reti ad Alte Prestazioni (ICAR), 2014
[16] D. H. Stojanovic, N. M. Stojanovic, “Indoor localization and tracking: methods,
technologies and research challenges”, University of Nis, Faculty of Electronic
Engineering, Department of Computer Science, Republic of Serbia, 2014
[17] C. Medina, J. C. Segura, A. De la Torre, “Ultrasound Indoor Positioning System
Based on a Low-Power Wireless Sensor Network Providing Sub-Centimeter Accuracy”, University of Granada, ETSIIT, 2013
[18] M. Fathizadeh, J. E. Cody, “Design of a mobile robot and use of RFID for fast
werehousing” Purdue University, Calumet, 2012
[19] L. Zwirello, T. Schipper, M. Harter, T. Zwick, “UWB Localization System for
Indoor Applications: Concept, Realization and Analysis”, Karlsruhe Institute of
Technology (KIT), Germany, 2012
[20] A.Vico, “Localizzazione tramite UWB”, Università degli Studi di Padova, 2012 [21] A. De Angelis, J. O. Nilsson, I. Skong, P. Handel, P.Carbone, “Indoor Positioning
By Ultrawide Band Radio Aided Inertial Navigation”, Metrology and Measurement
Systems, Vol. XVII, pp. 447-460, 2010
[22] E. Karapistoli, F. N. Pavlidou, I. Gragopoulos, I. Tsetsinas, “An Overview of the
IEEE 802.15.4a Standard”, Aristotle University of Thessaloniki, 2010
[23] C. C. Lin, S. S. Xue, L. Yao, “Position Calculating and Path Tracking of Three
Dimensional Location System based on Different Wave Velocities”, National Taipei
University Technology, 2008
[24] M. Porretta, P. Nepa, G. Manara, F. Giannetti, “Location, Location, Location”, IEEE Vehicular Technology Magazine, 2008
[25] F. Thomas, L. Ros, “Revisiting Trilateration for Robot Localization”, IEEE