Information Technology Reference
In-Depth Information
A Path-Planner for Mobile Robots of Generic
Shape with Multilayered Cellular Automata
Fabio M. Marchese
Dipartimento di Informatica, Sistemistica e Comunicazione
Universita degli Studi di Milano - Bicocca
Via Bicocca degli Arcimboldi 8, I-20126, Milano, Italy
Marchese@DISCo.UniMIB.IT
Abstract.
In this paper we present a Path-Planning Algorithm for a
non-holonomic mobile robot. The robot we considered has to move us-
ing smoothed trajectories, without stopping and turning in place, and
with a minimum steering radius. We have studied an algorithm based
on a directional (anisotropic) propagation of attracting potential values
on a Multilayered Cellular Automata model. The algorithm finds all the
optimal collision-free trajectories following the minimum valley of a 3D
potential hypersurface embedded in a 4D space, built respecting the im-
posed constraints. Our approach turn out to be distributed and reactive
to environmental dynamics. It is also flexible, because it is applicable on
a wideclass of vehicles with generic shapesand withdifferent kinematics.
1 Introduction
In this paper we describe a very fast, safe and complete path-planning method
for robots based on Multilayered Cellular Automata. Our aim is to design and
construct a robot navigation system that interacts with the environment and
reacts as fast as possible to its dynamical events. Many authors have proposed
different solutions during the last twenty years, based, for example, on a geo-
metrical description of the environment (e.g. [7,8]). The path-planners working
on these models generate very precise optimal trajectories and can solve really
di
*
cult problems, also taking into account non-holonomic constraints, but they
are very time consuming, too. In our opinion, to face a real dynamical world,
a robot must constantly sense the world and re-plan accordingly to the new
information.
Other authors have developed alternative approaches less precise, but more
e
*
cient: the Artificial Potential Fields Methods. In the eighties, Khatib [5] first
proposed this method for the real-time collision avoidance problem in a continu-
ous space. Jahanbin and Fallside first introduced a wave propagation algorithm
in the Configuration Space on discrete maps (
Distance Transform
[4]). In [2],
the authors used the Numerical Potential Field Technique on the Configuration
Space to build a generalized Voronoi Diagram. Zelinsky extended the
Distance
Transform
to the
Path Transform
[12]. Tzionas et al. in [11] described an al-
gorithm for a diamond-shaped holonomic robot in a static environment, where
