不确定性下的基于契约的多智能体逻辑控制器综合
《Nonlinear Analysis: Hybrid Systems》:Contract-based multi-agent logical controller synthesis under uncertainty
【字体:
大
中
小
】
时间:2026年08月06日
来源:Nonlinear Analysis: Hybrid Systems 4.1
编辑推荐:
摘要:我们提出了一种基于新颖的、完备的契约合成框架,用于在随机或对抗性环境中为多个相互作用的系统组件计算分布式逻辑控制器。该框架将组件间的交互抽象为有限图上的多玩家游戏,并将所有可控制系统组件的规范表示为该图上的ω-正则(如LTL)属性。我们分别为每个可控制组件本地共同合成契约和
摘要:我们提出了一种基于新颖的、完备的契约合成框架,用于在随机或对抗性环境中为多个相互作用的系统组件计算分布式逻辑控制器。该框架将组件间的交互抽象为有限图上的多玩家游戏,并将所有可控制系统组件的规范表示为该图上的ω-正则(如LTL)属性。我们分别为每个可控制组件本地共同合成契约和控制器候选方案,同时提出一种协商机制,通过迭代优化这些候选方案,直至找到解决给定分布式合成问题的方案。我们的框架依赖于最近引入的“许可模板”概念,该概念能够以简洁的数据结构存储大量控制器候选方案。我们利用这类模板的高效可计算性、适应性及组合性,构建了一个高效且完备的、基于契约的分布式逻辑控制协商框架。通过在机器人运动规划基准测试中对比我们的原型工具CoSMo与现有最先进工具,展示了我们方法的优异性能。
引言:在复杂环境中确保自主系统的正确性与可靠性,需要将形式化方法、控制技术与学习技术进行有机整合。本文聚焦于这样一个挑战:为多个需要在随机或对抗性环境中可靠运行的相互作用系统组件计算分布式逻辑控制器。由此产生的(离散且基于事件的)逻辑控制软件构成了控制软件栈的更高层次,它负责监督底层(连续的)控制策略,而这些控制策略既可以通过学习获得,也可以从一阶物理原理中推导出来。有限图上的游戏为建模系统组件的逻辑、基于事件的交互能力提供了一种成熟的方法。因此,这类模型是针对描述预期逻辑交互的规范,对“设计即正确”的逻辑控制软件合成问题进行形式化表达的有效手段。从算法层面来看,基于图上游戏的控制设计采用了反应式合成技术,这是一种源自计算机科学领域形式化方法社区的、已被充分理解且高度自动化的设计流程。反应式合成的优势在于能够为自动合成的控制软件提供强有力的正确性保障。将反应式合成用于控制领域与它在传统形式化软件设计中的应用相比,不同之处在于控制应用通常已经具备系统组件间(以及与外部环境之间)交互能力的模型,该模型可表示为给定的游戏图G。在本文中,我们利用这一给定模型的信息,让每个组件能够在G上解读自身的逻辑规范Φp,并在此认知基础上独立计算自身的控制策略πp。此外,在运行时,每个组件仅能观察到其他“玩家”的当前控制选择,而无法知晓其未来的控制策略,因此也无法利用这些信息来调整自身策略,这使得最终的分布式控制软件具有极高的鲁棒性。所提出的控制框架的核心要素在于将策略模板[1]作为本地控制器加以运用。策略模板类似于通过反应式合成通常计算得到的传统策略,但它能以简洁明了的数据结构存储大量相关策略。这种“许可性”——其概念灵感来源于传统的监督控制方法[2]——使得框架能够高效地适应新的规范要求,我们借此在合成过程中让各组件之间协商出中间控制设计方案,从而以“假设-保证”式的方式共同合成契约与控制器。尽管传统的(无模型)分布式反应式合成被认为是不可判定的,但这种方法仍使我们能够在许多情况下实现完备且正确的合成框架。虽然本文的会议版本已发表在[3]中,但本论文在此基础上进行了扩展:首先,不再仅考虑两个相互作用的控制系统,而是考虑k个;其次,还将额外的外部(不可控)环境过程建模为完全对抗性的或存在随机不确定性的类型。这样一来,分别形成了k+112和k+12玩家的游戏图模型G,且每个(受控的)玩家p∈Psys(其中Psys=k)在G上都有一个独立的奇偶性目标Φp,这与[3]中研究的2玩家多目标奇偶性游戏有所不同。尤其是对随机环境的扩展,使得我们的框架能够应用于基于强化学习在带奖励的马尔可夫决策过程(MDP)上训练得到的策略的监督工作。这是因为可以將底层的MDP直接转换为本文所假设的给定游戏图模型G。我们在7.3节通过一个新的机器人示例展示了所计算的分布式监督控制器的功能。此外,本文还提供了所有正式证明,这些证明专门针对[3]中讨论的2玩家情形。作为一个示例,考虑图1所示的完全自动化的笔生产工厂。该工厂在A1处有一台用于获取笔的原材料的机器。如有需要,它还可以生产带有橡皮的笔,但这要求该机器从C1处获取橡皮。为此,工厂配备了一台机器人,负责将原材料从B3输送到A1处的生产机器。因此,这台机器人需要无限次地往返于A1和B3之间,即需满足LTL目标2,其中(Ri:P)表示Ri位于单元格P中。为了将橡皮送到生产机器处,工厂还有一台机器人,它负责从B3获取原材料,并通过C1处的传送带将材料送入生产机器,前提是第一台机器人已将原材料送至A1,也就是说,其目标是满足相应条件。由于这两台机器人共享同一工作空间,它们的控制器需要在不考虑对方动作的情况下确保规范得到满足。如果使用传统的反应式合成引擎为这些机器人合成逻辑控制器,那么只会计算出一个单一的控制策略,例如一直沿着路径A1→A2→B2→B3→B2→A2→A1循环的策略。但实际上,第一台机器人并不一定非得遵循单一路径才能满足目标φ1。它只需最终能够从A1到达A2或B1,从A2和B1到达A3或B2,从A3和B2到达B3,以此类推即可。这些非常局部的活性属性恰恰体现了每一个正确控制策略的本质,可以被概括为一个策略模板,而且无需任何计算开销,就可以从传统合成引擎中提取出来[1]。这种控制器表示方式具有诸多优势。首先,策略模板具有可组合性。如果突然要求第一台机器人还需要从A3收集并存放货物,我们可以分别为该目标独立合成一个策略模板,然后通过简单地将所有现有的活性属性结合起来,就将这两个模板组合在一起。这样,第二台机器人就可以选择一种同时满足两个目标的策略,只要它遵守所有模板中的属性即可。其次,策略模板能够保留所有可能的策略选择,从而实现具有高度鲁棒性的控制方案,能够有效应对运行时的各种不确定性。例如,如果由于其他机器人的存在,A1暂时被阻塞,第一台机器人仍可以继续前往B3和A3,直到A1再次可用。第三,Nayak等人[4]最近研究表明,策略模板的灵活性使得可以通过对非线性动态系统的连续反馈控制,以可证明的正确方式实现逻辑策略选择,而无需对时间和空间进行离散化处理。虽然上述示例展示了策略模板对于单个组件的灵活性,但本文则利用它们易于组合和适应的特点,用于基于契约的分布式合成。为此,我们注意到,如果没有关于另一台机器人行为的任何假设,第一台机器人就没有任何策略能够满足自身的规范,例如,如果第二台机器人始终停留在B3处,第一台机器人就永远无法从B3获取原材料。然而,由于这两台机器人都是工厂设计师设计的,因此可以将它们设计成“适度”协作,从而实现两个目标。因此,我们假设第一台机器人可以“要求”第二台机器人最终离开B3,这样它就能获取原材料。从算法层面来看,这是通过分别为两台机器人本地计算策略模板[1]和假设模板[5]来实现的。后者包含了第二台机器人必须满足的局部要求,只有满足这些要求,第一台机器人才能实现自身的目标。当我们转变视角,为第二台机器人针对其自身的目标φ2本地合成策略时,就可以迫使它遵守第一台机器人先前计算得出的假设模板。不过,这又可能为下一轮对第一台机器人提出新的假设。由于模板具有易于组合的特性,每轮的计算都非常高效,最终得到的算法时间复杂度与游戏图的大小呈多项式关系。在这个示例中,最终得到的两组兼容的策略模板要求:当第二台机器人位于B3时,第一台机器人必须前往A1;只有在第一台机器人允许的情况下,它才能前往B3(而第一台机器人会根据其最终的模板允许这样做);同时,当第二台机器人到达时,第一台机器人也最终会允许它前往B3。此外,该算法还会输出一组兼容的策略模板(每台机器人各一个),从而为每台机器人提供最大的实现自由度——它们选择的任何控制方案都能让另一台机器人也实现自身的目标。通过允许存在随机对抗性环境,我们还可以利用这些模板来监督通过MDP训练得到的策略,这类MDP会在工作空间中因建模不完善而存在不确定性的所有状态转换上分配奖励。在这种情况下,经过协商得到的策略模板可以与所学策略相结合,从而在形式化保证的前提下,实现训练时所设定的目标,比如能耗控制或与人类行为的匹配度控制。我们将在7.3节进一步阐述这一应用场景。概述:由于多智能体控制系统对于实现可信的自主性具有重要意义(例如自动驾驶汽车或无人机送药系统),因此有大量研究致力于多智能体或多组件系统的控制器合成。这一领域的现有研究涵盖了多智能体控制的多个方面,如分布式状态估计与预测、编队控制、共识形成、碰撞避免、假设-保证契约以及网络控制。鉴于该领域的研究成果极为丰富,本综述仅聚焦于多智能体逻辑控制,也就是控制一组智能体来实现用线性时序逻辑(LTL)描述的、可能存在冲突或需要协作的逻辑规范。我们的工作源于[6]、[7]这两篇开创性论文(针对单智能体系统),这些论文的灵感来自于这样一个观察:LTL是一种强大的规范语言,可用于描述那些超越稳定性与共识性(通常通过反馈控制实现)的任务目标,例如自动驾驶的交通规则[8]、[9],或移动机器人的导航功能[7]、[10](相关综述可见[10]、[11])。多智能体逻辑控制的主要挑战在于智能体之间的策略相互依赖性,以及它们与对抗性或随机性环境的相互依赖性,尤其是在无限的时间范围内。这种相互依赖性往往会导致僵化的解决方案,即为每个智能体固定一种策略。虽然这些固定的策略方案是正确的,但它们缺乏灵活性。如果某个智能体需要偏离既定策略(如1.1节中的示例所示),那么所有长期的正确性保证都将失效。而我们的新方法则计算出一个契约,该契约既考虑了长期的战略相互依赖性,又允许在存在对抗性和/或随机性环境的情况下具备局部灵活性。多智能体逻辑控制:在多智能体逻辑控制的相关研究中,有很大一部分致力于解决这样一个问题:自主智能体的复杂连续反馈动态行为——通常由(低级)差分方程或微分方程来建模——与(高级)逻辑目标的实现之间存在矛盾,这些逻辑目标包括避开障碍物或到达目标位置等。为有效解决这一问题,人们通常会针对某些子问题展开研究,这些子问题旨在简化(高级)逻辑控制问题,并仅通过(低级)控制方式在局部处理灵活性与相互依赖性问题。有一类研究关注的是那种高层目标为安全型或短时间范围规范的子问题。除了传统的安全控制方法——即防止智能体的行为导致不良后果外,这类研究还包括基于控制屏障的多智能体控制[12]、[13],针对多组件系统的LTLf或safeLTL规范合成方法[14]、[15]、[16],假设-保证安全控制方法[17]、[18]、[19]、[20],以及针对所学策略的安全屏蔽技术(相关内容可见[21]、[22]、[23]、[24])。而对于那些超越安全范畴、涉及长期目标规范的场景(例如用STL、MTL或LTL形式化表达的规范),通常不会对环境中的确定性因素进行建模。由此产生的逻辑控制器综合问题属于非反应型问题,这意味着存在一个可预先计算的可行方案,从而避免了战略相互依赖的问题。对于这类非反应型逻辑控制问题,所有的逻辑规范通常会被转化为优化问题中的逻辑约束,然后利用控制领域的优化技术来解决(相关介绍可见[25])。在多智能体系统中,解决此类非反应型逻辑控制器的方法多种多样,包括混合整数线性规划形式[26][27]、基于数值向量的分配方法[28]、基于市场的契约机制[29]、控制屏障函数方法[30][31][32][33][34]、基于自动机的方法[35][36][37][38]以及基于佩特里网的方法[39][40](全面概述可见[41])。能够处理包括低级动态特性和战略相互依赖性在内的所有LTL规范的分类方法极为罕见。有一些关于单个组件与全局环境交互的示例见[42][43][44],而有限的多智能体系统相关研究则可见[45][46]。另一种方法是基于抽象的控制器综合,即把状态、输入和时间离散化为有限模型(相关概述见[47][48])。尽管这种方法常常会受到维度灾难的影响,但也存在针对多个组件的组合式和分布式方法,例如[49][50][51][52][53][54]。不过与我们的工作不同,所有这些方法都采用固定的策略配置来处理战略相互依赖性问题,缺乏任何局部策略灵活性。
本文的贡献在于:与之前讨论的相关工作不同,本文并未直接处理多智能体控制系统的低级连续动态特性,而是聚焦于更高层次的逻辑控制层面,同时实现了战略相互依赖性与局部策略灵活性的平衡。由此,我们得到的解决方案具备许多优异特性,远远超越了此前研究中使用的各类现成博弈求解方法。具体而言,本文提出了一种新算法,通过迭代方式为每个智能体计算策略模板,将其作为逻辑上的假设-保证契约,以此解决k+{0.5,1,1.5}玩家的多目标奇偶性博弈问题。从直观上讲,策略模板将不同策略之间的长期相互依赖需求转化为一种数据结构,这种结构在综合阶段和运行时都易于调整,从而为逻辑多智能体控制的解决方案增添了逻辑鲁棒性和适应性的新维度。因此,我们的工作主要与其他多目标奇偶性博弈的求解算法相关,具体内容将在下一节中阐述。
虽然本文侧重于这种新的博弈求解技术,但我们指出,所生成的策略模板确实可以与控制屏障技术和李雅普诺夫技术结合使用,用于处理低级连续动态系统,这一方法在关于单个系统与其环境交互的研究中已有探讨[4]。至于构建这样的混合多层多智能体控制器综合框架的正式工作,我们将留待未来研究。
在多玩家博弈求解领域,假设-保证契约已被证明非常有用,被应用于多种类型的博弈问题中[55][56][57][58][59][60][61][62]。在这些研究中,我们专注于针对所有ω-规则规范类的反应型逻辑控制设计,这使得我们的工作与其它基于A/G的分布式反应型综合方法[55][56][59][60][63]最为相似。然而,与这些工作不同的是,我们假设已给定一个联合博弈图,这使我们能够运用此前在形式化方法领域未被探索过的独特综合技术。因此,我们为k+0.5情况开发出了一个既完备又具有分布式的综合框架,而对于k+{1,1.5}情况,则该框架是完备的但非完全的。现有的工具要么集中式地进行综合,如[55][58][59],要么不够完备,如[57][60][62],又或者无法处理所有类型的LTL规范[18][62][63]。此外,我们还同时设计契约和控制器,也就是说,不像[17][61]那样假设契约是已给定的。
在关于分布式反应型综合的相关文献中,人们考虑了不同的合作模式。在[64]中,尽管场景是非零和的,但作者仍将参与者视为对手关系。他们的方法依赖于安全均衡[65],这是纳什均衡[66]的一种改进形式,即参与者首先试图满足自身的规范,然后再试图破坏其他参与者的规范。因此,该作者提出的算法用于计算安全均衡策略配置。类似地,在[67]中,作者寻找的是一种均衡策略配置,即参与者没有动机偏离自己的策略。在[68][69][70]中,作者并未为参与者固定此类策略配置,而是假设参与者具有特定的理性行为,这种行为被形式化为支配策略或可接受策略。这就隐含了对其他参与者行为的假设,这些假设可用于实现局部可行性,即只要在其他参与者行为符合假设的前提下,某个参与者就能满足自身的局部规范。与之相比,我们的工作则计算出明确的假设——这些都是具体且可操作的请求,可供其他参与者共享——因此,参与者可以自由选择任何满足既定假设的策略,无需遵循某种特定的理性策略选择。
与我们的方法类似,[59][60][71][72]也计算了组件之间的明确契约,之后每个组件都可以选择遵守该契约的任意策略。虽然[59]使用单一的集中式有界综合问题来寻找多个交互组件之间的契约,但[60][71][72][73]中的方法则是在局部综合问题之间通过协商算法来实现,因此在概念上与我们更为相似。不过,[71]中所解决的问题来自监督控制领域,因此采用了不同的组件交互表述方式。在[72]中,假设参与者是理性的,并将安全均衡的概念推广到了契约层面。而我们的工作则不对参与者的理性程度做任何假设,所计算的契约则是尽可能具有合作性的。与我们的工作最接近的是[60],它借鉴了[77]的研究成果来构建假设,但这些假设并非最具合作性。关于我们的方法与[59][60]相比在CPS综合问题应用上的独特优势,我们将在第7节再次进行讨论,同时还会提供有限的实证比较。
容许型策略模板最初由Anand等人[1][5]为两玩家零和博弈引入,后来被扩展到2+0.5玩家零和博弈[78]。它们还被用作合成非线性动态系统混合控制器的指导工具[4],以及合成零和无限博弈的控制器[79]。与这些工作不同,我们使用容许型策略模板来合成k+1.5玩家非零和博弈中具有最大合作性的契约,其中关于两玩家博弈的初步版本可见[3]。
本文的结构如图2所示,第3.3节和第4.4节将对其进一步详细阐述。第2节介绍了所需的预备知识后,第3节对所研究的基于契约的综合问题进行了形式化定义,第4节则通过容许型模板对该问题进行了具体实例化。接着在第5–6节中,我们利用这一实例化结果设计出了用于求解该问题的协商算法。最后,第7节通过将基于C++的原型工具CoSMo与现有最先进求解器在一系列基准测试任务上的表现进行对比,为我们的协商框架具备理想的计算性能提供了实证支持。
**预备知识**
符号说明:我们用N表示包含零在内的自然数集合。对于两个满足a2时的k+1.5玩家博弈的假设-保证分布式综合工具——我们重点研究了这些较为简单的博弈问题。特别是,我们探讨了CoSMo在处理这些问题时的性能表现。
**CRediT作者贡献声明**
Ashwani Anand:写作——审稿与编辑,写作——初稿撰写,软件开发,形式化分析,概念构思。
Satya Prakash Nayak:写作——审稿与编辑,写作——初稿撰写,可视化,软件开发,形式化分析,概念构思。
Anne-Kathrin Schmuck:写作——审稿与编辑,写作——初稿撰写,项目监督,项目管理,资金申请,概念构思。
**利益冲突声明**
作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。
**致谢**
本研究得到了德国科学基金会项目SCHM 3541/1-1和389792660以及TRR 248–CPEC的支持。
Ashwani Anand | Satya Prakash Nayak | Anne-Kathrin Schmuck
德国凯泽斯劳滕,马克斯·普朗克软件系统研究所(MPI-SWS)
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号