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

Hong Fa Ho, Wen Cheng Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publication22nd IEEE International Symposium on Intelligent Control, ISIC 2007. Part of IEEE Multi-conference on Systems and Control
PublisherIEEE Computer Society
Pages77-82
Number of pages6
ISBN (Print)142440441X, 9781424404414
DOIs
Publication statusPublished - 2007 Jan 1
Event2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007 - Singapore, Singapore
Duration: 2007 Oct 12007 Oct 3

Publication series

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

Other

Other2007 IEEE 22nd International Symposium on Intelligent Control, ISIC 2007
CountrySingapore
CitySingapore
Period07/10/107/10/3

Fingerprint

Varying Environment
Motion Planning
Motion planning
Time-varying
Robot
Robots
Motion
Optimal Path
Dynamic programming
Time Complexity
Dynamic Programming
Optimality
Graph in graph theory

ASJC Scopus subject areas

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

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). [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 proceedingConference 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, 07/10/1. 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). https://doi.org/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{6ff258536d1c4bc8aae254607c6ee8c7,
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",
month = "1",
day = "1",
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",

}

TY - GEN

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

AU - Ho, Hong Fa

AU - Liu, Wen Cheng

PY - 2007/1/1

Y1 - 2007/1/1

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

ER -