航天器时态规划技术研究进展

李朝玉，徐 瑞，曾 豪，朱圣英，梁子璇

(1. 北京理工大学宇航学院，北京 100081；2. 深空自主导航与控制工信部重点实验室，北京 100081；3. 北京空间飞行器总体设计部，北京 100094)

0 引 言

航天器系统级自主性是衡量其一定时间内在没有地面站支持的情况下实现任务目标的能力，智能规划技术是航天器实现自主运行的核心技术[1]。作为人工智能领域中研究较早的方向之一，20世纪50年代后期，Newell和Simon设计出了逻辑理论家程序及问题求解程序，在人工智能领域具有重要的地位[2]。20世纪70年代至90年代中期，非线性规划方法在领域无关规划中占有主导地位，以此Fikes和Nilsson设计了最具影响力的STRIPS规划系统，其采用与文字相关的术语至今仍被使用[3]。20世纪90年代后期，空间探测等领域对自主性的需求推动了考虑时间等信息的面向现实问题规划技术的研究和发展。

随着航天任务增多和探测空间越来越远，为了能够降低运行成本、提高总体任务回报率、提高对感知数据反应能力和保证在有限监督下不确定环境中航天器安全运行，自主任务规划技术备受美国国家航空航天局(NASA)与欧洲航天局(ESA)等各航天大国和机构的关注[4]。

深空1号(DS-1)上的远程智能体(RA)和地球观测1号(EO-1)上的自主科学飞船实验最具代表性，实现了在轨自主任务规划技术的飞行验证和应用[5]。RA中任务规划思想在NASA开发的可扩展通用远程操作规划框架(EUROPA)[6]中得到延续和拓展。美国喷气推进实验室(JPL)开发的自主调度与规划环境系统(ASPEN)[7]是EO-1中连续规划软件CASPER的基础，同时应用到雷达卫星RADARSAT和轨道快运太空任务。ESA最初在硬件编码环境下对基于时间线的规划技术和约束可满足技术进行了使用和验证，两个决策支持系统MEXAR2和SKeyP分别用于火星快车号(MEX)在轨内存操作的调度和太阳及日光层观察航天器(SOHO)在资源受限情况下的操作规划[8]。先进规划与调度计划(APSI)软件框架进一步推动了AI技术在ESA航天项目中的应用[9-10]，例如用于火星快车任务长期规划器(MrSPOCK)[11]和国际伽玛射线天体物理实验室卫星(INTEGRAL)[12]。

上述研究表明：设计、实现和验证自主任务规划技术非常困难。经典规划问题采用具有限制性假设的状态转移系统模型，包括规划解是序列式的、隐去时间表示等[13]。在此模型下，动作或者事件具有瞬时性，两者之间不存在时间约束，无法有效全面地描述和求解航天器任务规划问题。由于空间环境动态多变和无法预知的特点以及航天器系统复杂性，给航天器自主任务规划技术带来以下难点问题[14-16]：

1)活动和目标具有持续时间和截止期限要求：航天器活动非瞬时发生，具有一定的持续时间，多数活动具有特定时间窗口(例如通信)；任务通常要求在一定时间内实现，而不能无限期等待；

2)活动间存在时间约束：大部分活动开始时间、持续时间和结束时间具有约束，例如航天器需要在相对于零点的10 min后执行拍照动作。活动间存在顺序、并行、交错等多种时间约束；

3)有限的资源：航天器的燃料和存储能力等有限，资源需要在一定的时间区间内进行管理和分配，以保证资源的合理利用和航天器任务的完成；

4)不确定性：空间环境复杂恶劣、不完全可观，导致航天器活动时间不固定，如火星车转移到指定地点受火星表面崎岖地形影响造成持续时间不确定。同时由于部件老化或损坏，航天器无法控制某些动作的精准实现，会出现执行时间或效果偏差；

5)航天器系统复杂：航天器具有多个不同功能的子系统，不仅包含姿态控制等基本保障系统，还需要考虑执行特定任务的专用系统，如有效载荷。不同子系统下，包含不同层级的执行器或控制器，如阀门、传感器等，航天器模型呈现复杂多样性。

以上难点问题给航天器任务规划技术提出新的挑战：航天器模型复杂多样，时间要求苛刻、约束密集耦合。针对具有时间属性的规划问题，通常采用先规划生成顺序动作序列再进行调度的方式，但会出现调度无法满足时间和资源约束，需要重新规划的情况，无法满足航天器实时性要求。因此，面对航天器自主控制和运行的实际应用和发展趋势，开展考虑时间属性的航天器自主任务规划技术具有重大的理论和现实意义。本文首先对航天器时态规划技术进行定义和规划模型建立方法分析，随后梳理国内外任务规划技术研究成果，最后分析主要方法优缺点和发展趋势，并对未来航天器时态规划技术的研究方向提出建议。

