Interactive Navigation in Complex Environments Using Path Planning

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

Abstract

We present a novel approach for interactive navigation in complex 3D synthetic environments using path planning. Our algorithm precomputes a global roadmap of the environment by combining a variant of randomized motion planning algorithm with a reachability-based analysis. At runtime, the algorithm performs graph searching and automatically computes a collision-free and constrained path between two user specified locations. It also
enables local user-steered exploration, subject to motion constraints and integrates these capabilities in the control loop of 3D interaction. Our approach requires no semantic or functional information about the model and the performance of the preprocessing algorithm grows as a linear function of the model size. We demonstrate its performance on two complex environments: a power plant and a factory room.

Publication

Interactive Navigation in Complex Environments Using Path Planning
Brian Salomon, Maxim Garber, Ming C. Lin and Dinesh Manocha
ACM SIGGRAPH 2003 Symposium on Interactive 3D Graphics pdf(721k)

Video

Click for the video accompanying our paper at the I3D conference.

For more information see the web pages at the University of North Carolina on Motion Planning and Navigation.

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.