AF: Small: New Directions in Geometric Shortest Paths
AF:小:几何最短路径的新方向
基本信息
- 批准号:1814172
- 负责人:
- 金额:$ 29.99万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-10-01 至 2022-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。
项目成果
期刊论文数量(11)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Efficient Algorithms for Least Square Piecewise Polynomial Regression
最小二乘分段多项式回归的高效算法
- DOI:
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Lokshtanov, Daniel;Suri, Subhash;Xue, Jie
- 通讯作者:Xue, Jie
Computing Shortest Paths in the Plane with Removable Obstacles
计算具有可移除障碍物的平面中的最短路径
- DOI:
- 发表时间:2018
- 期刊:
- 影响因子:0
- 作者: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
- 期刊:
- 影响因子:0
- 作者:Bandyapadhyay, S;Kumar, N;Suri, S;Varadarajan, K.
- 通讯作者:Varadarajan, K.
Shortest Paths in the Plane with Obstacle Violations
越障平面上的最短路径
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:1.1
- 作者:Hershberger, J.;Kumar, N.;Suri, S.
- 通讯作者:Suri, S.
The maximum exposure problem
最大曝光问题
- DOI:10.1016/j.comgeo.2022.101861
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Kumar, Neeraj;Sintos, Stavros;Suri, Subhash
- 通讯作者:Suri, Subhash
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Subhash Suri其他文献
A linear time algorithm for minimum link paths inside a simple polygon
- DOI:
10.1016/0734-189x(86)90070-8 - 发表时间:
1986-04-01 - 期刊:
- 影响因子:
- 作者:
Subhash Suri - 通讯作者:
Subhash Suri
Pursuit Evasion on Polyhedral Surfaces
- DOI:
10.1007/s00453-015-9988-7 - 发表时间:
2015-04-29 - 期刊:
- 影响因子:0.700
- 作者:
Kyle Klein;Subhash Suri - 通讯作者:
Subhash Suri
Range Counting over Multidimensional Data Streams
- DOI:
10.1007/s00454-006-1269-4 - 发表时间:
2006-09-12 - 期刊:
- 影响因子:0.600
- 作者:
Subhash Suri;Csaba D. Toth;Yunhong Zhou - 通讯作者:
Yunhong Zhou
Computing euclidean maximum spanning trees
- DOI:
10.1007/bf01840396 - 发表时间:
1990-06-01 - 期刊:
- 影响因子:0.700
- 作者:
Clyde Monma;Michael Paterson;Subhash Suri;Frances Yao - 通讯作者:
Frances Yao
Algorithmic issues in modeling motion
运动建模中的算法问题
- DOI:
10.1145/592642.592647 - 发表时间:
2002 - 期刊:
- 影响因子:0
- 作者:
Pankaj K. Agarwal;Leonidas J. Guibas;H. Edelsbrunner;Jeff Erickson;M. Isard;Sariel Har;J. Hershberger;Christian Jensen;L. Kavraki;Patrice Koehl;Ming Lin;Dinesh Manocha;Dimitris Metaxas;Brian Mirtich;David Mount;S. Muthukrishnan;Dinesh Pai;E. Sacks;J. Snoeyink;Subhash Suri;Ouri E. Wolfson;Merl Mirtich@merl Com - 通讯作者:
Merl Mirtich@merl Com
Subhash Suri的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Subhash Suri', 18)}}的其他基金
AF: Small: Geometric Methods for Network Science
AF:小:网络科学的几何方法
- 批准号:
1525817 - 财政年份:2015
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
AF: Medium: Collaborative Research: Uncertainty Aware Geometric Computing
AF:媒介:协作研究:不确定性感知几何计算
- 批准号:
1161495 - 财政年份:2012
- 资助金额:
$ 29.99万 - 项目类别:
Continuing Grant
RI: Medium: Collaborative Research: Minimalist Mapping and Monitoring
RI:媒介:协作研究:极简制图和监测
- 批准号:
0904501 - 财政年份:2009
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Geometric Approaches to Ad Hoc and Sensor Networks
Ad Hoc 和传感器网络的几何方法
- 批准号:
0612299 - 财政年份:2006
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
NeTS-NOSS: Collaborative Research: Lightweight Monitoring Tools for Sensor Networks
NeTS-NOSS:协作研究:传感器网络的轻量级监控工具
- 批准号:
0626954 - 财政年份:2006
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Geometric Computing over Distributed and Streaming Data
分布式和流数据的几何计算
- 批准号:
0514738 - 财政年份:2005
- 资助金额:
$ 29.99万 - 项目类别:
Continuing Grant
ITR/PE+SY: Collaborative Research: Foundations of Electronic Marketplaces: Game Theory, Algorithms and Systems
ITR/PE SY:合作研究:电子市场基础:博弈论、算法和系统
- 批准号:
0121562 - 财政年份:2001
- 资助金额:
$ 29.99万 - 项目类别:
Continuing Grant
Geometric Problems in Graphics, Databases and Networking
图形、数据库和网络中的几何问题
- 批准号:
0049093 - 财政年份:2000
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Geometric Problems in Graphics, Databases and Networking
图形、数据库和网络中的几何问题
- 批准号:
9901958 - 财政年份:1999
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Efficient Fair Queuing and Load Balancing
高效的公平队列和负载均衡
- 批准号:
9628190 - 财政年份:1996
- 资助金额:
$ 29.99万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
- 批准号:
2327010 - 财政年份:2023
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
- 批准号:
2327011 - 财政年份:2023
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
- 批准号:
2311397 - 财政年份:2023
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: New directions in geometric traversal theory
NSF-BSF:AF:小:几何遍历理论的新方向
- 批准号:
2317241 - 财政年份:2023
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
AF: Small: New Tools to Analyze Random Walks
AF:小:分析随机游走的新工具
- 批准号:
2203541 - 财政年份:2022
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
- 批准号:
2224718 - 财政年份:2022
- 资助金额:
$ 29.99万 - 项目类别:
Standard Grant