（计算机软件与理论专业论文）一种基于启发式搜索的感知图规划算法的研究与实现.pdf

e0 譬! i hi ， o j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东：i l n 范大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名： 主盈丝 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 ：l k n 范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东：i l n 范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：；毳笔荔 日 期：习础 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： e 钞 i 。婚 摘要 由于智能规划能应用于很多领域，近年来，智能规划研究得到了飞速的发展，一些 学者提出了不确定性规划问题。然而，经典的图规划算法无法解决不确定性规划问题。 因此，不确定性规划问题引起了众多智能规划研究者的关注，至今为止，能解决不确定 规划问题的规划器有s g p ，c f f ，p f f 等。这其中，最出名的是1 9 9 8 年由d a n i e ls w e l d ， c o r i nr a n d e r s o n 和d a v i de s m i t h 提出的感知图规划( s g p ) 。 感知图规划算法既有优点也有缺点，它的缺点有算法比较复杂，时间复杂度较高； 不具有启发式搜索，搜索是从初始状态出发，搜索可能为真的所有命题，效率较低；这 样致使s g p 规划器的整体性能很低。为了克服感知图规划的缺点，本文提出了基于启 发式搜索的感知图规划算法。 本文提出了一种基于启发式搜索的感知图规划算法的新算法。该算法与现有算法不 同，采用了f f 中使用的启发式方法。同时采纳了f f 中使用的放松动作。因此在图扩张 阶段，不用处理互斥关系，极大地提高了效率。本文提出的方法提高了规划器的求解能 力，对理论和实际应用都有很大的价值。 关键词：人工智能；智能规划；图规划；感知图规划；启发式搜索 a b s t r a c t ： r e c e n t l y , d u et oi n t e l l i g e n tp l a n n i n g sb r o a da p p l i c a t i o ni nm a n yf i e l d s ，s o m es c h o l a r s p r o p o s e du n c e r t a i np l a n n i n gp r o b l e m h o w e v e r , c l a s s i c a lg r a p h p l a n c a n n o ts o l v et h e u n c e r t a i np l a n n i n gp r o b l e m i ti sd i f f i c u l t f o ru n c e r t a i np l a n n i n gp r o b l e m si n i n t e l l i g e n t p l a n n i n gd o m a i n s ，b u t l e ym o r ea p p r o a c ht h er e a lw o r l dp r o b l e m s s o m ep l a n n e r sf o r u n c e r t a i np l a n n i n gp r o b l e m sa r ed e v e l o p e d ，w h i c ha r eb a s e do ng r a p h p l a n ，s u c ha ss g p , c f f a n dp f es e n s o r yg r a p h p l a n - s g pi st h em o s tf a m o u so n et h a td a n i e ls w b l d ，c o r i nr a n d e r s o na n dd a v i de s m i t hp r o p o s e di n19 9 8 1 1 1 eu n c e r t a i np l a n n i n ga l g o r i t h m sh a v es o m er e s t r i c t i o n s ，e g ，i t sa l g o r i t h mi sn o t s i m p l ea n dt i m ec o m p l e x i t yi sv e r yh i g h a l s o ，i td o e s n tu s eh e u r i s t i cr e s e a r c h , a n dt h e r e s e a r c hf r o mt h ei n i t i a ls i t u a t i o ni ss l o w s oo i lt h ew h o l et h ep e r f o r m a n c eo fp l a n n e rs g pi s h i 曲l yp o o r w ep r o p o s ean e wa l g o r i t h mb a s e do ns g pf o ru n c e r t a i np l a n n i n gp r o b l e m st o s o l v et h i sp r o b l e m t l l i sp a p e rm a k e sr e s e a r c ho nak i n d o fc o m p l e xp l a n n i n gp r o b l e m s u n c e r t a i n p l a n n i n gp r o b l e m s t h ep a p e ra p p l i e sa n o v e li n t e l l i g e n tp l a n n i n ga l g o r i t h mw h i c hi ss e n s o r y g r a p h p l a n 晰t 1 1h e u r i s t i cr e s e a r c h i nc o n t r a s tt ot h ee x i s t i n gm e t h o d s ，t h ea l g o r i t h ma d o p t s t h eh e u r i s t i cm e t h o d su s e di nf ea tt h es a m et i m e i ti n t r o d u c e st h er e l a xa c t i o na l s ou s e di n f f h e n c et h ea l g o r i t h mn e e d n td e a lw i t hm u t e xr e l a t i o n s ，a n da d v a n c e st h ea p p r o a c ho f f o r w a r dg r a p he x p a n s i o n n l ep r o p o s e dm e t h o di m p r o v e st h ep l a n n e rs o l v i n ga b i l i t y , b o t l l t h e o r e t i c a la n dp r a c t i c a la p p l i c a t i o no fg r e a tv a l u e k e yw o r d s ：a i ；i n t e l l i g e n tp l a n n i n g ；c j r a p h p l a n ；s e n s o r yg r a p h p l a n ；h e u r i s t i cr e s e a r c h i i - y 目录 摘要i a b s t r a c t i i 目录i i i 第一章引言1 第二章智能规划与启发式搜索的研究与发展2 2 1 智能规划简介2 2 2 启发式搜索概述3 2 3 启发式搜索的发展4 2 3 1u n p o p 一- 第一个启发式搜索规划器( 1 9 9 6 ) 4 2 3 2h s p - 一第一个性能卓著的启发式搜索规划器( 1 9 9 8 ) 4 2 3 3h s p r 后向搜索规划器( 1 9 9 9 ) 5 2 3 4f f 前向搜索规划器( 2 0 0 0 ) 5 2 3 5h s p 2 0 一- h s p 的改进( 2 0 0 0 ) 7 2 3 6a l t a l t ：一个混合式启发式状态规划器( 2 0 0 0 ) 7 2 3 7s a p a 能处理时间和资源的规划器( 2 0 0 1 ) 7 2 3 8b p 第一个真j 下意义上的双向搜索规划器( 2 0 0 1 ) 8 2 3 9a l t w l t 具有启发式搜索的p s p 规划器( 2 0 0 5 ) 9 2 3 1 0c f f 第一款性能突出的一致性规划器( 2 0 0 6 ) 9 2 4 启发式搜索总结与展望1 l 第三章基于启发式搜索的感知图规划算法( h s g p ) 1 2 3 1 感知图规划( s g p ) 1 2 3 1 1 条件效果1 2 3 1 2 感知动作与主题知识1 3 3 1 3 感知图规划的算法1 3 3 2h s g p 中使用的启发式1 5 3 3h s g p 算法1 6 3 3 1h s g p 图扩张算法1 6 3 3 2h s g p 解搜索算法1 6 第四章h s g p 规划系统的设计与实现1 8 4 1 系统介绍1 8 4 2 系统基本数据结构的设计1 8 4 2 1 结点结构1 8 4 2 2 命题结点结构1 9 4 2 3 动作结点结构1 9 4 2 4 目标的描述2 0 4 2 5 域和初始问题的描述2 0 4 2 6 规划图的描述2 l 4 3 系统工作流程2 3 i i i 4 4 开发工具及测试环境2 4 4 5 实验结果及分析2 4 结论2 6 参考文献2 7 后记3 0 在学期间公开发表论文情况3 1 东北师范大学硕士学位论文 第一章引言 智能规划是一个涵盖许多领域的交叉性学科，多年来，许多国内外优秀学者一直致 力于智能规划这一方向的研究，比较著名的规划器如b l a c k b o x 、f f 、l g p 、s g p i a n 等， 四届i p c 比赛的世界冠军都采用了图规划的技术。近年来，智能规划的研究更是发展飞 速。随着规划问题研究的深入，许多学者提出了不确定性规划问题。目前能解决不确定 性规划问题的规划器有s g p ，c f f ，p f f 等。感知图规划( s g p ) 是由d a v i de s m i t h 和d a n i e ls w e l d 等人提出的，该方法可以较快速解决不确定性规划问题。 现有的感知图规划算法复杂，而且效率较低。本文提出了一个全新的算法：基于启 发式搜索的感知图规划算法( h s g p ) ，该算法完善了解决不确定性规划问题的方法。 本文首先对基于图规划的启发式搜索进行了较详细的介绍，分析了目前启发式规划 的研究现状和发展情况，然后深入地研究了感知图规划理论。在对启发式搜索和感知图 规划深入研究的基础上，提出了基于启发式搜索的感知图规划算法。 l 东北师范大学硕士学位论文 第二章智能规划与启发式搜索的研究与发展 2 1 智能规划简介 由于感知图规划以图规划为基础，我们首先介绍一下智能规划以及图规划的基础知 识。包括智能规划的基本概念、应用领域以及规划问题知识表示等内容。 简单地说，能完成一个特定任务的动作序列就是一个规划。 通常情况下，我们都假设规划环境是确定性的、有限的、完全可观察的、静态的( 只 有当智能体行动时才发生变化) 以及离散的( 对于时间、行动、对象以及效果) ，这些被 称为“经典规划 ( c l a s s i c a lp l a n n i n g ) 环境，但是由于现实世界的复杂性，实际问题环 境往往是部分可观察的或随机的，即被称为“非经典规划环境。随着规划技术的应用j 的逐渐推广，越来越多的关注开始集中于非经典规划问题。1 随着智能规划研究的发展与成熟，使得智能规划在许多方面都得到了应用，例如在 机器人、航空航天中。规划问题表示的发展过程为：1 9 7 1 年提出的s t r i p s 系统、1 9 8 6 年提出的动作描述语言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 ) 晗1 、1 9 9 8 年提出的规划 领域定义语言( p d d l ) 口3 。其中，p d d l 语言后来成为公认的国际智能规划比赛 ( i n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n ，i p c ) 的标准语言，下面对这些语言做简单介绍。 _ 1 9 9 8 年第一届i p c 使用的语言是p d d l l 2 h 1 ，p d d l l 2 包含了a d l 和s t r i p s 表示。2 0 0 2 年，m a f i af o x 和d e r e kl o n g 哺3 在第三届i p c 中提出了p d d l 2 1 ，它的表 达能力可以分为5 个层次。p d d l + 嫡3 是对p d d l 2 1 的第5 层描述，在第5 层，动 作可以开始一个过程，一个动作或者一个事件可以结束一个过程。p d d l 2 2 盯1 保留了 p d d l 2 1 的前三层的表达能力，新增了导出谓词和初始化时间命题两种表达能力。 p d d l 3 0 晒1 是在2 0 0 6 年规划比赛( m c 5 ) 的描述语言，其主要的新特点是在p d d l 2 2 的基础上，增加了对所谓的“软目标 ( s o f tg o a l s ) 和“状态轨迹约束”( s t a t et r a j e c t o r y c o n s t r a i n t s ) 的描述。软目标是指对于合法规划解不一定必然会达到的期望目标。状态轨 迹约束主要是指规划结构中的约束，用来表示规划领域和或规划问题的合法规划解必 须满足的某些控制知识或限制。状态轨迹约束同样有“硬约束 和“软约束 之分。软 目标和状态轨迹约束都是用来表示某种偏好，而这种偏好通常都会反映到对规划解的质 量的评价。 2 东北师范大学硕士学位论文 2 2 启发式搜索概述 通常求解规划问题是困难的，在纯s t r i p s 规划中，如果我们忽略删除效果，规划 的求解难度会从p s p a c e 降低到p 阳3 。限制长度忽略删除效果的放松规划问题仍然是 n p h a r d 的，而当不限制长度时，是p s p a c e c o m p l e t e 的。而对于非经典规划问题求 解就更为困难，例如不确定性规划问题是e x p c o m p o l e t e 到2 e x p c o m p l e t e 的，概率 规划是从n p p p - c o m p l e t e 到不可判定的( u n d e c i d a b l e ) 。因此，怎样提高规划器的性能成 为非常值得研究的问题。在这方面，主要有问题公式化、搜索空间和启发式搜索等方法。 其中以启发式搜索效果最好，并且可以结合其他方法。求解启发式的方法有很多，主要 有取层号法、最大启发值法、取和法和放松规划( r p ，r e l a x e dp l a n ) 等。此外，我们还 可以利用互斥对启发式进行提高。启发式搜索可以用来指导前向、后向和p o c l ( p a r t i a l o r d e rc a u s a ll i n k ) 搜索等。 受2 0 世纪6 0 年代中期d r e w m c d e r m o t t 的在状态空间启发式规划的启发，许多研 究者转向这个方向进行研究。在过去的这几年，许多研究者在域独立、状态空间、启发 式规划这些领域进行了深入的研究，并且一些性能很高的规划器被开发出来。这些规划 器通常接受s t r i p s 公式。在s t r i p s 中，动作a 由三部分构成：p r e ( a ) ，a d d ( a ) 和 d e l ( a ) ，它们分别表示动作a 的前提，添加效果和删除效果。它们都是命题的集合。一 个规划任务p 是一个三元组 ，这里i 是初始状态，a 是可用动作集，g 是目 标集。状态被表示成一些命题的集合。基于规划任务p = ( a ，i ，g ) 的放松规划任务 p ，定义为： p ，- ( a ，i ，g ) a = ( p r e ( a ) ，a d d ( a ) ，巾) i ( p r e ( a ) ， a d d ( a ) ，d e l ( a ) ) a 放松规划是不可纳的( i n a d m i s s i b l e ) ，但是效率非常高。寻找一个最优的放松规划解 是n p h a r d 的。 为了叙述方便，我们先定义一些概念。 状态空间( s t a t es p a c e ) ：是一个四元组 ，其中，s 为有限状态集合，f 为状态转换函数，c 为成本函数c ( a ，s ) o ( 它表示在状态s 上执行动作a 的代价) 。如果 一个状态空间再加上一个给定的初始状态i 和目标集g ，我们叫做一个状态模型，即， 一个状态模型是一个六元组 ，其中，s ：有限非空状态集；i ：i s 是初始状态；g ：g ds 是非空目标集；a ：a ( s ) 3a 是在状态s 上的能够执行的动作； 坟a ，s ) ：对于所有s ，a a ( s ) ；c ( a ，s ) - 是在状态s 上的执行动作a 的代价。 3 东北师范大学硕士学位论文 2 3 启发式搜索的发展 本部分我们将对l o 年来国内外出现的采用启发式搜索的规划器，进行深入研究， 并指出其优缺点，进而给出改进方法。研究启发式搜索技术的发展过程与方向，对于我 们今后设计解决实际问题的启发式函数很有指导意义。 2 3 1u n p o p - - - , 第一个启发式搜索规划器( 1 9 9 6 ) 在智能规划发展的早期，很多人对偏序规划( p o p ，p a r t i a lo r d e rp l a n n i n g ) 进行了研 究，并开发出了许多规划器，但它们的性能不是很理想。其中，比较著名的一个规划器 是u c p o p u0 。，它能够处理a d l 动作描述，条件效果u u 和全称量化的前提和效果。u c p o p 没有使用任何启发式，在此我们不做具体介绍( 有关偏序规划的基础知识见h 2 3 ) 。下面我 们重点介绍它的扩展叫n p o p o 在状态空间启发式规划中，u n p o p 是第一个规划器。u n p o p 通过建立规划图来扩 展著名的m e a n s - e n d s 分析- - g r m g ( g r e e d yr e g r e s s i o n - m a t c hg r a p h ) ，它包括次目标和能 够得到次目标的动作。一个规划问题的次目标是问题的目标和能够得到这些目标动作的 前提。g r m g 的创建从问题目标开始，直到所有的次目标到达问题的最后一层，即， 初始状态。从图中得到的信息可以用于搜索阶段，这有两个目的：a ) 估计给定目标s 和初始状态之间的距离b ) 对图中没有出现的动作进行剪枝。搜索从目标开始，后向推 进，在每个状态都重建g i w s 。 2 3 2h s p 第一个性能卓著的启发式搜索规划器( 1 9 9 8 ) g r a p h p l a n 的出现，是规划发展史上的一个里程碑。g r a p h p l a n 以其卓越的 性能赢得了人们的重视。但在a i p s 9 8 中，h s p m l 超越了g r a p h p l a n 和s a t p l a n 一 举赢得了冠军。h s p 的确非常好，它和i p p n 钔，s t a n n 胡，b l a c k b o x 进行了比较，结 果显示，h s p 能求解更多的问题。 在h s p 中，它定义了一个估价函数： 咖) = 一朋一叫僦如筹s 其中，g s ( p ) 代表在状态s 上得到命题p 的代价。采用的启发式函数是h ( s ) = g s ( p ) 。 h s p 采用的是累加启发值( h a d d ) 。 g ；( c ) = g s ( r ) r e ( h s p 用h 砸d 来指导爬山算法。爬山算法非常简单，每步都选择最好的后继去扩展， 循环直到实现目标。因为累加启发值h 甜d 会高估代价，所以它是不可纳的。事实上，参 加a i p s 9 8 的是h s p l 2 ，用c 语言实现。 4 东北师范大学硕士学位论文 2 3 3h s p r 后向搜索规划器( 1 9 9 9 ) 在h s p 中，它的主要瓶颈是在对于每个新状态都要重新计算启发值。在h s p r 中， 一个重要的改进就是改变搜索方向来避免这个问题。 h s p r 从目标开始后向搜索，而不是从初始状态开始的前向搜索，即，回溯搜索。 在h s p r 中，最重要的一点就是：g ( p ) 是从初始状态i 开始到达命题p 的估计代价，这 个值不用每次计算。换句话说，在h s p r 中，估计代价g ( p ) 只从i 计算一次，就可以用 于定义任何状态的启发值。这是h s p 和h s p r 最大的不同点。在h s p r 中，采用的启发 式函数是h ( s ) = g ( p ) 。 p e s 在h s p 中，计算h ( s ) 时，目标固定，随着状态s 的改变，每次进入一个新的状态， 必须重新进行计算：而h s p r ，在计算h ( s ) 时，固定初始状态i ，计算到达每个状态的 值。在解的提取阶段，h s p r 利用启发值指导进行后向搜索，这与图规划类似。此外， h s p r 还采用了类似于图规划的互斥来进行剪枝。 最后，我们对h s p 和h s p r 使用的启发式函数总结如下： 办0 ) = g ( p ，s )加o ) = g ( p ，) p e g，j h s p 中使用的非可纳的启发值h a d d 来源于一个放松问题的最优代价函数的一个估 计值。在这里，删除效果被忽略了。这种忽略明显存在2 个问题：( 1 ) 这个估计值并不 好，因为它忽略了次目标之间的促进作用( 一个目标的实现可以使另一个子目标变得简 单) ( 2 ) 放松是不好的，它忽略了次目标之间的负相互作用。这需要一个更好的启发值来 指导搜索。尽管h s p r 在某些领域比h s p 性能优越，但是h s p r 只能找到合理的规划解， 并不难找到最优解。此外，h s p r 占用内存比较大。 2 3 4f f - - 前向搜索规划器( 2 0 0 0 ) f f 是一款性能非常优异的规划器，它在 p c 2 中，获得了第一名的好成绩。f f 中 使用的启发式如下： h ( s ) ：= m n la i a i 是时间步i 所选的并行动作的集合，n 是表示包含了所有目标的第一个命题层的 层数。实验表明，这种方式所获得的估计值通常要比h s p 估计值小，因为在求解一个 规划时要考虑命题之间的积极作用。同时，f f 还采用了两个启发式优化技术一n o o p 优先启发式( n o o p f i r s t ) 和难易程度启发式。 在g r a p h p l a n 中，使用了默认的n o o p 优先启发式，也就是，若存在一个n o o p 支持命题p ，那么在规划器尝试选择其它实动作支持p 前，优先考虑该n o o p 。对于放 松任务，n o o p 优先启发式，确保了所返回的规划是一个最小度量。使用这个策略，使 得g r a p h p l a n 所返回的规划将包含每个动作至多一次。如果能通过n o o p 到达一个 命题，那么我们就这样做。问题是，当n o o p 不可用时，我们应该选择哪个支持动作? s 东北师范大学硕士学位论文 一个好的想法就是选择支持动作的前提看起来“简单”的。从规划图的创建阶段来看， 我们能得到一个简单的度量对一个动作的前提的难易程度的度量，如下所示： d i f f i c u l t y ( o ) ：= p e p 他( o ) m i n ip 为时间步i 中命题层中的成员 当每个动作被首次插入图中时，它的d i f f i c u l t y 就被设置完成，在规划提取过程中， 当遇到一个命题的n o o p 不可用时，我们就简单的选择一个带有最小d i f f i c u l t y 的支持 动作。这个启发式在有多个动作支持同一个命题时运行的很好，但是，一些动作的 d i f f i c u l t y 必须小于其他的动作的d i f f i c u l t y 。 f f 中使用的搜索算法是爬山算法的一个改进算法一加强爬山算法。 在a i p s 9 8 竞赛中所使用的h s p i ( 实际参加比赛的为h s p l 2 ) ，也就是h s p 的第一 个版本。它使用的是一个改进的爬山算法搜索策略。此策略通常选择当前状态的一个 最优后继。我们选择使用局部搜索，是因为状态估计的代价是昂贵的，我们希望使用 尽可能少地状态估计来到达目标状态。 f f 中采用了一个不同的搜索算法，一个爬山的加强形式，它结合了局部搜索和全 局搜索。( 具体算法略，参见n 町) 与爬山算法相似，加强爬山算法也是从初始状态出发的。 那么，对于中间搜索状态s ，从s 出发，使用完整的广度优先搜索。这个算法或者找到 最近的较优后继( 而不是最优后继) ，即，带有严格较优估计的最近的状态s ，或者失败。 在后种情况下，整个算法失败，在前种情况下，把从s 到s 的路径添加到当前规划中， 并且迭代执行该算法。直到到达目标状态一估计值为零的状态，搜索结束。 对从s 出发的广度优先算法的执行进行标准化，所产生的状态保存在队列中。搜 索反复删除队列的第一个状态s ，并且通过运行g r a p h p l a n 对其进行估计。如果这 个估计值优于s 的估计值，搜索成功。否则，把s 的后继放到队列尾部。( 避免平原和局 部极小) 为了避免重复访问同一状态，我们把访问过的状态放在内存中的一个哈希表 中。如果没有新的状态出现，广度优先搜索失败。此外，f f 中另一个重要的创新点是 帮助动作的使用。状态s 帮助动作集h ( s ) 定义为如下形式： h ( s ) ：- - oip r e ( o ) s ，a d d ( o ) n g l ( s ) o ) 在这里，g l ( s ) 表示当( a ，s ，g ) 任务开始时，在第一时间步放松的g r a p h p l a n 所创建的目标集合。总之，我们把这些在第一时间步可应用的并且能至少添加一个目标 ( 命题) 的动作视为帮助动作。 下图给出了f f 系统体系结构，它显示了f f 是如何安排它的最基本的技巧的。 任务描述广 解，失败 卅旬强派爬山算法卜 图lf f 系统基本体系结构 6 东北师范大学硕士学位论文 2 3 5h s p 2 0 h s p 的改进( 2 0 0 0 ) 如前所述，h s p 可以和当时最好的规划器相媲美。然而，h s p 不是一个最优的规 划器。更糟糕的是h s p 采用的算法是不完备的。h s p 2 0 n 铂使用最好优先算法( b e s t f i r s t s e a r c h ) 来克服了这个问题。因此，我们把用递增启发值h a d d 来指导b f s 算法的规划器 叫做h s p 2 0 。b f s 像a 掌算法一样需要构建节点的o p e n 表和c l o s e d 表。但是节点的权 值是通过估价函数f ( n ) = g ( n ) + w 木h ( n ) 来给定，这里，g ( n ) 是一个累积代价，h ( n ) 是到目标 的估计代价，w 1 为常量；w = l 时，为a 算法。w l 就是w a * 算法。h s p 2 0 使用了 非可纳的启发值h 。d d 来指导w a * 算法，h a d d 在产生每个新状态时都从头开始计算。参数 w 的值一般固定为5 ，即使w 的值在 2 ，l o 之间，不会产生大的影响。实验结果表明， h s p 2 0 的性能在整个h s p 家族中，整体性能是最优异的。 2 3 6a l t a l t ：一个混合式启发式状态规划器( 2 0 0 0 ) a u a l t n 印是用c 语言实现的规划器，建立在规划器s t a n 和h s p r 基础上。s t a n 是一个用来生成规划图的g r a p h p l a n 模式的规划器；前面讲过，h s p r 是一种提供优 化的状态搜索机制的启发式规划器，a l t a l t 利用基于图规划的启发函数来指导其搜索 过程。在a l l a l t 中默认使用的启发函数是h a d i s 。m 2 m ，启发函数h a d j s 。m 2 m 的基本思想 是从考虑次目标之间的促进作用及反作用来调整和代价法。h a d i s u m 2 m = c o s t p ( s ) + 么 m 科( s ) ，其中，c o s t p ( s ) 利用公式c o s t p ( s ) = l + c o s t t p ( s + p r e ( a ) 一a d d ( a ) ) 来计算，么( s ) 用 1 m 双( s ) = m a x 6 ( p ，q ) 来计算。其中，m a x 8 ( p ，q ) = l e v ( p ，q ) 一m a x ( 1 e v ( p ) ，l e v ( q ) ) ，p ， q s 。l e v ( s ) 表示命题集合s 中的所有命题以非互斥关系出现在串行规划器中的最小命 题列。a i ，t a l t 的性能a i p s 0 0 的规划器大赛上的测试问题都是非常健壮的。对a u a l t 的主要评价为：1 ) a i ，t a i t 的性能优于s t a n 与h s p r ，充分显示了g r a p h p l a n 及其 启发式状态空间搜索的互补作用的力量。2 ) a l t a l t 能够降低启发式计算，虽然所生成 的解的质量有点影响。 2 3 7s a p a 能处理时间和资源的规划器( 2 0 0 1 ) s a p a ( s c h e d u l i n ga n dp l a n n i n ga g e n t ) n 钔是一个前向状态空间系统，用i a v a 实现。 它采用基于图规划的启发式，生成代价敏感时序规划( c o s t s e n s i t i v et e m p o r a lp l a n n i n g ) 。 s a p a 满足规划质量的多目标和执行时的代价。动作具有持续性，它们的前提条件可以 是即时的( i n s t a n t a n e o u s ) 或是持续的( d u r m i v e ) ，并且动作效果可在执行期间的任何 时间点产生。每一个动作a 和一个执行代价c e x e c ( a ) 相关。从规划图中产生启发 式，对每一个动作引入代价函数c ( a ，t ) ，表示估计的代价使动作a 在时间t 执行。类 似地，对每一个命题p ，代价函数c ( p ，t ) 说明在时间t 到达p 的代价。s a p a 用与t g p 口剐 不同的方法通过规划图传播代价信息：c ( a ，t ) = m a x c ( p ，t ) ：f p r e ( a ) ( 最大化 传播) ；c ( a ，t ) = c ( p ，t ) ：p e p r e ( a ) ) ( 和传播) ；c ( a ，t ) = 0 5 m a x c ( p ，t ) ：p 7 东北9 币范大学硕士学位论文 p r e s ( a ) + 0 5 c ( p ，t ) ：p p r e ( a ) ( 结合传播) 。通常在与固定点相连时才传播代价 信息，并在整个过程中忽略互斥信息。这样s a p a 基于传播的代价函数产生几个启发 式信息指导规划进行前向搜索。对于每一个状态s ，h ( s ) 通过f ( c ( p s ) ，t ( p s ) ) = a c ( p s ) + ( 1 a ) t ( p s ) ，这里t ( p s ) 是具有限定代价( 从s 开始的规划到达到目标所估 计的最小量) 和所有目标都达到的最早时间，c ( p s ) 是每一个单独目标在它们各自的最 终期限达到的代价总和，o a l 。 2 3 8b p 第一个真正意义上的双向搜索规划器( 2 0 0 1 ) 以上分析表明，虽然这些规划器的性能在很大程度上取决于它们使用的启发式函数 的精确性，但是，实验表明，它们搜索空间的顺序也对它们有很大的影响。像u n p o p ， g r t 陋2 2 1 和h s p a s p 乜羽，它们从初始状态开始搜索，直到达到目标；相反，h s p r 和 a u a l t 从问题的目标开始搜索，直到它们达到问题的初始状态。在h s p 2 0 中，用户 可以自己决定搜索的方向，实验表明，这存在一个明显的问题，有些人偏爱这个或另一 个方向，而没有证据表明这两个方向应该被选择。下面我们介绍一种双向策略一 b p ( b i d i r e c t i o n a lh e u r i s t i cp l a n n e r ) 2 朝。 双向搜索在一些有关人工智能的教材中经常提到的一种比较著名的搜索策略口印。但 是，作为一种搜索策略，双向搜索并没有被广泛采纳。特别是在规划领域，仅仅有一些 系统能够执行两个方向的混合搜索。仅有的双向搜索规划器，据作者所知，有 p r o d i g y 泌2 7 1 ，f l e c s 乜8 3 等。所有的这些规划器都是由卡耐基梅隆大学的p r o d i g y 项目( 有关r o d i g y 项目的更多信息，参见：h t t p ：w w w c s c m u e d u p r o d i g y ) 开发 的。但是实际上，这些规划器都是前向规划器，后向搜索仅作为一种选择动作的机制。 b p 是第一个真正意义上的双向搜索规划器。 b p 是一种域独立的混合搜索策略，组合了前向和后向搜索策略。搜索从初始状态 开始，用一个加权的a + 算法向前搜索，直到没有更优的状态为止：在这一点，算法开 始改变方向，并且从目标开始搜索，直到到达前面一步的最佳状态。在找到一个解之前， 搜索方向可能改变很多次。 b p 使用了两个域独立的启发函数，一个是基于a s p h s p 的目标排序( g o a lo r d e r i n g ) 技术，另一个是双向规划系统( b i - d i r e c t i o n a lp l a n n i n gs y s t e m ) 。并对a i p s 一些规划实 例进行了验证，得到了很好的效果。在前向搜索阶段，b p 使用的是一个爬山算法，在 后向阶段，b p 处理的是状态集，而不是像很多规划器那样处理的是状态。它包括回溯 测试和状态回溯两个方面。我们可以用下式表示： h ( s ) = w l l ( s ) + w 2 x h ( s ) 其中，l ( s ) 是从初始状态得到到达状态s 的时间步数，h ( s ) 是回溯阶段返回的启 发值，w l ，w 2 是用户自己定义的变量( 在a 算法中的权值) 。 随着智能规划的发展，近年来p s p ( p a r t i a ls a t i s f a c t i o np l a n n i n g ) ( 亦称过描述 o v e r - d e s c r i p t i o np l a n n i n g ) 在许多应用领域兴起，它主要应用在实体要达到比现有资源 8 东北师范大学硕士学位论文 多的目标。p s p 规划的目标是寻找一个规划，使得它有最高的净效益，它只能满足目标 的部分要求。在p s p 问题中，最著名的是n e tb e n e f i t 问题。早期比较著名的规划 器是o p ( o f i e n t e e f i n gg r a p h ) 2 9 o 迄今为止，性能比较突出的具有启发式搜索的p s p 规 划器有s a p a p s ，a l t w l t 3 们，p r e p l a n 3 1 ，o p t i p l a n 删等。 2 3 9a l i w l t , - - 具有启发式搜索的p s p 规划器( 2 0 0 5 ) a l t w l t ( al i t t l eo f n l i sa n daw h o l el o to f t h a t ) 是一款具有启发式搜索的p s p 规划器。这个规划器之所以取名为a l t w l t ，是因为它以a u a l t p s 为基础。下面我们 以n e tb e n e f i t 问题为例来介绍a l t w l t 的工作原理。在n e tb e n e f i t 问题中， 每个合取目标都有一个相关的固定u t i l i t y ，每个实例化动作都有一个与之相关的代价。 我们的目标就是找到一个最优的n e tb e n e f i t ，即，总u t i l i t y 与总代价之差。 我们定义一个规划问题p = ( a ，i ，g ) ，( 有关p s p 的更详细知识见。h 1 ) 下图是许多 p s p 问题的层次结构。 图2 p s p 层次结构图 a l t a l t p s 使用一个贪心方法来到达前面的次目标。次目标可能是指数级的。一旦 目标被选择，a l l a l t p s 就找到了一个规划解。但是a l t a l t p s 使用的启发式对u t i l i t y 和代价是敏感的。要计算启发值，必须首先计算代价传播。此外，a l t w l t 在求解时， 没有考虑互斥情况；如果放松规划中有互斥情况，则对目标进行惩罚( p e n a l t y )使用相 互作用因素来调整代价，类似的来调整和启发式m a x 9 1 ，9 2 。g l e v ( 9 1 ，9 2 ) 一m a x ( 1 e v ( 9 1 ) ， l e v ( 醇) ) 。最终为每个目标寻找最好的规划。a l t w l t 比较突出的一点是，考虑了残 余代价( r e s i d u a lc o s t ) 。 此外，o p t i p l a n 是第一个参加i p c ( 具体指2 0 0 4 年的i p c - 4 ) 的使用整数编程 i p ( i n t e g e rl i n e a rp r o g r a m m i n g ) 的求解s t r i p s 问题的规划器。在i p c 中，获得了第二 名的优异成绩。 2 3 1 0c f f 第一款性能突出的一致性规划器( 2 0 0 6 ) 一致性规划是一种不确定性规划。不确定规划的来源有两个，分别为初始状态不确 定和动作效果不确定。一致性规划是处理初始状态不确定的规划方法。同时，一致性规 9 东北师范大学硕士学位论文 划在规划执行过程中不具有感知能力b 别。无论从哪个可能初始世界开始，我们都能找到 规划解。一致性规划可以转化为在信念空间( 即，它的元素是可能世界状态的集合) 中的 搜索问题。b o n e t 和g e f f n e r 。剐引入了一种在信念状态中利用启发式来指导前向搜索解 决规划问题的方法。但是在信念状态中可能世界的个数非常大甚至在一些比较简单 的例子中，在其系统g p t 中，都不可解。其他的一些求解器，像b e r t o l i ，c i m a t t i ，和 r o v e r i 口7 啦! 用b d d 来表示信念状态来处理这个问题。通