基于HTN的巡视器动态规划方法

师 明, 高宇辉, 张 弓

(1. 北京航天飞行控制中心, 北京 100094; 2. 航天飞行动力学技术重点实验室, 北京 100094)

0 引 言

深空探测任务中,地面运控中心根据任务目标、巡视器遥测状态、测通通信条件等要求,生成周期性的任务计划和工作指令。为提高工程系统的稳健性和运行效率,工程部门引入人工智能技术开发规划调度系统,完成复杂约束条件下的事件冲突消解。例如,火星快车人工表示(Mars express artificial representation, MEXAR)系统采用时间轴表示框架构建领域相关的约束能力模型,支持生成多日/周工作计划,使火星快车数据下行管理的规划事件减少了50%[1]。MEXAR的成功经验为先进规划与调度计划(advanced planning and scheduling initiative, APSI)软件平台奠定了技术基础,后者将规划领域模型描述为并行的时间线集合,在规划过程中进行并行事件的约束传播和冲突消解,获取规划问题的可行解[2-3]。欧洲航空局(European Space Agency, ESA)在APSI之后推出的火星快车科学规划工具系统,将APSI的时间线框架拓展为通用、灵活的软件架构[3-4]。但是,APSI的设计目的在于解决复杂度较高的问题,缺少对于一般问题的普适性。美国宇航局(National Aeronautics and Space Administration,NASA)针对不同任务特点推出多个规划架构和系统平台。哈勃天文望远镜长期任务调度和规划系统,支持生成多达5 000个观测活动的工作序列[5]。“深空一号”任务中所采用的远程智能体规划系统,使用任务分解和迭代修补的方法完成对资源和时间约束的处理,支持巡视器自主飞行,但系统实现较为复杂[6-7]。在南极测绘、地球观测一号和轨道快车等多个空间飞行任务中,应用部署的自动调度和规划环境(automated scheduling and planning environment,ASPEN)系统开发架构,采用时间推理系统表示和处理时间约束[8-9]。在国际空间站“太阳能电池阵列约束引擎”、行走机器人控制、水下无人驾驶系统等使用的可扩展通用远程操控规划架构(extensible universal remote operations planning architecture,EUROPA)采用基于组件的软件框架和面向对象的语法,描述时间、资源、规则和变量等约束条件,具有领域建模、规划表示、约束传播等功能[10-12]。在火星巡视器机遇号和勇气号中使用的活动计划生成系统,则同时调用了EUROPA、ASPEN两个规划器,采用时间线技术处理能源、通信等约束[13-14]。上述规划系统均以时间线为核心进行约束表示和冲突消解,高度依赖地面测控系统提供长时间的连续跟踪,以完成对多个事件的安排。

在嫦娥探月工程中,总体部门在嫦娥3号任务中提出“工作模式”的概念,并应用于历次深空探测任务[15]。工作模式是巡视器动作序列的逻辑关系的组合,不考虑动作的时间信息。如祝融号针对低温、弱光照的环境,设计了4种正常工作模式以确保能源安全[16]。北京飞行控制中心作为深空探测地面运控中心,采用经典动作规划技术,以工作模式为规划对象构建智能规划系统,解决了约束条件下多分支作业选择困难和事件属性设置复杂等难题[17]。为提升测控效率,深空探测任务存在动态规划的需求。动态规划与事件的时间属性密切相关,因此需要进一步完善领域知识模型,以支持巡视器活动序列的动态调整。

分层任务网络(hierarchical task network,HTN)是一种基于状态转移的规划方法,最初由Sacerdoti在1975年的研究中提出[18];Yang等引入前置条件完善了动作集合的定义[19];Kambhampati等进一步将分层非线性规划与领域知识结合,提出任务分解和一致性验证的方法[20],至Erol形成经典的HTN形式化定义[21-22]。HTN规划方法采用原子命题集合表示系统状态、动作和方法,将复合任务不断分解为子任务,形成原子任务的集合并作为规划的最小单元。对于巡视器任务规划问题而言,方法的适用性主要体现在3个方面:首先,HTN规划基于领域知识进行推理,将复合任务逐层分解,适用于巡视器任务规划中任务目标的层次性特征;然后,基于分层分解的思想处理复杂问题的方法使HTN规划有能力解决大规模问题,对规模和数量日益庞大的巡视器任务规划问题具有很强的应用潜力;最后,HTN规划方法具有很强的领域知识表达能力,能够充分表达任务分解过程中的条件以及动作执行对系统状态的改变。因此,采用HTN规划能够清晰地表达逻辑推理过程,且便于记录任务分解的关键节点,有利于在动态执行环境下进行方案修复。但是,基于HTN理论发展而来的领域无关规划器不支持对时间关系的处理[23]。相关研究中针对具体问题,发展出一种基于简单时间网络(simple temporal network, STN)的处理方法,包括建模中引入时态偏好[24]、设计特定数据结构进行算法优化[25]等,在文献[26]和文献[27]等特定领域的规划器得到应用,不具有普适性。

本文采用HTN的方法,提出任务、周期作业、动作序列、状态受限事件、原子动作和指令计划6层规划体系,结合飞控工程经验把全局时间点引入Allen教授提出的区间代数定义,拓展事件时态约束关系的表示方法,实现一种基于虚拟事件和虚拟指令的动态规划方法。所提出的动态规划流程和处理方法可以广泛应用于不同型号航天器地外天体的巡视探测任务。

1 问题描述

巡视器探测目标距离遥远,存在长时间单程时间延迟,如地球到月球的单程通信时延达到1.35 s,地球到火星的单程通信时延达到22.3 min,地球到冥王星的单程通信时延超过6 h 58 min[16],结合测控资源现状,测控弧段资源有限,巡视器不能依赖地面运控中心实时规划的结果。同时,巡视器在受到外部空间环境、载荷平台状态异常等扰动时,地面飞控作业需要及时引入新的约束条件,生成新的规划方案,以避免对飞控实施工作造成影响,因此在飞控任务中催生出动态规划的需求。

考虑以下影响因素:

(1)工作模式是一种基于状态转移的设计,未考虑事件的时态属性,导致巡视器工作状态与地面飞控中心是一种松耦合关系,降低了人在回路的控制能力。

(2)在进出测控区、光照阴影区等测控时间点时,需要根据巡视器遥测数据判定的状态,安排临时任务,生成新的指令。考虑到未知环境隐含的不确定性,临时任务可能会对初始规划结果中的事件时态关系产生影响。

(3)动作执行状态的改变,带来状态一致性的问题。动作序列与条件效果序列是对应的,在动作执行过程中,这种对应关系不应该发生变化。临时新增任务所包含的动作和动作序列,可能导致状态空间发生变化,进而导致规划结果的不准确。

因此,需要引入一种领域知识模型的范式,以表征事件之间的时态约束关系;减少动态规划带来的不确定性,提高工程任务的执行效率。

2 基于HTN的领域知识建模

本文结合巡视器领域知识,将工程任务自上而下分为任务、周期作业、动作序列、状态受限事件、原子动作和指令计划6个层级,如图1所示。完成任务目标确定、约束传播与状态一致性判定,最后通过指令展开获得航天器上行的指令序列。每个层级都包含特有的领域知识,通过HTN的范式定义统一起来,具体定义如下。

图1 基于HTN的任务分层模式设计Fig.1 Task layering pattern design based on HTN

定义 1科学探测任务:

P=〈D,S0,TCN〉

(1)

式中:D表示领域知识模型;S0表示任务初始状态;时态约束网络(temporal constraint network, TCN)表示时态约束网络。通过对工程总体文件进行分析,获得巡视器科学探测任务。

定义 2状态集合:

S=〈Q,C〉

(2)

式中:Q表示巡视器本体相关的状态,包括主体坐标、桅杆指向、天线指向、电量等;C表示外部约束条件集合,包括太阳高度角、通信链路、载波切换计划等。每个目标命题都具有如下形式Si={s′∈S,∀s∈G},其中G为任务目标状态集合。任务初始状态S0表示在初始时刻i=0时的任务状态,g是状态集合中的元素,表示巡视器在当前任务的目标状态。

定义 3领域知识模型:

D=〈O,M,δ〉

(3)

式中:O表示动作序列的集合;M表示方法集合;δ表示状态转移函数。

下面对领域知识模型中的3个元素进行详细描述,所涉及到变量定义中,均满足条件∀i∈N。

