基于状态差异的火星巡视器快速任务规划修复方法

陈 超，徐 瑞，李朝玉

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

引 言

由于距离地球遥远，火星探测器与地面站之间的通信存在3～20 min的长时延，严重影响着任务的成败。火星探测器需具备高度的自主能力，例如高增益天线的自主指向、利用星敏进行姿态校准、在线数据的存储与转发，以及在时间和资源约束条件下活动的合理安排等[1]，以降低地面依赖性、缩短任务周期。自主任务规划技术可实现这一目标[2]。现有文献已经从动作[3]、资源[4]、时间线[5]等多个角度对自主任务规划技术进行研究。但目前人类对火星的认知不全面，火星表面地形的变化、土壤的坚硬程度、岩石的大小等仍存在极大的不确知性，影响着巡视器执行任务的时间长短、消耗能量以及存储空间大小等，严重制约着既定规划的成功执行。例如，“探路者号”（Pathfinder）任务中的“索杰纳号”（Sojourner）巡视器就因为在先验规划过程中没有充分考虑到这些不确定性因素的影响，整个任务中大约有70%的时间处于闲置状态[6]。此外，风沙等突发事件、电子器件故障等意外事件，都会对任务的成功执行造成巨大威胁。因此，火星巡视器不仅需要具备任务规划能力，自主管理日常活动，更需要具备任务规划修复能力，自主应对执行过程中出现的执行失败情况，以增强自身的鲁棒性，提高任务回报率。

在应对突发事件导致任务规划执行失败的问题方面，存在两种策略：完全重规划和规划修复[7]。其中，完全重规划是指放弃已有的规划结果，重新决策出一个新的动作序列来完成任务目标，而规划修复是指通过增、删、替换、移动等操作，对已有规划结果进行修补来达成任务目标。虽然规划修复在理论上不一定比完全重规划简单[8]，但大量的仿真实验表明规划修复效率更高[9-12]。Scala等[13]基于巡视器动作模式的多样性，采用约束满足问题（Constraint Satisfaction Problem，CSP）求解技术，在规划执行失败时，通过动作模式重构完成任务规划修复。但是该方法不改变动作顺序及类型，无法处理一般的规划执行失败问题。Gallien等[14]将执行阶段设计成感知–修复–行动三阶段的循环过程，对执行任务过程中出现的错误，在限定时间内采用规划器推理得出相应的解，用于解决执行失败的问题。但是该方法采用偏序规划方法，效率较低。Guzman等[15]提出响应式规划（Reactive Plan，RP）方法，为执行体设计了一个响应式规划器，通过与任务规划器互相配合，并采用修复结构树来提高规划修复的速度。但是修复结构树的长度和深度需要通过机器学习获得，不能普遍适用于所有情况；并且即使修复结构树只包含少量动作，其中也会包含大量无用节点，这样会造成存储空间和搜索时间的浪费。

针对巡视器在火星表面执行任务过程中由环境不确定性和自身设备故障等引起的规划执行失败问题，本文提出了一种基于状态差异的规划修复方法（State Difference Plan Repair，RPDS），使巡视器能够迅速从失败中恢复正常。与响应式规划方法RP不同的是，本文不提前构建修复结构树以辅助规划修复，而是在执行失败后，利用不同状态之间的差异，有目的地生成搜索节点，并对扩展的节点根据谓词冲突进行筛选，从而删减搜索空间，加快巡视器规划修复的速度。

本文的结构组织如下：第一部分构建火星巡视器任务模型并引出部分状态的概念，为后续的方法描述奠定基础。第二部分提出基于部分状态的火星巡视器快速任务规划修复策略，为第三部分描述基于实际状态与部分状态之间的差异而设计的搜索空间删减方法建好框架。第四部分给出仿真测试结果和分析。最后给出本文结论。

1 火星巡视器任务模型

