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 language | English |
---|---|
Pages (from-to) | 144-148 |
Number of pages | 5 |
Journal | Advanced Science Letters |
Volume | 15 |
Issue number | 1 |
DOIs | |
State | Published - Aug 2012 |
Keywords
- Exact cell decomposition
- Mobile robot
- Opposite angle
- Path planning