A fast coalition structure search algorithm for modular robot reconfiguration planning under uncertainty

Ayan Dutta, Prithviraj Dasgupta, Jose Baca, Carl Nelson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of reconfiguration planning in modular robots. Current techniques for reconfiguration planning usually specify the destination configuration for a modular robot explicitly.We posit that in uncertain environments the desirable configuration for a modular robot is not known beforehand and has to be determined dynamically. In this paper, we consider this problem of how to identify a new’best’ configuration when a modular robot is unable to continue operating efficiently in its current configuration.We build on a technique that enumerates all the possible partitions of a set of modules requiring reconfiguring as a coalition structure graph (CSG) and finds the’best’ node in that graph. We propose a new data structure called an uncertain CSG (UCSG) that augments the CSG to handle uncertainty originating from the motion and performance of the robot. We then propose a new search algorithm called searchUCSG that intelligently prunes nodes from the UCSG using a modified branch and bound technique. Experimental results show that our algorithm is able to find a node that is within a worst bound of 80% of the optimal or best node in the UCSG while exploring only half the nodes in the UCSG. The time taken by our algorithm in terms of the number of nodes explored is also consistently lower than existing algorithms (that do not model uncertainty) for searching a CSG.

Original languageEnglish (US)
Title of host publicationDistributed Autonomous Robotic Systems - The 11th International Symposium
EditorsGregory Chirikjian, M. Ani Hsieh
PublisherSpringer Verlag
Pages177-191
Number of pages15
ISBN (Electronic)9783642551451
DOIs
StatePublished - 2014
Event11th International Symposium on Distributed Autonomous Robotic Systems, DARS 2012 - Baltimore, United States
Duration: Nov 8 2012Nov 11 2012

Publication series

NameSpringer Tracts in Advanced Robotics
Volume104
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Conference

Conference11th International Symposium on Distributed Autonomous Robotic Systems, DARS 2012
CountryUnited States
CityBaltimore
Period11/8/1211/11/12

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A fast coalition structure search algorithm for modular robot reconfiguration planning under uncertainty'. Together they form a unique fingerprint.

  • Cite this

    Dutta, A., Dasgupta, P., Baca, J., & Nelson, C. (2014). A fast coalition structure search algorithm for modular robot reconfiguration planning under uncertainty. In G. Chirikjian, & M. Ani Hsieh (Eds.), Distributed Autonomous Robotic Systems - The 11th International Symposium (pp. 177-191). (Springer Tracts in Advanced Robotics; Vol. 104). Springer Verlag. https://doi.org/10.1007/978-3-642-55146-8_13