深空探测器自主规划技术研究进展

徐 瑞，李朝玉，朱圣英，王 棒，梁子璇，尚海滨

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

引 言

深空探测指人类对月球及以远的天体或空间环境开展的探测活动，作为人类航天活动的重要方向和空间科学与技术创新的重要途径，是当前和未来航天领域的发展重点之一。由于深空探测任务具有探测目标远、飞行时间长等特点，会出现上传指令延迟、星体遮挡等问题，依靠地面测控站对探测器进行遥测遥控的方式难以满足探测器控制的实时性、鲁棒性和安全性等要求。自主技术是保证探测器在深空环境下安全可靠运行的关键技术之一，也是未来深空探测技术发展的重要方向，而自主规划技术是实现探测器自主运行的核心技术之一。

自主规划是人工智能领域较早的研究方向之一，可以追朔到1957年Newell和Simon的问题求解程序（General Problem Solution，GPS）、1969年Green的QA3系统。1971年Fike和Nilsson的STRIPS系统在智能规划领域具有划时代的意义[1]，将状态表示为命题的集合，通过操作集合中的命题来实现状态的改变，其所采用与文字相关的术语至今仍被使用。为解决经典规划问题，如着色问题和航空货物运输问题，学者们提出了多种形式规划方法，包括前向状态空间搜索、图规划、分层任务网规划等。将规划问题转换为约束可满足问题、命题可满足问题等形式，利用已有的约束推理技术等进行求解也是一种常用的规划方法。然而，传统规划方法难处理具有时间、资源、参数等复杂约束关系的深空探测器规划问题，因此，航天大国纷纷开展研究并取得一定的成果。

自主规划技术在20世纪90年代首次在深空探测任务中得到应用和验证。在初期应用中，探测器只有部分系统具有自主性，例如美国发射的“卡西尼号”（Cassini）探测器和“NEAR”探测器，在一定程度上减少了地面人员的任务操作。全局自主在“深空一号”（Deep Space One）探测器中得到了飞行验证[2]，利用研制的“远程智能体”（Remote Agent）软件系统实现了探测器自主任务管理、任务规划、自主执行、状态监测等，在1周的飞试验行中成功验证了其可靠性，可以在没有地面干预的情况下完成自主任务规划和运行，其应用大大降低了操作费用。2003年，美国国家航空航天局（National Aeronautics and Space Administration，NASA）在地面采用MAPGEN（Mixed Initiative Activity Plan GENerator）规划器对“火星探测漫游者”（Mars Exploration Rover，MER）任务中火星车科学设备进行自主规划和调度，并计划在2020火星探测车实现星载自主调度，然而迫于进度压力，目前未能实现[3]。至今，NASA开发的自主调度与规划环境系统（Automated Scheduling and Planning Environment，ASPEN）、可扩展通用远程操作规划框架（Extensible Universal Remote Operations Planning Architecture，EUROPA）和欧洲航天局（European Space Agency，ESA）开发的先进规划与调度框架（APSI）先后服务于“地球观测一号”（Earth Observing One）、火星探测车等多个航天任务[4]。

深空探测器自主规划技术的研究对于未来的空间任务主要具有如下几方面的意义[5]：

1）减少地面干预，降低探测器操作费用以及对航天测控网络的需求；

2）应对深空任务中的不确定性，增加任务执行的可靠性；

3）采用高级任务指令，增加地面与航天器系统的可交互性；

4）通过规划对系统的各种资源进行合理分配和利用，提高任务的回报；

5）规划系统可以灵活地运用到今后的航天器的设计和研制中，缩短小型航天器的研制周期。

深空探测器自主规划技术的应用将会给深空探测领域带来革命性的变化，掌握该技术对促使我国空间以及航天技术水平的提高具有重要意义。

本文明确了深空探测器自主规划技术定义的基础上，介绍了目前深空探测器自主规划技术面临的挑战，总结和分析了自主规划中的关键技术，并给出未来深空探测器自主规划技术的发展方向。

1 深空探测器自主规划内涵

1.1 定义与内涵

深空探测器自主规划技术是根据对空间环境的感知和认识、探测器自身的能力和状态，利用计算机软件技术、人工智能理论方法等，依据一段时间内的任务目标，对若干可供选择的动作、可用资源、约束关系等进行推理，自动地生成一组时间有序的动作序列，称一个“规划”（plan）。该规划一旦执行，便可以将探测器的状态成功转移到期望的目标状态[6]。

深空探测器任务规划问题Φ用一个五元组描述

3）活动的执行最终结果状态集合包含目标集G。

1.2 规划技术面临的挑战

