Logistica robotizzata

Robot industriali

I robot sono utilizzati per risolvere problemi in una maniera che agli esseri umani risulta molto difficile da realizzare

compiono azioni e calcoli con elevata precisione
eseguono azioni ripetitive senza interruzione
operano in ambienti ostili
eseguono istruzioni prestabilite
possono adattarsi ai cambiamenti nell'ambiente di lavoro

La soluzione di problemi complessi tramite robot può seguire due approcci diversi, che poi sono gli stessi che si ritrovano in tutti i settori tecnologici.

Soluzione monolitica

Il primo approccio è quello di realizzare un'unica macchina che risolve il problema complesso. Però questo porta a problemi di realizzazione, programmazione, manutenzione, scarsa scalabilità e flessibilità, ecc.

Si pensi ad un impianto di movimentazione merci realizzato con nastri trasportatori.

Soluzione distribuita

Il secondo approccio è quello di realizzare molti robot più semplici che collaborano tra loro per raggiungere l'obiettivo comune. A fronte di una maggiore complessità organizzativa per la gestione delle interazioni, si hanno dei vantaggi non indifferenti.

Ad esempio si ottiene un sistema flessibile, scalabile all'occorrenza, a cui sono applicabili economie di scala, con manutenzioni localizzate, con copertura di ampie aree, con specializzazione nei compiti, ecc.

Si pensi alla movimentazione merci realizzata con una molteplicità di piccoli robot trasportatori tutti uguali.

Ovviamente sono possibili anche soluzioni miste.

Uno dei settori più sensibili alle problematiche dell'automazione è la logistica.

I robot mobili vengono denominati AGV Automated Guided Vehicles.

Collaborazione tra robot

La presenza di molteplici robot nello stesso ambiente richiede di gestire gli spostamenti e le possibili interazioni tra i robot, e tra robot ed esseri umani.

L'obiettivo è quello di assegnare ai robot dei compiti che devono essere svolti in contemporanea senza che vi siano interferenze dannose tra le varie entità presenti.

Modelli matematici

Modello del singolo robot

I singoli robot devono essere descritti in una forma tale da evidenziare quelle caratteristiche che sono di interesse per il raggiungimento dell'obiettivo globale.

Nel caso della logistica e quindi della movimentazione delle merci, sicuramente alcuni aspetti caratterizzanti il robot riguardano il suo movimento.

E' necessario quindi descrivere l'AGV dal punto di vista cinematico (posizione, velocità, ecc).

Il movimento del robot verrà descritto in termini di variabili di controllo su cui si andrà ad agire per determinarne gli spostamenti. Si otterrà un modello che dipenderà dalle caratteristiche costruttive del robot. Si dovrà tenere conto di vincoli riguardanti i valori applicabili alle variabili di controllo e di vincoli riguardanti gli spostamenti ammissibili.

Ad esempio, come vincoli saranno previsti una velocità massima di spostamento, un raggio di curvatura minimo e ci saranno delle posizioni non occupabili a causa della presenza di ostacoli o di altri robot o esseri umani.

Sarà compito del dispositivo controllore stabilire i valori da applicare alle variabili di controllo per ottenere il comportamento desiderato.

Linearizzazione

E' difficile che il modello matematico ottenuto per il robot descriva un legame lineare tra le variabili di controllo e le variabili cinematiche di uscita.

Questo ci impedisce di applicare le tecniche di controllo automatico sviluppate per i sistemi lineari.

Si ricorre quindi ad una diversa scelta delle variabili di controllo e ad opportune trasformazioni di tali variabili (realizzate mediante appositi moduli) in modo tale che il sistema complessivo diventi lineare.

Una volta ottenuto un modello lineare si ricorre agli usuali schemi di controllo, ad esempio la retroazione negativa.

Interazione tra robot

Una volta realizzato il controllo del singolo robot in modo tale che compia gli spostamenti desiderati, si sale di livello di astrazione e si crea un modello dell'insieme dei robot.

I robot possono scambiarsi informazioni tra loro. Ad esempio possono comunicare agli altri robot la propria posizione in modo tale che ognuno possa pianificare lo spostamento successivo che porti al compimento del compito assegnato evitando collisioni.