自主任务规划属于高层次的智能决策，在给定初始状态下找到满足约束并且能够完成任务目标的动作序列的一种技术[16]。本文假设火星巡视器的姿态、导航等系统具备一定自主能力，在接收各自的任务指令后，各系统能够以一定的方法完成指令。由此，定义如下几个方面的规划修复问题。

表1 火星巡视器模型中的活动及其含义Table 1 Activities in the Mars rover model and their meanings

图1 对岩石采样的动作模型示例Fig.1 An example of an action model for rock sampling

一般情况下，火星巡视器接收任务指令，进行任务规划，在获得规划结果后执行具体指令时，需要传感器感知环境信息并将其传回监控系统，用于观察和控制任务的执行情况。然而感知状态中含有许多与具体动作执行无关的冗余信息，影响任务规划修复的效率。例如，对于原位采样动作，感知状态中着陆器的位置、通信设备的占用情况等就不必要显示。因此，利用感知状态与动作执行的必要状态之间的差异，定义部分状态，在状态中直接提取与动作直接相关的信息，以减小任务规划修复的搜索空间大小，加快任务规划修复速度。

假定任务目标是对w2处的土壤进行采样分析并将分析结果传回着陆器，对应的动作序列ΠA及部分状态序列如图2所示。G0表示初始部分状态，G3为目标部分状态，图2中带下划线的谓词为下一个动作的前提条件。每个状态下的所有动作前提集合即构成一个部分状态，为规划修复提供可选修复目标。此时，若外界环境的发生改变或其它原因导致待执行动作的前提条件得不到满足，便可利用部分状态中来设计快速任务规划修复策略。

图2 规划的部分状态序列Fig.2 Partial state sequence of the plan ΠA

2 火星巡视器快速任务规划修复策略

在任务执行的过程中，火星巡视器将要执行动作的前提条件可能会因为环境的不确定性或者自身设备的故障而不再得到满足，执行效果达不到预期，从而被迫中止任务。任务规划修复就是在尽可能保留原有规划结果的前提下，运用一定技术和方法，使巡视器能够从失败状态中恢复正常、继续执行任务。相较于感知状态而言，部分状态包含未执行动作的必要条件，不含冗余信息，缩小了状态空间的规模，有利于快速完成任务规划修复。因此，设计基于部分状态的火星巡视器快速任务规划修复策略。

图3 任务规划修复策略示意图Fig.3 Illustration of mission plan repair strategy

火星巡视器快速任务规划修复策略的伪代码如图4所示。第1～4行对规划结果中的动作序列运用状态回退函数，通过计算得到部分状态集合G。以G为可选修复目标，引导修复操作。当巡视器监控到动作ak的前提条件被破坏而难以执行时，记此时的巡视器状态为S（第5行），未执行动作集合为PA（第6行）。其中，PA既是原规划结果中的动作序列，又是一个不完整的规划修复解。规划修复的要求之一就是尽可能地保留PA中的元素。第8～28行是整个策略的核心部分。从失败动作前提所在的部分状态 Gk−1开始，尝试寻找使PA一致的修复动作序列，即PA在当前状态S下能够得到应用。若不存在这样的动作序列，换到下一个部分状态，重复该过程。

图4 火星巡视器快速任务规划修复策略伪代码Fig.4 Pseudocode of fast mission plan repair strategy for Mars rover

在每次求解的过程中，构造一颗搜索树Tree以存储中间状态信息。Tree中的节点是部分状态，边是动作。其节点的生成和扩展通过回退函数完成，直至达到限制要求。图4中的策略采用宽度优先原则对树进行扩展，并对树的生长过程进行了限制，即树的深度需要小于可能扩展的部分状态数量+3（第15行，从第8行可知i的取值跨度为n–k+1，则可能扩展的部分状态数量也为n–k+1，深度限制加3即为第15行中的n–k+4）。通过限制树的深度，避免树的无穷扩展，缩小算法的搜索时间，以实现快速完成修复的目的。当扩展的节点在S下被满足时，通过节点和边的关系逆序追溯修复动作序列，对PA进行修补（第21行），返回修复解。若所有尝试都失败了，策略返回失败标志，通知巡视器调用规划器进行完全重规划或等待地面救援。

