There already exists a large number of classical path planning methods. However, many of these techniques are not amenable to sensor based interpretation. It is not possible to simply add a step to acquire sensory information, and then construct a plan from the acquired model using a classical technique, since the robot needs a path planning strategy in the first place to acquire the world model.

The first principal problem in sensor based motion planning is the *
find-goal* problem. In this problem, the robot seeks to use its on-board
sensors to find a collision free path from its current configuration to a goal
configuration. In the first variation of the find goal problem, which we term
the * absolute find-goal * problem, the absolute coordinates of the
goal configuration are assumed to be known. A second variation on this
problem is described below.

The second principal problem in sensor based motion planning is *
sensor-based exploration*, in which a robot is not directed to seek a
particular goal in an unknown environment, but is instead directed to explore
the apriori unknown environment in such a way as to see all potentially
important features. The exploration problem can be motivated by the following
application. Imagine that a robot is to explore the interior of a collapsed
building, which has crumbled due to an earthquake, in order to search for
human survivors. It is clearly impossible to have knowledge of the building's
interior geometry prior to the exploration. Thus, the robot must be able to
see, with its on-board sensors, all points in the building's interior while
following its exploration path. In this way, no potential survivors will be
missed by the exploring robot. Algorithms that solve the find-goal problem
are not useful for exploration because the location of the ``goal'' (a human
survivor in our example) is not known. A second variation on the find-goal
problem that is motivated by this scenario and which is an intermediary
between the find-goal and exploration problems is the * recognizable *
find-goal problem. In this case, the absolute coordinates of the goal are
not known, but it is assumed that the robot can recognize the goal if it
becomes with in line of sight. The aim of the recognizable find-goal
problem is to explore an unknown environment so as to find a recognizable
goal. If the goal is reached before the entire environment is searched,
then the search procedure is terminated.

In prior work we developed a scheme to solve one type of exploration
problem. As a byproduct, the algorithm can then also solve both variations
of the find-goal problem. The algorithm is based on the * Generalized
Voronoi Graph * (GVG), which is a roadmap. We have developed an
incremental approach to constructing the GVG of an unknown environment
strictly from sensor data. We only assume that the robot has a dead
reckoning system and on board sensors that measure distance and direction to
nearby obstacles.

In collaboration with JPL, we have been developing algorithms for the autonomous navigation of future Mars Rover vehicles. These algorithms (the "WedgeBug" and "RoverBug" algorithms) are the sensor-based analogies to the classical tangent graph algorithm, but assume no apriori knowledge of the robot's environment, and also take the limited field-of-view of the rover's cameras into account. See this page for more detail and some fancy figures related to this project.

Our current research activities center around how to incorporate uncertainty into sensor-based planning.

- Howie Choset (now in the dept. of mechanical engineering at CMU)
- Sharon Laubach (Now at JPL)
- Kristo Kriechbaum
- Sam Pfister
- Dr. Stergios Roumeliotis