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

AF:Small：面对不确定性时路由、搜索和覆盖的几何优化问题

基本信息

批准号：
2007275
负责人：
Joseph S. Mitchell
金额：
$ 45万
依托单位：
SUNY at Stony Brook
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007275&HistoricalAwards=false
关键词：
AF Small Geometric Optimization Problems

项目摘要

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.

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

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Geometric Spanning Trees Minimizing the Wiener Index

DOI：
10.48550/arxiv.2303.01096
发表时间：
2023-03
期刊：
ArXiv
影响因子：
0
作者：
A. K. Abu-Affash;Paz Carmi;Ori Luwisch;Joseph S. B. Mitchell
通讯作者：
A. K. Abu-Affash;Paz Carmi;Ori Luwisch;Joseph S. B. Mitchell

Planar Bichromatic Bottleneck Spanning Trees

平面双色瓶颈生成树

DOI：
10.4230/lipics.esa.2020.1
发表时间：
2020
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Abu-Affash, A. Karim;Bhore, Sujoy;Carmi, Paz;Mitchell, Joseph S.
通讯作者：
Mitchell, Joseph S.

Area-Optimal Simple Polygonalizations: The CG Challenge 2019

面积最优简单多边形：2019 年 CG 挑战赛

DOI：
10.1145/3504000
发表时间：
2022
期刊：
ACM Journal of Experimental Algorithmics
影响因子：
0
作者：
Demaine, Erik D.;Fekete, Sndor P.;Keldenich, Phillip;Krupke, Dominik;Mitchell, Joseph S.
通讯作者：
Mitchell, Joseph S.

Approximating Maximum Independent Set for Rectangles in the Plane

平面内矩形的近似最大独立集