logo SBA

ETD

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

Tesi etd-05222020-102010


Tipo di tesi
Tesi di laurea magistrale
Autore
FORTE, PAOLO
URN
etd-05222020-102010
Titolo
Heuristic search methods for combined task assignment, motion planning and coordination in fleets of mobile robots
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA ROBOTICA E DELL'AUTOMAZIONE
Relatori
relatore Prof.ssa Pallottino, Lucia
relatore Prof. Pecora, Federico
supervisore Dott.ssa Mannucci, Anna
Parole chiave
  • heuristic search methods
  • task assignment
Data inizio appello
19/06/2020
Consultabilità
Completa
Riassunto
This work consider the Task Assignments Problem for fleets of Automated Guided Vehicles (AVGs), while taking into account the subsequent path planning problem and the coordination problem. The estimated costs are interrelated and the overall performance of the team need not be a standard sum of cost model, enabling straightforward treatment of the additional costs incurred by precedence constraints due to coordination problem. Additional penalization costs are incurred by overlap between paths. This work shows that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. Sequential application of task assignment and path planning often gives rise to pathological situations, such as deadlocks, in which AGVs block each other, thus preventing tasks completion. The MRTA problem can take widely differences depending on the characteristics of the robots in the fleet and of the application context. Goals can be shared or individual. Robots may be aware of each other’s tasks or not; tasks may or may not require interaction between robots; The fleet can be a centralized or distributed system; in this study, a centralized system is considered. The aim of this report is to expose the work tread for final master thesis which was held at ̈Orebro University. A modified systematic algorithm is proposed, that finds a solution in a reasonable time both on small instances (if interference is considered) and on big instances (if interference is not considered). Aiming at larger problems, some changes are introduced that allow to find an optimal assignment quickly even for problems of considerable size. Simulations are performed on maps of real industrial environments, to compare the proposed method with traditional task assignment algorithms.
File