ATD: Stochastic Obstacle Scene Problem with Adversarial Agents

在有障碍物的网络上导航是模拟两个地点（例如，两个城市或两个库存存储地点）之间最优旅行的自然方式。这门学科是高度跨学科的，借鉴了运筹学、统计学、概率论、优化、计算机科学和图论，在国防后勤、机器人群的分散控制、多障碍环境中的自主路径规划、目标跟踪和中和以及海军后勤等领域都有应用。尽管网络（遍历）优化已经取得了一些成功，但要使其在实践中得到广泛应用，还需要解决一些基础和应用研究方面的挑战。网络优化的进展影响着制造和物流分析、供应链管理、通信网络和交通管理等领域以及我们日常生活的许多方面。因此，开发更快更好的网络遍历/阻塞优化算法将对科学和社会产生直接影响。这项研究还将增加学术界和工业界之间的合作和伙伴关系。该项目的成果将通过研究文章、会议记录和系列研讨会传播。相关代码将作为开源软件包公开提供。该项目将通过教授专题课程和为研究生和博士后组织研讨会来整合研究和教育，并努力支持在这一主题上工作的少数民族、女性和年轻研究人员。本项目的目标是利用空间网络优化找到随机障碍场景（SOS）问题的最优或接近最优解决方案。研究者将研究SOS问题的两种变体。首先是原始的SOS问题，也称为最优遍历路径（OTP）问题，其中单个导航代理（NAVA）在包含“禁止区域”的空间中选择成本最小的路径。在第二个SOS问题（研究人员最近介绍的最优障碍物放置（OOP））中，障碍物放置代理（OPA）在遍历窗口中插入障碍物，以使NAVA的遍历长度最大化。本研究的主要目标是改进两种变体的启发式算法，引入新的变体，并研究理论基础。SOS问题设置非常普遍，适用于在遍历成本不同且可能无法遍历区域的介质中的对抗性代理。本项目的研究目标是：(a)将SOS问题向多个方向扩展，例如高维版本，并开发改进OTP和OOP算法的潜在策略；(b)从概率/统计和计算的角度引入和开发两个SOS变体的权约束版本，研究解决策略，并开发更全面的网络遍历优化/阻塞方法。(c)研究网络遍历和阻塞算法的理论性质（包括复杂度），以及OTP问题的代价函数特征。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Navigation on a network with obstacles is a natural way to model optimal travel between two locations (e.g., two cities or two inventory storage locations). This subject is highly interdisciplinary, drawing on operations research, statistics, probability, optimization, computer science, and graph theory, and has applications across defense logistics, decentralized control of robot swarms, autonomous path planning in obstacle rich environments, target tracking and neutralization, and naval logistics. Despite network (traversal) optimization having seen some success, there are several basic and applied research challenges that need to be addressed to enable its widespread use in practice. Progress in network optimization affects areas such as manufacturing and logistics analysis, supply chain management, communication networks and traffic management and many aspects of our daily life. Thus, the development of faster and better optimization algorithms in network traversal/blocking will have a direct impact on science and society. This research will also result in increased collaboration and partnership between academia and industry. Results of this project will be disseminated through research articles, conference proceedings, and seminar series. Relevant code will be made publicly available as open-source software packages. The project will integrate research and education by teaching special topics courses and organizing seminars for graduate students and postdocs, with efforts made to support underrepresented minority, female, and young researchers working on this topic.The goal of this project is finding optimal or near-optimal solutions to the stochastic obstacle scene (SOS) problem using spatial network optimization. The investigator will study two variants of the SOS problem. First is the original SOS problem, also called the Optimal Traversal Path (OTP) problem), in which a single navigating agent (NAVA) chooses a cost-minimal path in a space containing “forbidden regions.” In the second SOS problem (optimal obstacle placement (OOP), recently introduced by the investigator), an obstacle placing agent (OPA) inserts obstacles in the traversal window so as to maximize NAVA’s traversal length. The main goals of this research are to improve heuristic algorithms for both variants, to introduce new variants, and to study theoretical underpinnings. The SOS problem setting is quite general and applies to adversarial agents in a medium where traversal cost is heterogeneous with possibly untraversable regions. The research objectives of this project are to (a) extend the SOS problem in various directions, e.g., high dimensional version and develop potential strategies to improve OTP and OOP algorithms, (b) introduce and develop the weight constraint versions of both SOS variants, study the solution strategies and develop a more comprehensive approach to network traversal optimization/obstruction all from the probabilistic / statistical and computational points of view, and (c) study the theoretical properties (including complexity) of the network traversal and obstruction algorithms together with the characterization of the cost functions for the OTP problem.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.