1 航天器时态规划的定义和建模方法

考虑航天器系统模型、领域约束和所处环境特征，给出航天器时态规划技术定义，如下：

定义1.(航天器时态规划技术)航天器时态规划技术是指根据空间环境感知和认识以及航天器本身的能力和状态，对时间属性进行显示表示，利用人工智能搜索技术、知识建模技术和智能推理技术等，针对一定时间内的任务目标，对若干可供选择的动作进行选择和所涉及的约束进行推理，自动生成时间有序的活动序列，实现将动作的选择和调度进行整合。

时态规划技术同时考虑航天器动作之间的因果关系和时间约束，可以更真实地对航天应用进行建模和规划。规划问题定义是规划前对规划问题进行的描述，因此规划建模语言是自主规划发展的关键。目前，时态规划建模方法主要有两种形式[17]：(1)扩展状态空间表示方法，其基于状态之间的时间限定持续区间；(2)时间线表示方法，其依赖于单个状态变量随时间的演化及时间线元素之间的约束。

1.1 状态空间时态规划建模方法

1.1.1以动作为中心的模型表示语言

国际智能规划大赛(IPC)公认标准规划领域定义语言(PDDL)[18]是一种以动作为中心的建模语言，以STRIPS操作符和ADL语言为基础，对动作和状态进行标准化定义，使用前置条件和效果描述动作的可用性和状态转换。针对实际规划问题需求，提出使用较为广泛的PDDL2.1版本[19]，在PDDL1.2基础上定义持续动作，增加了数值流、连续效果及灵活的规划质量度量等，核心思想是将持续动作看作两个瞬间的开始时和结束时的动作，通过持续时间约束(限制动作开始和结束时间之间的可能延迟)和持续性条件(要求在动作执行过程中的所有状态都要保持一定条件)连接在一起。

PDDL2.1存在两个局限性:(1)条件和效果只能放在动作的开始和结束点。可以通过将一个具有中间时间点的复杂持续动作拆分为多个子动作来避免这种限制，但手工编码持续性动作是困难的且容易出错。(2)问题定义仅由初始状态和目标状态组成，导致无法轻松表达环境的演变知识(如航天器预计将在11∶05进行对地观测)和对解决方案进行时间上的限定约束(如从20点到22点发动机不能工作)，以上两种功能都在语言的后期版本中引入。PDDL2.2[20]的定时初始字元可用来描述环境的演化，它允许在任意时间对谓词进行真值赋值(如在时间11∶05时谓词Point(dir1)将成为真值)。PDDL3.0[21]引入的状态轨迹约束可用来表达时间上的扩展目标如截止期限。尽管这些扩展在表示现实世界的问题上是必不可少的，但针对它们在时态规划领域的研究和应用非常有限。

尽管以STRIPS为基础的建模语言对规划领域做出了很大贡献，但是用来表示具有时间、资源、相互排斥关系和并行性仍具有一定困难。例如，为了表示时间和资源，需要引入大量的命题和领域原子，同时很难决定哪些动作可以同时发生，无法指定动作内部中间时间点和解决多个动作的共同影响。因此，要想解决航天任务这类现实问题必须寻找表达能力更强的规划知识表达方式。

1.1.2以动作为中心的时态规划问题定义

以PDDL2.2为基础，给出时态规划问题和关键元素定义，其中在活动、条件和效果的建模中体现出领域时间属性。

定义2.时态规划问题P由五元组定义P=(V,I,T,G,A)表示，式中：

V为命题条件集合；

I是初始状态，对V中的所有命题的值分配T或F的完整集合；

T是一组定时初始字元，为一个元组([t]f:=v)，其中f∈V，t∈R+是壁钟时间，在该时间f将被赋予布尔值v；

G⊆V是目标状态，当规划执行完需要实现的命题条件集合；

1.2 基于时间线的时态规划建模方法

1.2.1基于时间线的模型表示语言

基于时间线的任务规划从不同角度处理时态规划问题，不明确区分状态、动作和目标，而是将规划领域表示为独立但相互作用的组件组成的系统，组件表示为时间线，由给定的时间约束集合支配。这种范式诞生于空间操作规划和调度的背景下，在过去20年里已被应用于空间探测任务的短期到长期规划任务以及航天器在轨自主运行等复杂情况。例如，DS-1采用的领域描述语言(DDL)[22]，使用状态变量时间线表示航天器子系统，标记用来代表某一状态变量处于特定状态的时间跨度或者间隔，协调条件用于描述时间约束。

