Time and motion in 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.