由于深空探测器系统复杂、约束耦合、活动并行、运行环境不确知等特点，传统的自主任务规划技术已无法适用于深空任务。深空探测器自主规划问题面临新的挑战[7]，其中包括以下几个方面。

1） 耦合时间约束。多数活动必须在特定时间窗口进行，比如通信活动必须按照一定的顺序执行，同时部分活动需要并行执行。

2）有限资源 。探测器的能量和存储能力有限，资源需要在一定的时间区间内进行管理和分配，以保证探测器的安全运行和任务的完成。

3）复杂任务目标 。需要实现的目标较多且价值和重要性不同，应进行合理安排，得到最大的科学回报。同时，部分规划任务需要找到最短路径或者燃耗最小的规划序列来实现目标。

4）自主执行不确定性。转移到指定地点、完成维护操作或者装配某结构的时间具有不确定性。

2 关键技术发展及分析

2.1 自主规划和执行框架

为了降低深空探测器对地面的依赖、提高探测器的自主性，自主任务规划与执行不可或缺。作为自主系统的关键部分，任务规划为探测器未来一段时间内的活动序列做出决策；执行系统按照该活动序列驱动探测器的执行机构实现不同功能，并将动作完成情况和环境感知信息反馈给任务规划。

由于深空环境的不确知，探测器任务执行存在复杂情况，简单地根据传感器感知的信息而做出机械响应的方式[8]并不适用。因此，基于决策和快速响应的混合结构被广泛采用[9]，主要存在如图1所示的两种自主规划框架。在由决策层、执行层和控制层组成的三层结构中，决策层负责顶层任务规划并将规划结果传给执行层，同时接受返回的执行情况并对异常做出重新决策；执行层负责指令展开和执行结果传递；控制层负责驱动对应的执行机构完成指定的动作，并将动作执行情况传回执行层。“深空一号”的“远程智能体”采用的就是这样的三层结构。

图1 不同的自主规划执行框架图Fig.1 Different automated architectures of planning and execution

在三层结构的基础上，美国的喷气推进实验室（Jet Propulsion Laboratory，JPL）提出了由功能层和决策层组成的两层控制框架CLARAty[10]（Coupled Layer Architecture for Robotic Autonomy）。其中，决策层包含基于声明型模型的规划调度模块和基于程序型模型的执行模块，根据任务要求生成探测器的规划结果；功能层包含具体星上器件执行动作的指令序列，能够预测各自的能源消耗信息并将其发送给决策层。类似地，CASPER（Continue Activity Scheduling Planning Execution and Replanning）[11]和CLEaR（Closed-Loop Execution and Recovery）[12]也将规划调度和执行都放入决策层，并在“勇气号”（Spirit）等探测器上实现了应用。

考虑到深空探测器是由多子系统构成的复杂系统，在设计自主执行框架时，可以结合工程实际，采取如图2所示的框架。其中，决策层中的任务监控器接收地面控制中心制定的任务要求并进行命令转化，交由任务规划器处理，同时接收处理后的规划结果，控制活动向执行层传达；执行层根据具体的指令要求，控制并协调功能层中不同模块之间的执行过程；功能层由姿态规划、轨迹规划、轨道设计等不同功能的模块组成，根据指令要求具体计算探测器详细的活动参数，并驱动执行机构执行。

图2 深空探测器自主规划执行框架设计Fig.2 Autonomous architectures design of planning and execution for the deep space probe

无论采用何种自主规划执行框架，规划和执行都是相互联系、彼此影响、共同作用，此时，规划器能够根据深空探测器当前的状态信息和环境变化、执行异常等突发事件，给出具体的决策方案，例如哈勃望远镜任务规划[13]，太空飞船有效载荷规划[14]，基于ASPEN设计的航天器操作规划[15]等，使探测器能在复杂动态的环境中长期稳定地运行[16]。

2.2 任务规划知识模型

求解一个规划问题首先需要用规划知识描述语言对其进行描述，将其转化为计算机可识别的形式，从而被规划器求解，因此规划语言的发展是智能规划技术发展的基础。

在规划领域中，Fike和Nilsson引入了STRIPS操作符，可以很简单地对规划进行描述。其定义包括初始状态、目标状态和动作，其中动作用前提条件和效果来表示，前提条件表示动作执行前必须满足的条件，效果表示动作执行后可以保证为真的状态。但随着规划技术的不断发展，研究人员发现STRIPS的表达能力有限，无法满足一些实际问题的建模需求，因此，Pednault在STRIPS的基础上提出了动作描述语言ADL（Action Description Language）[17]，ADL语言继承了STRIPS语言的知识，并且放松了STRIPS语言的一些限制，增加了条件效果、量化效果等语言特征，使得规划语言更加灵活，而且应用范围也更加广泛。

