【博士论文】《多Agent系统中的突现行为开发和控制》美国空军技术学院195页

2022 年 9 月 27 日 专知

好奇心驱使人类在地球海洋的最深处航行，捕捉宇宙中最早的光芒。在这些广袤的地方，存在着各种结构和复杂的生态系统。每一个生态系统中都居住着无数的适应性有机体和粒子，每一个都创造了自己的微观世界，充满了奇妙和神秘的行为。这些复杂的自适应性系统（CAS）围绕着我们，影响着一切，从一个人的草坪如何生长到全球天气模式。这些自然系统产生了高度的研究兴趣，因为它们的固有特性：层次结构、稳健性、适应性和任务的分散执行；构建在相对简单的组件基础上[13, 55, 57, 93, 96, 103, 108, 103]。

在当今世界，由自主实体组成的多Agent系统部署迅速增加[25, 49, 68]。这些系统必须对Agent的损失具有鲁棒性，对环境变化具有适应性，并具备同时完成多项任务的能力。Agent互动的高度复杂性、可能的系统状态以及Agent通信和传感器数据的数量使集中控制方法不堪重负[17, 91, 129]。此外，像它们的自然对应物一样，这些系统包含难以预测和控制的非线性行为[25, 49]。这些行为，被称为突发行为[14, 55]，造成了一个具有挑战性的设计问题。

工程师们面临的问题是如何设计一个复杂的、多Agent的系统，它本身是分散的，但又是适应性强的。其中一个方法是开发一个自组织系统，该系统具有与系统目标相匹配的突发属性，即所需的宏观行为。然而，目前该领域还没有一个商定的框架，或模型来设计这种系统[69, 57, 30]。大量研究者认为，新兴系统具有有益的特征，如自组织行为、稳健性、适应性和分散控制[13, 55, 57, 93, 96, 103, 108]；这些都是工程系统的理想特征。虽然存在许多建模方法[57, 103, 49]，但相对较少[33]研究Agent生理学或形态学对突发行为的影响。本论文基于一个主要的概念制定了多Agent、突发事件系统：Speciation（物种形成），并研究其在弱突发现象的演化中的作用，以实现一个宏观的目标。

物种形成是指一个种群中Agent的多样性。差异可以是形态上的，也可以是生理上的。形态上的差异是物理上的差异，如在一些蚁群中区分兵蚁和工蚁种群的较大身体尺寸和下颚[139]。这些生理上的差异意味着通过长期的进化过程形成物种。对于工程系统，人类衍生的差异，如各种传感器套件和发动机，用人类主导的进化过程取代自然进化过程。不同类型车辆的发展和能力的完善仍然是进化上的迭代，只是人为的。

生理上的差异指的是Agent如何运作，并根据Agent如何消化来自环境的信息而变化[4]。例如，社会性蜘蛛Anelosimus studiosus看起来都是一样的，都有同样的一套技能，如网的维护、狩猎、育雏等。然而，Holbrook等人[53]发现，这个特定物种的驯服和被动成员，致力于与属性相一致的特定任务，攻击性的蜘蛛倾向于狩猎，而被动的则承担网络维护和育雏任务。这些差异在于蜘蛛内部，可能是基于遗传物质或学习经验。最终的结果是生理上的物种形成。这里感兴趣的一个主要生理物种形成的特征是Agent根据当前环境或学习经验改变其功能的能力。这使得生理上的物种形成特别强大，因为它创造了具有可塑性的Agent。

从生物学上讲，可塑性是指Agent在形态上或生理上适应其环境的变化[5]。进一步深入研究社会性蜘蛛Anelosimus studiosus的习性，Holbrook等人[53]发现，如果他们建立一个全部是攻击性的，或全部是被动的蜘蛛群落，那么这些群落会自我组织成执行所有需要任务的群体，如网的维护、狩猎等，而不管蜘蛛的内部偏向。换句话说，蜘蛛通过完成不太理想的任务表现出生理上的可塑性，保证了群体的生存。

