Motion planning algorithm for homogeneous combinatorial robots in time-varying environment

Hong Fa Ho; Wen Cheng Liu

doi:10.1109/ISIC.2007.4450864

Motion planning algorithm for homogeneous combinatorial robots in time-varying environment

Hong Fa Ho^*, Wen Cheng Liu

^*Corresponding author for this work

Department of Electrical Engineering

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

1 Citation (Scopus)

Abstract

This paper introduces the concept of homogeneous combinatorial robots, specifying their properties and algorithms needed to solve the problems in motion-planning. In this paper, "homogeneous combinatorial robots" are a set of robots that can be combined and separated freely in motion. The complexity and obstacles of motion planning are explained in terms of the principle of optimality. To plan the optimal paths in time-varying environment for those robots, a dynamic programming algorithm is developed and proposed in the paper. Suppose η is the maximum number of vertices of the time-varying graph, n is the number of robots, and k is the number of steps of the motion plan. The time complexity of this problem is O(η^2nk).

Original language	English
Title of host publication	22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control
Publisher	IEEE Computer Society
Pages	77-82
Number of pages	6
ISBN (Print)	142440441X, 9781424404414
DOIs	https://doi.org/10.1109/ISIC.2007.4450864
Publication status	Published - 2007
Event	2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007 - Singapore, Singapore Duration: 2007 Oct 1 → 2007 Oct 3

Publication series

Name	22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control

Conference

Conference	2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007
Country/Territory	Singapore
City	Singapore
Period	2007/10/01 → 2007/10/03

ASJC Scopus subject areas

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering
Modelling and Simulation

Access to Document

10.1109/ISIC.2007.4450864

Cite this

Ho, H. F., & Liu, W. C. (2007). Motion planning algorithm for homogeneous combinatorial robots in time-varying environment. In 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control (pp. 77-82). Article 4450864 (22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control). IEEE Computer Society. https://doi.org/10.1109/ISIC.2007.4450864

Motion planning algorithm for homogeneous combinatorial robots in time-varying environment. / Ho, Hong Fa; Liu, Wen Cheng.
22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control. IEEE Computer Society, 2007. p. 77-82 4450864 (22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control).

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

Ho, HF & Liu, WC 2007, Motion planning algorithm for homogeneous combinatorial robots in time-varying environment. in 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control., 4450864, 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control, IEEE Computer Society, pp. 77-82, 2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007, Singapore, Singapore, 2007/10/01. https://doi.org/10.1109/ISIC.2007.4450864

Ho HF, Liu WC. Motion planning algorithm for homogeneous combinatorial robots in time-varying environment. In 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control. IEEE Computer Society. 2007. p. 77-82. 4450864. (22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control). doi: 10.1109/ISIC.2007.4450864

Ho, Hong Fa ; Liu, Wen Cheng. / Motion planning algorithm for homogeneous combinatorial robots in time-varying environment. 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control. IEEE Computer Society, 2007. pp. 77-82 (22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control).

@inproceedings{c4862cceee82401c8daa749016f27089,

title = "Motion planning algorithm for homogeneous combinatorial robots in time-varying environment",

abstract = "This paper introduces the concept of homogeneous combinatorial robots, specifying their properties and algorithms needed to solve the problems in motion-planning. In this paper, {"}homogeneous combinatorial robots{"} are a set of robots that can be combined and separated freely in motion. The complexity and obstacles of motion planning are explained in terms of the principle of optimality. To plan the optimal paths in time-varying environment for those robots, a dynamic programming algorithm is developed and proposed in the paper. Suppose η is the maximum number of vertices of the time-varying graph, n is the number of robots, and k is the number of steps of the motion plan. The time complexity of this problem is O(η2nk).",

author = "Ho, {Hong Fa} and Liu, {Wen Cheng}",

year = "2007",

doi = "10.1109/ISIC.2007.4450864",

language = "English",

isbn = "142440441X",

series = "22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control",

publisher = "IEEE Computer Society",

pages = "77--82",

booktitle = "22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control",

note = "2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007 ; Conference date: 01-10-2007 Through 03-10-2007",

}

TY - GEN

T1 - Motion planning algorithm for homogeneous combinatorial robots in time-varying environment

AU - Ho, Hong Fa

AU - Liu, Wen Cheng

PY - 2007

Y1 - 2007

N2 - This paper introduces the concept of homogeneous combinatorial robots, specifying their properties and algorithms needed to solve the problems in motion-planning. In this paper, "homogeneous combinatorial robots" are a set of robots that can be combined and separated freely in motion. The complexity and obstacles of motion planning are explained in terms of the principle of optimality. To plan the optimal paths in time-varying environment for those robots, a dynamic programming algorithm is developed and proposed in the paper. Suppose η is the maximum number of vertices of the time-varying graph, n is the number of robots, and k is the number of steps of the motion plan. The time complexity of this problem is O(η2nk).

AB - This paper introduces the concept of homogeneous combinatorial robots, specifying their properties and algorithms needed to solve the problems in motion-planning. In this paper, "homogeneous combinatorial robots" are a set of robots that can be combined and separated freely in motion. The complexity and obstacles of motion planning are explained in terms of the principle of optimality. To plan the optimal paths in time-varying environment for those robots, a dynamic programming algorithm is developed and proposed in the paper. Suppose η is the maximum number of vertices of the time-varying graph, n is the number of robots, and k is the number of steps of the motion plan. The time complexity of this problem is O(η2nk).

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

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

U2 - 10.1109/ISIC.2007.4450864

DO - 10.1109/ISIC.2007.4450864

M3 - Conference contribution

AN - SCOPUS:41149165744

SN - 142440441X

SN - 9781424404414

T3 - 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control

SP - 77

EP - 82

BT - 22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control

PB - IEEE Computer Society

T2 - 2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007

Y2 - 1 October 2007 through 3 October 2007

ER -

Motion planning algorithm for homogeneous combinatorial robots in time-varying environment

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this