logo SBA

ETD

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

Tesi etd-07052016-022655


Tipo di tesi
Tesi di laurea magistrale
Autore
MORVIDONI, MATTEO
URN
etd-07052016-022655
Titolo
A framework for Decentralised Task Allocation with Informative Path Planning using submodular rewards
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA ROBOTICA E DELL'AUTOMAZIONE
Relatori
relatore Prof. Innocenti, Mario
correlatore Prof. Tsourdos, Antonios
controrelatore Prof.ssa Pallottino, Lucia
Parole chiave
  • coordinated search
  • distributed algorithm
  • greedy algorithm
  • optimization
  • path planning
  • RRT
  • submodularity
  • task allocation
Data inizio appello
21/07/2016
Consultabilità
Non consultabile
Data di rilascio
21/07/2086
Riassunto
The core work of this thesis tackles the case-study problem of coordinating the motion of a multi-agent, multi-target system subject to bounding constraints.
The need for efficient detection and tracking of stationary or moving objects, such as lost people, over a wide, open area motivates the use of swarms of Unmanned Autonomous Vehicles (UAVs).
Typically these agents have bounded resources to comply with, such as fuel limitation, allotted mission time and the like. Thus a careful evaluation is required prior to the actual path generation: an optimal task allocation between agents and targets has to be executed to not potentially waste any resource at disposal.
Given that optimal results usually aren’t obtained in real scenarios due to the high computational burden (centralized approach) or the nature of the problem itself (NP-Hard), the key is distributing the computational load among all agents through a decentralized approach, while compromising on performances.
Leveraging the submodularity property of a special class of functions, the study produced a novel solution for Decentralised Task Allocation, which allows to achieve a reduced computational burden and still guarantee a sub-optimal level of performances.
A novel algorithm has been implemented to generate the path for each agent (RSIG, Rapidly-exploring Submodular Information Gathering), which is a custom version of the RRT* path planner based on criteria of information retrieval.
File