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.
Mhequb Hayat Abubakr Muhammad
Department of Computer Science LUMS School of Science & Engineering,Lahore,Pakistan Department of Electrical Engineering LUMS School of Science & Engineering,Lahore,Pakistan
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
4474-4479
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）