Previous | [1] | [2] | [3] | [4] | [5] | [6] | 7 | [8 |

On the Motion Planning Problem:

The Case of A Polygonal Object Moving Amidst

Obstacles of Arbitrary Shape

**Ping-Lih Lin, Yat-Chen Chen and Shyang Chang**

National Tsing Hua University

Hsinchu, Taiwan, R.O.C.

The motion planning problem for a polygonal object moving in a cluttered workspace populated with obstacles of arbitray shape is considered in this paper. The grayscale morphology is invoked to calculate some geometric information such as the local distance information, the Voronoi diagram, and the skeleron representation. The advantages of this geometric information are: (1) A part of the Voronoi diagram will be adopted as the main protion of the guidance path (or called the nominal path). (2) By using both local distance information and the skeleton representation of the moving object, the collision detection process can be carried out very efficiently. In addition, a so-called phase map is also proposed in order to get smooth motion. Whenever a collision is expected, a closed-loop feedback modification technique will be invoded, or a reverse motion heuristic will be adopted if there exists a supplementary path in the neighborhood of the collision position. Finally, Examples are given to demonstrate the power of this proposed algorithm.

Keywords: motion planning, grayscale morphology, Voronoi diagram, skeleton representation, terrian map, phase map

Received May 6, 1991; revised December 18, 1991.

Communicated by Wen-Hsiang Tsai.