3 基于状态差异的搜索空间删减方法

在实际应用火星巡视器快速任务规划修复策略时，节点需要频繁地生成、扩展（第17～19行）。此时，若使用盲目搜索，无疑会增加问题求解的时间。相反，若能充分利用实际状态与部分状态之间的差异，设计相应的节点生成方法和冲突消解方法，有目的的生成和扩展节点，会减小搜索空间大小，从而缩短搜索的时间，提高方法的效率。

3.1 节点生成方法

在PDDL2.1的描述中，状态主要由谓词表示。当动作执行失败时，状态中只有部分谓词发生变化。因此，针对执行失败的动作，结合失败时的实际状态与部分状态之间谓词的差异，如图5所示，将部分状态分割成相同谓词和相异谓词两部分。修复时，忽略相同谓词，采用状态回退函数对相异谓词回退，进行后向搜索，有目的地扩展并生成搜索节点，可以减少扩展节点的总数，加快搜索效率。而在节点扩展的过程中，以相异谓词为起点进行回退后的状态可能会删除相同谓词部分，导致最终得到的修复解无法满足期望要求，从而诱发新一轮的搜索过程，降低修复效率。因此，在得到修复解之后，需要检查解的可行性：即在感知状态下模拟应用规划修复解后，判断推导的理论状态是否包含相应的部分状态，若包含，说明修复解可行，否则应该舍弃该节点继续处理下一个节点。

图5 基于状态差异的节点生成方法示意Fig.5 Node generation method based on state difference

3.2 冲突消解方法

图6 部分状态与回退状态之间的冲突示意Fig.6 Conflict between the partial state and the regressed state

通过分析可以发现，发生冲突的部分状态节点至少有两个名称相同但参数不相同的谓词成分，如at（r，w1）与at（r，p）。但名称相同而参数不同的谓词不一定构成冲突，例如描述巡视器载荷能力的谓词（supports?camera?mode），用于表征相机具有的功能模式，例如光谱成像、立体成像、红外成像等，这类谓词可以在同一个部分状态中并存而不产生冲突。因此，有必要针对火星巡视器，明确会引发部分状态节点冲突的谓词。在第1部分建立的火星巡视器任务模型中，易产生冲突的谓词是（at?rover?waypoint）和（at_lander?lander?waypoint），分别描述巡视器和着陆器的位置。由此，可以设计节点中的冲突消解方法如下：在判断节点是否存在冲突时，首先判断部分状态中是否存在可能引发冲突的谓词；若存在，再进一步判断其参数是否会引发冲突。冲突的部分状态自身就存在矛盾，所以在根据回退动作生成节点后，可以将自身冲突的节点删除，以减少要扩展的节点，进一步节省问题求解的时间。

4 仿真测试

为验证本文提出的基于状态差异的火星巡视器快速任务规划修复方法RPDS的有效性，设置如图7所示的仿真场景：存在4个地点w0、w1、w2、w3，各地存在岩石或者土壤样本；w0和w3之间、w3和w1之间、w1和w2之间道路互通，巡视器可以直接通过；目标object0和object1在4个地点方向均可见；初始状态下，着陆器L位于w0，巡视器R位于w3，任务目标是对w2的土壤进行采样并将分析数据传回着陆器、对w3的岩石采样并将分析数据传回着陆器、对object1拍摄高分照片并将数据传回着陆器。利用Sapa规划器[18]对该问题进行求解，得到的规划结果如图7中的下部分所示。由此，巡视器就可以在不同时刻执行对应的动作以完成任务目标。同时，根据定义2中的状态回退函数 Γ (s1,a)，可以计算得到部分状态集合。当该规划执行失效时，触发RPDS进行规划修复。

图7 仿真场景示意及规划结果Fig.7 Simulation scenario and its planning results

