航天器自主任务规划修复技术研究进展

徐 瑞，陈 超，崔平远，朱圣英，徐 帆

(1. 北京理工大学宇航学院，北京 100081；2. 深空自主导航与控制工信部重点实验室，北京 100081；3. 宇航智能控制技术重点实验室，北京 100854)

0 引 言

智能规划通过采用知识推理方法来寻找从指定状态到达目标状态的活动序列[1]，是希望系统能够通过执行这些活动完成任务。虽然目前国内外关于航天器自主任务规划的研究比较多[2-6]，但实际应用比较少，其中一个重要原因是将规划与执行分开[7]。由于航天器所处环境存在动态性、不确定性和不可控性，且任务目标在航天器运行过程中可能发生变化[8]，继续执行原有任务规划结果可能无法达成目标。此时，通过地面遥测遥控的方式已经很难满足航天器控制的实时性和安全性要求。例如火星探路者号就由于未考虑到实际执行时的环境影响，任务规划结果执行失败[9]。因此，为了增强航天器自主能力、提高航天任务回报率，需要将规划与执行结合在一起，智能处理规划结果执行失败的问题[10-12]。

在执行过程中，若外界环境发生变化(如火星车行进过程中刮起了风暴)，或者目标发生变化(如火山突然爆发需要观测)，或者动作执行失败(如太阳帆板未能展开)，原规划结果都不能保证任务被顺利完成。此时，存在完全重规划、规划修复两种方法使航天器继续执行任务。其中，完全重规划是指抛弃已有规划结果，重新搜索抵达目标的动作序列；而规划修复是指对已有规划结果做一定修改来达成目标。考虑到正常的星上规划过程需要耗费大量时间，且原有规划结果给执行器或者其它智能系统已经承诺一定资源或者其它信息，有效地利用已经生成的规划结果显得更加合理。此外，对于有人参与的复杂任务，若抛弃原有规划结果重新生成一个新的规划结果，技术人员势必耗费时间去熟悉了解，在一定程度上影响任务的执行效率。综上所述，规划修复技术比完全重规划技术更具有应用前景。

面对航天器自主控制和自主运行的发展趋势，开展航天器自主任务规划修复技术研究具有重大的理论意义和现实意义。本文首先给出航天器自主任务规划修复技术的定义，指出其难点，接着梳理国内外的研究成果，然后对规划修复方法的评价标准——规划稳定性进行了总结，最后概括分析了各种方法的优缺点，并对未来航天器自主任务规划修复技术的研究方向提出了发展建议。

1 航天器自主任务规划修复技术的定义和难点

综合考虑航天器执行任务的特点与任务规划修复方法的特征，给出航天器自主任务规划修复技术的定义如下：

定义1. (航天器自主任务规划修复技术)航天器自主任务规划修复技术是指在航天器任务规划结果执行失败时，通过智能搜索和智能推理方法，在原有规划结果的基础上，充分利用航天器专家知识，使航天器从失败中恢复，从而得以继续执行任务的一项技术。该技术只能处理既定领域下的规划执行失败情况，而不能应对模型之外的故障情况，即需要新知识才能完成修复的故障。

虽然航天器自主任务规划修复技术只在模型之中解决问题，但它将规划和执行有机结合，既可以利用人工智能的方法在任务层面统筹全局，提前预测、修复故障，增强系统的可靠性；又可以充分利用星上资源，在当前约束条件下尝试所有可能的故障修复方法，提高系统的执行效率。因此发展航天器自主任务规划修复技术势必成为提高智能航天器鲁棒性的必然要求和趋势。

虽然在理论上规划修复不一定简单[13]，但试验结果表明规划修复效率更高[14-17]。然而由于航天器领域的特殊性，航天器自主任务规划修复技术存在如下难点：

1)及时性。航天器资源有限且任务周期一般固定不变，当任务尤其是对于观测彗星撞击等具有强烈时间要求的任务执行失败时，需要航天器能够在任务截止时间之前，快速给出有效的修复方案。

2)环境不确定性。环境不确定性难以避免，一方面影响动作执行，另一方面需要航天器根据不同情况给出不同修复方案。

3)目标动态性。航天器执行任务过程中，目标可能发生动态变化，如新的观测请求。此时，航天器自主规划修复技术需要考虑未执行的动作序列是否有利于完成目标，以及如何利用该序列来完成新目标。

4)系统耦合性。航天器各子系统之间存在耦合性，使得航天器动作之间存在并行性。当任务执行发生并发性动作冲突时，需要航天器能够综合考虑系统之间的关系，在尽可能不破坏已有约束的前提下，给出合理高效的修复方案。

5)资源约束的动态复杂性。航天器上存在离散资源(载荷、子系统等各种设备)和连续资源(电能、燃料等)。对于航天器任务尤其是航天器组网任务来说，资源占用或者资源消耗情况在实际执行时才能确定，而在规划时只能给出资源消耗的大致范围。当任务执行发生资源冲突时，航天器需要考虑规划结果中已执行部分和未执行部分的资源利用、分配情况，在资源总量一定的前提下给出合理有效的资源修复方案。

6)动作时间连续性。每个航天器活动都有一定持续时间，而且该持续时间可能也是变化的(如航天器姿态转动需要的时间长短是由初始姿态和目标姿态之间的差值决定)，且由于环境存在不确定性，部分动作的持续时间是不可控的(如着陆器的行进时间与地形地貌等因素有关)。当动作执行发生时间冲突时，比如动作过早发生、过早完成或者推迟发生、推迟完成等，需要一个良好的修复机制来保证任务继续执行。

2 自主任务规划修复技术研究现状

当航天器执行任务出现小范围偏差，即动作序列局部失效，且不需要额外的设备或知识时，自主任务规划修复方法可以有效地使航天器从失败中恢复。根据方法内容，将目前的规划修复技术分为下面五类：规则匹配型、局部调整型、删除/求精型、状态转移型和构造新问题型。每类所包含的修复方法以及各自的特点如表1所示。

表1 规划修复方法分类Table 1 Classification of plan repair methods

2.1 规则匹配型修复策略

规则匹配型方法事先定义一系列的错误修补规则，每一个规则描述对应的任务在执行失败的情况下应该如何进行修复。当实际执行失败时，便从规则集合中搜索解决方案，其算法流程如图1所示。规则来自专家经验，如“若太阳帆板未能正确对日定向，则调整航天器姿态”。应用该技术的典型系统有CHEF系统[18]和O-Plan系统[19]。CHEF中的规则是对错误的解释，而O-Plan中的规则是一些提前定义好的规划。当执行失败时，CHEF自动构建解释，包括导致失效的步骤信息、状态信息以及这些失效步骤试图实现的目标集合。基于该解释，CHEF从修复规则集合中选择一个修复策略子集合进行实例化，然后从该策略子集合中挑选最佳的修复策略。而O-Plan对于执行失败的动作不采用失败的解释方法，而是从一些预定义的规划中挑选一个规划来满足当前失效动作的效果。当失败时，执行停止，一个修复规划被插入执行。由于规则是根据经验制定，该策略只能应对已知问题。

2.2 局部调整型修复策略

规划和规划修复通常被认为是一次性完成的，即规划器立即给出相应的动作序列。然而实际上，在动态多变的环境中，规划需要多次进行。此时，充分利用之前的规划过程和规划结果，可以完成修复，如图2所示。

2.2.1基于规划库的局部调整方法

保存之前的规划结果形成规划库，其表示方法既有逻辑表示[20]，也有框架表示[21]；其储存模式既可以保存整个规划结果，如基于案例的规划方法[22]，又可以保存部分规划结果，如宏动作表示的规划修复方法[23]。执行失败时，基于案例的规划方法通过规划结果提取、规划结果重用、规划结果修订等一系列操作，从规划库中提取相似问题的解并作一定修改，使得该解能够解决当前问题；而采用宏动作表示的规划修复方法在规划库中只包含领域中经常出现的部分规划，并引入宏动作对库中的规划进行管理。通过重新定义宏动作的前提和效果，实现了多个宏动作之间的匹配，完成规划修复。