为了将规划语言标准化，统一规划语言的表示方法，McDermott于1998年提出了规划领域定义语言（Planning Domain Definition Language，PDDL）[18]，能够表示STRIPS、ADL以及其他语言，现在已经成为国际规划大赛的标准语言，并且在规划领域中有着广泛的应用。PDDL将规划问题用领域文件和问题文件描述，从语法和语义的角度给出了规划的定义，可以描述动作类型、动作参数类型以及条件效果和数值变化等。由于经典规划中认为动作是瞬时发生的，考虑到实际任务中存在的持续性动作，PDDL2.1引入数值流、持续动作及规划评价标准[19]，加强了语言表达能力，可以描述离散持续动作、连续动作等，突破了传统规划中动作瞬时完成的假设。目前PDDL建模最常使用的版本为PDDL2.1。

对于深空探测器而言，系统繁多，每个系统由许多原始的组件构成，每个组件一次仅能执行一个活动，许多组件都会限制活动序列。每个活动可能对它的开始时间、结束时间和区间都有绝对和相对的限制。而STRIPS类的语言表示具有时间、资源、互斥关系和并行性是很困难的。NASA在其开发的Europa平台中基于DDL语言定义了新领域定义语言（New Domain Definition Language，NDDL）[20]，该语言不区分状态和动作，利用区间和区间之间的约束以及时间线/活动的表示方法来描述规划问题。其组成包括类、变量、谓词及规则。在经典规划领域，通常采用PDDL及其拓展语言描述模型，但对于复杂深空探测任务，PDDL会有明显不足，星上活动相互约束，资源有限，NDDL这种基于约束的表达方法解决了这一问题，约束可以用来表示互斥关系、活动前提条件和效果以及不同的资源类型等，表达更具灵活性。

为避免生成在实际执行过程中不合理的活动序列，需要考虑深空探测任务中活动间的约束关系，包括时间约束和资源约束。

2.2.1 时间约束

表1 时间区间关系表示Table 1 Time interval relation representation

2.2.2 资源约束

在实际任务中，探测器活动除了要占用时间外，还需要消耗一定的资源，资源是对系统中能源和可用设备的描述，分为可重复资源和消耗性资源。可重复资源在规划动作执行时被占用，结束后返还。消耗性资源在被使用时容量减少，有些可以通过生产动作进行补充，例如太阳能电池充电；有些资源无法得到补充，例如推进剂的消耗等。在规划中将资源表示为一个三元组R=(N,T,Q)，其中N为资源的名字，T为资源的类型，Q为资源的容量。

2.3 任务规划技术

深空环境的不确知、任务复杂、时间资源约束耦合以及活动并发性等特殊情况对任务规划技术提出了更高的需求。因此在进行深空探测器任务规划技术研究时，不仅要考虑任务活动的选择，也需要对时间和资源等进行分配调度，传统的任务规划方法并不能同时进行处理，发展适合深空探测领域的任务规划技术是必要的。

传统的规划系统一般分为输入、规划方法和输出三部分组成。其中，输入通常包括：问题空间的初始状态、系统所要达到的目标、可能实施的动作[23]。而输出则是满足相关要求和约束的动作序列。

传统的规划方法存在着较难满足和求解具有时间资源等约束的实际规划问题。因此，从20世纪90年代开始，为了提高规划效率和规划能力，依次提出了约束可满足规划（Constraint Satisfaction Problem，CSP）[24]、分层任务网规划[25]、概率论规划[26]和时态规划[27]4种广泛应用的方法。

表2给出了当前广泛使用任务规划方法的特点和局限性。针对深空探测任务规划中的约束复杂等特殊问题，总结出了3种适用于深空探测的新任务规划的方法：基于持续动作的任务规划、基于迭代修复的任务规划和基于CSP的任务规划，如表3所示。

表2 任务规划方法比较Table 2 Comparison of different mission planning methods

表3 深空探测器适用任务规划方法Table 3 Mission planning methods for dee space probe

对于实际的深空探测任务，其动作有一定的执行时间，因此采用基于持续动作的规划方法处理持续动作、资源约束和有截至时间的任务目标。该方法用一系列基于距离的启发式来控制搜索，同时考虑了搜索的满足和优化两个方面，以松弛时间规划图为基础设计可纳且高效的启发式。对于满足搜索和优化搜索，分别提出了基于规划质量的启发式和基于目标完成时间和松弛图的启发式。该方法能够解决深空探测器面临的复杂时间资源等约束，但对规划器的处理能力和求解效率都有一定要求。

