Path Planning Algorithms under the Link-Distance Metric
Dartmouth Technical Report TR2006-585
David P. Wagner
Date: February 2006
URL (PDF): (2291KB)
Abstract:
The Traveling Salesman Problem and the Shortest Path Problem
are famous problems in computer science which have been well
studied when the objective is measured using the Euclidean distance.
Here we examine these geometric problems under a different set of
optimization criteria. Rather than considering the total distance
traversed by a path, this thesis looks at reducing the number of
times a turn is made along that path, or equivalently, at reducing
the number of straight lines in the path.
Minimizing this objective value, known as the link-distance, is useful
in situations where continuing in a given direction is cheap, while turning
is a relatively expensive operation. Applications exist in VLSI, robotics,
wireless communications, space travel, and other fields where it is
desirable to reduce the number of turns.
This thesis examines rectilinear and non-rectilinear variants of the
Traveling Salesman Problem under this metric. The objective of these
problems is to find a path visiting a set of points which has the smallest
number of bends. A 2-approximation algorithm is given for the rectilinear
problem, while for the non-rectilinear problem, an O(log n)-approximation
algorithm is given. The latter problem is also shown to be NP-Complete.
Next, the Rectilinear Minimum Link-Distance Problem, also known as
the Minimum Bends Path Problem, is considered. Here the objective
is to find a rectilinear path between two points among rectilinear obstacles
which has the minimum number of bends, while avoiding passing through
any of the obstacles. The problem has been well studied in two dimensions,
but is relatively unexplored in higher dimensions. A main result of this
thesis is an O(n^{5/2} log n) time algorithm solving this problem in three
dimensions. Previously known algorithms have had worst-case running
times of Omega(n^3).
This algorithm requires a data structure that supports efficient operations
on pointsets within rectangular regions of the Euclidean plane. We
design a new data structure, which is a variation on the segment tree,
in order to support these operations.
Finally, an implementation of the data structure and of the algorithm
solving the Minimum Link-Distance Problem demonstrates their
experimental running times and ease of implementation.
Note:
Doctoral dissertation.
Co-Advisors: Robert Scot Drysdale, Clifford Stein;
Thesis Committee: Amit Chakrabarti, Joseph S. B. Mitchell