ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-05142021-171527


Tipo di tesi
Tesi di laurea magistrale
Autore
SARNO, VALERIA
URN
etd-05142021-171527
Titolo
Sviluppo di algoritmi per il problema di task assignment in sistemi multi-robot
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA ROBOTICA E DELL'AUTOMAZIONE
Relatori
relatore Prof.ssa Pallottino, Lucia
Parole chiave
  • task assignment
  • mobile robots
  • sistemi multi-robot
  • travel salesman problem
  • problema del commesso viaggiatore
Data inizio appello
03/06/2021
Consultabilità
Non consultabile
Data di rilascio
03/06/2061
Riassunto
In questo lavoro di tesi vengono proposti due differenti algoritmi per la risoluzione del problema di task assignment nei sistemi multi-robot. La particolarità dell'approccio presentato risiede nel fatto che, per entrambi gli algoritmi, i task vengono dapprima riuniti in cluster e solo successivamente assegnati ai robot: effettuare l'assegnamento dei cluster e non dei singoli task, infatti, permette loro di ottimizzare il proprio tragitto, riordinando la sequenza dei task in modo tale da percorrere la minor distanza possibile.
Il primo algoritmo presentato risolve in maniera centralizzata un problema di programmazione lineare intera per assegnare i cluster ai robot; il secondo, invece, si basa su un approccio "market-based" e prevede che ciascun robot selezioni autonomamente il miglior cluster per sé stesso, risolvendo eventuali conflitti attraverso una fase di consenso.
Questi due algoritmi sono stati messi a confronto in varie situazioni, evidenziando le loro differenze, individuandone vantaggi e svantaggi e determinando il miglior approccio da utilizzare a seconda dello scenario considerato.
File