Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:An efficient algorithm for self-reconfiguration planning in a modular robot
Authors: Thomas Larkworthy ; Subramanian Ramamoorthy
Date:May 2010
Publication Title:Proc. IEEE International Conference on Robotics and Automation, 2010.
Publication Type:Conference Paper Publication Status:Published
An efficient planning algorithm for the hexagonal metamorphic self-reconfiguring system (SRS) is presented. Empirically, the algorithm achieves an time complexity of O(n) averaged over random problem instances. The planning algorithm is capable of solving approximately 97% of planning tasks in the general state space of configurations containing less than 20,000 units. The state space is divided into two classes according to planning efficiency. The configurations belonging to the first class permit an Euler tour to be wrapped around the robotic aggregate. The existence of the Euler tour implies units are free to move around the perimeter of the SRS. Planning between configurations in this class can be performed in O(n) using a specialized planning algorithm. The set of Euler tour configurations span a large volume of the general state space of the hexagonal SRS. A second specialized planning algorithm plans from a general configuration to a nearby Euler tour configuration. While planning in the general configuration state space is computationally harder, the distance required to plan is short. Thus, the combination of both algorithms allows us to efficiently plan for a large proportion of possible reconfiguration tasks for the hexagonal metamorphic robot.
2010 by The University of Edinburgh. All Rights Reserved
Links To Paper
1st Link
Bibtex format
author = { Thomas Larkworthy and Subramanian Ramamoorthy },
title = {An efficient algorithm for self-reconfiguration planning in a modular robot},
book title = {Proc. IEEE International Conference on Robotics and Automation, 2010.},
year = 2010,
month = {May},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh