A mixed skill-based and optimization methodology for human-robot task allocation and scheduling

In the last few years, collaborative robotics is becoming one of the most adopted technologies in smart factories, in the industry 4.0 scenario. The involvement of collaborative robots (cobots) implies the integration of the so called human-robot collaboration system. One of the crucial problems that arises in human-robot collaboration is the optimal task distribution and coordination among the agents during assembly processes, known as human-robot task allocation and scheduling problem. This thesis has the purpose of formalizing an offline methodology for solving the task allocation and scheduling issue. The result achieved is a mixed skill-based and optimization approach, where the core of the methodology is the Hungarian Algorithm. The Hungarian Algorithm is an efficient optimization tool to solve the so called balanced assignment problem. In this thesis, it is modified in order to design an algorithm that is able to solve also unbalanced assignment problems, in which the number of tasks is different from the number of agents, like in all the relevant assembly processes. The method is called Hungarian Algorithm Cluster-based task allocation, due to the concept of clustering between two classes that is presented, and considers as cost function the task processing times and the posture evaluation of the human agent. Besides the task assignment solution, the operations are coordinated through a scheduling policy. This policy is obtained by means of a Mixed Integer Linear Programming (MILP) formulation, with a multi-objective optimization. The skill-based phase considers the robot capabilities in order to evaluate its suitability in performing the required tasks. Finally, the concepts of assembly tree and precedence graph are formalized. The proposed strategy is then validated on two different layouts, with a real cobot, proving its correct work.

Negli ultimi anni la robotica collaborativa sta diventando una delle tecnologie più impiegate nelle smart factory, nello scenario dell’industria 4.0. Il coinvolgimento di robot collaborativi (cobot) implica l’integrazione del cosiddetto sistema di collaborazione uomo-robot. Uno dei problemi cruciali che sorgono nella collaborazione uomo-robot è la distribuzione ottimale e il coordinamento dei compiti tra gli agenti durante i processi di assemblaggio, ossia il problema di assegnazione e pianificazione dei compiti tra uomo e robot. Questa tesi ha lo scopo di formalizzare una metodologia offline per risolvere il problema dell’allocazione delle attività e della pianificazione. Il risultato ottenuto è un approccio misto basato sulle competenze e sull’ottimizzazione, in cui il nucleo della metodologia è l’algoritmo ungherese. L’algoritmo ungherese è uno strumento di ottimizzazione efficiente per risolvere il cosiddetto problema dell’assegnazione bilanciata. In questa tesi, viene modificato per progettare un algoritmo in grado di risolvere anche problemi di assegnazione non bilanciati, in cui il numero di task è diverso dal numero di agenti, come in tutti i relativi processi di assemblaggio. Il metodo è chiamato Hungarian Algorithm Cluster-based task allocation, per via del concetto di clustering tra due classi che viene presentato, e considera come funzione di costo i tempi di processamento delle operazioni e la valutazione della postura dell’agente umano. Oltre alla soluzione di assegnazione delle attività, le operazioni sono coordinate attraverso una politica di pianificazione. Tale politica si ottiene mediante una formulazione di Programmazione Lineare Intera Mista, con un’ottimizzazione multi-obiettivo. La fase basata sulle competenze considera le capacità del robot al fine di valutarne l’idoneità nell’esecuzione delle attività richieste. Infine, vengono formalizzati i concetti di albero di assemblaggio e grafo di precedenza. La strategia proposta viene poi validata sperimentalmente su due differenti layout, con un robot collaborativo, dimostrandone il corretto funzionamento.