用三元组〈head(o),pre(o),effect(o)〉表示动作序列集合O,head(oi)为动作序列的头部文件,包含了动作序列名称和缺省参数;pre(oi)表示执行动作序列o前需要满足的前提条件;effect(oi)是执行动作序列oi后产生的效果。动作序列集合O将任务分解为带参数选项的“工作模式”,每个模式包含了缺省的动作序列,同时还定义了一些与规划计算相关的属性或约束。在领域模型中,动作序列执行的前置条件即当前巡视器本体状态需要满足约束条件,判断条件为pre(o)={S(Q),S(C)}。

综合分析探测点可达性评估方法、测控跟踪条件计算方法、太阳高度角/方位角的预报方法、不同路况下能源消耗估算策略以及科学探测需求,将巡视器动作序列实例化表示为工作模式,定义

O={!perceive,!move,!detect,!charge,!sleep}

式中:!perceive表示感知模式,即巡视器获取导航信息数据,并将导航信息数据下传到地面控制中心;!move表示移动模式,即巡视器接收地面控制中心指令,达到目标位置;!detect表示探测模式,即巡视器所携带的有效载荷设备加电工作,获取科学探测数据,并在通信窗口内将数据下传到地面控制中心;!charge表示充电模式,即巡视器调整太阳翼,按规定实现对日定向后保持静止状态,蓄电池组开始充电;!sleep表示休眠模式,巡视器其他设备完全断电不工作。工作模式的名称、前提条件和动作效果,作为参数写入巡视器配置文件。工作模式构成了HTN的原子任务,动作序列则用来完成原子任务并改变当前状态,当序列数量N=1时,表示该工作模式仅包含一个动作。

用四元组〈head(m),pre(m),subTask(m),Ep(m)〉表示方法集合M。其中,head(mi)表示方法的头部文件,包含了方法名称和传递参数;pre(mi)表示使用方法mi前需要满足的前提条件,所有采用该方法的任务所传递的参数需保持一致;subTask(mi)表示将复合任务分解为子任务,以及执行子任务所使用的方法mi;Ep(mi)表示执行方法mi需要引入的外部计算,包括能源消耗估算和本体坐标时间转换两个独立的计算子程序。

状态转移函数δ可以表示为M×O→S,δ(s,o)表示在某个状态si下应用某个操作符oi的后继状态,有δ(si,oi)=si+1,δ(si+1,oi+1)=si+2。可知,不断利用方法m对任务网络中的复合任务进行分解,可以获得原子任务网络。规划问题的求解过程即一个任务不断分解的过程。

定义 4定义TCN为:

TCN=〈J,C〉

(4)

表示所有任务集合和事件间约束关系组成的有向加权图。以巡视器起点坐标为规划起点,目标点为终点,过程中经过的导航点可以将一个长周期的巡视探测任务划分为多个短周期的作业J0,J1,J2,…,Jn,构成TCN网络的节点;C在式(2)中已定义,表示外部约束条件集合,包括太阳高度角、通信链路、载波切换计划等。其中,时间信息隐含在事件之间的约束关系中。

利用TCN定义的作业见逻辑关系,可以获得有序的工作序列。一个HTN的规划解由初始网络TCN0分解得到,且动作序列〈a0,a1,…,an〉满足对应作业序列〈J0,J1,…,Jn〉在任务网络TCN上的状态一致性约束,规划结果是原子动作集合A的相关函数,且满足Π={ai,∀i∈N}。

定义 5状态受限事件:

I=〈S,A〉

(5)

式中:S为状态集合;A为动作集合。

状态受限事件可以表示多个活动事件之间的时态关系。以移动模式为例,状态受限事件包括盲走、自主移动、视觉测程、多电机移动和分离移动等,每个事件由动作和动作序列组成。在自主移动工作模式下,需要完成前障避障相机加电、前障避障相机分频参数设定、前障避障相机曝光行位置设定、前障避障相机自动曝光、陀螺零偏修正、火星车移动、转向轮回零设置、相机断电、正常退出等动作。当遥测结果判定满足制导、导航与控制(guidance, navigation and control, GNC)交出移动控制权且移动断电,即证明自主移动结束,可以转入下一个工作状态。

