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

构成现代互联世界的设备不断收集着大量的时空数据。利用这些数据实现战略和社会利益的能力在很大程度上取决于人们如何最好地利用关于不断变化的世界的信息，在这个世界中，许多数据必然是不确定的。大型数据集有可能以以前无法想象的统计细节水平捕捉数据中的随机变化。随之而来的是越来越多的数据获取，这就带来了一个挑战，即在面对不确定性的情况下，稳健地、战略性地做出决策，同时配备能够实现高度详细的随机变化模型的数据。海量数据的可用性为利用这些数据在降低风险的同时做出经济决策提供了机会。在面对不确定性进行优化时，重要的是不仅要考虑“预期”的结果，还要考虑意想不到或低概率的事件。该项目旨在设计算法，以解决在面对不确定时空数据时的一些具有挑战性的最优决策问题，例如客户需求地点、交通系统拥堵、犯罪事件和其他地理空间事件。激励应用包括送货服务、自动驾驶车辆的协调、智能城市、安全巡逻、物资搬运和搜救。该项目将推进具有不确定性的几何环境中优化问题的算法研究。不确定性可以以各种方式产生，包括位置不确定性(关于场地或代理人的坐标)、存在不确定性(关于场地是否存在或相关)以及领域不确定性(关于感兴趣领域的几何/拓扑)。大多数问题都是某种形式的优化问题，其中的目标是最小化成本或最大化收益，或者是多个标准的某种组合。众所周知，许多问题在计算上是困难的(例如，NP-Hard)，甚至在完全已知的数据的确定性设置中也是如此，并且在面对不确定性时变得更具挑战性。在不确定几何数据的精确随机模型中工作，目标是提供具有可证明保证的解决方案，通常是以优化问题的近似算法的形式。需要研究的具体问题包括车辆路径问题(例如，随机环境下的随机旅行商问题(TSP))的变化，在具有位置不确定性的地点上构建稳健的几何网络，以及多个移动机器人代理的最优部署以搜索几何区域中位置未知但可能由统计分布描述的一个或多个目标。一类新的问题涉及隐私方面的几何布线，并试图建立模型并解决在精确意义上寻找解决方案的问题，以最大限度地减少从部分数据中推断一个人的意图的可能性：这些最不可预测的路径/旅行优化问题基于使用故意随机化来提高隐私和安全性。认识到几何结构在设计有效的确定性数据近似算法中发挥了关键作用，该项目的一个基本目标是确定可以在多大程度上利用几何结构来产生比一般情况下可能的更好的结果。这项工作将依赖于计算几何、组合优化、网络和近似算法领域的方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.