以DDL语言为基础，NASA提出了新领域定义语言(NDDL)[6]，用于规划系统EUROPA的建模，采用兼容性来支配时间线上断言得到合理安排(如代表着火星车移动r到x的活动，必须通过将r放在x处的断言来满足)。针对时间关系采用Allen的区间代数方法显式定量指定了需要改变和保持的约束。一个解是一组断言之间不存在空隙的时间线，并满足所有的兼容性。这个范例允许描述带有时间项的规划领域、资源、并行活动、活动集合的互斥现象、分割先前条件和条件效果。ASPEN建模语言AML[23]是考虑分层任务网络(HTN)思想的基于时间线的表示语言，核心部分是活动，可以用来表示目标、高级任务或基本动作，子活动用于将目标和高层次任务细化为原始动作。

其与基于STRIPS操作符的规划建模语言相比，存在几个主要不同点：

1)使用变量/值的表示方法而不是命题逻辑；

2)不区分状态和动作，仅使用区间和区间之间的约束来描述，规划问题只是需要将时间线用区间填满即可；

3)对于时间要求严格的空间环境，使用基于时间线的表示方式使得规划解鲁棒性更强，有利于与规划序列执行相结合。

由于航天器需要同时支持时间和资源的处理，且需要考虑规划序列的执行，因此，基于时间线的建模方法在航天任务规划系统中得到广泛应用。但同样存在缺点，主要体现在缺乏因果关系的明确表示，在规划过程中较难应用启发式和直接描述冗余约束，修改模型困难。同时缺少像PDDL一样的规范标准[24]。

1.2.2基于时间线的时态规划问题定义

根据航天器任务规划特点并结合当前研究，给出基于时间线的时态规划问题的规范化定义。

定义3.状态变量x是个四元组x=(N，V,T,D)，式中：N是状态变量名称；V是状态变量值的非空集合；T:V→2V为状态变量值转换函数；D:V→T×T∞是状态变量值持续函数，D(v)=(dmin,dmax)，dmin≥0且dmax≥dmin，表明状态变量在时间(dmin,dmax)内保持值为v。

定义4.如果x=(N，V,T,D)是一个状态变量，对于x的标记形式为：xi=(v,[e,e′],[d,d′])，其中xi是标记名称，i∈N；v∈V，e,e′,d,d′∈T，对于D(v)=(dmin,dmax)，e≤e′且dmin≤d≤d′≤dmax。

对于状态变量x的时间线Lx是对于x的标记的有限序列，形式为x1=(v1,[e1,e′1],[d1,d′1]),…,xk=(vk,[ek,e′k],[dk,d′k])，其中i=1,…,k-1，vi+1∈T(vi)且e′i≤ei+1。最后一个标记的区间[ek,e′k]被称为时间线的时间范围，标记数量k为组成时间线的长度。状态变量和时间线如图1所示。

图1 状态变量示意图Fig.1 Diagram of state variable

一组时间线的规划时间范围H是每个时间线时间范围的最小值。

时间关系是基于时间线的规划模型中重要元素，它们可以是两个时间段之间的关系，也可以是一个时间段和一个时间点之间的关系。

定义5.时间段之间时间关系表示形式为Aγ[l,u]B，其中A=[sA,eA]和B=[sB,eB]为时间段，sA,eA，sB,eB∈T，l∈T，u∈T∞且γ∈R，R为Allen十三种时间约束关系集合，即R={before, meet, overlap, start, during, finish, after, it-met-by, is-overlapped-by, is-started-by, includes, is-finished-by, equal}。

定义6.原子是指定常量⊥或者时间关系形式aiγ[l,u]aj或aiγ′[l,u]t，其中ai和aj是标记变量，l,t∈T，u∈T∞，γ∈R和γ′∈R′。

特称命题定义为∃a1[x1=v1]…an[xn=vn].C形式，其中a1,…,an是不同的标记变量；对于所有i=1,…,n，xi是状态变量，vi∈V(xi)(即ai[xi=vi]是被标注的标记变量)；C是原子的结合。

命题的界限变量是a1,…,an，任何可能发生在C中的与a1,…,an不同的变量在命题中是自由发生的。特称命题的析取组成了同步规则。

定义7.同步规则表示为a0[x0=v0]→ξ1∨…∨ξk(k≥1)，其中ξi是一个特称命题，其边界变量是与a0不同的所有变量，只有a0是可能自由发生的。a0[x0=v0]被称为规则触发条件。当触发条件为空的时候，形式为⊥→ξ1∨…∨ξk(k≥1)，其中ξi是没有自由变量的特称命题。

定义8.基于时间线的规划领域定义为二元组D=(VS，S)，其中VS为状态变量集合；S为同步规则集合。

定义9.对于领域D=(VS，S)的规划目标G是双元组(Γ,Δ)，其中Γ是形式(g,x,v)的集合，g是目标标记变量的名字，x∈VS且v∈V(x)；Δ为关系目标，是正向布尔公式，仅包含发生在Γ中的目标。

定义10.基于时间线的时态规划问题定义为三元组PT=(D,G,H)，其中D为规划领域，G为规划目标，H∈T是规划时间范围。

