Adam R. Bates, Avleen S. Bijral, Jane Mulligan, and Greg Grudic; ICRA 2009 Accepted.

Many terrains in outdoor robot navigation problems have paths that are
distinct and continuous compared to the non-traversable regions. In
image space these paths correspond to continuous segments that can be
thought of as clusters embedded in image feature space. These segments
very often translate directly to traversable ground plane. In this paper
we build the intuition for semi-supervised methods in path
identification and present a Markov random walk based approach that
requires very few labeled points. The method creates a nearest neighbor
graph representation of the current image frame using features deemed
suitable for the task and propagates labels based on the concept of
absorbing Markov chains. We extend this formalism to the task of
dynamically identifying traversable and non-traversable regions in the
incoming image frames. We present results on actual terrains
corresponding to test courses used by the LAGR test team. The results
demonstrate that with minimal initial supervision the robot can navigate
to the goal. We also conduct comparisons of our path labeling technique
against other machine learning techniques including nonlinear support
vector machines on hand labeled data. The results demonstrate that our
semi-supervised approach is proficient in the domain of path traversal
in unstructured domains.