Year

1991

Degree Name

Doctor of Philosophy

Department

Department of Computer Science

Abstract

The work reported in this thesis is motivated by the need to construct a navigation system for mobile robots which can operate in unknown and partially known environments, and which has the capability to progressively learn an environment A new environment mapping procedure is described that constructs high resolution maps of an environment using ultrasonic range sensing. The ultrasonic range maps are converted into quadtrees. Quadtrees are used by the navigation system as the data structure that models the environment.

This thesis presents a new algorithm for a mobile robot to explore an unknown environment using the quadtree data structure and the distance transform path planning methodology. Past approaches to robot path planning have concentrated on finding the shortest path to a goal. A path planner should also support finding a variety of other kinds of paths to a goal. For example a path planner could support finding "conservative", "adventurous" and "safe" paths. Conservative paths favour known areas, while adventurous paths avoid known areas. Safe paths keep a safe distance from obstacles, while simultaneously keeping the path length to the goal as short as possible. It is shown that the new mobile robot exploration algorithm can generate a wide variety of path planning behaviours by a novel use of distance transforms.

Much of the research effort into path planning for mobile robots has concentrated on the problem of finding paths by translation of the robot body only. The problem of finding paths which require the rotation of the robot body have been largely ignored. This thesis presents an new algorithm for path planning with three degrees of freedom which is based upon an extension to the "safe" path planning behaviour.

Finally it is shown that the new algorithms that have been presented are computationally efficient, and have desirable features that are absent from other path planning algorithms.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.