LCS Publication Details
Publication Title: The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs
Publication Author: Bender, Michael A.
Additional Authors: Slonim, Donna K.
LCS Document Number: MIT-LCS-TM-535
Publication Date: 9-1-1995
LCS Group: Theory of Computation
Additional URL: No URL Given
Abstract:
We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for robots, which helps the robots recognize certain previously-seen nodes. We represent an algorithm in which the robots learn the graph and the homing sequence simultaneously by actively wandering through the graph.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.