Traffic Management of Automated Guided Vehicles in Flexible Manufacturing Systems

The objective of the research carried out by Roberto Olmi has been the development of an innovative traffic management system (TMS) for fleets of automated guided vehicles (AGV) operating in industrial environments. These vehicles are used for the transport of materials in environments where the presence of people and moving machinery has to be expected. The TMS has to control the motion of the vehicles so as to avoid collisions and optimize transport times. The approach is based on the decomposition of the problem into three parts: assignment of transport tasks, path computation, motion control of each AGV along its path. Transport orders are assigned to available vehicles by solving a linear assignment problem through the Jonker Volgenant algorithm. The objective is to minimize the sum of the times required by each vehicle to reach the pick station assigned to it. The motion of the vehicles is defined incrementally by a controller that periodically computes the list of the trajectory segments that each AGV is allowed to cover. The sequence of segments is determined so as to minimize the nominal travel time. In order to define the movement of vehicles along their routes, a tool called Coordination Diagram (CD) has been applied. Through this instrument, the problem of coordinating the motion of N AGVs is transformed into a shortest path problem within an N dimensional space with obstacles. The main contribution of this dissertation is the application of the CD to the problem of coordinating a fleet of AGVs in industrial environments. In [1], [2] and [3], the student has developed an original method to calculate efficiently the CD. This method is based on an approximation of the CD that allows to reduce the computational cost of the algorithm and thus makes it suitable for the coordination of tens of vehicles. To calculate the shortest path to the CD, in [4] and [5] a complete planning solution has been proposed that provides greater efficiency with respect to an incremental approach. However, since the CD changes each time that a path of a vehicle is modified, an incremental approach is required for the coordination of AGVs. In particular, in [3] the action that maximizes the advancement of the fleet while respecting the constraints imposed by the CD is determined by solving Maximum Independent Set problem. The solver is an heuristic algorithm which has time complexity quadratic in the number of vehicles considered. In order to test the proposed TMS, a simulation software has been developed using Matlab. The simulations consider AGVs operating on real layouts developed by Elettric80 S.p.A., a manufacturer of AGV. The proposed algorithm is much more flexible than the one currently used by the company. It does not require the manual definition of traffic rules and it allows a significant savings of time (> 30 days / person) in the construction of new plants. The research project presented in this dissertation has been selected as a finalist at the “European Technology Transfer Award 2010” organized by the associations EUROP(1) and EURON(2).----- (1) EUROP (www.robotics-platform.eu) is the European Robotics Technology Platform, an industrydriven framework for the main stakeholders in robotics. (2) EURON (www.euron.org) is the European Robotics Research Network, a community of more than 200 academic and industrial groups in Europe.