## High Dimensional Deterministic Planners

##### Overview

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.

##### Benefits

- point-represented contact space
- smaller number of guards to represent the free space
- resolution completeness in lower (<=3) dimensional space
- easy extension to higher dimensional problems

##### Publications

Planning Motion in Point-Represented Contact Spaces Using Approximate Star-Shaped Decomposition, Jyh-Ming Lien and Yanyan Lu,

Paper (pdf) / BibTeX

*Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, Oct. 2009Paper (pdf) / BibTeX

##### Examples

**2D Free Flying Robot**(34 guards)

**3D Translational Robot**(8 guards)

**3D Free Flying Robot**(103 guards)

##### Related work

List of MASC Research Pages