Motion planning for metamorphic systems: Feasibility, decidability, and distributed reconfiguration

被引:31
作者
Dumitrescu, A [1 ]
Suzuki, I
Yamashita, M
机构
[1] Univ Wisconsin, Dept Comp Sci, Milwaukee, WI 53201 USA
[2] Kyushu Univ, Dept Comp Sci & Comp Engn, Fukuoka 8128581, Japan
来源
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION | 2004年 / 20卷 / 03期
关键词
decidability; metamorphic systems; motion planning; reconfiguration;
D O I
10.1109/TRA.2004.824936
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
In this paper, we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that applies to a relatively large subclass of configurations, called horizontally convex configurations. We then discuss several fundamental questions in the analysis of metamorphic systems. In particular, the following two questions are shown to be decidable: 1) whether a given set of motion rules maintains connectivity; 2) whether a goal configuration is reachable from a given initial configuration (at specified locations). In the general case in which each module has an internal state, the following is shown to be undecidable: given a set of motion rules, whether there exists a certain type of configuration called a uniform straight-chain configuration that yields a disconnected configuration.
引用
收藏
页码:409 / 418
页数:10
相关论文
共 15 条
[1]
Burks A.W., 1970, Essays on Cellular Automata
[2]
Butler Z, 2002, 2002 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS I-IV, PROCEEDINGS, P809, DOI 10.1109/ROBOT.2002.1013457
[3]
Chirikjian G, 1996, J ROBOTIC SYST, V13, P317, DOI 10.1002/(SICI)1097-4563(199605)13:5<317::AID-ROB5>3.0.CO
[4]
2-T
[5]
DEMAINE E, 2002, MORE GAMES NO CHANCE, P405
[6]
DUMITRESCU A, IN PRESS INT J ROBOT
[7]
A SEMIRING ON CONVEX POLYGONS AND ZERO-SUM CYCLE PROBLEMS [J].
IWANO, K ;
STEIGLITZ, K .
SIAM JOURNAL ON COMPUTING, 1990, 19 (05) :883-901
[8]
MURATA S, 1994, IEEE INT CONF ROBOT, P441, DOI 10.1109/ROBOT.1994.351257
[9]
NGUYEN A, 2000, P IEEE INT WORKSH AL
[10]
Useful metrics for modular robot motion planning [J].
Pamecha, A ;
EbertUphoff, I ;
Chirikjian, GS .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1997, 13 (04) :531-545