Conflict-free scheduling and routing of automated guided vehicles in
mesh topologies


  Conflict-free scheduling and routing.pdf (Size: 4.15 MB / Downloads: 0)

Introduction

Automated guided vehicles (AGV) are widely used for transfer-
ring loads in industrial environments. Typical applications of AGVs
are in flexible manufacturing systems (FMSs), automatic material
handling systems and container terminals [14].
In the real world, the path topology of AGVs is mesh-like.
Therefore, the conflict-free routing and scheduling algorithms for
AGVs in mesh topology are very important and applicable [5,6].
Most of the existing methods work with a small number of
AGVs and offer a low degree of concurrency. With a drastically
increased number of AGVs in recent applications (e.g. in the order
of a hundred in a container handling system), efficient algorithms
are needed to resolve the increased contention of resources among
AGVs [5].

Related works

A number of results have been published on conflict-free
routing of AGVs, which are categorized in [5]. As the best of
our knowledge, there are few works on AGV routing in mesh
topology [1,68]. Some of the related works are briefly introduced
in the section.
In [7], an algorithm for routing 4n2 concurrent AGVs using a
sorting algorithm on a mesh structure is proposed. The optimized
version of this algorithm appears in [8]. This latter algorithm
guarantees that each AGV reaches to its destination with less
than 3n movements. However, the number of movements is not
optimized and AGVs do not use the shortest path to reach to their
destinations in any of the above algorithms.

Prototype implementation

In this section, the practical results of our approach are
presented. The prototype is implemented in Java programming
language and has been run on a PC with 1800 MHz AMD Athlon
x64 3000 C processor and 1 GB RAM. We have simulated a square
(n  n) mesh with multiples of n2 AGVs that an (approximately)
equal number of AGVs are located on each buffer. The AGVs are
assigned to junctions randomly.
We have implemented all simulations with our routing
algorithm. The resulting routing time in small meshes was
negligible and for larger cases was near to 16 ms.
The goal of the system is to reduce the number of delays that are
evaluated as a measure of improvement, as shown in the diagram
of Fig. 4. According to this figure, the number of delays is a linear
function of AGVs/Junctions. Indeed increasing the number of AGVs
cannot move the average delays sharply in a fixed mesh which uses
the proposed algorithm.