一种基于时标状态的启发式航天器任务规划算法

李朝玉，徐瑞

(1.北京理工大学 深空探测技术研究所，北京 100081；2.飞行器动力学与控制教育部重点实验室，北京 100081)

一种基于时标状态的启发式航天器任务规划算法

李朝玉1，2，徐瑞1，2

(1.北京理工大学 深空探测技术研究所，北京 100081；2.飞行器动力学与控制教育部重点实验室，北京 100081)

深空探测领域对实时性要求较高，在较短时间内找到规划解是深空探测自主任务规划中的一个要求，运用启发式规划算法是达到该要求的方法之一。而深空探测自主任务规划的另外一个特点是需要处理持续动作和数值信息。针对深空探测任务特点，采用规划领域定义语言PDDL，建立深空探测领域中知识模型，描述操作中遇到的时间与资源约束；随后应用以条件数为代价的启发式搜索方法对深空探测规划问题进行求解，并将其与TFD规划器中以动作时间为代价的上下文增强累加启发式搜索方法得到的结果进行对比，得出以条件数为代价的启发式搜索方法在搜索速度方面效果更佳，满足深空探测自主规划任务实时性要求。

深空探测；启发式；持续动作；数值

0 引 言

深空探测领域对实时性要求较高，在较短时间内找到规划解是深空探测自主任务规划中的一个要求。近些年，规划领域蓬勃发展，规划效率不断提高，有很多具有发展前景的规划方法出现，而启发式搜索方法就是其中之一。这种方法的中心思想就是在搜索过程中运用启发式信息引导搜索向希望的节点进行，直至找到目标节点为止。在深空探测自主任务规划中运用启发式信息进行搜索会减少搜索时间，大大提高产生规划解的效率[1]。

深空探测中约束复杂，任务执行必须精准，运用启发式过程中不宜过多地进行放松；与此同时，探测器运行速度快，有时遇到观测的现象时需要能够较快产生规划解，因此探测器自主任务规划系统要求具有较高的搜索速度，寻找一种快速高效的启发式显得尤为重要[2]。起初设计启发式时，对时间和数值方面没有考虑，深空探测领域中时间信息和数值量都是无法避免的，如电量、存储量等[3]。因此，当引进持续动作和数值量后，必须对启发式进行改进，才能用于深空探测中的时间和数值规划[4-5]。

本文针对深空探测任务要求规划解质量高、搜索速度快的特点，在TFD规划器中采用的以动作时间为代价的上下文增强累加启发式[6]基础上，对代价计算方法进行改进，设计了一种基于时标状态的启发式规划算法，该算法以条件数为代价，以达到对时间和数值信息的处理和对搜索过程的快速引导。应用到深空探测领域，一定程度上能够提高实时处理问题的能力。

1 深空探测器自主任务规划模型

用传统的离散动作表示深空任务中的动作已经无法解决实际问题，因此需要采用持续动作，即用一定的值表示动作执行时间。此外，还需考虑动作与动作间的并行性，以此可减少执行任务的完成时间，提高效率。

对于深空探测任务来说，探测器进入接近段后，速度非常快，姿态轨道等的调整很频繁，因此对实时性要求非常高[7]。因此本文以此阶段为例，采用规划领域定义语言PDDL[8]对其进行描述建模，并对其进行求解。不仅能表示任务的持续时间和约束， 还利于后面规划算法对时间进行处理。

1.1 领域文件的建立

深空探测器天体探测接近段中，涉及到的动作有转向、校准相机、打开相机、拍照、关闭相机、下传数据等活动。下面将对接近段任务进行领域建模。

建模过程中，包括类型、谓词、函数以及持续动作的说明[9]。其中，谓词指深空探测器中各个对象的属性，具有一定的取值范围；函数则表示动作之间的转换；持续动作的说明中则包含了动作涉及的参数，持续时间，需要满足的开始条件、持续条件、结束条件以及动作产生的效果[10]。在描述过程中，会有数值量的出现，这些数值量则表示各个活动所涉及到的数值变量和资源情况，如存储器的存储空间、燃料使用情况、电量储存量等[11]。

表1为该任务建模中所涉及的活动及其含义描述。领域文件中对相机系统、姿态系统、导航系统、推进系统和通信系统进行建模，共15个活动，且文件中对每个活动的持续时间、参数、开始条件和结束效果都作了定义。

表1 深空探测器小天体接近段任务模型的活动及其含义描述

