Control of Automatic Guided Vehicles (AGVs)

Background

Automated Guided Vehicle (AGV)-based material handling systems are widely used for transportation tasks in flexible manufacturing and storage systems. AGVs were introduced in 1955 and since then their use has grown enormously. In an AGV system several parts can be distinguished, namely the vehicles, the transportation network, the physical interface between the production/storage system and the control system. This thesis is concerned with the control system. The productivity of AGV-based systems depends on the quality of the control system. An efficient control system requires efficient operational strategies for task assignment, scheduling, routing, dispatching and deadlock avoidance of the AGVs.

A task assignment strategy determines which AGV processes which task, where a task usually comprises the transportation of goods between two given points and possibly the pick-up time and its due time. Once a task has been assigned it has to be scheduled, i.e., the actual pick-up time is determined. Furthermore, the routing process calculates the route of the AGV from the pick-up point to the drop destination. Note, that the scheduling process can work together with the routing process to determine a pick-up time suitable for routing. The dispatching process is needed to avoid conflicts and deadlock situations. Deadlock can occur at buffer areas of pick-up and delivery points. During operation, deadlocks and collisions are either detected and resolved by rerouting vehicles to buffer areas or deadlocks and collisions are predicted and avoided by preplanning of routes. Detection and solving of deadlocks instead of predicting and avoiding them results in a lower performance of the system.

The routing and dispatching complexity heavily depends on the allowed degrees of freedom. How many AGVs are allowed to change their route during the routing process (separate vs. simultaneous decisions)? Are one-load-carrying or multiple-load-carrying AGVs used in the system? Where can the vehicles drive through the network, e.g., are they driving on a bidirectional graph or are they allowed to drive wherever they'd like (free-range)? Does the routing have to respect any deadlines?

Furthermore, we distinguish between off-line control and on-line control AGV systems. In a off-line control system the transportation demands are known in advance or are perfectly predictable and all information in the system needs to be accurate. Due to the stochastic nature of the transportation process, control systems capable of making real-time decisions are required. A control system can be used decentrally and centrally.

Abstract of the thesis

The online control of AGVs is key to an efficient transportation system and the focus of this work. The presented heuristics for the task assignment builds the first step. Further, a dynamic, polynomial-time, sequential routing algorithm is studied in detail with a bigger framework that guarantees a deadlock and conflict-free routing of the AGVs in undisturbed operations. Nevertheless, to deal with disturbances we studied among others the case of small delays of AGVs with four strategies. A programmed simulator models a setting from an industrial partner which shows a wide area of promising results, i.e. that the industrial partner could expect a 15% better performance by replacing the current AGV system with the presented approaches.

Simulator

During this thesis a simulator was developed which includes task assignment strategies, routing algorithms and disturbance management. Using the c++ graph library LEDA the outcome of these algorithms is simulated. Here is a movie of an example setting:

Simulation movie

Future research topics

• The graph of our industrial partner was improved but we are convinced that there is more potential in optimizing the graph with sophisticated methods.
• The transportation system of our partner would have the possibility to use interim storage areas. We did not study how such interim storage areas can be used efficiently and if thus can increase the performance.
• We gave two ideas for improving the sequential routing approach. These and further ideas could be tested with a simulator to see if they have promise.
• One introduced approach for resolving small delays is based on rerouting on a subgraph. Unfortunately, there is no guarantee for a solution if the rerouting is based on a sequential routing algorithm. We believe that for a simplified graph a resolving with a simultaneous routing approach would be a good way out of this problem.

Industry Contact

LogObject is a logistics company with focus on dynamic resource management. The industry expertise will accompany this thesis. Models and algorithms shall be tested over storage and/or manufacturing systems of LogObject in a test embedding. Depending on the progress of the work it might become possible to validate the results on a real manufacturing system.