期望状态序列导向的深空探测器规划修复方法

陈 超,徐 瑞,李朝玉,朱圣英,梁子璇

(1.北京理工大学宇航学院,北京 100081；2.深空自主导航与控制工信部重点实验室,北京 100081)

0 引 言

作为探索其它天体上生命迹象、追溯太阳系起源的重要手段,深空探测一直是NASA、ESA以及中国、日本、印度等机构和国家航天发展的重点[1-5]。通过遥控遥测的方式,人类可以借助深空探测器获取大量有关地外天体的有价值信息[6-7]。然而,由于对深空环境认知不全、设备长时间运行导致的性能下降以及太阳风等难预测的突发事件,探测器的既定规划在执行中面临着实际状况与预期不符,进而导致任务目标无法实现的难题[8-9]。因此,在器地通信存在长时延、星蚀、日凌等客观事实下,探测器应具备自主重规划功能,以增强其自主应对故障的能力,提高任务回报。

重规划可分为完全重规划与规划修复两类[10]。其中,完全重规划放弃既定规划,重新决策出新的动作序列来完成任务目标。此时,可以利用现有的任务规划方法[11-13]实现完全重规划；而规划修复对既定规划进行修补来实现任务目标,一般通过改造现有规划器实现规划修复。虽然规划修复在理论上不一定比完全重规划简单[14],但大量的仿真实验表明,规划修复效率更高[15-17]。考虑到任务的时效性以及任务执行失败可能导致的故障迅速蔓延,深空探测器应优先选择规划修复方法应对突发事件。

现有的规划修复方法根据采用的修复策略,可分为规则匹配型、局部调整型、删除/求精型、状态转移型以及构造新问题型五类[10]。由于空间环境的不确知性,通过提前设想故障类型并人为给出解决方案的规则匹配型规划修复方法,无法应对实际执行中的各种突发情况[18]。Bechon等[19]依次移除动作后再利用原有规划方法来寻找机器人任务执行失败的解决方案,本质上是初始状态不断变化下的完全重规划,效率有待进一步提高；Soubaras等[20]将规划修复问题转化成柔性作业车间调度问题,并提出15数码算法,能够给出水下航行器群中部分个体失效时的规划方案,但是应对突发事件类型有限。Zheng等[21]通过删除、注入、修改参数等方式,调用其提出的混合动态变化遗传算法,来给出不同突发事件下多卫星系统的观测通信方案,但是对动作时序的讨论少。Guzman等[22]基于状态回退机制提出了响应式规划方法,可以快速给出下一个动作或者一段特定时间内的动作,但处理的动作对象是瞬时、串行的。Scala等[23]基于火星巡视器动作模式的多样性,利用约束可满足理论,提出了基于动作模式重构的规划修复方法,却并未考虑能源消耗的问题。Chen等[24]从能源和动作逻辑两个角度分别提出了全局能源诊断及修复方法、小偏差规划修复方法,并结合二者提出了响应式规划修复策略,但是修复时采用盲搜策略,效率有待进一步提高。

考虑深空探测器多系统耦合并行、活动持续且消耗能源,同时探测任务多时间窗口的特点,本文采用PDDL2.2[25](Planning domain definition language 2.2)对深空探测器任务规划进行建模,为获取初始规划结果以及后续规划修复做好准备。针对环境不确知、设备故障及外部突发事件引起的既定规划失效问题,结合动作的完成情况,本文在前向状态坞概念的基础上,提出了逻辑与能源混合的期望状态序列计算方法,为规划修复提供可选目标。在此基础上,提出了能源补给优先的规划修复策略,并设计了状态转移路径搜索算法。最后以火星环绕器为例,通过仿真测试,验证了本文方法的有效性和合理性。

1 规划修复问题及建模方法

规划修复是在既定规划基础上的再决策。而既定规划是在执行环境的先验知识条件下,通过合理挑选、安排活动的顺序并处理好时间、能源与活动之间的约束关系,进行综合决策后给出的规划结果。深空探测器的既定规划可以在人工给出后通过地面站上传,也可以自主生成,其定义如下：

