Single Cluster Graph Partitioning (SCGP) for Robotics Applications

Summary

We present 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(n^2)$ 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.

This work was presented at the Robotics Science and Systems conference in June, 2005.

RSS 2005 Conference Materials

• The paper: PDF (514 KB)

  @inproceedings{OlsonSCGP2005,
  	author="Edwin Olson and Matthew Walter and John Leonard and Seth Teller",
  	title="Single Cluster Graph Partitioning for Robotics Applications",
  	booktitle="Proceedings of Robotics Science and Systems",
  	pages="265-272",
  	year={2005}
  }
  

• Our spotlight slides PPT
• The poster we presented PDF CDR

People

Robotics, Vision, and Sensor Networks Group 32 Vassar Street, 32-33x Cambridge, MA 02139 Tel: 617-253-6583 Fax: 617-258-7413