Lo scambio di informazioni avviene tramite appositi canali di comunicazione e può riguardare tutti i robot o solo una parte, ad esempio quelli che si trovano nelle immediate vicinanze.

I canali di comunicazione instaurati tra i vari robot si possono utilmente descrivere con grafi. I nodi possono rappresentare i robot comunicanti, mentre gli archi possono rappresentare i canali di comunicazione.

A seconda che il trasferimento di informazione sia unidirezione o bidirezionale, si può ricorrere a grafi orientati o non orientati.

Un percorso tra due nodi può quindi rappresentare un trasferimento di informazione tra due robot.

Il grafo descrive la situazione esistente in un certo momento, quindi lo si deve vedere come una struttura dinamica in continuo mutamento.

Consensus

Quando i robot si scambiano informazioni a livello locale, cioè esclusivamente con le entità che sono in prossimità, si ha un problema.

Il singolo robot, non avendo a disposizione la conoscenza della situazione complessiva, si trova a dover prendere delle decisioni disponendo di una conoscenza parziale del sistema. Le sue decisioni mirano ad ottimizzare il suo obiettivo, ma si rischia che le azioni ottime per uno vadano in conflitto con le azioni ottime degli altri, risultando in un peggioramento delle prestazioni complessive.

Ad esempio, due robot potrebbero entrambi decidere di percorrere nello stesso momento uno stretto corridoio in direzioni opposte, risultando in uno stallo che non permette l'evoluzione del sistema.

Il consensus mira ad individuare dei criteri decisionali locali (del singolo) che portino all'ottimizzazione globale realizzando una strategia condivisa implicita (consensus) tipica dei sistemi complessi.

Sotto opportune ipotesi, quale ad esempio che sia possibile lo scambio di informazione tra ogni possibile coppia di robot e quindi il grafo delle comunicazioni sia totalmente connesso, la strategia locale più opportuna è sempre quella derivata dal gradiente. In fondo la natura insegna che si tende sempre al livellamento delle differenze.

Alcuni casi in cui è utile il consensus sono i seguenti.

Nel rendez-vous, tutti i robot devono incontrarsi in un unico punto. Il consensus si ottiene agendo sulle singole coordinate spaziali

Nell'allineamento, tutti i robot devono muoversi nella stessa direzione. Il consensus si ottiene agendo sulla direzione.

Nella misura distribuita, tutti i robot devono concordare sul valore misurato di una grandezza. Il consensus si ottiene sulla misura.

Formazioni

Una applicazione particolare del consensus è la costituzione di una formazione, cioè il raggiungimento di una particolare disposizione spaziale dei robot.

Il problema è legato a quello del rendez-vous. Infatti il punto di rendez-vous costituisce il riferimento per le coordinate, il baricentro della formazione. La posizione di ogni singolo robot sarà quindi espressa in termini relativi al riferimento comune.

Controllo del traffico

Localizzazione

Gli AGV necessitano di conoscere la loro posizione relativamente all'ambiente in cui operano per poter prendere una decisione sui successivi spostamenti da compiere.

L'ambiente viene descritto tramite una mappa.

Odometria

Il metodo più semplice per stabilire la propria posizione è l'odometria.

Il robot determina la propria posizione basandosi sulle informazioni provenienti da propri sensori di movimento.

La posizione corrente viene quindi determinata in modo indiretto basandosi su dei calcoli.

Ad esempio dalla rotazione delle ruote si calcola lo spazio percorso o la direzione verso cui il robot è rivolto.

L'odometria però soffre di alcuni problemi.

E' necessario conoscere esattamente la posizione di partenza, che non può essere ricavata dai sensori. Questo richiede che qualcuno esterno al robot gli fornisca questa informazione. Eventuali errori nella determinazione della posizione iniziale influiscono su tutti i movimenti successivi del robot in quanto non c'è alcun modo per rilevarli o correggerli.

Inoltre, disturbi e rumori nelle misure dei sensori comportano un accumularsi degli errori di determinazione della posizione.

Sensori esterocettivi

