Information Technology Reference
In-Depth Information
first room of the previous problem. The new paths found, from a certain point
on, merge into the old paths, as expected when we have optimal trajectories.
Another property is the selection of the nearest goal in a set of goals. Setting
a)
b)
Fig. 9.
An example of a two starting points problem (a) and an example with two goal
poses (b)
more goals, the algorithm finds the paths that reaches the nearest of them along
an admissible path. We can also address mixed situations where there are more
than one starting and/or goal points: in this particular problem, the results
are the shortest paths connecting each starting points to the nearest goal as in
Fig. 9.b, in which a goal in the second room has been added.
6 Conclusions
In this paper we have described a solution to the Path-Planning Problem for a
non-holonomic Mobile Robot with a Cellular Automata approach. Some results
and properties of this work can be stated: 1) CA is a good formalism when
Decomposition Models are used to represent the environment (Occupancy Grid);
2) the algorithm is flexible, it can be used with different types of kinematics, just
changing the set of weights, and with robot with different shapes; 3) it is quite
simple to implement this algorithm directly on a SIMD machine; 4) it generates
all the collision-free trajectories, also with cluttered obstacles distributions, even
allowing to pass more than once in the same position; 5) trajectories found
are smoothed, while respecting the imposed kinematics constraints; 6) it is a
Reactive Path-Planner: it allows an incremental updating of the trajectories
every time a modification of the environment is detected by sensors, or the goal
changes (e.g. following other robots).