定义1.一个规划结果P是一列时间有序的实例化动作集合。对于P中的任意元素a,可以形式化描述为a=。其中,ta表示动作a的执行安排时间,na表示a的名称,pa表示a的具体参数,da表示a的持续时间。

然而,深空环境不确知,导致先验知识不足,既定规划难以正确执行。同时,设备故障、太阳风暴等突发事件导致执行异常,既定规划难以保证探测任务的成功。因此,在深空探测器的既定规划失效时,有必要研究规划修复问题及其解决方法。

定义2.一个规划修复问题Π是一个六元组,即Π=。其中,P是既定规划,IΠ表示执行异常时深空探测器的状态,GP则描述既定规划P中仍未实现的任务目标；F描述探测器状态的逻辑命题,其取值为true或false；V表示探测器状态中的数值变量及其取值范围；操作O包含了改变探测器状态的方式及效果。规划修复问题就是在F和V的约束下,如何从O中找到一系列操作并实例化,使得探测器能够从状态IΠ到达既定规划P中的任务目标状态GP。

为了形式化描述深空探测器的规划修复问题并进行求解,考虑到探测任务的时间约束,采用支持时间窗口表达的规划领域定义语言PDDL2.2[25]进行建模。

PDDL2.2采用一阶逻辑,通过谓词的形式将逻辑与数值相结合,为后续的任务规划及规划修复奠定模型基础。它将任务分成领域、问题两部分进行描述。其中,领域主要描述探测器的行为能力及相关约束,例如数传操作及其能源需求、指向约束、时间窗口约束、持续时间约束等；问题主要描述具体的探测任务,包括探测器的初始状态和任务目标,例如获取某区域的光学影像并传回地面。而在领域和问题的描述中,操作和时间窗口的表示至关重要。

对于操作,其实例化后就是动作。操作中的任意一个元素都可以表示成o=,其中no表示该操作的名称,po表示其参数,do表示其持续时间,Pre描述其前提条件,Eff则表示其效果。在PDDL2.2中,一个持续动作被转化成开始(at start)、中间(over all)、结束(at end)三部分进行描述。例如,对地数传操作,参数包含可用的数传窗口、使用的数传天线及其工作模式,以及要传输的目标影像及其类型；持续时间难以估计,因此使用函数表示方法,由外部确定；开始前提包括探测器指向地球、数传天线可用且已打开、已经获得目标影像并且数传窗口可用；开始效果为数传天线进入工作状态；中间的前提条件为探测器继续指向地球、剩余存储可用、数传窗口可用且星上能源充足；没有中间的效果和结束的前提条件；结束效果为数传天线闲置、目标影像成功被传输、剩余存储减小、可用存储增加、星上可用能源降低。其中,操作消耗的能源、持续时间等难以提前确定的量都采用函数形式由外部输入确定。

对于时间窗口,采用由一对相反谓词和不同时刻组成的时间初始化文字表示。例如,(at 120(image_active w1probe))表示了探测器在120 s可以进行观测,(at 180 (not (image_active w1probe)))则表示探测器在180 s无法观测。由此,两者结合,就可以表示一个从120～180 s的观测窗口。

在建模过程中,主要从顶层考虑探测器的执行能力,设计相应的操作,并加入时间、能源、参数等相关约束,建立探测器领域模型。同时着眼于探测任务目标,输入不同阶段探测器的初始状态和任务目标,形成探测器问题模型。领域模型和问题模型经过不断测试、确认没有错误后,作为自动规划器的输入,调用智能规划算法,输出任务规划方案,为后续的探测器执行和规划修复提供依据。

2 期望状态序列计算

