July
2011
Path Planning with Adaptive Dimensionality
Authors:
Abstract:
Path planning quickly becomes computationally hard as the dimensionality of the state-space increases. In this paper, we present a planning algorithm intended to speed up path planning for high-dimensional state-spaces such as robotic arms. The idea behind this work is that while planning in a high-dimensional state-space is often necessary to ensure the feasibilityof the resulting path, large portions of the path have a lower-dimensional structure. Based on this observation, our algorithm iteratively constructs a state-space of an adaptive dimensionality--a state-space that is high-dimensional only where the higher dimensionality is absolutely necessary for finding a feasible path. This often reduces drastically the size of the state-space, and as a result, the planning time and memory requirements. Analytically, we show that our method is complete and is guaranteed to find a solution if one exists, within a specified suboptimality bound. Experimentally, we apply the approach to 3D vehicle navigation (x, y, heading), and to a 7 DOF robotic arm on the Willow Garage’s PR2 robot. The results from our experiments suggest that ourmethod can be substantially faster than some of the state-of-the-art planning algorithms optimized for those tasks.
copied = false, 2000);
">
@conference{Gochev-2011-109567,
author = {Kalin Gochev And Benjamin Cohen And Jonathan Butzke And Alla Safonova And Maxim Likhachev},
title = {Path Planning with Adaptive Dimensionality},
booktitle = {Proceedings of 4th Annual Symposium on Combinatorial Search (SoCS '11)},
year = {2011},
month = {July},
pages = {52 - 59},
}
author = {Kalin Gochev And Benjamin Cohen And Jonathan Butzke And Alla Safonova And Maxim Likhachev},
title = {Path Planning with Adaptive Dimensionality},
booktitle = {Proceedings of 4th Annual Symposium on Combinatorial Search (SoCS '11)},
year = {2011},
month = {July},
pages = {52 - 59},
}