Time and motion in graphs

图表中的时间和运动

• 批准号: RGPIN-2021-03064
• 负责人: Dyer, Danny
• 金额: $ 1.31万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742358
• 关键词: Time; motion; graphs

A graph is an abstract idea used to model relationships between important objects, people or ideas. Thus, maps, computer networks, and even family trees can be represented as graphs. This research is interested in moving through graphs - like getting directions on how to drive between two different cities. Particularly, this research deals with searching and domination problems, which have applications to search and rescue, video game artificial intelligence, and even to cleaning nuclear plant water supply pipes. This research deals with using software agents to guard against attacks by malicious "intruders", and subsequently how to capture these intruders if they do attack. Discrete pursuit-evasion (also called graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment, while graph domination can be thought of as how to distribute guards to minimize damage if an attack occurs. In one popular formulation, the environment is a computer network and it is modeled as a graph. Classically, the problem has been to determine the minimum number of agents needed to capture the intruder. This research program deals with minimizing the response time after an attack, and then how to minimize the cost of the response when the intruder's position is uncertain. These problems are difficult to solve, even with computers, and consequently we need theoretical research, like that involved in this program of research, to "cut corners" and make this more practical. Because of the applications of this research to network security problems, the proposed research is likely to have impact in the design and construction of computer networks to minimize damage caused by malicious agents, and will contribute to the advancement of mathematical research in graph searching and graph domination problems. It will also provide training opportunities for graduate and undergraduate students.

图表是一种抽象概念，用于对重要对象、人或想法之间的关系进行建模。因此，地图、计算机网络，甚至家谱都可以用图表来表示。这项研究的兴趣在于浏览图表——比如获取如何在两个不同城市之间开车的方向。特别是，这项研究涉及搜索和控制问题，可应用于搜索和救援、视频游戏人工智能，甚至清洁核电站供水管道。这项研究涉及使用软件代理来防范恶意“入侵者”的攻击，以及随后如何捕获这些入侵者的攻击。离散追击逃避（也称为图搜索）是数学和计算机科学中的一系列问题，其中一个群体试图在环境中追踪另一个群体的成员，而图支配可以被认为是如何在发生攻击时分配警卫以最大程度地减少损失。在一种流行的表述中，环境是计算机网络，并且被建模为图形。传统上，问题是确定捕获入侵者所需的最少代理数量。该研究计划涉及最小化攻击后的响应时间，以及当入侵者的位置不确定时如何最小化响应成本。这些问题即使用计算机也很难解决，因此我们需要像本研究项目那样的理论研究来“走捷径”，使其更加实用。由于这项研究在网络安全问题上的应用，所提出的研究可能会对计算机网络的设计和构建产生影响，以最大限度地减少恶意代理造成的损害，并将有助于图搜索和图支配问题的数学研究的进步。它还将为研究生和本科生提供培训机会。