定义11.灵活计划Π是二元组(L,R)，其中L是时间线集合，R是标记间关系集合，包含标记名称和所属时间线。

定义12.对于规划问题PT=(D,G,H)，灵活计划Π=(L,R)是有效的当且仅当：L是对状态变量VS的时间线集合，Π满足S中的所有同步规则。

对于规划问题PT=(D,G,H)，当灵活规划Π有效且满足目标G，则该规划为问题的一个规划解。

2 时态规划技术研究现状

航天器时态规划问题中，通常需要处理持续活动、目标截止时间、并行性、轨迹约束和连续变化等时间属性。由于缺少特定标准，研究人员通常以经典规划技术为核心，挑选有限的关注因素进行拓展，因此往往处理时间能力不足。同时，由于规划知识建模语言限制，没有基于时间线的规划器参加IPC大赛(除2002年的IxTeT)，缺少标准化的对比与评价。根据规划技术特点，将时态规划技术分为前向链、模型转换、规划空间和HTN四种类别，每类所包含的规划方法以及各自的特点如表1所示。

2.1 前向链时态规划方法

大部分时态规划器直接由经典规划器拓展而来，时间属性满足方向由前向链时态规划器主导。根据前向链规划器的搜索空间将其分为三类：

2.1.1首次适应时态规划方法

首次适应时态规划器本质上为经典规划器，通过采用经典规划器生成顺序解决方案，然后进行重新调度实现时间约束满足，用最简单明了的方法来处理时间属性，如图2所示。2008年IPC组织者利用MetricFF[25]规划器为比赛提供对比的基础方案，最终赢得了该届时间满足方向的比赛。YAHSP[26-28]规划器的第二版和第三版在规划过程中使用Bonet和Geffner的hadd启发式方法[29]，增加了从当前状态构建的松弛规划图中所有目标流的深度。DAEYAHSP2[30]规划器在任意时间规划方法中，进行多次后处理，通过遗传规划技术来进一步找到优化的规划序列。其他类型规划器如MIPS[31]和LPG的早期版本[32]也采用重新调度的方法来支持时态规划问题。

图2 首次适应时态规划方法示意图Fig.2 Diagram of first-fit temporal planning

尽管此类规划器在大赛中取得一定优势，但它们只能解决简单时态规划问题，不能求解具有必须并行动作的规划问题，例如“姿态定向”和“目标拍照”两个动作只能同时执行而不能顺序执行(如图3所示)。在实际应用中，先规划后调度方式容易造成重规划，无法满足航天器实时性要求。

图3 必须并行动作示意图Fig.3 Diagram of required concurrency action

2.1.2决策时点时态规划方法

状态空间下的时态规划器需要克服一个重要的技术障碍：每个动作可以从无限多的时间点中的任一时间点开始。大部分规划器通过将动作的可能开始时间限制在一小部分的特殊时间点(称为决策时点)内避免无限分支因素。规划器在时间状态空间进行搜索，时间状态N的核心是世界状态state(N)，使其可以利用可达性启发式，通过增殖和推进两种方式生成子节点。该方法的关键特性是决策时点的选择：在一些动作刚结束或刚开始的时候选择开始一个动作。

TLPlan[33]规划器首先在前向链中引入了决策时点，通过在时间戳上启动新的动作或将时间戳提前(通常在下一个效果之后)生成搜索节点的后继节点，使用线性时间逻辑进行搜索控制，具有明显领域相关性，可处理必须并行活动。许多有影响力的时态规划器以此为基础，如SAPA规划器[34]建立在Fast Forward规划器上，将决策时点思想应用到领域无关规划中，首次提出时间松弛规划图(TRPG)来计算时间标记状态的启发式值，可处理具有连续时间区间的活动、具有截止时间的目标和度量资源约束。TFD规划器[35]基于Fast Downward规划器，将多值规划任务作为输入，将持续并行动作分为多类瞬时动作，进而继续使用因果图启发式和上下文增强累积启发式进行搜索。TP4规划器[36]使用反向状态空间搜索以及与时间或资源相关的可采纳启发式，可求解部分时态规划问题，其中持续时间以单位时间衡量。

与经典规划相比，决策时点规划方法在几乎每个搜索节点都有一个额外的分支，造成计算资源极大浪费。支持具有必须并行活动的情况，但对于丰富的时间表达问题仍然不完备[37]。此外，由于它们先选择可以执行动作的时间，后选择执行哪个动作，导致缺乏系统性，例如对于完全独立于计划其余部分的动作，规划器将在每个决策时点都会考虑其执行，导致了许多可被视为等同的计划。

2.1.3时间提升规划方法

