（控制科学与工程专业论文）基于pddl的成像卫星操作规划问题研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 成像卫星规划问题的研究可以分为两大类：任务计划自动生成问题和操作指 令自动生成问题。目前，国内外研究大多针对任务计划自动生成问题，其研究成 果十分丰富；而公开的有关操作指令自动生成问题的研究资料却相对较少。因此， 本文针对成像卫星操作指令的自动生成问题，开展了成像卫星操作规划问题建模、 算法、系统以及子目标冲突消解机制等关键问题研究，主要研究成果如下： 1 建立了成像卫星操作规划模型。成像卫星操作规划问题研究的首要任务是 根据成像卫星操作规划问题的特点，建立反映问题本质的模型。本文从成像卫星 的任务特性出发，通过与传统规划语言和规划建模方法比较，分析了规划领域定 义语言p d d l ( p l a n n i n gd o m a i nd e f i n i t i o nl a n g u a g e ，p d d l ) 描述成像卫星操作 规划问题的适用性和基于p d d l 的规划建模方法的模型描述能力。在此基础上， 基于p d d l 的规划建模框架，通过定义对象、谓词、函数和动作，建立了成像卫 星操作规划模型。与当前相关研究中建立的模型相比，该模型包含了更多的模型 要素，更具合理性，描述能力更强，更具有应用价值。 2 研究了成像卫星操作规划问题的求解算法。为了验证模型和系统的有效性， 本文采用一种基于时序规划图的启发式规划算法求解成像卫星操作规划问题。重 点分析了该算法的问题求解能力及其求解成像卫星操作规划问题的适用性。 3 研究了成像卫星操作规划系统以及子目标冲突消解机制。为了有效地解决 成像卫星操作指令的自动生成问题和子目标冲突问题，本文提出并设计了一种基 于p d d l 的成像卫星操作规划系统结构。在系统设计的基础上，采用j a v a 语言实 现了基于p d d l 的成像卫星操作规划系统。最后，通过典型的仿真实例，综合验 证了成像卫星操作规划模型、算法和系统的有效性。 本文的研究给出了成像卫星操作指令自动生成的一种解决方案，对于解决其 它类型的航天资源操作规划问题也有一定的借鉴作用。 主题词：成像卫星操作规划建模p d d l 规划算法规划系统 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t t h er e s e a r c ho nt h ei m a g i n gs a t e l l i t ep l a n n i n gp r o b l e mc a nb ed i v i d e di n t ot w o t y p e s ：t h e a u t o m a t i cg e n e r a t i o no fm i s s i o ns c h e m e ( a g m s ) ，a n dt h ea u t o m a t i c g e n e r a t i o no fo p e r a t i o nc o m m a n d ( a g o c ) c u r r e n t l y ，t h ei n t e m a t i o n a la n dd o m e s t i c r e s e a r c hm o s t l yf o c u s e so nt h ea g m s ，w h i c hh a sg a i n e dq u i t ea1 0 to fa c h i e v e m e n t s a n dr e l a t i v e l y1 e s sr e s e a r c ho nt h ea g o ci sf o u n di np u b l i cl i t e r a t u r e s t h e r e f o r e ， a i m i n ga tt h ea u t o m a t i cg e n e r a t i o no ft h ei m a g i n gs a t e l l i t eo p e r a t i o nc o m m a n d ，t h i s t h e s i ss t u d i e st h ek e yq u e s t i o na b o u tm o d e l i n g ，a l g o r i t h m ，s y s t e ma n dt h em e c h a n i s mt o s o l v es u b g o a lc o n f l i c to ft h ei m a g i n gs a t e l l i t eo p e r a t i o np l a n n i n gp r o b l e m ( i s o p p ) t h e m a i na c h i e v e m e n t sa r ea sf o l l o w s ： 1 p r e s e n t i n gt h ei m a g i n gs a t e l l i t eo p e r a t i o np l a n n i n gm o d e l ( i s o p m ) t h ep r i m a r y t a s ko ft h er e s e a r c ho nt h ei s o p pi st op r e s e n tt h em o d e lw h i c hc a nr e f l e c te s s e n c eo f p r o b l e ma c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ei s o p p s t a r t i n gf r o mt h ec h a r a c t e r i s t i c s o ft h ei m a g es a t e l l i t em i s s i o n ，a n dc o m p a r e dw i t hc l a s s i c a lp l a n n i n g l a n g u a g ea n d p l a n n i n gm o d e l i n gm e t h o d ，t h i st h e s i sa n a l y z e st h ea p p l i c a b i l i t y o fp d d l ( p l a n n i n g d o m a i nd e f i n i t i o nl a n g u a g e ) i nd e s c r i b i n gt h ei s o p p ，a n dt h em o d e ld e s c r i p t i o n a b i l i t yo ft h ep d d l b a s e dp l a n n i n gm o d e l i n gm e t h o d b a s e do nt h e s e ，t h ei s o p mi s p r e s e n t e db yd e f i n i n gt y p e ，p r e d i c a t e , f u n c t i o n a n da c t i o nw i t h i nt h ep d d l b a s e d p l a n n i n gm o d e l i n gf r a m e w o r k c o m p a r e dw i t ht h em o d e l sf o r m u l a t e di np r e v i o u s s t u d i e s ，t h em o d e lw ep r e s e n ti n c l u d e sm o r em o d e le l e m e n t s ，o w n sb e t t e rd e s c r i p t i o n a b i l i t ya n d i sm o r er a t i o n a l ，p r a c t i c a la n da p p l i c a b l e 2 t h es o l v i n ga l g o r i t h mo ft h ei s o p pi sr e s e a r c h e d i no r d e rt ov a l i d a t et h em o d e l a n ds y s t e mw ep r e s e n t ，ah e u r i s t i cp l a n n i n ga l g o r i t h mb a s e do nt e m p o r a lp l a n n i n gg r a p h i sa p p l i e dt os o l v et h ei s o p p t h i st h e s i se m p h a s i z e so na n a l y z i n gt h ep r o b l e ms o l v i n g a b i l i t yo ft h ea l g o r i t h ma n dt h ea p p l i c a b i l i t yo ft h ea l g o r i t h mi ns o l v i n gt h ei s o p p ， 3 t h ei m a g i n gs a t e l l i t eo p e r a t i o np l a n n i n gs y s t e m ( i s o p s ) a n dt h em e c h a n i s mt o s o l v es u b g o a lc o n f l i c ta r er e s e a r c h e d an e wp d d l b a s e di m a g i n gs a t e l l i t eo p e r a t i o n p l a n n i n gs y s t e ma r c h i t e c t u r ei sp r o p o s e da n dd e s i g n e dt os o l v et h ea u t o m a t i cg e n e r a t i o n o ft h ei m a g i n gs a t e l l i t eo p e r a t i o nc o m m a n da n dt h es u b g o a lc o n f l i c tp r o b l e me f f e c t i v e l y b a s e do nt h es y s t e md e s i g n t h ep d d l b a s e di s o p si sr e a l i z e dw i t hj a v al a n g u a g e f i n a l l y ，t h et y p i c a ls i m u l a t i o ne x a m p l e sa r eg i v e nt ov e r i f yt h ev a l i d i t yo fi s o p m ， c o r r e s p o n d i n ga l g o r i t h ma n ds y s t e m t h i sr e s e a r c hp r e s e n t sam e t h o dt os o l v et h ea u t o m a t i cg e n e r a t i o no ft h ei m a g i n g s a t e l l i t eo p e r a t i o nc o m m a n d ，w h i c hs e r v e s a sar e f e r e n c ef o rs o l v i n go t h e rt y p e so f s p a c e r e s o u r c eo p e r a t i o np l a n n i n gp r o b l e m s k e yw o r d s ：i m a g i n gs a t e l l i t eo p e r a t i o np l a n n i n gm o d e l i n g p d d l p l a n n i n ga l g o r i t h mp l a n n i n gs y s t e m 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1 成像卫星操作规划模型中的对象定义、描述及示例3 7 表3 2 成像卫星操作规划模型中的谓词定义及描述3 8 表3 3成像卫星操作规划模型中的函数定义及描述3 9 表3 4 成像卫星操作规划模型中的动作定义及描述4 0 表3 5 成像卫星操作规划问题的求解类型4 8 表5 1成像卫星无任务冲突情况下的任务列表6 6 表5 2 成像卫星无任务冲突情况下的规划方案6 6 表5 3 成像卫星有任务冲突情况下的任务列表6 9 表5 4 子目标冲突情况7 0 表5 5 成像卫星有任务冲突情况下的规划方案7 0 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图1 2 图2 1 图2 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图3 1 8 图3 1 9 图3 2 0 图3 2 1 图3 2 2 图3 2 3 图3 2 4 图3 2 5 图3 2 6 图3 2 7 图3 2 8 图目录 成像卫星操作指令的生成及执行流程2 论文的组织结构1 1 成像卫星操作规划问题的主要输入输出要素。1 7 成像卫星操作规划问题求解思路2 0 原子型资源随时间变化情况2 6 连续型资源随时间变化情况2 6 领域描述文件格式2 8 问题描述文件格式2 8 状态动作模型3 0 基于p d d l 的动作模型表示3l 动作实例。3 2 状态约束的表达3 2 遥感器转向瞄准动作的状态约束3 3 加入持续时间的动作模型3 3 加入静态持续时间的遥感器开机动作模型3 3 加入动态持续时间的遥感器转向瞄准动作模型3 4 资源数值约束在资源消耗过程中的表达3 4 资源数值约束在资源产生过程中的表达3 4 加入资源数值约束的存储转发数传动作模型3 5 外部事件约束的表达3 6 数传时间窗口的表达3 6 遥感器开机动作模型4 1 遥感器关机动作模型4 l 遥感器校准动作模型4 1 遥感器转向瞄准动作模型4 2 遥感器成像动作模型4 2 数传天线开机动作模型4 3 数传天线关机动作模型4 3 数传天线转向瞄准动作模型4 3 数传天线捕获跟踪动作模型4 4 数传天线存储转发数传动作模型4 4 成像卫星实拍实传动作模型4 5 第v 页 国防科学技术大学研究生院硕士学位论文 图3 2 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图5 1 图5 。2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 9电源充电动作模型4 6 s a p a 算法的架构5 0 前向状态空间搜索算法5 1 基于松弛的时序规划图的代价传播5 3 基于松弛的规划解的启发值计算5 4 t i l s a p a 算法的架构5 5 t i l s a p a 规划器的比赛结果5 6 基于p d d l 的规划问题求解结构5 8 基于p d d l 的成像卫星操作规划系统结构6 0 原型系统6 3 规划结果的g a n t t 图显示6 3 规划结果的p e r t 图显示6 4 成像卫星无任务冲突情况下的任务示例6 5 成像卫星无任务冲突情况下的规划结果显示6 7 成像卫星有任务冲突情况下的任务示例6 8 成像卫星有任务冲突情况下的规划结果显示7 0 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：陋二型聿 日期：泐多年j j 月j 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：巨型堑 作者指导教师签名： 咎乏矿一 日期：炒孚年fj 月7 日 日期：驯p 年月l1 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 课题背景与研究意义 现代军事战争已成为陆、海、空、天、电“五维一体”的联合作战【1 2 ，3 4 】，能 否快速准确地感知战场态势进而获取信息优势是取得胜利的关键。从海湾战争、 科索沃战争直到2 0 0 3 年的伊拉克战争，成像卫星在争夺战场制信息权中，发挥了 巨大的作用，已成为打赢现代高技术局部战争至关重要的装备。成像卫星具有成 像面积大、范围广，提供信息迅速、可靠，可长期反复监视特定的地区，不受国 界和地理条件限制，可提供近实时的信息等特点。总之，现代军事战争条件下， 成像卫星是实现航天力量与军事力量结合的关键，是夺取战场信息优势的核心，对 支持诸军兵种联合作战指挥控制有着极其重要的作用。 成像卫星一个完整的工作过程包括目标观测和数据传输两个子过程，并且只 有当卫星和地面目标、地面站或中继卫星可见时，卫星才能执行这些任务，这就 在时间上大大限制了卫星资源的可用性。由于成像卫星是在轨运行的，卫星的存 储器、燃料和电源等资源的补充也非常困难。同时，成像卫星研制成本高，研制 周期长。一些卫星重达十几吨，耗资几十亿美元，制造耗时十几年。这些都使得 成像卫星在轨的时间和资源显得十分宝贵。为了有效的利用成像卫星宝贵的轨道 资源，实现在有限的时间内尽可能满足不同用户、不同优先级的任务需求，这就 需要为成像卫星制定合理的任务计划和操作指令。 成像卫星的操作指令通常是由地面预先编制完成的，一般分为任务计划编制 和操作指令生成两个阶段。地面指挥控制中心根据用户需求通过任务计划编制软 件生成卫星的任务计划( 相当于卫星的高级任务指令) ，再经过操作指令编制软 件生成卫星的操作指令，然后经由地面测控站或中继卫星载入成像卫星，成像卫 星根据操作指令利用遥感器获取地面目标的图象信息，通过数传天线传回至地面 接收站和信息处理中心【5 , 6 】。整个成像卫星操作指令的生成及执行流程，如图1 1 所示。 传统的卫星任务计划和操作指令的制定方式是通过操作人员和用户协商，由 人工制定的，需要操作人员凭主观经验分析用户需求及卫星的各种约束条件，往 往经过较长时间才能获得一种可行但不一定优化的任务计划和操作指令，这种人 工制定的方式不但耗时费力，而且容易出错。 成像卫星的任务计划和操作指令的制定工作十分复杂、困难，采用传统手工 制定的方式显然不能满足实际需求。近年来，各国都在大力发展成像卫星相关应 用技术，其中，规划技术作为解决成像卫星任务计划和操作指令自动生成问题的 第1 页 国防科学技术大学研究生院硕j 学位论文 关键技术，已经成为r 一个重要的研究方向。目前，国内外现有研究大多刽刘成 像p 军的仆务计划编制阶段，其研究成果十分丰富；而公开的有芙操作指令生成 阶段的研究资料却相对较少。因此针对成像卫星操作指令的自动生成问题，丌胜 成像卫星操作规划问题建模、算法、系统以及子e l 标冲突消解机制等关键问题研 究是十分必要的。 地面测控：一 | 地面测控谂7 衿 垒：篁= ! 蛳接收 地面指控i 。f信息处理t 山l 成像卫星 地丽目标 图i1 成像h 星操作指令的生成及执行流程 本课题开胜的成像卫星操作规划蛔题研究主要有以下几方面意义： ( ”提高卫星的自治能力，减少地面人手指令干预，大大节省人力资源和经 费开支； ( 2 ) 提高系统的规划和推理能力，从而增加任务的时效性和n j 韶性： ( 3 ) 合理分配和利用成像卫星的遥感器资源，增加信息款取能力从而提高 任务的叫报收益。 ( 4 ) 相关技术成果可以灵活地运用到今后成像一丝的设计和研制叶1 ，达到减 少成像卫星研制周期的日的。 总之，成像卫星操作规划问题研究是一个重要而紧迫的研究课题掌握相关 技术对促进我国成像卫星以及航天技术水下的提高具有重要意义。 1 2 国内外研究现状 121 成像卫星规划问题研究现状 成像卫星规划问题的研究可以分为任务计划出动2 成问题和操作指令自动生 第2 页 蝥 誓”柏 国防科学技术大学研究生院硕士学位论文 成问题两人类。就目前的文献来看，国内外关于任务计划自动生成问题的研究成 果十分丰富，而公开的有关操作指令自动生成问题的研究资料却相对较少。因此， 为便于阐述，本文对两类子问题的研究现状不进行区分，仅从模型、算法及软件 系统三个方面对成像卫星规划问题的研究现状进行回顾和总结。 ( 1 ) 问题求解模型 目前，成像卫星规划问题求解模型主要有数学规划模型，约束满足模型，序 列决策模型，图模型，通用问题模型，状态动作模型等【r ，j 。 在国外的研究中： p e m b e r t o n t 9 1 、w o l f e t l o j 在没有考虑存储器容量约束和数传任务需求的情况下， 且假定任务间不存在任何的时间和逻辑关系的条件下，建立了数学规划模型。法 国欧空局的b e n s a n a 】等人针对s p o t 5 卫星，建立了整数规划模型。l e m a i t r e t l 2 】 针对敏捷卫星( a g i l es a t e l l i t e ) ，在没有考虑存储器容量约束的条件下，建立了约 束满足问题模型。b e n s a n a l l 3 1 针对s p o t 任务规划研究中，考虑成像卫星存储器容 量约束，侧视条件约束等多种约束的条件下，提出了一种值约束满足问题模型， 但是没有考虑数传任务需求。d a m i a n i | 1 4 】针对成像任务的动态变化建立了成像卫星 自主任务规划的序列决策模型。g a b r e l l l 5 】针对单颗成像卫星的任务调度问题，建立 了一种无圈有向图模型，且利用无圈有向图的成像路径表示任务规划结果。 v a s q u e z t l 6 】等人将s p o t 5 卫星的任务调度问题转化为0 1 背包问题。s m i t h i l 川采 用a s p e n 建模语言建立了e o 1 的状态动作模型。f r a n k 1 8 】采用一种基于约束的时 间间隔表示法建立了卫星的状态动作模型。b e a u m e t 6 1 】采用规划领域定义语言建立 了敏捷卫星的状态动作模型。此外，目前实际应用中还存在许多针对具体卫星的 专用模型，例如p o t t e r ”】等人针对l a n d s a t 7 设计的任务调度模型，以及m u r a o k a l 2 u j 等人针对对地观测卫星设计的a s t e r 规划模型等。 在国内的研究中： 哈尔滨工业大学的杨家军【2 1 】在考虑小卫星自主运行模糊特性所引起的规划与 调度的动态特性条件下，提出了任务规划与调度的模糊智能模型。 中国科学院空间科学与应用研究中心的代树武，刘洋2 2 , 2 3 , 2 4 】等人提出了卫星模 型、推理机支持下的智能规划与调度技术结构和采用分层a g e n t 控制的自主控制 系统，主要用于将卫星成像计划分解成比较详细的操作指令序列。 国防科学技术大学的贺仁杰【2 5 】在调度约束条件分析和些基本假设的基础 上，建立了两种问题求解模型：约束满足问题模型和混合整数规划模型。刘洋i z 6 j 针对有新成像任务到达的情况，建立了动态约束满足调度模型。张万鹏1 6 】针对多星 侦察系统的任务特点，设计了一种多星任务规划调度建模框架，模型包括四个部 分：活动，资源，事件和约束。张巾凡【5 1 针对卫星的优化成像目标序列求解，建立了 第3 页 国防科学技术大学研究生院硕士学位论文 一种尢圈有向图模型。张正强【2 7 】针对单星的自主控制问题，建立了智能成像卫星 的规划域模型。王钧1 8 】针对成像卫星综合任务调度问题，基于全局优化模式，建立 了多目标任务调度模型；基于阶段优化模式，建立了综合任务调度问题的多目标 有向图模型。王军刚2 8 】在研究了不确定条件下的成像卫星调度问题，建立了成像 卫星鲁棒性调度模型和成像卫星动态调度模型。 ( 2 ) 问题求解算法 成像卫星规划问题求解算法主要分为完全搜索算法和不完全搜索算法两类p 】。 由于成像卫星规划问题的特点和复杂性，目前大多数研究工作主要集中在不完全 搜索算法上。 在国外的研究中： p e m b e r t o n 9 】提出了一种对大规模问题的迭代求解方法。w o l f e 和s o r e n s e n j 比较了贪婪算法、具有前瞻( 1 0 0 k a h e a d ) 功能的贪婪算法以及遗传算法等三种算 法。在贪婪算法中，所有地面目标按照优先级别进行排序，然后按顺序依次选择， 根据约束条件安排最佳成像时刻。具有前瞻功能的贪婪算法在选择下一个成像任 务时需要考虑其对其他成像任务的影响。遗传算法中，定义了相应的交叉、变异 算子，允许撤销已经安排的成像任务，可以得到一个较好的规划方案。文中的实 验证明，当问题规模较大时遗传算法取得的规划效果最好。l e m a i t r e l l 2 l 采用约束规 划方法和局部搜索算法对相应的问题模型进行求解。b e n s a n a 1 3j 等人基于值约束满 足问题模型比较了完全搜索算法( 深度优先搜索、动态规划、r u s s i a nd o l ls e a r c h ) 和不完全搜索算法( 贪婪搜索、禁忌搜索) 在不同问题规模情况下的性能。文中 给出的实验证明，完全搜索算法可用于求解小规模问题的最优解，而禁忌搜索可 以在合理的时间内得到较大规模问题的一个满意解。g a b r e l l l 5 】针对s p o t 5 卫星的 任务规划问题，采用标记校正算法对无圈有向图模型进行求解。v a s q u e z l l 6 】等人针 对建立的背包问题模型，采用禁忌搜索算法进行求解。s h e r w o o d 2 9 】等人在用于 e o 1 卫星的a s p e n 系统中采用了一种基于局部搜索的算法。f r a n k t l 8 l 采用启发式 搜索算法对问题进行了求解。 在国内的研究中： 国防科学技术大学贺仁杰【2 5 】针对不同的两种问题求解模型给出了相应的禁忌 搜索算法和列生成算法。刘洋1 2 6 j 设计了模型求解的动态回溯算法和基于局部修改 的递进规划算法。张万鹏【6 】采用基于动态优先级的局部邻域搜索算法完成了问题模 型的求解。张帆【5 】基于遗传算法针对单星轨道圈次的任务规划问题提出了最短路径 优化算法。张正强【2 7 1 采用基于任务网络的引导式状态空间搜索算法和采用基于任 务网络的后向状态空间搜索算法求解了单颗自主成像小卫星的规划域模型。王钧【8 】 针对成像卫星综合任务调度问题，基于全局优化模式，给出了一种基于s p e a 2 算 第4 页 国防科学技术大学研究生院硕士学位论文 法的多目标综合任务调度算法；基于阶段优化模式，首先提出了一种基于拍摄概 率的成像任务预分配方法，将多星任务调度转化为单星任务调度；然后给出了一 种基于多目标进化算法的成像路径搜索算法用于求解单星的任务调度问题。王军 引28 】提出了基于偏好的分层多目标遗传算法用于求解成像卫星鲁棒性调度模型； 提出了动态插入任务启发式算法用于求解成像卫星动态调度模型。 ( 3 ) 软件系统 美国国家航空航天局喷气动力实验室研究开发了一种航天任务规划调度环境 as p e n l j u j ( a u t o m a t e ds c h e d u l i n ga n dp l a n n i n ge n v i r o n m e n t ，a s p e n ) 系统。 a s p e n 是一个面向对象的系统，它提供了一组可重用的软件组件，实现了在复杂 规划调度系统中通用的一些要素，采用了一种基于局部邻域搜索的算法进行规划 调度。 美国v e r i d i a n 公司开发的通用资源、事件、活动调度系统g r e a s 【3 1 1 ( g e n e r i cr e s o u r c ee v e n ta n da c t i v i t ys c h e d u l e r ，g r e a s ) 。g r e a s 是一个专门用 于构建卫星任务规划及资源调度应用的软件平台，通过创建代表活动、资源、事 件以及约束的对象来进行建模，可以集成成熟的商业优化软件进行任务规划调度。 此外，g i 迎a s 还提供了功能完善的可视化模块，用于对任务规划及资源调度过程 进行展现和与用户进行交互。 美国a g i ( a n a l y t i c a lg r a p h i c si n c ) 公司在2 0 0 3 年5 月推出的卫星工具包 s t k 的规划调度模块s t k s c h e d u l e r f 3 2 j 。s t k s c h e d u l e r 模块是与s t k 完全集成的 附加模块，用户可以定义任务和资源，制定请求冲突的解决方案，以及通过多种 图形、表格、文本报告来分析结果。s t k 对象、可见性计算和事件报告可以方便 地从场景中输入，用于定义任务时序窗口和资源可利用时间。此外，s t k s c h e d u l e r 模块采用了神经网络和贪婪算法等优化技术进行任务规划调度。 1 2 2 人工智能规划问题研究现状 规划问题作为人工智能的一个重要的研究领域已有5 0 多年的历史。规划问题 研究的主要目的是建立起高效实用的规划系统。该系统的主要功能可以描述为： 给定问题的状态空间描述、初始状态和目标状态以及可以对系统状态之间进行变 换的动作集合，规划系统能够给出从初始状态变到目标状态的一个动作序列，即 规划方案。 规划问题根据环境的不同，可以划分为经典规划问题和非经典规划问题，一 般地，对于经典规划问题大多做以下的假设：1 ) 规划是动作的序列：2 ) 动作的 前提条件是确定的；动作的效果是确定的。最初经典规划问题还有一些细节的假 设，例如动作执行的时间是原子时间，即是瞬间完成的。但在面向实际应用的过 第5 页 国防科学技术大学研究生院硕士学位论文 程中，经典规划问题增加了时序约束、资源约束、外部事件约束和目标优化策略 等信息。非经典规划问题是在部分可观察的或随机的环境下的规划问题，不满足 经典规划问题的假设。本文研究的成像卫星操作规划问题很显然属于经典规划问 题的范畴。 为便于阐述，从规划问题表示、规划问题求解及应用领域三个方面对人工智 能规划问题研究现状进行回顾和总结。 ( 1 ) 规划问题表示 规划问题表示是规划问题求解的前提，一个实际问题领域的规划问题如果不 能通过规划语言来表示，那么任何一个规划器都不能对它进行求解，因此说规划 语言的发展是规划技术发展的关键因素i 圳。 s t r i p s 系统是由斯坦福大学的f i k e 和n i l s o n l 3 4 1 于1 9 7 1 年开发的，它使得规 划可以非常自然、容易的表示，因此在规划研究历史中具有划时代的意义。但在 面向实际应用的过程中，s t r i p s 语言有限的表示能力无法进一步满足一些实际问 题的模型化要求。这样如何设计一种能够有效表示实际问题的规划语言就成为了 规划技术应用的关键。动作描述语言a d l ( a c t i o nd e s c r i p t i o nl a n g u a g e ，a d l ) 是由e p e d n a u l t t 3 5 】于1 9 9 6 年提出的一种新的规划语言，该语言放宽了s t r i p s 语 言中的些限制，除了具有s t r i p s 语言的表示能力外，还能表达条件效果、量化 效果等语言特征。1 9 9 8 年由d r e wm c d e r m o t t 3 6 j 提出的规划领域定义语言( p l a n n i n g d o m a i nd e f m i t i o nl a n g u a g e ，p d d l ) 已经逐渐地成为国际规划大赛的标准语言，该 语言先后推出了p d d l l 2 、p d d l l 7 、p d d l 2 1 、p d d l + 、p d d l 2 2 、p d d l 3 0 等多个版本【3 7 j ，不仅给出了规划问题定义的语法，也从语义的角度给出了规划的 定义。p d d l 语言是一种命题式描述机制的领域描述语言，具有很强模型表达能力， 极大地推动了规划技术的发展。 总之，规划语言的研究是规划问题表示的关键，具有重要的现实意义和实用 价值。 ( 2 ) 规划问题求解 规划问题求解的研究主要集中于各种规划算法的研究，其目的是：当给定问 题的状态空间描述、初始状态、目标状态以及可用动作集合信息后，通过有效的 推理，给出从初始状态到达目标状态的规划方案，即自动给出一个动作序列，使 得在初始状态下通过执行这个动作序列就可以到达目标状态。 状态空间搜索是最直接的规划算法p 引，按照算法搜索的方向，分为前向状态 空间搜索算法和后向空间搜索算法，前者是从问题的初始状态出发，使用问题的 动作向前搜索目标状态；后者是从问题的目标状态出发，使用动作的逆，向后搜 索初始状态。实践证明，没有一个好的启发式函数，无论是前向还是后向搜索都 第6 页 国防科学技术大学研究生院硕士学位论文 不是岛效的。 偏序规划搜索规划空i 司【3 8 】，不承诺完全有序的动作序列，而是先生成动作之 间的偏序描述，然后逐步细化，最终在动作的偏序描述中提取全序规划解。偏序 规划的优点在于同全序规划相比，能够将规划问题分解成多个子问题进行求解， 而不足之处是不直接表示状态，所以很难获取精确的启发式信息。 可满足性规划s a t ( p l a n n i n ga ss a t i s f i a b i l i t y ) 方法是19 9 2 年k a u t z 3 9 , 4 0 , 4 1 1 等 提出的，其基本思想是猜测一个规划解的长度，将规划问题转化为一组命题公式， 然后再去求解可满足性规划问题，如果该组命题公式是不可满足的，那么就增加 规划解的长度，直到公式可满足，便返回规划解。该方法存在的缺点是：1 ) 编码 太大，这是因为对于每一个离散的时间点的所有可能的操作和命题都必须明确描 述；2 ) 无法处理连续变化的时间信息和时间约束的操作。 分层任务网络规划( h t n ) 的提出和开发与s t r i p s 系统几乎同时，但其理论 基础的建立却较晚1 4 2 , 4 3 】。e r o l t 4 4 1 等人对分层任务网络规划进行了较系统的理论研 究。分层任务网络规划的基本思想是将高级任务分解为原子任务对问题进行求解。 该方法由于不能处理那些事先没有定义好的高级任务，因而具有脆弱性的缺点。 图规划( g r a p h p l a n ) 是由b l u m 和f u r s t 于1 9 9 5 t 4 5 j 年提出的，该方法第一次采 用图的方式来解决规划问题，开辟了规划问题求解的新途径，使规划领域取得了 革命性进展。图规划算法在两个阶段间交替执行：图扩张阶段和规划提取阶段。 图扩张阶段正向扩张规划图直到目标状态的所有命题都出现且两两不互斥，或规 划图达到稳定状态为止。规划提取阶段逆向搜索规划图以求出规划解。 启发式规划方法是由b o n e t 和g e f f n e r 于1 9 9 8 年提出的【46 。，该方法利用启发 式函数来指导状态空间搜索，事实证明采用启发式的规划器比没有采用启发式的 规划器表现出了更强的问题求解能力。 时序图规划方法【47 】是由美国华盛顿大学的w e l d 教授于1 9 9 9 年提出的，该方 法的目的是在充分考虑现实世界规划问题的细节的基础上，进一步扩展规划算法 的处理问题的范围和提高规划的质量。该方法可以看作是对规划问题求解能力的 提升和对原有规划定义的扩展。与以往的规划方法不同，时序图规划方法关注的 是一类更为复杂的问题，其规划解往往更符合实际问题的需要。 近年来，将启发式与时序图规划相结合已经成为规划问题求解方法的一个重 要的研究方向。基于时序规划图的启发式规划方法不仅能够处理更为复杂的问题， 而且有较快的问题求解效率，更大程度地满足了现实问题的需求。 ( 3 ) 应用领域 规划技术正在逐渐被应用到现实生活中的多个领域【4 引，例如欧洲智能规划网 p l a n t 就列出了规划技术在航天航空、机器人、农业生产、工业制造、商业金融 第7 页 国防科学技术大学研究生院硕士学位论文 和军事国防等方面约2 0 项应用【4 9 】，而实际的应用远远不只这些。以下简要介绍几 个典型的应用领域【5 0 】：航天航空、机器人、智能企业和商业软件。 规划技术在航天航空领域的应用主要集中在各类航天器和无人机等领域的研 究。其中，比较典型是美国宇航局开发的a s p e n 系统【3 0 1 ，该系统获得了1 9 9 9 年 美国宇航局的软件比赛优秀奖，且广泛的应用于各类的航天器上。 规划技术在机器人领域的应用十分广泛，是一个非常活跃的研究领域。目前 主要研究领域包括【5 1 】：路径与运动规划、感知规划、导航规划、操纵规划和领域 无关规划。 规划技术在智能化工厂中的应用【5 2 】是指从生产设计到监测生产的一系列过 程。目前主要研究领域包括：生产流程规划和生产安排规划和调度。 规划技术在商业中的应用更加广泛，目前主要研究领域有：网络信息集成和 运输规划。 1 2 3 现有研究的特点和不足 ( 1 ) 现有研究大多针对成像卫星的任务计划自动生成问题，其研究成果十分 丰富；而国内外现有的关于操作指令的自动生成问题的研究资料却相对较少，因 此有必要针对成像卫星操作指令的自动生成问题，开展成像卫星操作规划中的关 键问题研究。 ( 2 ) 现有研究大多基于一些简化的问题求解模型，不考虑某些实际的任务需 求和约束条件，如数传任务需求、存储器容量约束以及时间窗口约束等，这样基 于简化模型求解得到的规划方案很难满足实际问题的要求。 ( 3 ) 缺乏对成像卫星问题领域共性的分析、归纳和总结，现有研究大多是针 对特定型号的卫星，建立的问题求解模型同星载设备密切相关，不具有一般性和 通用性，且都具有一定缺陷。 ( 4 ) 缺乏对问题求解算法的深入研究，问题求解算法的研究大多都针对具体 型号卫星的简化模型，灵活性和适应性较差。 ( 5 ) 现有研究大多仅考虑单一的优化目标，如时间代价或资源消耗等，这样 优化其中任何的单一优化目标都不能反映问题的本质。 ( 6 ) 缺乏对问题求解模型和算法统一求解框架和系统的研究，现有研究中规 划系统大多没有将问题求解模型和算法有效的区分开来，系统的灵活性和通用性 较差。 ( 7 ) 缺乏对子目标冲突消解机制的研究，由于成像卫星的星载资源和可用时 间有限，不可避免地会产生不同子目标之间的冲突，为了解决该问题，规划系统 设计时，必须包含一个子目标之间的冲突消解机制。 第8 页 国防科学技术大学研究生院硕士学位论文 1 3 论文的主要工作 本文重点研究了成像卫星操作规划问题建模、算法、系统以及子目标冲突消 解机制等关键问题。主要工作具体包括： 1 、基于p d d l 的成像卫星操作规划问题建模研究 成像卫星操作规划问题建模是成像卫星操