Directed graphs for the analysis of rigidity and persistence in autonomous agent systems
Directed graphs for the analysis of rigidity and persistence in autonomous agent systems
复制标题
DOI：
10.1002/rnc.1145
复制
发表时间：
2007-07-10
影响因子：
3.9
通讯作者：
Blondel, Vincent D.
中科院分区：
文献类型：
--
作者：
Hendrickx, Julien M.;Anderson, Brian D. O.;Blondel, Vincent D.
我们认为在本文中形成的自主代理移动在一个二维空间。每个代理都试图保持其与预先指定的一组其他代理的距离恒定，问题是确定是否可以保证每对代理（即使是那些没有明确保持的代理）之间的距离保持恒定，从而导致持续存在。形成形状。我们在这里提供了一个理论框架来研究这个问题。我们用有向图描述了对智能体之间距离的约束，并定义了持久图。一个图是持久的，如果几乎所有相应的代理形成的形状持续存在。虽然持久性与刚性的经典概念有关，但这是两个不同的概念。我们导出了持久图的各种性质，并给出了判定持久图的组合判据。我们还定义了最小的持久性（持久性与尽可能少的边缘），我们将我们的结果应用到有趣的特殊情况下的无圈图。版权所有（C）2006约翰威利父子有限公司
We consider in this paper formations of autonomous agents moving in a two-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant and the problem is to determine if one can guarantee that the distance between every pair of agents (even those not explicitly maintained) remains constant, resulting in the persistence of the formation shape. We provide here a theoretical framework for studying this problem. We describe the constraints on the distance between agents by a directed graph and define persistent graphs. A graph is persistent if the shapes of almost all corresponding agent formations persist. Although persistence is related to the classical notion of rigidity, these are two distinct notions. We derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define minimal persistence (persistence with the least possible number of edges), and we apply our results to the interesting special case of cycle-free graphs. Copyright (C) 2006 John Wiley & Sons, Ltd.