时间提升规划器利用时间提升的思想突破了决策时点规划器的局限性，即延迟关于何时执行动作的决策，直到所有关于执行哪些动作的决策完成，并通过简单时间网络(STN)跟踪时间约束。CRIKEY规划器[38]是首次针对时态PDDL问题的完整的前向链规划方法，核心为MetricFF规划算法，利用松弛规划图计算启发式和有用的动作辅助动作选择，在检测到包络动作后，通过绑定STN和使用贝尔曼算法检测并行活动的时间一致性，从而处理活动交错并行的问题，规划完成后使用时间约束网络对整体规划进行推理，确定活动准确执行时间。

以上思想在CRIKEY3[39]，POPF[40]，COLIN[41]和OPTIC[42]规划器中均得到使用。例如，POPF规划器在前向搜索基础上支持偏序规划，采用后期承诺方法实现部分排序和灵活性，即延迟对排序决策、时标和数值参数值的承诺，在动作开始和结束时管理约束集。同时受益于前向规划的信息搜索控制，通过线性规划求解器实现时间和度量决策。POPF2规划器在POPF上进行拓展，对顺序约束做更少承诺和改进时间松弛规划图启发式方法，采用Stochastic-POPF的代价优化，并使用了随时搜索功能，可以找到更多完成时间有效的规划解。COLIN规划器值得注意的是它能够处理并行性甚至线性连续变化的情况。

与首次适应时态规划器和决策时点时态规划器不同，时间提升规划器对于PDDL2.1的语义是完备的，并且可以解决具有必须并发和相互依赖的动作的问题。

以上所有前向链规划器主要依靠改进经典规划器的启发法来指导搜索，其中大部分是基于忽略了动作的删除效果而构建的TRPG，例如SAPA，CRIKEY，COLIN和OPTIC等。尽管这些启发式方法对规划大赛中问题非常有效，但其效率依赖于完全定义的状态，对于具有必须并行动作的规划问题使用启发式仍是挑战，因此对于航天器规划情景有效适应存在一定困难。

2.2 模型转换时态规划方法

模型转换规划方法通常将任务规划模型转换为可满足问题模型或使用特殊数据结构，并采用相应技术进行求解。根据转换后模型，可分为基于图规划和可满足技术的时态规划方法。

2.2.1基于图规划的时态规划方法

图规划(GraphPlan)技术主要思想是构造一个包含所有可能状态的紧凑搜索树，并在该树中找到一个解。该算法包括图扩展和解提取两个阶段，采用可达性分析排除许多不相容的动作序列以及组合，丰富的规划图结构使得对规划研究和拓展道路更为宽广。对于时态规划领域，通常在动作层或命题层引入时间进行拓展。TGP规划器[43]首次在GraphPlan规划器上考虑了持续STRIPS动作。在规划图动作层引入时间信息，构建时从一命题层开始，通过在所有可能的动作中选择一个最早结束的动作来推进。该规划器具有决策时点规划方法特点，对于丰富时间属性规划问题不完备。TPSYS[44]规划器做出改进，可以处理PDDL2.1 Level3时态规划域，动作可以在开始时具有效果。TGP和TPSYS在动作持续时间差别很大时，规划图的构建非常缓慢。

LPGP规划器[45]是针对PDDL2.1首个领域无关的完备方法，在GraphPlan框架中将时间引入命题层，避免了因动作持续时间差别大造成的效率低。每个持续动作被分为开始动作、结束动作和不变性检查动作，通过一种新颖的规划图时间泛化方法归约为线性规划处理时间信息，如图4所示。TLP-GP[46]规划器进行了类似的工作，但使用了析取时间网络处理时间约束。LPG[32]规划器在规划图中应用随机局部搜索，最新版本使用LPGP方法生成规划图处理交错并行性，同时目标函数中考虑了并行动作的个数和从当前状态开始的整个规划的执行时间。优化时态规划系统CPPlanner作为第一个基于Graphplan的优化规划器可以处理更丰富的时间领域(即动作可以产生中间效应)。

图4 LPGP规划图示意图Fig.4 Diagram of LPGP plan graph

图规划方法在处理时态规划领域时，采用将持续动作分解为瞬时动作处理，在时间处理丰富性方面一直在进步，但针对具有丰富时间约束的航天器规划问题仍然存在搜索空间大的问题。

2.2.2基于可满足技术的时态规划方法

基于可满足技术(SAT)的规划方法将规划问题编码为SAT公式，其中每个变量表示相应动作或命题在潜在规划中的发生位置，因果关系被表示为若干底层子句，输出规划具有有效步骤数，每个步骤可包含多个动作，通过SAT求解器寻找一个模型。如果模型存在，则会从中提取一个规划。在优化经典规划和并行规划中，可满足性规划性能表现一直很强。为了能够处理时态规划，STEP、SCP2和T-SATPLAN规划器等利用离散时间表示方法，为每个步骤分配一个离散时间标签，但无法有效利用并行性，且造成计算代价较大[47]。