如图1所示,探测器的既定规划在实际执行时,若异常导致规划失效,其动作根据安排的发生时刻与当前执行时刻的相对关系,可分为异常出现前已经执行完成的部分以及异常出现后未执行完成的部分。由于探测器的活动具有一定的持续时间,既定规划中未执行完成的部分活动可能已经发生但未结束(如图1中的a1～a3,称为未完成执行的动作),而其它活动仍未开始(如图1中的b1～b8,称为待执行的动作)。已有的规划修复方法大都忽略这一事实,而选择放弃未完成执行的动作并寻找新的动作序列以连接当前异常状态与部分待执行的动作,从而丢失部分有价值的参考信息,在一定程度上降低了规划修复效率。

图1 根据动作执行完成情况划分后的既定规划Fig.1 A pre-designed plan after division according to the completion of action execution

因此,从既定规划中提取未完成执行动作的期望效果、待执行动作的期望前提,组成期望状态集合,并按照期望效果在前、期望前提按动作发生顺序排列的方式进行组合,构成期望状态序列。这样做有以下优势：1)相对于探测器庞杂的状态信息,期望状态只包含了动作的必要前提/效果,从而缩小了搜索空间大小；2)相较于任务目标,期望状态序列为规划修复提供了更容易达成的目标,从而使得规划修复能够快速给出修复方案；3)由于并行动作之间的不互斥,待执行的动作可以另安排执行时间而不产生冲突,从而使得探测器能够在有限的时间内集中处理当前未完成执行动作的执行失效问题,进一步缩小了搜索空间大小。为有效管理执行过程中探测器的状态信息以及既定规划中的期望状态序列信息,借用前向状态坞[24]这一概念,提出逻辑与能源混合的期望状态计算方法,为后续的规划修复搜索提供子目标。

2.1 前向状态坞

探测器的既定规划是一组时间有序的动作集合。图2所示描述了探测器观测某区域并将观测结果传回地面这一任务的既定规划。其动作根据所属的子系统,可以分别被纳入姿态系统、相机以及数传天线三条时间线上。不同时间线上的动作在同一空时间线上映射,可转换为一组时间有序的状态队列(如图2中的{S1,…,S6})。执行过程中,探测器通过动作的连续执行,实现不同状态之间的转移,直至完成任务目标。当突发事件发生时,实际执行状态与规划预期状态不一致,导致既定规划无法适用于当前情形。此时,由图1可知,存在探测器的感知状态、未完成执行动作、待执行动作,以及由动作导出的多个期望状态信息,为了便于在规划修复时及时给出可用的修复目标,高效管理状态,给出前向状态坞的概念,其定义如下：

定义3.一个前向状态坞Rf是一个七元组,表示成：Rf=。其中,t表示当前的执行时刻;Acur表示当前正在执行的动作集合;Scur表示当前探测器的感知状态;Scexp表示当前期望的状态;Anext表示即将执行的动作集合;Snexp表示Anext执行前的期望前提;Ei表示已经执行但未结束的动作效果集合;Eo表示观测到、待发生的突发事件。

如图2所示,前向状态坞是一段时间区间内的状态集合。其成员可分为两大类：当前执行时刻包含的相关信息(包括Acur、Scur、Scexp),以及未来一段时间内的相关信息(包括Anext、Snexp和Ei、Eo)。已经执行完成的动作,其效果通过状态转移归结到探测器的当前状态中,从而可以被忽略。前向状态坞总是从动作的发生时刻或者执行异常的时刻开始,而其终端由于动作持续并行的影响,无法简单地根据时刻确定。例如,图1对应的前向状态坞中,Acur包含a1～a3,Anext包含b1、b2,不包含Snexp以及Eo。在正常执行时,其两端会随着动作的不断执行而随时间向前移动,并更新成员信息；在执行失败时,其起始端固定在失败时刻,而其终端随着规划修复的不断进行,逐渐向前扩展,直至找到修复方案。

2.2 逻辑与能源混合的期望状态计算方法

期望状态是在理想状况下,既定规划在各个执行时刻想要实现的状态。在前向状态坞中,期望状态序列为规划修复提供修复目标,包括已开始执行但未结束动作的期望状态Ei以及待执行动作发生的期望状态Snexp,可通过式(1)的状态回退函数Γ(S,a)计算。而当前的期望状态Scexp是部分待执行动作的必要前提,因此可以看成是Snexp的特殊情况。

