TY - GEN

T1 - Time complexity of motion planning algorithm for homogeneous combinatorial robots

AU - Ho, Ng Fa

AU - Tai, Hong Shuo

PY - 2006

Y1 - 2006

N2 - Some properties and an algorithm of the motion planning problem of homogeneous combinatorial robots are presented. Homogeneous combinatorial robots can be combined and separated freely in the process of moving. The motion planning problem of homogeneous combinatorial robots in a static discrete environment is proven to be compliant to the principle of optimality. A backward dynamic motion planning algorithm is used to find the optimal motion plans. Suppose that|V| is the number of all vertices in the graph, n is the number of robots, and k is the number of stages robots passing the graph. The time complexity without considering the limitation function of this problem is 0(|V|2nk). Furthermore, the time complexity with the limitation function of the problem is presented.

AB - Some properties and an algorithm of the motion planning problem of homogeneous combinatorial robots are presented. Homogeneous combinatorial robots can be combined and separated freely in the process of moving. The motion planning problem of homogeneous combinatorial robots in a static discrete environment is proven to be compliant to the principle of optimality. A backward dynamic motion planning algorithm is used to find the optimal motion plans. Suppose that|V| is the number of all vertices in the graph, n is the number of robots, and k is the number of stages robots passing the graph. The time complexity without considering the limitation function of this problem is 0(|V|2nk). Furthermore, the time complexity with the limitation function of the problem is presented.

UR - http://www.scopus.com/inward/record.url?scp=34250702193&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250702193&partnerID=8YFLogxK

U2 - 10.1109/SICE.2006.314875

DO - 10.1109/SICE.2006.314875

M3 - Conference contribution

AN - SCOPUS:34250702193

SN - 8995003855

SN - 9788995003855

T3 - 2006 SICE-ICASE International Joint Conference

SP - 4280

EP - 4284

BT - 2006 SICE-ICASE International Joint Conference

T2 - 2006 SICE-ICASE International Joint Conference

Y2 - 18 October 2006 through 21 October 2006

ER -