A reachability-based decoupling solution to the routing problem in smart manufacturing

We address optimal routing in smart manufacturing according to a model predictive control (MPC) approach that was proposed in a recent PhD thesis. In this PhD work, a mixed logical dynamical (MLD) model of the transport line in a plant is adopted with a cost function that favors those actions which move pallets towards their destinations through the shortest path. Conflicts are avoided by introducing state-dependent constraints on the admissible control actions. %while avoiding conflicts. The resulting constrained optimization problem is admittedly computationally intensive due to its combinatorial nature, which can slow down the transport line operation and reduce the manufacturing plant throughput as the number of pallets and the MPC prediction horizon grow. Here, we propose a methodology to defeat such a computational complexity by decoupling the MPC optimization program into multiple smaller dimensional programs that can be solved in parallel. This is achieved using a graph representation of the transport line and partitioning it in sub-graphs associated to the different pallets by resorting to reachability analysis over the MPC prediction horizon. A reduced MLD model is determined for each sub-graph by pruning state and input variables, and eliminating redundant equations and constraints from the complete MLD model. If the MPC solutions computed in parallel on the sub-graphs are not conflicting, then, the planned actions are applied. If instead some conflict is detected, sub-graphs are joined together and the reduced MLD model and associated MPC solution of the joint sub-graph are computed. The same procedure is repeated until all conflicts are solved. Although general, the proposed strategy is developed with reference to the manufacturing plant studied in the reference PhD thesis. Extensive simulations show the effectiveness of the reachability-based decoupling approach.

Questo lavoro affronta il problema della movimentazione dei pallet in sistemi manufattuieri automatizzati secondo l'approccio del controllo predittivo del modello (MPC) applicato ad un modello ibrido "mixed logical dynamical (MLD)" della linea di trasporto con una funzione di costo che favorisce le azioni che spostano i pallet verso la loro destinazione lungo il percorso più breve evitando conflitti. L'approccio descritto è stato proposto in una recente tesi di dottorato dove è stato evidenziata la complessità computazionale del risultante problema di ottimizzazione vincolata a causa della sua natura combinatoria. Ciò può rallentare il funzionamento della linea di movimentazione e ridurre la produttività dell'impianto. In questo lavoro, proponiamo una metodologia per ridurre la complessità computazionale disaccoppiando il programma di ottimizzazione MPC in più programmi dimensionalmente più piccoli che possono essere risolti in parallelo. Ciò si ottiene rappresentando mediante un grafo la linea di trasporto, e suddividendolo in sottografi associati ai diversi pallet mediante analisi du raggiungibilità sull'orizzonte predittivo dell'MPC. Viene quindi determinato un modello MLD ridotto per ciascun sottografo eliminando le variabili di stato e di ingresso e le equazioni e vincoli ridondanti dal modello MLD completo. Se le soluzioni MPC calcolate in parallelo sui sottografi non sono in conflitto, vengono applicate le azioni pianificate. Se invece viene rilevato qualche conflitto, i sottografi corrispondenti ai pallet in conflitto vengono uniti insieme, viene calcolato il loro modello MLD ridotto e la soluzione MPC associata. La stessa procedura viene ripetuta finché tutti i conflitti non vengono risolti. Sebbene generale, la strategia proposta viene sviluppata con riferimento a uno specifico impianto. Simulazioni estensive confermano l'efficacia della decomposizione basata su analisi di raggiungibilità.