第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201810038 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190828.1720.006html 线性时序逻辑约束下的滚动时域控制路径规划 焦梦甜，宋运忠 (河南理工大学电气工程与自动化学院，河南焦作454003) 摘要：针对有限确定性系统中的路径规划问题，本文提出了一种线性时序逻辑约束下的在线实时求解滚动时 域控制的新方法。该方法将滚动时域控制方法和满足线性时序逻辑公式的策略相结合，控制目标是在满足高 级别任务规范的同时，使收集的累积回报值最大化。其中，在有限时域内的每个时间步长上局部优化回报值， 并应用当前时刻计算获得的最优控制序列。通过执行适当的约束，保证控制器产生的无限轨迹满足期望的时 序逻辑公式。而且，由于地势影响因子的引入，所建议的方案更接近于真实情况。仿真实验结果验证了文中提 出方法的可行性和有效性。 关键词：线性时序逻辑；滚动时域控制；路径规划；最优控制；有限确定性系统；Buchi自动机；Product自动机：地 势影响因子 中图分类号：TP273文献标志码：A文章编号：1673-4785(2020)02-0281-08 中文引用格式：焦梦甜，宋运忠.线性时序逻辑约束下的滚动时域控制路径规划.智能系统学报，2020,15(2)：281-288。 英文引用格式：JIAO Mengtian,SONG Yunzhong.Receding horizon control path planning with linear temporal logic constraints J.CAAI transactions on intelligent systems,2020,15(2):281-288. Receding horizon control path planning with linear temporal logic constraints JIAO Mengtian,SONG Yunzhong (School of Electrical Engineering and Automation,He'nan Polytechnic University,Jiaozuo 454003,China) Abstract:To address the path planning problem in finite deterministic systems,we propose a new method based on lin- ear temporal logic constraints for the online real-time solution of receding horizon control.This method combines a re- ceding horizon control method with a strategy that satisfies a linear temporal logic formula.The control objective is to maximize the collected reward while satisfying the high-level task specification,where the rewards are locally optim- ized at each time step over a finite horizon,and the immediate optimal control computed for the current time step is ap- plied.By enforcing the appropriate constraints,the infinite trajectory produced by the controller is guaranteed to satisfy the desired temporal logic formula.Furthermore,by introducing the terrain factor,the results can be easily obtained.The simulation results indicate the feasibility and effectiveness of the proposed method. Keywords:linear temporal logic;receding horizon control;path planning;optimal control;finite deterministic systems; Buchi automaton;product automaton;terrain factor 因时序逻辑语言与自然语言高度相似，具有 划一组机器人的行为。文献[7]已经将一个线性 强大的表达力，近年来，越来越多的学者开始做 时序逻辑片段作为车辆路径问题的一种规范语 基于时序逻辑理论的路径规划研究。文献4] 言。文献[8]在有时间限制的动态环境中进行线 性时序逻辑约束下的路径规划研究。文献[9-10] 提出了基于计算树逻辑的智能体规划，文献[5-6] 认可了一种自上而下的线性时序逻辑规划方法， 着重从单一的、全局的线性时序逻辑规范上来规 其中，机器人团队被给予一种全局性线性时序逻 收稿日期：2018-10-31.网络出版日期：2019-08-29 辑规范，并努力将任务公式分解为独立的局部线 基金项目：国家自然科学基金项目(61340041,61374079)：河南 省自然科学基金资助项目(182300410112). 性时序逻辑规范，以至于可以根据局部规范单独 通信作者：焦梦甜.E-mail:jiaomengtianxaz@l63.com. 处理每一个独立的机器人。文献[11]探讨了一种
DOI: 10.11992/tis.201810038 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190828.1720.006.html 线性时序逻辑约束下的滚动时域控制路径规划 焦梦甜，宋运忠 （河南理工大学 电气工程与自动化学院，河南 焦作 454003） 摘 要：针对有限确定性系统中的路径规划问题，本文提出了一种线性时序逻辑约束下的在线实时求解滚动时 域控制的新方法。该方法将滚动时域控制方法和满足线性时序逻辑公式的策略相结合，控制目标是在满足高 级别任务规范的同时，使收集的累积回报值最大化。其中，在有限时域内的每个时间步长上局部优化回报值， 并应用当前时刻计算获得的最优控制序列。通过执行适当的约束，保证控制器产生的无限轨迹满足期望的时 序逻辑公式。而且，由于地势影响因子的引入，所建议的方案更接近于真实情况。仿真实验结果验证了文中提 出方法的可行性和有效性。 关键词：线性时序逻辑；滚动时域控制；路径规划；最优控制；有限确定性系统；Büchi 自动机；Product 自动机；地 势影响因子 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2020)02−0281−08 中文引用格式：焦梦甜, 宋运忠. 线性时序逻辑约束下的滚动时域控制路径规划 [J]. 智能系统学报, 2020, 15(2): 281–288. 英文引用格式：JIAO Mengtian, SONG Yunzhong. Receding horizon control path planning with linear temporal logic constraints[J]. CAAI transactions on intelligent systems, 2020, 15(2): 281–288. Receding horizon control path planning with linear temporal logic constraints JIAO Mengtian，SONG Yunzhong (School of Electrical Engineering and Automation, He’nan Polytechnic University, Jiaozuo 454003, China) Abstract: To address the path planning problem in finite deterministic systems, we propose a new method based on linear temporal logic constraints for the online real-time solution of receding horizon control. This method combines a receding horizon control method with a strategy that satisfies a linear temporal logic formula. The control objective is to maximize the collected reward while satisfying the high-level task specification, where the rewards are locally optimized at each time step over a finite horizon, and the immediate optimal control computed for the current time step is applied. By enforcing the appropriate constraints, the infinite trajectory produced by the controller is guaranteed to satisfy the desired temporal logic formula. Furthermore, by introducing the terrain factor, the results can be easily obtained. The simulation results indicate the feasibility and effectiveness of the proposed method. Keywords: linear temporal logic; receding horizon control; path planning; optimal control; finite deterministic systems; Büchi automaton; product automaton; terrain factor 因时序逻辑语言与自然语言高度相似，具有 强大的表达力，近年来，越来越多的学者开始做 基于时序逻辑理论的路径规划研究[1-3]。文献 [4] 提出了基于计算树逻辑的智能体规划，文献 [5-6] 着重从单一的、全局的线性时序逻辑规范上来规 划一组机器人的行为。文献 [7] 已经将一个线性 时序逻辑片段作为车辆路径问题的一种规范语 言。文献 [8] 在有时间限制的动态环境中进行线 性时序逻辑约束下的路径规划研究。文献 [9-10] 认可了一种自上而下的线性时序逻辑规划方法， 其中，机器人团队被给予一种全局性线性时序逻 辑规范，并努力将任务公式分解为独立的局部线 性时序逻辑规范，以至于可以根据局部规范单独 处理每一个独立的机器人。文献 [11] 探讨了一种 收稿日期：2018−10−31. 网络出版日期：2019−08−29. 基金项目：国家自然科学基金项目 (61340041, 61374079)；河南 省自然科学基金资助项目 (182300410112). 通信作者：焦梦甜. E-mail：jiaomengtianxaz@163.com. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
·282· 智能系统学报 第15卷 基于线性时序逻辑规范的自下而上的规划算法， 时刻，对于新的测量状态重复以上过程。这个过 提出了一种部分分散性的解决方案，即只是考虑 程随着时间的推进反复滚动进行。对于一个复杂 具有相互依赖性的智能体的集群，不再去研究整 环境下的路径规划问题，采用滚动时域策略，路 个团队的智能体行为。 径的每一小段都通过求解一个有限时域约束优化 然而，尽管上述方法解决了时序逻辑综合问 问题得到。因此，滚动时域控制方法能够极大地 题，但不能处理依赖于时变参数（动态）的优化问 减少计算时间。 题，此时，可通过在智能体规划上应用滚动时域 定义2有限加权确定性切换系统 方法来解决这个问题。其中，滚动时域控制是一 一个有限加权的确定性切换系统是一个元组 种考虑整个固定时域范围的控制方法，对于每次 T=(Q,qo,△，w,Π，)，其中 由优化算法得到的最优控制序列，仅取序列中的 Q是状态的有限集合，每个状态代表道路网 第一个元素作为当前时刻的控制率。目前，滚动 络中的一个节点； 时域控制的应用几乎遍及各个领域216。同时】 90∈Q是初始状态，代表初始位置； 在滚动时域控制方法与满足时序逻辑公式的控制 △二Q×Q是切换函数，代表节点与节点之间 策略相结合的应用方面，文献[17]中提出了一种 切换关系的集合； 用于控制自动车辆的滚动时域控制方法，该方法 w:△→R是权重函数，为所有节点之间的有 必须满足在分区环境区域内所发生的服务请求的 效切换分配一个正权值成本，如时间或距离等； 丰富任务规范。滚动时域控制也曾被用于文 献[18-19]中，使一个单独智能体的线性时序逻辑 Ⅱ是观测状态的集合，即原子命题集合： 规划达到一个局部最优行为。此外，文献[20-21] h:Q→2”是观测图，即观测状态的命题函数。 也通过应用滚动时域方法来规划智能体的运动， 定义3线性时序逻辑任务公式 然而，作者没有考虑要优化任何回报的收集问题。 线性时序逻辑(linear temporal logic,LTL) 本文针对有限确定性系统中的路径规划问 语句Φ是由切换系统的原子命题、布尔算子逻辑 题，根据给定的回报动态假设和局部回报感知特 连接词[-(Negation)、A(Conjunction)、v(Disjuncti- 点，开发出具有高级线性时序逻辑任务规范和局 on)】和时序逻辑算子[G(Always)、F(Eventually) 部最优回报收集的智能体运动规划的通用框架， X(Next)、U(Until))]组合构成的表达式。例如， 将控制综合问题划分为更小的子问题，并以类似 XQ表示状态Q对应的区域是智能体将要到达的下 于滚动时域的方式逐渐获得可行的正确控制策 一个目标位置，QUQ2表示智能体必须经过状态 略。其中，将智能体的运动环境抽象建模为有限 Q2对应的区域才能到达Q对应的区域。 且确定性的加权切换系统。同时，为了保证满足 定义4 Btichi自动机 时序逻辑规范，从线性时序逻辑模型检测2四中获 一个Buchi自动机是用B=(Ss,S,∑，6，Fa) 得灵感，在切换系统和满足线性时序逻辑公式的 描述的元组，其中 Btichi自动机21之间构造Product自动机，用于获 S是状态的有限集合； 取满足任务的所有可行路径。并遵循类似于离散 S0二Ss是初始状态的集合； 李雅普诺夫函数的构造，提出了一种将成本函数 ∑是输入字母表； 分配给Product自动机状态的算法。即该方法利 6:S×∑→2是切换函数； 用自动机的方法进行模型检测，通过对有限时域 FSS是接受状态的集合。 范围内的成本函数进行重新规划和优化，迭代地 对于Ⅱ上的任意LTL公式中，可以构造一个输 从所有局部路径中寻找回报值最大化的一条局部 入字母表为Σ=2”，接受满足的2”上所有序列的 路径，从而确保系统朝着任务满意度的方向前 Buichi自动机。 进。而且，为使得研究结果更符合实际，我们在 定义5加权Product自动机 势函数中引入地势影响因子，使得改进的势函数 给定一个加权确定性切换系统和一个Buchi 可以更加精细地描述智能体移动的环境。 自动机，则Product自动机为P=厂⑧B,被表示为P= 预备理论 (Sp,Sm,△p,wp,Fp,其中 Sp=QxSg: 定义1滚动时域控制 Sm={qo}×So: 滚动时域控制的理论思路为：在每个时刻，当 △pSS×S是切换的集合，被定义为：如果 前状态的代价函数在有限时域内被优化，并在该 q→Tq,sgBs,(g,.(g,s》e△p: 时刻，仅取最优控制序列中的第一个控制信号实 wp:△p→R是权重函数，被定义为 际作用到系统中，舍去后面各项。接着，在下一 wp((g,s),(g,s))=((g,q)):
基于线性时序逻辑规范的自下而上的规划算法， 提出了一种部分分散性的解决方案，即只是考虑 具有相互依赖性的智能体的集群，不再去研究整 个团队的智能体行为。 然而，尽管上述方法解决了时序逻辑综合问 题，但不能处理依赖于时变参数 (动态) 的优化问 题，此时，可通过在智能体规划上应用滚动时域 方法来解决这个问题。其中，滚动时域控制是一 种考虑整个固定时域范围的控制方法，对于每次 由优化算法得到的最优控制序列，仅取序列中的 第一个元素作为当前时刻的控制率。目前，滚动 时域控制的应用几乎遍及各个领域[12-16]。同时， 在滚动时域控制方法与满足时序逻辑公式的控制 策略相结合的应用方面，文献 [17] 中提出了一种 用于控制自动车辆的滚动时域控制方法，该方法 必须满足在分区环境区域内所发生的服务请求的 丰富任务规范。滚动时域控制也曾被用于文 献 [18-19] 中，使一个单独智能体的线性时序逻辑 规划达到一个局部最优行为。此外，文献 [20-21] 也通过应用滚动时域方法来规划智能体的运动， 然而，作者没有考虑要优化任何回报的收集问题。 Buchi ¨ 本文针对有限确定性系统中的路径规划问 题，根据给定的回报动态假设和局部回报感知特 点，开发出具有高级线性时序逻辑任务规范和局 部最优回报收集的智能体运动规划的通用框架， 将控制综合问题划分为更小的子问题，并以类似 于滚动时域的方式逐渐获得可行的正确控制策 略。其中，将智能体的运动环境抽象建模为有限 且确定性的加权切换系统。同时，为了保证满足 时序逻辑规范，从线性时序逻辑模型检测[22] 中获 得灵感，在切换系统和满足线性时序逻辑公式的 自动机[23] 之间构造 Product 自动机，用于获 取满足任务的所有可行路径。并遵循类似于离散 李雅普诺夫函数的构造，提出了一种将成本函数 分配给 Product 自动机状态的算法。即该方法利 用自动机的方法进行模型检测，通过对有限时域 范围内的成本函数进行重新规划和优化，迭代地 从所有局部路径中寻找回报值最大化的一条局部 路径，从而确保系统朝着任务满意度的方向前 进。而且，为使得研究结果更符合实际，我们在 势函数中引入地势影响因子，使得改进的势函数 可以更加精细地描述智能体移动的环境。 1 预备理论 定义 1 滚动时域控制 滚动时域控制的理论思路为：在每个时刻，当 前状态的代价函数在有限时域内被优化，并在该 时刻，仅取最优控制序列中的第一个控制信号实 际作用到系统中，舍去后面各项。接着，在下一 时刻，对于新的测量状态重复以上过程。这个过 程随着时间的推进反复滚动进行。对于一个复杂 环境下的路径规划问题，采用滚动时域策略，路 径的每一小段都通过求解一个有限时域约束优化 问题得到。因此，滚动时域控制方法能够极大地 减少计算时间。 定义 2 有限加权确定性切换系统 Γ = (Q，q0，∆，ω，Π，h) 一个有限加权的确定性切换系统是一个元组 ，其中 Q 是状态的有限集合，每个状态代表道路网 络中的一个节点； q0 ∈ Q 是初始状态，代表初始位置； ∆ ⊆ Q× Q 是切换函数，代表节点与节点之间 切换关系的集合； ω : ∆ → R +是权重函数，为所有节点之间的有 效切换分配一个正权值成本，如时间或距离等； Π 是观测状态的集合，即原子命题集合； h : Q → 2 Π是观测图，即观测状态的命题函数。 定义 3 线性时序逻辑任务公式 ϕ ¬ ∧ ∨ G F X U XQ Q Q1UQ2 Q2 Q1 线性时序逻辑 (linear temporal logic, LTL) 语句 是由切换系统的原子命题、布尔算子逻辑 连接词 [ (Negation)、 (Conjunction)、 (Disjunction)] 和时序逻辑算子 [ (Always)、 (Eventually)、 (Next)、 (Until)] 组合构成的表达式。例如， 表示状态 对应的区域是智能体将要到达的下 一个目标位置， 表示智能体必须经过状态 对应的区域才能到达 对应的区域。 定义 4 Buchi ¨ 自动机 一个 Buchi ¨ 自动机是用 B = (SB，SB0，Σ，δ，FB) 描述的元组，其中 SB是状态的有限集合； SB0 ⊆ SB是初始状态的集合； Σ 是输入字母表； δ : SB ×Σ → 2 SB是切换函数； FB ⊆ S 是接受状态的集合。 Π ϕ Σ = 2 Π ϕ 2 Π Buchi ¨ 对于 上的任意 LTL 公式 ，可以构造一个输 入字母表为 ，接受满足 的 上所有序列的 自动机。 定义 5 加权 Product 自动机 Buchi ¨ P = Γ ⊗ B (SP，SP0，∆P，ωP，FP) 给定一个加权确定性切换系统和一个 自动机，则 Product 自动机为 ，被表示为 P = ，其中 SP = Q×SB； SP0 = {q0} ×SB0； ∆P ⊆ SP ×SP q → Γq ′ s h(q) → Bs′ ((q,s),(q ′ ,s ′ )) ∈ ∆P 是切换的集合，被定义为：如果 ， ， ； ωP:∆P → R +是权重函数，被定义为 ωP((q,s),(q ′ ,s ′ )) = ω((q,q ′ ))； ·282· 智 能 系 统 学 报 第 15 卷
第2期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·283· Fp=Q×Fs是P上接受状态的集合。 是将地势影响因子对智能体行使速度或距离的影 其中，P上的一个轨迹p=(qo,so)(q,s)…是一 响相应的附加在原有的状态点距离上，以定量的 个无穷序列，且(q,so)∈Sm,对于k≥0时，(qk,)一 准确表达智能体在状态点之间的“实际距离”（若 P(qk+I,sk+)。同时，我们通过移除Buchi自动机的状 切换系统中一个横向单元格的距离为10，假设智 态定义p在r上的投影yr,即可得，若p=(go,so)(q1, 能体在第一种地势区域中，横向行驶一个单元格 s)…,则 需要10min,而在第2种地势区域中，横向行驶一 Yr(p)=q=9og.. (1) 个单元格需要运行12min,此时可将第一种地势 的影响因子设为1，第2种地势的影响因子设为 2问题描述 1.2,并在仿真中分别将两种地势区域中连接横向 给定一个有限加权确定性切换系统「，一个 单元格的状态点之间的实际距离表示为10和12)。 线性时序逻辑任务公式以及一个假设的回报函 即地势影响因子表示为一个可以定量表达地貌形 数。本文的目的是设计一个控制器，使获得的回 态特征和地形属性对智能体实际运行距离影响的 报以滚动时域控制的方式最大化，同时保证产生 因子，人类完全可以通过经验获取地势影响因子 的最优轨迹满足中。 的大小以准确描述状态点之间的实际距离。 2.1切换系统 在本例子中，设定图1切换系统网格中的红 一个确定性加权切换系统的例子如图1所示。 色线条区域、黑色线条区域、绿色线条区域分别 观测状态的集合为Ⅱ={a,b,c,d,其中，观测状态 为不同的地势区域，具有不同的地势影响因子。 a、b、c、d分别用黑色、绿色、蓝色和红色的实心 假设3个区域的地势影响因子ρ的大小如下： 圆圈表示。同时，白色圆圈表示非观测状态。 红色线条区域： 。10<w(q,g)<15 。0<w(q,q)≤10 (2) 黑色线条区域： 1.2,10<w(g,q)<15 p1, 0<w(q,q)≤10 (3) 绿色线条区域： ∫1.3,10<w(q,q)<15 p={1l,0<w(g,90≤10 (4) 若在本例中，不顾及区域之间的地势差别而 粗糙地描述智能体的工作环境，则将导致仿真中 图1给定的切换系统 Fig.1 Given transition system 智能体判断最优路径时出现差错，使最终得到的 图1模拟了一个智能体在类似图形中运动的 仿真结果不切合实际情况，这也与智能体可以应 环境建模。在这个例子中，Γ共有100个状态，位 用在各种复杂环境的目的相斥。若引入地势影响 于矩形网格的顶点，单元大小为10。权重函数 因子，则可以更精细地描述智能体运动的环境模 ω(q,g)是顶点q与g之间的欧几里得距离，如果两 型，使研究结果更符合实际，更真实接近智能体 个顶点之间的欧几里得距离小于15，则两个顶点 在实际情况下的最优路径判断。 之间存在切换关系q一4。 2.2 线性时序逻辑公式中 此外，由于智能体的运行环境中各区域地势 将下面的LTL公式作为智能体的监视任务： 不可能完全相同，而不同的地势就会影响智能体 中=Ga AGFb 的运行距离或速度，本文把在不同地势中影响智 AGb→X-bUc) (5) 能体运动的因素称为地势影响因子，并用符号ρ来 AG(c→XcUd) 表示。图1的切换系统是按照空间距离均匀划分 Φ的第一行，Ga确保智能体在任何时间避免 的模拟单元格，假设智能体分别在图1上的其中 a观测状态。第二行，Gb强制智能体重复访问观 两种地势区域横向行驶了一个单元格，虽然在图1 测状态b。第三行，确保智能体到达观测状态b 上的行驶距离是相同的，但是由于地势的影响， 后，并在返回状态b之前进人观测状态c。同样， 智能体在不同地形运行相同距离时耗用时间不 第四行确保了智能体到达观测状态c之后并在重 同。因仿真中需要实时规划最优路径，故需要将 新回到c之前，智能体被驱动到观测状态d。即 地势影响因子的影响考虑在内，最直接的表达即 智能体要完成b→c→d的监视任务
FP = Q× FB是 P 上接受状态的集合。 P p = (q0,s0)(q1,s1)··· (q0,s0) ∈ SP0 k ⩾ 0 (qk ,sk) → P(qk+1,sk+1) Buchi ¨ p Γ γΓ p = (q0,s0)(q1, s1)··· 其中， 上的一个轨迹 是一 个无穷序列，且 ，对于 时， 。同时，我们通过移除 自动机的状 态定义 在 上的投影 ，即可得，若 ，则 γΓ(p) = q = q0q1 ··· (1) 2 问题描述 Γ ϕ ϕ 给定一个有限加权确定性切换系统 ，一个 线性时序逻辑任务公式 以及一个假设的回报函 数。本文的目的是设计一个控制器，使获得的回 报以滚动时域控制的方式最大化，同时保证产生 的最优轨迹满足 。 2.1 切换系统 Π = {a,b, c,d} 一个确定性加权切换系统的例子如图 1 所示。 观测状态的集合为 ，其中，观测状态 a、b、c、d 分别用黑色、绿色、蓝色和红色的实心 圆圈表示。同时，白色圆圈表示非观测状态。 图 1 给定的切换系统 Fig. 1 Given transition system Γ ω(q,q ′ ) q q ′ q ↔ q ′ 图 1 模拟了一个智能体在类似图形中运动的 环境建模。在这个例子中， 共有 100 个状态，位 于矩形网格的顶点，单元大小为 10。权重函数 是顶点 与 之间的欧几里得距离，如果两 个顶点之间的欧几里得距离小于 15，则两个顶点 之间存在切换关系 。 ρ 此外，由于智能体的运行环境中各区域地势 不可能完全相同，而不同的地势就会影响智能体 的运行距离或速度，本文把在不同地势中影响智 能体运动的因素称为地势影响因子，并用符号 来 表示。图 1 的切换系统是按照空间距离均匀划分 的模拟单元格，假设智能体分别在图 1 上的其中 两种地势区域横向行驶了一个单元格，虽然在图 1 上的行驶距离是相同的，但是由于地势的影响， 智能体在不同地形运行相同距离时耗用时间不 同。因仿真中需要实时规划最优路径，故需要将 地势影响因子的影响考虑在内，最直接的表达即 是将地势影响因子对智能体行使速度或距离的影 响相应的附加在原有的状态点距离上，以定量的 准确表达智能体在状态点之间的“实际距离”(若 切换系统中一个横向单元格的距离为 10，假设智 能体在第一种地势区域中，横向行驶一个单元格 需要 10 min，而在第 2 种地势区域中，横向行驶一 个单元格需要运行 12 min，此时可将第一种地势 的影响因子设为 1，第 2 种地势的影响因子设为 1.2，并在仿真中分别将两种地势区域中连接横向 单元格的状态点之间的实际距离表示为 10 和 12)。 即地势影响因子表示为一个可以定量表达地貌形 态特征和地形属性对智能体实际运行距离影响的 因子，人类完全可以通过经验获取地势影响因子 的大小以准确描述状态点之间的实际距离。 ρ 在本例子中，设定图 1 切换系统网格中的红 色线条区域、黑色线条区域、绿色线条区域分别 为不同的地势区域，具有不同的地势影响因子。 假设 3 个区域的地势影响因子 的大小如下： 红色线条区域： ρ= { 1.5, 10 <ω(q,q ′ ) < 15 1.2, 0 <ω(q,q ′ ) ⩽ 10 (2) 黑色线条区域： ρ= { 1.2, 10 <ω(q,q ′ ) < 15 1, 0 <ω(q,q ′ ) ⩽ 10 (3) 绿色线条区域： ρ= { 1.3, 10 <ω(q,q ′ ) < 15 1.1, 0 <ω(q,q ′ ) ⩽ 10 (4) 若在本例中，不顾及区域之间的地势差别而 粗糙地描述智能体的工作环境，则将导致仿真中 智能体判断最优路径时出现差错，使最终得到的 仿真结果不切合实际情况，这也与智能体可以应 用在各种复杂环境的目的相斥。若引入地势影响 因子，则可以更精细地描述智能体运动的环境模 型，使研究结果更符合实际，更真实接近智能体 在实际情况下的最优路径判断。 2.2 线性时序逻辑公式 ϕ 将下面的 LTL 公式作为智能体的监视任务： ϕ := G¬a ∧GFb ∧G(b → X¬bUc) ∧G(c → X¬cUd) (5) ϕ G¬a GFb b → c → d 的第一行， 确保智能体在任何时间避免 a 观测状态。第二行， 强制智能体重复访问观 测状态 b。第三行，确保智能体到达观测状态 b 后，并在返回状态 b 之前进入观测状态 c。同样， 第四行确保了智能体到达观测状态 c 之后并在重 新回到 c 之前，智能体被驱动到观测状态 d。即 智能体要完成 的监视任务。 第 2 期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·283·
·284· 智能系统学报 第15卷 2.3假设的回报函数 - L(p)= 假定本文描述的系统在具有回报的环境中操 pwp(Pe,Pk+） (6) 作，令在k时刻，与状态q∈Q相关的回报是R(q,k)。 其中，地势影响因子ρ根据式(2)(4)中的定义 其中，回报R(q,)与Q中的状态以时间变化的方式 取值。 联系在一起。并假设在k时刻，系统只能观测当前 此外，定义从状态p∈S到状态p∈Sp的距离 状态q的邻域N(q,k)SQ中各个状态的回报值。同 函数为 时，假设在每个状态q∈Q,如果g与g的欧几里得距 minL(p)若Dp,p）≠O 离不大于29，则在状态q处可以观测到状态g处的 d(p,p')= pED(p.p) (7) 00 若D(PP）=O 回报量。在本案例研究中，定义R(4,)的算法步骤 因为wp是一个正值函数，对于所有p,p∈Sr, 如下： dp,p)>0。其中，可以通过Dijkstra算法等最短 算法1回报值定义算法 路径算法有效计算d(p,p)。 1)定义回报最大值为25 定义6P中一个状态的势函数 2)定义回报最小值为10 状态点的势函数V(p),peS被定义为 3)在k=0时刻：当w(q,q)≤29，并且随机函数 randi(2,l)≠1成立时，设置实际回报值在可取范围 mind(p,p）)若p生F V(p)= (8) 内随机产生 0若p∈F 4)在k>0时刻：当w(q,q)≤29时，设置实际回 式中：F,为F的最大自我可达集合，同时，对于所 报值在可取范围内随机产生 有的p∈SP,V(p)≥0。当且仅当p∈F时，V(p)=0; 根据上述定义算法，回报最大值设置为25， 当且仅当p可到达集合F中的一个状态，则V(p)≠ 最小值设置为10。在k=0时刻，是否可以观测到 o。因此，可得知V(p)代表p到集合F的最短 邻域内每个状态点的回报R(q,0)只有50%的可能 距离。 性，并且回报的实际值是从范围[10,25]内的均匀 本文通过提出算法2来获得对应于任务公式 分布中随机生成的。相似地，在以后的每个时刻 Φ的Buichi自动机，Product自动机，最大自我可达集 k>0,回报值从[10,25]范围内的均匀分布中随机 合F和势函数V(p)。 地重新分配。 算法2势函数计算算法 本文的目的是合成一个控制器，在满足时序 1)构建Buichi自动机：B=LTL2BA(): 逻辑任务的同时，使回报值以滚动时域的方式最 2)构建Product自动机：P=T⑧B; 大化。其中，本文提出的滚动时域控制策略的主 3)对于所有p∈Sp,p∈Fp,计算dp,p'): 要组成部分如下：在时刻k,状态为qk,通过在时域 4)设置Fp=Fp; N上求解最大化回报值的在线优化问题生成了一 5)若存在q∈Fp使mind(q,p)=o,则从Fp中移 个有限轨迹qk+1qk+2…qk+N。应用第一个控制动作 除q以此获得最大自我可达集合F: (q,9k1,然后在时刻k+1,再次计算最优轨迹。 6)若F=O,则返回无满足任务的路径： 7对于所有p∈Sp,使用定义(8)获得V(p) 3构建势函数 4滚动时域控制器设计 本文在Product自动机的状态上引入一个正 值势函数V,它使用权重wp来执行满足自动机的 控制设计的核心组成部分是一个运行在Product 接受条件。从概念上讲，这个函数类似于李雅普 自动机上的状态反馈控制器，该控制器在一定的 诺夫能量函数，其创建满足给定公式的“进展”。 约束条件下，在预定的固定时域内优化有限轨 它将先被离线计算一次，然后将与滚动时域控制 迹。同时，这些约束确保了Product自动机状态上 器一起在线使用。 的势函数在有限时间内减少，从而保证在满足 首先，令D(p,P）={pP1P2…Plp1=P,Pm=P:Pk→ LTL公式方面取得进展。 Ppk+1,k=1…,n-1表示从状态p,∈Sp到状态p∈ 为了说明控制器的工作原理，首先，将k时刻 Sp的所有有限轨迹的集合。若D(p,P)≠O,则表 的当前状态表示为pk,并在k时刻，定义有限固定 明状态P,可以到达状态P,或者状态p可以到达 时域N内Product自动机上的一个有限预测轨迹 状态P,即两个状态之间存在有效切换。 P为：P=PP2#…Pk,其中，P张表示在k时刻时， 其次，为一个有限路径p=p1P2…Pn定义一个 预测轨迹的第个状态。其次，定义P(Pk,W)为从状 路径长度函数： 态P:∈S出发，时域N内所有预测轨迹的集合。此外
2.3 假设的回报函数 k q ∈ Q R(q, k) R(q, k) Q k q N(q, k) ⊆ Q q ∈ Q q q ′ q q ′ R(q, k) 假定本文描述的系统在具有回报的环境中操 作，令在 时刻，与状态 相关的回报是 。 其中，回报 与 中的状态以时间变化的方式 联系在一起。并假设在 时刻，系统只能观测当前 状态 的邻域 中各个状态的回报值。同 时，假设在每个状态 ，如果 与 的欧几里得距 离不大于 29，则在状态 处可以观测到状态 处的 回报量。在本案例研究中，定义 的算法步骤 如下： 算法 1 回报值定义算法 1) 定义回报最大值为 25 2) 定义回报最小值为 10 k = 0 ω(q,q ′ 3) 在 时刻：当 ) ⩽ 29 ，并且随机函数 randi(2,1)≠1 成立时，设置实际回报值在可取范围 内随机产生 k > 0 ω(q,q ′ 4) 在 时刻：当 ) ⩽ 29 时，设置实际回 报值在可取范围内随机产生 k = 0 R(q,0) k > 0 根据上述定义算法，回报最大值设置为 25， 最小值设置为 10。在 时刻，是否可以观测到 邻域内每个状态点的回报 只有 50% 的可能 性，并且回报的实际值是从范围 [10,25] 内的均匀 分布中随机生成的。相似地，在以后的每个时刻 ，回报值从 [10,25] 范围内的均匀分布中随机 地重新分配。 k qk N qk+1qk+2 ···qk+N (qk ,qk+1) k+1 本文的目的是合成一个控制器，在满足时序 逻辑任务的同时，使回报值以滚动时域的方式最 大化。其中，本文提出的滚动时域控制策略的主 要组成部分如下：在时刻 ，状态为 ，通过在时域 上求解最大化回报值的在线优化问题生成了一 个有限轨迹 。应用第一个控制动作 ，然后在时刻 ，再次计算最优轨迹。 3 构建势函数 V ωP 本文在 Product 自动机的状态上引入一个正 值势函数 ，它使用权重 来执行满足自动机的 接受条件。从概念上讲，这个函数类似于李雅普 诺夫能量函数，其创建满足给定公式的“进展”。 它将先被离线计算一次，然后将与滚动时域控制 器一起在线使用。 D ( pi , pj ) = { p1 p2 ··· pn|p1 = pi , pn = pj；pk → Ppk+1, k = 1,··· ,n−1} D ( pi , pj ) , Ø 首先，令 表示从状态 pi∈SP 到状态 pj∈ SP 的所有有限轨迹的集合。若 ，则表 明状态 pi 可以到达状态 pj，或者状态 pj 可以到达 状态 pi，即两个状态之间存在有效切换。 其次，为一个有限路径 p = p1 p2 ··· pn定义一个 路径长度函数： L(p) = ∑n−1 k=1 ρωP(pk , pk+1) (6) 其中，地势影响因子 ρ 根据式 (2)~(4) 中的定义 取值。 p ∈ SP p ′ 此外，定义从状态 到状态 ∈ SP的距离 函数为 d(p, p ′ ) = min p ∈D(p, p ′ ) L(p) 若 D(pi , pj) , Ø ∞ 若 D(pi , pj) = Ø (7) ωP p, p ′ ∈ S P d(p, p ′ ) > 0 d(p, p ′ ) 因为 是一个正值函数，对于所有 ， 。其中，可以通过 Dijkstra 算法等最短 路径算法有效计算 。 定义 6 P 中一个状态的势函数 状态点的势函数 V(p), p ∈ SP被定义为 V(p) = min p ′∈F ∗ P d(p, p ′ ) 若p < F ∗ P 0 若p ∈ F ∗ P (8) F ∗ P FP p ∈ SP V(p) ⩾ 0 p ∈ F ∗ P V(p) = p F ∗ P V(p) , ∞ V(p) p F ∗ P 式中： 为 的最大自我可达集合，同时，对于所 有的 ， 。当且仅当 时 ， 0； 当且仅当 可到达集合 中的一个状态，则 。因此，可得知 代 表 到集合 的最短 距离。 ϕ Buchi ¨ F ∗ P V(p) 本文通过提出算法 2 来获得对应于任务公式 的 自动机，Product 自动机，最大自我可达集 合 和势函数 。 算法 2 势函数计算算法 1) 构建 Buchi ¨ 自动机： B = LTL2BA(ϕ) ； 2) 构建 Product 自动机： P = T ⊗ B ； p ∈ S P p ′ ∈ FP d(p, p ′ 3) 对于所有 ， ，计算 ) ； F ∗ 4) 设置 P = FP； q ∈ F ∗ P min p ∈F ∗ P d(q, p) = ∞ F ∗ P q F ∗ P 5) 若存在 使 ，则从 中移 除 以此获得最大自我可达集合 ； F ∗ 6) 若 P=Ø ，则返回无满足任务的路径； 7) 对于所有 p ∈ S P，使用定义 (8) 获得 V(p)。 4 滚动时域控制器设计 控制设计的核心组成部分是一个运行在 Product 自动机上的状态反馈控制器，该控制器在一定的 约束条件下，在预定的固定时域内优化有限轨 迹。同时，这些约束确保了 Product 自动机状态上 的势函数在有限时间内减少，从而保证在满足 LTL 公式方面取得进展。 k pk k N pk pk := p1|k p2|k ··· pN|k pi|k k i P(pk ,N) pk ∈ SP N 为了说明控制器的工作原理，首先，将 时刻 的当前状态表示为 ，并在 时刻，定义有限固定 时域 内 Product 自动机上的一个有限预测轨迹 为 ： ，其中， 表示在 时刻时， 预测轨迹的第 个状态。其次，定义 为从状 态 出发，时域 内所有预测轨迹的集合。此外， ·284· 智 能 系 统 学 报 第 15 卷
第2期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·285· 由于Product自动机P上的有限预测轨迹会被唯一 情况2V(p)>0,存在i=1,2,…,N使V(Pk-1)=0 地映射到切换系统T上的一个有限轨迹qk=y(p), 若定义(p)为p-,中第一次出现势函数为 因此，若定义与k时刻的预测轨迹P,∈P(P,N)相关 0的标志，即Vp-)=0。则控制器为 的预测回报为R(p),则可将其表示为切换系统 Pi=RH(Pu,Pi) T中有限轨迹y(p)上各状态点回报值的累积总 :=argmax R(p) (14) PLEP(pL.N) 和，如式(9)所示 约束条件：Vp上W)=0。 R(P)= ∑Ryr(Pt》 (9) 其中，若先前的预测轨迹包含这种状态，则强 制最优预测轨迹中的一个状态具有0值的势函数。 4.1滚动时域控制器 情况3V(p)=0 根据Product自动机和滚动时域控制的特点， 控制器定义如下： 可以将滚动时域控制器的设计分为两部分，即k= Pi=RH(Pe.Pi) 0时刻和k>0时刻。 :=argmax R(p) (15) PLEP(PL-N) 4.1.1k=0时刻的滚动时域控制器 约束条件：V(Pw)O时刻，应用滚 约束条件：V(po)0时刻的滚动时域控制器 离线初始化： k>0时刻，控制器的形式表示为 1)构建对应于的Buichi自动机 p度=RH(P,p度-) (11) B=(SB,Sm,2”,6B,FB5 即，它取决于当前状态P,和上一时刻获得的 2)构建Product自动机： 最优预测轨迹p-,=Pi-1…P-1。根据滚动时域 P=T⑧B=(SP,Sm,△p,wP,FPi 控制方案的性质，先前预测轨迹的第一个控制信 3)计算所有状态p∈S,的势函数V(p)。 息被利用。因此，可获得等式(12)： 在线滚动时域控制 Pk=Piw-1,k=1,2,… (12) 1)若存在Po∈So使V(po)≠o,则设置k=0 为满足线性时序逻辑任务，P将用于强制重 2)观测q∈N(qo,)邻域内各状态的回报值， 复执行此控制器以使P上状态的势函数最终减少 获得R(q): 到0。同时，使用以下3种情况来定义控制器(11)： 3)获得p6=RH(So: 情况1V(p)>0,任意k≥1都使得V(P-)≠0 4)在Product自动机P上执行切换(po,Pio), 滚动时域控制器被定义如下： 在切换系统T上执行(q,Yr(pio)切换； Pi=RH(Pu Pi) 5)设置k=1,进入循环； :=argmax R(p) (13) P∈nmM 6)观测q∈W(q,k)邻域内各状态的回报值， 约束条件：V(pw)<VP-)o 获得R(q): 在此情况下，保证P上状态的势函数最终减 7)获得卫=RH(pk,P-i为 少的关键是终端约束条件V(Pww)<V(P-1),即最 8)在Product自动机P上执行切换(p,Pi), 优预测轨迹p必须结束在比先前预测轨迹p-势 在切换系统T上执行(q,yr(Pi)》切换： 函数低的一个状态。 9)设置k←-k+1:
P Γ qk = γΓ(pk) k pk ∈ P(pk ,N) Rk(pk) Γ γΓ(pk) 由于 Product 自动机 上的有限预测轨迹会被唯一 地映射到切换系统 上的一个有限轨迹 ， 因此，若定义与 时刻的预测轨迹 相关 的预测回报为 ，则可将其表示为切换系统 中有限轨迹 上各状态点回报值的累积总 和，如式 (9) 所示: Rk(pk) = ∑N i=1 Rk(γΓ(pi |k)) (9) 4.1 滚动时域控制器 k > 0 根据 Product 自动机和滚动时域控制的特点， 可以将滚动时域控制器的设计分为两部分，即 k = 0 时刻和 时刻。 4.1.1 k = 0 时刻的滚动时域控制器 k = 0 P S P0 = {q0} ×S B0 RH0 (S P0) 在 时刻，由于 的初始状态不是唯一的， 因此，可以从集合 中选取任意初始 初始状态。并将在初始时刻执行的控制器表示为 ，定义如下: p ∗ 0 = RH0 (S P0) :=agrmax p0 ∈P(p0 ,N) R0(p0) (10) 约束条件： V(p0) 0 时刻的滚动时域控制器 k > 0 时刻，控制器的形式表示为 p ∗ k = RH(pk , p ∗ k−1 ) (11) pk p ∗ k−1 = p ∗ 1|k−1 ··· p ∗ N|k−1 即，它取决于当前状态 和上一时刻获得的 最优预测轨迹 。根据滚动时域 控制方案的性质，先前预测轨迹的第一个控制信 息被利用。因此，可获得等式 (12)： pk = p ∗ 1|k−1 , k = 1,2,··· (12) p ∗ k−1 P 为满足线性时序逻辑任务， 将用于强制重 复执行此控制器以使 上状态的势函数最终减少 到 0。同时，使用以下 3 种情况来定义控制器 (11)： V(pk) > 0 k ⩾ 1 V(p ∗ i|k−1 情况 1 , 任意 都使得 ) , 0 滚动时域控制器被定义如下： p ∗ k = RH(pk , p ∗ k−1 ) :=argmax pk∈P(pk ,N) Rk(pk) (13) V(pN|k) 0 i = 1,2,··· ,N V(p ∗ i|k−1 情况 2 ，存在 使 )=0 i 0 (p ∗ k−1 ) p ∗ k−1 V(p ∗ i 0 (p ∗ k−1 )|k−1 ) = 0 若定义 为 中第一次出现势函数为 0 的标志，即 。则控制器为 p ∗ k = RH(pk , p ∗ k−1 ) :=argmax pk∈P(pk ,N) Rk(pk) (14) V(p ∗ i 0 (p ∗ k−1 )−1|k 约束条件： ) = 0。 其中，若先前的预测轨迹包含这种状态，则强 制最优预测轨迹中的一个状态具有 0 值的势函数。 情况 3 V(pk) = 0 控制器定义如下： p ∗ k = RH(pk , p ∗ k−1 ) :=argmax pk∈P(pk ,N) Rk(pk) (15) 约束条件： V(pN|k) 0 RH(pk , p ∗ k−1 ) p ∗ k (pk , p ∗ 1|k ) P (qk , γΓ(p ∗ 1|k )) Γ k+1 切换系统 的总体控制策略在算法 3 中给 出。在离线计算势函数之后，该算法在 时应 用滚动时域控制器 ，在 时刻，应用滚 动时域控制器 。在算法的每次迭代中， 滚动时域控制器返回最优预测轨迹 ，立即切换 应用在 上，对应的切换 应用在 上。然后在 时刻重复该过程。 算法 3 滚动时域控制算法 输入 Γ = (Q,q0,∆,ω,Π,h) ，线性时序逻辑公式 ϕ 输出 控制策略 离线初始化： 1) 构建对应于 ϕ 的 Buchi ¨ 自动机 B = (S B,S B0 ,2 Π ,δB,FB); 2) 构建 Product 自动机： P = Γ ⊗ B = (S P,S P0,∆P,ωP,FP); 3) 计算所有状态 p ∈ S p的势函数 V(p)。 在线滚动时域控制 1) 若存在 p0 ∈ S P0使 V(p0) , ∞，则设置 k = 0 q ∈ N(q0, k) R0(q) 2) 观测 邻域内各状态的回报值， 获得 ； p ∗ 0 = RH0 3) 获得 (S P0) ； P (p0, p ∗ 1|0 ) Γ (q0, γΓ(p ∗ 1|0 )) 4) 在 Product 自动机 上执行切换 ， 在切换系统 上执行 切换； 5) 设置 k = 1 ，进入循环； q ∈ N(qk , k) Rk(q) 6) 观测 邻域内各状态的回报值， 获得 ； p ∗ k = RH(pk , p ∗ k−1 7) 获得 ) ； P (pk , p ∗ 1|k ) Γ (qk , γΓ(p ∗ 1|k )) 8) 在 Product 自动机 上执行切换 ， 在切换系统 上执行 切换； 9) 设置 k ← k+1 ； 第 2 期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·285·
·286· 智能系统学报 第15卷 10)结束循环： 生满足Φ的轨迹，并根据提出的滚动时域控制律 11)否则，将无源于9的满足的运行路径； 使获得的局部回报值最大化。在此案例研究中， 12)结束。 具有回报值的状态可以被看作是“目标”，回报值 的大小可以被视为与每个目标相关的“吸引力”。 5仿真结果分析 回报值最大化的控制目标，可以被解释为：使系 统在具有高度吸引力的测量状态中所收集到的信 将有限切换系统T,LTL公式中，时域N作为输 息量获得最大化。 入，函数R(g,k)生成了定义在厂状态上的时变回报 在本案例研究中，选择时域N=4。通过应用 值。通过执行算法3概述的控制算法，在Γ中产 算法3，系统轨迹的前4个截图如图2所示。 (a)第1个时间步长下的 (6)第1个时间步长下的 当前状态及回报感知状态 最优预测轨迹 (c)第2个时间步长下的 (d)第2个时间步长下的 当前状态及回报感知状态 最优预测轨迹 图2在滚动时域控制律下系统轨迹的截图 Fig.2 Screenshots of the system trajectory under the receding horizon control law 在图2中，具有回报量的状态（回报感知状 将势函数与时间步长的关系以及回报值总和与时 态)都用青色标出，青色圆圈的大小与相应状态 间步长的关系绘制在图3中。 点的回报值大小成正比。各子图的含义如下： 在每个时刻上绘制了势函数V(p)。可得知， 图2(a):在k=0时刻，初始状态被标记为紫色。 经过51个时间步长后，势函数大小变为0，这意 图2(b):滚动时域控制器RHP(Sm)在初始状态 味着到达了Product自动机的接受状态。鉴于每 下开始运行，将有限时域内的最优预测轨迹用 次到达接受状态时，系统至少访问一次b、c、d,即 一系列黄色状态标记。 完成b→c→d监视任务的一个周期。同时，可从 图2(c):第一次切换qo→Tq应用在有限加权 图片看出，势函数的曲线几乎总是在下降，即始 切换系统T上，同时，切换pPo→Pp应用在Product 终朝着任务公式“进展”。 自动机P上。系统的当前状态(q)被标记为紫色。 从图3可以看出回报值在每个离散时刻变 图2(d):滚动时域控制器p=RH(p1,p6)在p1处 化，收集到的回报量总和在稳步增长。其实，控 被计算。有限时域内的最优预测轨迹p用一系列 制器通常选择满足终端约束，而不是选择增加势 黄色状态标记。 函数以便获得更多回报。因此，在这种情况下 同时，将仿真时间设置为100个时间步长，并 对势函数的约束控制了局部回报量的最大化
10) 结束循环； 11) 否则，将无源于 q0的满足 ϕ 的运行路径； 12) 结束。 5 仿真结果分析 Γ ϕ N R(q, k) Γ Γ 将有限切换系统 ，LTL 公式 ，时域 作为输 入，函数 生成了定义在 状态上的时变回报 值。通过执行算法 3 概述的控制算法，在 中产 生满足 ϕ 的轨迹，并根据提出的滚动时域控制律 使获得的局部回报值最大化。在此案例研究中， 具有回报值的状态可以被看作是“目标”，回报值 的大小可以被视为与每个目标相关的“吸引力”。 回报值最大化的控制目标，可以被解释为：使系 统在具有高度吸引力的测量状态中所收集到的信 息量获得最大化。 在本案例研究中，选择时域 N = 4 。通过应用 算法 3，系统轨迹的前 4 个截图如图 2 所示。 (a) 第1个时间步长下的 当前状态及回报感知状态 (b) 第1个时间步长下的 最优预测轨迹 (c) 第2个时间步长下的 当前状态及回报感知状态 (d) 第2个时间步长下的 最优预测轨迹 图 2 在滚动时域控制律下系统轨迹的截图 Fig. 2 Screenshots of the system trajectory under the receding horizon control law 在图 2 中，具有回报量的状态 (回报感知状 态) 都用青色标出，青色圆圈的大小与相应状态 点的回报值大小成正比。各子图的含义如下： 图 2(a)：在 k = 0 时刻，初始状态被标记为紫色。 RH0 (S P0) p ∗ 0 图 2(b)：滚动时域控制器 在初始状态 下开始运行，将有限时域内的最优预测轨迹 用 一系列黄色状态标记。 q0 → Γq1 Γ p0 → Pp1 P (q1) 图 2(c)：第一次切换 应用在有限加权 切换系统 上，同时，切换 应用在 Product 自动机 上。系统的当前状态 被标记为紫色。 p ∗ 1 = RH(p1, p ∗ 0 ) p1 p ∗ 1 图 2(d): 滚动时域控制器 在 处 被计算。有限时域内的最优预测轨迹 用一系列 黄色状态标记。 同时，将仿真时间设置为 100 个时间步长，并 将势函数与时间步长的关系以及回报值总和与时 间步长的关系绘制在图 3 中。 V(p) b → c → d 在每个时刻上绘制了势函数 。可得知， 经过 51 个时间步长后，势函数大小变为 0，这意 味着到达了 Product 自动机的接受状态。鉴于每 次到达接受状态时，系统至少访问一次 b、c、d，即 完成 监视任务的一个周期。同时，可从 图片看出，势函数的曲线几乎总是在下降，即始 终朝着任务公式“进展”。 从图 3 可以看出回报值在每个离散时刻变 化，收集到的回报量总和在稳步增长。其实，控 制器通常选择满足终端约束，而不是选择增加势 函数以便获得更多回报。因此，在这种情况下， 对势函数的约束控制了局部回报量的最大化。 ·286· 智 能 系 统 学 报 第 15 卷
第2期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·287· 600 我可达集合F的最短距离不同)，并且相邻时刻的 势函数变化率不同，因此，两种情况下控制器产 生的轨迹完全不同。对比回报值总和的仿真结 果，也可得出获取的累积回报值大小不同。两种 0102030405060708090100 时间步长 情况的仿真结果对比突出了在地势不同的运行区 (a)势函数 域内，必须要引入地势影响因子的意义。 1500 然而，本文只是比较客观的加入了几个假设 的地势影响因子来阐述不同地势对智能体在状态 点之间运行距离的影响，所假设的因子数值大小 500 与智能体的实际工作环境无关，即本文只是在一 0102030405060708090100 个模拟的复杂多变地势环境下，通过假设的地势 时间步长 (b)回报值总和 影响因子来实现满足控制目标的路径规划。在实 际状况下，便可通过人为经验获得地势影响因子 图3100个时间步长下的势函数和回报值总和 的大小来准确规划每一时刻的最优路径以获得最 Fig.3 Potential function and total reward for 100 time- step 大累积回报值。 此外，本文对未引入地势影响因子的情况进 6结束语 行了仿真，其中，将式(6)表述的路径长度函数重 新定义为 本文提出了一种线性时序逻辑约束下的在线 实时求解滚动时域控制的新方法来解决有限确定 L(p)=〉wp(Pk,Pk+) (16) 性系统中的路径规划问题。该方法描述了保证无 由于式(6)与式(8)所定义的势函数严格相 限轨迹满足给定线性时序逻辑公式的情况下，局 关，而式(6)与式(16)存在差异，因此，未引入地 部优化有限确定性系统轨迹的滚动时域控制框 势影响因子与引入地势影响因子的区别实质为势 架，其优化标准被定义为最大化与系统状态相关 函数定义的差异。根据算法1和算法2，以及滚 联的时变回报值，同时，也开发了基于类能量函 动时域控制算法3，通过MATLAB仿真，绘制了 数定义的强化自动机接受条件的可证明正确的控 未引入地势影响因子情况下的势函数以及回报值 制策略。 总和与时间步长的关系，如图4所示。 有关线性时序逻辑约束下的滚动时域控制问 400 题，将来会有多个研究方向。例如，可以将所提 300 出的框架扩展到有限概率系统，马尔可夫决策过 0 程和部分可观测马尔可夫决策过程。还可以尝试 100 将研究成果扩展到其他有限系统模型，如非确定 0 102030405060708090100 时间步长 性系统。 (a)势函数 参考文献： 1500 [1]Fainekos G E,Girard A,Kress-Gazit H,et al.Temporal lo- gic motion planning for dynamic robots[J].Automatica, 500 2009,45(2)343-352 0 10203040.5060708090100 [2]Plaku E,Karaman S.Motion planning with temporal logic 时间步长 specifications:progress and challenges[J].Al communica- (b)回报值总和 tions,.2015,29(1)151-162. 图4未引入地势影响因子时100个时间步长下的势函 [3]Saha S,Julius AA.Task and motion planning for manipu- 数和回报值总和 lator arms with metric temporal logic specifications[J]. Fig.4 Potential function and total reward for 100 time- IEEE robotics and Automation letters,2018,3(1): step without terrain influence factor 379-386. 对比图3和图4的势函数仿真结果，可知，在 [4]Andersen M S,Jensen R S,Bak T,et al.Motion planning 两图中的每一相同时刻，状态点的势函数大小不 in multi-robot systems using timed automata[J].Promot- 同（当前状态到Product自动机接受状态的最大自 ing health for working women,2004,37(8):597-602
0 10 20 30 40 50 60 70 80 90 100 200 400 600 势函数 (a) 势函数 (b) 回报值总和 0 10 20 30 40 50 60 70 80 90 100 500 1 000 1 500 回报值总和 时间步长 时间步长 图 3 100 个时间步长下的势函数和回报值总和 Fig. 3 Potential function and total reward for 100 timestep 此外，本文对未引入地势影响因子的情况进 行了仿真，其中，将式 (6) 表述的路径长度函数重 新定义为 L(p) = ∑n−1 k=1 ωP(pk , pk+1) (16) 由于式 (6) 与式 (8) 所定义的势函数严格相 关，而式 (6) 与式 (16) 存在差异，因此，未引入地 势影响因子与引入地势影响因子的区别实质为势 函数定义的差异。根据算法 1 和算法 2，以及滚 动时域控制算法 3，通过 MATLAB 仿真，绘制了 未引入地势影响因子情况下的势函数以及回报值 总和与时间步长的关系，如图 4 所示。 0 10 20 30 40 50 60 70 80 90 100 势函数 100 200 300 400 0 10 20 30 40 50 60 70 80 90 100 回报值总和 时间步长 时间步长 500 1 000 1 500 (a) 势函数 (b) 回报值总和 图 4 未引入地势影响因子时 100 个时间步长下的势函 数和回报值总和 Fig. 4 Potential function and total reward for 100 timestep without terrain influence factor 对比图 3 和图 4 的势函数仿真结果，可知，在 两图中的每一相同时刻，状态点的势函数大小不 同 (当前状态到 Product 自动机接受状态的最大自 F ∗ 我可达集合 P的最短距离不同)，并且相邻时刻的 势函数变化率不同，因此，两种情况下控制器产 生的轨迹完全不同。对比回报值总和的仿真结 果，也可得出获取的累积回报值大小不同。两种 情况的仿真结果对比突出了在地势不同的运行区 域内，必须要引入地势影响因子的意义。 然而，本文只是比较客观的加入了几个假设 的地势影响因子来阐述不同地势对智能体在状态 点之间运行距离的影响，所假设的因子数值大小 与智能体的实际工作环境无关，即本文只是在一 个模拟的复杂多变地势环境下，通过假设的地势 影响因子来实现满足控制目标的路径规划。在实 际状况下，便可通过人为经验获得地势影响因子 的大小来准确规划每一时刻的最优路径以获得最 大累积回报值。 6 结束语 本文提出了一种线性时序逻辑约束下的在线 实时求解滚动时域控制的新方法来解决有限确定 性系统中的路径规划问题。该方法描述了保证无 限轨迹满足给定线性时序逻辑公式的情况下，局 部优化有限确定性系统轨迹的滚动时域控制框 架，其优化标准被定义为最大化与系统状态相关 联的时变回报值，同时，也开发了基于类能量函 数定义的强化自动机接受条件的可证明正确的控 制策略。 有关线性时序逻辑约束下的滚动时域控制问 题，将来会有多个研究方向。例如，可以将所提 出的框架扩展到有限概率系统，马尔可夫决策过 程和部分可观测马尔可夫决策过程。还可以尝试 将研究成果扩展到其他有限系统模型，如非确定 性系统。 参考文献： Fainekos G E, Girard A, Kress-Gazit H, et al. Temporal logic motion planning for dynamic robots[J]. Automatica, 2009, 45(2): 343–352. [1] Plaku E, Karaman S. Motion planning with temporal logic specifications: progress and challenges[J]. AI communications, 2015, 29(1): 151–162. [2] Saha S, Julius A A. Task and motion planning for manipulator arms with metric temporal logic specifications[J]. IEEE robotics and Automation letters, 2018, 3(1): 379–386. [3] Andersen M S, Jensen R S, Bak T, et al. Motion planning in multi-robot systems using timed automata[J]. Promoting health for working women, 2004, 37(8): 597–602. [4] 第 2 期 焦梦甜，等：线性时序逻辑约束下的滚动时域控制路径规划 ·287·
·288· 智能系统学报 第15卷 [5]Kloetzer M,Xuchu Ding,Belta C.Multi-robot deploy- DUAN Haibin,YANG Zhiyuan.Large civil aircraft re- ment from LTL specifications with reduced communica- ceding horizon control based on cauthy mutation pigeon tion[C].The 50th IEEE conference on decision and con- inspired optimization[J].Scientia Sinica technologica, trol and European control conference.Orlando,USA, 2018.48(03):277-288 2011:4867-4872 [17]Ulusoy A,Belta C.Receding horizon temporal logic con [6]Shital S.Chiddarwar,N Ramesh Babu.Multi-agent sys- trol in dynamic environments[J].The international journ- tem for off-line coordinated motion planning of multiple al of robotics research,2014,33(12):1593-1607. industrial robots[J].International journal of advanced ro- [18]Ding X C,Belta C,Cassandras C G.Receding horizon botic systems,2011,8(1):102-112 surveillance with temporal logic specifications[C].The [7]Karaman S,Frazzoli E.Vehicle routing with linear tempor- 49th IEEE conference on decision and control.Atlanta. al logic specifications:applications to multi-UAV mission USA.2010:256-261 planning[J].International journal of robust Nonlinear [19]Tumova J,Dimarogonas D V.A Receding horizon ap- control,.2011,21(12):1372-1395 proach to multi-agent planning from local LTL specifica- [8]Zhou Y,Maity D,Baras JS.Optimal mission planner with tions[C].2014 American control conference.Portland, timed temporal logic constraints[C].IEEE 2015 European USA.2014:1775-1780. control conference.Linz,Austria,2015:759-764 [20]Wongpiromsarn T,Topcu U,Murray R M.Receding hori- [9]Chen Y,Ding XC,Stefanescu A,et al.Formal approach to zon temporal logic planning for dynamical systems[C]. the deployment of distributed robotic teams[J].IEEE trans- Proceedings of the 48th IEEE conference on decision and actions on robotics,2012,28(1):158-171. control.Shanghai,China,2009,57(11):5997-6004. [10]Ulusoy A,Smith S L,Ding X C,et al.Optimality and ro- [21]Wongpiromsarn,Topcu,Ufuk,et al.Receding horizon bustness in multi-robot path planning with temporal logic control for temporal logic Specifications[C].Proceedings constraints[J].International journal of robotics research, of the 13th ACM international conference on hybrid sys- 2013,32(8:889-911. tems.Stockholm,Sweden,2010:101-110. [11]Guo M,Dimarogonas D V.Multi-agent plan reconfigura- [22]朱创营，常亮，徐周波，等.含有合取查询的时态描述逻 tion under local LTL specifications[J].International 辑ALC-LTL模型检测).智能系统学报，2014,9(06)： journal of robotics research.2015.34(2):218-235. 714-722 [12]Dunbar W B.Caveney D S.Distributed receding horizon ZHU Chuangying,CHANG Liang,XU Zhoubo,et al.Re- control of vehicle platoons:stability and string search on the model checking of temporal description lo- stability[J].IEEE transactions on automatic control,2012, gic ALC-LTL containing conjunctive query[J].CAAI 57(3:620-633. transactions on intelligent systems,2014,9(06):714-722. [13]李佩杰，林颂晨，白晓清，等.计及配电网三相模型的电 [23]郭建，边明明，韩俊岗.LTL公式到自动机的转换).计 动汽车充电滚动时域控制[].中国电机工程学报， 算机科学，2014,906)：714-722 2016,36(17):4533-4543. GUO Jian,BIAN Mingming,HAN Jungang.Translation LI Peijie,LIN Songchen,BAI Xiaoqing,et al.Receding- from LTL formula into automata[J].Computer science, horizon-control-based charging method of electric vehicle 2014,906:714722 considering three-phase model of distribution network[J]. 作者简介： Proceedings of the CSEE,2016,36(17):4533-4543. 焦梦甜，硕士研究生，主要研究方 [14]Grema A S,Cao Y.Receding horizon control for oil 向为复杂系统建模与控制。发表学术 reservoir waterflooding process[J].Systems science 论文2篇。 Control engineering an open access journal,2017,5(1): 449461. [15]王文彬，秦小林，张力戈，等.基于滚动时域的无人机动 态航迹规划).智能系统学报，2018,13(04)524-533， WANG Wenbin,QIN Xiaolin,ZHANG Lige,et al.Dy. 宋运忠，教授，博士生导师，主要 namic UAV trajectory planning based on receding hori- 研究方向为多智能体系统的分析与控 zon[J].CAAI transactions on intelligent systems,2018, 制、非线性系统的分析与控制。主持 13(04):524-533. 完成国家自然科学基金项目5项。发 [16]段海滨，杨之元.基于柯西变异鸽群优化的大型民用飞 表学术论文80余篇。 机滚动时域控制).中国科学：技术科学，2018,48(03)： 277-288
Kloetzer M, Xuchu Ding, Belta C. Multi-robot deployment from LTL specifications with reduced communication[C]. The 50th IEEE conference on decision and control and European control conference. Orlando, USA, 2011: 4867–4872. [5] Shital S. Chiddarwar, N Ramesh Babu. Multi-agent system for off-line coordinated motion planning of multiple industrial robots[J]. International journal of advanced robotic systems, 2011, 8(1): 102–112. [6] Karaman S, Frazzoli E. Vehicle routing with linear temporal logic specifications: applications to multi-UAV mission planning[J]. International journal of robust & Nonlinear control, 2011, 21(12): 1372–1395. [7] Zhou Y, Maity D, Baras J S. Optimal mission planner with timed temporal logic constraints[C]. IEEE 2015 European control conference. Linz, Austria, 2015: 759-764. [8] Chen Y, Ding X C, Stefanescu A, et al. Formal approach to the deployment of distributed robotic teams[J]. IEEE transactions on robotics, 2012, 28(1): 158–171. [9] Ulusoy A, Smith S L, Ding X C, et al. Optimality and robustness in multi-robot path planning with temporal logic constraints[J]. International journal of robotics research, 2013, 32(8): 889–911. [10] Guo M, Dimarogonas D V. Multi-agent plan reconfiguration under local LTL specifications[J]. International journal of robotics research, 2015, 34(2): 218–235. [11] Dunbar W B, Caveney D S. Distributed receding horizon control of vehicle platoons: stability and string stability[J]. IEEE transactions on automatic control, 2012, 57(3): 620–633. [12] 李佩杰, 林颂晨, 白晓清, 等. 计及配电网三相模型的电 动汽车充电滚动时域控制 [J]. 中国电机工程学报, 2016, 36(17): 4533–4543. LI Peijie, LIN Songchen, BAI Xiaoqing, et al. Recedinghorizon-control-based charging method of electric vehicle considering three-phase model of distribution network[J]. Proceedings of the CSEE, 2016, 36(17): 4533–4543. [13] Grema A S, Cao Y. Receding horizon control for oil reservoir waterflooding process[J]. Systems science & Control engineering an open access journal, 2017, 5(1): 449–461. [14] 王文彬, 秦小林, 张力戈, 等. 基于滚动时域的无人机动 态航迹规划 [J]. 智能系统学报, 2018, 13(04): 524–533. WANG Wenbin, QIN Xiaolin, ZHANG Lige, et al. Dynamic UAV trajectory planning based on receding horizon[J]. CAAI transactions on intelligent systems, 2018, 13(04): 524–533. [15] 段海滨, 杨之元. 基于柯西变异鸽群优化的大型民用飞 机滚动时域控制 [J]. 中国科学: 技术科学, 2018, 48(03): 277–288. [16] DUAN Haibin, YANG Zhiyuan. Large civil aircraft receding horizon control based on cauthy mutation pigeon inspired optimization[J]. Scientia Sinica technologica, 2018, 48(03): 277–288. Ulusoy A, Belta C. Receding horizon temporal logic control in dynamic environments[J]. The international journal of robotics research, 2014, 33(12): 1593–1607. [17] Ding X C, Belta C, Cassandras C G. Receding horizon surveillance with temporal logic specifications[C]. The 49th IEEE conference on decision and control. Atlanta, USA, 2010: 256–261. [18] Tumova J, Dimarogonas D V. A Receding horizon approach to multi-agent planning from local LTL specifications[C]. 2014 American control conference. Portland, USA, 2014: 1775–1780. [19] Wongpiromsarn T, Topcu U, Murray R M. Receding horizon temporal logic planning for dynamical systems[C]. Proceedings of the 48th IEEE conference on decision and control. Shanghai, China, 2009, 57 (11): 5997–6004. [20] Wongpiromsarn, Topcu, Ufuk, et al. Receding horizon control for temporal logic Specifications[C]. Proceedings of the 13th ACM international conference on hybrid systems. Stockholm, Sweden, 2010: 101–110. [21] 朱创营, 常亮, 徐周波, 等. 含有合取查询的时态描述逻 辑 ALC-LTL 模型检测 [J]. 智能系统学报, 2014, 9(06): 714–722. ZHU Chuangying, CHANG Liang, XU Zhoubo, et al. Research on the model checking of temporal description logic ALC-LTL containing conjunctive query[J]. CAAI transactions on intelligent systems, 2014, 9(06): 714–722. [22] 郭建, 边明明, 韩俊岗. LTL 公式到自动机的转换 [J]. 计 算机科学, 2014, 9(06): 714–722. GUO Jian, BIAN Mingming, HAN Jungang. Translation from LTL formula into automata[J]. Computer science, 2014, 9(06): 714–722. [23] 作者简介： 焦梦甜，硕士研究生，主要研究方 向为复杂系统建模与控制。发表学术 论文 2 篇。 宋运忠，教授，博士生导师，主要 研究方向为多智能体系统的分析与控 制、非线性系统的分析与控制。主持 完成国家自然科学基金项目 5 项。发 表学术论文 80 余篇。 ·288· 智 能 系 统 学 报 第 15 卷