Jump to: navigation, search

Spectral Analysis and Enhancement of Probabilistic Roadmap Method for Robot Motion Planning

Fig. 1 Motion Planning Problem (Example)
Fig. 1 Motion Planning Problem (Example)

Probabilistic Roadmap Method (PRM)
Probabilistic Roadmap Method (PRM) \scriptstyle[1] is an extremely effective motion planning construct in robotics that captures the connectivity of a high dimensional configuration space \scriptstyle\mathcal{C}_{space} cluttered with obstacles and narrow passages. In PRM, random (samples) configurations (\scriptstyle[0\ 1]^d) are taken and tested whether they are in free space \scriptstyle\mathcal{C}_{free},\ \scriptstyle[Fig.\ 2]. These collision-free configurations (nodes) are further checked for feasible paths (edges) between them. Space between all combinations of two nodes are checked for collision. These nodes and edges form a graph representing collision-free configurations and paths between them in \scriptstyle\mathcal{C}_{free}. This graph can easily be traversed for finding path between start and goal configuration.

Spectral Analysis of PRM Graph
The graph \scriptstyle (G)can be represented as \scriptstyle G=(V,E), where \scriptstyle V and \scriptstyle E refers to vertices (nodes) and Edges, respectively. The Laplacian matrix of Graph is \textstyle L:=(a_{i,j})_{n\times n} is defined as:

\textstyle a_{i,j} := \Bigg\{ \begin{array}{ll}
deg(v_{i}) & : i=j\\
-1 & :i\neq j\ \textrm{and}\ v_{i}, v_{j}\ \textrm{are\ adjacent}\\
0 & : \textrm{otherwise}

Laplacian matrix gives important information about graph. The eigen-vector decomposition of laplacian matrix can be used to find algebraic connectivity of a graph. This is also called spectrum of graph \scriptstyle[Fig.\ 3]. Every PRM graph has different spectrum, from where we get spectral properties. These properties can be used to detect narrow passages in \scriptstyle\mathcal{C}_{space}, \scriptstyle[2,\ 3] (work of CyPhyNets). This process of analyzing and exploration of different properties about graph is spectral analysis.

Project Abstract
We intend to explore the spectral properties of the PRM graph and subsequently find the connection between spectral geometry of configuration spaces and the topological and geometrical obstructions encountered by motion planning algorithms. This can lead to new motion planning algorithms in robotics or perhaps a way of characterizing configuration spaces from a spectral perspective.

Fig. 2 Random Sampling Example (50 Samples)
Fig. 2 Random Sampling Example (50 Samples)
Fig. 3 Spectrum Plot (Values: Red (+ve), Blue (-ve) and Black (0)) (400 Samples)
Fig. 3 Spectrum Plot (Values: Red (+ve), Blue (-ve) and Black (0)) (400 Samples)

[1] L.E. Kavraki, P. Svestka, J.C. Latombe and M. H. Overmars, "Probabilistic roadmaps for path planning in high-dimensional configuration spaces", IEEE Transactions on Robotics and Automation, 12 (4): 566–580, 1996.

[2] Hassan Mohy-ud-Din and Abubakr Muhammad, Detecting Narrow Passages in Configuration Spaces Via Spectra of Probabilistic Roadmaps, SAC’10, March 22-26, 2010, Sierre, Switzerland.

[3] Abubakr Muhammad and Mhequb Hayat, Spectral Properties of Probabilistic Roadmaps. (Submitted)

Personal tools