Spectral properties of expansive configuration spaces: An empirical study

Motion planning in high dimensional configuration space is an intractable problem. Sampling based motion planning is considered as one of the best ways to tackle the "curse of dimensionality" and to model the configuration space. In these methods (e.g. probabilistic roadmap (PRM)), a graph is produced by random nodes of valid configurations. As the number of the nodes N increases, for expansive configuration spaces the failure probability of PRM planner exponentially approaches zero; but computing expansiveness property is not feasible for most interesting problems. Another major hurdle is narrow passages detection. Therefore, we need easily computable ways to characterize the properties of configuration spaces. We propose a new framework for narrow passage detection using spectral analysis of the graph Laplacian of the PRM. We give empirical evidences to show that eigenvalues and eigenvectors reveal useful information about number and size of narrow passages, visibility and expansiveness. Simulations on various motion planning scenarios are done to verify the framework.