Interactive Navigation in Complex Environments Using Path Planning

Brian Salomon, Maxim Garber, Ming C. Lin, and Dinesh Manocha

A portion of a path planned by our system

A portion of a path planned by our system. An avatar is shown traversing the path marked in red. The red squares indicate nodes of our roadmap graph searched to compute this path.

We have developed a system for navigation of massive environments using path planning. Our system provides the user with a "local driving mode" that keeps an avatar constrained to walkable surfaces in the model and a global path planner. Arbitrary configurations are specified by the user and a preprocessed graph is searched for a path between the configurations. The graph is generated using an algorithm based on the "visibility" PRM technique and the runtime path following uses the local driving mode to move the user along the path.



CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175


Our work was supported in part by ARO contract DAAD19-99-1-0162, NSF award ACI 9876914, ONR Young Investigator Award N00014-97-1-0631, a DOE ASCI grant, and by Intel Corporation.

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. In most cases, these works may not be reposted without the explicit permission of the copyright holder.