尽管有多种方法提高规划库的规划修复效率，如Fukushima等[24]的正交表搜索，但航天器星上资源极其有限，其效率仍待进一步提高。

2.2.2基于动作模式重构的局部调整方法

当任务没有明确的质量要求时，通过调整动作的部分参数，可以在不改变原有任务规划指令序列整体的基础上，完成任务规划修复。例如，航天器成像动作参数可以由高分辨率设置成低分辨率，数传动作参数可以由高频传输改成低频传输。这样，既不影响原有指令序列的完整性，又能完成任务规划修复。因此，Scala等[25]提出ReCon方法，将原规划结果转换成约束可满足问题(Constraint satisfiability problem, CSP)模型，在执行出现资源冲突时，对资源信息进行更新并利用CSP求解器，调整动作模式以解决该问题；而当出现其它异常时，中止执行过程，进行完全重规划。显然，该方法只适用于对目标没有具体要求的任务修复，对于具有明确质量要求的任务，如获得高分照片，该方法会失效。

2.3 删除/求精型修复策略

规划结果的执行是动作有序完成的过程。当执行出现故障，找到失效动作，将其删除，并用新的动作序列代替该失效动作的效果插入到原命令序列中，即为删除/求精型修复策略。如图3所示，若相机因外界扰动未能校准，那么成像动作会因为相机校准的前提无法得到满足而失效。此时，删除该成像动作，原命令序列变得不再“完整”，即不一致。通过规划求精方法[26]寻找使命令序列一致的解即为规划修复解。例如，航天器可以调整姿态，重新校准相机，再调整姿态对目标进行观测，接着继续执行原指令序列。若删除成像动作后通过求精无法找到解，扩大动作失效范围，继续尝试求精，直至扩展到目标状态。例如，若相机损坏无法校准，则跳过观测任务，直接进行下一探测任务如采样，或者直接返回规划修复失败标记。

根据规划求解方式的不同，在确定失效动作范围时，存在规划图、启发式和分层任务网络(Hierarchy task net, HTN)三种不同的删除/求精型任务规划修复方法。

2.3.1基于规划图的删除/求精方法

规划图是一种特殊的数据结构，命题层和动作层交替向前扩展，直至达到不动点。基于规划图的规划修复方法将当前失效动作的删除/求精称之为局部搜索，而将扩展的失效动作范围求解称之为系统搜索[14]。该方法优先尝试使用局部搜索来解决执行失败的问题。在求解过程中，由于失效动作被删除，原规划结果出现缺陷，具体包括互斥动作以及不被支持的前提条件或者目标。通过添加动作、给动作排序等方法逐一解决暴露的缺陷，找到所有的修复方法，然后引入代价函数，最终确定最优的规划修复动作序列。但由于规划图只能面向完全实例化的动作而无法处理框架型动作(部分实例化或者完全未实例化的动作)，基于规划图的修复技术需要耗费大量的计算时间和存储资源来使动作完全实例化。

2.3.2基于启发式的删除/求精方法

启发式估计当前搜索节点到目标节点的代价值，用于挑选扩展节点中最优的那个，指导规划的搜索方向。Krogt等[27]以当前规划结果为根节点，通过构建“移除树”这种数据结构，设计启发式，以选择合适的移除树并对其进行生长、合并操作，从而确定当前规划结果中应该删除的动作范围。但是这个修复过程只能处理初始条件或者目标状态改变的情况，无法处理中间过程失效的情况。对此，Arangú等[28]通过核实和修复，提出了一种通用的修复方法，对其进行了完善。基于启发式的规划修复方法将规划和规划修复技术联系在一起，但是由于通过试错法逐层扩展移除树，耗时且具有一定盲目性。

2.3.3基于HTN的删除/求精方法

HTN规划通过行动分解方法，不断地分解、改进规划问题，直至达到系统能直接执行的原子行动。在确定失效动作范围时，基于HTN的规划修复方法存在两种方式：局部型和全局型。局部型在失败动作的周围添加动作，如PRIAR[29]。PRIAR利用节点之间的因果关系构建验证结构，通过它来明确失败的位置和具体特征，并根据这些特征选择相应的修复策略。全局型在整个计划之中搜寻失效的动作的范围，然后进行删除/求精操作，如Replan算法[30]。Replan用演绎树(derivation tree)记录HTN规划结果的生成过程。当执行失败时，对应于演绎树上一个失效的叶节点，包含该节点的最小子树被删除，然后不完整的部分经过HTN规划器的求精操作变得完整，规划修复也就完成任务。在确定最小子树的时候，采用试错法逐层扩展，直至找到解或者扩展到整个任务网络。该方法有一定应用[31-32]，但是仍然采用试错法确定动作失效范围，影响规划修复的效率。

2.4 状态转移型修复策略

动作包含前提和效果，若其前提在某一状态下得到满足，那么执行动作就能将其效果作用于该状态，从而实现不同状态之间的转移。在动作执行失败时，通过状态转移，寻找合适的动作序列，代替原效果，即完成规划修复。例如，动作navigate(l1,l2)表示火星车由地点l1前进到l2，其前提条件包括火星车位于l1、电源充足，其效果为火星车位于l2。若在即将执行该动作的时候发现电池能量不够，该动作不应被执行。此时，若应用状态转移型修复策略，需搜索效果为使电池充电的动作，来满足navigate的前提。如图4所示。基于这一思想，Guzman等[33]采用“规划窗口”限制规划修复的长度和深度，将整个规划结果分成几部分并对各部分提前计算修复结构体。当任务执行失败时，在修复结构体中寻找一条路径到达指定状态；当不存在这样的路径，进行完全重规划。

而在开始进行修复之前，对完全重规划策略和规划修复策略进行评价选优，往往能够提高规划修复的效率。为此，Garrido等[34]将执行失败后的原规划结果P分割成前、后两部分，即P1和P2，通过采用忽略动作负效果的松弛策略来分别计算完全重规划策略的代价值Ereplan和规划修复策略的代价值Erepair，如式(1)和式(2)所示。其中，C(X)表示计算规划结果X的代价值函数。

Ereplan=C(P)+0

(1)

Erepair=C(P1)+C(P2)

(2)

该策略利用后向搜索，在规划修复时速度快，但是在确定需要到达的子目标状态时，仍通过试错法尝试，搜索效率可进一步提高。

2.5 构造新问题型修复策略

对于给定的任务，规划器能够给出该问题对应的有序动作解，即计划。当任务执行失败时，从原有计划中提取相关信息构造新问题，再次利用规划器也可以完成规划修复，如图5所示。提取的信息包括可用动作、动作间的约束等。

2.5.1基于数字宏动作的修复方法

宏动作是几个互相联系的动作集合。宏动作结合数值型变量形成的数字宏动作，可以用来处理实际任务执行时资源消耗冲突和动作失效的问题。例如对于观测任务，可将姿态调整、相机校准、姿态调整、目标成像这四个动作看成一个宏动作，而其中每个动作均会消耗一定的电能。类似地，从原计划中提取若干个这样的宏动作集合，并把它们作为附加内容加入到规划领域动作知识中，再利用规划器对失败问题求解，也可完成任务规划修复。而关于如何提取有效的数字宏动作，Scala[35]作了详细的研究。

2.5.2基于PSP的修复方法

航天器的规划结果中包含对航天器各子系统或其他航天器的承诺。这些承诺既包括各系统之间的协议，如相机工作的时候主发动机应关闭，也包括规划修复技术中的稳定性，即动作稳定性(新旧计划之间的动作序列组成尽可能相似，如火星车在前进过程中电能不足导致动作执行失败，未能抵达目标位置，满足动作稳定性要求的修复解应该是打开太阳帆板，给电池储能，待电充满后，继续执行剩余指令)和因果链稳定性(新旧计划之间的动作序列因果关系尽可能相似，如原计划中航天器先转向A方向进行相机校准再转向B方向进行观测，那么满足稳定性要求的新计划应该尽可能保留这一条因果链)。通过搜集这些承诺信息，并把它们作为软目标(尽可能完成的目标)，加入新问题之中，再利用PSP规划器进行求解，就可以完成规划修复[36]。

