基于扩展状态深空探测器任务规划方法

金颢，徐瑞，崔平远，朱圣英

（1.北京理工大学 深空探测技术研究所，北京 100081；2.深空自主导航与控制工业和信息化部重点实验室，北京 100081）

引 言

深空探测器自主任务规划技术是解决远距离探测器自主运行问题的一项关键技术[1-4]。由于深空距离远、外部环境复杂且不确定性强、科学目标的突现性等特点，传统的地面控制方法已经逐渐无法满足深空探测的需求[5-7]，需要探测器在在轨运行过程中，根据对空间环境的感知和认识及其本身的能力和状态，利用智能规划理论技术，依据一段时间内的任务目标，对若干可供选择的活动或状态及所建模的约束进行推理，自动地生成一组时间有序活动或状态序列来支持探测器在未来一段时间内的自主运行[8-10]。探测器系统复杂，且存在约束类型多、子系统耦合性强、运行环境不确知等特点，传统规划模型难以准确描述系统的功能特性，从而降低了探测器在轨自主任务规划的可靠性[11-13]。针对自主任务规划中系统模型难于精确描述、规划效率低等难点，寻求一种新的合适的建模方法成为深空探测器自主任务规划中亟待解决的问题之一。

深空探测器自主任务规划需要对问题进行更简洁、明确的描述。通过将探测器各子系统的行为表示为时间的函数，对任务规划中涉及的时间约束关系进行统一处理。并且子系统的状态转换由若干事件组成，需要定义在一定的时间区间上[14]。如相机拍照前需要进行一系列的准备事件:主通道开启、大容量上电等。状态转移能够表示时间线上状态之间的逻辑关系，并且转移的持续时间会对问题的规模和局部搜索技术产生影响，为了应对规划执行时的不确定性，需要在规划过程中对状态转移进行显式处理。

知识建模是知识推理的前提。Fike和Nilsson提出的斯坦福研究委员会问题求解器（STanford Research Institute Problem Solve，STRIPS）[15]由于引入了STRIPS操作符而使得规划可以非常容易地进行描述和操作。但STRIPS的表达能力存在很大的局限性，它不能描述具有一定持续时间的动作，不能描述动作间复杂的约束关系等。O-Plan和IxTeT规划器采用动作的概念对物理系统进行描述，并且能够对时间约束进行处理[16-17]。然而，它们一般默认只考虑在动作开始点和结束点上需要满足的约束，这样的处理方式可能会影响到模型的准确性。APSI（Advanced Planning and Scheduling Initiative） 规划系统，作为“火星快车”任务中自主规划系统的开发框架，能够有效地处理任务规划中复杂的时间、资源及参数约束[18-19]。但是，规划器中并没有涉及状态转换时间的处理问题。在EUROPA（Extensible Universal Remote Operations Planning Architecture）规划系统中，将各子系统的活动与状态等统一采用token的形式进行描述，并引入时间线的概念，直观地描述token之间的时间约束关系[20-21]。模型中采用统一的形式对动作、状态、目标等概念进行描述，在描述探测器时并不能真实地体现各子系统状态或活动信息。任务规划领域知识建模技术的发展趋向于更合理准确全面的描述实际问题[22-25]，实际系统状态变化灵活、功能高度复杂的特性，往往导致模型并不能很好地描述。

本文针对规划问题中系统间状态转换频繁及状态间切换并非瞬时完成的特点，引入了扩展状态的概念。建立基于扩展状态的任务规划模型对各子系统复杂功能进行描述，设计基于扩展状态的任务规划算法，对问题搜索空间进行削减，实现降低规划步数，提高规划效率的目标。最后通过仿真计算，验证了模型的合理性及算法的有效性。

1 状态知识表示

状态是一个不断变化的系统的条件描述，它表示被控系统在一段时间内的行为表现。为了便于对本文中任务规划方法进行描述，首先给出状态知识表示中几个基本的概念。

定义1.状态变量SV（State Variable）是建模时对于系统知识的抽象结果，可定义为一个四元组的形式。

其中:N为该状态变量的名称；V是该状态变量的取值空间，即状态变量的值域，为一个非空集合；T为该状态变量各取值之间的转换规则或约束；D表示该状态变量各取值的持续时间。

定义2.状态S是状态变量在某一个时间点或某一时间区间上的取值，可用一个四元组进行表示。

其中:N为该状态的名称；ts、te、d分别为该状态的起始时间、结束时间和持续时间，并且均表示为区间的形式，即ts=[s,s′]，te=[e,e′]，d=[d,d′]，用于应对执行过程中所可能出现的不确定性问题。

定义3.状态时间线STL（State Time Line）用于表示系统状态变量在规划周期内取值（即状态）随时间的变化情况。每一条状态时间线都是系统在规划周期内的连续状态序列，即

规划问题的一个可行解就是一个状态时间线的集合。定义4.运行规则表示状态之间或者状态和资源之间的约束关系。

定义5.基于状态时间线规划问题P可表示为一个二元组为