Table 1 Description of activities in mission model of the deep space explorer for the closing phase to a small body

活动名称含义Cam＿Ready准备好相机Cam＿Open打开相机Cam＿Takephoto相机拍照Cam＿Close关闭相机ATT＿Maneuver探测器转向Nav＿prepare准备导航Nav＿process导航过程Prop＿warmingup推进器预热Prop＿startup推进器启动Prop＿thrust推进器进行推进Prop＿closing推进器关闭Com＿system＿prepare数据传递系统准备Com＿uplink上传数据Com＿downlink下传数据Com＿close数据传递系统关闭

1.2 问题文件的建立

问题文件用于描述探测任务的对象、初始状态以及任务目标，也是地面工作者操作探测器的接口。本文所建立的问题模型包括相机、导航系统、推进系统、探测器指向以及探测目标。拍照时，相机需要对准探测目标进行拍照。

图1表示出该探测任务的初始状态。在初始状态中，相机cam1处于闲置关闭状态；剩余电量为800 W，剩余数据储存量为500 MB，推进剂剩余500 g；推进机prop1预热时间为25 s，推进时间为10 s；数据传输准备时间需要20 s，数据上传时间需要35 s，下传时间需要50 s；探测器开始指向为初始方向Initial。此次设定的科学观测任务目标为：利用相机cam1对小天体asteroid1和恒星star1进行拍照。具体描述如图2所示。

图1 深空探测器小天体接近段任务的初始状态

Fig.1 Initial states of the deep space explorer in the closing phase to a small body

图2 深空探测器小天体接近段的任务目标

Fig.2 Description of goals of the deep space explorer

2 基于时标状态的启发式规划算法

早期的规划方法并不能处理具有连续动作的规划问题，因此启发式函数也只是对瞬间的动作节点进行计算。然而，深空探测任务中，动作都具有持续时间，传统的启发式处理方法已经不再适用。随着规划技术的发展，产生了可对连续动作和数值量进行处理计算的启发式，启发式搜索方法也得到了相应的改进，以适应现实问题的需要。本文设计一种以条件数为代价的上下文增强累加启发式， 达到对连读动作和数值量处理的目的。

2.1 持续动作和数值处理方法

对启发式的改进涉及到两个方面：将持续动作转换为操作，使之可以用来进行启发式的计算；对规划任务中的数值部分进行处理。在这里采用的方法是引入瞬时动作(instant actions)处理持续动作部分，估计改变比较变量值的代价处理数值部分[12]。

1)瞬时动作

为了处理持续动作，需要引入瞬时动作的概念来估计时态任务。瞬时动作又可分为四部分：压缩动作、开始动作、等待动作、由逻辑公理导出的瞬时动作。

(1)压缩动作

主要是通过对原时态规划任务中的条件与效果进行简化处理。压缩条件三元组， 一个瞬时动作的压缩逻辑效果表示为

其中：o为动作；v和v′为变量；w和w′为变量可取值；z为部分状态。

压缩的数值效果表示为：o:z→v∘v′(∘为符号+=，-=，*=，/=，:=)。

每个瞬时动作都分配给一个代价cost(o)，这个代价可能是真实的值或者数值变量。在不同的代价计算公式中，cost(o)计算的方法也是不同的。

压缩动作图例如图3所示。

图3 压缩动作图例Fig.3 Compressive actions

压缩动作转换后为：

条件：cond={a，b}； 效果：eff={c，d，d}

(2)开始动作

将持续动作进行压缩，导致忽略了持续动作执行过程中到达的中间状态的启发式值，因此引入开始动作。它包含持续动作的开始效果，以及压缩动作所包含的所有条件，即开始、持续和结束条件。与压缩动作的唯一不同是没有结束效果。开始动作代价计算：原始持续操作的持续时间。

(3)等待动作

当启发式计算需要用到结束效果时，就用压缩动作，因为开始动作没有结束效果。而当持续动作已经在时标状态S下运行了，则认为动作的条件已经得到了满足，此时引入等待动作。每个调度效果<Δt，c↔，c┤，e>中增加一个等待动作o，其中效果为effect→e，代价根据采用的方法计算。图4为等待动作图例。

图4 等待动作图例Fig.4 Waiting actions

等待动作转换为：

条件：cond=∅； 效果：eff={goal}

(4)由逻辑公理导出的瞬时动作

最后一组瞬时动作是从逻辑公理导出的，例如公理z→v=w可得到瞬时动作o，其代价cost(o)=0，效果为{v=w′，z→v=w|w′∈Dv{w}}。

