Universit`
a degli Studi di Pisa
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE Corso di Laurea Magistrale in Ingegneria Robotica e dell’Automazione
Tesi di Laurea Magistrale
GESTIONE CENTRALIZZATA
PER L’ALLOCAZIONE DINAMICA DI TASK
IN UN SISTEMA MULTI-ROBOT
Candidato Letizia Curti Relatore Lucia Pallottino Anno Accademico 2015-2016Alla vita, che ci riserva sempre grandi sorprese.
Contents
1 Introduzione 13
2 L’Architettura modulare 19
2.1 Il Sistema Multi-Robot . . . 20
2.2 I Task . . . 24
2.3 Il modulo Management and Planning . . . 26
2.3.1 Task Management . . . 26
2.3.2 Path Planning . . . 27
2.3.3 Pianificazione . . . 28
2.4 Il modulo Task Assignment . . . 30
3 Il modulo Task Assignment 33 3.1 Tassonomia del problema di MRTA . . . 33
3.2 Formulazione del problema di MRTA . . . 35
3.2.1 Funzione Utilità . . . 36
3.3 Risoluzione del problema MRTA . . . 37
3.3.1 Assegnazione dei task come un problema di programmazione lineare . . . 38
3.3.2 Algoritmo iterativo per l’assegnazione dei task . . . 39
4 Implementazione dell’Architettura 45 4.1 Introduzione a ROS . . . 45 4.1.1 I Nodi . . . 48 4.1.2 Il Master . . . 48 4.1.3 La comunicazione in ROS . . . 48 4.1.4 Il Bag . . . 55
4.2 ROS e i moduli dell’architettura generale . . . 55
4.3 Visualizzazione dello scenario in ROS . . . 60 5
Squadra di droni per consegna a domicilio . . . 64 5.2 Scenario 2:
Squadra di taxi per il trasporto di passeggeri . . . 65 5.2.1 Risultati . . . 67 5.3 Utility Function come strumento di design . . . 70
6 Conclusioni 73
List of Figures
2.1 Schema a blocchi dell’architettura modulare riconfigurabile . . . 19
2.2 Blocco MRS con ingressi e uscite . . . 20
2.3 Blocco Task con ingressi e uscite . . . 24
2.4 Blocco Management and Planning con ingressi e uscite . . . 26
2.5 Blocco Task Assignment con ingressi e uscite . . . 30
3.1 a) Rappresentazione della tassonomia di Gerkey e Matarić lungo tre assi [16] b) Rappresentazione della tassonomia per il caso in esame . 34 4.1 Tipi di dato supportati da service e topic . . . 49
4.2 Procedura sequenziale per comunicazione asincrona tra nodi ROS . 50 4.3 Computation Graph . . . 56
5.1 Visualizzazione 3D dello scenario del trasporto passegegri . . . 67
5.2 Scenario con ostacoli statici e rottura del taxi blu a) Il taxi blu carica il passeggero b) Poco dopo il taxi blu si rompe e rimane fermo c) Arriva il taxi rosso a caricare i passeggeri del taxi rotto d) Il taxi rosso porta i passeggeri a destinazione risolvendo l’emergenza . . . . 68
5.3 Scenario con ostacoli statici ed evoluzione del sistema senza impre-visti a) Situazione iniziale prima dell’arrivo dei task b) Arrivo dei primi 3 task c) Il taxi verde esegue il primo task arrivato d) Il taxi blu esegue il secondo task arrivato e) Fine della missione: l’ultimo passeggero viene fatto scendere alla sua destinazione dal taxi verde, gli altri sono alle fermi alle pompe di benzina in attesa di nuove chiamate . . . 69
5.4 Scenario con ostacoli statici ed evoluzione del sistema senza impre-visti a) Il taxi viola sta finendo di scaricare il passeggero verde ed è in riserva b) Il taxi viola raggiunge la pompa di benzina più vicina . 70 5.5 Scenario con ostacoli statici e dinamici a) Arrivano dei passanti nello scenario (visualizzati nei cerchi neri) b) Si vede che il taxi grigio passa dietro l’ostacolo evitandolo . . . 70
specifica: il taxi carica il passeggero giallo poiché questo gli permette di compiere complessivamente il percorso più breve c) II specifica: il taxi carica il passeggero azzurro poiché per lui la seconda tratta è più lunga di quella del passeggero giallo, in questo modo il tassista può guadagnare di più . . . 72
List of Tables
2.1 Classificazione del Sistema Multi-Robot in esame . . . 22 A.1 Elenco dei topic creati per l’implementazione dell’architettura . . . 91
Sommario
Obiettivo di questo lavoro è la progettazione di un’architettura software per la risoluzione centralizzata di un problema di assegnazione dei task ad una squadra di robot (Multi Robot Task Allocation, MRTA).
Il sistema multi-robot (Multi-Robot System, MRS) considerato è omogeneo, ovvero ogni robot possiede le stesse abilità, e si muove all’interno di uno scenario di cui si conosce la mappa completa, ad eccezione di alcuni ostacoli dinamici, che possono dunque presentarsi in modo imprevisto.
Il sistema di gestione deve organizzare la squadra in modo tale da portare a ter-mine tutte le richieste effettuate dagli utenti durante la missione, ottimizzando alcune grandezze di rilevanza ingegneristica, come il consumo di risorse dei robot e il tempo di completamento di tutti i compiti assegnati.
Il generico task che ogni robot dovrà eseguire consiste nel soddisfare la richiesta dell’utente che gli è stato assegnato, si farà riferimento in particolare a due situa-zioni di interesse sociale: il trasporto passaggeri per un sistema di “taxi intelligenti” e la consegna a domicilio per una squadra di droni.
La gestione dell’assegnazione dei compiti alla squadra dovrà essere completamente centralizzata, si richiede dunque la presenza di un supervisor che, con una co-noscenza completa dell’ambiente e del MRS, prenda tutte le decisioni utili alla risoluzione del problema di MRTA.
Il principale contributo di questo lavoro è il design di un’architettura modulare ri-configurabile, progettata per affrontare il problema del MRTA come un problema di Programmazione Lineare Intera Binaria (Binary Integer Linear Programming, BILP). La generalità dell’architettura permette di utilizzare il sistema di gestione proposto in vari scenari, che presentano caratteristiche fondamentali simili, ma composizione dei task e contesto di applicazione diversi.
Abstract
The main aim of this work is the design of a software architecture for centrally resolution of a Multi-Robot Task Allocation (MRTA) problem.
The multi-robot system is considered homogeneous, each robot has the same abil-ities, and they move within a scenario for which we have the complete knowledge of the map, except for some dynamic obstacles, which can therefore show up un-expectedly. The management system must organize the team so as to complete all the requests made by users during the mission, optimizing some engineering relevant variables, such as the resources consumption of the robots and the com-pletion time of all assigned tasks.
The tasks that each robot will have to perform is to reach the user who required the intervention of the robot. We studied in particular two type of situations which are interesting for social interest: the passengers transport for a "smart Taxi" sys-tem and the home delivery for a team of drones.
The management of the task allocation to the team will be completely centralized, it therefore requires the presence of a supervisor that has to take all useful deci-sions to the resolution of the MRTA problem thanks to the full knowledge of the environment and the MRS.
The main contribution of this work is the design of reconfigurable modular archi-tecture, designed to address the problem of the MRTA as a problem of Binary Integer Linear Programming (BILP). The general architecture allows you to use the management system proposed in various scenarios, which have similar basic characteristics, but differences in the composition of the task and the context of application.
Capitolo 1
Introduzione
Negli ultimi decenni l’interesse per i Sistemi Multi-Robot (Multi Robot Systems, MRS) è cresciuto sempre di più. Grazie alle loro molteplici caratteristiche, queste squadre di robot sono state studiate per una vastissima gamma di scenari, dalla difesa[17] all’ambito industriale[9], e sono state proposte per l’esecuzione di compi-ti (task) sempre nuovi. La ricerca in questo ambito si è focalizzata con parcompi-ticolare attenzione su scenari di applicazione dinamici, dove i robots devono fare i conti con l’imprevedibilità e la mutevolezza dell’ambiente in cui si trovano.
L’interesse per questo tipo di sistemi ha origini prevalentemente ingegneristiche in quanto, rispetto ad un singolo robot, un MRS riesce a migliorare l’efficacia e l’ef-ficienza di un sistema robotico sia dal punto di vista delle prestazioni, sia rispetto alla robustezza e affidabilità del sistema.
I contesti in cui le performance assumono un ruolo decisivo sono quelli dove i com-piti da eseguire richiedono la collaborazione di più robot, che possono avere uguali o diverse abilità; o ancora scenari in cui la realizzazione di un singolo task da parte di ciascun robot contribuisce ad un aumento delle performance dell’intero sistema. La robustezza e l’affidabilità si possono ottenere più facilmente in un MRS, esso può essere infatti progettato e realizzato in modo tale da garantire due caratte-ristiche importanti: adattività e resistenza ai guasti (fault tolerance); un Sistema Multi-Robot che presenta entrambe le caratteristiche si definisce robusto.
L’adattività si riferisce alla capacità di un MRS di modificare il proprio comporta-mento nel tempo a seconda delle variazioni dovute a: ambiente dinamico, cambia-menti nella missione, cambiacambia-menti nella composizione o nelle abilità del sistema, in modo tale che le prestazioni globali possano essere migliorate, o quantomeno non degradate.
La fault tolerance è la capacità del MRS di porre rimedio a guasti dei singoli o ad errori di comunicazione, tra due o più robot, che possono verificarsi in qualsiasi momento durante la missione.[1]
Per queste ed altre ragioni, a partire dalla fine degli anni ’80 la comunità di ricerca 15
in ambito robotico si è attivata sempre di più nel campo della robotica cooperati-va, partendo con alcuni progetti come CEBOT [2], GOFER [3].
Il rapido progresso della robotica cooperativa e l’evoluzione delle tipologie di task da affrontare ha portato allo studio di scenari molto diversi tra loro, come ad esem-pio: rilevamento di dispositivi dannosi [17][4], spostamento e consegna di pacchi e oggetti [5], esplorazione di ambienti con veicoli terrestri [6] ed aerei[7], gioco del calcio[8].
Stimoli fondamentali che hanno dato, negli ultimi anni, un notevole impulso al-la ricerca sui MRS sono le competizioni di robotica, una delle più importanti è RoboCup[9]. L’ambiente RoboCup in cui il MRS deve eseguire i task specificati è altamente dinamico e include una squadra avversaria; in questo contesto dunque il progetto del sistema multi-robot si può considerare una delle principali sfide scientifiche da sviluppare nell’ambito della robotica cooperativa.
Obiettivo di questo lavoro è la progettazione di un’architettura software per la risoluzione centralizzata di un problema di assegnazione dei task ad una squadra di robot (Multi Robot Task Allocation, MRTA). Il sistema multi-robot considerato è omogeneo, ovvero ogni robot possiede le stesse abilità, e si muove all’interno di uno scenario di cui si conosce la mappa completa, ad eccezione di alcuni ostacoli dinamici, che possono dunque presentarsi in modo imprevisto.
Il sistema di gestione deve organizzare la squadra in modo tale da portare a ter-mine tutte le richieste effettuate dagli utenti durante la missione, ottimizzando alcune grandezze di rilevanza ingegneristica, come il consumo di risorse dei robot e il tempo di completamento di tutti i compiti assegnati. Il task che ogni robot dovrà eseguire consiste nel raggiungere l’utente che ha richiesto l’intervento del robot, si farà riferimento in particolare a due situazioni di interesse sociale: il tra-sporto passaggeri per un sistema di “taxi intelligenti” e la consegna a domicilio per una squadra di droni.
La gestione dell’assegnazione dei compiti alla squadra dovrà essere completamente centralizzata, si richiede dunque la presenza di un supervisor che, con una co-noscenza completa dell’ambiente e del MRS, prenda tutte le decisioni utili alla risoluzione del problema di MRTA.
Per la risoluzione del problema sopra descritto esistono in letteratura numero-sissime metodologie differenti. Prima di tutto dobbiamo fare una distinzione tra approccio distribuito e approccio centralizzato al problema di MRTA. Nella gestio-ne distribuita del problema di assegnaziogestio-ne dei task non vi è un unico supervisor che decide per la squadra, ma ogni robot prende delle decisioni autonomamente. In base alle strategie di interazione adottate si avranno comportamenti diversi della squadra e conseguenti risoluzioni del MRTA. L’interesse della ricerca per il
proble-17 ma del MRTA distribuito sta aumentando negli ultimi anni, nella letteratura più recente troviamo dunque principalmente sistemi di gestione de-centralizzati[11] o ibridi (in parte centralizzati e in parte distribuiti)[10] del MRS. Tuttavia dal punto di vista ingegneristico/applicativo i sistemi centralizzati vengono spesso preferiti a quelli distribuiti per ottimalità e sicurezza del risultato. Tralasciando dunque i confronti con i sistemi di gestione distribuiti poiché di scarso interesse per il no-stro lavoro, passiamo ad una breve presentazione delle principali metodologie che possiamo trovare in letteratura per la risoluzione del problema MRTA.
Possiamo distinguere tre tipi di architetture[13] per la risoluzione del problema MRTA: quelle basate su ottimizzazione combinatoria, architetture basate sul mer-cato, e quelle che si basano sul comportamento dei robot.
Nelle architetture basate su ottimizzazione combinatoria il problema di Task Al-location viene considerato come un problema di massimo (o minimo) vincolato. Viene definita una Funzione Utilità (Utility Function, UF) che rispecchi al meglio le esigenze e le specifiche del problema, tenendo conto delle grandezze e dei pa-rametri caratteristici del sistema che si vogliono massimizzare o penalizzare. Per ogni coppia (robot, task) viene dunque calcolata la rispettiva UF, ed in base alla sua natura e alle scelte implementative l’assegnazione dei compiti viene fatta in modo tale da massimizzare una Utility Function globale, che non è altro che una combinazione lineare di tutte le UF associate ad ogni coppia. In [7] viene presenta-ta un’architettura basapresenta-ta su programmazione lineare utilizzapresenta-ta per l’assegnazione di traiettorie ad una squadra di veicoli aerei autonomi con lo scopo di ottimizzare la loro coordinazione in volo.
Nelle architetture basate sul mercato vengono implementate strategie ispirate a quelle economiche, attraverso un approccio basato principalmente sul concetto di asta si fornisce un modo per coordinare le attività tra i robot. Un’asta è un proces-so di assegnazione di un insieme di beni o servizi ad una serie di offerenti in base alle loro offerte e a determinate regole dell’asta stessa. Questo tipo di approcci richiede uno scambio importante di informazioni (i.e. Contract Net Protocol[18]) tra i robot per quanto riguarda i task richiesti. Ogni robot fa un’offerta relativa ad un determinato task in base alle propria capacità di portarlo a termine. Il processo di negoziazione ha come obiettivo l’ottimizzazione di una certa UF che caratterizza le prestazioni della squadra. In [3] troviamo un esempio di Task Allo-cation in ambiente indoor in cui sono presenti task di complessità diverse.
Le architetture basate sul comportamento assegnano i task considerando, per ogni robot, il livello di impazienza e di acquiescenza rispetto ai compiti da eseguire. Questi aspetti motivazionali sono combinati fra loro in modo tale da formare una sorta di stima delle UF associate ad ogni coppia (robot, task). Troviamo un noto esempio di sistemi basati sul comportamento in [12] con l’architettura ALLIAN-CE.
Dopo aver impostato l’architettura del sistema di gestione del MRS si passa alla formalizzazione del problema di allocazione dei task vero e proprio, e quindi alla scelta dell’algoritmo più adeguato alla sua risoluzione. Tra gli algoritmi più utiliz-zati in letteratura troviamo: algoritmi per la Programmazione Lineare Binaria[7], Greedy Algorithm[14], Hungarian Algorithm.[6]
Il principale contributo di questo lavoro è il design di un’architettura modulare riconfigurabile, progettata per affrontare il problema del MRTA come un problema di Programmazione Lineare Intera Binaria (Binary Integer Linear Programming, BILP). La generalità dell’architettura permette di utilizzare il sistema di gestione proposto in vari scenari, che presentano caratteristiche fondamentali simili, ma composizione dei task e contesto di applicazione diversi.
La gestione del MRS è completamente centralizzata, vi è un supervisor che moni-tora continuamente lo stato dei robot e dell’ambiente, risolvendo quando necessario il problema di assegnazione dei compiti ai robot disponibili. L’assegnazione dei ta-sk è dunque dipendente dallo stato del robot, ma tutte le analisi di fattibilità e delle Utility Function coinvolte vengono elaborate completamente dal supervisor, a differenza dell’approccio market-based che troviamo ad esempio in [3], in cui vi è un central planner che interroga i robot sulle loro possibilità di eseguire tutti i task presenti e resta in attesa delle loro risposte prima di effettuare l’assegnazione. Nel nostro lavoro dunque un miglioramento che si ottiene è una maggiore velocità di risposta del sistema.
Per la risoluzione del problema di TA si è scelto il Metodo del Simplesso, uno dei più utilizzati in Programmazione Lineare Intera Binaria. In particolare si imple-menta una versione iterativa dell’algoritmo, poiché per far fronte ai cambiamenti ambientali e dello stato dei robot è necessario fare nuove assegnazioni dei task durante una missione. Anche in [3] troviamo l’operazione di ri-assegnazione dei task, in cui vediamo coinvolta l’intera squadra ad ogni iterazione. Nel nostro la-voro invece il re-assignment è parziale e dunque, coinvolgendo solo i robot liberi, richiede un costo computazionale minore.
Con il nostro sistema di gestione è garantita una soluzione ottimale, anche se locale, per il problema di TA. Possiamo notare un miglioramento rispetto alle architetture basate su comportamento confrontando un risultato ottenuto in [12]. Nell’articolo viene presentato un esempio in cui l’assegnazione basata su comportamento è lon-tana dall’ottimalità, mentre la nostra basata su Programmazione Lineare darebbe la soluzione ottima del problema.
Abbiamo testato il funzionamento dell’architettura su uno scenario simulato in cui una squadra di taxi deve soddisfare tutte le chiamate dei clienti. Si mostrerà che il problema di MRTA viene risolto correttamente anche aumentando la
com-19 plessità del sistema. Si dimostra la riconfigurabilità dell’architettura a partire dal designdella Funzione Utilità presentando un esempio di come può essere utilizzata per determinare andamenti diversi dell’evoluzione del sistema.
Il lavoro è così organizzato: nel Capitolo 2 viene presentata l’architettura modu-lare proposta, sono dunque descritti in modo approfondito i blocchi che la compon-gono. In particolare nel Capitolo 3 si riporta nel dettaglio il blocco che si occupa di risolvere il problema dell’allocazione dei task, blocco centrale di questo lavoro. Si fornisce una formulazione dettagliata del problema e delle tecniche di risoluzione adottate per gli scenari presi in esame. Si procede nel Capitolo 4 con l’esposizione della parte implementativa, si fornisce un’introduzione al software utilizzato ROS (Robot Operating System) e si presentano nel dettaglio alcune strutture ROS uti-lizzate per la realizzazione dell’architettura. Nel Capitolo 5 infine si presentano i risultati ottenuti in simulazione, testando l’architettura in due scenari diversi: trasporto passaggeri per un sistema di “taxi intelligenti” e la consegna a domicilio per una squadra di droni. Si può vedere che la riconfigurabilità dell’architettura permette al nostro Sistema di Gestione del MRS di essere adattato alla risoluzione del TA anche in scenari di tipo diverso.
Capitolo 2
L’Architettura modulare
Nel capitolo si descrivono nel dettaglio i quattro blocchi che compongono l’ar-chitettura modulare riconfigurabile in esame, per ogni blocco verranno specificate le parti che possono essere riprogrammate in base allo scenario in cui si vuole uti-lizzare l’architettura.
In Figura 2.1 è mostrato lo schema completo dell’architettura, dove i blocchi Tasks, e MRS determinano il tipo di scenario in cui intervenire, mentre i blocchi Manage-ment and Planninge Task Assignment svolgono tutte le funzioni utili alla risoluzione del problema di TA nello scenario considerato.
Figura 2.1 Schema a blocchi dell’architettura modulare riconfigurabile
2.1
Il Sistema Multi-Robot
I Sistemi Multi-Robot ci permettono di intervenire in moltissime situazioni in cui un aumento delle prestazioni e della robustezza rispetto al singolo robot fanno una grande differenza. Per lo sviluppo dell’architettura di gestione di un MRS è molto importante conoscere tutte le caratteristiche del sistema, così da sfruttare al meglio le sue potenzialità.
Nell’architettura progettata in questo lavoro, il blocco MRS (in Figura 2.2) relativo alla squadra di robot rappresenta l’insieme di tutti i robot presenti nello scenario, essi comunicano esclusivamente con il blocco Management and Planning.
Gli ingressi e le uscite che coinvolgono il MRS sono:
Ingressi:
• ASSEGNAZIONE TASK → ogni robot riceve il task da eseguire e il percorso per raggiungerlo
Uscite:
• STATO DEI ROBOT → ogni robot invia un messaggio con le proprie carat-teristiche: nome, posizione e orientazione nello spazio, completamento del task assegnato, livello di batteria, segnalazione di guasto
Figura 2.2 Blocco MRS con ingressi e uscite
Si possono trovare in letteratura diverse classificazioni dei Sistemi-Multi Ro-bot, [15][19] si riporta di seguito quella che abbiamo ritenuto essere più utile per
2.1. IL SISTEMA MULTI-ROBOT 23 l’obiettivo di questo lavoro.
Si fa una distinzione iniziale tra due categorie: il tipo di interazione tra robot e il tipo di sistema multi-robot.
Tipo di interazione tra robot • Tipologia di Obiettivo
– Individuale – Condiviso
• Consapevolezza degli altri (Awareness)
– Aware: i robot hanno un qualche tipo di informazione sugli altri com-ponenti del sistema
– Not Aware: i robots agiscono senza nessuna consapevolezza degli altri componenti del sistema
• Contributo del singolo agli obiettivi altrui
– Si, positivo: i robot con le proprie azioni contribuiscono anche al rag-giungimento dell’obiettivo altrui
– Si, negativo: i robot con le proprie azioni condizionano negativamente gli obiettivi altrui (MRS avversari)
– N o: i robot non intervengono negli obiettivi altrui • Tipologia di organizzazione
– Fortemente centralizzata: durante l’intera durata della missione le de-cisioni vengono prese dallo stesso robot (leader) stabilito all’inizio – Debolmente centralizzata: durante la missione più di un robot può
assumere il ruolo di leader
– Distribuita: i robot sono completamente autonomi nel prendere deci-sioni che riguardano gli altri, non esiste un leader
Tipo di sistema multi-robot • Composizione
– Omogenea: i robot sono identici da un punto di vista sia hardware che software.
– Eterogenea: i robot possono avere differenze sia sui dispositivi hardware che sulle procedure di controllo (software).
• Tipo di riorganizzazione della squadra in relazione agli imprevisti
– Deliberativa: permette ai membri del team di affrontare gli imprevisti fornendo una strategia di riorganizzazione complessiva dei comporta-menti di tutta la squadra. Dunque è previsto un piano a lungo termine che preveda l’utilizzo di tutte le risorse disponibili affinché venga portato a termine un obiettivo globale
– Reattiva: ciascun robot della squadra affronta gli imprevisti riorganiz-zando individualmente il proprio comportamento al fine di raggiungere il proprio obiettivo. Dunque dal leader viene fornito direttamente al robot coinvolto un piano per affrontare il problema in esame
Rispetto a questa classificazione il nostro Sistema Multi-Robot presenta le carat-teristiche riportate in Tabella 2.1.
TIPO DI INTERAZIONE TRA ROBOT
Tipologia di Obiettivi Individuale Condiviso
X
Contributo del singolo agli Si, positivo Si, negativo No
obiettivi altrui X
Consapevolezza degli altri Aware Not Aware
(Awareness) X
Tipologia di organizzazione Fortemente Debolmente Distribuita centralizzata centralizzata
X
TIPO DI SQUADRA
Composizione Omogenea Eterogenea
X
Tipo di riorganizzazione Deliberativa Reattiva
della squadra in relazione X
agli imprevisti
2.1. IL SISTEMA MULTI-ROBOT 25 La nostra squadra dunque è composta da robot che hanno un obiettivo comune, quello di soddisfare tutte le richieste che vengono effettuate dagli utenti nel tem-po. Ogni robot deve portare a termine un task che costituisce una piccola parte del’obiettivo globale, e in casi di emergenza può intervenire nell’esecuzione di un compito assegnato ad un altro componente della squadra.
Ogni robot possiede alcune informazioni sugli altri componenti, in particolare rile-va la presenza di altri robot se presenti nella propria area sensibile, e può ricevere altri tipi di informazione sulla squadra dal blocco Management and Planning, ad esempio in situazioni di emergenza.
L’organizzazione del MRS è fortemente centralizzata, la squadra viene gestita dal-lo stesso leader che prende qualsiasi tipo di decisione durante tutta la missione. Il comportamento di un MRS con queste caratteristiche è detto Cooperativo, altri esempi di scenari in cui vengono utilizzate squadre cooperative sono: lo sposta-mento di grandi materiali, la pulizia di ambienti[20], l’esplorazione di ambienti impervi e non noti[6], missioni di ricerca e recupero[21].
Inoltre la squadra di robot in esame è omogenea, i robot hanno le stesse capacità e possono muoversi nello spazio senza vincoli.
Come vedremo successivamente, nel blocco Management and Planning viene effet-tuata una pianificazione (path planning) di alto livello degli spostamenti dei robot, che permette anche di evitare la collisione con gli ostacoli (obstacle avoidance) pre-senti nello scenario. Il pianificatore utilizzato non si occupa invece del problema di collision avoidance, ovvero di garantire che non ci siano collisioni tra robot in movimento, poiché problemi come questo sono di livello inferiore e vengono dun-que delegati ad altri pianificatori.
In caso di imprevisti la squadra ha un comportamento reattivo, dal sistema cen-trale viene fornito un piano di riorganizzazione solo ai robot coinvolti.
Il Sistema Multi-Robot può variare in base allo scenario, l’architettura è pro-gettata per adattarsi ad un MRS con un numero variabile di robot, mentre tutte le altre caratteristiche della squadra viste fin’ora non possono variare.
2.2
I Task
Figura 2.3 Blocco Task con ingressi e uscite
Nel blocco Task viene specificato l’obiettivo globale che il Sistema Multi-Robot dovrà portare a termine e dunque anche le tipologie di task che i robot dovranno eseguire.
In Figura 2.3 è rappresentato il blocco Task, le uscite (in arancione) rappresentano le richieste degli utenti che arrivano durante la missione e che vengono poi inviate al Task Manager.
Riassumiamo di seguito le caratteristiche principali dei task nei due scenari che abbiamo preso in esame:
• Trasporto passeggeri con “taxi intelligenti”
Task globale → soddisfare tutte le chiamate dei clienti che arrivano durante la missione
Sub-task →il taxi deve raggiungere la posizione del passeggero e successiva-mente la sua destinazione
• Consegna a domicilio con una squadra di droni Task globale →consegnare tutti i pacchi in magazzino
2.2. I TASK 27 La riconfigurabilità dell’architettura ci permette di gestire scenari e obiettivi diver-si, con semplici modifiche al blocco principale di gestione del sistema Management and Planning si può adattare la risoluzione del problema di Task Assignment al particolare tipo di task al quale siamo interessati.
In questo lavoro ci occuperemo di due scenari diversi, e vedremo dunque varie tipologie di task, di cui daremo una formalizzazione dettagliata nel Capitolo 5 insieme alla descrizione degli casi di studio.
2.3
Il modulo Management and Planning
Figura 2.4 Blocco Management and Planning con ingressi e uscite
In Figura 2.4 è mostrato il blocco Management and Planning, esso all’interno dell’architettura si occupa quasi completamente della gestione effettiva dell’asse-gnazione, monitorando lo stato di robot e task e pianificando i percorsi che devono compiere i robot per poter eseguire i propri compiti.
Suddividiamo tutte le funzioni di questo blocco in due sotto-blocchi: il Task Managemente il Path Planning.
2.3.1
Task Management
Nella parte sinistra dello schema in Figura 2.4 abbiamo il sotto-blocco Task Management, o gestore dei task. Esso si occupa di monitorare l’evoluzione dei task nel tempo, stabilisce quali sono i compiti da assegnare e provvede ad inviarli al blocco Task Assignment. I compiti da gestire provengono da due fonti diverse: il blocco Task e il sotto-blocco Path Planning.
In particolare il gestore riceve dal blocco Task le nuove richieste degli utenti, men-tre dal Path Planning riceve i task che sono stati completati, e quelli che invece devono essere riassegnati. Quest’ultimo caso può presentarsi nel momento in cui un robot abbia dei problemi, ad esempio in caso di rottura del robot o di scarica
2.3. IL MODULO MANAGEMENT AND PLANNING 29 delle batterie, per cui non riesca a portare a termine il compito a lui assegnato. Le grandezze che vengono coinvolte nel sotto-blocco Task Management sono:
Ingressi :
• NUOVI TASK → richieste degli utenti, cambiano a seconda dello scenario • STATO DEI TASK → il gestore riceve dal sotto-blocco Path Planning il
vettore dei task completati e il vettore dei task che vanno riassegnati Uscite:
• TASK DA ASSEGNARE → i task che devono ancora essere assegnati ven-gono inviati al blocco Task Assignment per essere assegnati
2.3.2
Path Planning
Nella parte destra dello schema in Figura 2.4 abbiamo il sotto-blocco Path Plan-ning. Esso oltre a svolgere la sua principale funzione di pianificatore dei percorsi, si occupa anche di monitorare continuamente lo stato dei robot, e in base alle in-formazioni che riceve li classifica come robot: in esecuzione, in ricarica, disponibili. Tenendo sotto controllo anche il livello di batteria, il pianificatore può decidere se mandare o meno i robot in ricarica, oppure far intervenire alcuni robot nell’esecu-zione di compiti assegnati ad altri.
Gli ingressi e le uscite coinvolti nel sotto-blocco Path Planning sono:
Ingressi :
• MAPPA → la mappa dell’ambiente in cui i robot si muovono è nota e viene letta dal pianificatore affinché possa calcolare i percorsi necessari
• ASSEGNAZIONE → le assegnazioni robot-task stabilite dal blocco Task As-signment vengono ricevute dal pianificatore e diventano, per i robot, punti di partenza e punti di arrivo
• STATO DEI ROBOT → il pianificatore (planner) riceve da ogni robot un messaggio con il suo stato: nome, posizione e orientazione nello spazio, completamento del task assegnato, livello di batteria, segnalazione di guasto Uscite:
• ASSEGNAZIONE TASK → il planner calcola i percorsi che devono compiere i robot per eseguire i compiti loro assegnati e invia dunque ad ogni robot il task da eseguire e il percorso per raggiungerlo
• ROBOT DISPONIBILI → dal monitoraggio dello stato dei robot il planner capisce quali sono i robot pronti a ricevere un nuovo task e invia dunque al blocco Task Assignment il vettore dei robot disponibili
• STATO DEI TASK → dal monitoraggio dello stato dei robot il planner ca-pisce quali sono i task completati e quelli che vanno riassegnati e lo comunica al sotto-blocco Task Management
• TEMPI DI PERCORRENZA → vengono calcolati dal pianificatore i tempi di percorrenza dei cammini minimi che permettono ai robot di arrivare ai task presenti nello scenario, le informazioni vengono poi inviate al blocco Task Assignmentche le utilizzerà per calcolare assegnazioni ottime robot-task
2.3.3
Pianificazione
Nella nostra architettura il modulo di pianificazione dei percorsi (path planning) viene considerato una “scatola nera” (black box), in quanto non ci siamo occupati del design di un nuovo algortmo di pianificazione, ma abbiamo utilizzato algoritmi già esistenti e disponibili in letteratura, adattandoli alla struttura implementativa dell’architettura.
Per poter simulare l’ambiente abbiamo utilizzato delle mappe che vengono uti-lizzate dal planner come grafi non orientati su cui poter fare pianificazione. In particolare i nodi del grafo rappresentano i punti dello spazio che i robot dovranno raggiungere (way points), e gli archi rappresentano il percorso per passare da un way point al successivo.
Per la pianificazione abbiamo scelto l’Algoritmo di Dijkstra[22], un algoritmo mol-to nomol-to in letteratura e perfettamente adatmol-to al nostro caso, in quanmol-to si utilizza per cercare i cammini minimi (percorsi più brevi tra due nodi) in un grafo con o senza ordinamento, ciclico e con pesi non negativi sugli archi.
Dalla lunghezza dei cammini minimi trovati con la pianificazione, il sotto-blocco Path Planningricava i tempi di percorrenza di ciascun cammino, essendo nota la ve-locità dei robot. Queste informazioni vengono mandate al blocco Task Assignment con cui questo può calcolare le assegnazioni robot-task più vantaggiose.
Ripianificazione
Gli scenari trattati in questo lavoro presentano ostacoli, sia statici che dinamici. In letteratura esistono molti algoritmi di complessità diverse che permetteno ai
2.3. IL MODULO MANAGEMENT AND PLANNING 31 robot di evitare gli ostacoli (obstacle avoidance) durante i loro spostamenti. Poiché la pianificazione non è punto centrale di questa trattazione, il problema di obstacle avoidance viene risolto in due modi abbastanza semplici a seconda della tipologia di ostacolo:
• Ostacoli statici: sono fissi e presenti durante tutta la missione.
La collisione viene evitata partendo dalla modifica del grafo che rappresenta l’ambiente, in quanto gli ostacoli vengono trattati come nodi del grafo i cui archi entranti e uscenti hanno un peso infinito e saranno quindi sicuramente scartati dall’Algoritmo di Dijkstra in fase di pianificazione.
• Ostacoli dinamici: sono fissi o mobili, arrivano in modo casuale.
Il problema di obstacle avoidance viene risolto con una ripianificazione dei percorsi effettuata negli istanti in cui arrivano nuovi ostacoli.
Nel blocco Management and Planning il sotto-blocco Path Planning è la parte riconfigurabile. In particolare è possibile utilizzare un algoritmo di path planning diverso, si può aggiungere un algoritmo che faccia anche pianificazione del moto per risolvere il problema della collisione tra robot, si può implementare un modulo di obstacle avoidance diverso. Inoltre è possibile modificare la mappa dell’ambiente adattando il grafo al nuovo scenario.
2.4
Il modulo Task Assignment
Figura 2.5 Blocco Task Assignment con ingressi e uscite
In Figura 2.5 è rappresentato il blocco che si occupa dell’assegnazione dei task. Esso costituisce il cuore dell’architettura in esame, e ne costituisce la parte che ab-biamo completamente sviluppato in questo lavoro. Per questo motivo il capitolo successivo è interamente dedicato alla descrizione dettagliata del funzionamento di questo blocco e all’analisi delle sue parti riconfigurabili.
Gli ingressi e le uscite coinvolti nel blocco Task Assignment sono:
Ingressi :
• TASK DA ASSEGNARE → dal blocco Task Management arrivano i task che devono ancora essere assegnati ai robot disponibili
• TEMPI DI PERCORRENZA → per il calcolo di assegnazioni robot-task otti-me il blocco Task Assignotti-ment utilizza le informazioni sui tempi di percorrenza dei cammini minimi calcolate dal pianificatore
• ROBOT DISPONIBILI → è il vettore che viene inviato dal blocco Mana-gement and Planning con i robot che sono disponibili a ricevere un nuovo task
2.4. IL MODULO TASK ASSIGNMENT 33 Uscite:
• ASSEGNAZIONE → le assegnazioni robot-task calcolate vengono inviate al pianificatore che provvederà a comunicarle ai robot interessati
La riconfigurabilità di questo blocco sta nel design di un indicatore fonda-mentale per la risoluzione del problema di assegnazione dei task, la Funzione di Utilità. Nel capitolo successivo si descrive dettagliatamente questa funzione e co-me è possibile modificarla per adattare il blocco Task Assignco-ment allo scenario considerato.
Capitolo 3
Il modulo Task Assignment
Negli ultimi decenni il mondo della ricerca in ambito robotico ha investito sem-pre di più nello studio dei Sistemi Multi-Robot e in particolare nella coordinazione di questi sistemi. In questo contesto ha attirato molto interesse il problema della ripartizione dei compiti tra più robot (Multi-Robot Task Allocation, MRTA), dive-nendo un argomento chiave di ricerca a sé stante.
Se si ha a che fare con MRS cooperativi, ci si imbatte inevitabilmente nella questio-ne fondamentale: quali robot dovrebbero eseguire quali compiti affinché la squadra raggiunga il suo obiettivo globale in modo cooperativo? Si può rendere la divisio-ne dei compiti ottima rispetto ad alcuni aspetti desiderati? Rispondere a queste domande significa occuparsi di risolvere il problema di MRTA, che costituisce il nodo centrale di questo lavoro.
Partiamo dalla definizione di “compito” o task: con esso si intende un sotto-obiettivo che è necessario portare a termine per raggiungere l’sotto-obiettivo generale del sistema, ogni task può essere raggiunto indipendentemente da altri sotto-obiettivi. In questo capitolo viene inizialmente riportata una classificazione del problema di ripartizione dei compiti, successivamente si formalizza il particolare problema di MRTA preso in esame e si riporta infine una descrizione dell’approccio utilizzato per la risoluzione di quest’ultimo.
3.1
Tassonomia del problema di MRTA
In letteratura vengono presentate tassonomie che mappano le diverse categorie di MRTA in modelli matematici appartenenti ad altri ambiti come la ricerca ope-rativa e l’ottimizzazione combinatoria, creando dunque un parallelo importante tra la robotica e questi campi di ricerca.
Presentiamo di seguito la tassonomia che si ritiene più adeguata al nostro scopo, 35
quella di Gerkey e Matarić[23], in cui il problema di MRTA viene categorizzato rispetto a tre assi, come possiamo vedere in Figura 3.1(a).
(a) (b)
Figura 3.1 a) Rappresentazione della tassonomia di Gerkey e Matarić lungo tre assi [16] b) Rappresentazione della tassonomia per il caso in esame
Tassonomia di Gerkey e Matarić lungo i tre assi: • Tipo di Task
– Single-Robot task (SR) → serve un solo robot per eseguire un task – Multi-Robot task (MR) → servono più robot per eseguire alcuni task • Tipo di Assegnazione
– Instantaneous Assignment (IA) → l’allocazione è istantanea, non c’è pianificazione di assegnazioni future (un esempio: consegna di un pac-chetto al destinatario)
– Time-extended Assignment (TA) → vengono fatte assegnazioni sia istantanee sia per il futuro, a ciascun robot dunque vengono assegnati più task che devono essere eseguiti secondo un determinato programma (un esempio: sorveglianza dell’ingresso di un edificio per la difesa dagli intrusi)
• Tipo di Robot
– Single-Task robot (ST) → ogni robot può eseguire un solo task alla volta
3.2. FORMULAZIONE DEL PROBLEMA DI MRTA 37 – Multi-Task robot (MT) → alcuni robot possono eseguire più task
con-temporaneamente
Rispetto a questa classificazione il problema di assegnazione dei task di cui ci occupiamo in questo lavoro presenta le caratteristiche evidenziate in rosso in Figura 3.1(b). Ovvero è un problema di tipo Single-Task robot, Single-Robot task, Instantaneous Assignment (SR-ST-IA).
3.2
Formulazione del problema di MRTA
Dall’abbondanza di studi che possiamo trovare in letteratura si evince un gran-de interesse per problemi di Task Assignment di tipo SR-ST-IA, non solo per la grande varietà di contesti in cui esso può essere applicato, ma anche e soprattutto perché questo caso particolare di MRTA si può considerare un’istanza del Pro-blema di Assegnazione Ottima (Optimal Assignment Problem, OAP), argomento centrale della ricerca operativa.
Poiché vogliamo occuparci di un problema di MRTA in un contesto di ottimizza-zione, dobbiamo stabilire in fase di design cosa vogliamo ottimizzare. In un mondo ideale potremmo pensare di ottimizzare direttamente le prestazioni complessive del sistema, ma nella realtà spesso è difficile anche solo quantificarle.
Per avvicinarci il più possibile ad una assegnazione ottima dei compiti dobbiamo dunque ricorrere ad una sorta di stima delle prestazioni, detta Funzione Utilità (Utility Function, UF). Questa funzione rappresenta un concetto che accomuna molte discipline tra cui l’economia, la teoria dei giochi, la ricerca operativa, e an-che dunque il coordinamento di Sistemi Multi-Robot.
Essa nasce dalla considerazione che è possibile, all’interno di un sistema che deve eseguire dei compiti, stimare il valore (o il costo) di esecuzione di ogni azione. A seconda del contesto, la Funzione Utilità viene anche detta fitness, valutazione o costo. Nell’ambito dei Sistemi Multi-Robot, la formulazione della UF può variare molto, partendo da sofisticati metodi basati sulla pianificazione fino ad arrivare a metriche più semplici basate su misure ottenute dai sensori.
In ogni sistema in cui si deve risolvere un problema di Task Allocation è dunque ragionevole ipotizzare che ci sia un modulo adibito al confronto e alla selezione, tra una serie di alternative disponibili, delle UF che risultano più vantaggiose al fine del raggiungimento dell’obbiettivo globale del sistema in esame.
In questo lavoro è proprio il blocco Task Assignment ad occuparsi del calcolo delle UF necessarie e della loro successiva selezione. Si presenta dunque la formalizza-zione della Funformalizza-zione Utilità che abbiamo scelto di utilizzare per risolvere il nostro problema di assegnazione dei compiti. Si vedrà successivamente che questa
funzio-ne può essere un importante strumento di design con cui è possibile riconfigurare l’architettura in base allo scenario in esame.
3.2.1
Funzione Utilità
La nostra architettura gestisce il problema di assegnazione dei compiti in modo completamente centralizzato, e sarà proprio il supervisor del sistema a calcolare tutte le UF tra cui saranno poi scelte quelle ottime, come vedremo più avanti. Per poter definire la UF utilizzata per la nostra architettura dobbiamo dunque assumere che il supervisor del sistema sia sempre in grado di calcolare le Funzioni Utilità per ogni robot relativamente a ciascun task presente nello scenario.
La fase di calcolo delle Funzioni Utilità prevede che il gestore del sistema faccia la stima di una UF per ogni coppia roboti-taskj, dove roboti è l’i-esimo robot di-sponibile a ricevere assegnazioni e taskj è il j-esimo task da eseguire al momento della stima.
Dati:
• R: vettore dei robot disponibili di dimensione variabile n • T : vettore dei task da eseguire di dimensione variabile m Si definisce: Uritj = max n 0, Pritj − CRritj o (3.1) In (3.1) troviamo l’espressione della Utility Function associata ad ogni possibile assegnazione robot(ri) − task(tj), ∀ ri ∈ R e ∀ tj ∈ T.
Se ri può eseguire tj, la UF è definita come la differenza (positiva) tra una funzione che esprime le Prestazioni(P ) e una che esprime il Consumo Risorse(CR) che si avrebbero se il robot ri eseguisse il task tj. Se ri non è in grado di eseguire tj la UF è definita nulla.
Data in (3.1) la UF associata ad una coppia generica ri − tj, si definisce la Funzione Utilità Globale come la combinazione lineare di tutte le Uritj.
Dunque dati n × m coefficienti aij, ∀ri ∈ R, ∀tj ∈ T si ha: U F =X
ri,tj
3.3. RISOLUZIONE DEL PROBLEMA MRTA 39 Indicando con i il robot ri, ∀i = 1, . . . , n, e con j il task tj, ∀j = 1, . . . , m, si hanno in (3.3) e (3.4) le espressioni delle funzioni P e CR per la generica assegna-zione i − j.
Pij = fex(texij) + ft(taj) (3.3)
CRij = fr(lci) (3.4)
Con:
• fex(texij) → funzione che determina l’influenza del tempo di esecuzione (tex)
sulle Prestazioni. In particolare texij è la stima del tempo impiegato dal
robot ri per eseguire il task tj
• ft(taj) →funzione che determina l’influenza del tempo di arrivo(ta) del task tj sulle Prestazioni
• fr(lci) →funzione che determina l’influenza del livello di carica(lc) del robot ri sul Consumo Risorse
Le funzioni fex(texij), ft(taj)e fr(lci)rappresentano alcuni degli aspetti
riconfi-gurabili dell’architettura in esame, esse sono infatti importanti strumenti di design con cui è possibile adattare la Funzione Utilità allo scenario a cui siamo interessa-ti.
A dimostrazione di questo nel Capitolo 5 sono presentate le diverse espressioni delle funzioni di design e dunque delle UF utilizzate nei due contesti che abbiamo studiato.
3.3
Risoluzione del problema MRTA
Il particolare problema di assegnazione dei compiti ad un Sistema Multi-Robot di tipo ST-SR-IA rappresenta la sotto-categoria di MRTA che comprende i casi in cui si cercano assegnazioni uno a uno tra task singolo-robot indipendenti e robot singlo-task indipendenti. In letteratura troviamo molti metodi di risoluzione del problema per questa specifica sotto-categoria, tra questi possiamo individuare tre categorie:
• Metodi basati su programmazione lineare: il Task Assignment viene for-mulato come un problema di programmazione lineare binaria e risolto con algoritmi di ottimizzazione combinatoria. Si ha un esempio in [7].
• Metodi basati su aste: vengono implementate strategie ispirate a quelle eco-nomiche, attraverso un approccio basato principalmente sul concetto di asta. Ogni robot fa la sua offerta in base alla sua possibilità di esecuzione di un task. Si ha un esempio in [25].
• Metodi basati su campi potenziali: la procedura che accomuna questi metodi prevede che ogni robot (oppure un sistema centrale), calcoli un campo po-tenziale sovrapposto all’ambiente in cui si trova, per poi muoversi su di esso seguendo il gardiente del campo fino a raggiungere un minimo locale. Si ha un esempio in [24].
3.3.1
Assegnazione dei task come un problema di
program-mazione lineare
L’approccio che è stato scelto per questo lavoro è la programmazione lineare. Avendo a che fare in particolare con un problema di assegnazione di tipo ST-SR-IA useremo la Programmazione Lineare Intera Binaria (Binary Integer Linear Programming, BILP), questa ci permetterà di fare Task Assignment utilizzando algoritmi robusti esistenti in letteratura che danno soluzioni ottime al problema. In (3.5) troviamo una prima formalizzazione del nostro problema di MRTA. Dati n il numero di robot disponibili e m il numero di task da assegnare, siano aij ∈ {0; 1} n × m coefficienti e Uij la Funzione Utilità associata all’assegnazione i − j, allora il problema di MRTA può essere formulato in questo modo:
max A P i,j aijUij P i aij ≤ 1, ∀j = 1, . . . , m (vincolo SR) P j
aij ≤ 1, ∀i = 1, . . . , n (vincolo ST)
A ∈ {0; 1}n×m di elementi {aij}
(3.5)
Risolvere un problema di assegnazione di tipo ST-SR-IA di m task per n robot significa dunque trovare la matrice A degli n × m coefficienti aij ∈ {0; 1} tali che sia risolto il problema di massimo vincolato in (3.5), ovvero tali che sia massima la combinazione lineare delle UF associate ad ogni coppia roboti− taskj, rispetto alle n × mvariabili aij vincolate ad essere soluzioni del sistema di equazioni in (3.5). La matrice A è detta Matrice di Assegnazione (Assignment Matrix), utilizzando
3.3. RISOLUZIONE DEL PROBLEMA MRTA 41 la programmazione lineare binaria gli elementi di A potranno assumere soltanto il valore 0 oppure 1, in particolare si avrà un’assegnazione roboti − taskj solo in corrispondenza di aij = 1.
Possiamo dunque vedere come la BILP si presta molto bene alla risoluzione del nostro problema di MRTA, in quanto la Funzione Utilità complessiva è combina-zione lineare delle Uij, e inoltre siamo interessati ad avere informazioni solo su quali siano le assegnazioni tra robot e task e quali no, dunque una varibile binaria rappresenta perfettamente questo tipo di situazione.
In letteratura possiamo trovare moltissimi algoritmi creati proprio per la riso-luzione di questo particolare problema di OAP, tra questi si sceglie il Metodo del Simplesso, presentato nel paragrafo successivo insieme all’algoritmo completo di assegnazione dei task.
3.3.2
Algoritmo iterativo per l’assegnazione dei task
Si formalizza ora il problema in (3.5) come un problema di programmazione lineare intera binaria in forma canonica.
Dati u vettore delle funzioni utilità, a vettore delle incognite, C matrice dei vincoli e b vettore dei limiti superiori sulle incognite, si definisce:
max a u Ta Ca ≤ b
0 ≤aij ≤ 1, con aij ∈ Z ∀j = 1, . . . , m ∀i = 1, . . . , n
(3.6)
Il problema in (3.6) differisce da quello in (3.5) principalmente nella formalizzazione dei vincoli, compito dell’algoritmo di risoluzione sarà dunque quello di trovare il vettore delle incognite a che rispetti i vincoli di disuguaglianza e massimizzi la funzione obiettivo uTa.
In particolare vediamo che la funzione obiettivo da massimizzare si presenta come il prodotto scalare tra due vettori le cui espressioni derivano da grandezze che abbiamo già definito.
Siano A la Matrice di Assegnazione di n × m elementi aij e U la Matrice di Utilità di n × m elementi Uij, a partire da queste due matrici si definiscono in (3.7) i due vettori a e u.
Con Ai si indica la i-esima riga della matrice A e con Ui si indica la i-esima riga della matrice U, per i = 1, . . . , n. Ogni riga di A e di U ha m elementi, dunque il
vettore a ha dimensioni (n · m) × 1 mentre uT ha dimensioni 1 × (n · m). a= AT1 AT 2 . . . AT n u= U1T UT 2 . . . UT n → uT =U 1 U2 · · · Un (3.7)
Dalle definizioni in (3.7) possiamo ricavare la relazione U F =X
ri,tj
aijUritj = u
Ta (3.8)
da cui notiamo che la funzione obiettivo da massimizzare in (3.6) è proprio la UF globale definita in (3.2).
In (3.6) troviamo una nuova formalizzazione dei vincoli ST-SR-IA, espressi me-diante la matrice C. I prodotti tra le righe di C e il vettore delle incognite a corrispondono esattamente ai vincoli espressi in (3.5), in cui ogni vincolo ha limite superiore 1 per cui si avrà b = 1(m·n×1).
La matrice C ha dimensioni (n + m) × (n · m), essa assume una forma particolare che viene riportata in (3.9), al crescere delle dimensioni del sistema variano le sue dimensioni ma non la sua struttura.
L’ultimo vincolo di (3.6) lo imponiamo sulle incognite aij, affinché assumano solo il valore 0 oppure 1, in modo tale da riportarci al caso di Programmazione Lineare Intera Binaria che fa al caso nostro.
C= 111 112 · · 11m 0 0 · · 0 · · · · · · · · 0n1 0n2 · · 0nm 011 012 · · 01m 121 122 · · 12m 0 0 · · 0 · · · · 0n1 0n2 · · 0nm · · 011 012 · · 01m · · · · · · · · 0 0 · · 0 1n1 1n2 · · 1nm Im×m Im×m · · Im×m (3.9) Data la definizione in (3.6), per la risoluzione del nostro problema di BILP abbia-mo scelto una procedura numerica efficente abbia-molto nota in letteratura detta Metodo del Simplesso (Simplex Method).
L’algoritmo viene solitamente formulato su problemi di LP posti in forma standard, dove si deve cioè massimizzare(o minimizzare) una funzione lineare sottoposta a
3.3. RISOLUZIONE DEL PROBLEMA MRTA 43 vincoli di uguaglianza(e non disuguaglianza come è invece per la forma canonica), e in cui le variabili siano positive o nulle. Tuttavia si può sempre passare da forma canonica a forma standard attraverso una semplice operazione di somma, o sot-trazione, a seconda della necessità.
Riprendendo la nostra formulazione in forma canonica in (3.6), abbiamo già visto che si vuole massimizzare la funzione obiettivo uTa rispetto al vettore delle inco-gnite a sottoposte ai vincoli di disuguaglianza Ca ≤ b.
Se a tale formulazione si somma(si sottrae) una variabile chiamata “di slack” (“di surplus”) si perviene al problema di BILP equivalente in forma standard, in quanto si avrà che: Cka ≤ bk⇔ Cka+ yk= bk con yk ≥ 0 ∀k = 1, . . . , n · m
Ad ogni iterazione il Metodo del Simplesso trasforma il sistema dei vincoli di ugua-glianza di partenza, risolvendoli utilizzando diversi set di variabili, in un sistema equivalente chiamato tabella del simplesso, su cui applica una serie di trasfor-mazioni fino a trovare la soluzione di base ammissibile ottima. Si definisce base ammissibile una base per il sistema Ca = b che sia linearmente indipendente alla matrice A. Il metodo necessita di una soluzione di base ammissibile del sistema per iniziare, per poi muoversi lungo il perimetro della regione ammissibile passando, ad ogni iterazione, da una soluzione di base (feasible solution) ad una adiacente di valore maggiore, fino al raggiungimento dell’ottimo, oppure fino a quando non si determini che il problema è illimitato(infeasible solution).
Per l’implementazione del Metodo del Simplesso si utilizza la libreria open-source GLPK (GNU Linear Programming Kit), essa ha lo scopo di risolvere problemi di programmazione lineare su larga scala, programmazione intera mista (Mixed Inte-ger Linear Programming, MILP), e altri problemi connessi a questi, tra cui anche problemi di BILP. È un insieme di routine scritte in linguaggio ANSI C e organiz-zate in una libreria disponibile gratuitamente in rete[26].
Per il Metodo del Simplesso esiste la routine glp_simplex, la cui espressione è: int glp_simplex (glp_prob ∗lp, const glp_smcp ∗parm)
Riportiamo in Algoritmo 1 lo pseudocodice per la procedura implementata nel nostro blocco Task Assignment per la risoluzione del problema di BILP (3.6) equi-valente a quello di assegnazione (3.5) con la routine glp_simplex.
Al passo 2 viene creato l’oggetto “problema” lp, al passo 3 si caricano in lp tutte le informazioni che descrivono il problema da risolvere: la matrice dei vincoli C, calcolata a partire da n e m come in (3.9), il vettore dei limiti b, il vettore delle incognite a, il vettore delle funzioni utilità u, i vincoli sulle variabili aij. Tutti i dati del problema vengono caricati in lp tramite apposite routine della libreria
Algorithm 1 Metodo del Simplesso implementato con la libreria GLPK 1: procedure SimplexMethod(n, m, u)
2: lp ← glp_create_prob(); 3: load the data of the problem in lp 4: glp_simplex(lp, NULL); 5: z ← glp_get_obj_val(lp); 6: for k ←1, n · m do 7: ak ← glp_get_col_prim(lp, k); 8: end for 9: end procedure
GLPK. Al passo 4 viene effettivamente risolto il problema di LP con il Metodo del Simplesso, la routine glp_simplex riceve in ingresso il problema definito sopra lp, e il parametro parm viene settato a NULL, in questo modo il solver funzionerà nelle sue impostazioni di default. Una volta trovata la soluzione al problema, essa viene salvata, insieme ad altre informazioni, in lp. Si può poi accedere alla soluzione e alle informazioni con altre routine, quella che troviamo al passo 6 carica in z la soluzione ottima trovata, mentre al passo 7 vengono caricate in a le componenti della base ammissibile ottima trovata.
In Algoritmo 1 abbiamo descritto la procedura SimplexMethod(), vediamo ora come questa viene usata dal blocco Task Assignment per la risoluzione del problema di assegnazione dei compiti nel Sistema Multi-Robot.
Si riporta in Algoritmo 2 lo pseudocodice dell’algoritmo completo di assegnazione dei task.
Algorithm 2 Algoritmo di Assegnazione dei compiti per il Sistema Multi-Robot Input: assignment, accident, R, T , tex
Output: A
1: if assignment= true ∨ accident = true then 2: set n ← R.size() and m ← T.size()
3: if n >0 ∧ m > 0 then
4: compute the matrix U in function of the inputs R, T , tex 5: obtain the vector u from the matrix U
6: a ← SimplexM ethod(n, m, u)
7: obtain the matrix A from the vector a 8: end if
9: end if
3.3. RISOLUZIONE DEL PROBLEMA MRTA 45 missione possono crearsi delle situazioni in cui diventa necessario calcolare una nuo-va assegnazione, che nel nostro caso non coinvolgerà tutta la squadra ma soltanto i robot ancora disponibili e i task che sono rimasti da eseguire. La ri-assegnazione ci permette dunque di far fronte a vari tipi di cambiamenti, a partire da quelli ambientali fino a quelli riguardanti lo stato di qualche robot.
Definiamo due variabili booleane assignment (assegnazione) e accident (impre-visto), esse valgono false finché non si presentano situazioni particolari che deter-minano il settaggio del loro valore a true. Nel dettaglio, le situazioni che rendono necessaria un’operazione di ri-assegnazione, e dunque di ricalcolo dell’Algoritmo 2, vengono elencate di seguito, specificando per ognuna quale variabile booleana viene coinvolta.
• arriva un nuovo task da eseguire ⇒ assignment = true
• un robot ritorna disponibile e sono rimasti task da eseguire ⇒ assignment = true
• un robot si rompe ⇒ accident = true
• un robot si scarica prima di aver completato il task a lui assegnato ⇒ accident = true
Altre situazioni in cui può essere necessaria una ri-assegnazione dei compiti possono essere la presenza di ostacoli lungo il percorso di un robot, o la presenza di robot stessi. In questi casi il blocco Task Assignment prende dei provvedimenti. Sia k ∈ N il passo di iterazione corrente e si richiamino R, il vettore di robot dispo-nibili di dimensione variabile n(k) e T , il vettore di task da eseguire di dimensione variabile m(k). Dati i il robot i-esimo di R e j il task j-esimo di T , per verificare se durante l’esecuzione di un task un robot abbia incontrato un impedimento, il blocco Task Assignment controlla che sia rispettata la disuguaglianza in (3.10).
texij(k) − texij(0) < Uij (3.10)
Richiamando una grandezza già vista in (3.3), con texij(0) si indica il tempo di
esecuzione del task j per il robot i calcolato nell’istante iniziale, ovvero nel mo-mento in cui il blocco ha calcolato l’assegnazione i-j, mentre con texij(k)si indica il
tempo di esecuzione associato alla stessa coppia ma calcolato al passo di iterazione corrente.
La verifica viene effettuata solo se texij(k) > texij(0), poiché se texij(k) ≤ texij(0)
il robot sta impiegando un tempo inferiore a quello stimato per eseguire il task. Se la disuguaglianza non viene rispettata, e dunque texij(k) − texij(0) ≥ Uij
per qualche 1 ≤ i ≤ n(k) e 1 ≤ j ≤ m(k) allora anche in questo caso il blocco Task Assignment metterà la variabile booleana imprevisto a true e si avrà una nuova iterazione dell’Algoritmo 2.
Capitolo 4
Implementazione dell’Architettura
In questo capitolo si fornisce un’introduzione al software ROS (Robot Operating System) utilizzato per l’implementazione dell’architettura progettata. Verranno descritti gli strumenti principali con cui è stata realizzata la struttura SW del nostro sistema di gestione del MRS. Si descriverà infine il pacchetto del software ROS utilizzato per la visualizzazione dei risultati in un ambiente 3D.
In Appendice A si riportano le parti fondamentali del codice creato.
4.1
Introduzione a ROS
Di fronte al continuo progesso della tecnologia nell’ambito della robotica e ai crescenti obiettivi sempre più audaci che essa si pone, lo sviluppo in ambito soft-ware è divenuto non meno difficoltoso. Programmare robot, e a maggior ragione una squadra di robot, richiede di abbandonare la sicurezza dello sviluppo software classico e di immergersi nel mondo fisico, nella sua casualità, nel suo essere asin-crono, dove l’unica consapevolezza di ciò che accade è data dai sensori e un minimo errore può avere grandi ripercussioni sull’intero sistema, dove le risorse in termini di memoria, processori, energia di alimentazione sono limitate.
Programmare robot è una sfida che va ben oltre alle capacità del singolo ricerca-tore. Dinanzi alle sopra citate difficoltà negli ultimi anni sono stati molteplici i f ramework realizzati dalle varie comunità di ricercatori, tra questi noi abbiamo scelto di utilizzare ROS.
ROS è un software gratuito sia per l’ambito di ricerca che per fini commer-ciali. Ciò ha favorito fin da subito il suo sviluppo nel corso degli anni grazie al contributo della comunità di ricerca mondiale, contributo che è divenuto uno dei suoi punti di forza. Esso consiste in una collezione in continua crescita di librerie software e strumenti open source progettati al fine di aiutare gli sviluppatori nella
realizzazione di applicazioni robotiche. Acronimo di Robot Operating System, a discapito del nome non si identifica in un sistema operativo nel senso stretto del nome. Viene definito infatti come meta-operating system, inglobando le caratte-ristiche tipiche di un vero e proprio sistema operativo (astrazione dell’hardware sottostante, gestione dei processi, gestione dei dispositivi) ma con l’aggiunta di elementi tipici di un middleware (fornisce l’infrastruttura per la comunicazione tra processi/macchine differenti), e di un framework (strumenti per lo sviluppo, debugging e simulazione). ROS opera essenzialmente su piattaforme Unix-Based, anche se sono numerevoli le piattaforme sperimentali. Attualmente supporta tre differenti linguaggi: C++, Phyton, LISP.
I principali vantaggi che si possono ottenere dall’utilizzo di un software come ROS sono:
• Sistemi Distribuiti
Numerevoli robot ai giorni nostri contano su software basato sulla coopera-zione di molti processi spesso nemmeno risiedenti sulla stessa macchina, ma diffusi su più computer differenti. Alcuni possono integrare in sè più compu-ter, altri possono operare con un singolo computer e suddividere il proprio software in più parti cooperanti tra loro per raggiungere l’obiettivo comune. Uno stesso task può essere raggiunto con la coordinazione di più robot che devono agire all’unisono per risolvere il problema. In tutti i suddetti casi coesiste la necessità di poter comunicare tra processi, siano essi insiti nel-lo stesso robot o suddivisi tra differenti, e il middleware garantito da ROS permette ciò tramite due meccanismi primari, i topic per una comunicazione asincrona, e i servizi (service) per la tipologia sincrona, ognuno dei quali verrà discusso piu avanti.
• Standardizzazione e riutilizzo del codice
Il rapido progresso della robotica ha portato allo sviluppo di algoritmi sem-pre più complessi ed efficaci per ovviare a tipici problemi in questo ambito quali ad esempio la navigazione, il mappaggio di una zona, la scelta del per-corso migliore. Risulterebbe dunque utile avere un’implementazione stabile di tali algoritmi senza dover completamente riscrivere il codice o integrare nuove parti ogni volta che si cambi sistema. Ciò è garantito da ROS, che fornisce pacchetti (packages) già debuggati e testati di molti algoritmi usati in robotica.
• Testing
Il testing su software per applicazioni nell’ambito della robotica richiede tem-po ed è molto incline alla presenza di errori. Per semplificare un tem-po’ le cose
4.1. INTRODUZIONE A ROS 49 ROS permette di trattare sistemi in cui la parte di controllo a livello hard-ware è separata dalla gestione dei meccanismi di più alto livello, e di testare questi ultimi simulando l’hardware e il software di basso livello. Inoltre ROS offre la possibilità di memorizzare i dati ottenuti dai sensori e in fase di test in un formato che prende il nome di bag, per poi visualizzarli, analizzarli e riutilizzarli anche più volte nello stesso processo o in processi differenti. La struttura di ROS si basa su un’architettura a grafo, dove la gestione dei processi avviene nei nodi. I nodi ROS comunicano tra loro in due modi: in maniera asincrona, attraverso messaggi che vengono scambiati tramite dei topic ai quali possono sottoscrivere e/o sui quali possono pubblicare, e in maniera sincrona con la chiamata di service.
Strutturalmente ROS si sviluppa su 3 livelli concettuali:
• Livello Filesystem: comprende tutte le risorse utilizzate in ROS, in particola-re Packages, Metapackages, Package Manifest, Stack, Message Type, Service Type.
• Livello del Grafico Computationale: il Computation Graph consiste nella rete peer-to-peer descritta da tutti i processi attivi in ROS che stanno elaborando dati contemporaneamente.
• Livello Comunitario: comprende tutte le risorse che permettono a comunità separate di ricercatori di poter interagire tra loro scambiando software. Trovandoci di fronte ad una struttura software ricca di strumenti e di concetti si ritiene poco opportuno e soprattutto poco utile dilungarci in questo lavoro nella descrizione di tutte le componenti ROS, sulle quali già esiste una documentazione vastissima in rete. Si prosegue piuttosto con la descrizione degli elementi princi-pali ponendo un’attenzione particolare su quelli che risultano fondamentali per la comprensione dell’implementazione della nostra architettura.
Elementi principali del Computation Graph: ∗ I Nodi
∗ Il Master ∗ I T opic ∗ I Servizi ∗ I Bag
4.1.1
I Nodi
Un nodo è un processo che compie una qualsiasi attività computazionale all’in-terno del sistema ROS. Essendo ROS progettato per essere modulare, tipicamente un sistema basato su di esso comprende numerosi nodi, che in questo contesto sono interpretabili come moduli software, ognuno dei quali incaricato di gestire un aspetto del comportamento del sistema.
I nodi e le loro interconnessioni formano il Computation Graph, essi comunicano attraverso topic, service e Parameter Server. Un processo diviene un nodo ROS dopo essersi registrato presso il Master. I nodi sono unità di sviluppo e costruzione del sistema, implementano interfacce ben definite, forniscono specifiche funziona-lità, sono riconfigurabili senza necessità di modifica del codice sorgente.
Ogni nodo in esecuzione dispone di quello che viene definito graph resource name, un nome che lo identifica rispetto al resto del sistema, e di un tipo che semplifica il processo di indirizzamento di un nodo eseguibile all’interno del F ilesystem.
4.1.2
Il Master
E’ il processo fondamentale per l’esecuzione di ROS. Offre ai nodi un servizio di registrazione e di naming, permette infatti al singolo nodo di contattarne un secondo attraverso una metodologia peer-to-peer. Tiene inoltre traccia per ogni singolo topic dei relativi nodi che pubblicano messaggi (Publisher) e di quelli che leggono messaggi (Subscriber), allo stesso tempo mantiene traccia dei service for-niti dai nodi.
Gestisce il Parameter Server ai nodi che ne richiedono i servizi. Il Parameter Server è un dizionario condiviso e accessibile dai nodi. Può essere utilizzato per memorizzare e recuperare parametri del sistema runtime, rendendoli disponibili a tutto il Computation Graph. I parametri vengono memorizzati in un namespace gerarchico, la risoluzione dei nomi e il recupero dei valori dei parametri è realizzato tramite funzionalità di alto livello.
4.1.3
La comunicazione in ROS
La comunicazione tra i nodi ROS rappresenta una delle peculiarità di questo software, essa può avvenire attraverso due modalità, che verranno descritte nei paragrafi seguenti.
• Comunicazione Sincrona → tramite semantica di tipo request/reply dei Service
4.1. INTRODUZIONE A ROS 51 In questo lavoro verrà utilizzata soltanto una comunicazione asincrona, dunque ci dilungheremo un po’ di più sui concetti di topic e messaggio, mentre per quanto riguarda i service saranno fornite solo le nozioni principali.
Comunicazione asincrona: i Topic
La comunicazione asincrona tra nodi avviene tramite scambio di messaggi. In ROS un messaggio è una struttura dati fortemente tipizzata. Sono supportati tutti i tipi standard primitivi riportati in Figura 4.1, così come array di tipi primitivi e costanti.
Figura 4.1 Tipi di dato supportati da service e topic
Ogni messaggio può essere composto da altri messaggi o array di altri messag-gi, arbitrariamente nidificati in complessità. Inoltre è possibile utilizzare messaggi predefiniti in altri package specificandone la dipendenza sul file manifest e inclu-dendone il corrispondente header. La struttura di un messaggio è descritta da un semplice file di testo denominato msg file, di estensione .msg, contenuto so-litamente nella sottocartella msg del relativo pacchetto. Questi file descrivono i campi (fields) di un messaggio ROS e sono utilizzati per generare codice sorgente relativo ai messaggi in diversi linguaggi di programmazione.
I topic costituiscono il mezzo di comunicazione asincrono, unidirezionale, per lo scambio di messaggi tra nodi, secondo una semantica di tipo publish/subscribe.
La comunicazione è unidirezionale, i messaggi sono pubblicati dai nodi publisher e vengono letti dai nodi subscriber. Nodi che generano dati possono pubblicarli come publisher in topic di interesse, nodi che sono interessati invece a ricevere de-terminate comunicazioni possono sottoscrivere un topic come subscriber. Un nodo può essere sia publisher che subscriber del medesimo topic, inoltre possono esserci più publisher e subscriber concorrenti per un singolo topic, e un singolo nodo può pubblicare e/o sottoscriversi a più topic. In generale, publisher e subscriber non sono consapevoli dell’esistenza degli altri, questo permette un disaccoppiamento tra la produzione dell’informazione e il suo consumo.
Ogni topic è fortemente caratterizzato dal tipo di messaggio che viene pubblicato, i nodi possono ricevere solo messaggi il cui tipo corrisponda. Ciò determina che all’interno del topic sia possibile scrivere o leggere un solo tipo di messaggio, per questo ogni topic è identificato dal proprio nome e dal tipo supportato.
Figura 4.2 Procedura sequenziale per comunicazione asincrona tra nodi ROS
In Figura 4.2 è mostrata la procedura sequenziale che permette a due nodi della rete di poter scambiare messaggi attraverso un topic, il publisher è chiamato T alker e il subscriber è il Listener.
La procedura può essere riassunta nei seguenti passaggi:
1. Il publisher si registra al Master attraverso XMLRPC e gli invia informazioni riguardo a ciò che andrà a pubblicare ovvero: tipo dei messaggi, nome del topic e il proprio URI.
