Scelta dell’algoritmo di planning
In letteratura esistono diverse tecniche di risoluzione del problema del motion plan- ning, alcune delle quali sono state brevemente presentate in precedenza. Fondamen- tale è stata la valutazione di quale delle macro-categorie di metodi potesse rispondere più efficacemente alla specificità del problema.
Le valutazioni fatte hanno preso in considerazione particolarmente due caratteristiche della ricerca del percorso:
• che consentisse una sua duttile gestione, in modo da renderlo rispondente agli obiettivi di progetto.
Il secondo punto sottintende la volontà di fornire un elevato insieme di possibili scel- te all’algoritmo di ricerca, nell’ottica di limitare il numero di rotazioni o di scegliere quelle in cui l’angolo appartenga a un range desiderato. Questo è un punto focale al fine di non sottoporre eccessivi stimoli di guida all’utente.
Se da un lato alla richiesta di sicurezza, caratteristica fondamentale ed imprescindi- bile, bene rispondono gli algoritmi dei potenziali nodali, essi risulterebbero in con- trasto alle richiesta di un percorso segmentato. D’altra parte i più recenti algoritmi basati sulla probabilità, oggi i più utilizzati, risultano essere sicuramente i più econo- mici, computazionalmente parlando. Essi, però, essendo legati per l’appunto ad un campionamento pseudo-randomico, permettono di gestire meno gli angoli di curva- tura delle traiettorie, a meno di non campionare in maniera molto fitta lo spazio. Ciò potrebbe richiedere una sovra-stimolazione del soggetto per seguire la traiettoria tro- vata. Inoltre, per garantire la sicurezza dell’utente, alla classica formulazione sarebbe necessario aggiungere un calcolo anche qui basato sui potenziali, in modo da mante- nersi sufficientemente lontani dagli ostacoli. Questo farebbe in qualche modo perdere il vantaggio nel suo utilizzo. Va, però, sottolineato come ad oggi per la guida indoor questo sia il metodo più utilizzato, in particolare, però, per una pianificazione locale real-time, sfruttando una o più telecamere.
A queste considerazioni, inoltre, va aggiunto la facile reperibilità delle piantine degli edifici. Stante questa possibilità di attingere ad un’importante fonte di dati, si è optato per sfruttarla al massimo. Avendo a che fare con una netta definizione dell’insieme de- gli ostacoli fissi, la scelta è ricaduta sull’utilizzo di metodi combinatori. Nello specifico è stata sviluppata la decomposizione in celle dello spazio, ispirata alla decomposizione trapezoidale.
Le considerazioni fatte nella scelta iniziale sono, quindi, riassumibili nelle seguenti osservazioni sui metodi combinatori:
• la formulazione stessa prevede la determinazione dei nodi come centrali rispetto alle celle, per cui con delle distanze minime note dagli ostacoli;
• risulta semplice definire le adiacenze e valutarle in maniera congeniale rispetto ai compiti da adempiere;
• consentono di sfruttare maggiormente le informazioni date dalla planimetria del luogo in esame;
• avendo suddiviso il problema del planning tra alto e basso livello, il principa- le aspetto negativo, rappresentato dal costo computazionale, risulta essere di secondaria importanza.
Scendendo poi nel dettaglio dei metodi di decomposizione in celle, fin da subito si è optato per scartare la scelta della decomposizione approssimata a favore di quella esatta. Ciò è stato dettato dalla volontà da un lato di massimizzare le informazioni di cui si è a disposizione e dall’altro dalla sicurezza di aver a che fare con un algoritmo completo, sottostando alle proprietà di accessibilità e preservazione della connettibilità del grafo.
Questa scelta comporta, dal punto di vista algoritmico, la necessità di ricercare i vertici degli ostacoli e tracciare una linea di delimitazione. La decomposizione può essere ef- fettuata tracciando segmenti verticali o orizzontali. L’insieme delle linee suddividerà lo spazio in celle, di cui verranno ricercate successivamente le adiacenze ed assegnati i costi.
Essendo le celle elementi basilari su cui si fonda la ricerca, la definizione di queste en- tità è una delle condizioni che direzionerà il percorso stesso. Per questo motivo prima di proseguire secondo una via ci si è soffermati ulteriormente su questo passaggio. Per meglio comprenderne le criticità verranno riportati degli esempi grafici di alcuni pos- sibili risultati. Ciò che in questa fase verrà mostrato risulta essere un’esemplificazione degli scenari, sfruttando tali modelli per meglio evidenziare ed esasperare gli aspetti in discussione. In una seconda fase verranno presentati i risultati sulle reali piantine
su cui l’algoritmo è stato utilizzato.
In questo stadio gli unici nodi a comporre il grafo sono quelli al centro delle celle. Una definizione del genere potrebbe richiedere l’introduzione di ulteriori calcoli e/o strategie per trovare un percorso tra due celle vicine. In particolare, le difficoltà insor- gono nel momento in cui è richiesto di passare tra due stanze vicine attraverso una porta o più in generale un restringimento. Come si può vedere per esempio nella Fi- gura 4.2, non sempre esiste un segmento congiungente due nodi, nonostante le celle risultino essere vicine e con una porzione di lato a comune. Nella realtà un percorso valido sussiste, ma questo andrebbe ricercato con un ulteriore aggravio computazio- nale e, comunque, discostandosi da un percorso rettilineo. Inoltre, potrebbe essere trovato effettivamente un percorso, ma che risulti pericolosamente vicino ad un osta- colo. Tale situazione è poco sicura per l’utente e, nonostante il planning di basso livello sarebbe in grado di sopperirvi, le scelte progettuali hanno tentato di non relegare il compito all’obstacle avoidance, quando il problema possa essere ovviato a priori. Va comunque notato come l’introduzione dei nodi sui segmenti a comune tra due celle vicine potrebbe di per sé consentire di trovare un percorso accessibile.
Presi ad esame singolarmente i metodi di suddivisione in celle verticale ed orizzon-
(a) (b)
Figura 4.2:Caso di connessione tra due punti attraverso una porta considerando i soli nodi baricentrici delle celle: a) caso di suddivisione verticele dell’immagine; b) caso di doppia suddivisione.
Per cui, si è optato per una diversa implementazione in cui vengano fuse entrambe le decomposizioni. Si avrà, perciò, a che fare con una doppia decomposizione dell’imma- gine. Questo, riportato al caso di una planimetria, comporterà il vantaggio di avere a disposizione una o più celle anche nelle zone di passaggio tra due stanze o restringi- menti. Per il nostro problema ciò risulta sostanziale. Senza perdere di generalità, si pensi ad esempio al caso precedente, in cui è necessario attraversare una porta per il raggiungimento del goal. Avere questa tipologia di suddivisione consente, già con la realizzazione di questo scarno grafo, di sfruttare dei nodi intermedi che consentano la pianificazione di una traiettoria equidistante dagli ostacoli più vicini nei punti di maggior criticità.
Oltre questo caso specifico, anche se importante e sicuramente presente più volte in un problema del genere, una doppia suddivisione consente di aumentare il numero di nodi. Così facendo vengono fornite maggior possibilità di scelta all’algoritmo di ricerca sul grafo. Tale amplificazione dell’insieme non aggrava particolarmente la ri- cerca stessa. Consente, però, di poter inserire maggiori parametri di ottimizzazione e di aver vertici in posizioni strategicamente ottimali, in quanto dettati dalla presenza di ostacoli lungo un qualsiasi asse.
Un esempio pratico delle possibili influenze sul cammino è riportato in Figura 4.3.
Rilevamento dei Vertici degli ostacoli
Uno step fondamentale nell’algoritmo risulta essere il rilevamento dei vertici degli ostacoli. Questo perché, come precedentemente specificato, tali punti rappresente- ranno l’origine dei segmenti di delimitazione delle celle. Diverse sono le possibilità per effettuare una corner detection. Nel presente lavoro si è deciso di utilizzare l’algo- ritmo di Harris, precedentemente descritto. Tale fase risulta altresì essere una parte delicata del codice. Il tuning dei parametri ha preso in considerazione che, nonostante il tempo impiegato non risulti essere un vincolo particolarmente stringente, non vi
(a) (b)
(c)
Figura 4.3:Esempi di cammini ottenuti per connettere due nodi di partenza ed arrivo nei casi di suddivisione: a) solo verticale, b) solo orizzontale; c) doppia-suddivisione.
fosse un eccessivo aggravio computazionale.
Per un’immagine che sia costruita opportunamente con lo scopo di essere utilizzata per il presente planning, tutti i corner vengono rilevati. Ciò non vale altrettanto per alcune delle situazioni reali che verranno di seguito preposte. In situazioni in cui o la scala non consenta una netta definizione di un muro di separazione o la risoluzione stessa dell’immagine risulti scadente, il metodo utilizzato potrebbe fallire. Non poten- do sfruttare ulteriormente la funzione per eliminare questi errori, successivi controlli hanno provato ad ovviarvi.
La loro localizzazione risulta, però, imperfetta. Nonostante l’errore sia molto picco- lo, in media di 3 pixel, esso può portare ad una notevolissima crescita del numero di celle che vengono generate o all’accostamento erroneo di diverse linee di delimita-
zione. Verrebbe cosi ad essere corrotta l’informazione originale, rischiando anche di accrescere notevolmente la grandezza del grafo con conseguente maggior richiesta di elaborazione. Per ovviare a questa imprecisione è stata implementata una apposita funzione che prende come punto di partenza i corner trovati e ricerca nell’intorno di ognuno di essi il punto esatto in cui posizionarlo. Considerando il fatto di aver a che fare con ingombri di edifici, la ricerca è stata limitata a soli 8 pattern possibili, come riportato schematicamente in Figura 4.4
(a) (b)
Figura 4.4: a)Pattern ricercati nella correzione, b) riposizionamento corner.
Un esempio viene riportato di seguito, Figura 4.5, dove il numero di celle passa da 572 a 457 dopo la correzione. Considerando il fatto che per ogni cella vanno effettuate le operazioni di ricerca dei nodi sui lati e delle adiacenze, il guadagno è sostanzia- le. Ancor più importante notare come il posizionamento errato di alcuni corner non consentiva la delimitazione di alcune celle, condizione che avrebbe precluso al rileva- mento corretto dei rispettivi dati e, nel peggiore dei casi, alla perdita di connettibilità del grafo.
Generazione delle celle
Una volta che si hanno a disposizione i dati delle posizioni dei vertici degli ostacoli vengono tracciate le linee di delimitazioni. Queste sono generate nelle quattro dire-
(a)
(b)
Figura 4.5:Esempio dell’affinamento del risultato della corner detection: a) viene riportata la suddivisione senza la correzione dei corner; b) viene mostrato il risultato della suddivisione con la correzione dei corner.
zioni principali, con origine il corner stesso, fintanto che non si vada ad intercettare il successivo ostacolo.
descritto anche in precedenza, è stato qui introdotto un elemento di novità. Nella suddivisione esatta in celle, infatti, i confini vengono generalmente tracciati solo in direzione verticale od orizzontale. Nel presente lavoro è stato deciso di utilizzare en- trambe le opzioni al fine di ottenere una doppia suddivisione. Se da un lato questo, ine- vitabilmente, aumenta il costo computazionale dell’intero algoritmo, dall’altro rende possibile sfruttare appieno le informazioni contenute nella planimetria.
Utilizzando solo una delle metodologie di suddivisione esatta e dati la tipologia di immagini ed eventuali imprecisioni nella stessa, potrebbero nascere delle celle molto allungate in una direzione e strette nell’altra. Sussisterebbe il rischio di incorrere in situazioni in cui, due celle effettivamente adiacenti, non risultino avere i nodi - po- sizionati nei loro baricentri - connettibili da un semplice segmento di retta. Anche nell’ipotesi di trovare un percorso, esso potrebbe risultare innaturale e più lungo e tortuoso del dovuto.
Questo tipo di decomposizione presenta ancora delle caratteristiche deleterie per la ri- cerca. Da un lato sussistono dei casi in cui vengono a crearsi delle celle di dimensione molto piccole rispetto alla scala dell’immagine. Questo può comportare la generazio- ne di una traiettoria molto spezzettata e che richiederebbe diversi cambi di direzione e feedback di controllo molto frequenti. Inoltre, non è pensabile ed utile controllare l’utente con precisione eccessiva a rimanere lungo il cammino.
Viceversa, in spazi aperti molto ampi e senza ostacoli intermedi, si vengono a forma- re delle celle eccessivamente grandi. Questo fattore porterebbe a dover raggiungere il nodo al centro di queste celle come percorso intermedio, per poi dirigersi verso il successivo. Così formato, infatti, il grafo non presenterebbe alternative per scegliere una traiettoria più consona.
Per ovviare a queste imperfezioni e migliorare i dati che contenuti nel grafo, è quindi richiesto un’ulteriore elaborazione dell’immagine. In particolare le operazioni imple- mentate sono due:
• Divisione delle celle troppo grandi.
La definizione delle soglie viene fatta in maniera automatica ed in funziona alla scala dell’immagine. In particolare viene calcolata una parametro pari alla dimensione di un box attorno all’utente, che rappresenterà uno spazio di sicurezza all’interno del quale non dovranno esservi ostacoli. A partire da esso verranno calcolate le soglie.
Quella minima, sotto la quale si cerca di inglobare una cella, è definita in modo che la dimensione inferiore sia tale da contenere un utente in sicurezza. In caso ciò non sia rispettato, verrebbe cercata tra i vicini un’adeguata candidata che inglobi la cella in esame. Ai fini di mantenere le celle di forma rettangolare, l’adeguatezza o meno del- l’operazione di merge dipende dalla dimensione e posizione del lato a comune. Infatti, sarà necessario che la cella da inglobare e quella inglobante, condividano esattamente lo stesso lato. Qualora ciò non venisse rispettato, il merge non verrebbe effettuato. Il processo esemplificato viene riportato in Figura 4.6.
Questo controllo si rende necessario anche per un secondo motivo. Come detto in precedenza, il presente metodo di doppia-suddivisione è stato implementato col fine di sfruttare al massimo le informazioni della mappa. Punti in cui questa informazione risulta cruciale è nel passaggio attraverso le porte. Qualora la cella interna della porta venisse, invece, inglobata in maniera errata, si perderebbe il vantaggio di informazioni contenute dalla stessa, rendendo la traiettoria potenzialmente meno sicura o addirit- tura perdendo di connettibilità.
Il successivo passaggio risulta essere la divisione delle celle troppo grandi. Anche in questo caso la soglia di riferimento è definita in funzione del parametro precedente. Tale esigenza nasce dalla volontà di mettere a disposizione della ricerca un maggior numero di nodi come possibile scelta per un percorso ottimale. Qualora una o entram- be le dimensioni superassero la soglia, le celle verrebbero equamente divise passando dall’avere un unico nodo a duo o quattro rispettivamente. Il processo anche in questo caso è schematizzata graficamente in Figura 4.7.
Figura 4.6:Processo di merge: nella parte superiore dell’immagine l’operazione è andato a buon fine; in quella inferiore non vengono rispettati i vincoli e la suddivisione non varia.
Figura 4.7:Divisione delle celle, può coinvolgere solo una o entrambe le dimensioni.
Queste due accortezze fanno si che la maggior parte delle celle si trovi in un range di dimensione, andando ad acquisire un’informazione sostanzialmente omogenea su tutta la mappa, ma che automaticamente si infittisca in presenza di un gran numero di ostacoli. Il risultato raggiunto è quello, a titolo di esempio, di Figura 4.8.
(a)
(b)
Figura 4.8: a)Risultato della doppia-suddivisione in celle; b) risultato della suddivisione dopo merge e divisione delle celle.
Ricerca delle adiacenze
La ricerca delle adiacenze parte dai dati acquisiti in fase di generazione delle celle. Ad ogni nodo baricentrico della cella è stata associata una posizione e dei dati ritenuti importanti. In particolare sono salvati, in un’apposita struttura, le lunghezze dei lati ed i vertici del poligono. Questi valori vengono utilizzati nella ricerca dei vicini. Si parte andando ad ispezionare la porzione di immagine compresa tra le delimitazioni della cella ed una loro maggiorazione. Nonostante questa sia la scelta di default nel codice, è possibile apportarvi delle modifiche.
In particolare un flag apposito gestisce tre tipi di ricerca del vicinato: • solo lateralmente;
• lateralmente ed in diagonale; • tutti i nodi a vista.
I tre casi portano naturalmente alla definizione di tre grafi molto differenti tra di loro. Queste alternative sono state implementate per andare ad analizzare direttamente gli effetti sul un problema formulato. La differenza tra i tre casi è mostrata, a titolo d’e- sempio, nella Figura 4.9.
(a) (b) (c)
Figura 4.9:Esempio di adiacenze a) solo laterali, b) laterali ed in diagonale; c) tutti i nodi a vista.
La scelta di impostare la ricerca tutta intorno alla cella nasce da considerazioni fatte in funzione alle prove condotte. Usare solo adiacenze derivanti da celle che si trova- no di lato, sopra o sotto, risulta in certi casi limitante per l’algoritmo che andrebbe a produrre in uscita delle traiettorie che non rispecchiano appieno i parametri di ot- timizzazione. Di contro prendere in considerazione tutti i nodi nel "campo visivo" della cella produrrebbe un risultato ottimo dal punto di vista della distanza percorsa. Spesso sarebbe, però, ai limiti della sicurezza per l’utente che si vedrebbe condotto pericolosamente vicino agli ostacoli. Il giusto trade-off tra le due necessità sembra es- sere raggiunto nel caso in cui i vicini siano tutti quelli in un intorno della cella stessa, indipendentemente dalla direzione relativa in cui esse si trovino.
Queste considerazioni portano, però, a definire solo i nodi vicini e non quelli adia- centi. In fase di progettazione è stata, infatti, posta una dovuta distinzione tra le due definizioni:
• Celle vicine : sono quelle celle che rispecchiano la condizione posta di vici- nanza come descritto in precedenza; in particolare sono state considerate vicine quelle celle che si trovano in un intorno dei bordi della cella in esame.
• Celle adiacenti : sono quelle celle, tra le vicine, i cui baricentri siano connetti- bili da un segmento.
Una volta trovate tutte le celle vicine, le stesse vengono ispezionate per rispondere alla condizione di adiacenza. Più specificamente, tale qualità è valida nel momento in cui tra i due nodi sia possibile un percorso rettilineo di uno spessore dato. La con- nessione risulta consistente se per tutta la sua lunghezza non avvenga lo scontro con un ostacolo. Lo spessore del segmento è calcolato automaticamente in funzione della scala. Viene definito così un cammino per un oggetto puntiforme contornato da una box di sicurezza, come mostrato in Figura 4.10.
Figura 4.10:Calcolo delle adiacenze: sono validati solo gli archi che consentano di connet- tere due nodi tramite un segmento e considerando una bounding box attorno l’oggetto del planning.
Nodi sui lati
Arrivati a questo punto il grafo risulta essere già ricco delle principali informazioni richieste per una basica pianificazione. Avendo, però, tra gli obiettivi quello di ricer- care una traiettoria per quanto possibile confortevole per l’utente, gli attuali nodi non risultano esser sufficienti.
Si ricorda come da interviste e prove sperimentali effettuati precedentemente rispetto alla presente tesi, sia risultato che le persone non vedenti tendano a ruotare netta- mente in caso di necessità, con un angolo tendenzialmente compreso tra 35° e 60°. Per tentare, quindi, di inserire anche questo parametro in fase di elaborazione del percorso è stato necessario introdurre nuovi nodi. Questi sono stati posizionati nel punto me- dio delle porzioni di lato condiviso dalle celle. Tale passaggio è diventato importante anche in funzione alla modalità di determinazione delle adiacenze. Dovendo rispetta- re il vincolo sopra descritto affinché due celle possano essere definite adiacenti, non sarebbe stato possibile garantire la preservazione della connettibilità del grafo.
Vengono analizzare le motivazioni di questa scelta per step.
Per quanto riguarda la volontà di naturalezza della traiettoria, prima di questa nuova introduzione si venivano a creare delle situazioni in cui sarebbe stato chiesto all’utente rotazione anche prossime ai 90°, come nell’esempio in Figura 4.11. Questa possibi- lità è da scoraggiare in quanto comporterebbe una condotta poco spontaneo ed una perdita immotivata di tempo. Il soggetto dovrebbe arrivare in un punto, stopparsi, ruotare sul posto e solo dopo proseguire. Quindi un processo macchinoso e difficile