Si ricorre a sensori che permettono di determinare la posizione misurando la distanza rispetto a punti di riferimento presenti nell'ambiente.

Ad esempio uno scanner laser rotante è in grado di misurare la distanza dagli ostacoli circostanti. Posizionando particolari superfici riflettenti (landmark) in punti prestabiliti di posizione nota con precisione, il robot è in grado di determinare la sua posizione all'interno dell'ambiente. Infatti basta conoscere la distanza planare da tre punti noti per ottenere la posizione univoca.

In presenza di disturbi nelle misure è usuale ricorrere a tecniche di filtraggio statistico (filtro di Kalman)

Sicurezza ed efficienza

Il movimento di macchine può causare gravi danni a cose e persone.

E' necessario attuare tutte le misure necessarie a prevenire gli incidenti.

Ad esempio, gli scanner laser possono essere usati anche per attuare misure di sicurezza individuando la presenza di ostacoli, che siano ambientali, altri robot o persone.

Se il movimento può causare un danno è necessario arrestare immediatamente il robot.

Questo però comporta una riduzione di efficienza del sistema nel suo complesso. L'arresto di un robot di movimentazione comporta una perdita di tempo.

Si devono quindi cercare delle soluzioni che permettano di assicurare la sicurezza e nel contempo sfruttare al massimo le risorse disponibili.

Aree riservate

Una prima soluzione è quella di riservare, se possibile, delle aree dove possono muoversi solo i robot. In tal modo è possibile ridurre drasticamente le occasioni di collisione accidentale con persone, con conseguente interruzione del servizio.

Roadmap

Una seconda soluzione è quella di predisporre dei percorsi obbligati per i robot. In questo modo si riducono drasticamente lo occasioni di collisione tra robot. Questi percorsi definiscono una roadmap.

I percorsi (reali o virtuali) collegano i vari punti della mappa tra cui devono spostarsi i robot e vengono studiati per ridurre al minimo le interferenze.

I percorsi vengono suddivisi in molti segmenti relativamente piccoli.

I segmenti sono studiati in maniera tale da rendere agevole la loro percorrenza da parte dei robot, evitando arresti e brusche rotazioni.

Il segmento sostituisce le coordinate spaziali del robot aiutando a semplificare il problema della pianificazione dei percorsi da seguire.

Ogni robot conosce in quale segmento si trova.

In ogni segmento può essere presente un solo robot, che quindi lo occupa in maniera esclusiva.

Il sistema centrale di controllo assegna ad ogni robot alcuni segmenti in base allo spostamento che deve compiere.

Le intersezioni sono particolari segmenti che gestiscono gli incroci tra percorsi.

I segmenti possono essere unidirezionali o bidirezionali. I segmenti unidirezionali possono facilitare la pianificazione dei percorsi, ma riducono le possibilità di spostamento e i flussi del traffico.

Creazione automatica di roadmap

La definizione manuale della roadmap è un problema molto complesso sia per il numero di segmenti da considerare, sia per i vincoli da rispettare.

Sono stati ideati degli algoritmi che automaticamente permettono di:

coprire lo spazio libero collegando tutti i punti di interesse
creare percorsi ridondanti che riducono le occasioni di collisione e quindi riducono la congestione del traffico
massimizzare la connettività per offrire quante più alternative possibili
soddisfare il requisito fisico sulla facilità di percorrenza dei singoli segmenti

Algoritmo di creazione di una roadmap

1) nello spazio libero, individuare corridoi e intersezioni

Si applica la Medial Axis Transform per partizionare la mappa in regioni a cui appartengono zone non libere connesse.

Il bordo delle partizioni individua i corridoi e le intersezioni.

I corridoi sono i lati delle partizioni, delimitati da due ostacoli e paralleli ai bordi degli ostacoli.

Le intersezioni si trovano all'incrocio di corridoi, delimitate da corridoi e non parallele ai bordi degli ostacoli.

2) Si riempiono i corridoi di segmenti, considerando lo spazio che ogni robot occupa. Questo può essere visto come un cerchio di un certo raggio. Di conseguenza i segmenti paralleli dovranno avere una distanza minima tra loro.

