Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T02:13:16.633Z Has data issue: false hasContentIssue false
  • English
  • Français

searchUCSG: a fast coalition structure search algorithm for modular robot reconfiguration under uncertainty

Published online by Cambridge University Press:  13 February 2014

Ayan Dutta ,
Prithviraj Dasgupta ,
José Baca  and
Carl Nelson
Ayan Dutta*
Affiliation:
Computer Science Department, University of Nebraska at Omaha, Omaha, NE 68182, USA
Prithviraj Dasgupta
Affiliation:
Computer Science Department, University of Nebraska at Omaha, Omaha, NE 68182, USA
José Baca
Affiliation:
Computer Science Department, University of Nebraska at Omaha, Omaha, NE 68182, USA
Carl Nelson
Affiliation:
Mechanical and Materials Engineering Department, University of Nebraska-Lincoln, Lincoln, NE 68508, USA
*
*Corresponding author. E-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

We consider the problem of dynamic reconfiguration by modular self-reconfigurable robots (MSRs) in the presence of uncertainty in their motion and the environment. Specifically, we consider the situation where the MSR is unable to continue its motion in its current configuration and needs to identify a new configuration among the existing modules, which would be the most configuration suitable for performing the robot's assigned task under the current circumstances. To address this problem, we propose a new data structure called an uncertain coalition structure graph (UCSG) that accommodates uncertainty in the MSR's motion and the environment, using a framework from cooperative game theory called the coalition structure graph. We then propose a new search algorithm called searchUCSG that intelligently prunes nodes from the UCSG using a modified branch-and-bound technique. We have shown analytically that our algorithm is anytime, that is, if it terminates arbitrarily, it returns the best solution found thus far, which is guaranteed to be within a constant bound from the optimal solution. We have verified the performance of our algorithm experimentally in simulation and shown that it is able to find a solution that is within the worst bound of 80% of the optimal solution while exploring only half of the nodes in the UCSG. Our algorithm also takes lesser computation time than the existing algorithms (that do not model uncertainty) for solving similar problems. Finally, to verify the operation of our algorithm, we have implemented it to partition a set of mobile e-puck robots into clusters and shown how different number of robots and different robot motion uncertainty parameters affect the formed clusters.

Keywords

DARS2012Modular robotsMulti-robot systemsSpace roboticsAutomation
Type
Articles
Information
Robotica , Volume 32 , Issue 2: Distributed Autonomous Robotic Systems (DARS). , March 2014 , pp. 225 - 244
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Butler, Z., Brynes, S. and Rus, D., “Distributed Motion Planning for Modular Robots with Unit Decompressable Modules,” IEEE/RSJ International Conference on Intelligent Robots and Systems (2001) pp. 790–796.Google Scholar
2.Chirikjian, G., Pamecha, A. and Ebert-Uphoff, I., “Evaluating efficiency of self-reconfiguration in a class of modular robots,” Robot. Syst. 13, 317–338 (1996).Google Scholar
3.Chu, K., Hossain, S. G. M. and Nelson, C., “Design of a Four-DOF Modular Self-Reconfigurable Robot with Novel Gaits,” ASME International Design Enggineering Technical Conferences (DETC2011-47746) (2011).CrossRefGoogle Scholar
4.Dasgupta, P., Ufimtsev, V., Nelson, C. and Mamur, S. M. G., “Dynamic Reconfiguration in Modular Robots Using Graph Partitioning-Based Coalitions,” International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) (2012) pp. 121–128.Google Scholar
5.Evans, J., Optimization Algorithms for Networks and Graphs, Vol. 1 (CRC Press, Boca Raton, FL1992).Google Scholar
6.Hossain, S. M. G., Nelson, C., Dasgupta, P., “RoGenSiD A Rotary-Plate Genderless Single-Sided Docking Mechanism for Modular Self-Reconfigurable Robots, ASME 2013 International Design Engineering Technical Conferences (ASME IDETC) (Aug. 4–7, 2013).CrossRefGoogle Scholar
7.Kamimura, A., Yoshida, E., Murata, S., Hurokawa, H., Tomita, K. and Kokaji, S., “Distributed Self-Reconfiguration of M-TRAN III Modular Robotic System,” Intl. J. Robot. 27 (1), 373–386 (2008).Google Scholar
8.Meier, P., “Variance of a weighted mean,” Biometrics 9 (1), 59–73 (1953).CrossRefGoogle Scholar
9.Myerson, R., Game Theory: Analysis of Conflict (Harvard University Press, Cambridge, MA, 1997).Google Scholar
10.Narendra, M. and Fukunaga, K., “A branch and bound algorithm for feature subset selection,” IEEE Trans. Comput. 100 (9), 917–922 (1977).Google Scholar
11.Rahwan, T. and Jennings, N. “An Improved Dynamic Programming Algorithm for Coalition Structure Generation,” Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Vol. 3 (2008) pp. 1417–1420.Google Scholar
12.Rahwan, T., Ramchurn, S., Jennings, N. and Giovannucci, A., “An anytime algorithm for optimal coalition structure generation,” J. Artif. Intell. Res. (JAIR) 34, 521–567 (2009).Google Scholar
13.Ramaekers, Z., Dasgupta, P., Ufimtsev, V., Hossain, S. G. M. and Nelson, C., “Self-Reconfiguration in Modular Robots Using Coalition Games with Uncertainty,” Proceedings of the Automated Action Planning for Autonomous Mobile Robots Workshop (2011).Google Scholar
14.Ramchurn, S., Polukarov, M., Farinelli, A., Truong, C. and Jennings, N., “Coalition Formation with Spatial and Temporal Constraints,” Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (2010) pp. 1181–1188.Google Scholar
15.Rosa, M., Goldstein, S., Lee, P., Campbell, J. and Pillai, P., “Scalable Shape Sculpturing via Hole Motions,” Proceedings of 2006 IEEE International Conference on Robotics and Automation, Orlando, FL (2006) pp. 1462–1468.Google Scholar
16.Rothkopf, M., Pekeč, A. and Harstad, R., “Computationally manageable combinational auctions,” Manage. Sci. 44 (8), 1131–1147 (1998).Google Scholar
17.Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach (MIT Press, Cambridge, MA, 2008).Google Scholar
18.Sandholm, T., Larson, K., Andersson, M., Shehory, O. and Tohme, F., “Coalition structure generation with worst case guarantees,” Artif. Intell. 111 (1–2), 209–238 (1999).CrossRefGoogle Scholar
19.Sen, S. and Dutta, P. S., “Searching for Optimal Coalition Structures,” Proceedings of Fourth International Conference on Multi-Agent Systems (2000) pp. 287–292.Google Scholar
20.Shehory, O. and Kraus, S., “Methods for task allocation via agent coalition formation,” Artif. Intell. 101 (1), 165–200 (1998) (Elsevier).CrossRefGoogle Scholar
21.Stoy, K., Brandt, D. and Christensen, D., Self-Reconfigurable Robots: An Introduction (MIT Press, Cambridge, MA, 2010).Google Scholar
22.Winter, D., Biomechanics and Motor Control of Human Gait: Normal, Elderly and Pathological (Waterloo Biomechanics, Ontario Canada, 1991). ISBN 0-88898-105-8.Google Scholar
23.Yim, M.et al., “Modular self-reconfigurable robot systems: Challenges and opportunities for the future,” IEEE Robot. Autom. Mag. 14 (1), 43–53 (2007).CrossRefGoogle Scholar
24.Zilberstein, S., “Using Anytime Algorithms in Intelligent Systems,” AI Mag. 17 (3), 73 (1996).Google Scholar