2)数值信息处理

数值方面是指有些变量需要用数值表示，例如深空探测器的电量是有一定值的，如果按以前没有数值量时的情况，只能用0和1表示没电还是有电，这样就无法表示实际用电量。

在变量处理过程中，数值量没有出现在条件或者目标当中。因此通过估计改变比较变量需要的代价是一种处理数值量的有效方法。

考虑未满足条件v=w，其中v∈Vc是比较变量，w∈{true，false}，v=v′▷◁0是相关的比较公理；数值变量v′代表数值流集合F(v)中的算术表达式，集合F(v)是输入度为0的变量的集合，也称为v′的祖先。来自于瞬时动作的规则集合influencing(v)={o:z→v1∘v2|v1∈F(v)}作用在变量上，接下来，就从influencing(v)中选择对原子有积极效应的规则。

为了表明比较变量的变化情况，需要定义新的符号，如式(1)所示

(1)

在扩展状态s中，如果式(1)成立，influencing(v)中的规则o:z→v1∘v2是可以改变变量v的值w(v=v′▷◁0是与之相关的比较公理)。

(2)

其中，s[v1∘v2]是与s相似的状态，但是其v1∘v2使得变量值更新和一个子序列的公理更新。

2.2 以条件数为代价的上下文增强累加启发式

由于TFD规划器中以动作时间为代价的上下文增强累加启发式计算较复杂，因此对代价计算方法进行简单化，尽量能够减小搜索时间。由代价值得到启发式值h(n)，h(n)值的好坏直接影响到下个节点的选取，因此找到一种计算快速、易于理解的启发式函数算法对整个搜索过程有着极为重要的作用[2]。

在对启发式函数进行介绍前，需要对一些符号做出说明[12]。s表示状态，v=w为原子(以下用x表示)，s[v=w]表示一种状态，在这种状态下，除了变量v的值以外，其他与s都相同；相似地，s[s′]也为一种状态，此状态下，某些变量值与状态s′下相同，其他变量的值则与状态s下相同。var(x)指原子x中的变量。

一个操作是效果的集合，形式为v=w′，z→v=w，其中z是一个部分状态，v是一个变量，w′和w属于变量值域Dv，对应于v不同状态下的值。这一效果意味着在与部分状态z相符合的当前状态s下，变量v的值为w′，作用操作o后，生成继承状态s′，此状态下变量v的值变为w。为了将此意义表示清楚，通常写作以下形式：o:v=w′，z→v=w。

启发式h(S)定义如下

(3)

其中：xs是状态s下的变量var(x)对应的原子；h(x|xs)是指变量var(x)由状态s下的值改变到状态s★下的值所用代价。

对于上面介绍的规则o:v=w′，z→v=w，条件v=w′需要先实现，然后条件z在得到的状态s下进行评估。拓展式(3)得到

(4)

以条件数为代价的启发式计算仍以瞬时动作为基础。对于压缩动作和开始动作，代价cost=|conditions|，即代价为压缩动作后的前提条件数，例如对于图3来说，cost=2。对于等待动作，cost=0，因为动作已经在执行，说明该动作的条件数已经得到满足；从逻辑公理导出的瞬时动作，例如公理z→v=w可得到瞬时动作o，其代价cost(o)=0，效果为{v=w′，z→v=w|w′∈Dv{w}}。

以条件数为代价，式(4)进行拓展，如式(5)所示。

(5)

2.3 规划算法

在整个搜索过程中，采用的主要搜索算法为A*算法。A*算法是一种静态网络中求解最短路径的最有效方法。启发式则是用来引导搜索算法的，并在父节点的确定过程中，对各个动作间进行时间约束的判断，即判断动作间是否满足先后顺序条件，不满足时间约束的节点即被移除掉，选择下一个节点，使其搜索效率更高。

在本文的搜索算法中，使用的启发式为以条件数为代价的上下文增强累加启发式。搜索过程如图5所示。

此算法将创建两个表，名称分别为OpenList和CloseList。OpenList存放已经生成而未被考察的节点，CloseList则存放记录已经访问过的节点。首先将初始节点放入OpenList中，因为在第一步中，没有别的节点可供选择，所以将初始节点直接从OpenList移除，放入到CloseList中，并将初始节点的所有子节点放入到OpenList中。然后根据启发式信息对初始节点的子节点进行排序，选择优先级最高且满足时间约束的节点放入到CloseList。再次将此节点的子节点(OpenList中没有并且也不是CloseList中的节点)放入到OpenList中，并对OpenList中节点重新计算启发式，然后再选择优先级最高的节点重复处理[3]。

