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.