Matrix completion as a post-processing technique for probabilistic roadmaps

Abstract

Inspired by the recent literature on matrix completion, this paper describes a novel post-processing algorithm for probabilistic roadmaps (PRMs). We argue that the adjacency matrix associated with real roadmaps can be decomposed into the sum of low-rank and sparse matrices. Given a PRM with n vertices and only $O(n{\log }^{2}n)$ collision-checked candidate edges, our algorithm numerically computes a relaxation of this decomposition, which estimates the status of all $n(n-1)/2$ possible edges in the full roadmap with high accuracy, without performing any additional collision checks. Typical results from our experiments on problems from the Open Motion Planning Library indicate that after checking $5\%$ of the possible edges, the algorithm estimates the full visibility graph with $96\%$ accuracy. The practical utility of the algorithm is that the average path length across the resulting denser edge set is significantly shorter (at the cost of somewhat increased spatial complexity and query times). An ancillary benefit is that the resulting low-rank plus sparse decomposition readily reveals information that would be otherwise difficult to compute, such as the number of convex cells in free configuration space and the number of vertices in each. We believe that this novel connection between motion planning and matrix completion provides a new perspective on sampling-based planning and may guide future algorithm development.