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

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

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.