1.1 假设

这项工作的假设是，将物种形成与突发系统的有益特征结合起来，就会产生一种可推广的、分散控制的方法，用于复杂的多Agent系统。在Agent层面上，物种进化形成使Agent分成不同功能组，定义为利基。每个利基都向一个子目标看齐，形成一个由不同利基物种组成的层次。当利基群体致力于完成次级目标时，他们的行动就会聚集成一个符合系统目标的宏观层面行为。通过使用物种形成，人们可以设计一个多层次的分层系统，其固有的突发行为支持系统的整体目标。

1.2 背景

突现研究与许多学科交叉，如物理学、生物学和生态学[56, 93, 97]。它为那些研究秩序如何在复杂的适应性系统中自发产生的研究提供了一个理论框架[70]。这些系统中的秩序与复杂的、集体的行为有关，这些行为是由实体之间和它们的环境之间的非线性相互作用产生的[128]。对于Reynolds's boids[110]来说，有组织的鸟群是从一群在天空中移动的鸟的混乱中出现的。对于康威[116]来说，非凡的生命模式是从飞机上的简单规则中生长出来的。在这两个例子中，秩序产生于连续和离散领域的Agent互动，由简单的互动规则创造和限制。局部Agent互动（即微观层面的行动）和全局结果（即宏观层面的行为）之间的相互作用，是突现论背后的基本概念。

突现的主要问题之一是围绕着它的哲学辩论，其基础是一个简单得令人难以置信的问题："什么是突现？" 换句话说，当人们在一个自然或工程系统中观察到一个令人惊讶的行为时，它是一种突现的行为还是简单的结果[9]？根据人们的询问，答案是 "是 "或 "不是"，这种争论可以追溯到19世纪，当时G.H. Lewes指出，某些自然现象无法用定量术语来表达[24]。这些现象似乎超出了构成它们的各个部分和组件的简单总和[55]。Lewes认为这些是突现的行为，并主张它们可能是无法解释的。

科学界的大多数人对无法解释的现象的想法并不满意。接受这些行为是无法解释的，使得对突现的研究相当无意义，正如Hempel和Oppenheim[52]所说，"它鼓励一种对科学研究感到窒息的认命态度"。这一论点迫使突现研究者找到一个折中的办法，或者完全放弃这一追求。

尽管社会各界对突现行为缺乏充分的共识，但一般来说，突现行为是指复杂系统所表现出来的一种新的或令人惊讶的行为模式[112]；它不能仅仅被解释为其各部分的总和[103]。然而，令人惊讶和新颖这两个词使定义变得复杂。例如，成群结队是一个普遍接受的突现行为[112, 24, 9]；然而，雷诺兹[110]发明了三个简单的移动物体规则，称为boids，可以产生鸟类成群结队的现实模拟。如果人们用雷诺兹的方法对一些空中无人机进行规划，那么人们就会期望发生成群结队的现象，如果没有发生，实际上是令人惊讶的。这是否意味着成群结队不再是突现性的？在作者看来，不是。成群结队仍然是一种突现的属性，因为它仍然是一种宏观层面的行为，是由简单的Agent的相互作用产生的。这就引出了Chalmers的定义。"突现是一种现象，其中复杂、有趣的高层功能是以简单的方式结合简单的低层机制而产生的"[19]。这个定义避免了使用惊讶和新颖这样的术语，同时允许因果关系和预测的争论。

因果关系和预测对于那些寻求在工程系统中建立突现行为的人来说都很重要。没有因果关系，人们就无法创造出一个具有所需突现特性的系统，而且，尽管预测在动态环境中仍然非常困难，因为不可能知道与系统及其环境相关的所有未知变量，但对系统的行为方式有一定的了解，例如机器人会成群结队，根据信息素建立路径等，是一个很好的特性。这就引出了Bedau对突现问题的解决方案。Bedau[9]定义了两种主要的突现行为：弱的和强的。弱突现是一种行为或模式，可以归结为微观层面上的Agent的行动和行为。另一方面，强突现是不可还原的，意味着因果途径，向上或向下，都是无法确定的。由于这项工作关注的是现实世界的系统，它同时接受Chalmer和Bedau的定义，因为它们有利于突现研究的应用。

