06-02-2013, 04:10 PM
Distributed Shortest-Path Finding by a Micro-robot Swarm
Distributed Shortest-Path Finding.pdf (Size: 702.41 KB / Downloads: 50)
Introduction
In swarm robotics an often needed behaviour is to search for interesting spots
within the workspace and to form a communication/transportation line between
the found spot(s) and another area of interest or another object.
Several researchers proposed algorithms based on signalling wavefronts to
solve shortest path problems in sensor and communication networks or the multi
robot domain. E.F. Moore described in [1] four wavefront algorithms to find the
shortest path in a maze. And also the Bellman-Ford algorithm computes the
smallest spanning tree in a maze. O’Hara and Balch described in [2] an algorithm
that guides robots with the help of fixed communication nodes exploiting
Payton’s pheromone algorithm. In Payton’s algorithm described in [3] a robot
close to the source will broadcast a hop count pheromone message through the
swarm. If a robot close to the target gets this message, it will send a second
hop count pheromone message in the opposite direction. All robots know the
direction vector to the target and the source now. Adding those direction vectors
leads to the shortest path. Two problems could occur with this algorithm.
Firstly the robots do not know if they are on the shortest path or not. If the
robots follow the gradient, they will be guided to the source or the target, but
they do not keep up a path between the source and the target. And secondly if
two robots in the swarm become source robots at the same time, the algorithm
will be confused by different directions. Inspired by those algorithms we tried to
overcome this problem. The pheromone used in our algorithm counts the hops
up and down. This enables the robots to know wether they are on the shortest
path or not despite of cycles in the maze.
The JASMINE Swarm Micro-robot
The underlying swarm micro-robot JASMINE was developed especially for
swarm robot research and swarm robot games. Despite its small size of about
27×27×35 mm3, it has excellent local communication abilities and a far distance
scanning and distance measuring sensor. The excellent communication abilities
result from six infra-red sensors and emitters arranged around the robot with a
displacement of 60◦. Those sensors could also be used for short distance measurements.
The far distance measuring sensor is hooked to the front of the robot.
Two differentially driven wheels give this micro-robot a high manoeuvrability at
a high speed. Optical encoders allow odometric measurements in the mm-range.
Different from many other swarm robots JASMINE supports only local communication.
Long distance communication via radio frequency is not implemented
and does not correspond with the views of the construction team about swarm
robot capabilities. Figure 1 shows the JASMINE swarm micro-robot and the
sensor placement.
Experiments
The simulation for evaluating the proposed algorithm is based on a model of
JASMINE. The simulation environment Breve described in [4] has been used for
the simulation of the JASMINE robots. The distributed shortest-path algorithm
was implemented in Steve2 and MDL2 which is our further development from
MDLe by Manikonda et al., see [7].
Many simulation experiments have been performed with several source positions.
Figure 2 shows an experiment3. Hundred robots have been equally distributed
in Fig. 2(a) with a communication range of 20 cm. Figure 2(b) shows the
robots in the aggregation phase the white robots stand on the shortest path, the
sources are green and the black robots are moving towards the nearest source.