深空探测器各载荷间约束关系复杂耦合，基于CSP的规划方法将规划问题和调度问题统一编码为约束形式，用约束可满足技术求解。与经典的约束可满足规划不同的是，实际深空探测任务中动作有一定的持续时间，导致其规划解的长度不固定，通常采用定界分层方法，能够有效的解决深空探测器载荷之间的复杂约束以及过耦合状态，并且快速实现规划前对约束的预处理，但是由于在规划过程中需要使用一致性对规划相容性进行判断，剪枝方法不仅占用大量计算资源，一旦过度剪枝还会降低算法的效率。

基于迭代修复的规划方法采用时间线框架描述规划知识，能够一定程度上满足深空探测器任务规划对时间约束的需求。该方法根据探测器当前状态，添加满足约束的活动，采用基于冲突修复的偏序规划算法搜索求解，算法框架如图3所示[28]。但是该搜索算法需要定义冲突类型，不同的冲突有其对应的解决方法，对计算能力需求强，且有时出现无解却无法提前中断搜索的情况，导致效率低下。

2.4 任务重规划/规划修复

在探测任务执行过程中，若外界环境发生了变化[29]（如火星车行进过程中地形的改变）或者动作执行失败[30]（如太阳帆板未能展开），原规划结果无法保证任务的顺利完成。此时，深空探测器需要利用任务重规划/规划修复技术，根据执行情况和自身能力综合决策出新的规划结果，以保障任务目标的实现[31]。此外，对于超新星爆发、火山喷发等极具探测意义的突发事件，探测器能利用规划修复技术在局部调整已有规划结果，在不影响原任务目标实现的基础上，也能完成这些突发事件的探测[32]。

任务重规划技术放弃已有规划结果，在任务执行失败的时候利用局部搜索、进化算法、神经网络、约束可满足问题求解等方法[33-35]决策出探测器在未来一段时间内需要采取的操作。但由于星上计算资源有限、问题求解困难，任务重规划难以在短时间内给出合理可行的任务执行方案。相反，规划修复技术可充分利用已有的规划结果，通过参数调整、动作删除、求精搜索等方法[36]自主生成一些中间的规划修复目标，缩小问题求解规模，提高问题求解效率。尽管在理论上已经证明规划修复问题的复杂度不一定比重规划的低[37-38]，但大量实验结果表明规划修复效率更高[39-40]。因此，在应对任务执行过程中的突发事件时，探测器应该优先采用规划修复方法做出快速决策。

现有的规划修复方法大致可以归为5类[41]：规则匹配性、局部调整型、删除/求精型、状态转移型，以及构造新问题型。各类型所包含的典型方法、规划器、处理类型及局限如表4所示。由于深空探测器任务执行存在多子系统耦合的特点，其活动持续、并行且消耗资源。同时，对于着陆下降、彗星环绕观测等时间要求紧迫的任务，规划修复技术需要在更短时间内快速给出合理可行的修复方案。此外，由于对探测目标的认知受限、空间环境的不确知以及设备损耗、太阳风暴等突发事件难精准预测，规划修复技术面临着固有模型不适应新的执行环境、探测器未来状态难预测、既定规划的失效部分难确定等难题。因此，表4中的大部分规划修复方法难以直接应用到深空探测领域。

表4 多种规划修复方法的比较Table 4 Comparison of different plan repair methods

为有效解决深空探测器规划修复问题，一种解决方式是融合表3中的多项规划修复技术，为深空探测器提供高效求解规划执行失败问题的方法。例如，已知执行失败类型处理和未知执行失败类型处理相结合的混合智能规划修复方法。其中，针对已知执行失败类型的处理，可以事先在器上存储修补规则，根据诊断后的失败原因选择对应的修复策略完成规划修复；或基于已有的规划历史结果，组建规划库，指导现有规划的修复。针对未知执行失败类型的处理，可以结合当时的执行环境，识别不再可用的动作序列并将其删除，然后采用目标导向的智能搜索等方法求解修复方案；或提前通过状态回退构造规划修复候补树，便于快速找到修复方案。针对目标变化或者失效规划部分占比过大的情况，可以从原规划结果中提取动作信息或约束关系以增强领域信息，从而构造新问题，再通过规划器来完成修复方案求解。

2.5 运动规划技术

深空探测任务约束复杂、姿态和轨道机动频繁，需要实现姿态和轨迹自主控制，因此通常根据当前状态生成姿态路径或轨迹，在任务过程中进行自主姿态规划和轨迹规划。

2.5.1 深空探测姿态规划

深空探测中的姿态规划主要用于完成对日定向、对地定向、小行星观测等姿态机动任务，通过规划出姿态路径来指引姿态机动。姿态机动是深空探测器从一种姿态转换到另一种姿态的再定向过程。姿态规划能够极大地减少姿态控制系统对复杂姿态控制方法的需求和依赖，可以使深空探测器具备更高层次的自主运动规划和自主运行能力。