最新的ITSAT[47]规划器将可满足性检查方法扩展到时态规划领域，支持求解具有必须并发性的PDDL2.1问题。首先将所有持续性动作分解为两个瞬时动作，通过求解非时态问题得到因果关系有效规划，然后，规划器通过STN对规划问题中的时间约束进行推理从而实现调度。如果不存在这样的调度，则通过附加子句扩展问题，避免造成时间不一致的因素，然后重新启动该过程，直到找到时间有效的规划解，流程如图5所示。

图5 ITSAT规划流程示意图Fig.5 Diagram of TISAT planning method

2.3 规划空间时态规划方法

在规划空间规划中，节点是部分规划，弧是进一步完成部分规划的细化操作，算法从一个空规划开始，经过细化操作，以最终包含实现所有目标的解决方案的节点为目标。特点是使用最小承诺原则，将有关动作顺序和参数绑定的决策推迟到强制执行为止，产生的规划序列更具鲁棒性和灵活性，对于解决时态规划问题具有一定优势。对于时间拓展，使用时间区间来表示动作和命题，动作之间的因果关系被部分规划中的时间顺序所取代，通过时间映射管理器启发的系统进行冲突处理。根据规划问题表示和求解方式的不同，分为结合偏序因果链和基于时间线的规划空间时态规划方法。

2.3.1偏序因果链规划空间规划方法

VHPOP[48]是一种基本的规划空间规划器和偏序因果链的完整应用，建立在UCPOP规划器基础上，支持持续动作并采用简单时间约束问题(STP)来进行时间推理，并将领域无关规划中的启发式方法应用到具有持续动作的规划领域。与以前的偏序规划器相比，启发式方法的使用很大程度上提高了规划效率，但是VHPOP不支持数值效果与前提条件，仍不具有竞争力或可扩展性，落后于当前的领先技术。

Vidal和Geffner的CPT[49]是一个更全面的规划空间规划器，应用偏序因果链并结合约束可满足技术，通过推断和搜索寻找具有最佳完成时间的规划。CPT优化规划效率的关键是使用编码为CSP的修剪规则，将时间约束编码为STP并通过Lhomme的边界一致性方法来检查。然而，CPT限制动作不会重叠，因此CPT虽可以处理持续性动作，但无法处理必须并行性，是不完备的。

规划空间规划方法在时间拓展方面起到率先作用，基于时间线的方法和HTN方法均采用规划空间规划思想，且在航天器任务规划中得到广泛应用。

2.3.2基于时间线规划技术

迄今为止，基于时间线的规划方法是空间领域实践中应用最成功的方法[50-51]。受控制理论启发，将领域知识建立为基于时间线的时态规划模型，规划过程在表示世界的初始已知事实的时间线集合上进行操作，通常采用规划空间搜索方法，根据期望要求迭代添加值和时间约束完善时间线的行为[52]，如图6所示。方法重点在于约束系统的时间演化，而不是合成一组顺序动作，以实现期望的目标状态。

图6 基于时间线的时态规划方法示意图Fig.6 Sketch of timeline-based planning method

基于时间线规划方法可以追溯到IxTeT规划器[53]，以规划空间规划方法支持显式的时间和资源，使用年代记定义了时间点作为表示时间关系的基础。采用基于最小承诺原则的领域无关搜索策略，内部大部分表示和推理由特定的约束可满足问题来处理。NASA和ESA等航天大国和机构均开发了基于时间线框架的规划系统，例如HSTS(RAX-PS)、ASPEN、EUROPA和APSI，均采用与时间线和令牌相似方法表示状态变量值随时间的变化和持续性，其中部分时间线与动作和感知直接相关[54]，紧密集成规划和调度，使用兼容性的概念来描述各时间线之间的相互作用以及时间线上令牌的关系。例如，在代表火星车位置的时间线上，与值going(a,b)相关的时间区间必须由at(a)和at(b)相连。规划器通过缺陷挑选和求解的机制进行规划，并从规划空间规划中借鉴了大部分搜索技术，使用手工编码的领域控制知识来指导搜索，寻找满足所有兼容性的完全定义的时间线。EUROPA基于HSTS思想进行拓展，将规划视为一个动态约束满足问题，规划器的选择只会导致在底层约束网络中添加约束。因此，EUROPA不仅用于规划，而且还可用于处理留给CSP或SAT求解器的问题，如调度和优化问题。

ESA启动了APSI计划[9]，确定了基于时间线的表示框架(APSI-TRF)，但其目标是基于时间线的审议层为实施基于时间线的规划器提供便利，包括时间线表示和专门的约束求解器模块，对时间约束和绑定约束进行推理。它已被用作GOAC-APSI规划器的构建模块和MrSPOCK的基础层。

2.4 基于HTN的规划技术

