Robotics: Science and Systems I

Single-Cluster Spectral Graph Partitioning for Robotics Applications

Edwin Olson, Matthew Walter, Seth Teller, John Leonard

Abstract: We present SCGP, an algorithm for finding a single cluster of well-connected nodes in a graph. The general problem is NP-hard, but our algorithm produces an approximate solution in O(N2) time by considering the spectral properties of the graph's adjacency matrix. We show how this algorithm can be used to find sets of self-consistent hypotheses while rejecting incorrect hypotheses, a problem that frequently arises in robotics. We present results from a range-only SLAM system, a polynomial time data association algorithm, and a method for parametric line fitting that can outperform RANSAC.



    AUTHOR    = {Edwin Olson and Matthew Walter and Seth Teller 
                 and John Leonard},
    TITLE     = {Single-Cluster Spectral Graph Partitioning
                 for Robotics Applications},
    BOOKTITLE = {Proceedings of Robotics: Science and Systems},
    YEAR      = {2005},
    ADDRESS   = {Cambridge, USA},
    MONTH     = {June},
    DOI       = {10.15607/RSS.2005.I.035}