在搜索过程中，有两个特殊量值得注意。首先，引入一个时间小量 ，用来满足“无移动目标”规则，当一个动作加入时标状态后就会引入此小量。其次，引入一个特殊动作“let_time_pass”，此动作可应用在任何一个状态下，此动作仅让时间流逝，而不会产生任何效果。

图5 基于时间约束的启发式规划算法

Fig.5 Heuristic algorithm based on time constraints

3 仿真分析

在规划系统中，搜索算法的选取对结果的产生有着重要的作用，当然在利用启发式的搜索中，启发式信息的好坏对得到的规划质量和搜索速度也至关重要。其中一个发展方向则是针对某个领域设计出具有针对性的启发式，在此领域能够取得理想的效果即可。因为本文是针对深空探测器设计的启发式，因此就需要分析这种启发式在深空探测问题中所取得的结果和效果。

采用第1节所建立的深空探测器小天体接近段的任务模型，利用基于时标状态的规划器进行规划的搜索求解，获得了任务的规划结果。如图6所示。

从得到的规划方案可看出，时间以0.000 1 s的单位向前推进，以满足“无移动目标规则”(no moving target rule)。对于第1节建立的探测器任务，规划器只需要40.000 3 s即可实现目标。实现目标所需要的步数根据初始状态和目标状态决定的。因为采用了时标状态及时间推进小量∈，准备相机和调整探测器指向可同时进行，所以节省整个规划任务解的时间，提高效率。

Time： Action：ActionDuration：000000000：(cam＿readycam1)[1000000000]000000000：(att＿maneuveratt1initialasteroid1)[1500000000]10．00000000：(cam＿opencam1)[100000000]15．00000000：(cam＿takephotocam1asteroid1)[500000000]20．00000000：(att＿maneuveratt1asteroid1star1)[1500000000]35．00000000：(cam＿takephotocam1star1)[500000000]Time： Action：ActionDuration：000000000：(cam＿readycam1)[1000000000]000000000：(att＿maneuveratt1initialasteroid1)[1500000000]10．00010000：(cam＿opencam1)[100000000]15．00010000：(cam＿takephotocam1asteroid1)[500000000]20．00020000：(att＿maneuveratt1asteroid1star1)[1500000000]35．00030000：(cam＿takephotocam1star1)[500000000]Solutionwithoriginalmakespan40found(ignoringno⁃moving⁃targets⁃rule)．Solutionwasepsilonizedandrescheduledtoamakespanof400003．Planlength：6step(s)．Makespan：400003

图6 深空探测器小天体接近段任务的规划方案

Fig.6 Plans for missions in the closing phase to a small body

按照第1节的建模方法建立多个深空探测领域问题模型。然后分别运用以动作时间为代价的和以条件数为代价的启发式搜索方法求解，记录搜索时间和规划解的完成时间，将两种结果对比，进而分析两种启发式信息的效果。用曲线图7表示，形象地比较两种启发式在搜索时间方面的优劣。

图7 启发式搜索时间曲线比较图Fig.7 Comparison of heuristic 1 and heuristic 2

在图7中，启发式1为使用以动作时间为代价的上下文增强累加启发式(TFD中)得到的搜索结果，启发式2为使用以条件数为代价的启发式搜索方法得到的结果。横坐标是问题号数，问题号数是以问题复杂程度由简单到复杂排列，而问题复杂程度的判定是以领域描述复杂度及问题难易度为标准。以问题搜索时间为纵坐标，单位为秒(s)，单位长度为0.5 s，因此同一个横坐标下，曲线在下方的启发式方法搜索时间短，效果好。由图可知，随着问题复杂度的增加，问题搜索时间也增加；在两种启发式结果比较中，起初区别并不明显，而随着问题复杂度的增加，差别逐渐拉开，以条件数为代价的启发式搜索方法显示出优势。

从上述实验结果可知，对于深空探测领域问题，应用以条件数为代价的启发式搜索算法仍能得到规划结果，并且搜索时间仍然比较理想。当两种启发式得到的规划解质量相同时，在搜索时间方面，以条件数为代价的启发式搜索方法略胜一筹，适合实时性要求高的深空探测器。

4 结 论

