Efficient coordinated motion

被引:5
作者
Basu, A [1 ]
Elnagar, A
Al-Hajj, R
机构
[1] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2H1, Canada
[2] Univ Sharjah, Dept Comp Sci, Sharjah, U Arab Emirates
[3] Amer Univ Sharjah, Dept Comp Sci & Math, Sharjah, U Arab Emirates
关键词
coordinated motion; efficient block movement; complexity analysis;
D O I
10.1016/S0895-7177(99)00222-8
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The problem of efficiently coordinating the motion of multiple objects is examined. It is assumed that there is sufficient space without objects to guarantee a solution. For simplifying the analysis, we also consider all objects to have the same size. A new divide-and-solve technique is proposed for addressing coordinated motion problems. The algorithm suggested divides a problem into subproblems, solves the smaller problems locally, exchanges objects across the local boundaries, and repeats the process until the desired configuration is achieved. It is shown that the average complexity of such an algorithm is much better compared to naive methods for solving this problem (C) 2000 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码:39 / 53
页数:15
相关论文
共 21 条
[1]  
Aho A. V., 1983, DATA STRUCTURES ALGO
[2]  
CHIACCHIO P, 1994, P 1994 AM CONTR C, V1
[3]  
CORRIGAN K, 1996, P TECHN PROGR, V2, P823
[4]   Two-arm trajectory planning in a manipulation task [J].
Garvin, GJ ;
Zefran, M ;
Henis, EA ;
Kumar, V .
BIOLOGICAL CYBERNETICS, 1997, 76 (01) :53-62
[5]  
Guo W. G., 1996, Proceedings of the IEEE International Conference on Industrial Technology (ICIT'96) (Cat. No.96TH8151), P493, DOI 10.1109/ICIT.1996.601638
[6]   ON THE COMPLEXITY OF MOTION PLANNING FOR MULTIPLE INDEPENDENT OBJECTS - PSPACE-HARDNESS OF THE WAREHOUSEMANS PROBLEM [J].
HOPCROFT, JE ;
SCHWARTZ, JT ;
SHARIR, M .
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1984, 3 (04) :76-88
[7]  
HOPCROFT JE, 1984, 84616 CORN U
[8]  
Kornhauser D., 1984, P 25 IEEE S FDN COMP, P241
[9]  
KOSUGE K, 1994, P IEEE RSJ GI INT C, V4, P1042
[10]  
Kumar K, 1996, ELECTRON INFORM PLAN, V23, P233