An Efficient On-line Path Planner for Outdoor Mobile Robots Operating in Vast Environments

Alex Yahja, Sanjiv Singh and Anthony (Tony) Stentz
Journal Article, Robotics and Autonomous Systems, Vol. 33, No. 2, pp. 129-143, August, 2000

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Mobile robots operating in outdoor unstructured environments often have only incomplete maps and must deal with new objects found during traversal. Path planning in these environments must be incremental to accommodate new information and must use efficient representations. This article reports recent results in path planning using an efficient data structure (framed-quadtrees) and an optimal algorithm (D*) to incrementally replan optimal paths. We show how the use of framed-quadtrees leads to paths that are shorter and more direct than when other representations are used. We also show the difference in performance when the robot starts with no information about the world versus when it starts with partial information about the world. Our results indicate that, as would be expected, starting with partial information is better than starting with no information. However, in many cases, partial information results in performance that is almost as good as starting out with complete information about the world, while the computational cost incurred is significantly lower. Our system has been tested in simulation as well on an autonomous jeep equipped with local obstacle avoidance capabilities. Results from both simulation and real experimentation are discussed.

author = {Alex Yahja and Sanjiv Singh and Anthony (Tony) Stentz},
title = {An Efficient On-line Path Planner for Outdoor Mobile Robots Operating in Vast Environments},
journal = {Robotics and Autonomous Systems},
year = {2000},
month = {August},
volume = {33},
number = {2},
pages = {129-143},
keywords = {optimal path planning, framed quadtrees, outdoor mobile robots, unstructured environments},
} 2019-06-28T10:54:07-04:00