考虑火星巡视器领域特点，其规划执行失败类型主要分为两种，一是固有条件的破坏，如w1和w2之间的道路被破坏，导致巡视器无法直接从w1到达w2；另一种是可变条件的改变，如巡视器位置的变化、电能的存储变化等。当规划失效时，例如，若由于某种原因w3和object1之间不可互见，使得第1个动作（校准相机）的前提条件被破坏，从而使巡视器处于闲置状态。巡视器的感知状态与规划结果中的预估状态存在差异，RPDS就利用这些不同，有目的地向着对应的部分状态生成并扩展节点，并通过不断地搜索和冲突消解，完成规划修复问题的求解。

仿真中，通过在不同执行时刻手动植入意外事件来模拟规划执行失效，并采用RPDS进行修复。仿真测试结果如表2、图8和图9所示。其中，RP为文献[15]中的方法，在该仿真算例中，构造的修复结构树长度为3，深度为4。代码语言为Java，测试环境为I7-6 700 CPU@3.40 GHz和 8 GB内存。

图8 不同方法的运行时间对比Fig.8 Comparison of operation time of different methods

图9 不同方法的扩展节点数对比Fig.9 Comparison of the number of expansion nodes in different methods

表2 不同方法测试结果对比Table 2 Comparison of test results of different methods

从仿真结果可以看出，本文提出的基于状态差异的任务规划修复方法RPDS不仅能够处理固有条件被破坏、可变条件被改变的动作执行错误，而且相较于RP方法，既减少了因为构造修复结构树而增加的节点扩展数，且在大部分情况下缩短了修复时间，尤其是对于回退目标状态包含失败动作的前提条件情况，RPDS能够提升大约62%的效率。此外，与重规划方法Sapa的结果比较，RPDS提高了巡视器从执行失败中恢复的效率。

采用文献[11]中稳定性的评价方法，统计两个规划结果中互不相同的动作数之和，从表2的最后两列结果可知，RPDS在快出给出修复解的同时，仍然能够以较少的动作保障规划稳定性。从第10例规划修复问题可以看出，相较于文献[15]中提出的规划修复算法RP，本文提出的方法RPDS能够处理更多的规划执行失败情况。可能的原因如下：RP在每次修复时，都是将已有规划结果按固定长度划分后，在限定的搜索空间内，通过后向搜索找到新的动作序列完成修复。那么对于每段中处于右端点的动作，在该限定的搜索空间内没有对应的子节点，从而导致RP无解的情况，或者该动作能够在下一段规划结果中找到规划解，但是由于搜索深度的限制，RP仍然无法给出对应的修复方案。而对于本文提出的RPDS方法来说，直接利用整个已有规划结果，从中提取部分状态，为规划修复提供修复目标，而不需要提前建立小范围内的搜索空间，从而避免了规划结果分段所导致的断层节点动作无法修复的问题。

RPDS能够快速解决问题，主要是因为它能充分利用已有规划中的动作信息，构建部分状态，明确其与实际状态之间的差异，有目的地进行搜索，同时在已知回退目标状态的前提下，通过节点生成和冲突消解方法的控制，能够减少节点扩展数、缩减搜索空间的大小，从而提高修复效率。

5 结 论

火星表面凹坑、凸起、坡度和石块的随机分布，土壤松软、厚度不均等复杂地貌，以及自身电子设备的意外故障等，均容易导致火星巡视器任务执行失败。针对该问题，本文提出了适用于火星巡视器的基于状态差异的快速任务规划修复方法RPDS，完成了以下工作：①利用火星巡视器的感知状态与动作执行的必要状态之间的差异，在已有规划的基础上，构建了不同时刻的部分状态，为规划修复提供可选修复目标；②基于部分状态，给出了火星巡视器快速规划修复策略；③利用部分状态和实际状态之间的差异，提出了基于状态差异的搜索空间删减方法，有目的性地生成、扩展节点并消解冲突。通过仿真实验验证，RPDS能够快速有效地完成任务规划修复，并能够保障规划稳定性，可以为航天器自主快速应对执行时的突发事件提供技术支撑。