本文针对深空探测任务特点，采用规划领域定义语言PDDL，建立深空探测领域中多个问题模型，并对模型语句及定义方法举例说明，展示操作中遇到的时间与资源约束。随后应用以条件数为代价的启发式搜索方法对深空探测模型求解，并将其与以动作时间为代价的上下文增强累加启发式搜索方法得到的结果对比，得出以条件数为代价的启发式搜索方法在搜索速度方面略胜一筹，满足深空探测自主规划任务实时性要求。

[1] Bonet B， Geffner H. Planning as heuristic search[J]. Artificial Intelligence， 2001，129:5-33．

[2] Edelkamp S， Schrödl S. Heuristic search: theory and application [M]. United States of America: Margan Kaufmann， 2011:1-427．

[3] Cushing W， Kambhampati S， Mausam，et al. When is temporal planning really temporal？ [C]∥The International Joint Conference on Artificial Intelligence. Hyderabad， India：[s.n.]， 2007.

[4] Haslum P， Geffner H. Heuristic planning with time and resources[C]∥Proceedings of the Sixth European Conference on Planning. Toledo， Spain:[s.n.]， 2001.

[5] Minh B D， Kambhampati S. Sapa: a multi-objective metric temporal planner[J]. Journal of Artificial Intelligence Research， 2003，20:155-194．

[6] Helmert M， Geffner H. Unifying the causal graph and additive heuristics[C]∥Proceeding of the 18th International Conference on Automated Planning and Scheduling(ICAPS). Sydney， Australia: [s.n.], 2008.

[7] 彭婷.基于修复策略的深空探测器自主任务规划方法研究[D].北京:北京理工大学，2012.[Peng T. Autonomous mission planning method of deep space explorer based on repair planning strategy[D]. Beijing∶Beijing Institute of Technology， 2012.]

[8] Fox M， Long D. PDDL2.1: an extension to PDDL for expressing temporal planning domains[J]. Journal of Artificial intelligence research， 2003，20:61-124．

[9] Smith B， Sherwood R， Govindjee A， et al. Representing spacecraft mission planning knowledge in ASPEN[C]∥Artificial Intelligence Planning Systems Workshop on Knowledge Acquisition. Pittsburgh: [s.n.]， 1998.

[10] 饶东宁，蒋志华，姜云飞.规划领域定义语言的演进综述[J].计算机工程与应用，2010，46(22):23-25.[Rao D N， Jiang Z H， Jiang Y F. Review on evolution of planning domains definition language[J]. Computer Engineering and Applications， 2010，46(22):23-25.]

[11] Helmert M. The fast downward planning system[J]. Journal if Artificial Intelligence Research， 2006(26):191-246．

[12] Eyerich P， Mattmüller R， Röger C. Using the context-enhanced additive heuristic for temporal and numeric planning[C]∥Proceeding of the 19th International Conference on Automated Planning and Scheduling (ICAPS). Thessaloniki， Greece: [s.n.], 2009. 作者简介： 李朝玉(1990—)，女，博士，主要研究方向：深空探测器自主任务规划。 通讯地址：北京市海淀区中关村南大街5号院北京理工大学宇航学院(100081) 电话：(010)68918910 E-mail:handylzy@163.com

[责任编辑：高莎]

Time Stamped States based Heuristic Algorithm for Spacecraft Mission Planning

LI Zhaoyu1，2， XU Rui1，2

(1.Institute of Deep Space Exploration Technology， Beijing Institute of Technology， Beijing 100081， China;2.Key Laboratory of Dynamics and Control of Flight Vehicle， Ministry of Education， Beijing 100081， China)

For real time in deep space exploration， it is a requirement of autonomous mission planning for the explorer to find a plan as soon as possible. A kind of method is to use heuristic algorithm. At the same time， durative actions and numeric information have to be processed. According to these characteristics， this paper adapts planning domain definition language (PDDL) to establish knowledge models and describe time and resource constraints. Then the heuristic algorithm based on condition number is proposed to solve planning problems of deep space exploration. Finally， we compare this heuristic with context-enhanced additive heuristic based on action time in TFD (Temporal Fast Downward) planner. The result of the experiment shows that the heuristic algorithm we proposed is better to solve the planning problems in deep space from the point of view of real time．

deep space exploration; heuristic; durative actions; numeric

2014-12-20

2015-02-10

国家重点基础研究发展计划(973计划)(2012CB720000)；民用航天项目

V44

A

2095-7777(2015)01-0020-07

10.15982/j.issn.2095-7777.2015.01.003