HTN规划由于任务分层分解原理和领域知识表示的可表达性而适合于大规模的实际规划问题。像规划空间规划器一样，HTN规划器维护具有因果关系的部分规划表示，并进一步通过分解将抽象动作转换为子动作[55]。HTN方法发展于规划空间规划，SHOP和SHOP2规划器引入了基于状态的HTN规划器，从而发生了分层规划的重大转变，其通过顺序构建计划来遵循前向链机制[56]。为了处理时态规划领域，SHOP2开发一种多时间线预处理(MTP)技术，将时间PDDL操作符转换为SHOP2操作符，该操作符在当前状态下为多个时间线维护统计信息，跟踪当前状态下的时间信息。规划方法是图灵完备的，并且针对大量规划问题是健全而完整的。SHOP2的操作符与PDDL中的Level 2动作具有相同的表现力，但是SHOP2不明确支持PDDL Level 3中的持续性动作且没有明确的机制来推理持续性和并发动作。

SIADEX-TD[57]规划器能够应对更丰富的时间规划问题(如部分订单度量结构、截止日期、时间界标、同步功能或活动并行执行)，通过动作链构建了一个内在的顺序解决方案，在原有SIADEX的规划范式下，使用STN分两步对时间约束进行表示和推理：将抽象任务分解为子任务后，则在规划中引入低细节定性时间约束，作为规划的时间框架。随后，一旦将其子操作明确包含在规划中，便添加更精确的时间约束，以编码规划中每个最终操作之间的因果关系。另一方面，SIADEX-TD支持Allen和van Benthem独立定义的所有关系，允许在持续性动作中的任意时间点放置效果，条件仅限于动作开始时间进行。但是，如果多个顺序解决方案将导致相同的调度计划，则部分顺序计划将在搜索空间中出现多次，且无法处理并行性。

SHOP2会生成时间固定的调度表，与SIADEX-TD的STN带有活动最早执行时间的调度表一致，但是SIADEX-TD能够处理截止日期和地标，并根据其他条件(即最新执行时间)获得不同的调度表。针对使用STN进行时间推理的方法，Li[58]等进行拓展，可生成灵活规划解。为了能够处理时间约束复杂的航天器规划问题，HTN方法与基于时间线方法结合是当前的一个研究方向[59]。

3 航天器时态规划技术分析与发展建议

3.1 航天器时态规划发展趋势分析

针对航天器时态规划具有规划对象和动作数量多、约束复杂和实时性要求高的特点，时态规划技术不断改进和发展来满足现实问题需求，其发展趋势如下：

1)提升启发式规划方法求解航天器规划问题的能力。基于PDDL的规划方法在搜索过程中表示规划和计算启发式依赖于规划知识的根本表达形式，使得开发的启发式规划方法难以适应航天器规划问题(可包含数千个对象和基本动作实例)。因此，有些研究尝试消除经典规划器的限制[60-61]，例如Ridder和Fox[60]构建一个提升规划图用于启发式评估，但其改进仍是增量开发，未脱离经典规划的其他限制，并且尚未适应于时态规划。

2)规划中时间知识表达和处理能力亟需进一步加强。航天器模型中时间约束复杂，对于PDDL2.1语义完备的规划器(如CRIKEY3)对任务规划问题中时间属性表示和处理能力有限。因此，拓展规划器时间处理能力受到当前研究重视，如OPTIC规划器支持PDDL2.2及PDDL3子集，TLP-GP使用更具表现力的语言，可在操作中的任意固定时间使用定时的初始文字、期限、条件和效果。

3)高性能时态规划算法是目前研究重点。为了能够处理持续动作，大部分基于PDDL的规划方法将动作分解为与原始操作中存在时间点一样多的瞬时动作。尽管可行，但使其适应于具有任意数量时间点会导致复杂度增加，搜索空间膨胀，求解效率无法满足航天器实时性要求。

由于对时间属性表达能力和规划技术处理能力限制，基于PDDL的时态规划技术目前很少能够在大型航天器任务规划问题中使用。但基于时间线的规划系统在许多空间应用程序中得到广泛应用和发展，其关键在于灵活的基于时间线的表示形式，对时间属性的表达能力强，且允许对基本规划范式进行扩展。扩展中最普遍的是可支持资源，由特定的缺陷求解器来处理。最小承诺原则允许更紧凑的搜索空间，在单个搜索节点中表示多个可能的规划。尽管基于时间线规划方法得到广泛应用，但仍存在一定缺点需要进一步研究。

1)基于时间线的规划器集成领域无关的搜索控制和启发式困难。但可以利用规划问题结构，通过拓展部分规划解决可见冲突，从而减轻对启发式的需求。部分学者通过将松弛图的思想引入到规划空间规划方法中，实现对部分规划的评价[62]。

2)航天器复杂系统规划模型的建立对专家经验知识依赖较大，给工程人员增加负担，且直接影响规划搜索效率与质量。因此，研究人员通过开发交互式建模软件或者研究引入领域无关启发式方法对时间线规划方法进行改进。

