AF: Small: New Directions in Geometric Shortest Paths

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

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.