基于斯塔克伯格博弈的含不可控智能体的信号时序逻辑运动规划方法

《Nonlinear Analysis: Hybrid Systems》：A Stackelberg game approach for signal temporal logic motion planning with uncontrollable agents

　　摘要：本文研究了在存在不可控智能体的情况下，基于信号时序逻辑的运动规划问题。现有研究主要在鲁棒控制框架下处理该问题，假设不可控智能体具有对抗性，并考虑最坏情况。虽然这种方法能确保安全性，但在不可控智能体拥有与系统目标并非完全对立的自身目标时，可能会过于保守。鉴于这一局限性，我们提出了一个基于斯塔克伯格博弈框架的STL运动规划新框架。具体而言，我们假设系统控制器作为领导者先制定计划，然后不可控智能体作为追随者根据既定计划及自身目标采取最优响应。我们的目标是为领导者设计出一种控制序列，使得对于任何做出最优响应的理性追随者，领导者的STL任务都能得到满足。我们通过将问题转化为单阶段优化问题，并运用反例引导的合成技术，给出了有效的解决方案。仿真结果证明了所提方法的有效性。

引言：决策制定和任务规划是自主系统设计中的核心挑战。近年来，由于形式化方法能够为系统正确性提供严格的规范和保障，因此在高层次任务规划领域受到了广泛关注[1][2][3]。在这些方法中，时序逻辑作为一种表达能力很强的工具，能够以数学上严谨且易于理解的方式描述复杂的时空约束。尤其是最初在[4]中提出的信号时序逻辑，因其非常适合描述动态不确定环境中的实值信号的空间-时间要求，而被广泛研究[5][6][7]。在STL规范的运动规划方面，最常用的方法是基于优化的方法[8][9]，该方法利用二元变量来表示STL公式的满足情况，从而将运动规划问题转化为混合整数规划问题。另一种方法则利用控制屏障函数，为STL公式满足区域对应的正向不变集提供充分条件[10][11]。这些方法主要解决开环控制问题，即在没有外部干扰的情况下设计出满足STL规范的单一控制序列。当存在外部干扰或不确定性时，基于在线信息的反馈控制就变得至关重要。在STL控制合成领域，一种直接的方法是将开环轨迹合成方法融入到滚动时域控制框架中，参见[12][13][14][15][16][17][18]，这种方法需要在实时情况下迭代求解优化问题，每一步仅应用最新的控制输入。为确保递归计算的可行性，还需要解决一个鲁棒优化问题，以保证在所有可能的干扰情况下STL任务都能得到满足[17][19][20][21]。上述关于存在外部输入时的STL控制合成的现有研究基本上都属于零和博弈范畴。在这种框架下，控制器旨在确保在所有可能的外部输入情况下STL公式都能得到满足，这可以理解为另一个目标与系统STL任务完全对立的参与者。虽然零和设定在纯粹对抗性环境中不可或缺，但当不可控智能体拥有自身合理的目标时，它往往会导致过度保守。例如，在一个仅有智能体1可控且其STL任务取决于联合轨迹的双智能体系统中，若采用零和设定，控制器就必须保守地规划，以应对智能体2的所有可能行为。然而，如果智能体2也有自己的（不一定相互冲突的）STL目标，那么考虑其理性行为更为合适。这就自然引出了非零和建模方式，即每个智能体都追求不同的目标。

我们的贡献：基于以上考虑，本文在斯塔克伯格博弈或领导者-追随者博弈框架下，通过共享协议或任务公告获取不可控智能体的任务信息，弥补了零和方法的不足。我们的贡献如下：首先，与零和博弈模型中将不可控性视为来自固定不确定性集的纯粹对抗性干扰不同，我们考虑并形式化了控制器（领导者）和不可控智能体（追随者）都受任务驱动、各自追求由STL公式指定的目标的场景下的STL运动规划问题。这些目标不一定相互对立，且假设领导者知晓追随者的任务。具体而言，领导者先确定一系列控制输入，随后追随者计算出能优化自身任务的最优响应控制序列。其次，根据在领导者策略下追随者的目标是否可满足，我们表明该问题可产生两类解决方案：合作型解决方案，即领导者预判追随者行为，在可能的情况下使两个STL目标都得到满足；对抗型解决方案，即领导者通过消除追随者完成其STL任务的可能性，迫使其不进行干预。对于每类解决方案，我们都提出了有效方法，为领导者设计出最优控制序列，使得对于任何做出最优响应的理性追随者，领导者的STL任务都能得到保证。最后，我们通过两个机器人路径规划案例研究，展示了所提框架的有效性。此外，虽然我们当前的方法适用于扩展性较差的MIP框架，但本文提出的斯塔克伯格框架也与平滑STL语义和基于梯度的优化方法相契合。

