2002 · 181 citations · 14 references
EngineeringComputer ScienceMathematicsAlgorithmsMachine LearningRobot LearningAutonomous ExplorationGraph-based LearningHuman-robot Interaction LearningMulti-robot ExplorationMulti-robot LearningRandom WalksActive Learning For Robot LearningCollaborative Robot LearningCooperative Robot LearningExplorationRandom Walk AlgorithmsRandom Walks On Graphs
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 two robots which helps the robots recognize certain previously-seen nodes. We then present an algorithm in which the robots learn the graph and the homing sequence simultaneously by wandering actively through the graph. Unlike most previous learning results using homing sequences, our algorithm does not require a teacher to provide counterexamples. Furthermore, the algorithm can use efficiently any additional information available that distinguishes nodes. We also present an algorithm in which the robots learn by taking random walks. The rate at which a random walk converges to the stationary distribution is characterized by the conductance of the graph. Our random-walk algorithm learns in expected time polynomial in n and in the inverse of the conductance and is more efficient than the homing-sequence algorithm for high-conductance graphs.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
14
Learning regular sets from queries and counterexamples
Dana Angluin · Information and Computation · 1987 · 2.1K citations