Masters Theses

Date of Award

8-1988

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Robin Cockett

Abstract

In recent years, considerable progress has been made towards the development of intelligent autonomous mobile robots which can perform a wide variety of tasks. Although the capabilities of these robots vary significantly, each must have the ability to navigate within its environment from a starting location to a goal without experiencing collisions with obstacles in the process - a capability commonly referred to as "robot navigation".

Numerous algorithms for robot navigation have been developed which allow the robot to operate in static environments. However, little work has been accomplished in the development of algorithms which allow the robot to navigate in a dynamic environment. This thesis presents a mathematically-based navigation algorithm for a robot operating in a continuous-time environment inhabited by moving obstacles whose trajectories and velocities can be detected.

In this methodology, the obstacles are represented as sheared cylinders to depict the areas swept out by the obstacle disks of influence over time. The robot is represented by the cone of positions it can reach by traveling at a constant speed in any direction. The methodology utilizes a three-dimensional navigation planning approach in which the search points, or tangent points, are the points in time at which the robot tangentially meets the obstacles. These tangent points are determined by calculating the intersection curves between the robot and the obstacles, and then using the first derivative of the intersection curves to make the tangent selections. Paths are created as sequences of these tangent points leading from the robot starting location to the goal, and are searched using the A* strategy, with a heuristic of the Euclidean distance from the tangent point to the goal.

The main contribution of this thesis is the development of a methodology which produces optimal tangent paths to the goal for a dynamic robot environment. This feature is significant, since no other algorithm located in the literature survey as background to this thesis has shown the ability to produce paths with optimal properties.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS