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 T_a 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 uT_a.

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=         AT₁ AT 2 . . . AT n         u=         U₁T 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

T_{a (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 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 uT_{a 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 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.

4.1. INTRODUZIONE A ROS 53 2. Il subscriber si registra al Master attraverso XMLRPC. Anche lui invia in-

formazioni su tipo dei messaggi, nome del topic e proprio URI.

Il Master tiene in memoria la lista di tutti gli URI degli attuali publisher, aggiornandola qualora fosse necessario. Il Master mantiene una tabella in cui risiedono tutti i dati sia per i subscriber che per i publisher.