3) Si definiscono le intersezioni, facendo in modo che tutti i segmenti di corridoi diversi vengano collegati tra loro

4) Si stabiliscono le direzioni di percorrenza dei segmenti.

Si associa alla mappa un grafo orientato pesato in cui i nodi sono le intersezioni e i punti di riferimento, gli archi sono i percorsi nei corridoi e i pesi sono i tempi di percorrenza o distanze.

Se possibile si vorrebbe che i corridoi fossero bidirezionali.

Per corridoi con più percorsi paralleli si può assegnare metà percorsi ad una direzione e metà all'altra.

Per corridoi con un unico percorso si deve decidere la direzione da assegnare, garantendo la possibilità di spostarsi tra due punti qualsiasi.

Si vuole che il grafo sia totalmente connesso e quindi che esista un percorso tra ogni coppia di nodi

Inoltre si vuole che il grafo sia bilanciato per massimizzare il flusso del traffico

5) Si stabilisce la forma fisica dei segmenti in modo tale che siano facilmente percorribili dai robot.

Per ottenere curve sufficientemente dolci si possono usare le curve di Bezier.

Pianificazione dei percorsi

Ogni robot deve muoversi da un punto iniziale ad un punto finale percorrendo un percorso definito da una sequenza di segmenti.

Considerando il grafo associato a corridoi e intersezioni, il robot passerà di nodo in nodo.

Tipicamente esistono più percorsi possibili per spostarsi tra due nodi quindi ci si pone il problema di trovare un percorso ottimale.

Si noti che gli algoritmi di pianificazione dei percorsi si basano su informazioni note a priori, quali la geometria dell'ambiente e i tempi di percorrenza stimati. In realtà potremmo non disporre della conoscenza perfetta del problema. Ad esempio si possono verificare situazioni di congestione che rendono inattendibili i tempi di percorrenza stimati, oppure alcuni spazi potrebbero diventare inaccessibili e quindi inutilizzabili per gli spostamenti.

Per la pianificazione vengono utilizzati degli algoritmi sub-ottimali che consentano di ottenere una soluzione ragionevolmente buona con un costo computazionale accettabile.

$A^{*}$ permette di trovare un percorso ottimale rispetto ad una certa metrica euristica di costo

$A^{*}$ parte dal nodo iniziale e crea un albero di percorsi alternativi che cresce progressivamente fino a raggiungere il nodo destinazione. La crescita dell'albero avviene dal nodo della frontiera che presenta un costo stimato minimo per il raggiungimento della destinazione. Il costo del percorso viene stimato utilizzando il costo avuto per giungere fino al nodo considerato più il costo per la destinazione stimato grazie ad una funzione euristica specifica del problema.

$A^{*}$ risulta poco efficiente nel caso di modifiche all'ambiente che richiederebbero una continua ripianificazione.

L'algoritmo $D^{*}$ cerca il percorso ottimale partendo dal nodo destinazione fino ad arrivare al nodo corrente. Il costo per raggiungere la destinazione è quindi noto e non stimato. Il costo effettivo è calcolato di volta in volta basandosi sulle informazioni correnti. Si adatta bene ad ambienti altamente dinamici.

Coordinamento

Sia $A^{*}$ che $D^{*}$ operano considerando i singoli robot. Quindi la pianificazione che si ottiene non è la soluzione ottimale. Ad esempio non tiene conto che un segmento previsto nel percorso ottimale di un robot potrebbe non essere utilizzabile a causa della presenza di un altro robot.

E' necessario introdurre un livello superiore di coordinamento.

Il coordinamento può essere centralizzato o distribuito.

Il coordinamento centralizzato viene operato da un'entità di supervisione che determina i percorsi ottimali dei singoli robot evitando sovrapposizioni.

In caso di conflitti nell'occupazione di un segmento, si può ricorrere a priorità tra i compiti dei robot. Quindi le allocazioni dei segmenti seguono l'ordine di priorità.

Sfruttando la conoscenza globale della situazione si possono ottenere soluzioni migliori. Tuttavia è un metodo computazionalmente molto oneroso viste le dimensioni dei problemi tipici (decine di robot, migliaia di segmenti).