动作集合A=〈dura,Ta,Ea〉,dura表示动作的持续时间;Ta是a的开始时间;Ea是a在开始时间、结束时间的动作执行效果集合。每个动作都有一个非负的起始时间Ta和一个正实数的持续时间dura,并且采用了一个保守的动作模型,即:

(1) 所有的前提条件必须在动作的开始时间Ta为真;

(2) 不受动作本身影响的前提条件必须在动作的执行过程[Ta,Ta+dura]中全程为真;

(3) 效果在动作执行期间未定义,且仅保证在最后时间点Ta+dura为真。

这意味着,如果一个动作的某个前提或效果是另一个动作的某个前提或效果的否定,那么这两个动作无论如何都无法重叠执行。

如巡视器自主移动前需要进行陀螺零偏修正,定义为动作A1,完成该动作需要5 s,即dur1=5 s,在上一个动作完成后延时1 s启动,即启动时间为上一个动作完成后偏移Δt1=1 s;动作效果包括失效和正常两种情况,即Ea=[0,1]。则该动作正常执行的知识模型为A1=[5 s,+1 s,1]。

3 动态规划流程

HTN规划过程表达了复合任务与子任务之间的分解关系,以及系统状态转移的代价条件,并把求解搜索空间限定在不同规模的任务层级,有效地缩小了计算空间,提高了求解效率,可以解决较大规模的实际决策问题。

制定巡视器科学探测任务规划的流程如图2所示。

图2 动态规划流程Fig.2 Process of dynamic planning

步骤 1解析工程总体文件中所定义的工作模式,构建领域知识模型,定义工作模式活动顺序和相互间状态转移关系。

步骤 2依据状态转移条件δ进行工作模式间逻辑关系的推理,实现航天器在一个周期单元内的事件排序,形成任务定制文件。

通过对领域知识模型的分析可知,组成工作模式的动作序列是一类状态受限的事件。状态空间中从初始状态到达目标状态的路径是一个状态确定的解。在领域建模过程中,本文构建TCN任务约束网络,在节点属性中包含约束条件,因此在搜索过程中可以避免冗余路径。基于状态一致性的判定,状态空间可以拓展至所有节点,因此对于有限状态空间是完备的,避免了搜索失败的可能性。

本文采用前向剪枝策略的启发式搜索算法,TCN中每一个节点对应状态搜索空间的一个状态,每一条有向边对应一个状态转换条件,从当前路径出发进行前向搜索。

具体流程如算法1所示。

算法 1 基于前向剪枝策略的启发式搜索算法输入 任务集合输出 巡视器动作集合步骤 1 任务集合P中选择一个短周期作业J,作为任务约束网络的初始节点步骤 2 设置初始节点J初始状态和目标状态步骤 3 设置解集为空,即Π=0步骤 4 从初始节点J开始进行循环迭代搜索步骤 4.1 If 节点J所代表是一个原子动作 Then If 节点J的当前状态S满足状态转移条件 Then 开始下一个节点的状态判断,即S=S+δ(o×m) 把节点J包含的动作属性o,放入解集,即Π=Π+{o} 上述动作,完成领域模型D的约束传播 Else 搜索失败,跳出循环Else 跳至步骤4.2判读步骤 4.2 If 节点J是一个动作序列 Then 判读动作属性a、状态属性S是否满足状态转移条件。 If 条件为真,把动作序列{o0,o1,…,on}放入解集,进行网络节点信息更新。 Else 搜索失败,跳出循环Else 跳至步骤4.1判读

规划解是在不断地选择动作和状态转移的迭代中得到的。首先,判断作业是否为原子任务,当一个工作模式所包含的动作即可完成该作业,且满足目标状态,则认为该作业是不需要继续分解。算法获得局部规划解,并对当前巡视器中状态进行更新和重置。如果作业是非原子任务,则包含多个工作模式,进行使用局部最优搜索遍历分支,找到满足约束条件的动作序列。在一个事件集的约束网络中,多个工作模式可能出现冲突,冲突的原因包括未赋值参数冲突、违反参数约束冲突、未分配时间约束冲突、违反时间约束冲突、未分配预留项冲突、可耗尽资源冲突、不可耗尽资源冲突、状态需求冲突、状态转移冲突等。采用约束满足问题(constraint satisfaction problem, CSP)前向搜索算法进行循环迭代,直至冲突完全消解。如果冲突不能完全消解,则通过人机迭代的方式进行决策。将获得的工作模式序列放入结果集合中,并更新任务状态。进而获得巡视器在一个工作周期内的事件排序,即任务定制文件。

