Time complexity of motion planning algorithm for homogeneous combinatorial robots

Ng Fa Ho; Hong Shuo Tai

doi:10.1109/SICE.2006.314875

Time complexity of motion planning algorithm for homogeneous combinatorial robots

Ng Fa Ho^*, Hong Shuo Tai

^*Corresponding author for this work

Department of Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2006 SICE-ICASE International Joint Conference
Pages	4280-4284
Number of pages	5
DOIs	https://doi.org/10.1109/SICE.2006.314875
Publication status	Published - 2006
Event	2006 SICE-ICASE International Joint Conference - Busan, Korea, Republic of Duration: 2006 Oct 18 → 2006 Oct 21

Publication series

Name	2006 SICE-ICASE International Joint Conference

Conference

Conference	2006 SICE-ICASE International Joint Conference
Country/Territory	Korea, Republic of
City	Busan
Period	2006/10/18 → 2006/10/21

ASJC Scopus subject areas

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering

Access to Document

10.1109/SICE.2006.314875

Cite this

@inproceedings{3f02c68287cb40e4935346a1b5555b06,

title = "Time complexity of motion planning algorithm for homogeneous combinatorial robots",

abstract = "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.",

author = "Ho, {Ng Fa} and Tai, {Hong Shuo}",

year = "2006",

doi = "10.1109/SICE.2006.314875",

language = "English",

isbn = "8995003855",

series = "2006 SICE-ICASE International Joint Conference",

pages = "4280--4284",

booktitle = "2006 SICE-ICASE International Joint Conference",

note = "2006 SICE-ICASE International Joint Conference ; Conference date: 18-10-2006 Through 21-10-2006",

}

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 -

Time complexity of motion planning algorithm for homogeneous combinatorial robots

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this