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

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


Download
  • Adobe portable document format (pdf) (306KB)
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.

Abstract
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.

Keywords
optimal path planning, framed quadtrees, outdoor mobile robots, unstructured environments

Notes
Number of pages: 15

Text Reference
Alex Yahja, Sanjiv Singh, and Anthony (Tony) Stentz, "An Efficient On-line Path Planner for Outdoor Mobile Robots Operating in Vast Environments," Robotics and Autonomous Systems, Vol. 33, No. 2&3, August, 2000, pp. 129-143.

BibTeX Reference
@article{Yahja_2000_3330,
   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",
   pages = "129-143",
   publisher = "Elsevier Science",
   address = "P.O.Box 211, 1000 AE Amsterdam, The Netherlands",
   month = "August",
   year = "2000",
   volume = "33",
   number = "2&3",
}