（计算机软件与理论专业论文）自动规划中群体智能技术的研究.pdf

摘要 自动规划中群体智能技术的研究 专业：计算机软件与理论 博士生：柴啸龙 指导教师：姜云飞教授 摘要 自动规划是人工智能中的一个重要研究领域，在机器人的动作规划，货运码 头调度，以及工厂的车间作业调度，现代物流管理以及宇航技术等领域中都有着 广泛的应用，因此受到了研究者越来越多的重视。自动规划研究的是通过对周围 环境进行认识与分析，根据预定实现的目标，对有限个可供选择的动作及其所提 供的资源限制进行推理和评估，综合制定出实现目标的一个动作集的有序序列， 即规划解。不确定规划是自动规划中的一个研究分支，最近几年迅速成为了一个 新的研究热点。其中的不确定性有动作效果的不确定性，状态的不完全观察，以 及扩展性目标等。 群体智能是通过模拟自然界生物群体行为来实现人工智能的一种方法，它强 调个体行为的简单性，群体的多样性和全局性，以及优异个体带来的进化性，并且 有不断修正和进化的策略。群体智能在很多应用领域中都表现出了较好的寻优性 能。如果能将群体智能算法引用到自动规划领域中，是一个预期良好的规划策略。 本文详细介绍了蚁群规划算法的设计及算法，在规划图的基础上引入蚁群算 法，提出并定义了基于规划图的路节，路线，提出了适合真伪动作序列的理想命 题集，并给出了评价路线优劣的不协调度，通过不协调度的值的变化，向着不协 调度越来越小的方向可以引导规划解的搜索。通过禁忌连接集的引入，可以极大 地缩减搜索空间。另外，作为一个启发式公式，评价蚁群路线的不协调度可以方 便地融入一些领域知识，从而进一步提高算法的效率。并通过实例分析验证了算 法的有效性和可行性。 摘要 在传统规划问题上，寻找规划解都是n p ，甚至n p 完全的问题，如果动作的 执行效果带有不确定性，如在m a r k o v 决策过程的规划问题中，规划的求解将会 更加困难，现有的m a r k o v 决策过程的规划算法往往用一个整体状态节点来描述 某个动作的实际执行效果，试图回避状态内部的复杂性，而现实中的大量动作往 往都会产生多个命题效果，对应多个命题节点。为了能够处理和解决这个问题， 本文提出了映像动作，映像路节和映像规划图等概念，并在其基础上提出了 m a r k o v 决策过程的蚁群规划算法，从而解决了这一问题。并且证明了算法得到 的解，即使在不确定的执行环境下，也具有不低于一定概率的可靠性。 关键词：自动规划，规划图，m a r k o v 决策过程，不确定规划，群体智能算法 a b s t r a c t r e s e a r c ho ns w a r m i n t e l l i g e n c et e c h n o l o g yi nt h e a u t o m a t e dp l a n n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：c h a ix i a o l o n g s u p e r v i s o r s ：p r o f j i a n gy u n f e i a b s t r a c t a u t o m a t e dp l a n n i n gi sa ni m p o r t a n tr e s e a r c hf i e l di na r t i f i c i a li n t e l l i g e n c e t h e p l a n n i n gt e c h n o l o g yh a sb e e na p p l i e di n t om a n yf i e l d s ，s u c ha st h et a s ks c h e d u l i n go f w o r k s h o p ，m o d e ml o g i s t i c sm a n a g e m e n t ，a n dt h es p a c en a v i g a t i o nt e c h n o l o g y s ot h e r e s e a r c h e r sa r ep a y i n gm o r ea n dm o r ea t t e n t i o n st ot h er e s e a r c ho ft h ea u t o m a t e d p l a n n i n g a u t o m a t e dp l a n n i n gs t u d i e sh o wt og e ti n f o r m a t i o na n dr i g h ta n a l y s i sf r o mt h e e n v i r o n m e n t s ，h o wt oc o n s t i t u t ea no r d e r e da c t i o n ss e q u e n c e ，t h a ti st h ep l a n n i n g s o l u t i o n , b ya n a l y s i n gt h ef i n i t ea c t i o n sw h i c hw i t hd i f f e r e n tr e s o u r c e sa n dc o s t i n r e c e n ty e a r s ，i n c r e a s i n gi n t e r e s th a sb e e nd e v o t e dt op l a n n i n gu n d e ru n c e r t a i n t y , a n d d i f f e r e n tr e s e a r c hl i n e sh a v eb e e nd e v e l o p e d p l a n n i n gw i t he x t e n d e dg o a l su n d e rf u l l o b s e r v a b i l i t y , a n d t h ea c t i o n e x e c u t i n g e f f e c t sw i t h u n c e r t a i n t y u n d e rf u l l o b s e r v a b i l i t y ( o rp a r t i a lo b s e r v a b i l i t y ) ，e t c ，h a v eb e e nt h er e s e a r c hf o c u s e s s w a r m i n t e l l i g e n c ei sa na r t i f i c i a li n t e l l i g e n c em e t h o dw h i c hw o u l ds i m u l a t et h e n a t u r eb i o l o g ys w a r mb e h a v i o r s s w a r mi n t e l l i g e n c ee m p h a s i z e st h es i m p l e n e s so f t h ei n d i v i d u a lb e h a v i o r ，t h ed i v e r s i t ya n dg l o b a lb e h a v i o ro ft h es w a r m ，a n dt h e e x c e l l e n ti n d i v i d u a lw o u l db r i n ge v o l u t i o n st ot h es w a r m a n dt h es w a r mi n t e l l i g e n c e a l s oh a st h ep e r s i s t e n tp o l i c yo fo b t a i n i n gr e v i s e m e n ta n de v o l u t i o n a n dt h es w a r m i n t e l l i g e n c et e c h n o l o g yh a sb e e ns u c c e s s f u l l ya p p l i e di n t om a n yf i e l d s ， i nt h i sp a p e r ，t h ed e s i g n i n ga n dt h ea l g o r i t h m so ft h ea n tc o l o n yp l a n n i n gm e t h o d - - a r ed e t a i l e dp r e s e n t e d a n dt h ec o n c e p t so fp a t h s e c t i o n ，p a t ha r ep r e s e n t e db a s e dt h e p l a n n i n gg r a p h a n dt h ei d e a lp r o p o s i t i o ns e ta r ea l s op r e s e n t e dw h i c hc o u l du s e db y t r u ea c t i o n ss e q u e n c eo rt h ef a l s e t h ed e g r e eo fd i s o r d e ri sp r e s e n t e dt oe v a l u a t et h e p a t h sf o u n db ya n t s t h r o u g ht h ev a l u ec h a n g i n go ft h e t h ed i s o r d e rd e g r e e ，t h e s e a r c ho ft h ep l a n n i n gs o l u t i o nc o u l db ei n d u c e dt ot h ed i r e c t i o no fm o r el e s sd i s o r d e r d e g r e e a n dt h es e a r c h i n gs p a c ec o u l db ec u td o w nn o t a b l yt h r o u g ht h et a b o o c o n n e c t i o ns e t a sah e u r i s t i cf o r m u l a ，t h ed i s o r d e rd e g r e eo ft h ea n tp a t h sc o u l db e a d d e dw i t hs o m e d o m a i nk n o w l e d g e s i nt h ec l a s s i c a lp l a n n i n gp r o b l e m s ，t of o u n dap l a n n i n gs o l u t i o ni sa nn p p r o b l e mo re v e na nn pc o m p l e t ep r o b l e m i f t h ee x e c u t i n ge f f e c t so ft h ea c t i o nt a k e u n c e r t a i n t y ，s u c ha st h ep l a n n i n gp r o b l e mo fm a r k o vd e c i s i o np r o c e s s e s ( m d p ) ，t h e p r o b l e mw o u l db em o r ed i f f i c u l t i nt h i sp a p e r , s o m ec o n c e p t ss u c ha st h er e f l e c t i o n a c t i o n ，r e f l e c t i o np a t h s e c t i o n ，a n dr e f l e c t i o np l a n n i n gg r a p ha r ep r e s e n t e db a s e dt h e g r a p hp l a na l g o r i t h m ，a n dt h ea n tc o l o n yp l a n n i n ga l g o r i t h mw o u l db ed e s i g n e db a s e d t h e m i nt h ea l g o r i t h m ，t h ea c t i o nc o u l dg e n e r a t em o r en o d e st h a te a c ho n ei sa r e p r e s e n t a t i o no fap r o p o s i t i o n i ti sp r o v e dt h a tt h e r ea r en ol e s st h a nac e r t a i n t y p r o b a b i l i t yt h a tt h es o l u t i o no f t h ea n tc o l o n yp l a n n i n ga l g o r i t h mw o u l db er e l i a b i l i t y e v e ni nt h eu n c e r t a i na c t i o ne x e c u t i n ge n v i r o n m e n t s k e y w o r d s ：a u t o m a t e dp l a n n i n g ，p l a n n i n gg r a p h ，m a r k o vd e c i s i o np r o c e s s e s ， p l a n n i n gw i t hu n c e r t a i n t y ，s w a r mi n t e l l i g e n c ea l g o r i t h m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：紫啸右 日期：2 0 0 q 年- i2 r 月2 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：柴哺柱 导师签名 日期：砷俨l 乙月z 日 日期：年月 日 第1 章绪论 第1 章绪论 自动规划( a u t o m a t e dp l a n n i n g ) y 、称智能规划。 作为基础性知识，本章主要介绍智能规划的研究背景，发展历史【1 1 。介绍智 能规划和一般人工智能问题求解的区别，阐述智能规划和普通的搜索问题的区 别；并介绍智能规划的一些应用。以及若干智能规划的基本理论和基本的求解技 术。介绍了论文的研究工作，主要创新点与贡献，最后给出了论文的结构。 1 1 智能规划研究历史 智能规划由于其研究具有很强的理论价值和应用背景，因此虽然研究历史不 长，但是自诞生开始就一直广受国内外学者的关注和研究【l 捌。 人们对智能规划的研究迄今已经有半个多世纪了，最早可以追溯到1 9 5 6 年 n e w e l l 、s h a w 和s i m o n 设计的逻辑理论家( l o g i ct h e o r i s t ) 程序，这个系统采 用了启发式信息和反向搜索技术；随后他们设计的g p s 系统把领域知识与一般 的搜索控制信息相分离。上述两个系统特别是g p s 在人工智能领域中具有非常 重要的地位，但它们还不是真正面向规划问题研制的智能规划系统。 1 9 6 9 年，g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统【3 】，这一系统被大多数的智能规划研究人员认为是第一个规划系统，原因就 在于他是第一个面向现实规划问题提出的规划系统；1 9 7 1 年，f i k e s 和n i l s s o n 设计的s t r i p s 系统【4 】在智能规划的研究中具有重大的意义和价值，他的突出贡 献是引入了s t r i p s 操作符的概念，使得原来很神秘的规划问题求解变得明朗清 晰起来；此后到1 9 7 7 年先后出现了h a c k e r 、w a r p l a n 、小t e r p l a n 、 a b s t r i p s 、n o a h 、n o n l i n 等规划系统。在这十年间人们研究智能规划的兴 致比较高，普遍认为规划问题必须用定理证明的理论来解决，直到c h a p m a n 设 第l 章绪论 计的规划系统t w e a k 5 】出现。c h a p m a n 详细全面地分析了利用定理证明理论解 决规划问题中的关键问题：模型与规划解的对应关系，提出了著名的模态真值标 准( m o d a lt r u t hc r i t e r i o n ) 理论。c h a p m a n 的分析使人们认识到简单地利用定理 证明的方法来解决规划问题是很难的，因此这以后到1 9 9 0 年间，在人们发现新 的求解方法之前，对智能规划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a k 和 p r o d i g y t 6 j 等较少的智能规划系统出现。 1 9 9 1 年，s o d e r l a n d 和w e l d 等人设计了世界上第一个完备、完全、系统的非 线性规划系统s n l p 7 , 8 】，奠定了非线性规划系统的基础。1 9 9 2 年，k a u t z 等把规 划问题求解转化为可满足( s a t ) 问题【乳1 1 】，一反定理证明式求解方法，利用在 约束可满足问题算法上的突破，有效地解决了部分规划问题。后来，基于此理论 的b l a c k b o x 规划系统【1 2 】在第一届智能规划系统的比赛中表现了非凡的解决问题 能力，一举夺魁，开辟了解决规划问题的又一新途径。1 9 9 5 年，a v r i mb l u m 等 设计的图规划系统g r a p h p l a n 1 3 】第一次采用图的方式来解决规划问题，并且提出 了用于规划的规划图的概念。后来很多规划系统都借鉴了图规划系统的方法，参 加第一届智能规划比赛的规划系统除委内瑞拉的h s p 外，其它四个规划系统 s g p 、b l a c k b o x 、i p p 和s t a n 都或多或少地采用了图规划的某种( 些) 技巧， 并且对图规划做了相应的扩充：s g p 加入了用户互操作界面；b l a c k b o x 则综合 了基于规划图的快速规划扩展和基于s a t 的快速规划验证；i p p 扩充了图规划 的问题描述语言，如支持a d l 规划描述语言，它能够处理条件效果等，这样它 的表达能力比图规划系统要强大；s t a n 在减少搜索和构造规划图的费用上做了 扩充。这些规划算法都是部分序或非线性的通用规划系统，此次比赛表明部分序 方法在规划求解中具有举足轻重的地位。两年以后，在第二届规划比赛上，部分 序规划的思想得到了进一步验证，并且在规划过程中规划知识被人们广泛关注。 在参加比赛的十六种规划系统中采用启发式知识的有十一个，并且采用启发式知 识的规划系统比没有采用启发式知识的规划系统得到的规划解效果好：例如比赛 评委评选出的最佳规划系统t a l p l a n n e r 和f f ，以及排名其次的s t a n 、h s p 2 、 m i p s 和s y s t e mr 都是采用启发式知识的规划系统，在此次比赛中采用启发式知 识的规划系统表现出很强的问题求解能力，而第一届比赛的冠军 b l a c k b o x ( g r a p h p l a n + s a t ) 则由于没有采用启发式知识在此次比赛中表现不如人 第1 章绪论 意。 图1 1 经典智能规划系统产生年代及发展情况表 综上所述，规划问题求解从最初的定理证明方法发展到s t r i p s 方法，之后 又出现了非线性规划系统，非线性规划系统采用目标导向的方式来生成规划：一 方面使得规划的生成速度大大提高；另一方面，由于是目标导向的生成方式，因 此使得生成规划的质量比较好。现在人们又在此基础上加入了启发式信息，进一 步提高了规划求解的效率和质量，另外，已经有人提出了建造基于知识的规划系 统的设想。 第l 章绪论 进入9 0 年代以来，由于在命题可满足领域的研究取得了较大进展，求解命题 可满足的s a t 求解器的速度得到了极大提高，这促进了基于s a t 的规划器的出 现。1 9 9 2 年，k a u t z 等首次把规划问题求解转化为可满足( s a t ) 问题 1 4 - 1 6 】，一 反定理证明式求解方法，充分利用在命题可满足问题算法上的突破，有效地解决 了部分规划问题。后来，基于此理论的b l a c k b o x 规划系统【1 6 j 在第一届智能规划系 统的比赛中表现了非凡的解决问题能力，一举夺魁，开辟了解决规划问题的又一 新途径。1 9 9 5 年，a v r i mb l u m 等设计的图规划系一e j e g r a p h p l a n t l 3 】第一次采用图的 方式来解决规划问题，并且提出了用于规划的规划图的概念。后来很多规划系统 都借鉴了图规划系统的方法，参加第一届智能规划比赛的规划系统除委内瑞拉的 h s p * f ，其它四个规划系统s g p 、b l a c k b o x 、i p p 和s t a n 都或多或少地采用了图 规划的某种( 些) 技巧，并且对图规划做了相应的扩充：s g p 加i 入了用户互操作 界面；b l a c k b o x 贝1 j 综合了基于规划图的快速规划扩展和基于s a t 的快速规划验 证；i p p 扩充了图规划的问题描述语言，如支持a d l 规划描述语言，它能够处理 条件效果等，这样它的表达能力比图规划系统要强大；s t a n 在减少搜索和构造 规划图的费用上做了扩充。 最近一些年来，类经典规划和非经典规划逐步得到深入的研究，并开始成为 研究热门，如规划图计算的深入研究，命题可满足技术的深入研究，以及约束可 满足技术，启发式控制的进一步研究等等。研究难度比较大的还有带时间和资源 的约束规划，不确定规划等等。 1 2 智能规划的简介 1 2 1 智能规划的具体含义 ”规划”这一术语广泛出现于机器人、控制理论和人工智能等研究领域中。由 于在多个不同的研究领域中都会用到”规划”这个术语，而在不同的领域中，”规 划”的具体含义却有所差别，因此，为了使我们能从概念上对不同领域中的”规划” 含义有个清醒的认识，我们从宏观上介绍各个不同领域中的”规划”的含义。 4 - 第1 章绪论 在机器人研究领域中，规划的含义是指一类具有感知、动作、计算能力的机 械系统( 比如机器人) 自动完成给定任务的过程。通常，在机器人研究领域中， 规划又叫运动规划或路径规划。例如，要求机器人在无碰撞的情况下将钢琴或沙 发从一个房间搬到另外一个房间。 在控制理论领域同样也存在所谓的规划，但其中规划的含义主要是研究如何 设计由微分方程所表示的物理系统( 比如，汽车、飞机、电子系统等) 的输入， 使得这些非线性动态系统能从初始状态转换成目标状态。例如，设想要对一飞行 器进行远程控制，使之从当前停留的位置移动到另一个具体的目标位置，在控制 理论中，规划的含义是指在理想的仿真条件( 忽略由于模型不精确引起的不确定 的情况) 下，要求能设计出相应的算法以计算出为完成上述任务所需要的期望输 入。 而在人工智能领域，规划的含义是指在给定工作环境下，由机器自动生成一 系列的动作，使之达到预先给定的目标。通常，人工智能中所研究的规划问题， 虽然也可用连续空间建模方法进行建模，但更为自然的建模方法是定义离散的状 态集合以及能作用于这些离散状态集合的有限动作集合，此时规划解是指适当的 动作序列。这类规划问题通常比较易于描述，因为在大多数情况下状态空间是有 限的，或者至少是可数无限的( 也就是说，对每一个状态均有唯一的整数与之对 应) ，因此，对这类规划问题的描述，一般不需要使用到机器人空间规划或运动 规划领域中常要使用的几何模型或微分方程。最近，为了能对那些存在不确定因 素环境下的规划问题、考虑有敌手环境下的规划问题以及带优化的规划问题进行 有效建模，许多有关决策理论的思想也被整合到规划问题的研究中来。 由于本文对规划的研究主要是属于人工智能范畴中的规划研究，因此对这方 面的介绍通常都会比较详细，并且后文除有特别说明，规划的含义也是指人工智 能范畴内的规划。而对其他领域，比如机器人领域或控制理论领域的介绍则一般 都是出于让读者能对整个规划领域有一个更为全局的了解或者使读者能更准确 的把握规划的具体含义以及规划研究的现实意义的目的而提及，因此，限于篇幅， 这部分介绍通常都会比较简略，如果读者对这部分介绍的内容感兴趣的话，可进 一步参考所引用的相关文献。 智能规划的研究具有广泛的应用背景。首先实际应用通常要求设计信息处理 第l 章绪论 工具，以提供经济和高效的资源规划。例如，在工厂作业调度规划问题中( j o b s h o ps c h e d u l i n g ) ，就是要考虑在有限的加工资源( 车床，刨床，钻床) 的情况下，根 据己知的工件的加工顺序要求对整个车间的生产作出安排，使得加工完所有工 件所需的时间尽可能的少每台机床的等待时间尽可能的短。这就使工厂在同样 设备条件下，由于作业调度规划合理而增加了生产能力，从而给工厂带来了可观 的经济效益。再比如考虑在有限辆的货运汽车的前提下，在不同的地点之间运送 货物的运输规划问题中，要求规划出一张车辆运转计划表，使得汽车尽可能地满 载运输，空车运行情况尽可能地少，车辆闲置的情况尽可能地少，这当然会给运 输公司带来可观的效益。其次，在复杂和动态任务中，需要设计出有效的规划工 具，以满足安全和效率上的需求。例如，在疏散规划问题中，要求制定有效的规 划以紧急疏散那些可能处于危险地带( 比如遇恐怖袭击、各种突发事件等) 的人 群，这类疏散规划的制定需要考虑危险源所在地点、有哪些可用资源、地理位置 如何、当时的天气状况、当时的政治氛围等多方面的因素，因此，有关当前状态 的所有信息几乎不可能得到。这就要求规划过程中必须能动态收集当时的信息， 并能在无法完全知道当前状态的情况下制定规划。第三，在复杂的人造装置中， 需要设计有效的规划工具，以集成更加自主和智能的机器装置。比如，在机器人 研究领域中的搬钢琴问题( p i a n om o v e r s p r o b l e m ) ，就是要求机器人能有效避开房 间之间的障碍物，自主地将一个曲尺形物体( 比如钢琴或沙发) 在无碰撞的情况 下从一个房间搬到另一个房间。正是由于智能规划技术具有如此广阔的应用前 景，吸引了一大批研究者致力于智能规划的研究，经过众多研究者的努力，现代 智能规划技术已经广泛应用于诸如智能工厂、机器人、物流自动调度、航空航天、 配置急诊手术等领域。 研究智能规划的另一个动机是更加理论性的。规划是理性行为的重要组成。 如果说人工智能的一个目的是从计算上认识和理解智能的各方面，那么作为关于 动作推理的规划是其中很关键的一个方面。智能规划是关于动作的推理，为了达 到预先确定的目标，通过预期动作的效果，选择和组织一组动作，是一种抽象且 清晰的推理过程。作为人工智能的一个领域，智能规划领域专门从计算上研究动 作推理过程。 第1 章绪论 1 2 2 智能规划与问题求解的区别 因为对输入和输出的要求不同，所以各种各样的规划问题之间有很大的区 别。研究规划问题的经典方法是从分析动作的效果入手，从一个初始状态出发， 试图通过推理得出实现目标状态的动作序列。因为在人工智能研究中一直起着重 要作用的搜索问题( s e a r c hp r o b l e m ) 也是试图获得从某个初始状态出发到达目标 状态的一系列状态转换步骤，所以搜索问题也是最早的智能规划问题。这种搜索 问题一般用在问题求解和定理机器证明中，所以g w e r n s t 和a n e w e l l 等人研 制的通用问题求解系统( g p s ，t h eg e n e r a lp r o b l e ms o l o v e r ) 被认为是世界上第一 个智能规划系统。 智能规划和问题求解的区别： 1 问题求解的主要研究成果主要体现在理论意义上，而智能规划主要面向 实际问题。 2 智能规划问题的操作的前提之间有很强的依赖与冲突关系，一个操作的 使用常常使另一个操作无法执行，甚至导致最终目标无法实现。因此，在智能规 划中一个重要的问题是如何解决操作间的冲突。 3 问题求解要求给出从初始状态到目标状态的操作序列；而规划问题并不 要求给出一个全序，能指出操作之间的半序关系也可以。 4 在实际规划中，操作的结果并不是完全确定的，因此需要考虑规划的监 视执行的问题。 1 9 6 0 年，著名人工智能大师j o h nm c c a r t h y 建议使用谓词演算去指导智能行 为中的推理，并由此提出了状态演算法( s i t u a t i o nc a l c u l u s ) ，第一个基于这种思想 建立起来的系统是g g r e e n 的问题解答系统q a 3 。 1 9 6 9 年，以著名人工智能专家n i l s s i o n 为首的斯坦福研究院人工智能研究组 提出了智能规划系统斯坦福研究院问题求解系统( s t r i p s ，s t a n f o r dr e s e a r c h i n s t i t u t ep r o b l e ms o l o v e r ) 。这是智能规划历史上具有重要意义的研究成果，它的 规划能力比以前所有规划系统的规划能力都强，s t r i p s 用在智能机器人s h a k e y 的动作规划中，s t r i p s 的知识表示方法及推理方法对它以后的规划系统具有深 刻的影响。 第l 章绪论 规划系统n o a h 参照了s t r i p s 的规划思想，但在最终形式上又有新的突 破。n o a h 系统从系统计划实现的目标出发，首先形成半序规划，然后把这些 半序规划组装在一起，要设法消去冲突的部分并适当增添实现某些规划的前提条 件，最终形成整个规划。 自八十年代后期以来，由于看到了智能规划在实际应用中具有良好的前景， 众多研究者投身到了相关研究中并提出了许多新的方法，如图规划方法 ( g r a p h p l a n ) 、基于命题可满足问题( s a t ) 的方法，基于记忆法、并行搜索法、 分级规划法，等等。其中图规划方法和基于命题可满足问题的方法在近年来有很 大突破，受到研究者的广泛关注，对智能规划的实用化也有重要的推动作用。 1 2 3 经典的智能规划方法 经典智能规划的主要思想是：对周围环境进行认识与分析，根据自己要实 现的目标，对若干可供选择的动作及所提供的资源限制施行推理，综合制定出实 现目标的规戈t j ( p l a n ) 。 智能规划研究的主要目的是建立起高效实用的智能规划系统。该系统的主要 功能可以描述为：给定问题的状态描述、对状态描述进行变换的一组操作、初始 状态和目标状态。智能规划系统能够给出从初始状态变到目标状态的一个操作序 列，其复杂性和所处的环境以及a g e n t 的功能有关。为了简化规划问题，传统的 规划一般都作出如下假设：( 1 ) 环境的状态的改变完全是由a g e n t 的动作的效果 造成的，排除了其他可能的影响和干扰；( 2 ) a g e n t 的动作的效果是完全确定的； ( 3 ) a g e n t 能够感知环境和它的动作的效果。人们把具有上述假设的规划问题 叫做经典规划问题。 1 2 3 1 半序规划以及规划的求精 n i l s s i o n 的著名规划系统s t r i p s 在人工智能规划历史上起着重要的作用。 在s t r i p s 系统中首先提出了用增加表和删除表描述环境和动作的方法，成功地 解决了智能规划中的最困难的问题一框架问题，而且该系统的效率很高。因此自 第1 章绪论 1 9 7 1 年产生以来，s t r i p s 系统在规划系统中一直占据统治地位。此后的研究工 作，大都在s t r i p s 的基础上加以改进，这其中最重要的一种方法就是半序规划。 这种规划借用了s t r i p s 的描述，但是不要求产生一个完整的操作序列，而是先 在操作之间生成半序描述，然后逐步加细求精，最后在操作的半序描述中抽出全 序的规划。 美国a r i z o n a 州立大学( a r i z o n as t a t eu n i v e r s i t y ) 工程和应用科学学院计 算机科学系的s u b b a r a ok a m b h a m p a t i 教授( h t t p ：r a k a p o s h i e a s a s u e d u r a o h u n l ) 在他所在的大学开设了人工智能中的规划和学习方法课程，并应邀在1 9 9 6 年a a a i 在俄勒岗州的波特兰市召开的会议上做教学报告。他对半序规划作了精 心的研究与总结，并且对半序规划给出其形式化描述，提出了逐步求精的思想， 把以前的半序规划统一在他的逐步求精思想中。以下的介绍就是使用了 k a m b h a m p a t i 的描述方法和思想。 半序规划的过程可以看作是对操作序列加上了一组约束，满足这些约束的动 作序列叫做候选规划。它是一个全序的操作序列，但是在半序上与约束的要求完 全一致，在数据结构课程中，也把这个过程叫做拓扑排序。 规划的过程可以看成是”排除”和”分裂”的过程。”排除”的过程就是增加约束， 排除掉那些不能成为解的候选规划。”分裂”的过程就是在规划中插入新的操作， 搜索那些满足条件的解。 操作的排序约束有两类，一类是先后关系约束( p r e c e d e n c ec o n s t r a i n t ) ，另 一类是邻近关系约束( c o n t i g u i t yc o n s t r a i n t ) 。先后关系约束要求一个操作在另 一个操作之前完成，而邻近关系约束要求一个操作必须直接在另一个操作之前。 此外，还有两类辅助约束，一类是间隔保持约束( i n t e r v a lp r e s e r v a t i o nc o n s t r a i n t s ， i p c ) ，另一类是真值点约束( p o i n t - t r u t hc o n s t r a i n t ) 。间隔保持约束要求在某一 期间某一条件p 总是成立的，而真值点约束要求在某一时间点上某一条件p 总是 成立的。 按约束要求给出操作序列的过程也叫做线性化，安全的线性化不但要满足对 操作的半序约束，而且要满足辅助约束。 例1 1 下面是半序规划的一个例子。 第l 章绪论 初始状态： a t b e d 目标： a to f f i c e 动作：i g e t - u p p r e c o n d i t i o n ： a tb e d a d dl i s t ：a tt a b l e d e l e l el i s t ：a tb e d 2 h a v e - f o o d p r e c o n d i t i o n ： a tt a b l e a d dl i s t ：h a d f o o d d e l e l el i s t ：a tt a b l e 3 g o - b y b u s hp r e c o n d i t i o n ： a th o m ea n dh a d - f o o d a d dl i s t ：a to f f i c e d e l e l el i s t ：a th o m ea n dh a d f o o d 4 g o - b y f o o t p r e c o n d i t i o n ： a th o m e a d dl i s t ： a t o f f i c e d e l e l el i s t ：a th o m e 半序规划增加了两个抽象的动作，一个是s t a r t ，另一个是f i n i s h ： s t a r t p r e c o n d i t i o n ： n u l l a d dl i s t ：t h ei n k i a ls t a t e d e l e t el i s t ：n u l l f i n i s h p r e c o n d i t i o n ：t h eg o a ls t a t e a d dl i s t ：n u l l d e l e t el i s t ：t h e g o a ls t a t e 初始规划仅由两个动作组成，一个是s t a r t ，另一个是f i n i s h 。其半序关系为s t a r t 在前，f i n i s h 在后，如下图所示： 图1 2初始的半序规划 1 0 第1 章绪论 在应用了动作s t a r t 后，半序规划继续考虑在s t a r t 和f i n i s h 之间插入其他动 作，因为g e t - u p 的a d d - l i s t 中有a tt a b l e 而a tt a b l e 是h a v e f o o d 的前提条件，所 以，可以把这两个动作插在初始规划中，让g e t - u p 在前，h a v e f o o d 在后。如图 1 3 所示。 图1 3在初始的半序规划中插入两个动作 图1 4在上述规划中再插入两个动作 半序规划实际上代表了一组动作序列，任何与上述半序规划的序相符合的全 序动作序列都是s t p s 系统的规划。 下面介绍半序规划的求精策略。 可以把半序规划的求精看成是一个过程或一个映射尺，尺把一个规划约束集 合p 映成为另一个规划约束集合，使$ e 4 p 的候选规划集是p 的候选规划集的 子集。如果p 。包含了p 的所有的解，则r 称作是完备的( c o m p l e t e ) 。如果p 的 候选规划集是p 的候选规划集的真子集，则r 称做是前进的( p r o g r e s s i v e ) 。如 果没有操作序列属于具有p 。的一个以上约束的候选规划集，则称尺具有系统性 ( s y s t e m a t i c ) 。完备性保证我们在求精的过程中不会丢失解，前进性保证我们在 求精的过程中会有效地剪掉不是解的候选规划，系统性保证我们在求精的过程中 只能对同一个候选解考虑一次。 求精策略可分为正向和反向两种。正向策略从初始状态出发，不断增加约束， 1 1 第1 章绪论 一直到目标状态得到满足为止；反向策略则从目标出发增加约束，直到动作的前 提条件都被问题的初始条件包含为止。因为反向策略产生的分支数比较少，所以 在规划系统中使用的比较多。 1 2 3 2 最小承诺策略 在规划的求精算法中一个大家热烈讨论的问题是规划过程中的最小承诺 ( l e a s tc o m m i t m e n t ) 问题。直观上说来，最小承诺就是在规划的求精过程中， 对规划个体所加的约束尽可能的少，以免过多的约束造成规划步骤间的不相容， 从而导致不必要的回溯。例如，如果在规划的求精过程中有两个可供选择的操作， 一个需要间隔保持约束，而另一个不需要，则我们应该选择后一种求精过程。再 比如，如果在两个供选择的操作中，一个是抽象的动作( 由若干具体简单动作抽 象得来) ，而另一个是具体的动作，则我们应该选择抽象的操作。 最小承诺与问题领域有很强的依赖性。一般说来，承诺相当于增加了约束， 这样容易识别半序规划是否包含解，但同时也增加了回溯的次数。因此，对于问 题的解比较少的问题领域，最小承诺比较有效，而对于解比较多的问题领域，效 果差一些。 1 2 3 3 基于逻辑的规划方法 逻辑规划系统是基于r o b i n s o n 的消解原理( r e f u t a t i o nr e s o l u t i o n ) 的，它 采用定理证明的方法，把求解规划的过程形式化为证明由初始状态和动作序列可 以证明目标状态的过程，其证明过程的解释就是一个规划解，也有人称这种方法 为基于变化( c h a n g e b a s e d ) 的规划，以命题逻辑、一阶谓词逻辑等规范逻辑和 各种非规范逻辑如默认推理( d e f a u l ti n f e r e n c e ) 、或然推理( p l a u s i b l ei n f e r e n c e ) 、 时序( 时态) 逻辑( t e m p o r a ll o g i c ) 、内涵逻辑( i n t e n s i o n a ll o g i c ) 、非单调逻 辑和模糊逻辑等为其理论基础。较为典型的系统是n e w e l l 、s h a w 和s i m o n 等在 1 9 5 6 年设计的逻辑理论家( l o g i ct h e o r i s t ) 程序和g r e e n 的q a 3 系统。但是基 于演绎的定理证明方法直接应用于规划问题求解有其固有先天性不足，它会产生 第l 章绪论 一些异常模型( a n o m a l o u sm o d e l s ) ：存在一些模型，它们满足定理，但是没有 相应的有效规划解存在。c h a p m a n 深入地研究了模型和规划解的对应关系，提出 了