(1)

图3 期望状态序列计算流程Fig.3 Diagram of expected state sequence calculation

图4 不同的期望状态计算过程示意图Fig.4 Diagram of the different expected state calculation process

值得注意的是,在使用PDDL2.2建立的深空探测器模型中,操作的前提和效果根据其持续时间被分成了开始、中间和结束三部分,而其实际效果又都在结束时体现。因此,在收集既定规划中动作的效果时,直接提取动作的结束效果；在收集动作的前提时,由于动作的连续计算,一个动作结束时的前提可能由自身开始时的效果提供,也可能被之前发生的其它动作提供。因此,自我满足的这部分被剔除,以避免被误认为需要额外动作来提供,从而减少不必要的求解时间。

3 基于期望状态序列的规划修复方法

探测器的既定规划具有动作持续、并行、消耗能源的特点,在前向状态坞的支持下,可统一映射到同一空时间线上,从而成为一组时间有序的状态点,而逻辑与能源(用数值体现)在状态点中可以体现。因此,规划修复问题可转化为从当前状态到期望状态序列的可行状态转移路径搜索问题。在问题求解过程中,提出能源修复与逻辑修复分离、能源补给优先的基于期望状态序列的规划修复方法,并进一步提出状态转移路径搜索算法。该规划修复方法具有以下优势：1)深空探测器的规划修复是逻辑与能源耦合的问题,优先补给能源,将能源修复与逻辑修复分离,可以在一定程度上降低整个规划修复问题的求解难度,减少逻辑修复过程中因能源约束不满足而导致的回溯次数,从而提高规划修复求解效率；2)利用期望状态序列进行修复,可以充分利用既定规划中的信息,有序地决策出修复方案；3)深空探测器的任务执行是个连续的过程,按照期望状态序列的顺序先修复未完成执行的动作,可以更及时地处理突发事件,降低影响程度,特别是在着陆下降等紧急任务中,可以做出快速响应。

3.1 能源补给优先的规划修复策略

探测器活动的顺利执行需要充足的能源支持,而修复方案可能会额外抢占既定规划中预分配的能源份额。因此,为了简化修复过程中局部逻辑冲突与全局能源冲突的耦合计算,在修复时优先对低可再生能源进行补给。如探测器通过帆板对日定向可以实现电能补给,在一定程度上能够减少因电能供给不足而导致的操作选取受限,从而降低规划修复问题求解难度。因此,设计能源补给优先的规划修复策略,将能源修复与逻辑修复分离,如图5所示。

图5 基于期望状态序列的规划修复方法流程Fig.5 Schematic diagram of the plan repair method based on expected state sequence

能源补给时,在可再生能源首次不足之前,利用补给-复原动作流[24](即在待执行动作前尝试插入能源补给动作进行充能以及状态回归动作将探测器状态恢复至待执行动作的期望状态),比较充能后富余的能源大小,从而确定最优的补给时刻及对应的能源补给方案。若能源不足以支撑既定规划中剩余动作的实施,且该能源没有补给方案,规划修复失败。此时,探测器进入安全模式,等待地面操作人员发现问题并上传有效的解决方案。否则,将能源补给方案与既定规划进行融合,并更新前向状态坞中的各个元素,从而更新期望状态序列。

在补充明显不足的可再生能源后,以期望状态序列中的元素为修复目标,搜索探测器当前状态到期望状态的可行路径。在该过程中,遵循已发生动作优先、待执行动作其次的修复顺序。只有当前向状态坞中的所有期望状态都不可达时,才会启用重规划方法,直接搜索到达任务目标的可行解。对于已发生动作,其期望状态是最晚结束时刻时的预期效果集合,如图4中的Ei。因此,其修复过程就是在找到一条从Scur到Ei的可行路径后,将修复方案与既定规划融合、生成新的执行方案。若不存在这样的解,进入待执行动作的修复。对于待执行动作,其期望状态是动作发生的预期条件,是一段时间内离散分布的状态点,随着前向状态坞的不断更新而不断变化。因此,其修复过程需要先根据期望状态中的逻辑条件及相关约束在探测器当前状态下满足的情况,分析、判断既定规划失效的原因,确定期望状态的时刻,然后搜索一条Scur到Snexp的可行路径。若搜索失败,尝试寻找到达下一个期望状态的路径,直至遍历整个既定规划。若整个期望状态序列都不可达,调用规划算法进行完全重规划。

值得注意的是,即使优先补给不足的能源,在逻辑修复时,仍有可能因为修复序列所包含的动作消耗能源总量太大而再次出现能源不足的问题。此时,本规划修复策略直接舍弃已有的搜索步骤,并直接以下一个紧邻的期望状态为目标进行新一轮修复过程。

3.2 状态转移路径搜索算法

在能源补给优先的规划修复策略中,可行状态转移路径的搜索是解决规划修复问题的关键。搜索时,本文采用最佳优先搜索算法确定节点的访问顺序,并修改现有的时间松弛规划图[26](Temporal relaxed planning graph,TRPG)启发式来评价节点,优先扩展评价值最高的节点。如图6所示,搜索过程中,将逻辑前提和数值前提在上一状态均得到满足的动作加以应用,实现状态转移。在转移过程中,通过简单时间约束网络和线性规划技术,对时间、能源约束进行推理,若发现时间窗口、能源总量等约束被破坏的情况,则进行回溯。重复该过程,直至找出一个可行的修复方案。

图6 状态转移路径搜索算法流程Fig.6 Procedure of the state transition path search algorithm

在整个搜索过程中,TRPG启发式能对待扩展节点的优劣进行评价,从而指导搜索方向,提高规划修复的搜索效率。如图7所示,TRPG忽略动作的删除效果、扩大数值效果(若动作的效果是增加/删除某类型能源值,则TRPG在下一事实层中直接将该类型能源增加/减小该能源的最大值/最小值)、并且将数值前提简化为大于/大于等于两种类型,采用事实层和动作层交替的框架向前扩展。其中,每个事实层和动作层都与对应事实成立的时刻、动作发生的时刻绑定。TRPG启发式则通过统计初始状态层到达目标状态层的动作序列中动作总数,给出启发式估计值。与规划中的功能一样,TRPG启发式也可以用于规划修复[27],为规划修复搜索提供目标距离估计和病态节点识别。

图7 时间松弛规划图示意图Fig.7 Illustration of temporal relaxed planning graph

在搜索过程中,TRPG启发式被多次调用,并且每次被调用时的待评估状态和目标状态都不尽相同。因此,为了获得准确的启发式值,在修复搜索过程中使用TRPG时需注意以下几条：

1)初始状态的改变。与原TRPG启发式中初始状态为执行前开始规划的状态不同,规划修复中的初始状态为计划执行失败时探测器的感知状态。但是考虑到前向状态坞中,在该状态下,部分动作已经开始执行但未结束(其效果被收入Ei之中),且被观测到的突发事件(Eo)将要发生,除了将当前探测器感知的状态置为TRPG启发式的初始状态外,为了充分利用既定规划中的信息,同时不遗漏新的执行环境,Ei和Eo都应被纳入到前向状态坞中,为后续的规划修复搜索分别提供修复目标和限制条件；

2)目标状态的改变。与原TRPG中固定的任务目标不同,规划修复中的目标可以是前向状态坞中任意一个可达的期望状态,因此规划修复目标是可变的。利用第2.2节中的期望状态序列计算方法可以提取不同时刻的规划修复目标,包括逻辑目标与数值目标；

3)动作数值部分的重新计算。由于PDDL 2.2支持的模型是离散的,动作的逻辑部分在TRPG构建后几乎保持不变,而数值部分由于动作对能源的依赖及生产而不断变化。因此,为了获取更准确的节点评价值,在每次更新规划修复目标状态且利用TRPG启发式估计目标距离时,数值部分需要重新计算,即重新计算动作的数值效果及其持续时间。

4 数值仿真

