High Dimensional Deterministic Planners

Simplification or decomposition is a common strategy to handle large geometric models, which otherwise require excessive computation to process. Star-shaped decomposition partitions a shape into a set of star-shaped components. A shape is star shaped if and only if there exists at least one point which can see all the points in the shape. Due to this interesting property, decomposing a configuration space into star-shaped components can be beneficial, e.g., for solving motion planning problem. In this paper, we propose a simple method to decompose the contact space, represented by point set data, into “approximate star-shaped” components. We propose two motion planning methods, one deterministic and one probabilistic, both based on this idea. To the best of our knowledge, this is the first work that uses the star-shaped decomposition to solve motion planning problems in both low and high dimensional configuration spaces.



Planning Motion in Point-Represented Contact Spaces Using Approximate Star-Shaped Decomposition, Jyh-Ming Lien and Yanyan Lu, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2009
Paper (pdf) / BibTeX

Related work

List of MASC Research Pages
Computer Science @ George Mason University