The Cye Personal Robot Path Planner
Description
Robust mobile robot navigation in real world environments is a long
standing problem in robotics. In this paper, we describe research in
navigation and path generation using the Probotics Cye robot. Cye is a
2-wheeled differential drive robot, whose primary mode of navigation
is ded-reckoning. The only sensors are wheel encoders - there are no
other active or passive sensing modes. The accuracy of the
ded-reckoning is sufficient for indoor navigation, through the use of
carefully designed wheels and a set of known calibration surfaces, or
"check points". An (inaccurate, incomplete) map of the world is
interactively constructed using Cye, in which known free space, known
obstacle areas, and unexplored areas are all marked. Path generation
in such an environment has the following challenges:
- Maintaining adequate distance from walls and other obstacles.
- The use of check points must be incorporated into the path planner,
to minimize ded-reckoning error.
- The robot should ideally used explored areas, but should be willing to
traverse unexplored areas if no suitable path through an explored area
is found.
- Path generation time must be short, as this is a robot which is
designed for both research and consumer use.
We solve these problems using a novel approach to the potential field
method. In the first stage, a standard potential field describing the
distance of any given world point to the nearest obstacle is
created. In this field, unexplored areas are marked with a
predetermined "pseudo-distance". This pseudo-distance is key to
allowing the use of unexplored areas when necessary. In the second
stage, a potential field is created in which each world point is the
distance to the goal, non-linearly weighted by that point's distance
to the nearest obstacle. The weighing is done such that points very
close to an obstacle or points in unexplored areas avoided if at all
possible. However, if a complete path cannot be generated in "safe"
areas, then the path will use these potentially unsafe areas.
After an initial path is found using this method, the next step is to
search for checkpoints. This is done by growing out a field from the
complete path, to measure the distance from known checkpoints to the
path. A search is then done which minimizes the robot's deviation,
while finding checkpoints which are necessary to reduce error. After
an appropriate set of checkpoints are found, the system plans paths to
these checkpoints using the above method.
This planner has been operating in the real world now for about 4
months, and is being used by robotics hobbyists and researchers. The
robot is capable of navigating distances of over a 1/10th of a mile
indoors, through narrow corridors and doorways, completing its path
without getting lost.
Images
The Cye Robot:
Path Planner:
Publications
Batavia, P. H., Nourbakhsh, I., Path Planning for the Cye Robot,, Submitted to the IEEE International Conference on Robots and Systems, 2000.
Parag Batavia, The Robotics Institute, Carnegie Mellon University
parag@ri.cmu.edu
Last modified: Thu Apr 13 10:17:21 EDT 2000