AF: Small: New Directions in Geometric Shortest Paths

AF：小：几何最短路径的新方向

• 批准号: 1814172
• 负责人: Subhash Suri
• 金额: $ 29.99万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814172&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Geometric

Shortest paths and reachability are fundamental problems with a long and distinguished history in computer science and mathematics. Due to growing integration of cyber and physical worlds through the Internet-of-Things (IoT), an increasing amount of data processing entails geometric models, and an ever growing set of smart mobile devices can interact with, and affect, the environment in which they operate - from self-driving cars to autonomous robots. Addressing the needs of these applications, this project explores new directions for shortest paths in geometric domains, organized around the following two broad themes: (1) improving shortest paths by removal of some path-blocking obstacles, and (2) searching for a randomized prize. The specific research topics of the project are novel, yet the general theme touches on many classical problems in geometry, combinatorial optimization, probability theory, decision science and search. The project significantly broadens the scope, applicability and relevance of geometric algorithms to search and planning in continuous spaces, by incorporating strategic intervention and planning under uncertainty. The fundamental nature of topics addressed in this project is likely to appeal to a broad set of students with diverse backgrounds, both graduate and undergraduate. The material generated from this project will be integrated into multiple courses on algorithms and computational geometry, including the investigator's newly launched Foundations of Data Science course.The project is centered around two research topics. The first topic deals with the following question of reachability: can one reach a target position from an initial position. When this is possible, the goal is to compute a feasible path, or perhaps the shortest one. The focus of the project is the "if not" side of this question, which is often left unattended. Specifically, if no feasible path exists, or the shortest path is unacceptably long, how many and which obstacles should be removed? This form of reachability augmentation in geometric domains is both fundamental and intellectually exciting, with many surprising twists and turns. The solution quality and the algorithmic efficiency critically depend on the geometry of the workspace and model assumptions: are obstacles convex or non-convex? Are obstacles disjoint or overlapping? Is the removal cost the same for all obstacles or different? The second topic proposes a novel framework for problems in which one tries a sequence of alternatives in search for a prize (favorable outcome), where each outcome is determined by a random trial. Computing combinatorial structures, such as shortest paths, in the presence of such random events poses significant intellectual challenges, and the project research contributes to an important body of knowledge.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.

最短路径和可达性是计算机科学和数学中具有悠久历史的基本问题。由于网络世界和物理世界通过物联网（IoT）日益融合，越来越多的数据处理需要几何模型，越来越多的智能移动的设备可以与其运行的环境进行交互并影响其运行的环境-从自动驾驶汽车到自主机器人。为了满足这些应用的需求，本项目围绕以下两个主题探索了几何域中最短路径的新方向：（1）通过消除一些路径阻塞障碍来改善最短路径，以及（2）寻找随机奖励。该项目的具体研究主题是新颖的，但总的主题涉及几何，组合优化，概率论，决策科学和搜索中的许多经典问题。该项目通过在不确定性下纳入战略干预和规划，大大拓宽了几何算法在连续空间中搜索和规划的范围、适用性和相关性。在这个项目中所解决的主题的基本性质可能会吸引一系列具有不同背景的学生，包括研究生和本科生。 该项目产生的材料将被整合到算法和计算几何的多门课程中，包括研究者新推出的数据科学基础课程。该项目围绕两个研究主题展开。第一个主题涉及以下可达性问题：一个人能否从初始位置到达目标位置。当这是可能的，目标是计算一个可行的路径，或者可能是最短的一个。该项目的重点是这个问题的“如果不是”方面，这往往是无人看管。 具体来说，如果不存在可行路径，或者最短路径长得不可接受，那么应该消除多少障碍物？几何领域中的这种形式的可达性增强既基本又令人兴奋，其中有许多令人惊讶的曲折。解决方案的质量和算法的效率关键取决于工作空间的几何形状和模型假设：是凸或非凸的障碍？ 障碍是不相交的还是重叠的？ 所有障碍物的清除成本是相同的还是不同的？ 第二个主题提出了一个新的问题框架，其中一个尝试一系列的替代品，以寻找一个奖（有利的结果），其中每个结果是由随机试验确定。计算组合结构，如最短路径，在这种随机事件的存在下，提出了重大的智力挑战，该项目的研究贡献了一个重要的知识体系。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

Efficient Algorithms for Least Square Piecewise Polynomial Regression

最小二乘分段多项式回归的高效算法

• 发表时间: 2021
• 期刊: ESA21: Proceedings of European Symposium on Algorithms
• 作者: Lokshtanov, Daniel;Suri, Subhash;Xue, Jie
• 通讯作者: Xue, Jie

Computing Shortest Paths in the Plane with Removable Obstacles

计算具有可移除障碍物的平面中的最短路径

• 发表时间: 2018
• 期刊: 16th Scandinavian Symposium and Workshops on Algorithm Theory (
• 作者: Agarwal, P;Kumar, N;Sintos, S;Suri, S.
• 通讯作者: Suri, S.

Improved approximation bounds for the minimum constraint removal problem

改进了最小约束去除问题的近似界限

• DOI: 10.1016/j.comgeo.2020.101650
• 发表时间: 2020
• 期刊: Computational geometry
• 作者: Bandyapadhyay, S;Kumar, N;Suri, S;Varadarajan, K.
• 通讯作者: Varadarajan, K.

Shortest Paths in the Plane with Obstacle Violations

越障平面上的最短路径

• 发表时间: 2020
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Hershberger, J.;Kumar, N.;Suri, S.
• 通讯作者: Suri, S.

The maximum exposure problem

最大曝光问题

• DOI: 10.1016/j.comgeo.2022.101861
• 发表时间: 2022
• 期刊: Computational Geometry
• 作者: Kumar, Neeraj;Sintos, Stavros;Suri, Subhash
• 通讯作者: Suri, Subhash