Question On deadlock

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 location.

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.

The easiest way is to have a robot in the charging station detect when it is fully charged and leave the station at that point.

Or you could have two charging stations.

The best way is to not allow deadlocks in the first place. However, if the charging station has a queue and robots can see that another robot is waiting, the deadlock is detected.

Hava a fully charged robot leave the charging station.

-- D. Jay Newman

Maryann,

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.

Andrew

Maryann wrote: