Being there, being the RRT: Space-filling and searching in place with minimalist robots Conference Paper uri icon

abstract

  • Inspired by the Rapidly Exploring Random Tree data-structure and algorithm for path planning in high-dimensional, continuous spaces, we consider an approach for spanning a space with a group of simple robots. We employ a minimalist approach in which contact sensors form the primary means of communication; the agent's physically embody the elements of the tree through their position and other agents can either follow the tree to useful locations or expand the tree by becoming part of it. Although robots are constrained in some of the operations they may perform in space, we argue that the original space filling aspects of the original data-structure remain in our implementation. We demonstrate that one may perform a planning query from a point to the tree origin directly via message passing where passing involves direct physical motion or simple IR messages. Based on the work done by Werger and Matari, our implementation proves that it is possible to form and maintain a RRT using simple position unaware robots. The work is important because it demonstrates that decentralized path planning can be performed by simple agents using purely reactive behaviors and at the same time poses significant challenges to keep the shape of the tree intact using position unaware robots. Copyright 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.

published proceedings

  • AAAI Spring Symposium - Technical Report

author list (cited authors)

  • Ghoshal, A., & Shell, D. A.

complete list of authors

  • Ghoshal, A||Shell, DA

publication date

  • August 2011