这篇论文的重点是提供可应用于工程系统的模型和算法，使人们能够设计出具有理想的突现行为的系统，如分工、系统稳健性等，而不需要一个集中的控制器，也不需要由主题专家制定的大量启发式指导。换句话说，设计具有高度适应性和稳健性的在线系统，只需最小的外部指导，基于在突发系统中发现的特性，对形态和生理上的agent物种形成的影响具有特定的兴趣。

1.3 研究问题

主要的研究假设是，物种形成创造了功能壁龛，建立了一个分层的自组织系统。这些系统，从目标驱动的角度设计，显示出有益的突发行为，如稳健性和适应性。这里提出的研究问题涉及该假说的不同部分。

1.Agent的物种形成是否会导致层次分明的自组织系统？

2.这些系统在动态环境中显示出稳健性吗？

3.这些系统能否在没有集中控制机构的情况下同时完成多项任务？

这些问题都直接与突现研究中提出的理论相联系。这里的重要区别是，本论文测试了Agent物种形成如何能创造出拥有这些特性的系统。

研究问题一涉及到突现研究中的一个基本观点：微观层面的互动形成了宏观层面的行为，从而在系统中强加了一个关系的层次结构。第三章至第六章分别介绍了在从事各种领域的Agent群中实例化物种形成的不同方法。每个所选领域的结果都表明，标本化的Agent根据其形态或生理学进行功能调整，从而形成第一层的自组织行为。这些行为然后聚集成宏观层面的行为，与系统目标保持一致。

研究问题二测试了这些系统在严重的环境变化下的鲁棒性如何。稳健性意味着系统能够在灾难性的环境变化后恢复到原来的状态，或者稳定到一个新的状态而不完全崩溃。尽管每一章都展示了对微小变化具有鲁棒性的系统，但第六章和第八章探讨了在极端环境变化（如资源饥饿）下标本种群的鲁棒性，以及系统之后如何达到一个新的稳定状态。第四章提出了一个宏观层面的指标，以图形方式描述了系统状态，允许分析系统的稳健性和可能出现的现象。第八章明确地评估了假设本身。

最后，研究问题三评估了Agent物种形成是否会导致分工等行为的出现，这些行为有助于提高广泛的任务能力。尽管分工是第六章的主要重点，但第三、四和五章都研究了只有通过自组织的多任务能力才能满足宏观层面目标的系统。

1.4 贡献

该研究将物种形成作为工程系统中突发行为的一个关键组成部分。研究结果表明，物种形成导致了Agent壁龛的横向转移，即功能相似的Agent群体。这些微观层面的转变改变了宏观层面的行为，而宏观层面的行为反过来又影响了微观层面的决策，形成了一个永久的反馈循环。研究结果还显示，物种形成如何导致系统的稳健性和适应性。由于宏观层面的行为依赖于微观层面的相互作用，这项工作强调了在形态和生理限制方面分散执行Agent决策的力量。

总的来说，实验表明，物种形成是建立稳健和适应性强的多Agent系统的关键。Agent在其生理学的指导下，自我组织成功能一致的壁龛，从而创造出宏观层面的新兴模式。新出现的模式，如劳动分工，依靠并影响这些壁龛的出现、增长和消失，通过一个反馈循环，在系统的等级层次中循环。横向运动的增加，即人口在功能壁龛之间的转移，为突现研究增加了一个被忽视的细微差别。与传统的、在突发的、分层的系统模型中发现的垂直反馈循环不同，这项工作显示了每个层次的Agent，甚至是突发行为之间的相互作用如何创造、加强和破坏宏观层次的突发行为。