根据规划目的可以将深空探测姿态规划分为多约束可行姿态机动规划和多约束最优姿态机动规划。前者的规划目的是得到满足多约束的安全的姿态机动路径，后者的规划目的是综合考虑各种约束的基础上基于特定指标实现姿态路径优化。

1）多约束可行姿态机动规划

多约束可行姿态机动规划统一考虑姿态指向和有界等多种约束，通过综合求解得到姿态机动路径、角速度和控制力矩等信息。深空探测器在姿态机动过程中会受到多种指向约束和有界约束的限制。这些姿态约束减小了深空探测器在三维姿态空间和姿态参数空间中的可行域，为姿态机动问题的求解带来了很大的困难。

目前的多约束可行姿态机动规划方法主要有势函数法、几何方法、随机规划方法和非线性规划方法。势函数法的针对姿态指向禁忌约束来构造排斥势函数，McInnes[42]通过对禁忌区域施加高势能实现对指向约束的规避。几何方法通常根据空间矢量的几何关系得到姿态机动可行解，Hablani[43]在单位球上定义排斥区域，通过求解两个相关转角得到理想的切线路径。随机规划算法在随机扩展的过程中对当前扩展节点是否进入障碍区进行检查，Xu等[44]在局部扩展后用二次规划方法求解，得到满足多种约束的姿态机动路径。非线性规划方法将姿态规划转换为非线性规划问题，Kim等[45]将姿态指向约束转化成二次凸约束的形式，从而得到满足约束的非线性解。

对于深空探测任务中，势函数法对计算资源要求低，实时性好，但是只适合处理简单指向约束。几何方法简单直观，然而模型较为复杂，占用过多资源。随机规划算法对复杂多约束的情况具有较大的适应能力，但是随机算法具有很大的不确定性，在深空应用中可靠性不足。非线性规划方法将非凸约束凸化，约束处理能力强，易于应用。表5对势函数法、几何方法、随机规划算法和非线性规划方法进行了对比。

表5 几种方法的比较Table 5 Comparison of several methods

2）多约束最优姿态机动规划

多约束最优姿态机动规划引入能量消耗或机动时间等优化目标，在综合考虑各种约束的基础上进一步实现目标优化。目前关于多约束最优姿态机动规划问题的研究方法主要有元启发式方法、线性松弛方法以及伪谱法等。

元启发式方法采用高层次的启发式实现算法随机性和局部搜索的平衡，Wu等[46]设计了角速度和时间的编码方法，将时间最优姿态路径规划问题转换成中间节点寻优的最优化问题，进而求出满足约束的姿态机动路径。根据姿态规划的搜索策略，将元启发式方法做如图4所示的分类。

图4 元启发式方法的分类Fig.4 The classification of meta-heuristic methods

线性松弛方法通过利用线性松弛技术确定最优值的边界来求解非凸二次约束二次规划问题，Sun等[47]利用半定松弛方法将原来的非凸二次约束二次规划问题转化为半定规划问题，并通过迭代秩最小化方法逐渐得到最优解。伪谱法利用正交多项式来表示最优解曲线，将原来的最优控制问题转化为求解正交多项式展开系数的非线性规划问题。

对于深空探测中的多约束最优姿态机动规划，线性松弛方法主要针对能量最优问题且计算效率较低，伪谱法并未考虑中间节点约束，元启发式方法优化效果较好，能够得到低能量或短时间的姿态机动路径。

2.5.2 深空探测轨迹规划

深空探测中轨迹规划的目标是根据深空探测器的位置信息及目标飞行区域或目标飞行点制定相应的机动策略，如探测器的机动点、机动时间及机动大小等，并生成连接初始位置和目标位置且满足一系列工程约束的飞行轨迹，使得探测器能够在不确定的环境下快速并安全抵达目标位置。

在深空中，有限的燃料和复杂未知的环境给轨迹规划带来了极大的挑战。由于探测器所携带的燃料有限，且需要在有限的时间内抵达目标地点，需要尽可能快速规划出节省燃料的轨迹。而复杂未知的深空环境则对轨迹规划的安全性提出了更高的要求。目前，轨迹规划主要由连续优化和离散搜索两种方法解决以上面临的两种问题。其中，连续优化主要根据飞行任务设置优化指标，生成平滑轨迹，且约束越多越难求解。而离散搜索则通过节点拓展的方式搜索出轨迹经过的节点，所生成的轨迹不平滑，但约束越多越容易求解。

