Here's a simpl[e deadlock in a multi-robot environment.
Two cooperating robots.
One robot gets a block of wood and holds it while the other one
drills a hole in it.
First robot has to go into another room to get the wood.
Second robot decides that it's batteries are getting low, and since
the first robot is not ready, it goes and sits in the charging station
until the first robot returns with the wood, and enters the drilling
First robot is returning, but it does not have enough battery power
to get to the drilling station, so it goes to the charging station.
Since robot #2 is using the station, it waits it's turn to charge.
Since robot #2 never sees that robot #1 is ready to drill, it just
keeps sitting on the charger, and there is a deadlock.
Now, how many ways can YOU think of to do the following:
1) Prevent the deadlock from hapenning in the first place.
2) Detect that the deadlock is going on.
3) "Unlock" the deadlock when it happens.
There are many, I'll tell you that much.
- Alan Kilian <alank(at)timelogic.com>
Bioinformatics Applications Director, TimeLogic Corporation
Basically a deadlock is a circular wait state where one or more robots
can't release their resources until other robots have released theirs.
The other robots can't release their resources until the first one or
more robots releases theirs! Result - no robot releases their resources
and the system comes to a stand still.
Deadlocks can be handled by prevention, avoiding or resolving.
Prevention is where the system is designed so that deadlocks do not
occur. Sounds nice, but it can be difficult to know if the system will
deadlock and therefore difficult to ensure that a deadlock cannot occur.
It can also lead to an underutilisation of resources. Avoiding is
detecting a deadlock at run time and then taking action to prevent it
occurring. This can have the problem that the deadlock is detected too
late for action to be taken to avoid it. This leaves the final option of
handling the deadlock when it has occurred. This usually involves the
robots releasing their resources, which may not be possible in a
physical system (if, for example, the resource is a location in the
environment). The deadlock then has to be fixed by either "braking" the
rules of the system or human involvement.
An alternative is to combine some of the above methods, for example, by
using agents to manage the resources and resolve deadlocks and to
look-a-head for possible deadlocks to try and prevent them.
Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here.
All logos and trade names are the property of their respective owners.