Avoiding deadlock in multi-agent systems

The problem of controlling the displacement of a group of robots is very difficult. On one hand, it can be solved by planning but this becomes very complex if the number of robot increases; on the other hand it can be solved by a local approach where each robot follows its own behaviour. Here we give an analysis of this last approach and present a solution to solve one of emergent possible problems: deadlock.