（计算机应用技术专业论文）带有抢占式动作规划的研究与实现.pdf

摘要 通过对规划问题研究，定义了一种新的动作- 抢占式动作。对抢占式动作的研 究包括了敌意规划和时态规划两方面，并且实现了系统凡心。带有抢占式动作的敌 意规划研究提出了新的应对模式，克服了现有应对模式需要依赖规划识别结果和反应 速度慢的缺点。这种应对模式是通过实时抢占算法和准确抢占算法实现的。在实时抢 占算法中，一旦执行危险动作，则判定为敌意，执行抢占式动作阻止其规划继续执行。 准确抢占算法首先对危险动作的相关资源分析，希望执行更为有效的抢占式动作，阻 止其规划执行。敌意规划研究中，资源是核心内容，通过对资源的研究提出了进程信 号量规划算法，它是将操作系统中进程管理方法引入规划领域，以不同以往的角度进 行规划。进程管理技术十分成熟，将其应用于规划领域，可以促进规划的发展。这种 方法重新定义了同步和互斥，同步决定了动作进程执行的先后顺序；互斥决定哪些动 作进程不能同时执行。为使进程信号量算法能够处理条件效果，提出了条件效果的结 构化扩展，将条件效果扩展为条件效果树。规划无法正常执行时如何实现规划目标是 带有抢占式动作时态规划研究的主要内容，提出了己知抢占式处理算法和未知抢占式 处理算法，分别处理抢占式动作已知和未知两种情况。时态规划中还提出了倒桥定理， 倒桥定理是求解规划的转化方法，给出了定理证明。通过对带有抢占式动作规划的理 论研究，开发了系统心，虬心实现了敌意规划中可执行抢占式动作的确定，以及 时态规划中对抢占式动作的处理。用实例对其加以测试，结果表明，该系统达到了预 期效果。 关键词：抢占式动作；实时抢占算法；准确抢占算法；抢占式处理算法；进程信 号量规划算法；倒桥定理 a b s t r a c t i nt h i sw o r k ，w ed e f i n ean e wa c t i o nn a m e dr o b a c t i o n w er e s e a r c h r o b a c t i o nf r o mt w oa s p e c t s ，n a m e l ya d v e r s a r i a lp l a n n i n g a n dt e m p o r a l p l a n n i n g w ea l s oc o m p l e t eas y s t e mn a m e d r a p w ep r o p o s ean e wp a t t e r nf o r r e s p o n d i n gt oa d v e r s a r i a lp l a n n i n g i td o s en o tn e e dp l a n n i n gr e c o g n i t i o n ，a n d i sf a s t e rt h a nt h ee x i s t i n gp a t t e r n r e a lt i m er o b b i n ga l g o r i t h ma n dr i g h t r o b b i n ga l g o r i t h m a r ep r o p o s e dt oe x p l a i nt h i sn e wp a t t e r n i fi te x e c u t e s d a n g e ra c t i o n ，i tw i l lb e a d v e r s a r i a li nr e a lt i m er o b b i n ga l g o r i t h m a n d r o b a c t i o ne x e c u t e st os t o pi tg o i n go n f o rr i g h tr o b b i n ga l g o r i t h m ，r e s p o n di s e x a c t b e c a u s er i g h tr o b b i n ga l g o r i t h md e a l sw i t ht h er e s o u r c e so fd a n g e r a c t i o n b yr e s e a r c ho nr e s o u r c e ，an e wa l g o r i t h m i s p r o p o s e d ，n a m e dp r o c e s s s e m a p h o r ep l a n n i n ga l g o r i t h m i tm a k e su s eo fp r o c e s sm a n a g e m e n ti nu s t e c h n i q u e o fp r o c e s sh a sb e e nm a t u r e i fi ti su s e di np l a n n i n g , i tw i l lp r o m o t ed e v e l o p m e n to f p l a n n i n g e x c l u s i o na n ds y n c h r o n i z a t i o n a r er e d e f i n e di nt h i sw o r k s y n c h r o n i z a t i o n d e t e r m i n a t e sw h i c ha c t i o n p r o c e s ss h o u l de x e c u t eb e f o r ea n o t h e r e x c l u s i o nd e t e r m i n a t e s w h i c ha c t i o n p r o c e s sc o u l dn o te x e c u t ew i t ha n o t h e rt o g e t h e r t od e a 1w i t hp l a n n i n g p r o b l e mw i t hc o n d i t i o n a le f f e c t ，a c t i o n sw i t hc o n d i t i o n a le f f e c ts h o u l db ee x t e n d e dt oa c o n d i t i o n a le f f e c tt r e e i fp l a n n i n gc a nn o te x e c u t e ，h o wt og e tt h eg o a li st h em a i n w o r ki n t e m p o r a l p l a n n i n gw i t h r o b a c t i o n k n o w nr o b b i n gm a n a g e m e n t a l g o r i t h ma n du n k n o w nr o b b i n gm a n a g e m e n ta l g o r i t h ma r ep r o p o s e d r e v e r s e b r i d g et h e o r e mi sp r o p o s e di nt e m p o r a lp l a n n i n g ri sa t r a n s f o r mm e t h o do fp l a n n i n g ，a n d i ti sd e m o n s t r a t e di nt h i sw o r k r a pc a nd e c i d ew h i c hr o b a c t i o n s h o u l de x e c u t ei n a d v e r s a r i a lp l a n n i n g ，a n dd e a l sw i t hr o b a c t i o nt om a k es u r et h ep l a n n i n gg o a li nt e m p o r a l p l a n n i n g b yt h ee x p e r i m e n t ，r a pf i t sw i t ht h et h e o r e t i c a lr e s e a r c h k e yw o r d s ：r o b a c t i o n ；r e a lt i m er o b b i n ga l g o r i t h m ；r i g h tr o b b i n ga l g o r i t h m ； r o b b i n gm a n a g e m e n ta l g o r i t h m ；p r o c e s ss e m a p h o r ep l a n n i n ga l g o r i t h m ；r e v e r s e b r i d g et h e o r e m 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 学位论文作者签名： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：i 銎! 土兰 日 期：赵翌呈王：弓 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 矽凳2 伽c ；rj 一 电话： 邮编： 东北师范大学硕士学位论文 引言 带有抢占式动作规划的研究包括了时态规划及敌意规划两方面，并且开发了系统 r a p 。抢占式动作在敌意规划中的应用，提出了新的应对模式，通过危险动作确认对 方执行规划为敌意规划，再由资源的分析，执行适当的抢占式动作，终止规划的执行。 这种模式有别于以往“识别对手规划产生应对规划 的模式，不依赖规划的识别 结果且应对更为迅速。具体提出了实时抢占算法和准确抢占算法，区别在于是否对危 险动作的相关资源处理。实时抢占算法不分析危险动作的相关资源，响应速度更快； 准确抢占算法对危险动作相关资源处理，针对性更强。 规划无法正常执行时如何实现规划目标是带有抢占式动作时态规划的研究内容， 它维护了规划的执行质量。具体提出了已知抢占式处理算法和未知抢占式处理算法， 已知抢占式处理算法又分为预期抢占式处理算法和异常抢占式处理算法。这些算法针 对不同的抢占式动作进行处理。 r a p 是根据带有抢占式动作规划研究所开发的系统，它实现了实时抢占算法、 已知抢占式处理算法和未知抢占式处理算法。敌意规划中，r a p 可以模拟对方规划 的执行，通过危险动作判定其是否为敌意规划，确定可执行的抢占式动作。时态规划 中，根据不同的抢占式动作，调用不同的处理程序，最终形成规划的初始条件集合。 通过实验验证，r a p 达到了带有抢占式动作规划研究的目标。 “资源”是带有抢占式动作敌意规划研究的核心内容，通过对资源研究提出了进 程信号量规划算法，这是一种不同于以往的规划方法。进程信号量规划算法首先分析 了现有的互斥关系，提出了相关干扰的概念，一定程度上解决了现有互斥关系影响规 划解并行性的缺陷。进程信号量规划算法基础在于进程和规划操作的共同特征同 步与互斥。算法包括两部分，第一部分预处理；第二部分算法的主体。预处理根据规 划问题特点给出可确定执行先后的动作的优先级。主体部分通过动作进程间同步、互 斥关系，获得规划解。为了使进程信号量算法可以处理条件效果，提出了条件效果的 结构化扩展。 时态规划研究中提出了倒桥定理，是求解满足约束极小值的充分必要条件，同时 给出了定理证明。倒桥定理是一种求解规划的转化方法。首先将时态规划问题转化为 非线性规划，再由倒桥定理求解。 东北师范大学硕士学位论文 第一章智能规划概述及扩展鞍点条件 1 1 智能规划概述 近代智能规划以图规划为基础，呈多元化发展，以时间和状态为纬度可分为三大 类n 3 。1 ) 离散时间，离散状态。包括系统搜索、启发式方法、局部搜索、转化方法。 系统搜索以整个状态空间为作用范围，是完备的规划方法。系统搜索首先将搜索空间 分解为多个子空间，每个子空间搜索完毕后，对子空间规划解进行评估。系统搜索方 法有g e n e r i c ! * 、u c p o p 晗3 、s t a n 3 、p r o p p l a n 、s y s t e mr 等。启发式方法利用搜 索树求解规划，根据定义的启发式函数决定搜索方向。这类方法无法处理全局约束， 并且过于依赖启发式函数，往往是不完备的。主要包括h s p h 。、h s p r 悔。、f f 砸。、a l t a l t 、 g r t 、m o g r t 盯1 等。局部搜索主要有a s p e n 。转化方法是将规划问题转化为约束 极值问题或可满足问题，再利用这两类问题已有的求解器求解。这类方法主要有 s a t 时1 0 1 、g p c s p n 卜1 3 3 。2 ) 离散时间，混合状态。主要包括系统搜索、启发式方法、 转化方法。系统搜索包括s p i e 2 、o p l a n 2 等。启发式搜索主要包括m e t r i c f f 、g r t 4 1 5 。 转化方法有l p s a t 。3 ) 连续时间，混合状态。主要包括系统搜索、启发式方法、局 部搜索。系统搜索包括s h o p 2 、t a l p a n n e r 、z e n o 等。启发式搜索主要包括m i p s 、 s a p a 、e u r o p a 。局部搜索主要有l p g n 6 1 。以时间和状态为纬度所介绍的规划器有一个 共同特点，都没有进行约束分解。由陈一昕等人实现的规划器s g p i a n u7 1 ，则采用了 约束分解的方法。 针对图规划，提出许多扩展方法。p a r a g r a p h n 印将图规划扩展到概率领域，它通过 目标回退算法求解最优可能规划解，并且使用了规划的合成与分解钔技术。以粗糙集 理论为基础的规划算法一粗规划脚3 ，允许初始条件集合不确定。p e g g 幢是图规划 的变种，利用定的存储空间，将深度优先算法转变为迭代式状态空间算法，它的速 度是使用c s p 力n 速器的图规划的2 至1 j 9 0 倍。条件效果方面，随着图规划研究的不断加 深，可以处理对象可变的条件效果暖羽。 经典规划常常忽略动作执行期间所发生的改变，也不考虑动作执行的持续时间， 这与现实问题并不符合，于是出现了“时态规划 。时态规划中动作不再是一个点执 行过程，前提、效果根据不同时态规划问题可以定义在动作执行过程中不同的时间段。 大体分为三种：开始( s t a r t ) 、结束( e n d ) 及整个持续时间( o v e r a l l ) 。动作执行的持 续时间根据不同的语言模型及规划问题也有所不同。时态规划是智能规划领域中比较 难的一个分支，也是一个不断发展的分支。但是，一些研究人员发现，现有的时态规 2 东北师范大学硕士学位论文 划器并不是“真正的时念规划器 池。纠1 。 时态规划研究主要分为两个方面心驯：扩展状态空间及约束方法。扩展状态空间又 可以细分为几个方面：规划空间，主要包括有s p e n b e r t h y 和d w e l d 实现的z e n o ， h l s y o u n e s 和r g s i m m o n s 实现的v h p o p ：扩展规划图，包括d e s m i t h 和d w e l d 实 现t g p ，a g e r e v i n i 和i s e r i n a 实现的l p g ；转化为线性规划，包括d l o n g 幂d m f o x 实 现的l p g p ；回退方法，包括s a p a ( m b d oa n ds k a m b h a m p a t i ) 、t p 4 ( p h a s l u ma n d h g e f f n e r ) 、t a l p i a n ( j k v a r n s t r 6 m ，p d o h e r t y ，a n dp h a s l u m ) 、t l p l a n ( f b a c c h u s a n dm a d y ) 、s g p i a n 。 此外，智能规划的研究范围不断扩大，增添了许多新的研究内容，如非确定性规 划1 ，灵活规划，误导动作研究阱1 ，规划识别汹1 。随着研究不断深入，智能规划 不再局限于理论研究，逐渐应用于实际问题啪驯。 1 2 互斥关系 本节主要介绍图规划中的互斥关系。图规划的互斥关系分为两种，动作互斥和命 题互斥，动作互斥又可分为干扰和竞争需要。 对于同一命题层的两命题p 和q ，若所有支持命题q 的动作和所有支持命题p 的 动作都互斥，那么p 和q 互斥口。如动作a 和b 支持命题p ，动作c 支持命题q ，a 和c 互斥，b 和c 也互斥，那么p 和q 互斥。 ，- 7 a 互斥 互斥b 、 c a p - j 7 b 互斥 。 ；互斥 图1 - 1 命题互斥 y m 互斥 文 a 互芹 b - - - 么2 n 二 蕾c 图1 - 2 动作的干扰且斥 图1 - 3 动作的竞争需要互斥 3 1 1 1 p 。q n p q 东北师范大学硕士学位论文 同一动作层的动作被标记为互斥。1 ，包括两种情况： 干扰。若动作删除了其他动作的前提或是添加效果，则这两个动作被标记为 互斥。 竞争需要。如果两动作的某一前提被标记为互斥，则动作标记为互斥。 动作b 删除了动作c 的添加效果q ，则动作b 、c 标记为互斥。 动作a 的前提m 和动作c 的前提n 被标记为互斥，则动作a 和c 被标记为互斥。 1 3 条件效果已有扩展方法 条件效果允许动作存在与内容相依赖的效果。条件效果用w h e n 子句来表示。主 要有三种扩展方法b 铂：全扩展，要素扩展以及i p p 方法。 例a c t i o na ：p r e c h ：e f f e c t p ：e f f e c t ( w h e n an ) ：e f f e c t ( w h e n m z g ) ：e f f e c t ( w h e nqe 一，) 动作a 是带有条件效果的动作。h 为动作的前提。a 包括四个效果语句，一个 普通效果p 和三个条件效果子句。第一个w h e n 子句表示条件效果前提为a ，效果为n ； 第二个子句前提为m ，效果为z g ；第三个子句前提q ，效果e 一厂，其中，r 表示 删除效果。 全扩展将动作的前提和条件效果前提的组合进行合并。因为对条件效果的前提进 行组合，所以存在组合爆炸问题。 要素扩展将动作效果组件化，每一个效果产生一个组件。组件的前提由动作的前 提和条件效果前提共同组成，条件效果的效果作为组件的效果。组件是新的处理单元， 也就是说整个算法针对的是组件而非动作，这使得互斥关系极其复杂，增加了整个处 理过程的难度，更可能使规划解丢失。 i p p 方法将带有条件效果的动作不做任何处理，直接嵌入到规划图中。i p p 方法 中，只有当动作的前提或效果互斥时，动作才被标记为互斥，并没有对条件效果产生 的互斥进行处理，所以解搜索速度缓慢。 处理条件效果的规划算法也在不断发展。通过在规划解搜索中判断是否需要条件 冲突检测，可以加快有效规划的搜索，提高了系统的效率1 ；利用前向搜索方法求解 规划解时，选择独立集而非单个动作，可以明显地减小搜索空间1 。 4 东北师范大学硕士学位论文 1 4 扩展鞍点条件 陈一昕等以k k t 、s p 为基础提出扩展鞍点条件( e s p c ) n 3 5 1 ，以此为理论基础 实现的规划器s g p i a n 在规划器大赛中取得了优异的成绩。 e s p c 不要求约束函数可微，但连续型e s p c 要求约束函数符合约束合格条件， 倒桥定理则不需要这个条件，本文分别从连续型桥型定理证明和k k t 条件的拉格朗 日惩罚函数两个方面说明。在 c o n s t r a i n tp a r t i t i o ni np e n a l t yf o r m u l a t i o n sf o rs o l v i n g t e m p o r a lp l a n n i n gp r o b l e m ) ) 给出了e s p c 的证明，连续型e s p c 证明存在问题，混合 型e s p c 证明更是错误的。 1 4 1k k t 条件 连续型非线性规划( c n l p l ) ： ( p c ) ：m i n 厂( x )x = ( ，石2 ，x v ) ze r 9 j 且应满足： j l o ) 一仇o ) ，h ：o ) ，o ) ) r ；0 g o ) 一( g l o ) ，9 2 0 ) ，g ，( x ) ) rs 0 ( 描j 丕1 ) 其中x 为连续型变量，厂( ) 连续、可微。 定义1 1 连续型满足约束极小值点( c m c ) 如果x 奉满足约束，并且在x 的 连续型邻域中，所有满足约束的x ，都有厂o 奉) sf ( x ) ，那么x 宰就是p c 的c m c 。 c n l p l 目的就是找到c m c 。 k k t 的惩罚函数n 1 为拉格朗日( l a g r a n g e ) 惩罚函数。设拉格朗同算子为 al ( 九，九，九) re r ”和。( 。，j 1 2 ，以) r 尺，函数如下： l ( x ，a ，肛) ly ( x ) + a r h ( x ) + ! z r g ( x ) ( 1 1 ) 要求j l l ( ) 和g ( ) 可微。 若x 为正则点n 1 ，则它的等式约束和有效不等式约束的梯度是线性无关的。即等 式约束梯度型，o h 2 ( x ) ，塑也和有效不等式约束梯度塑擎翌，塑垂生， 赴魂魄 o x卿 型是线性无关的，其中，a i a ( x ) 。a ( x ) 为有效不等式约束序号集合，a ( x ) - - iig i ( x ) = o ) 。 定理1 1k k t 条件h 嘲若x 木是p c 的c m c ，并且为正则点，那么存在唯一的 5 东北师范大学硕士学位论文 a 木e r m 和木e r r ，使丝堑掣；0 ，其中，口f ；0 ，v j 喏a ( x 掌) ： fi o 宰) ：o ) ； o z 否则u ； 0 。 应用k k t 条件对c n l p i 求解： f ( x ，a ，) = a f ( x ) + x r o h ( x ) + “ra g ( x ) 缸a x 。 缸 h ( x ) p r g ( x ) ；0( 1 2 ) 根据肛的设定及( 1 2 ) 即可求得石乖、a 和肛宰。将这种方法求出的点称为k k t 点，由于k k t 只是必要条件，所以并不是所有k k t 点都是满足约束极小值点。 1 4 2 鞍点条件( s p ) 连续型非线性规划( c n l p 2 ) ： ( p c ) ：r a i nf ( x ) x 一瓴，屯，) r 尺” 且应满足：h ( x ) = ( j l l o ) ，h ：o ) ，吒仁) ) r ；0 g ( x ) = ( 9 1 0 ) ，g ：o ) ，g ， ) ) r 苫0 ( 描述2 ) x 为连续型变量。 鞍点条件的拉格朗日惩罚函数，算子为 a = ( ，九，九) 7 e r ”和 一( p l , 肛2 ，以) re r ，函数如下： l ( x ，a ，) 一，( z ) 一九r h ( x ) 一r g ( x ) ( 1 3 ) 。 定理1 2 鞍点条件溉鞠1 对于连续可微的约束函数，x 宰是p c 的c m c ，如果存在 唯一的a , e r ”和p , e r 7 ，其中，半芑0 ，对于一切x r 9 ，a g r ”，及p e r 7 有 l ( x 木，a ，肛) n l ( x * ，a 木，肛唪) sl ( x ，a 木，拳) ( 1 4 ) 。 s p 只是充分条件，因为不一定存在a ，一c 和孝使( 1 4 ) 成立。 1 4 3 连续型e s p c 连续型e s p c 是解决描述1 型非线性规划的充分必要条件。 6 东北师范大学硕士学位论文 建立e s p c 的惩罚函数。设惩罚函数的算子为ae r ”和尺7 ，函数如下： l ( x ，口，卢) 一( x ) + 口ri h ( x ) i + 卢rm a x ( 0 ，g ( x ) ) ( 1 5 ) 其 中 ， m a x ( 0 ，g ( z ) ) = ( m a x ( 0 ，g ，( 工) ) ，m a x ( 0 ，9 2o ) ) ，r n a x ( 0 ，g ，( 石) ) ) ， ih ( x ) i - = ( ih d x ) l ，ih ：o ) l ，lk o ) 1 ) ，i 1 和m a x ( 0 ，) 称为转换函数。( 1 5 ) 不是简单的 将约束函数与算子相乘后代入惩罚函数，而是增加了转换函数1 i 和m a x ( 0 , - ) 。转换函 数的使用带来了便利和良好的性质。e s p c 是充要条件，而s p 、k k t 分别为充分条 件和必要条件，正是由于转换函数的使用。 定义1 2 函数的子微分n 1 用v ( x7 ) ，卢) 表示函数9 ( ) 在x e x 沿方向向量卢 的子微分，设为无穷小量，那么v ( 妒o ，) ，卢) ；1 1 翼丛生三堕堕塑。 o 一” 定义1 3 约束合格条件n 1 若x 木是p c 的c m c ，则它的连续等式约束和连续有 效不等式约束的子微分不全为o 。即不存在这样的声，使得所有i e e c v ( 红o 宰) ，卢) = 0 ，所有1 e u e cv ( g ，o 木) ，卢) = 0 。其中，e c 表示连续等式约束序号集 合，u e c 表示连续有效不等式约束序号集合。 定理1 3 连续型扩展鞍点条件n 1 如果x 木满足约束合格条件，那么工宰是p c 的 c m c 当且仅当存在& 宰o ，卢宰芑0 ，使得v a 拳掌 a 宰，v , o 幸幸 卢木满足不等式 工( 上幸，口，) s ( z 书，口幸木，卢事木) sl ( x ，口幸幸，卢木幸) ( 1 6 ) 其中，x 为连续邻域内的任意点，a e r ”，z e r 7 。 1 4 4 离散型e s p c 离散型非线性规划( d n l p ) ： ( p d ) ：m i nf ( y ) ) ，一( y x ，y 2 , - - - , y ，) r 尺” 且应满足：h ( y ) = ( i 1 1 0 , ) ，h ：( y ) ，( ) ，) ) r = 0 g ( y ) 一( g ，( ) ，) ，g ：( y ) ，g ，( ) ，) ) r 0 ( 描述3 ) y 为离散型变量。 定义1 4 离散型满足约束极小值点( c m d ) n 1y 宰满足约束，如果在离散型邻 7 东北师范大学硕士学位论文 域中，对于所有满足约束的y ，都有厂( y 术) s 厂( y ) ，那么y 鼍就是p d 的c m d 。 离散型邻域是一个用户定义概念，根据不同问题可以定义不同的邻域。 定理1 4 离散型扩展鞍点条件y 木是p d 的c m d 当且仅当存在6 t * 苫0 ， 卢木0 ，使得v a 事宰 a ，v 拳幸 卢掌满足不等式 工( y 幸，a ，) s ( y 木，口木宰，卢宰木) sl ( y ，口枣木，卢木木) ( 1 7 ) 其中，y 为离散型邻域内的任意点，a c r “，卢r 7 。 1 4 5 混合型e s p c 1 4 3 和1 4 4 中分别给出了连续型和离散型e s p c ，这是混合型e s p c 的基础。 混合型邻域由于离散部分的不确定使其也为用户定义类型。 混合型非线性规划( m n l p ) ： ( p m ) ：m i nf ( x ，y ) x 一“，屯，t ) re r ”，x 为连续型变量 x , y y ；( y l ，y 2 ，y 。) r 尺”，y 为离散型变量 且应满足：。h ( x ，y ) = 魄o ，) ，) ，h ：o ，y ) ，吒o ，y ”r - - 0 g ( x ，y ) = ( g 。o ，) ，) ，g ：o ，y ) ，g ，o ，) ，矿s o ( 描述4 ) 定义1 5 混合型满足约束极小值点( c m m ) n 1 ( x 掌，y 掌) 满足约束，如果混合型邻 域所有满足约束的( 石，y ) ，都有厂g 掌，) ，宰) sf ( x ，y ) ，那么o ，y 毒) 就是p m 的c m m 。 混合型e s p c 的惩罚函数n 1 l3 5 1 。惩罚函数的算子为ac r ”和t ie r 7 ，惩罚函数 如下： 1 4 x ，y ，口，) af ( x ，y ) + 口rl h ( x ，y ) i + 卢rm a x ( 0 ，g ( x ，y ) ) ( 1 8 ) 其中， m a x ( 0 ，g ( x ，y ) ) ，( m a x ( 0 ，9 1 0 ，y ) ) ，m a x ( 0 ，9 2 ( 工，y ) ) ，m a x ( 0 ，g ，o ，y ) ) ) ， i h ( x ，y ) l = ( i i l z l o ，y ) i , i h 2 0 ，y ) i ，l b ，y ) i ) 。 定理1 5 混合型扩展鞍点条件n 1( x 木，y 奉) 是p m 的c m m ，当且仅当存在 口宰0 ，术苫0 使得v 口誊事 口事，v 事毒 声木满足不等式 工( x 幸，y 木，a ，) s ( 工掌，y 木，口木宰，声枣木) sl ( x ，y ，口木，霉毒) ( 1 9 ) 8 东北师范大学硕士学位论文 其中，( x ，y ) 为混合型邻域内的任意点，口尺1 ，尺7 。 定义1 6 混合型邻域m m3 5 1 n m ( x ，y ) = n c ( x ) l y + n d ( y ) l x = ( x ，y ) i z n c ( x ) u ( x ，y ) lye n d ( y ) ) ( 1 1 0 ) 其中n c ( x ) 表示连续型邻域，n d ( y ) 表示离散型邻域。 此定义要求x 和y 互不干扰，所以并不能表示x ，y 有关联的邻域。 推论1 1 ( 1 ) 基于定义1 6 所定义的特殊邻域，将定理1 5 中不等式分解为 两个不等式， 三o 乖，) ，母，口，卢) s 三( _ 宰，y 掌，7 1 母搴，卢事吟s 三( i 堆，y ，口事奉，奉事) ye n d ( y , ) ( z 木，y 奉，口拳幸，木拳) s l ( x ，y ，a 誊 ，卢木书) x e n c ( x * ) 两个不等式都是必要条件，合在一起是充分条件。 9 ( 1 1 1 ) ( 1 1 2 ) 东北师范大学硕士学位论文 第二章进程信号量规划算法 带有抢占式动作敌意规划的核心问题是“资源 ，通过对资源的研究提出了实时 抢占算法和准确抢占算法。以资源为切入点重新分析规划问题，发现可以使用进程管 理的方法求解规划，这是一种新的规划研究角度。为了顺畅地将进程管理方法引入规 划以及便于理解，对资源进行修改，重新定义为信号量。 进程信号量规划算法首先分析了现有互斥关系，定义了相关干扰，提高规划解的 并行性。进程信号量规划算法通过重新定义同步与互斥来求解规划。最后提出了条件 效果的结构化扩展，使得进程信号量规划算法能够处理条件效果。 2 1 互斥关系的缺陷及改进 动作互斥中的竞争需要是通过上一层命题互斥来确定的，其只是上层命题互斥的 延续。命题互斥的标记是通过支持这些命题的动作来确定的。所以互斥关系的核心是 干扰。干扰由动作效果确定，其确定后，便可标记命题互斥，通过继承上层命题互斥， 便可标记竞争需要。 因为前提或添加效果被删除使得动作标记为互斥，本节分别从添加效果、前提被 删除两方面说明互斥关系的缺陷。 因添加效果被删除所标记的互斥一定程度上破坏了规划解的并行性。若规划问题 只包括两个动作a 、b ，目标集合是qae ，初始命题集合是pa 肌。动作a 的前提是 p ，添加效果为q ，删除效果pa ，。动作b 的前提为m ，添加效果为ea ，删除效果 是m 。a 、b 在同层执行就可达到目标状态，但是由于a 删除了b 的添加效果，所以 a 和b 标记为互斥，对该问题只做一层规划图扩展是无法达到目标状态，必须继续 扩展。干扰的标记不仅使规划图增添了额外信息，也破坏了规划解的并行性。 p 二= n o ：p 互后 m2 n 二p 图2 - 1 干扰且斥的说明 1 0 p q 一、 r互斥 e 上 m 东北师范大学硕士学位论文 这种干扰互斥是由于不同动作对同一命题的不同作用所产生的。是否在同一有效 规划中才是决定动作是否互斥的根本，所以根据命题决定动作是否标记为互斥，应该 考察该命题在规划中的重要程度。 定义2 1 相关干扰如果动作a 删除了动作b 的添加效果，并且该命题是规划 图中非n o o p 动作的前提，则动作a 和b 标记为相关干扰。 相关干扰并不能解决干扰所带来的问题，但是可以在一定程度上缓解这个问题。 图2 - 1 例子中a 与b 因为r 将被标记为互斥，但实际上r 不是任何动作的前提，所以 a 与b 并不是相关干扰，可以在同层执行，所以规划图只需扩展一层就可进行解搜 索。 当动作删除其他动作的前提，这两个动作标记为互斥。这种方式所标记的互斥实 际上是一种存在于动作内部的启发信息，被删除前提的动作应在删除该前提动作之前 执行。 2 2 规划作业的建立 首先完成规划问题到规划作业的转化，转化通过规划问题各个集合的信号量化实 现。 定义2 2 规划问题。”1 一个规划问题包括以下四个集合： 一个操作集合 一个对象集合 一个初始条件集合 一个目标集合 初始条件集合中每个元素都是一个命题；目标集合中每个元素都是一个命题，而 且要求规划结束时这些命题必须是真命题。 定义2 3 规划作业一个规划作业包括以下四个集合： 一个动作进程集合 一个初始条件信号量集合 一个目标信号量集合 一个信号量集合 方法2 1 动作进程的建立。 规划问题包括了一个操作集合，操作集合中有若干操作。首先根据具体问题将操 作实例化形成动作，建立与操作集合对应的动作集合，再由动作集合形成动作进程集 合。 动作进程是通过将动作前提及效果命题信号量化形成，也就是将前提及效果中的 每个命题都看作个信号量。若信号量由前提命题生成，则说明动作进程执行需要占 用该信号量；信号量由效果命题生成，动作执行后添加效果的信号量值加1 ，删除效 1 】 东北师范大学硕士学位论文 果的信号量值减1 。 这里以火箭问题为例完成动作进程集合的建立。 火箭问题的操作集合包括三个操作： 盍至：! 丛篚闻壁鲍拯佳篡金 m 0 v e ： ：p a r a m e t e r s ( ( r o c k ? r ) ( p l a c e ? h d m ) ( p l a c e ? t o ) ) ：p r e c o n d i t i o n ( ：a n d ( ：n e p ? f r o m ? t o ) ( a t ? r ? f r o m ) ( h a sf u e l ? f ) ) ：e f f e c t ( ：a n d ( a t ? r ? t 0 ) ( ：n o t ( a t ? r ? f r o m ) ) ( ：n o t ( h a sf u e l ? r ) ) ) u n l o a d ： ：p a r a m e t e r s ( ( r o c k7 0 ( p l a c e ? p ) ( c a r g o ? c ) ) ：p r e c o n d i t i o n ( ：a n d ( a t ? r ? p ) 伽? c ? r ) ) ：e f f e c t ( ：a n d ( a t ? c ? p ) ( ：n o t ( h a ? c ? r ) ) ) 1 0 a d ： ：p a r a m e t e r s ( ( r o c k ? r ) ( p l a c e ? p ) ( c a r g o ? c ) ) ：p r e c o n d i t i o n ( ：a n d ( a t ? r ? p ) ( a t ? c ? p ” ：e f f e c t ( ：a n d ( i n ? c ? r ) ( ：n o t ( a t ? c ? p ) ) ) 设火箭为r ，货物为a 、b ，地点是伦敦、巴黎，其中伦敦用l 表示，巴黎用p 表 示。现在对操作集合进行实例化，由于火箭从伦敦出发，到巴黎，本文只列举与规划 有关的动作。 火箭问题的动作集合： 表2 - 2 火箭问题的动作集合 u v c ： ：p r e c o n d i t i o n ( ：a n d ( a tr1 ) ( h a sf u e lr ) ) ：e f f e c t ( ：a n d ( a trp ) ( ：n o t ( a tr1 ) ) ( ：n o t ( h a sf u e lr ”) u n l o a d a ： ：p r e c o n d i t i o n ( ：a n d ( a trp ) ( i nar ) ) ：e f f e c t ( ：a n d ( a tap ) ( ：n o t ( i nar ) ) ) u n l o a d b ： ：p r e c o n d i t i o n ( ：a n d ( a trp ) ( i nbr ) ) ：e f f e c t ( ：a n d ( a tbp ) ( ：n o t ( i nbr ) ) ) l o a d a ： ：p r e c o n d i t i o n ( ：a n d ( a tr1 ) ( a ta1 ) ) ：e f f e c t ( ：a n d ( i na0 ( ：n o t ( a ta1 ) ) ) l o a d b ： ：p r e c o n d i t i o n ( ：a n d ( a tr1 ) ( a tb1 ) ) ：e f f e c t ( ：a n d ( i nb0 ( ：n o t ( a tb1 ) ) ) 动作所涉及的命题都转化为信号量，则动作转化为了动作进程，火箭问题也就丌 始向火箭作业转化。 火箭作业的动作进程集合： 盍2 ：圣么堑缝些笪动丝壅型篡佥 m o v e ： 需要占用： r - if u e l - r 1 2 东北师范大学硕士学位论文 效果： r - p + + r 一1 - f u e l f u n l o a d a ： 需要占用：r - p a - r 效果：a - p4 - + a r u n l o a d b ： 需要占用：r - p b r 效果：b - p + + b r l o a d a ： 需要占用：r - i a 1 效果：a - r + 4 - a 卜 1 0 a d b ： 需要占用：r - i b 1 效果：b r + 4 - b 1 - 信号量的具体含义在下文介绍。只有当信号量值大于o 时才可被占用，并且值的 个数决定了可被同时占用的动作进程个数。未消耗信号量是特例，在后面章节介绍。 方法2 2 初始条件信号量集合建立。 初始条件信号量集合由规划问题的初始条件集合信号量化后形成。初始条件集合 中的每个命题首先形成其所对应的信号量，并将信号量值全部赋1 。这样就形成了初 始条件信号量集合。 火箭问题的初始条件为a tal 、a tbl 、a trl 、f u e lr 。 先将这四个命题信号量化形成四个信号量分别为：a 1 、b 1 、r - 1 、f u e l - r ，并且这 四个信号量所对应的值都为1 。 方法2 3 目标信号量集合建立。 目标信号量集合由规划问题的目标集合形成。目标集合中的每个命题首先形成其 所对应的信号量，并将信号量值全部赋o 。这样就形成了目标信号量集合。 火箭问题的目标集合的命题为a tap 、a tbp 。 先将这两个命题信号量化形成两个信号量：a p 、b - p ，并且这两个信号量在规划 成功后所对应的值都应为1 。 方法2 4 信号量集合建立。 信号量集合由两部分组成，第一部分为动作进程集合所涉及到所有信号量，第二 部分由规划问题的对象集合中所有对象信号量化后形成。 火箭问题有三个对象分别为火箭r ，货物a 、b ，信号量化形成三个信号量r 、a 、 b 。火箭规划作业的信号量集合： 表2 - 4 火箭规划作业的信号量集合 对象信号量：r 、a 、b 命题信号量：r - i 、f u e l - r 、r - p a - r 、a - p 、a - i b r 、b - p 、b - i 定义2 4 信号量集合的初始化： 东北师范大学硕士学位论文 1 ) 对象信号量赋值为l 。 2 ) 初始条件信号量集合中的信号量赋值为1