为了检验本文提出的基于期望状态序列的深空探测器规划修复方法(以下用pr-e2s指代该方法)的有效性,以火星环绕器这类多时间窗口任务的对象为例,对其建模并进行数值仿真。

4.1 火星环绕器建模

规划修复是在约束条件下对探测器自身能力的充分再利用。考虑到环绕器在探测过程中,利用环火轨道实现全球探测和指定区域的观测,实现火星表面形貌、土壤特性、物质成分等的探测,并将所获得的数据传回地面,以建立火星总体性和全局性的科学认知[28]。因此,在进行规划修复前,设计火星环绕器的能力如下：

1)搭载相机和天线这两类设备,共四件。各自所支持的功能/模式见表1,状态包含打开、工作、关闭等；

表1 火星环绕器的主要设备及其功能Table 1 Main devices of the Mars orbiter and their functions

2)主要操作包括观测、数传、充电以及姿态机动等,如表2所示。各操作(充电操作除外)均消耗一定电能。

表2 火星环绕器的主要操作及其含义Table 2 Main operations of the Mars orbiter and their meaning

设置仿真初始条件如表3所示：相机与天线两类设备均处于关机状态,环绕器初始时指向太阳,保持+Z轴对日定向；星上存储总量为1000个单位,当前没有存储任何数据；星上电池容量为800个单位,当前电量为400个单位；对地数传速率为高速每秒20个单位,低速每秒10个单位；存在2个观测窗口以及2个数传窗口。

表3 火星环绕器初始状态设置Table 3 Initial state setting of the Mars Orbiter

设置仿真任务目标如表4所示：将g3区域的热成像图和光学成像图、g4区域的热成像图传回地面。

表4 火星环绕器的任务目标Table 4 Mission goals of the Mars Orbiter

采用PDDL 2.2建模语言,分别构建火星环绕器的领域模型和问题模型后,调用POPF2规划器[29],给出规划结果如图8所示。图8描述了探测器的姿态机动过程、相机和天线等各星载设备的工作时间和对应的动作,以及星上电能大小和存储值随时间的变化,共包含20个动作,构成表4任务目标的既定规划,为探测器的任务执行提供依据,也为后续的规划修复方法提供输入。

图8 深空探测器任务规划结果Fig.8 Mission plan result of the Mars orbiter

4.2 规划修复数值仿真结果及分析

图8中的既定规划包含20个动作,涉及4项载荷设备的活动、电能和存储这2种能源的消耗与补充,以及多个观测时间窗口和数传时间窗口的时间限制。在实际执行出错时,如何在限定的电能总量和存储总额的能源限制条件下,快速且合理地挑选活动并修改既定规划,以满足逻辑约束、能源约束、时间窗口约束等约束,使得环绕器能够继续完成任务,是规划修复面临的最大问题。

对于环境不确知、外部突发事件及自身设备故障等造成的既定规划执行失败的问题,采用事件的形式对其进行描述,即E=〈t,e〉。其中,E表示事件,t表示事件发生的时刻,e表示事件的具体内涵。例如E=〈10.5,(not (camera_calibrated cam))〉表示在t=10.5的时候,相机未校准。由此,结合探测器动作执行的特点,采取事件的形式,在不同的执行时刻注入逻辑约束不满足、能源供给不足等类型故障,来模拟探测器在执行过程中可能遇到的突发事件。

本文提出的方法pr-e2s在POPF2规划器上实现。针对图8的既定规划,本文共注入了30组故障,在配备Xeon(R)E5-2698 v3 @ 2.30 GHz CPU和12 GB内存的服务器上,测试本文方法的性能表现,并与第4届智能规划大赛表现最佳的规划器LPG-td[30]在同平台下进行对比。每次测试设置了10分钟的运算时长限制。测试结果如图9、图10所示。

图9 程序运行耗时结果对比(1)耗时结果都是通过程序运行三次后取平均值得到；测试问题上若无耗时数据点,说明该问题用该方法无法求解。Fig.9 Comparison of CPU time results