其中:SV表示状态变量的集合；OP表示涉及SV中变量的运行规则的集合。

定义6.规划解Ω的形式为一个时间线集合。

其中:STLk为一条状态时间线，是一个在时间上连续的状态序列。

STL0,STL1,···,STLk-1,STLk为满足规划问题目标及状态间同步性约束，并且在时间关系上并行的状态序列集合。

2 扩展状态知识描述

由定义可以得到，每一条状态时间线都由连续排列的状态序列组成，用于描述系统状态随时间的变化情况。而状态序列的连续排列表示系统状态的转换是瞬时完成的，即状态转换事件定义在某个时间点上，并不考虑该事件本身对规划过程产生的影响，如图1所示。但是，对于实际任务规划系统来说，每个状态转换描述一个事件集合，即状态转换不可能瞬时完成，需要一定的持续时间，并且可能同样涉及资源、变量等约束关系。因此，若是在规划中忽略状态转换带来的影响，可能会致使规划结果无法适用于实际系统，导致执行过程的失败。

图1 状态转换示意图Fig.1 Illustration of state transitions

为了更准确地描述规划问题，确保规划结果成功执行，本文在原有模型的基础上，引入过渡状态的概念，补充对于转换事件的建模，如图2所示。过渡状态链接同一时间线上两个不同的状态，用于描述不同状态之间的转换活动。例如，相机进行图像获取前需要进行一系列准备动作，如主通道开启、大容量上电等。由于这一系列动作持续时间短、事件数量多且不可避免，在规划中需要对这一类事件进行处理。若是对所有事件都进行描述并在规划过程中搜索，会大大增加问题的搜索空间，降低规划的效率。于是，考虑这些事件持续时间短、与其他时间线状态约束少等特性，特引入过渡状态这一概念，将这一系列事件作为一个整体对其进行描述。既能满足对模型描述的需求，也不会给规划搜索带来太大负担。同时，过渡状态应具有下列特点:

1）过渡状态的约束关系中包含较少的逻辑约束。

2）过渡状态的持续时间较短或与同时间线状态相比较短。

3）过渡状态在整个规划周期中所占时间比例一般较小。

图2 过渡状态示意图Fig.2 Illustration of transition states

在同一时间线上，每个过渡状态的后继状态是唯一确定的。为了达到削减规划搜索空间的目的，本文将过渡状态与其后继状态进行组合，并通过时间约束关系将二者进行绑定（过渡状态的结束时间与其绑定的后继状态的起始时间相同），作为搜索空间中规划操作新的基本对象。考虑过渡状态的约束关系中逻辑约束数量较少，这表明过渡状态被挑选添加到规划中的概率会小于其后继状态的概率。

定义7.扩展状态κ可表示为一个六元组的形式为

其中:N表示扩展状态的名称；Υ表示后继状态为S′的过渡状态的集合；ts，te，d分别表示κ的起始时间、结束时间和持续时间。

通过扩展状态κ的定义可以看出，过渡状态并不独立出现在问题的搜索空间中，而是被视为类似于κ的一种属性参与规划。另外，扩展状态κ的定义并没有对原有问题的搜索空间进行扩展，合理有效地解决了过渡状态可能引起的搜索空间急剧膨胀的问题。针对上述扩展状态定义，本文设计了基于扩展状态任务规划算法，能够在合理描述实际物理系统的同时，较为高效地实现问题规划。

3 基于扩展状态规划算法

深空探测器具有多子系统并行、运行约束复杂等特点，状态空间搜索会导致搜索空间指数爆炸。本文采用规划空间搜索策略，针对扩展状态模型定义过渡状态挑选策略，设计基于扩展状态规划算法实现缩减搜索空间、提高规划效率的目的。

3.1 缺陷类型设计

规划空间规划方法主要是搜索缺陷、挑选缺陷和解决缺陷3部分反复迭代的过程。每迭代一步需要进行一次约束传播检测，验证规划操作的合理性，并在必要时可以进行回溯。整个规划是对初始部分规划不断迭代求精的过程，直到搜索出规划问题的一个可行解。

在规划空间搜索中，缺陷是指导致当前部分规划不一致的潜在因素。规划搜索就是不断地检测当前部分规划中存在的不一致的因素，并逐步进行解决的过程。考虑到缺陷的语义和深空探测器系统复杂的运行约束，这里定义了下述5类缺陷:

1）扩展状态缺陷:如果当前部分规划中存在一个或多个扩展状态前提条件未得到满足，则该部分规划存在扩展状态缺陷。

2）未绑定过渡状态缺陷:如果当前部分规划中存在一个或多个未确定过渡状态的扩展状态，则该部分规划存在未绑定过渡状态缺陷。

3）变量缺陷:如果当前部分规划中存在包含一个或多个未赋值变量的扩展状态，则该部分规划存在变量缺陷。

4）互斥缺陷:如果当前部分规划中存在同一时间线，时间区间存在交叉的扩展状态，则该部分规划存在互斥缺陷。

