Award Date

5-2009

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi Gewali, Chair

Second Committee Member

Jan B. Pedersen

Third Committee Member

John Minor

Graduate Faculty Representative

Henry Selvaraj

Number of Pages

55

Abstract

We consider the problem of constructing multiple disjoint paths connecting a source point s to a target point t in a geometric graph. We require that the paths do not have any sharp turn angles. We present a review of turn constrained path planning algorithms and also algorithms for constructing disjoint paths. We then combine these techniques and present an O(nlogn) time algorithm for constructing a pair of edge disjoint turn constrained paths connecting two nodes in a planar geometric graph. We also consider the development of a turn constrained shortest path map in the presence of polygonal obstacles. Prototype implementations of the proposed algorithms are also presented. These problems have application for trajectory planning for unmanned aerial vehicles (UAV).

Keywords

Computer science; Drone aircraft; Guidance systems (Flight)

Disciplines

Computer Sciences | Navigation, Guidance, Control and Dynamics | Other Computer Sciences | Theory and Algorithms

Language

English

Comments

Signatures have been redacted for privacy and security measures.


Share

COinS