A study on the automatic path planning problem for various workspaces.

摘要

Automatic path planning is essential for many real world applications. Efficient representations of a moving object and its surroundings are crucial to efficient path planning algorithms. In this thesis, new representation schemes of various objects are developed and analyzed.;First, the problem of moving a ladder amidst polygonal obstacles is addressed. It is shown that computational complexity of the ladder problem is ;Next, we address the point moving problem using a workspace decomposition method. By defining a recti-linear visibility (;One of the major difficulties in solving the automatic path planning problem is the accuracy of workspace information. To alleviate this difficulty, we present an algorithm where only partial information of the workspace is given. Such workspace information is transformed into a probability field. An empirical study of aromatic path planning is presented using this probability field.