Time complexity of motion planning algorithm for homogeneous combinatorial robots

Ng Fa Ho*, Hong Shuo Tai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publication2006 SICE-ICASE International Joint Conference
Pages4280-4284
Number of pages5
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event2006 SICE-ICASE International Joint Conference - Busan, Korea, Republic of
Duration: 2006 Oct 182006 Oct 21

Publication series

Name2006 SICE-ICASE International Joint Conference

Conference

Conference2006 SICE-ICASE International Joint Conference
Country/TerritoryKorea, Republic of
CityBusan
Period2006/10/182006/10/21

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Time complexity of motion planning algorithm for homogeneous combinatorial robots'. Together they form a unique fingerprint.

Cite this