A cooperative path-planning for multiple automata by dynamic/static conversion

Abstract

An online path-planning algorithm for multiple automata is proposed. Each automaton usually goes straight to the goal. When some of the automata touch each other, some kind of swarm occurs and is identified by sensors. In general, several kinds of swarm appear, since a lot of automata collide in different circumstances. The proposed algorithm decomposes all simple and complex swarms uniformly by the following dynamic/static conversion: some automata are stopped in the swarm, and the others are moved around the set of stopped automata. By using this conversion, the algorithm destroys all swarms by some simple motions in common and is easily applied for some practical robots. Moreover, the automata decompose the swarm by cooperative motions as follows: an inside automaton comes close to its goal monotonously. Since all automata go straight to their goals outside the swarm, convergence of the automata toward their goals is naturally ensured. Communication overhead is kept small enough by using the monotony property, and consequently the algorithm can run online.