Matrix completion as a post-processing technique for probabilistic roadmaps:

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(nlog2n) 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 th...