ICRA'09 Paper Abstract


Paper FrB13.1

Brass, Peter (City College New York), Gasparri, Andrea (UniversitÓ degli Studi Roma Tre), Cabrera-Mora, Flavio (The City University of New York), Xiao, Jizhong (City College of New York)

Multi-Robot Tree and Graph Exploration

Scheduled for presentation during the Regular Sessions "Distributed Robot Systems - II" (FrB13), Friday, May 15, 2009, 10:30−10:50, Room: 505

2009 IEEE International Conference on Robotics and Automation, May 12 - 17, 2009, Kobe, Japan

This information is tentative and subject to change. Compiled on January 21, 2022

Keywords Distributed Robot Systems, Autonomous Agents, Networked Robots


In this paper we present an algorithm for the exploration of an unknown graph with $k$ robots, which is guaranteed to succeed on any graph, and which on trees we prove to be near-optimal for two robots, having optimal dependence on the size of the tree but not on its radius. We believe that the algorithm performs well on any graph, and this is substantiated by simulations. For trees with $n$ edges and radius $r$, the exploration time is $frac{2n}{k} + O(r^{k-1})$, improving a recent method with $O(frac{n}{log k} + r)$ cite{FSKP06}, and almost reaching the lower bound $max(frac{2n}{k}, 2r)$. The algorithm is meant to be used in indoor navigation or cave search scenarios where the environment can be modeled as a graph. In this scenario, communication is realized by the devices being dropped by the robots at explored vertices, and the states of which are read and changed by further visiting robots. Simulations on Player/Stage platform have been performed in both tree and graph exploration which corroborate the mathematical results.



Technical Content © IEEE Robotics & Automation Society

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2022 PaperCept, Inc.
Page generated 2022-01-21  09:15:25 PST  Terms of use