Time and motion in graphs

图表中的时间和运动

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

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