AF:Small:Geometric Optimization Problems for Routing, Searching, and Coverage in the Face of Uncertainty

A massive amount of spatio-temporal data is continuously collected by the devices that make up the modern, interconnected world. The ability to take advantage of this data for strategic and societal good depends, to a large extent, on how one can best utilize information about a constantly changing world in which much of the data is necessarily uncertain. Large data sets have the potential to capture the stochastic variation in data at a level of statistical detail previously unimaginable. Along with this increasing access to data comes the challenge of making decisions robustly and strategically in the face of uncertainty, while being equipped with data that enables a highly detailed model of stochastic variation. Availability of massive quantities of data presents opportunities for exploiting the data to make economical decisions while mitigating risk. When optimizing in the face of uncertainty it is important to account for not only the "expected" outcomes but also the unexpected or low-probability events. This project seeks to design algorithms that address some of the challenging optimal-decision problems in the face of uncertain spatiotemporal data, such as customer demand sites, congestion in transportation systems, incidences of crime, and other geospatial events. Motivating applications include delivery services, coordination of autonomous vehicles, smart cities, security patrols, material handling, and search and rescue. This project will advance the algorithmic study of optimization problems in geometric settings with uncertainty. Uncertainty can arise in various ways, including locational uncertainty (on the coordinates of sites or agents), existential uncertainty (on whether a site exists or is relevant), and domain uncertainty (on the geometry/topology of the domain of interest). Most of the problems are some form of optimization problem, in which the goal is to minimize a cost or maximize a benefit, or some combination of multiple criteria. Many of the problems are known to be computationally difficult (e.g., NP-hard), even in deterministic settings on perfectly known data, and become more challenging in the face of uncertainty. Working within precise stochastic models of uncertain geometric data, the goal is to provide solutions with provable guarantees, often in the form of approximation algorithms for optimization problems. Specific problems to be studied include variations on vehicle routing problems (e.g., stochastic traveling salesperson problems (TSP) in stochastic settings), constructing robust geometric networks on sites with locational uncertainty, and the optimal deployment of multiple mobile robot agents to search a geometric domain for one or more targets whose locations are unknown, but potentially described by a statistical distribution. A new class of problems addresses the privacy aspect geometric routing, and seeks to model and solve the problem of seeking solutions that are "least predictable" in a precise sense, minimizing the possibility that one's intent can be inferred from partial data: these least predictable path/tour optimization problems are based on the use of intentional randomization to advance privacy and security. Recognizing that geometric structure has played a critical role in the design of efficient approximation algorithms on deterministic data, an underlying goal of the project is to identify the degree to which geometry can be exploited to yield better results than are possible in general settings. This work will rely on methods from the fields of computational geometry, combinatorial optimization, networks, and approximation algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.