M.J. Terstegge
Deadlocks in AGV-systemen.
Literature survey,
Report 98.3.LT.5081, Transport Technology, Logistic Engineering.
On terrains where Automated Guided Vehicles (AGVS) operate, claim areas
are often used. These are areas in which only one AGV is allowed at a
time, ment to prevent AGVs from colliding with each other. The use of
these claim areas may lead to deadlock. This is the phenomenon that occurs
when each AGV in a set of AGVs is waiting for a claim area that is held by
another AGV in the set. This chain of waiting vehicles cannot be broken
without extemal intervention, and causes a great loss of time.
In literature a lot of methods are known to solve deadlock or keep
deadlocks from occuring. These methods can be divided into three
categories. Deadlock detection is a strategy in which no effort is made to
prevent deadlocks from happening. Instead, the detection algorithm tries
to detect deadlocks after they have appeared. After a deadlock is
detected, a deadlock recovery mechanism brings the system back into a
deadlock free state. This method works well in systems where deadlocks
don't occur often, and where the costs of these are acceptable. Deadlock
detection algorithms are also used as a support tool for deadlock
avoidance.
Deadlock prevention and deadlock avoidance both aim to keep the system
deadlock free, but this is achieved in different ways. Deadlock prevention
is a category of methods that make sure that one of the necessary
conditions for a deadlock to occur can never hold. Deadlock avoidance
consists of a group of algorithms that, using the knowledge that is
available about the routes to be covered, avoid the forming of a deadlock
in a dynamic manner. The well-known banker's algorithm is an example of
this. This is one of the best methods to keep AGV systems free from
deadlocks.
An important tool that can be used for examining, deadlocks is the
resource-allocation graph. This graph shows schematically to which AGVs
occupied claim areas are granted, and which AGVs are waiting for certain
claim areas. Many of the algorithms for deadlock detection, prevention and
avoidance make use of this graph.
Reports on Logistic Engineering (in Dutch)
Modified: 2000.02.27;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.