Mobile robot path planning with opposite angle-based exact cell decomposition

Byung Chul So, Jin Woo Jung

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Exact cell decomposition like the vertical cell decomposition is one of the fundamental and well-known mobile robot path planning algorithms which enable exact and complete motion planning but does not guarantee the optimality. As a result, the number of decomposed cells is generally too big and searching a path among these cells may take much time. In this paper, a novel method, opposite angle-based exact cell decomposition, is proposed to overcome these drawbacks by extending the line segments of each polygon obstacle to decompose the adjacent free space into convex cells. The proposed algorithm does not use vertical lines, which is used in the vertical cell decomposition, and does not use the merging process of tiny cells, which is time-consuming and used in the approximate cell decomposition and in the arrangement method, but uses lines with various directions to decompose an environment efficiently and reduce the number of decomposed cells less than the vertical cell decomposition. The convexity and validity of the proposed algorithm is analyzed mathematically and with some experiments. The experimental results show that the proposed algorithm is better than the vertical cell decomposition in almost all cases.

Original languageEnglish
Pages (from-to)144-148
Number of pages5
JournalAdvanced Science Letters
Volume15
Issue number1
DOIs
StatePublished - Aug 2012

Keywords

  • Exact cell decomposition
  • Mobile robot
  • Opposite angle
  • Path planning

Fingerprint

Dive into the research topics of 'Mobile robot path planning with opposite angle-based exact cell decomposition'. Together they form a unique fingerprint.

Cite this