Josh Casale's (Temporary) Project Site


My aim is to improve upon an existing framework for generating topologically-accurate approximations of Configuration Spaces.  I plan to introduce new heuristics for sampling and approximating higher-dimension C-Spaces, and in the final stages of the project, I will test the effectiveness of my solutions against known C-spaces of polyhedral objects.  The existing framework represents free space as an arrangement of contact surfaces, and approximates the C-Space with an adaptive volumetric grid.  This work is laid out in a series of papers from Manocha et al.[1] 


C-Space computation is a fundamental problem in algorithmic robotics and computational geometry, with important applications in fields such as motion planning, collision detection, layout and containment problems in manufacturing, spatial reasoning, assembly and task planning, and tolerance analysis and mechanism design.

In the worst-case, the combinatorial complexity of calculating exact free configuration space is exponential in the number of dimensions, and as such, representing and computing these spaces remains a major challenge, especially in higher dimensions.[2]  Because this problem has such far-reaching consequences, improving upon current techniques will serve as a springboard for further innovation.



The state-of-the-art in this particular problem is represented by the existing framework from Manocha et al that I plan to extend. 

 Three weeks:

·        Read through all current related literature

·         Cultivate a thorough understanding of the current techniques

·         Develop a working knowledge of C++ alongside in-class assignments

Six weeks:

·         Propose at least one new heuristic for sampling

·         Design an algorithm to implement said heuristic

Nine weeks:

·         Continue work on new heuristics

·         Conduct tests of existing heuristics and analyze results.

[2] Xinyu Zhang, Jia Pan, and Dinesh Manocha. Fast approximation of free configuration space using

regression and incremental learning. In conference submission, 2013.