连续优化方法主要对探测器在轨迹规划中的某些指标进行优化。探测器在飞行中除了飞往指定目标外，还需要考虑其他约束条件。在深空探测中，因为飞行距离远、飞行时间长等特点，所以还需根据所携带的燃料数量考虑燃料消耗问题，或根据任务需求考虑飞行时间问题。连续优化方法可以使得某些特定性能指标达到最优。因此，连续优化方法也称轨迹优化方法。目前，连续优化的主流方法有直接法、间接法、伪谱法和凸优化方法等。

直接法引入了时间离散网格，将控制变量或状态变量离散化，将动态的约束条件转化为代数约束条件，通过将控制变量和状态变量参数化，将优化问题转化为离散参数优化问题，进而利用优化算法进行问题求解。直接法可分为直接配点法和直接打靶法两大类。直接配点法[48-49]将控制变量和状态变量离散化，并将整个任务时间分成多段，每段的两个端点称为节点，两节点用多项式表示状态变量随时间的变化。直接打靶法仅将控制变量离散化，通过数值积分获得状态变量，从而求解出目标函数。直接配点法与直接打靶法对状态初始值的依赖度都较低，但相比之下直接配点法的精度较高。间接法的基本原理是最优控制理论的极大值原理，将最优控制问题转换为两点边界问题或多点边界问题进行求解。间接法的精度较高，但对初始值的依赖度更高。而混合法则是将直接法和间接法相结合，利用最优控制原理和非线性规划的优势，更有效地求取最优解。表6对直接配点法、直接打靶法和间接法进行了对比。

表6 连续优化方法的比较Table 6 Comparison of continuous optimization methods

在一些深空探测任务中，探测器需要飞往某些特定的区域或避开一些危险区域和障碍物，针对这一问题，离散搜索方法提供了可行的轨迹求解方法。离散搜索方法将轨迹分为多段求解，考虑各种路径约束，将各节点连接形成一条完整的轨迹。目前应用较多的离散搜索方法有图解法、A*搜索法和Way-Points方法等。

图解法的每一条轨迹都由一组导航点插入，将轨迹投影到一个有向图上[50]，用有向图中的点表示导航点，在特定条件下在过渡点进行转移，每个过渡点都由一段弧连接，弧段在有向图中表示为连接节点的有向线段。A*搜索法[51]定义了三维搜索空间并将空间划分为多个不同节点，将潜在的障碍物和危险区域用基本几何形状或其组合表示，通过满足一定的数学条件使某一段轨迹处于障碍物和危险区域之外。Way-Points方法[52]就是先给定一系列航天器必须经过的导航点，再用导航点参数表示轨迹并对其优化。离散搜索的方法在理论上可以确保收敛到全局最优解，但需要对搜做空间进行正确的离散化，且所生成的轨迹不是平滑的。图5表示了离散搜索方法的基本原理。

图5 离散搜索方法图示Fig.5 Diagram of discrete search methods

2.6 科学观测任务规划

深空科学观测任务利用深空探测器对地球以外的空间和天体进行观测，收集图像、电磁信号等信息。其主要的特点是存在时间窗口约束，只有在时间窗口之内才能观测到目标，完成观测任务。一些现有的规划系统同时具备对地和深空目标观测任务的规划能力，因此本文不着重区分观测对象。

观测任务规划方法按照航天器数量分为单星观测任务规划和多星观测任务规划。在多星观测任务规划中，按照规划系统架构又分为集中式规划、分布式规划和分散式规划。集中式规划容易造成单点失效或对规划卫星的计算压力过大，因此更适合小规模多星系统；分布式和分散式的规划架构具备充分利用多星计算资源、避免单点失效等优点，但需要平衡任务收益与通信代价。

一类观测任务规划方法主要关注约束处理，包括活动间逻辑约束和航天器时间资源约束，将观测任务规划问题抽象为约束满足问题（CSP），采用的方法主要为基于规则的搜索、约束推理技术及迭代修复方法。

法国航天局的Pleiades系列卫星以的自动化通用体系演示应用平台AGATA（Autonomy Generic Architecture -Test and Application）采用时间线上的约束网络模型描述观测规划问题[53-54]，构建反应型和慎重型任务相结合的规划架构[55]，外部环境通过反应型任务与慎重型任务交互，反应型规划采用启发式搜索方法，慎重型采用迭代随机贪婪搜索算法。

美国喷气推进实验室的人工智能小组开发的自主规划和调度环境（ASPEN）[56]采用状态时间线模型和迭代修复规划方法，具备时间资源约束处理能力。连续活动调度规划执行和重规划系统（CASPER）是ASPEN的软实时星上规划版本，能够在环境变化或目标变化后快速进行重新规划[57]。