Il coordinamento decentralizzato si basa su scelte autonome dei singoli robot.

Ogni robot calcola il proprio percorso ottimale in base alle proprie conoscenze.

E' un sistema computazionalmente più economico, ma difficilmente porta a soluzioni che si avvicinano a quelle ottimali. Inoltre senza opportune regole si rischia di innescare meccanismi di blocco che impediscono l'avanzamento del sistema.

Un buon compromesso è il coordinamento gerarchico. Si partiziona l'ambiente in aree in base a considerazioni, ad esempio, di traffico. Al livello superiore si pianificano i percorsi sotto forma di aree da attraversare per raggiungere l'obiettivo. A livello di area si pianificano i percorsi come segmenti da attraversare.

Il coordinamento gerarchico permette una distribuzione del calcolo raggiungendo soluzioni sub-ottimali.

Inoltre permette di considerare parametri che definiscono lo stato corrente del traffico all'interno delle singole aree di cui tenere conto nella pianificazione. Ad esempio il semplice numero di robot presenti in un'area è indicativo del traffico presente in essa.

Al posto del grafo iniziale si considera un grafo delle aree e vari grafi per le aree.

Si noti che i singoli robot possono acquisire informazioni aggiornate sul traffico che vanno ad aggiornare i pesi del grafo di pianificazione.

Collisioni

I robot dovranno affrontare situazioni di possibile collisione. E' necessario che abbiano la possibilità di scambiarsi informazioni tra loro per consentire una ripianificazione dei percorsi. In tal caso i robot che non possono proseguire per il rischio di collisione dovranno negoziare il diritto di passaggio su un segmento. Ad esempio si può stabilire una priorità tra i vari robot in cui il perdente dovrà mettersi in attesa o scegliere un percorso alternativo.

Particolarmente delicate sono le intersezioni perchè soggette alla maggiore probabilità di passaggio dei robot e quindi di collisione. Si può ricorrere a tecniche di allocazione delle risorse con accesso mutuamente esclusivo.

Partizionamento

Il partizionamento dell'ambiente dovrebbe seguire un criterio di distribuzione uniforme del traffico, cioè il numero di robot presenti in ogni area dovrebbe essere circa lo stesso. Una tecnica utilizzabile è il partizionamento di Voronoi prendendo le intersezioni come punti di riferimento. Il problema è che le partizioni ottenute utilizzando la distanza euclidea non tengono conto della differenza tra zone libere e non libere. Si utilizza quindi la distanza geodetica intesa come costo di spostamento tra due punti.

Un'altra problematica riguarda la dinamicità delle posizioni dei robot. Una partizione statica comporta la presenza di aree affollate e aree poco utilizzate. Si può ricorrere ad un partizionamento dinamico basato sulle posizioni correnti dei robot.

Il partizionamento dinamico geodetico procede nel modo seguente

Si considerano le posizioni correnti dei robot
Si clusterizzano i robot in base alla loro distanza di influenza reciproca
Si individuano i baricentri dei vari cluster di robot
Si applica un partizionamento di Voronoi dell'ambiente usando una distanza geodetica rispetto ai baricentri
Ad ogni cluster si associa un'area di pianificazione
Si determinano le distanze geodetiche tra i baricentri delle aree
Si procede periodicamente ad un aggiornamento della partizione

Attribuzione dei compiti

Si hanno un insieme di compiti/missioni da svolgere e un insieme di agenti a cui assegnarli.

Si suppone che gli agenti siano tra loro equivalenti rispetto ai compiti e che sia noto il costo che ogni agente dovrebbe sopportare per l'assolvimento di ogni compito.

L'obiettivo è di assegnare i compiti ai singoli agenti in modo tale da minimizzare il costo totale di assegnazione. Come costo dell'assegnazione si potrebbe considerare il tempo impiegato per lo spostamento.

Si noti che i compiti di norma non sono tutti noti a priori in quanto vengono definiti dinamicamente durante il funzionamento del sistema.

Per l'assegnazione dei compiti si può usare l'algoritmo ungherese