Sensor-Based Traffic Rules for Multiple Automata Based on a Geometric Deadlock-Free Characteristic
Takashi Yoshioka and Hiroshi Noborio
Division of Information and Computer Science, Osaka Electro-Communication University, Hatsu-Cho 18-8, Neyagawa, Osaka 572, Japan
In this paper, we propose a sensor-based and decentralized navigation algorithm for multiple automata and discuss its deadlock-free characteristic in an uncertain 2-d world without any static obstacles. We consider multiple, but a limited number of, automata. Each automaton has the same circular shape, finds another automaton in a contact manner by a ring of tactile sensors, and then selects one of three simple behaviors, i.e., stop, straight, and circular behaviors. In our algorithm, an automaton basically moves toward the goal direction, and if and only if the direction is interfered by another automaton, it avoids another automaton based on a common set of sensor-based traffic rules. By common sense, each automaton never enters any local and global deadlocks, which excludes and includes the goal, respectively. Because all kinds of deadlocks are generally classified as local and global deadlocks, we can easily see that our proposed algorithm ensures its deadlock-free characteristic.