上述方法主要关注约束处理，还有一类观测规划方法不仅处理约束还力求最大化任务收益，以处理观测目标多而观测资源有限的任务。其数学本质是复杂的组合优化问题，可建模为背包问题模型、图论问题模型、整数规划问题等。对此类观测任务的规划方法可分为精确算法和近似算法。动态规划、分支定价算法等精确算法对于复杂的问题需要大量计算时间，难以在多项式时间内找到最优解，因此实际中多采用近似算法在较短的时间内找到最优解或可接受的次优解。近似算法包括贪婪搜索、禁忌搜索、模拟退火、遗传算法及人工神经网络等。

SPIKE[58]规划调度软件系统用于哈勃天文望远镜的长期任务调度，能够生成包括多达5 000个（至少1 h）观测活动的多年调度。SPIKE同时采用了程序性搜索、基于规则的启发式搜索和人工神经网络方法，不仅处理约束，也考虑观测收益的优化。

在中欧合作的深空探测项目DSL（Discovering the Sky at the Longest Wavelengths）任务中，一个主探测器和8个子探测器绕月合作探测空间低频信号。此项目采用分布式星上规划算法，局部约束可满足问题采用贪婪搜索方法，全局优化采用分布式混合动态变异遗传算法（Distributed Hybrid Dynamic Mutation Genetic Algorithm，DHDMGA）[59]。针对该任务的星上任务自主重规划问题[31]，提出多目标混合动态变异遗传算法（Multi-Objective Hybrid Dynamic Mutation Genetic Algorithm，MO-HDMGA）和重规划方法结合的规划模式。王冲等在分析多卫星中心内部特点及中心间关系的基础上，建立数学模型并提出了多中心合作协同进化算法[60]。赵凡宇对航天器多目标观测任务调度与规划方法进行研究[61]，设计了基于蚁群算法的任务调度优化方法。上述算法都属于元启发式算法，虽然能够达到优化收益的效果，但是算法复杂度较高且具有随机性，并不适合计算资源有限，任务可靠性要求高的任务。

南京航空航天大学的学者基于多智能体技术对多星观测问题的规划和重规划进行研究[62]，采用基于合同网的二次任务分配策略和迭代重规划策略，证明分布式算法比集中式多智能体算法有更高的效率和更优的收益。针对DSL在有限通信条件下的规划，设计了基于博弈理论的分布式和分散式的规划方法[63]，提出3种多星协商机制：基于效能的可反悔机制、烽火信号机制和基于广播的机制。赵宇庭等提出具有私有性的分散式多探测器观测任务规划方法，设计基于双边匹配延迟接受策略的多智能体迭代协商机制，且在智能体内时间资源约束处理中也加入了优化策略，从规划机制和局部决策两个层面提高任务收益。基于合同网、博弈理论、双边匹配等多智能体方法，优化机制简洁，每个智能体内部算法复杂度低，适合多探测器分布式任务规划。

随着航天器数量的增长和观测任务复杂度的提高，地面管控资源越发紧缺，难以满足观测任务快速响应的需求，星上自主观测任务规划将成为未来的发展方向。随着未来星上计算能力的增强，机器学习等对计算资源要求较高的人工智能方法也将成为观测任务自主规划的可选方案。

3 深空探测器自主规划技术发展趋势

3.1 自主规划技术发展趋势

针对深空探测器自主规划面临的约束复杂、不确定性强和实时性要求高的特点，自主规划技术以满足实际自主运行需求为目标不断发展，从任务规划、规划修复和运动规划等方面力求形成高层决策的自主管理系统，保障探测器自主安全运行，其发展趋势为如下几个方面。

1）探测器由单一模型向多维度多尺度建模发展

深空探测器系统复杂，单一的模型描述语言难以充分刻画系统间的耦合约束条件。所以，需建立多维度、多尺度的规划知识模型，既能够提高规划解的可行性，又能降低规划算法的计算需求。

2）探测器规划向分布式群规划发展

针对多探测器分布式协同任务规划需求，研究适用于深空探测任务的体系结构和通信交互机制。充分利用器上计算资源、避免单点失效，快速应对和响应任务需求。

3）预先规划向复杂环境在线快速规划发展

深空探测任务过程中，未知的飞行环境、突发的科学目标等会经常导致预定规划难以正常执行。为了尽可能地完成任务目标，必须快速应对和解决规划失效的情况。所以，需要重点研究不确知环境下，预定规划序列执行失败时的快速重规划方法。

4）单一目标运动规划向多约束多目标运动规划发展

深空探测存在飞行环境复杂、姿态/轨迹约束多等问题，且星上资源有限。所以，需要考虑多约束下运动规划技术，并综合各性能指标，兼顾机动时间与能量消耗等条件，重点研究多约束多目标下的运动规划技术。