1.5 局限性

Holland写道，模拟模型 "描述的是可能性而不是实际情况[56]"，这项工作也代表了这个事实。这项工作中的各种模拟提供了在工程系统中可能发生的情况，并通过以下各章阐述了这些特性。然而，这些只是可能性。现实世界环境中未知变量的数量使得它几乎不可能解释所有可能发生的行为，不管是突发的还是其他的。此外，这些方法只适用于工程系统。自然系统中的物种形成是如何发生的，现在和这项研究开始时一样，都是一个谜。尽管作者可以说，物种形成的概念可以帮助对自然行为进行建模，但它并没有为其发生提供推理。此外，这项工作将自己限制在具有集合描述和规律的领域和系统中[55]，使生产的人工系统充斥着遵守已知规则和功能的简单Agent，避免了强突现的哲学雷区。

1.6 概要

每一章都探讨了突现研究的基本前提：简单的Agent互动创造了复杂的、宏观的模式。从主题上讲，每一章都包含了一种简单的Agent，具有明确的相互作用、期望的最终状态行为模式和分散的控制方法。尽管每一章都有这些特征，但除了第二章和第九章外，每一章都是独立的作品，有其特定的问题领域和方法。

第二章由背景材料组成，探讨了突现研究的历史，确立了突现的定义和相关术语，以及与后面各章中使用的方法有关的背景。熟悉突现、香农的信息熵和遗传算法的读者可以随时跳过这一章，因为每一个后续章节都有自己的相关背景和方法论部分。

第三章介绍了非正式团队分配算法（ITAA）。ITAA展示了被定义为特定Agent角色的Agent通信和物种形成是如何导致致力于共同目标的团队动态形成：巢穴防御。这一章与第二个研究问题相一致，即物种形成及其对系统稳健性的影响。此外，由于Agent必须同时完成多项任务，即搜索和捕获，本章支持研究问题三。本章介绍的具有内部阈值机制的预定义角色代表了Agent群体中的生理差异，以及它们如何创造所需的突发行为。在本章介绍的巡逻-追捕领域中，追捕小组自发地进行侧翼机动，这并没有正式编入系统，以捕获拥有卓越速度和机动能力的入侵Agent。此外，通过使用预定义的角色，Agent能够同时执行多种任务，如巡逻和追击，而不需要集中控制，从而产生一个可适应的系统和可扩展的控制解决方案。

在第四章中，香农的信息熵有两个目的。首先，二维、多无人机领域的Agent使用熵来指导目标选择决策，确保Agent在已知目标上的均匀分布。在这里，Agent的物种形成是以一种适应性的方式实现的，因为Agent不断地更新他们的世界观，并延伸到他们的功能，基于当前的本地信息。第二，香农熵被用来创建系统状态的宏观尺度。用于测量二维、多无人机领域的系统状态，以及康威的生命游戏[116]，结果显示，该指标准确地描述了处于稳定状态的系统，以及显示了正在经历关键变化的系统。这些临界变化可能是潜在的突发现象的指标，为识别新的系统行为的形成提供了一种可能的方法。检测到的变化也表明了系统中局部利基的建立，即等级层次的出现。本章探讨了研究问题一和三，具体展示了规格化的种群，使用熵来指导Agent决策，如何创建具有多任务能力的层次化自组织系统。