3)缺少像PDDL的标准表达形式和规划方法评价标准，导致基于时间线规划方法之间相互对比和与基于状态空间规划方法性能比较困难。部分学者通过开发模型转换工具、定义基于时间线规划等方法，使其标准化和规范化。

3.2 航天器时态规划发展建议

把时态规划技术应用到航天领域，需要考虑到航天领域的系统耦合性、资源有限性和时间约束复杂性等特殊性质。从当前的研究进展和需要解决的问题来看，建议时态规划技术在未来航天领域研究的发展方向为：

1)模型中时间表示方法研究

规划知识模型是对规划对象直接的表示和自主规划技术的基础，会影响后续所采用的规划技术。PDDL形式规划语言通过动作、条件和效果发生的时间表示，对于时间重叠或并行表达能力欠缺，且会造成规划搜索空间爆炸式增长。时间线表示形式对时间的表达能力强，但弱化了活动间因果关系。因此如何有效结合两者优点对时间特性进行合理表示是任务规划建模的关键，如目前开发的ANML建模语言。

2)时间约束推理技术研究

目前任务规划方法均采用时间约束网络或者线性规划方法对时间约束进行处理。以时间约束网络为例，当规划问题复杂时，时间约束网络规模较大，时间约束推理所需时间长。同时，规划过程中活动或约束是动态加入，对网络中所有节点和边进行推理，势必造成时间推理效率低下。因此，需要考虑推理效率和所需计算空间，对时间约束表示和快速推理方法进行研究。

3)规划过程中活动并行性处理方法研究

航天器任务规划问题中活动具有必须交错或并行执行的特点，比如拍照过程中需要姿态定向。因此，时态规划技术需要能够处理必须并行活动，这也是任务规划技术对时间属性处理能力最重要的体现。基于时间线的任务规划方法因采用时间区间表示方法从而可实现对并行活动的表示和规划，而基于动作的时态规划技术能够处理并行动作的能力仍有待提高，以适应对航天器规划问题的求解。

4)不确定时间下的时态规划方法研究

受空间环境复杂多变等影响，航天器部分活动执行时间不完全可控，如卫星观测时间窗口受云层影响而不确定。规划方法通常产生具有固定时刻的规划序列，其执行鲁棒性较差，遇到突发事件时会导致重规划，从而影响任务目标的准时实现甚至威胁航天器安全运行。因此，如何在规划过程中提前考虑时间不确定性，生成具有灵活性的规划解是时态规划技术在航天领域实际应用需要研究的重点。

5)规划序列时长优化方法研究

航天器任务规划方法通常以规划出有效解为目标，然而在任务完成时间要求严苛或星上资源非常有限情况下，需要求解最优时长的规划序列。目前，基于图规划和可满足技术的时态规划方法具有优化规划解的基础，基于时间线的规划方法对其较少研究。因此，需要结合航天任务工程实施需求进一步对规划序列时长优化的必要性进行论证和方法深入研究。

6)基于动作与时间线的混合规划方法研究

基于动作的时态规划方法能够处理必须并行性的规划器较少，处理任意时间点的效果和条件能力弱，但启发式方法对规划搜索起到良好的引导作用。基于时间线时态规划方法时间能力表达较强，但弱化了对因果关系的表示和推理，同时缺少对规划方法和规划解质量的评价机制。因此，对两类时态规划方法的理论分析以及如何利用两者优势发展时态规划技术值得未来进一步研究。

4 结 论

自主任务规划技术是实现航天器自主运行的核心技术之一，空间环境动态多变和无法预知的特点以及航天器系统复杂性，给自主规划技术带来了新的挑战，其中时间属性是航天器任务规划中的重要因素。本文阐述了航天器时态规划方法研究难点，并给出航天器时态规划技术定义，从状态空间时态规划和基于时间线规划两方面对规划知识建模方法和规划技术进行描述，分析当前技术优缺点和对航天器任务规划问题的适用性，并讨论了其发展方向。

实际航天器任务规划需要综合考虑动作、时间、资源和数值参数等，基于PDDL模式的规划方法缺少在以上因素同时出现时的理论研究，而基于时间线的规划方法弱化了因果关系推理，同时缺少正式标准定义和方法评价标准，因此时态规划技术在航天器规划问题的应用仍需要进一步进行理论研究和对比评价。同时，时态规划技术的实际应用需要辅以规划序列执行和重规划或规划修复等技术，形成闭环自主管理系统，进而体现自主规划技术的研究价值。

目前NASA和ESA分别开发出具有可拓展性的任务规划框架，并成功进行了星载试验或形成地面成熟的任务规划系统，用以支持航天器长期和短期任务的规划与调度。随着我国航天任务不断增加和深空探测任务的不断推进，有必要结合我国任务需求对自主任务规划技术进行更为深入的研究，为我国航天器自主运行提供技术支撑。