权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane

访问平面内一系列区域的最小链路 C 向路径