步骤 3动态事件分析与构建。

由于深空环境存在较大的未知性,很难准确地定性描述航天器在确定时刻的工况,需要处理较多的不确定性,包括太阳光压变化导致航天器空间引力场变化、深空热环境变化导致航天器内部元器件工作状态变化等。这种环境不确定性带来的状态空间的变化,可能导致既定的动作效果发生偏差。因此,需要引入动态规划及时进行纠正。

地面一般采用延时指令控制的遥操作模式,结合测控时间窗口生成一个周期单元的指令序列。以火星遥操作任务为例,把中继通信间隔作为周期单元,地面一次规划即生成一个火星日的延时指令序列,以确保火星车在无地面测控支持下可以完成既定任务[16]。在数传窗口对地下延时遥测、感知和探测数据,地面应用中心从工程和科学的角度进行作业执行效果研判,制定动态事件策略和下一个火星日的任务规划。

根据定制文件中对活动事件的安排,判断动态事件与全局时间点的时态关系,构建动态事件,实现新增事件的临时加入和实时更换。动态事件由虚拟事件和初始事件组成,无需调整原有事件间的时序逻辑,即可实现新增事件的临时加入和实时更换。采用虚拟指令的方式表示动态事件中的虚拟事件,虚拟指令仅作占位处理,不包含具体的指令内容,因此动作执行前后的状态空间保持一致,解决了状态一致性的衍生问题。

动态事件、虚拟事件与全局时间点的时态关系处理方法,详见第4节。

步骤 4按照时序关系,将事件逐级展开为有序指令集合,生成用于航天器任务规划控制的指令计划。其中,虚拟事件用虚拟指令替换,仅作占位处理,不包括具体的程控指令。由于虚拟事件没有影响初始事件之间的时序关系,因此原有状态空间未发生变化,并继承了初始事件的约束条件。

步骤 5地面操作人员通过人机交互的方式,确认是否有新增任务。如果有,则用新增事件替换虚拟事件,新增事件所对应的指令序列替代虚拟指令序列,生成调整后的指令计划;如果没有,则不改变指令计划。

4 动态事件的时态约束处理方法

Allen教授提出区间代数理论,事件之间包括13种常见的时态关系[28]。时间区间是一个由开始时间和结束时间组成的闭区间,为时态关系的推理提供了重要的数学工具。为精确描述事件之间的时态关系,以及更好地处理动态任务请求,本文把全局时间点概念引入Allen区间代数,用来表征事件、动态事件与全局时间点三者之间关系,拓展了时态约束关系的表示方法。本文沿用Allen所定义的时态关系符号,具体如表1所示。

表1 Allen区间代数定义的13种基本时态关系Table 1 13 basic tense relationships defined by Allen interval algebra

初始事件I与全局时间点T的时序逻辑判断,以及初始事件I、动态事件Id、虚拟事件Iv、全局时间点T的时序关系安排方法,描述如下:

(1) 如果I{<}T,动态事件和虚拟事件的安排需满足条件:I{di}Id&Id{f}T&Iv{f}T;

(2) 如果I{f}T,动态事件和虚拟事件的安排需满足条件:I{=}Id&Id{f}T&Iv=null;

(3) 如果I{di}T,动态事件和虚拟事件的安排需满足条件:I{di}Id&Id{di}T&Iv{di}T&I1{<}T&I2{>}T&I=I1+I2;

(4) 如果I{s}T,动态事件和虚拟事件的安排需满足条件:I{=}Id&Id{s}T&Iv=null;

(5) 如果I{>}T,动态事件和虚拟事件的安排需满足条件:I{di}Id&Id{s}T&Iv{s}T。

区间代数的拓展定义如表2所示。

表2 区间代数的拓展定义

5 仿真实验

以火星车一个火星日的活动事件安排为例进行方法验证。火星车遥操作任务规划根据火面环境、星历、地形图,以及火星车本体状态、工作能力等约束条件,形成工程任务和科学探测目标,制定在满足复杂约束条件下的作业定制文件。生成火星车在一个火星日内的移动、探测、感知、通信、太阳翼最优指向等行为序列和控制参数,最终输出完整的指令序列和控制策略。

