Type
Text
Type
Dissertation
Advisor
Hu, Jiaqiao | Mitchell, Joseph S.B., Arkin, Esther M. | Gao, Jie.
Date
2012-08-01
Keywords
Air Traffic Management, Algorithms, Complexity, Computational Geometry, Optimization, Path Planning | Computer science--Transportation planning--Theoretical mathematics
Department
Department of Computer Science
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71468
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Computing optimal routes subject to geometric constraints is a fundamental area of research in computational geometry. This thesis is devoted to the study of some specific geometric routing and optimization problems. The first main area of the thesis addresses a class of multicommodity flow problems in geometric domains: For a given planar domain P populated with obstacles of different types, we consider routing thick paths corresponding to motion of vehicles of different classes, from a source edge on the boundary of P to a sink edge on the boundary of P. Each class of vehicle has an associated path width required and a given set of types of obstacles it must avoid, while it can freely pass through other types of obstacles. The problem arises in air traffic management with different classes of aircraft that must avoid various types of weather disturbances. We show that the decision problem is NP-hard even when there are only two classes of vehicles and two types of obstacles. We present approximation algorithms for the multicriteria optimization problems that arise when trying to maximize the number of routable paths. We also give heuristics and provide an experimental analysis of their effectiveness. The second problem we address is that of computing a path or cycle that is constrained to be convex and to intersect a given set of connected, compact sets. In particular, we resolve an open problem posed more than two decades ago by Arik Tamir: Given a collection of compact sets, can one efficiently determine if there is a convex body whose boundary intersects every set in the collection? We prove that it is NP-hard, in general, to decide the existence of a convex traversal path, even if the input is a set of line segments in the plane. Further, we generalize our proof to show that deciding the existence of a convex surface stabbing a set of balls in three dimensions is NP-hard. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments in 2D, assuming the vertices of the transversal are restricted to a given set of points. In the third part of the thesis, we investigate the problem of computing paths and trees within an uncertain geometric domain, in which the set of obstacles is not known deterministically, but is specified by a stochastic model. The problems arise in routing aircraft through uncertain weather systems, especially in the case of merging flows of aircraft arriving to a terminal airspace in the presence of uncertain events that impact the availability of airspace. We formalize the problem of computing a highly probably path in geometric settings and prove NP-hardness of the general problem. Further, we develop efficient algorithms for computing paths and trees in the presence of uncertain geometric obstacles. We apply our methods to the problem of computing routes and trees for flows of aircraft that are designed to be robust to off-nominal events that may impact the super-dense operations airspace through which they are routed. | 137 pages
Recommended Citation
Yang, Shang, "Some Path Planning Algorithms in Computational Geometry and Air Traffic Management" (2012). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 674.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/674