ETD

• consensus-based bundle algorithm
• decentralized architectures
• fleet management
• hierarchical architectures
• intralogistics
• multi-agent path finding
• multi-robot systems
• multi-robot task assignment

Multi-robot systems are essential in intralogistics and their coordination requires advanced Fleet Management to jointly solve Multi-Robot Task Assignment (MRTA) and Multi-Agent Path Finding (MAPF). Currently, decentralized architectures present severe limitations: they decouple assignment and planning, use unrealistic metrics (such as Euclidean distance), and assume homogeneous fleets, thereby generating unfeasible logistical plans.
This thesis overcomes these critical issues by proposing two algorithmic architectures. The first is lazy-CBBA, a decentralized auction-based approach where each robot can be awarded multiple tasks. It couples task assignment with the search for real paths on a graph, using a cost function that evaluates obstacles, task execution times, battery levels, and fleet heterogeneity. The lazy heuristic uses the Euclidean estimate as a lower-bound to discard non-competitive paths a priori, reducing computation times while maintaining mathematical optimality.
The second contribution is the optimized lazy-TCBBA, designed to avoid assignment conflicts in the event of a disconnected communication network by dividing the fleet into teams (via spatial clustering). With an appropriate number of teams, lazy-TCBBA matches the performance of lazy-CBBA (in terms of total distance traveled by the fleet and maximum completion time), further reduces computation times, and guarantees a conflict-free assignment even without global network connectivity.

I sistemi multi-robot sono imprescindibili nell'intralogistica e il loro coordinamento richiede un Fleet Management avanzato per risolvere congiuntamente il Multi-Robot Task Assignment e il Multi-Agent Path Finding. Attualmente, le architetture decentralizzate presentano gravi limiti: disaccoppiano assegnamento e pianificazione, usano metriche irrealistiche (es. distanza Euclidea) e assumono flotte omogenee, generando piani logistici ineseguibili.
Questa tesi supera tali criticità proponendo due architetture algoritmiche. La prima è il lazy-CBBA, un approccio decentralizzato basato su aste in cui ogni robot si aggiudica più task. Esso accoppia l'assegnamento alla ricerca dei percorsi reali su grafo, usando una funzione di costo che valuta ostacoli, tempi di esecuzione dei task, batteria ed eterogeneità. L’euristica lazy usa la stima Euclidea come lower-bound per scartare a priori i percorsi non competitivi, riducendo i tempi di calcolo e mantenendo l'ottimalità matematica.
Il secondo contributo è il lazy-TCBBA ottimizzato, pensato per evitare conflitti nell’assegnamento in caso di rete di comunicazione non connessa grazie alla suddivisione della flotta in team (tramite clustering spaziale). Con un numero di team adeguato, il lazy-TCBBA eguaglia le prestazioni del lazy-CBBA (per distanza totale percorsa e tempo massimo di completamento), abbatte ulteriormente i tempi di calcolo e garantisce un assegnamento senza conflitti anche senza connettività della rete di comunicazione.