假定巡视器当前所在位置坐标A,将其作为本次周期作业的起点,在地形图上人工指定出规划的目标点位置B,二者相距40 m,且地形地貌满足作业执行的条件。A点和B点之间安排10个过程探测点称之为导航点。

根据巡视器位置信息、测控跟踪条件、太阳高度角确定的光照信息,计算巡视器进出地面测控区间的时间,确定测控有效跟踪弧段。依据巡视器位置信息、有效跟踪弧段、星球表面地形原始数据等信息,对长周期内的全部探测点进行可达性评估,确定行驶路径,标定周期作业的起点位置和终点位置,确定TCN的起点和终点。最后,根据周期作业起点位置信息,确定作业初始状态S0=〈Q,C〉,Q表示巡视器本体相关的状态,包括主体坐标、天线指向、电量、太阳翼指向、偏航机构姿态、云台机构姿态、桅杆机构姿态、机械臂等;C表示外部约束条件集合,包括太阳高度角、通信链路、载波切换计划等,构建初始任务约束网络的起点。因此,一个HTN的规划解是周期作业内的一个动作序列〈a1,a2,…,an〉,满足TCN中节点状态的一致性判断,即δ(si,oi)=si+1,δ(si,oi+1)=si+2,i=0,1,…,n。

根据领域知识要求每个导航点均需要安排感知、数传和移动3种行为,而每个行为又都需要满足电量、测控跟踪条件等要求。根据工作模式的状态转换关系进行分析,获得在A点和B点之间的行为序列<充电,感知,移动,感知,进出测控区,数传,移动>。对工作模式进行动作展开,获得动作序列<太阳翼机构加电控制,±Y太阳翼调整对日指向,调整遥测工作模式,局部感知,移动参数设置,移动时载荷探测设置,陀螺零偏修正,…,移动断电>。

当日计划完成移动盲走,涉及到通信模式、移动模式两个状态受限的事件,需要完成两个状态受限事件,分别是事件I0:通信模式;事件I1:移动盲走模式。状态集合中用[0,1]表示成功、失败。

分析工作模式的逻辑关系,建立领域知识模型,如表3所示。

表3 火星某日的领域知识模型

形成初始定制文件为活动事件序列:I0{<}I1{m}I0。定义动作Ai包含ni条指令序列,表示为Ai={XLi_1,XLi_2,…,XLi_ni},对于单个动作,n=1;对于动作序列,n>1。动作集合中的“火星车移动”是由多个动作组成的动作序列,进行指令展开前需要进行动作分解,以对应到指令,如表4所示。

根据遥测结果判断在下一个飞控时间窗口,可以新增对地通信事件,对领域模型进行完善,如表5所示。

表4 动作序列指令展开

表5 动态规划领域模型

根据动态规划流程,更新定制文件,当日的活动事件序列为:I0{<}I1{m}I0{m}I2,输出的指令计划如下:

[XL0_1,XL0_2]{<}[XL11,XL12,XL13,XL141,XL1_4_2, XL1_4_3,XL1_4_4,XL1_4_5,XL1_5,XL1_6,XL1_7]{m} [XL0_2]{m}[XL2_1,XL2_2,XL2_3,XL2_4]

(6)

进行指令展开后插入事件代码、组帧标识、事件开始时刻和偏移量、发令方式等,即可通过遥测岗位上注航天器,完成动态规划流程。

6 结 论

本文针对深空探测飞控任务中的动态规划需求,系统地提出基于HTN的领域知识建模方法;基于任务不确定性分析,在工作模式与动作这两个层级之间,引入状态受限事件,用以精确表征多个动作序列之间的时态关系,完善了状态受限事件的建模方法;把全局时间点概念引入Allen区间代数,拓展了事件时态约束关系的表示方法;提出使用虚拟事件、虚拟指令表征动态任务的方法,解决了状态受限事件在动作执行前后状态一致性判定带来的衍生问题。

所提方法进一步完善了“首次火星探测任务”遥操作任务智能规划系统的功能,有效提高了巡视器遥操作的工作效能和地面中心进行事件处理的灵活性,为任务的圆满成功提供了技术支撑。