C2T Group Research contracts: Elettric 80

Design and Optimization of AGV Traffic Management

Principal investigator: F. Dabbene

Phase 1: Duration 2008/2010, Euro: 128,000
Phase 2: Duration 2011/2012, Euro: 115,000
Phase 3: Duration 2013/2014, Euro: 115,000


Goal of the project is to design and optimize a traffic manager (TM) that guides the AGVs in the network, so to control the traffic flow of the AGVS in the graph, minimizing the service time, while avoiding collisions and deadlocks.


The problem at hand can be modeled as in figure:


We are given a connection graph composed by N nodes and n segments (links). Over this graph, we have to guide a number m of automated guided vehicles (AGV). We may assume that the  graph is described by a connection matrix S, that is constructed as follows:

·      Sij=0 if node i is not connected to node j

·      Sij= cij, if node i is connected to node j, where the value cij represents the cost of passing through the segment between I and j.

The order of magnitude of the considered problem is the following:

      the number of nodes N is of the order of 10,000

      the number of segments n is of the order of 50,000

      the number of AGVs m is of the order of 10-30

Aim of the project is to design and optimize a traffic manager (TM) that controls the traffic flow of the AGVS in the graph, avoiding collisions. The TM receives as input some request to serve a given node (that is, to guide a AGV to the node). Basically, the TM has to do comply to the following tasks:

1.    Select a free AGV

2.    Select a path from the current position of the AGV and the required node

3.    Dynamically assign (some) segments of the path

These three operations can be dynamically modified online.

Moreover, the TM has to obey some hard constraints: namely, a segment cannot be assigned if it is not free. A segment is free when these conditions hold: 1) the segment is not occupied by any vehicle; 2) there are not any adjacent segments that are occupied by an AGV that may block the considered segment; 3) the end point of the segment is free. These hard blockings are usually referred to as Layout Dependant Blockings. We describe them by means of an occupancy matrix O, that for every segment s provides a list of adjacent segments that are blocked by the presence of an AGV in s.

A deadlock is the situation when two or more AGVs block each other and none of them can move, without selecting another route. One of the tasks of the TM is to handle deadlocks, that is: 1) to avoid as much as possible the formation of deadlocks; 2) to detect possible deadlock situation; 3) to (try to) solve it, e.g. by re-directing one of the vehicles to a new position.

Hence, main goal of a TM is to optimize the service time (that can be measured for instance as the average time required to satisfy a request), under the over-mentioned constraints.

An importan consideration to make is hat the system under consideration is a dynamical system: the AGVs have their own dynamics, moreover they can stop for security reasons. Hence, the TM should assign/reassign paths dynamically. The proposed solution is a combination of ILP (integer linear programming) and sliding window approach.

Path planning and control of a four-wheel steering AVG

Principal investigator: F. Dabbene

Duration 2009/2010, Euro: 12,000

The project concerned the investigation of possible path planning and control strategies for automatic guided vehicles (AGVs) in the special case of four wheel-steering systems (4WS), see figure below.


By path it is meant the pure geometrical description of the motion of the AGV. It can be formally defined as the locus of points in the plane the AVG has to follow in the execution of the assigned motion. On the other hand, a trajectory is a path on which a time law is specified, e.g. in terms of velocities and/or accelerations at each point. The goal of trajectory planning is to generate the reference inputs to the motion control system which ensures that the AVG executes the planned trajectories. In this sense, the inputs of a trajectory planner algorithm are 1) the path description, 2) the path constraints and 3) the AVG dynamics, which impose constraints on the path itself. The goal of a control strategy is to design the inputs to the AGV in order to maintain its motion on the reference trajectories.


The main objectives of the C2T technical contribution to the project have been divided in the following workpackages: WP1) to provide an extensive literature review regarding the problem of path/trajectory planning for the specific case of 4SW-AGV; WP2) to provide a detailed analysis of the path and/or trajectory generation problem; WP3) to propose different control laws, analyzing their limits of performance; WP4) to analyze the robustness of the proposed control laws, and possibly devise techniques for designing controller robust with respect to parametric uncertainties on the distance L1 and L2, and/or with respect to offset errors on the steering angles.

The project lead to the design of a high-performance path following scheme, guaranteeing the following specifications.

Position error < 0.1 mm
Heading error < 0.01 deg