A block partitioning algorithm for modular robot reconfiguration under uncertainty

Ayan Dutra, Prithviraj Dasgupta, Jose Baca, Carl Nelson

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

3 Scopus citations

Abstract

We consider the problem of reconfiguring a modular self-reconfigurable robots (MSRs) in the presence of uncertainty due to operational limitations of the robot and dynamic nature of the environment. We employ a coalition game theory-based technique to address this problem by representing a configuration of the modules as a coalition structure and finding the 'best' configuration by searching for the optimal coalition structure. The key contribution of this paper is to speed up the search by making the observation that the maximum size a group or coalition of modules can have is limited to a maximum value, n max, which is determined by the operational and mobility constraints of the modules. We then propose an anytime algorithm called BlockPartitioning that uses integer partitioning along with an intelligent pruning technique to reject coalitions that are infeasible either due to their excessive size or due to excessive cost of coming together under current operational conditions. We have provided analytical results for our algorithm and also simulated it with different number of modules and different values of the maximum coalition size of an MSR called ModRED, and, shown that our algorithm takes nominal time to find the optimal solution (less than 1 sec. for up to 12 modules).

Original languageEnglish (US)
Title of host publication2013 European Conference on Mobile Robots, ECMR 2013 - Conference Proceedings
PublisherIEEE Computer Society
Pages255-260
Number of pages6
ISBN (Print)9781479902637
DOIs
StatePublished - 2013
Event2013 6th European Conference on Mobile Robots, ECMR 2013 - Barcelona, Spain
Duration: Sep 25 2013Sep 27 2013

Publication series

Name2013 European Conference on Mobile Robots, ECMR 2013 - Conference Proceedings

Conference

Conference2013 6th European Conference on Mobile Robots, ECMR 2013
CountrySpain
CityBarcelona
Period9/25/139/27/13

ASJC Scopus subject areas

  • Artificial Intelligence
  • Human-Computer Interaction

Fingerprint Dive into the research topics of 'A block partitioning algorithm for modular robot reconfiguration under uncertainty'. Together they form a unique fingerprint.

  • Cite this

    Dutra, A., Dasgupta, P., Baca, J., & Nelson, C. (2013). A block partitioning algorithm for modular robot reconfiguration under uncertainty. In 2013 European Conference on Mobile Robots, ECMR 2013 - Conference Proceedings (pp. 255-260). [6698851] (2013 European Conference on Mobile Robots, ECMR 2013 - Conference Proceedings). IEEE Computer Society. https://doi.org/10.1109/ECMR.2013.6698851