Delft University of Technology
Faculty Mechanical, Maritime and Materials Engineering
Transport Technology

M. van der Zee Dynamic free range routing for automatic guided vehicles
Masters thesis, Report 2005.TL.6969, Transport Engineering and Logistics.

In this thesis an algorithm is presented that allows for dynamic free range route planning of automatic guided vehicles (AGVs). This routing algorithm is based on the route choice methodology from the NOMAD microscopic pedestrian behavioral model.

When designing AGV systems, six design issues can be distinguished, namely vehicle design, facility layout, fleet size, idle vehicle management, control system design and operational procedure design. This thesis focuses on one of these operational procedures.
Operational procedure design consists of defining procedures for dispatching, scheduling and routing. Dispatching is the process of assigning a transportation job to an AGV, where scheduling is the process of dispatching a set of AGVs to a batch of transportation jobs. Routing is the process of determining routes for a set of AGVs to fulfill their respective transportation jobs. In this thesis, a new AGV routing methodology is presented. A routing procedure can be static or dynamic. In the case of dynamic routing, input information is used that evolves real-time, whereas in static routing information is assumed to be fixed and known throughout route execution. Routes can be determined for all AGVs in the system at one central location or locally at each AGV. Routing procedures that combine local and central routing are termed distributed.
Up until now, AGVs use a map of predefined, fixed paths that are combined to obtain routes along which they move from origin to destination point. The problem of scheduling and routing is addressed as a vehicle routing problem (VRP). Using fixed paths was historically defined, but also allows for reliable automation of vehicles with limited maneuverability.
The use of fixed paths posts some problems. Routes are unnecessary long, which leads to high transportation times and low system throughput. Path segments are shared between routes for multiple vehicles, which leads to congestion and deadlocks during route execution. Furthermore, the routing process is vulnerable to disruptions, for example if path segments cannot be used during operation due to vehicle break down.
Using dynamic information (on planned vehicle routes) and free range route determination might provide solutions to these problems. It is expected that the use of a dynamic free range routing process will result in better facility area utilization and decreased route length with respect to the fixed path routing case. Furthermore, it is expected that use of dynamic information on AGV movements combined with free range movement capabilities will allow for more flexible deadlock and congestion avoidance mechanisms and smaller differences between planned and realized arrival times. In the field of robotics, the problem of free range motion planning for car-like mobile robots is addressed. Difficulty in this field of motion planning is the fact that car-like mobile robots are in general not capable movement perpendicular to their direction of movement. This constraint on movement is termed a nonholonomic constraint. Solution methods are developed that allow for motion planning for mobile robots with nonholonomic constraints.

NOMAD is a microscopic pedestrian behavioral model, which is used to aid in the design public places by predicting pedestrian traffic flows. It assumes pedestrians to be economists that choose their walking trajectories, activity areas, activity completion times and activity order such as to minimize an expected cost function that reflects their personal preferences.
In the NOMAD model a strategic, tactical and operational level are distinguished. At the strategic level the activity choice of pedestrians is modeled. The tactical level is concerned with scheduling of these activities, route and destination choice and activity time choice. At the operational level, the determined routes are executed. Of specific interest to this thesis is the (free range) route choice mechanism.
A study of the NOMAD model has suggested that it might be useful for AGV routing. When applied to AGV routing, it is not used as a predictive pedestrian simulation tool, but as an optimized AGV control tool. The NOMAD model could be interesting to dynamic free range routing of AGVs, because it allows for time dependent determination of free ranging trajectories. Other interesting aspects are the fact that the model uses a layered structure that is quite similar to the structure for AGV system control adapted at the AGV laboratory and the fact that it allows for the implementation of AGV specific behavior. Problems that will have to be addressed are the fact that pedestrians are taken to be points in space in the NOMAD model, which does not apply to AGVs. Furthermore, AGVs have kinematic constraints that do not apply to pedestrians. Finally, AGVs put strict requirements on their orientation at the start and end of their trajectories.

An AGV routing algorithm is designed that makes use of the free range route choice mechanism of the NOMAD model. As starting point for this routing algorithm, an approach to AGV system control is used that distinguishes a strategic, tactical and operational level. In this thesis, the routing part of the tactical level is addressed.

Adapted AGV system control approach

The routing algorithm dynamically determines free ranging trajectories that are optimized regarding arrival time, the avoidance of static obstacles and the planned trajectories of other AGVs.
The routing algorithm was implemented in a software component in Object Pascal for Borland Delphi 7. This component was found to be able to determine free range trajectories with sufficient accuracy within computation times that allow for real time local application on AGVs.

To evaluate the routing algorithm, the component was implemented in a simulation. This simulation showed that free range trajectories were determined that on average are 19% shorter than routes determined using a mesh routing algorithm and 53% shorter than routes determined using a loop routing algorithm. The simulation showed that the routing algorithm effectively takes static obstacles and other vehicles into account. A reliable method for time window arrival was implemented. Moreover, up to a certain fleet size, trajectories were shown to have admissible midsections that do not violate the nonholonomic constraints on the vehicle.
It is recommended that the routing algorithm is further tested by implementing a suitable operational controller. This way, the influence of the routing algorithm on system throughput, safety and reliability can be investigated under stochastic (operational) influences. Finally suggestions are made with regard to the possibility of saving computation time and with regard to additional features that could be implemented in the routing algorithm.

Reports on Transport Engineering and Logistics (in Dutch)
Modified: 2005.07.07; , TU Delft / 3mE / TT / LT.