Recent Results in Path Planning for Mobile Robots Operating in Vast Outdoor Environments

Abstract

Mobile robots operating in vast outdoor unstructured environments often only have incomplete maps and must deal with new objects found during traversal. Path planning in such sparsely occupied regions must be incremental to accommodate new information and must use efficient representations. In this paper we report recent results in path planning using an efficient data structure (framed quadtrees) and an optimal algorithm (D*) to incorporate knowledge of the environment as it incrementally discovered. In particular, we 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, the effect of partial information is 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 and results from both simulation and real experimentation are discussed.