构造新问题的规划修复方法从原有计划中提取有用信息，有效地缩小新旧计划之间的差异，提高规划稳定性。但是对于航天器尤其是多星来说，系统组成复杂且耦合性强，若任何小错误都需要利用任务规划器来修复，无疑会增加任务规划器的压力。

3 航天器任务规划稳定性分析

动态环境下执行计划可能出现失败，此时规划修复方法比完全重规划方法更具优势。而规划修复方法离不开稳定性的要求。

定义2. (航天器任务规划稳定性)使用规划修复方法来解决航天器任务规划结果执行失败的问题，如果新计划中包含原计划的关键信息，如动作的种类、顺序、数量等，那么就称该新计划是规划稳定的，且新旧计划之间相同部分越多，稳定性越强。

在规划修复时遵循稳定性的要求，可以通过模式诊断识别动作执行失败的原因，获取关键的约束信息，并在无法成功修复时，保证系统能够处于安全状态[37]；也可以将原计划中的信息作为软约束加入到问题之中，用PSP技术进行求解；还可以将原计划片段化，通过组合的方式，达到充分利用原计划信息的目的[38]。

然而这些都是定性地描述稳定性，缺乏统一的定量标准来评价稳定性大小。Fox等[39]通过定义两个计划之间的距离来度量修复计划的稳定性大小，如式(3)所示。

S(PB)=nα+nβ

(3)

式中：S(PB)表示计算计划PB稳定性大小的函数。若用PA表示原计划，PB表示修复计划，则nα表示在PA中但不在PB中动作的数目，nβ表示在PB中但不在PA中动作的数目。

而Garrido等[34]通过百分比的方式来度量修复计划的稳定性大小，即PB中属于PA的动作的数目nη与PB中动作总数nω的比值，定义如下：

S(PB)=nη/nω

(4)

上述两种定量描述稳定性的方法虽然能够给出规划修复稳定的评价标准，但并未考虑到计划中动作的顺序关系。Scala等[25]将规划修复看成是在原有计划PA的基础上，通过一定的修复操作得到修复计划PB的过程。该修复操作被归纳为插入Oadd、删除Odel、替换Oremod和交换Oswap四种，其中替换是指改变动作的模式，交换是指改变两个连续动作之间的顺序。每种操作依次被赋予代价值α,α,γ,θ，且满足关系γ≪α<θ<2α，那么将计划PA转换成PB的代价EPA→PB如式(5)所示：

EPA→PB=α·Oadd+α·Odel+γ·Oremod+θ·Oswap

(5)

若用ER表示一个参考转换代价值，通过完全移除PA中的动作之后，再把所有动作插入到PB中来获得；用Et表示所有从PA转换成PB代价值中最小的代价值，那么PB的稳定性大小S(PB)就被定义为：

S(PB)=(ER-Et)/ER

(6)

但是，高稳定性不一定能够保证高质量的规划结果[40]。原有计划中除了包含动作的种类、顺序、数量等信息外，还包括因果链、合作关系等约束信息。因此，在以不考虑约束影响的稳定性评价方法为导向的情况下，搜索规划修复解时很有可能找到一个动作序列相似度高但约束被极大破坏的解，影响计划的执行效率。

4 航天器自主任务规划修复技术总结和发展建议

在任务执行过程中出现执行失败情况时，航天器自主任务规划修复面向任务目标，应用一定的技术方法，生成修复命令序列，使航天器恢复正常。不同的任务规划修复方法应用不同的策略，完成规划修复，各自的优缺点总结如表2所示。

分析各类任务规划修复方法，不难发现，它们都是通过修改领域动作集合和子目标来达到任务规划修复的目的。因此，可用规划修复问题来统一描述各类规划修复方法。