第五章在k-coverage领域进一步扩展了熵的使用。在k覆盖问题中，一个系统必须在所有已知目标中分配k个Agent[104]。该领域的困难在于，目标的数量和它们的位置都是先验的，而且Agent的通信范围有限。尽管第四章中基于熵的方法提供了一个起点，但所期望的最终状态并不是在所有n个目标上均匀分配Agent。这项工作选择实施在蜜蜂群中发现的信号抑制技术来解决这个问题。在蜜蜂群中，当涉及到招募他人进行资源收集时，蜜蜂可以抑制其他蜜蜂的信号[107]。Agent在接近目标或目标达到所需的饱和率时模仿这种行为，即当前有k个Agent与目标接触。信号抑制技术确保在每个时间步骤中只有k个Agent参与目标。结果表明，抑制信号的范围直接影响到多无人机群保持所需的k覆盖率的能力。本章再次强调了简单Agent的分布式决策是如何解决复杂问题的。此外，本章建立了Agent的形态种类，称为观察者和跟踪者，以实现k-分配。本章比较了真正的异质团队，即那些具有形态差异的团队，以及仅由一个物种组成的团队的性能，这些物种随着环境的变化而改变其生理反应阈值。通过这样做，本章与研究问题二和三相一致，因为所研究的系统必须适应动态变化，并同时完成两个任务：探测和覆盖。

第六章研究了导致分工出现的多Agent系统特性。它实证研究了Agent决策函数、种群规模和环境约束对在亚当-斯密的Pin工厂工作的同质人群的分工演变的影响[120]。结果显示，Agent决策函数的选择和人口规模都与分工的出现有很强的相关性。然而，它也表明，高程度的分工，即高度专业化的Agent，不一定会产生更高的资源生产，表明在设计突发系统时，必须对最终的系统结果进行批判性思考。此外，由于环境制约因素影响了Agent的表现，正确的Agent决策功能的选择也起了作用。本章强调了适应性生理学的力量，以及它们如何进化出复杂的、适应性强的种群，导致所研究的系统中出现分工。这一章支持了所有三个研究问题，因为规格化的种群必须在动态环境中完成九个不同的任务。Agent对特定任务的功能调整创造了利基，形成了所需的、宏观层面的行为，在这种情况下，就是制造资源。在关于鲁棒性的实验中，种群在运行期间经历了严重的环境变化。结果表明，特定的种群对环境变化具有鲁棒性，并且能够同时完成多项任务。

第七章为突发系统的建模提供了一个顶点部分。这个建模框架被称为生态系统离散事件模拟(eDEVS)，它结合了Uhrmacher等人建立的多层次DEVS(ml-DEVS)[131]、Barros的动态结构DEVS(DSDEVS)[6]和Holland的Echo模型[54]的部分内容，产生了一个对信息共享有严格限制的层次建模框架。eDEVS认为每个层次是一个耦合模型，定义为一个壁龛，进行并限制可能通过它们的信号和信息类型。通过在逻辑上将各层次分离成各自的利基，该框架能够实现动态的对象切换，从而使系统适应。使用eDEVS，人们可以模拟基于龛内和龛间信号的复杂行为。此外，eDEVS提供了对中期和长期系统目标的时间分析和测试，扩大了eDEVS的适用范围。在一个简单的蚁群领域的测试中，本章展示了eDEVS是如何对可适应的突发系统进行建模的，并允许对未预料到的突发行为进行因果分析，如狩猎队的形成。eDEVS是一个能够对分层系统以及微观-宏观和宏观-微观层面的互动进行建模的框架，产生了大多数突发系统的正式建模方法中所缺少的行为因果联系。

第八章正式阐述了Agent物种形成在突发系统中的影响，并评估了这一假设本身。这一章结合了在突现研究中发现的主题、定义和方法，并展示了Agent物种形成的纳入如何创造出具有多任务能力的稳健、分层的自组织系统。此外，还描述了一种基于物种形成的概念性算法，并在多个领域实施。这项工作的假设得到了三个不同领域的实验结果的支持：追逐-逃避游戏、K-覆盖问题和亚当-斯密的针厂。结果显示，特定的种群创造了层次分明的自组织系统，满足了多种任务，并且比非特定的种群对环境变化更加稳健。该算法在多个领域的使用显示了Agent物种形成和生理适应的普遍性，并增加了物种形成作为突发系统的一个基础部分。

最后，第九章结束了这项工作，包括未来研究机会和领域的途径，以及对这项工作的总结。