## 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

Name | Position | |
---|---|---|

Edwin Olson | eolson@mit.edu | Alumni |

Matthew Walter | mwalter@csail.mit.edu | Alumni |

John Leonard | jleonard@mit.edu | Faculty |

Seth Teller | teller@csail.mit.edu | Faculty |

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