5）资源缺陷:如果当前部分规划中资源分配不合理，如扩展状态的资源分配超出该资源的总量，则该部分规划存在资源缺陷。

解决缺陷过程中需要对挑选出的状态进行实例化，而状态的实例化又会向当前候选部分规划中引入缺陷。如果一个候选规划中不存在缺陷，那么该候选规划就是规划问题的一个可行解。

3.2 过渡状态挑选策略

每个扩展状态对应一个可能的过渡状态集合，针对这一特点，本文设计了下列4种过渡状态挑选策略:

1）约束导向策略，与扩展状态相关的约束决定它绑定的过渡状态。

2）最小缺陷导向策略，首先选择引入缺陷最少的过渡状态，如果有两个及以上的过渡状态满足最佳选择，它们将按任意顺序进行选择或用其他方法进行评估。

3）资源导向策略，首先选择涉及资源类型最少的过渡状态，如果有两个及以上的过渡状态满足最佳选择，它们将按任意顺序进行选择或用其他方法进行评估。

4）随机策略，如果对于过渡状态选择顺序没有特定需求，则按随机策略进行选择。

为了获取合适的过渡状态，本文对上述策略进行组合，并且采用资源导向及随机策略作为二次评估标准，保证了搜索策略的完备性。具体方法如图3所示。

图3 过渡状态搜索流程Fig.3 The process of transition state searching

3.3 规划搜索算法

本文的规划算法采用规划空间搜索的策略，在其架构的基础上，根据扩展状态的定义和结构特点，同时考虑上述过渡状态选择策略，设计了表1所示的基于扩展状态的任务规划算法。该算法能够有效地减少由于算法缺陷挑选顺序不合理和引发的回溯，提高算法的效率。

表1 基于扩展状态规划算法Table 1 Planning algorithm based on extensible states

4 仿真计算结果及分析

为了验证算法的有效性，建立了一个描述深空探测器领域的模型，并采用本文提出的算法进行了仿真验证。选取美国航空航天局在“深空1号”上已在轨验证的规划算法Europa算法进行比较，通过与Europa算法仿真结果进行对比，验证了该算法能够提高规划搜索的效率，进一步证明了该模型的合理性和有效性。

本文对深空探测器任务规划系统进行建模。每个状态变量描述一个探测器子系统，如推进子系统，太阳帆板子系统等。同时，将科学载荷亦作为子系统进行建模，每一种载荷视为一个子系统模型，并将载荷的操作作为规划问题的目标，例如导航相机的拍照操作。在实现目标获取规划解的过程中，主要处理下列几种约束关系:

1）状态同步约束:例如在拍照前，探测器的姿态需要指向所要拍摄的目标，对地通信时同样需要姿态系统保证一定的指向。

2）变量约束:探测器机动的角度应与下一时刻姿态的指向相对应。

3）资源约束:能源的最大值是一定的，任何时刻，状态消耗能源的总和不能超过能源最大值等。

考虑上述建模方法和约束关系，该模型包括11个子系统，共包含56个状态模型和92个约束关系。

本文选取深空探测器领域中10个不同的问题进行了仿真测试，结果如图4～5所示。由于测试问题按序号顺序所包含的目标的数量是逐渐增多的，故两种模型的计算处理时间是递增的。并且，为避免出现偶然性，本文的测试用例中对每个问题统计其10次计算的平均值。

图4 运行时间结果曲线Fig.4 Computational results of runtime curves

由于过渡状态的引入，对于同一个规划问题能够有效地削减问题搜索空间，减少规划过程中的搜索对象，提高规划搜索的效率。通过仿真结果可以看出，采用扩展状态算法的处理时间要低于采用Europa算法的处理时间，且随着问题中所含目标数量的增多，后者运行时间增加的速率亦超过前者。同时，过渡状态对一系列状态转换事件进行统一描述，可以减少规划迭代步数，从而进一步降低规划的时间消耗，使得扩展状态算法相比Europa算法能够较快获得规划结果。从仿真结果可得，基于扩展状态算法的规划步数也全部低于Europa算法，如图5所示，可以看出，针对同一领域中不同的问题，前者的规划步数均近似等于后者的一半。仿真试验结果表明，基于扩展状态规划算法能够减少无效的规划步数，降低规划搜索时间，有效地提高算法的求解速度。

图5 规划步数结果曲线Fig.5 Computational results of planning steps

5 结 论

本文针对深空探测器任务规划中系统功能复杂、状态转换频繁且并非瞬时完成等问题，引入过渡状态的定义，并在此基础上提出了扩展状态的概念，缩减了问题搜索空间，优化了规划搜索过程。通过分析扩展状态的结构特点，设计了过渡状态挑选策略，并提出基于扩展状态的规划搜索算法。最后针对深空探测器任务规划系统进行建模仿真，并选用Europa算法进行对比实验。数值仿真结果验证了本文的算法能够有效地减少规划过程中的规划步数，提高任务规划的效率。