相关工作：我们的工作与动态博弈理论背景下的分层博弈[22][23]，以及涉及受时序逻辑任务约束的不可控智能体的控制合成[24][25][26]密切相关。一些现有研究已经探讨了这两个领域的整合。例如[27]在斯塔克伯格博弈框架下，针对随机系统的数值效用最小违反问题进行了研究。在[28]中，作者通过引入分层超博弈模型，研究了在对抗性环境中的战略规划中的欺骗手段运用，该模型使领导者能够制定欺骗策略来影响追随者的认知，从而提高实现自身目标的可能性。此外，[29]研究了在斯塔克伯格博弈框架下的离散事件系统的监督控制问题。然而，这些工作主要聚焦于简单的安全规范或线性时序逻辑规范。据我们所知，将斯塔克伯格博弈应用于STL控制合成领域尚未有相关研究。

论文结构：本文的其余部分结构如下。第2节介绍一些必要的预备知识。第3节介绍领导者-追随者博弈框架，并构建斯塔克伯格STL合成问题（SPP-STL）。第4节提出两阶段合成流程，用于寻找SPP-STL的合作型和解对抗型解决方案。第5节通过两个案例研究展示我们方法的应用。最后，第6节对本文进行总结，并讨论未来研究方向。

系统模型：我们考虑如下形式的离散时间控制系统：xt+1=f(xt,ut,wt)，其中t=0,1,…为时间指标，xt∈X?Rn为时间t时的系统状态，ut∈U?Rm表示时间t系统控制器的有界输入，wt∈W?Re表示外部输入。我们假设初始状态固定为x0∈X。给定一系列控制输入u0:N?1=u0u1…uN?1∈UN和一系列外部输入w0:N?1=w0w1…wN?1∈WN，时间范围为N，系统的状态序列为ξf(x0,u0:N?1,w0:N?1)=x0。

存在干扰的鲁棒STL规划：文献中已对鲁棒STL运动规划问题进行了大量研究。该问题旨在从控制器的角度设计输入序列，以确保在所有可能的外部输入序列下STL公式都能得到满足。正式地，该问题可由以下优化问题描述：?minimizeumaxwJ(x0,u,w)，约束条件为?w∈WN:ξf(x0,u,w)??，其中J:X×UN×WN→R为通用成本函数，如结果状态的鲁棒值。

解决方案合成：两阶段方法：在本节中，我们将为SPP-STL的合作型和对抗型情况分别给出解决方案。我们的方法主要是为合作型情况设计的，因为需要协调领导者和追随者的目标，所以更具挑战性。随后我们证明，合作型情况的解决方案方法可以很容易地调整用于处理对抗型情况，即领导者试图迫使追随者的任务无法得到满足。

案例研究：本节我们展示了两个案例研究的仿真结果。我们的方法是用Python 3实现的，优化问题则用Gurobi求解。所有仿真都在配备Apple M2 CPU和8 GB内存的笔记本电脑上进行。所有源代码可在https://github.com/stack-stl/Stackelberg-STL获取。

结论：本文提出了一个基于斯塔克伯格博弈理论的框架，用于存在不可控智能体时的信号时序逻辑运动规划。与鲁棒控制方法相比，我们的框架更能体现不可控智能体的理性行为，为系统控制器提供了更灵活的解决方案。这项工作是朝着在斯塔克伯格博弈框架下进行STL运动规划迈出的第一步。不过，目前的结果还存在一些局限性，我们正致力于改进。

作者贡献声明：Bohan Cui：撰写——审阅与编辑，方法论。Xinyi Yu：撰写——初稿。Alessandro Giua：撰写——审阅与编辑，指导。Xiang Yin：撰写——审阅与编辑，指导。

利益冲突声明：作者声明存在以下可能被视为潜在利益冲突的财务利益/个人关系：Xiang Yin表示获得了中国国家自然科学基金的资金支持，且与中国国家自然科学基金存在包括资金资助在内的关系。其他作者则表示没有已知的可能构成利益冲突的财务利益或个人关系。

Bohan Cui|Xinyi Yu|Alessandro Giua|Xiang Yin
上海交通大学自动化与感知学院，中国上海200240