ICRA 2011 Paper Abstract


Paper ThA102.4

Hayat, Mhequb (LUMS School of Science & Engineering, Pakistan), Muhammad, Abubakr (LUMS School of Science & Engineering, Pakistan)

Spectral Properties of Expansive Configuration Spaces: An Empirical Study

Scheduled for presentation during the Regular Sessions "Planning, Scheduling and Coordination" (ThA102), Thursday, May 12, 2011, 09:05−09:20, Room 3C

2011 IEEE International Conference on Robotics and Automation, May 9-13, 2011, Shanghai International Conference Center, Shanghai, China

This information is tentative and subject to change. Compiled on August 18, 2019

Keywords Motion and Path Planning, Planning, Scheduling and Coordination, Collision Avoidance


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.



Technical Content © IEEE Robotics & Automation Society

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2019 PaperCept, Inc.
Page generated 2019-08-18  14:20:13 PST  Terms of use