图10 扩展节点数对比(2)无法获取LPG-td的源代码(https://lpg.unibs.it/lpg/),因此无法输出其扩展节点数。Fig.10 Comparison of the number of expansion nodes

具体来说,测试问题1～15针对表3的初始状态设置,问题16～30针对图8所示既定规划的中间、结束部分设置,以此说明本文方法在不同执行阶段的适用性。其中,问题1～5、问题16～20是由逻辑不满足引起的执行失败,问题6～10、问题21～25是由能源不足引起的执行失败,问题11～15、问题26～30是由逻辑约束和能源约束均不满足引起的执行失败,以此说明本文方法对不同失败类别原因的适应性。

统计三种方法成功求解问题的数目,结果见表5。可以看出,本文方法能够应对更多的突发事件。针对部分测试问题,其它方法无法求解而本文的规划修复方法却能快速解决,可能存在以下几个原因：

表5 成功率对比Table 5 Comparison of success rate

1)在既定规划执行前期,星载能源处于低水平而实现任务目标仍需要探测器执行大量活动。此时,其它方法需要进行多次回溯,在逻辑约束与能源约束同时满足的要求下扩展更多节点,导致运行时长超过最大时长限制；而规划修复只需满足既定规划中未执行动作的期望条件。相对于其它方法的搜索耗时,规划修复搜索空间小,目标距离短,从而能够快速找到修复方案；

2)在既定规划执行后期,存在固定的观测窗口和数传窗口的时间限制。此时,其它方法针对未实现的任务目标,面临着活动持续时间长而时间窗口短的矛盾,活动的选取和调度受到制约；而规划修复针对前向状态坞中的期望状态,相较于任务目标,修复目标距离更短,从而能够更容易快速找到修补动作,通过与待执行动作的融合,生成完整的修复方案。

从图9可以看出,本文方法能够在1 s以内求解所有的规划修复问题,且平均求解时间低于POPF2和LPG-td方法。对于这30个测试问题,本文方法的平均运算耗时为0.03415 s,是POPF2(12.89125 s)的0.265%,是LPG-td(9.27196 s)的0.368%。而在18、19、20这三个问题上,本文方法耗时略长于LPG-td方法。造成该现象的原因是搜索算法的不同：本文采用最佳优先搜索算法,而LPG-td采用带有概率选择下一扩展节点的Walkplan算法[30],在相同的问题下,LPG-td更容易跳出局部最优。

从图10可以看出,本文方法扩展的节点数远远低于POPF2,且能够额外解决一些问题。对于这30个测试问题,本文方法的平均扩展节点数为16.2个,是POPF2(1919.2个)的0.844%。

因此,可以得出结论：相较于其它方法而言,本文提出的基于期望状态序列的深空探测器规划修复方法能够更快、更好地解决探测器的规划修复问题。

5 结 论

针对深空环境不确知、外部突发事件及自身设备故障等引起的探测器既定规划执行失败问题,结合活动持续、并行、消耗能源的特点,本文提出了基于期望状态序列的深空探测器规划修复方法。该方法利用前向状态坞将既定规划中持续、并行的动作转化为一组时间有序的状态点,并通过期望状态的计算将逻辑与能源包含在状态点中,为后续规划修复提供子目标,并将规划修复问题转化为状态转移路径搜索问题。本文主要创新点如下：1)根据既定规划中动作的执行完成情况,提出了逻辑与能源混合的期望状态序列计算方法,能够计算出未完成执行动作的期望效果和待执行动作的期望前提,为规划修复提供可选修复目标；2)提出了将能源修复与逻辑修复分离的能源补给优先规划修复策略,不仅在一定程度上降低了规划修复问题求解的难度,而且使探测器能够及时自主应对突发事件；3)结合时间松弛规划图启发式,设计了状态转移路径搜索算法,削减搜索空间大小,提高修复效率；4)基于PDDL2.2设计了火星环绕器任务模型,并通过数值仿真验证了本文方法的有效性和合理性,可以为深空探测器自主应对突发事件提供技术支持。