3.2 自主规划技术研究方向

由于对时间资源等复杂约束的表达能力和有限计算资源下规划处理能力的限制，自主规划技术实际应用目前处于前期探索和研究阶段，仅在少数深空探测任务规划中进行了测试和试验。考虑到深空探测领域的系统耦合性、资源有限和约束复杂等特殊性质，从当前亟需解决的问题和发展趋势来看，建议在深空探测领域重点研究以下方向。

1） 任务规划与序列执行协调配合框架研究

随着深空探测器对自主能力需求的逐步提高，自主规划与序列执行框架设计更加趋于复杂化、并行化和一体化。对于仍未实现的探测任务目标或者重规划/规划修复任务，自主任务规划部分应该在探测器当前序列执行的基础上，结合当前及未来一段时间内的星载能源变化情况、各子系统的调度和健康状况，给出合理可行的执行方案；对于由环境变化、执行异常、设备故障等引起的规划失败，序列执行部分应当适时智能选取可执行活动继续执行，同时向自主任务规划部分发送重规划/规划修复请求。自主规划与序列执行之间如何协调配合完成规划–执行–重规划/规划修复是未来值得探讨的问题。

2） 任务规划模型中复杂约束表示方法研究

任务规划知识模型是自主规划技术基础并影响后续采用的规划搜索技术。PDDL形式语言通过动作、条件和效果将各状态相关联，对时间、资源约束表达能力欠缺，大规划规划问题会呈现搜索空间大的特点。基于时间线的表达方式采用约束可满足方法，复杂约束表达能力较强，但后续规划搜索效率有待提高。因此如何有效结合两者优势对具有多约束的深空探测任务规划模型进行合理表示是当前建模关键。

3） 巨型搜索空间下高效规划方法研究

深空探测规划问题具有大量并行活动和资源约束等需要处理，搜索空间大，基于状态空间规划的启发式规划方法难以求解具有复杂约束规划问题，且无法直接在基于时间线的规划方法中使用。同时，空间环境动态不完全可观测，使得任务规划过程需要考虑时间或资源等不确定性，给规划方法带来更大挑战。因此，如何利用两类任务规划方法优势发展巨型搜索空间下高效规划技术需要进一步研究。

4）不确定环境下自主任务重规划/规划修复技术研究

随着探测目标距离的大幅度增加，深空环境的不确知性增强，系统的长期运行可靠性降低，依赖于规划知识模型的深空探测器自主任务重规划/规划修复技术的实用性受到极大挑战。因此，匹配环境变化的自适应规划知识模型设计必定是自主任务重规划/规划修复研究的重点。此外，如何在有限的星载资源基础上，考虑现有执行序列对各子系统的调度，综合活动前提、执行时间、消耗资源以及任务截止时间要求，快速给出次优的解决方案，仍是研究重点。

5）多约束下深空探测器最优路径快速规划技术

在深空探测的复杂环境下，探测器运动存在约束复杂、通信时延和燃料有限等问题，通常需要提高探测器的自主能力、减少机动时间和燃料消耗。在引入机动时间和燃料消耗等优化目标的条件下，运动规划方法需要综合考虑多种约束的基础上进一步实现目标优化，但是星上资源有限，优化效率较低。因此，需要重点研究多约束下深空探测器最优路径快速规划技术，在提高算法的计算效率同时又能保持较好的机动时间和燃料消耗优化效果。

6）分布式多智能体自主规划技术

随着深空探测器任务复杂度和规模的提升，需要多探测器协作完成。分布式多智能体规划具有充分利用多探测器的规划能力、避免系统单点失效等优点，辅以合理的系统架构、规划协商模式及信息一致性策略，能提高规划效率、提升系统可靠性，有益于多探测器系统长期安全运行。启发式搜索、元启发式算法、市场机制、博弈论、机器学习等理论都可作为分布式多智能体规划的基础，但对于实际任务，则需要选择与场景需求和探测器能力相匹配的规划方法，并结合任务特点进行扩展和改进。

4 结 论

随着计算机技术和人工智能相关领域的蓬勃发展，自主规划技术解决现实深空探测器规划问题逐渐成为可能，在自主规划技术研究方面，已提出很多行之有效的规划方法，在工程和空间技术领域也得到有效应用。随着航天任务复杂化、飞行距离越来越远，自主规划技术需求不断增加，其已成为当前空间自主技术领域研究的热点。我国“天问一号”火星探测任务的成功实施，未来小行星探测、木星系探测等深空任务也在规划论证中。我国深空探测领域迎来了前所未有的发展机遇，应该把握机会，着力突破深空探测关键技术，开发具有自主知识产权的自主规划系统，推进航天器自主化和智能化发展。