定义3.(规划修复问题)一个规划修复问题是一个三元组P=(O,α,γ)，其中，O表示可用操作集合，α表示动作执行失败时的状态或者未来可能会失败的状态，γ表示通过规划修复能够达到的状态。

表2 现有多种规划修复方法的优缺点对比Table 2 Comparison of advantages and disadvantages of existing plan repair methods

规则匹配型修复策略中的O通过规则定义；局部调整型修复策略中的O源于历史计划；基于数字宏动作的修复方法中的O是从原计划中提取的数字宏动作和原有动作的组合；删除/求精型修复策略和状态转移型修复策略的γ是通过试错法确定的、能够使规划修复完成的某个状态；基于PSP修复方法中的γ是继承原计划约束的软目标。

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

1)规划修复的可行性研究

规划修复的可行性，即在修复之前，判断该问题是否可以通过规划修复方法解决。因为规划修复不一定能够保证找到执行失败的解决方法，且航天器资源有限，同时任务有效时间确定，若花费太多代价用于尝试求解一个不可能通过规划修复解决的失败问题，势必影响任务完成的质量和效率。因此有必要在对执行失败的任务修复之前，判断该问题的规划修复可行性。

2)规划修复的及时性研究

航天器资源有限且任务周期一般固定不变，当任务出现执行失败情况时，会影响任务的完成情况。如何保证在任务截止时间之前，航天器能够采取有效的修复方案从失败中恢复，就需要修复的时间尽可能得短。

3)确定动作失效范围方法的研究

无论是删除/求精型规划修复方法还是状态转移型规划修复方法，在寻找动作失效范围时，都是采用试错法从当前动作开始，删除当前动作，然后尝试求精操作。如果一个解决方法需要删除原规划结果尾部的动作，那么通过试错法的方式必定要浪费很多搜索时间。如果能够精准有效地确定动作的失效范围，就会大大缩短规划修复的搜索时间，提高规划修复的效率。

4)系统级规划修复的研究

在实际环境中，尤其是动态环境中执行任务，当遇到执行失败的情况，应用规划修复方法解决该问题时，存在局部和系统两种策略。局部策略只修复当前暴露的问题，修复完成后，就让智能体开始执行新计划；系统策略此外还检查当前状态下未执行的部分是否存在隐患，并解决整个计划的缺陷，从而使得规划修复完成后，生成的新计划鲁棒性更强。目前存在的规划修复方法大都采用局部策略，只解决当前出现的问题，而对系统策略研究较少。

5)并行动作、时间和资源冲突的研究

航天器实际执行任务时，除了必要的动作信息之外，还需要时间和资源的参与。无论资源还是时间在执行时出现冲突，都会导致整个任务的失败。而目前针对并行动作、时间冲突和资源冲突的规划修复方法研究较少，限制了自主规划技术在实际航天任务中的应用。

6)规划稳定性的评价标准研究

规划修复方法的好坏需要通过一定的评价标准来判断，其中一个评价标准就是规划稳定性。规划稳定性的评价既要考虑两个计划之间的动作数量、动作之间的顺序关系，也要考虑到计划中包含的约束关系，并采用定量方式以便于普遍接受。

5 结 论

航天器自主运行是未来航天发展的必然趋势。本文阐述了将规划与执行融为一体的航天器自主任务规划修复的必要性和难点，将自主任务规划修复技术归纳为规则匹配型、局部调整型、删除/求精型、状态转移型和构造新问题型五类分别进行描述，分析了规划稳定性的定量评价方法，并将规划修复技术总结为对规划修复问题元素的部分修改。

实际的航天任务规划与执行是动作、时间、资源三者相互作用的复杂过程，然而目前少有关于多因素影响下的任务规划修复方法理论研究。因此未来的航天器自主规划修复技术研究重点应该在于动作、资源和时间方面的复合修复策略研究、规划修复的可行性和及时性研究、高效的失效动作范围确定方法研究以及规划稳定性的定量判定标准等研究方向。