（计算机软件与理论专业论文）基于软约束的多agent灵活规划研究.pdf

东北9 币范大学硕士学位论文 摘要 智能规划自提出至今已经有几十年的历史。在科学研究飞速发展的今天，研究者们 不断地探索智能规划新的应用领域和发展方向，不断提出新的规划求解算法以扩展智能 规划处理问题的范围。而原有的经典规划由于种种假设限制了规划的发展，如传统的规 划问题只支持强约束，求解规划的算法也有很强的条件限制，传统的求解方法已经不能 确切描述真实世界的情况，由此出现了灵活规划和多a g e n t 规划等。 多a g e n t 规划是经典智能规划的扩展。通常情况下，多个a g e n t 可以相互协调地进 行规划以达到目标，但是经典的多a g e n t 规划要求约束的满足性取值是布尔型，即约束 只有两种情况，或者满足，或者不满足，这对于描述和求解大多数实际问题都过于严格 以致无法求得规划解。本文以经典多a g e n t 规划和灵活规划为基础，提出了一类新的规 划一多a g e n t 灵活规划，并用具体的l o g i s t i c s 域的实例加以解释和说明，给出具体的求 解过程。文中对灵活服务，灵活服务请求，局部规划和全局规划做出了完整的定义。同 灵活规划类似，文中对多a g e n t 灵活规划中出现的命题引入了真值度的概念，动作的效 果引入了满意度的概念。最后提出了求解这类问题的新思路一用分布式灵活约束可满足 方法求解，它是分布式c s p 和灵活c s p 技术的融合。换句话说，对于一个给定的多a g e n t 灵活规划问题，如果在现有的约束条件下求解困难或无法求解时，可以使多个a g e n t 相 互协调地工作，并以一定的满意度求得规划解，即在规划长度和规划的满意度之间做出 折衷处理。 使用j a v a 语言在e c l i p s e 平台上实现了论文提出的m a f c s p 规划系统，并以 l o g i s t i c s 域中的实例为对象进行求解，测试结果表明论文提出的算法能够对多a g e n t 灵 活规划问题进行有效的求解。论文提出的规划思想对于物流运输、企业管理和博弈等， 均有具有较大的研究价值和可观的应用前景。 关键字：多a g e n t 规划；软约束；分布式灵活c s p ；多a g e n t 灵活规划 东北师范大学硕士学位论文 a b s t r a c t m u l t i - a g e n tp l a n n i n g i sa ne x t e n s i o no fc l a s s i c a la r t i f i c i a l i n t e l l i g e n c ep l a n n i n g u s u a l l ym u l t i p l ea g e n t sc a na c tt o g e t h e rt oa c h i e v ep l a n n i n gg o a l b u tc l a s s i c a lm u l t i a g e n t m e t h o d sr e q u i r et h a tt h ec o n s t r a i n t sa r ee i t h e rt o t a l l ys a t i s f i e do rt o t a l l yv i o l a t e d ，w h i c hi st o o r i g o r o u st of o r m u l a t ea n dt os o l v em o s to ft h er e a lp r o b l e m s i nt h i sp a p e r , w ed e f i n ea m u l t i a g e n tf l e x i b l ep l a n n i n gp r o b l e mw h i c hs u p p o r t ss o f tc o n s t r a i n t s ，a n dt h e nw ep r e s e n ta n e wt e c h n i q u ec a l l e dd i s t r i b u t e df l e x i b l ec o n s t r a i n ts a t i s f a c t i o n ( c s e ) ，w h i c hi st h e c o m b i n a t i o no ff l e x i b l ec s pa n dd i s t r i b u t e dc s p ，t od e a lw i t ht h i sp l a n n i n gp r o b l e m f o ra g i v e nm u l t i a g e n tf l e x i b l ep l a n n i n gp r o b l e m ，m u l t i p l ea g e n t sc a np l a nc o o p e r a t i v e l yw i t ha s a t i s f a c t i o nd e g r e ew h e ns o l v i n gt h ep r o b l e mi sd i f f i c u l to ri n f e a s i b l e ，a n dt h e nw ec a ng e ta p l a nw i t hat r a d e o f fb e t w e e np l a nq u a l i t ya n dl e n g t h m o r ea n dm o r er e s e a r c h e r sa r ei n t e r e s t e di n t h i sa r e ad u et oi t sv a l u a b l et h e o r yr e s e a r c h a n da p p l i c a t i o np e r s p e c t i v e s n e wa p p l i c a t i o na r e aa n dd e v e l o p i n gd i r e c t i o na r ee x p l o r e d ，f o r e x a m p l e ，h o wt oe x t e n di n t e l l i g e n tp l a n n i n gt oh a n d l et h es c o p eo fp l a n n i n gp r o b l e m s t h e c l a s s i c a lp l a n n i n gr e s t r i c t st h ed e v e l o p m e n to fp l a n n i n g s u c ha s ，t r a d i t i o n a lp l a n n i n go n l y c a ns u p p o r tr i g o r o u sc o n s t r a i n t s ，a n dh a sh a r da n di m p e r a t i v ec o n s t r a i n t s ，w h i c ha t ef u l l y s a t i s f i e do rf u l l yv i o l a t e d t h a ti sp r o v e dt ob et o or e s t r i c t i v e i fo n ec o n s t r a i n ti sn o tt o t a l l y t r u e ，i ti ss u p p o s e dt ob ev i o l a t e dt h ec o n s t r a i n t t h ec l a s s i c a lp l a nt e c h n i q u ec a n td e s c r i b e t h er e a ls i t u a t i o n ，s ot h ef l e x i b l ep l a n n i n ga n dm u l t i - a g e n tp l a n n i n ga p p e a r m u l t i a g e n tp l a n n i n gi sd e v e l o p e dw i t hm u l t i - - a g e n ts y s t e m ；i th a st h ec h a r a c t e r i s t i c so f a r t i f i c i a lp l a n n i n ga n dd i s t r i b u t e dp l a n n i n g m a n yr e a lw o r l da p p l i c a t i o n sc a nb ec l a s s i f i e d i n t om u l t i a g e n tp l a n n i n gp r o b l e m ，a n dh a v et h ea t t r i b u t e so ff l e x i b l ep l a n n i n gp r o b l e m s w e c a n ts o l v e m u l t i - a g e n tf l e x i b l ep l a n n i n gp r o b l e m sb yd y n a m i cf l e x i b l e c o n s t r a i n t s s a t i s f a c t o r ym e t h o do rm u l t i - a g e n tt e c h n i q u e ，b e c a u s et h e ya r es i m i l a rw i t hb o t hb u tn o t e x a c t l yi nt h es a m es i t u a t i o n w eo n l yp a ya t t e n t i o nt os u c hp r o b l e m si nt h i sp a p e r s o f t c o n s t r a i n t sa r ei n t r o d u c e di n t om u l t i - a g e n tp l a n n i n g ，a n dt r a n s f o r mi n t od i s t r i b u t e df l e x i b l e c s pt os o l v e m u l t i a g e n tp l a n n i n gh a sm a n ya p p l i c a t i o n s ，s u c ha sl o g i s t i c sa n dt r a n s p o r t ，b u s i n e s s m a n a g e m e n ta n dg a m e s 1 ti sv e r yi m p o r t a n tt or e s e a r c ho ni t k e y w o r d s ：m u l t i - - a g e n tp l a n n i n g ；s o f tc o n s t r a i n t s ；d i s t r i b u t e df l e x i b l ec s p ；m u l t i a g e n t f l e x i b l ep l a n n i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：至煎趄， 日期： 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：纽 日 期：瑚! 奎：多 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 静芡力 力蜀、f 、t 电话： 邮编： 东北师范大学硕士学位论文 1 1 课题研究背景 第一章引言 规划问题求解从最初的定理机器证明方法发展至i j s t r i p s 方法，之后又出现了非线性 规划方法【1 】，其中最典型的代表是1 9 9 5 年b l u m 和f u r s t 提出的基于规划图的快速规划方法 图规划【2 1 ，第一次采用了有向无循环图的方式来解决规划问题，在智能规划领域中 取得了质的飞跃。而规划问题的研究类型也从经典的规划问题逐步地扩展到数值规划、 时序规划、灵活图规划、多a g e n t 规划i ”j 及不确定规划等。从1 9 9 8 年开始，每两年举行 一次国际规划竞赛，到目前为止已经成功地举行了六届，智能规划的重要性可见一斑。 近年来，随着国内外学者的深入研究，智能规划的发展取得了前所未有的成就。在 不断寻找新的求解方法和提高规划求解效率的同时，人们又在考虑如何提高规划质量以 及扩展规划的应用范围。 图规划【5 6 l 方法可以成功地解决s t r i p s 域的规划问题，而现实生活中大多数的实际 问题是非常复杂的，可能会由于s t r i p s 算法不能获得真实世界问题的准确描述，导致 很多问题无法求解或者求得较低质量的解，另外规划问题具体多样性，想对所有的规划 问题使用统一的s t r i p s 方法来处理也是不现实的。比如，对于具有多个自治的、具一 定智能行为的a g e n t 构成的规划问题，对于这类问题无须分解，它本身具有分布性，同 时多个a g e n t 内部信息是私有的，而a g e n t 之间又需要相互协作才能完成任务。再如， 对于经典规划问题，有的约束要求过于严格，在这样的约束控制下无法获得有效的规划 解，但如果对约束进行适当的放松，就会得出具有一定满意度的规划解，即原问题的松 弛解。诸如上述的不同规划问题就不能用一种统一的方法求解，应针对不同的应用领域， 提出与其相适应的规划方法。本课题针对的是规划域中比较复杂的一类问题多 a g e n t 灵活规划问题展开研究。 1 2 主要工作及论文结构 多a g e n t 规划是随着多a g e n t 系统发展起来的，它同时具有智能规划和分布式系统的 特点。在现实生活中有很多实际问题都可以归结为多a g e n t 规划问题，同时又具有灵活 规划问题的属性。对于这类规划问题，不能单纯地使用动态灵活约束可满足方法或多 a g e n t 相关技术进行求解，因为它与两者相似但又不完全相同，本课题主要针对的就是 这一类规划问题，在多：a g e n t 规划中引入软约束，并将其转化为分御式灵活c s p 求解。到 目前为止，还没有解决这类问题的有效方法，文章的后续部分将给出求解多a g e n t 灵活 东北师范大学硕士学位论文 规划问题的求解方法一分布式灵活c s p 。 论文的主要工作表现在以下几个方面：本文通过将灵活性引入多a g e n t 规划域，定 义了支持软约束的多a g e n t 灵活规划。引入了灵活服务，灵活服务请求，局部规划和全 局规划了的概念，以经典多a g e n t 规划和灵活规划为基础，提出了一类新的规划一多 a g e n t 灵活规划，并用具体的l o g i s t i c s 域的实例加以解释和说明，给出具体的求解过程。 同灵活规划类似，对多a g e n t 灵活规划中出现的命题引入了真值度的概念，动作的效果 引入了满意度的概念。最后提出了求解这类问题的新思路一用分布式灵活约束可满足方 法求解。用到的主要技术是分布式c s p 和灵活c s p 。 使用j a v a 语言在e d i p s e 平台上实现了m a f c s p 规划系统，并以l o g i s t i c s 域中的 实例为对象进行求解，达到了预期效果，m a f c s p 可以求解多a g e n t 灵活规划。论文 提出的多a g e n t 灵活规划有很多重要应用，如物流运输、企业管理、博弈等，均有具有 较大的研究价值和可观的应用前景。 主要对多a g e n t 灵活规划进行了系统而深入的研究，主要内容安排如下： 第一章是引言，介绍了课题的研究背景及论文的主要工作和组织结构。 第二章对智能规划进行概述，介绍了智能规划的发展和研究历史，智能规划的基本 概念，常见的几种求解方法，重点介绍了图规划。 第三章主要介绍灵活规划的基本概念和相关术语，详细地介绍了灵活规划的两种求 解方法：灵活图规划( f g p ) 和灵活b l a c k b o x ( f b b ) 。 第四章详细描述多a g e n t 灵活规划，定义了一些基本概念，并举例说明多a g e n t 规 划的问题域，并模拟了求解过程，将多a g e n t 灵活规划实例转化为p d d l 形式，并用分 布式灵活c s p 求解。 第五章是主要是系统设计与实现，介绍了系统的开发环境，系统的功能设计，并列 举了实例及实验结果。 最后，第六章的结论部分对论文的工作进行总结，并对未来的研究提出几点期望。 2 东北师范大学硕士学位论文 第二章智能规划综述 2 1 智能规划的发展和研究历史 从2 0 世纪6 0 年代发展至今，智能规划已经无论在理论研究上，还是在实际应用中都 取得了很大的进步。如机器人、自然语言理解、知识推理等。1 9 5 7 年n e w e l l 和s i m o n 开 发了问题求解程序g p s ；1 9 6 9 年，g r e e n 通过归结定理证明的方法来进行规划求解，并且 设计了q 蚂系统【7 】，这一系统被大多数的智能规划研究人员认为是第一个规划系统；1 9 7 1 年f i k e 和n i l s o n 的s t r i p s 系统1 8 j 在智能规划中具有划时代的意义，1 9 9 5 年b l u m 和f u r s t 针 对经典s t r i p s 规划领域，在“f a s tp l a n n i n gt h r o u g hp l a n n i n gg r a p ha n a l y s i si na r t i f i c i a l i n t e l l i g e n c e 一文中提出了图规划，将规划的发展提升到一个新高度，在接下来的十几 年中，许多规划的研究工作都或多或少地应用了这一思想。 规划实质上就是为了达到某个特定的目标需要执行的一个动作序列。到目前为止， 有关智能规划的相关研究工作在问题的描述和求解两方面都已经取得了相当大的进步， 出现了大量的规划求解方法。如，1 9 9 2 年，k a u t z 提出将规划问题编码为约束可满足( c s p ) 问趔9 - 1 2 ，成为规划求解的关键技术之一：近年来由于s a t 求解器的速度得到了很大提 高，这类规划器得到了研究者们的重视，出现了基于s a t 求解的规划方法【1 3 】；以及基于 整数线性规划技术的求解方法等等。与此同时也涌现了很多现代规划器，如f f f l 4 , 1 5 j ，f a s t d o w n w a r d l l 6 1 ，a t p l a n 1 7 】和b l a c k b o x l l 8 1 ，o p t i p l a n l l 引，l p g l 刎，m a x p l a n l 2 1 i 和s g p l a n 【2 2 l 等。 2 2 智能规划相关概念 研究智能规划的最终目的是为了求解规划问题，因此需要引入规划，s t r i p s 规划以 及规划解的定义。 定义2 1 规划如果一个实体在初始状态下，通过执行一系列动作，如执行动作1 ，动作 2 ，动作n ，最后到达目标状态，那么这个动作序列动作1 ，动作2 ，动作n ，就 叫做一个规划。 定义2 2s t r i p s 规划1 1 9 】一个s t r i p s 规划问题是一个三元组r = ( s , g ，o ) ，其中， s 代表初始状态，是基原子的有穷集合，通常采用合耿公式的形式，表示规划问题 的初始阶段哪些基原子为真。比如基原子a 出现在状态s 中，而b 未出现在状态s 中，即 a s ，b 仨s ，n a 在状念s 为真，而b 为假。 g 代表目标条件，是摹原子的合取形式，表示规划问题的最后阶段期望为真的条件。 东北师范大学硕士学位论文 0 是规划操作的集合规划操作o o 是一个l 嘲( n a m e 。，p r e 。，d e l ，a d c l ) 。其中， n a m e 。是操作的名称。p r e 。是前提列表，是一组文字( 正原子或负原子) 的集合，表示一个 状态为了执行某个操作必须满足的前提条件。d e l 。是删除列表，是一组文字( 正原子或负 原子) 的集合，表示一个状态执行了此操作后将要删除的条件。a d d o 是添加列表，是一组 文字( 正原子或负原子) 的集合，表示一个状态执行了此操作后添加的条件。同初始状态 一样，p r c 。，d c l o 和a d d o 都以合取的形式出现。 动作( 有时也称为规划步) a = ( n a m e 。，p r e 。，d e l 。，a d d 。) 是规划操作o e0 的一个实例。如 果状态s 满足a 的前提条件p r e 。，则动作a 可应用于状态s ，结果状态定义为： r e s u l t ( s ，a ) = ( s d e l a ) ua d d a 。 定义2 3 规划解1 1 规划解是一个动作序y l j a ，a 。，对于一个给定的规划问题p ( s ，g o ) ，如果在状态s 执行动作序y u a l ，a k 后得到状态r ，即： r - - r e s u l t ( r e s u l t ( ( r e s u l t ( r e s u l t ( s ，a 1 ) ，a z ，) ，) ，a g - , ) ，a k ) ，且r 满足目标条件1 3 l 则称动作序列 a 1 ，a k 是规划问题p ( s ，1 3 lo ) 的一个规划解。 在s t r i p s 描述中，时间的表示非常简单，时间是由有限的时间步( 从。至l j n ) 构成的。 火箭问题就是一个使用s t r i p s 描述的最典型的规划问题【2 1 。该问题的目标是用火箭r 把 货物a 和b 从初始地点x 运送到目标地点y 如果火箭和货物在同一地点，则货物可以装载 到火箭上，也可以从火箭上卸载下来；如果火箭有油，则它可以移动，每次移动都会把 油全部消耗掉。 例1 1 火箭问题 初始状态 a t ax ，a tbx ，f u e lr ，a trx ) 目标条件 a t a y a tb y ) 操作 l o a d ，u n l o a d ，m o v e 操作具体定义如表2 1 所示： 表2 1 各个操作的定义 n a m ep r ed e la d d m o v e ( r ，x ，y )a t ( r ，均a t ( r ，x )a t ( r ，y ) l o a d ( r ，x ，c )a t ( r ，x ) ，a t ( c ，x ) a t ( c ，) ( )i n ( c ，r ) u n l o a d ( r ，x ，c )a t ( r ，x ) ，i n ( c ，r )i n ( c ，r )a t ( c ，x ) 一般情况下，规划的复杂性与所处的环境以及a g e n t 的功能有关。为了简化规划问 题，传统的规划总是基于如下三条假设： 1 初始世界状态是确定的； 2 a g e n t 可以感知世界的状态和它动作的效果，环境状态的改变完全是由a g e n t 动作效果造成的，排除了其他可能的影响和干扰； 3 a g e n t 动作的前提和效果是完全确定的并已知的。 通常把具有上述假设的规划i 、u j 题称为经典规划问题。近年来，随着人工智能的飞速 发展，有关智能规划也逐渐成为热点研究领域，人们不仅仅满足于经典的智能规划，逐 东北师范大学硕士学位论文 步向各种扩展的智能规划方向发展。 2 3 智能规划求解 从上个世纪9 0 年代以来的十几年时间里，经典智能规划的研究取得了突破性的进 展，较之以往的规划器而言，现代规划系统无论从求解速度，还是求解的效率和能力上 都有实质性的提高。 规划问题的求解方法有很岁矧，其中b l u m 和f u r s t 提出的图规划方法在智能规划 领域里具有划时代的意义。这里重点介绍图规划求解方法。 图规划1 2 4 l 中提出了一个新的求解方法，采用了有向无循环图( 即规划图) 的方式来 解决规划问题。规划图是一个由两种结点，三种边构成的有向分层无循环图，每层对应 一个确定的时间步，两种结点分别是命题结点和动作结点，三种边分别是前提条件边， 添加效果边和删除效果边。规划图分为命题层和动作层，且命题层和动作层交替出现， 命题层只包含命题结点，动作层只包括动作结点。第一层是命题层，由一系列表示初始 状态为真的那些命题结点构成。接着是第一个动作层，由以初始命题结点为前提的动作 结点构成。然后是第二个命题层，由第一个动作层中的动作结点添加或删除的命题结点 构成。以此类推，第三个命题层，第三个动作层直到第n 个命题层，即规划目标 出现，规划图构造完毕，开始进入解搜索( 即有效规划搜索阶段) 。 规划图结点的互斥关系主要包括动作互斥和命题互斥。 动作互斥【2 】：在规划图中一个给定的动作层存在的两个动作结点，如果没有一个有 效规划能够同时包含这两个动作，那么这两个动作互斥。例如，动作a 添加了命题p ， 则另个动作b 删除了命题p ，那么动作a 和动作b 互斥。 干扰：如果一个动作删除了另一个动作的前提条件或添加效果，则称这两个动作互 相干扰。 竞争需要：如果动作a 的前提和另一个动作b 的前提条件在前一层被标记为两两互 斥，则称这两个动作a 和b 具有竞争需要。 命题互斥【2 j ：在规划图中存在两个命题结点，如果没有一个有效规划可以使两个命 题结点同时为真，那么这两个命题互斥。例如，所有添加命题p 的动作和添加命题q 的 动作都互斥，则称p 和q 在某个命题层互斥。一个命题和它的否命题也互斥。 2 3 1 图规划求解 在搜索有效规划的过程中，准确地判断出命题或动作问的互斥关系对于搜索规划图 的有效子图有很积极的作用。在规划图扩张过程中，图规划会用一些简单的规则记录互 斥关系，尽管这些规则不能保证找到所有的互斥关系，但通常能找到大多数，以减少搜 索有效规划时的代价。 图规划的求解过程主要分为两个阶段：扩张规划图和搜索有效规划。 ( ) 扩张规划图 东北师范大学硕士学位论文 在规划图的第一层命题层包含规划问题的初始条件，根据第一层中的可用命题添加 第一层的动作命题，创建动作层时，具体操作如下：对于前提在前一命题层出现的操作， 且该操作的任意两个前提条件都不互斥，则它可以被实例化为动作，添加到第一层动作 层中。再按照动作互斥的定义为每个动作检查动作间的互斥关系。创建命题层的操作如 下：把前一动作层中动作结点的添加效果和删除效果命题添加到下一层命题层中，并分 别用添加效果边和删除效果边连接前一层的动作结点和本层的命题结点。以此类推，直 至规划的目标命题在某个命题层出现。 ( 二) 搜索有效规划 给定一个规划图，图规划使用后向搜索方式来搜索有效规划。不同于其他的规划器， 图规划使用分层的方法来充分利用互斥约束关系。如时间步t 给定一组规划目标，要在 第t 1 层找到以这组规划目标为添加效果的动作，而这些动作的前提条件命题在t - 1 时 间步就构成了次目标集，如果这些次目标可以在t - 1 时间步内为真，则原规划目标就可 以在t 个时间步内满足，但若次目标不能在t - 1 个时间步内为真，则图规划会继续选择 一组不同的动作集，继续查找有效规划或证明原规划目标不能在第t 时间步为真。 为了实现这一策略，图规划采用递归搜索方法。对第t 时间步的每一个目标，在第 t - 1 动作层中选择可以达到这个目标，但又不与己选择的任何动作互斥的某个动作，在 第t 时间步，继续递归地选择下一个目标。如果递归调用返回失败，则需要为当前目标 选择另外一个支持动作，以此类推，直到所有的动作都不能添加这样的目标命题后，返 回失败；一旦在第t 时间步所有的目标命题都已为真，被选中支持动作的前提又构成了 第t 1 时间步的新目标集，称为次目标集，图规划搜索过程继续进行，直到第一层命题 层的次目标集与初始条件的交集不为空，此时搜索有效规划过程结束。 例1 1 所示规划问题对应的规划图如图2 1 所示： a t a a ib a tr f u e l a b r a x bx rx e lr i l l o a d a a y n l o a d b 础b y 图2 1 【2 1 火箭问题对戍的规划图，其中实线表示前提条件边或添加效果边，虚线表示删除效果边， 黑色圆点表示n o o p 动作。 n o o p 动作是一个比较特殊的动作，由于它没有前提条件，可以将一个命题无条件 6 东北师范大学硕士学位论文 地传播到下一层，所以n o o p 动作在求解有效规划的时候有很大作用。 ( 三) 规划图的逆向解搜索 逆向搜索阶段可以看成是一个动态约束可满足问题( d c s p ) 。d c s p 是约束可满足 问题( c s p ) 的扩展。d c s p 由一系列变量，活跃变量，变量的活跃标志( 用于标记哪 些变量是活跃的，即有合法的赋值) ，变量的域，以及合法变量值组合的一系列约束构 成。在一个d c s p 中，初始时变量的一个子集是活跃的，目标是找到满足变量之间约束 条件的所有活跃变量的赋值。d c s p 还包含活跃约束，其形式为“如果变量x 取值为v x ， 则变量y , z ，w 将处于活跃状态”，由此可以看出，规划图和d c s p 之间具有某种对应关 系。规划图中不同层的命题对应于d c s p 的变量，支持命题的动作对应于d c s p 的值域， 动作间的干扰关系和d c s p 中的约束相对应。活跃约束与动作的前提条件密切相关，如 果选择一个动作a 支持活跃命题p ，则动作a 的前提条件命题在前一层也应该全部处于 活跃状态，即全部为真。初始条件下，只有对应于规划目标的那些命题处于活跃状态。 2 3 2 图规划的特点 图规划之所以如此成功，主要原因是它具有如下特点： ( 1 ) 图规划是充分并完备的； ( 2 ) 规划长度和动作数量最优； ( 3 ) 求解规划分为两个部分：一是构造规划图，二是搜索规划图，有效规划是规划 图的一个子图( 简称规划子图) ； 很容易将搜索规划子图的过程转化为约束满足问题( c s p ) 求解。 2 3 3 其他求解方法 在1 9 9 5 年b l u m 和f u r s t 提出的图规划算法基础上，又出现了几种基本的求解方法： ( 1 ) 将规划问题编码为s a t 问题，用s a t 的求解技术求解转化后的智能规划问题； ( 2 ) 将规划问题编码为状态空间搜索问题，包括前向状态空间搜索和后向状态空间 搜索，它是在2 0 0 0 年之后发展起来的，也是目前最为高效且流行的智能规划 的求解方法； ( 3 ) 将规划问题编码为约束可满足问题( c o n s t r a i n ts a t i s f a c t i o np r o b l e m ，简称 为c s p ) ，利用c s p 的求解技术求解智能规划问题，目前，c s p 已经有比较成熟 且很高效的商业软件如i l o g ( 4 ) 当给定的智能规划问题比较复杂，求解很困难时，可以考虑将复杂的任务分解 为若干个简单而易解的小问题，利用现有的算法对分解后的小问题求解，然后 再通过规划融合技术求出原问题的解。 7 东北师范大学硕士学位论文 第三章灵活规划 3 1 灵活规划与灵活规划问题 一般情况下，传统的规划问题通常被归类于一种强约束问题，即对于约束也是要么 满足、要么不满足。求解规划的算法也是有很强的条件限制，命题要么为真、要么为假； 动作或者执行、或者不执行；这对于现实世界的问题来说要求过于严格。于是产生了灵 活规划，灵活规划支持软约束，可以找到一个折衷的规划解。目前，在国际上灵活规划 方面做得比较出色的有l a nm i g u e l ，j a r v i s 和q i a n gs h e n 。他们主要是应用g r a p h p l a n 框 架或结合c s p 来解决灵活规划问题。 1 9 9 7 年的第四届欧洲规划会议上，s u b b a r a ok a m b h a m p a t i 在“u n d e r s t a n d i n ga n d e x t e n d i n gg r a p h p l a n 一文中首次提出了图规划的解搜索过程相当于求解一个动态约束 可满足问题( a d c s p ) ，其中规划图中的命题相当于d c s p 中的变量；支持命题的动作相 当于命题的值域；目标中的命题相当于初始活跃变量；规划图中存在动作冲突约束、命 题约束、子目标激活约束三种约束。由于经典的c s p 中的强约束，很多现实生活中的 问题都无法用c s p 形式地描述出来。于是出现了c s p 的扩展版本：d c s p l 2 4 1 和f u z z y c s p l 2 5 1 ，但它们对c s p 的改进都是不完备的。2 0 0 1 年，l a nm i g u e l ，q i a n gs h e n 等结合了 f u z z yc s p 和d c s p 的优点提出了动态灵活c s p 技术1 2 刚，该技术时常用于求解带有软约 束的灵活规划问题。利用动态灵活c s p 求解灵活规划规划器有l 锄m i g u e l ，p e t e rj a r v i s 和q i a n gs h e n 开发的f g p ( f l e x i b l eg r a p h p l a n ) 和l f g p ( l e x i m i n ) ，它们都是比较成功 的。初步的实验结果表明，灵活规划问题在解决很多经典规划问题上要优于g r a p h p l a n 和s t a n 等经典规划器。同时它还能解决很多经典规划器所不能解决的问题。 由于c s p 技术发展成熟，而求解问题的效率很高，把规划问题转化为c s p 求解1 2 1 已是大势所趋。另一个原因是将规划问题编码为c s p 问题比较容易，它们之间存在着 某种对应关系。但由于c s p 的约束是强约束，很多真实世界问题无法用它描述和求解， 于是在此基础上又出现了d c s p 和f u z z yc s p ；1 9 9 7 年的第四届欧洲规划会议上， s u b b a r a ok a m b h a m p a t i 在“u n d e r s t a n d i n ga n de x t e n d i n gg r a p h p l a n 一文中首次提出了图 规划【2 8 l 的解搜索过程相当于求解一个动态约束可满足问题( a d c s p ) ，其中规划图中的命 题相当于d c s p 中的变量；支持命题的动作相当于命题的值域；目标中的命题相当于初 始活跃变量：规划图中存在动作冲突约束、命题约束、子目标激活约束三种约束。2 0 0 0 年l a nm i g u e l 和q i a n gs h e n 等人在第四届欧洲人工智能会议上发表的f l e x i b l eg r a p h p l a n 第一次将灵活的思想用于图规划中：2 0 0 1 年在人工智能工程应用上又发表了e f f i c i e n t f l e x i b l ep l a n n i n gv i ad y n a m i cf l e x i b l ec o n s t a i n ts a t i s f a c t i o n ，提出用动态灵活约束满足技 r 东北师范大学硕士学位论文 术求解灵活规划；2 0 0 2 年又发表了f l e x i b l ep l a n n i n gb yl e x i m i nf u z z yc o n s t r a i n t s a t i s f a c t i o n ；由于单纯的d c s p 和f u z z yc s p 对c s p 的改进都是不完备的，l a nm i g u e l 和q i a n gs h e n 等人于2 0 0 3 年在( ( a r t i f i c i a li n t e l l i g e n c e ) ) 上发表了f u z z yr r d f c s pa n d p l a n n i n g 一文，结合f u z z yc s p 和d c s p 二者的优点求解带有软约束的灵活规划问题。 目前利用动态灵活c s p 求解灵活规划规划器有i a i lm i g u e l ，p e t e rj a r v i s 和q i a n gs h e n 开 发的f g p ( f l e x i b l eg r a p h p l a n ) 和l f g p ( l e x i m i n ) ，它们都是比较成功的。 3 1 1 基本概念 一个灵活规划问趔2 9 j 形式化定义为一个四元组q j = f ，0 ，i ，分别表示规划对 象的集合，灵活操作集合，由灵活命题构成的初始条件集合，以及灵活目标条件。原始 规划中的布尔命题被灵活命题代替，灵活命题的形式为p ( p 巾1 ，由2 ，巾ik i ) ，其中巾i f ， k 表示灵活命题的主观真值度，是一个完全有序的集合，由k 上，k l ，k t 组成，k i 是k 中的一个元素，表示命题的主观真值度。布尔命题的真值度用k 的两个端点k 上和k t 刻画， 分别表示命题完全为真和完全为假。当处理真值度为k 上和k 的灵活命题时，分别采用布 尔类型形式一、( p 巾1 ，巾2 ，由j ) 和( p 巾1 ，巾2 ，巾j ) 。灵活操作用模糊关系r 描述，r 由一 个成员函数| lr ( ) ：l x 2 x i k 定义，其中i 2 x j 是在当前命题 列可用的子集的笛卡尔积。灵活操作0 0 表示它的前提条件被满足的程度。灵活操作 由从前提空间到一个全序的满意度范围脚一组灵活效果命题的映射这一模糊关系来描 述。l 由有限的满意度l j - ，l l ，1 2 ，l t 组成，其中l j - 和l t 分别表示完全不满足和完全满足，完 全不满足的动作由于其前提不成立，所以不能添加到规划图中来。n o o p 动作比较特殊， 它的满意度是l t 由此可以看出，灵活规划克服了经典规划问题强约束的缺点，在图规划框架的基础 上加入了处理松弛软约束和综合分析受损的规划结果的能力，对满意度和规划长度进行 折衷处理，从而更加灵活地解决现实世界中的规划问题。 3 1 2 灵活图规划( f g p ) 上一节已经介绍了灵活命题的定义，在灵活图规划中，命题之间也同样存在互斥关 系。如果两个灵活命题，它们所表达的核心命题一致，但却有着不同的真值度，那么这 两个命题互斥，如命题a tpl 1 1 ( 表示货物p 在l 地的真值度为1 1 ) 和a tpl1 2 ( 表示货物 p 在l 地的真值度为1 2 ) 互斥。如果两个灵活命题的支持动作两两互斥，则这两个命题互 斥，与图规划中的定义一致。动作结点之间的互斥约束是指没有一个有效规划可以同时 包含这两个动作，那么这两个动作互斥，当发生以下某种情况时，两个灵活动作互斥： ( 1 ) 不一致效果：两个动作产生的效果互斥。( 2 ) 干扰：一个动作的效果命题的真值 度与另一个动作的前提条件命题的真值度不同。( 3 ) 竞争需要：两个动作具有互斥的前 提条件。初始条件在灵活规划图的第层，前提条件在前一命题层为真，且都不互斥的 灵活操作可以实例化为动作，添加到下一动作层中，满意度也随之添加。n o o p 动作的 9 东北师范大学硕士学位论文 使用与图规划中相同。灵活图规划的解提取过程可以看成是动态灵活约束可满足问题 ( d f c s p s ) 来求解。 3 1 3 灵活b l a c k b o x ( f b b ) 与f g p 使用d f c s p ( 动态灵活约束可满足问题) 提取规划相比，f b b 对b l a c k b o x 框架 做了简单的修改以求解灵活规划问题，并调用标准的s a t 求解器提取规划。对于一个给 定的规划问题，f b b 可以求出多个具有不同满意度的规划解，即在规划长度和规划满意 度之间做折衷处理，这一点和f g p 相似。用f b b 求解灵活规划问题有几个主要的步骤。 1 用图规划的方法将规划问题转化为规划图结构，如果规划解存在，则转向步骤2 。 2 将规划图转化为c n f 范式，以此作为s a t 求解器的输入。 3 如果s a t 求解器找到了个模型，则该模型就对应一个有效规划，如果未求出有效模 型，则转向步骤1 继续求解。相应地，灵活规划图扩张和解提取过程也要做适当的修改。 f b b 是灵活规划问题的另一种新的求解方法，它和f g p 构成了灵活规划求解的两 个主要方向。一是在s t a n 和i p p 上发展起来的有效规划图方法，在用灵活规划方法求 解时可以减轻构建和维持较大规划图时的负担。二是可以将f b b 和f g p 两种求解方法 做比较，作为求解灵活规划时的实验依据。 3 2 灵活规划实例 以一个l o g i s t i c s 域问题为例，如图1 所示。有两个包裹p