（通信与信息系统专业论文）基于重构偏序规划的软件移植方法研究.pdf

摘要 软件移植是扩大软件使用范围，延长软件使用周期的重要手段之 一。但是现有的软件移植大多依靠开发人员的经验完成，难以保证移 植后系统与原系统的一致性。 本文将软件重构方法引入到软件移植之中，通过重构行为保持的 特点来保证软件移植的质量。同时为了适应复杂系统的移植，将智能 规划理论应用到软件重构中来。通过智能规划方法来指导软件重构操 作的选择，一方面使得软件移植工作可以部分自动化，另一方面也可 以避免重构操作选择的盲目性，从而提高软件移植的效率。 本文首先详细介绍了偏序规划方法，阐述了在e c l i p s e 平台下实 现s c h e m e 语言解释器插件的有关原理和技术，从而方便在软件开发平 台下实现偏序规划。为了保证软件结构描述的可视化，论文提出了基 于带属性类型图的软件结构描述方法，并通过g x l 语言将软件结构的 图形描述转换为基于谓词逻辑的软件描述，以便于实施规划。论文进 一步将偏序规划方法应用到软件重构，提出了一个基于偏序规划的软 件重构规划思想，有利于解决软件重构操作的选择问题。 论文最后以一个具体的软件移植项目为例，详细分析了重构偏序 规划的方法在软件移植中的应用，证明了软件移植中基于规划的软件 重构方法是有效的。 关键词软件重构，软件移植，偏序规划，s c h e m e 解释器 a b s t r a c t s o f t w a r em i g r a t i o ni so n eo ft h em o s ti m p o r t a n tm e a n so f e x p a n d i n g t h eu s a g es c o p eo fs o f t w a r ea n de x t e n d i n gs o f t w a r el i & c y c l e b u tm o s t e x i s t i n gm i g r a t i o nm e t h o d sr e l yo nt h ee x p e r i e n c eo fd e v e l o p e r s i ti s d i n l c u l tt o k e e ps y s t e mc o n s i g e n c yb e t w e e nt h en e ws y s t e ma n dt h e o r i g i n a lo n e t h i st h e s i si n t r o d u c e st h es o f t w a r er e f a c t o r i n gm e t h o di n t os o f t w a r e m i g r a t i o nb yu s i n gt h eb e h a v i o rk e e p i n gf e a t u r eo fr e f a c t o r i n gt o m a i n t a i nt h em i g r a t i o nq u a l i t yi nt h i sf i e l d ，a n ds i m u l t a n e o u s l yt oa d a p t c o m p l i c a t e ds y s t e m sm i g r a t i o n t h i st h e s i s a p p l i e st h ei n t e l l i g e n t p l a n n i n gt h e o r yi n t os o f t w a r er e f a c t o r i n gt oi n s t r u c tt h e r e f a c t o r i n g o p e r a t i o nc h o i c e i tc a u s e st h ew o r ko fs o f t w a r em i g r a t i o nt ob ep a r t i a l a u t o m a t e d ，w h i l ei tc o u l da v o i dt h eb l i n d n e s so fo p e r a t i o nc h o o s i n gi n r e f a c t o r i n g ，a n dt h e ni tr a i s e st h ee f f i c i e n c yi ns o f t w a r em i g r a t i o n 1 h i st h e s i sf i r s ti n t r o d u c e st h ep a r t i a lo r d e rp l a n n i n gm e t h o di n d e t a i l ，t h e na d d r e s s e st h er e l a t e dp r i n c i p l ea n dt h et e c h n o l o g yo ft h e s c h e m ei n t e r p r e t e ru n d e rt h ee c l i p s ei d e 弱a p l u g i n ，t h u si tr e a l i z e st h e p a r t i a lo r d e rp l a nu n d e rt h es o f t w a r ed e v e l o p m e n tp l a t f o r m i no r d e rt o e n s u r es o f t w a r ea r c h i t e c t u r ed e s c r i b e dv i s u a l i z a t i o n ，t h i st h e s i sp r e s e n t sa s o f t w a r ea r c h i t e c t u r ed e s c r i p t i o nm e t h o db a s e do nt h ea t t r i b u t e dt y p e g r a p ht h e o r y , a n dt r a n s f o r m ss o f t w a r es t r u c t u r eg r a p hd e s c r i p t i o ni n t o p r e d i c a t el o g i cd e s c r i p t i o nb yg x ll a n g u a g ef o ra c h i e v i n gp l a n n i n g f u r t h e r , t h i st h e s i sa p p l i e st h ep a r t i a lo r d e rp l a nm e t h o di n t os o f t w a r e r e t a c t o r i n g ，p r o p o s e sas o f t w a r er e f a c t o r i n gp l a n n i n gm e t h o db a s e do n t h ep a r t i a lo r d e r i n gp l a n n i n g ，w h i c hc o u l db eu s e f u lf o rt h es o l u t i o no f s o f t w a r er e f a c t o r i n go p e r m i o nc h o i c eq u e s t i o n f i n a l l y , t h i st h e s i st a k e sac o n c r e t es o f t w a r em i g r a t i o np r o j e c ta sa n e x a m p l e ，a n a l y s e st h ep a r t i a lo r d e r i n gp l a ns o f t w a r er e f a c t o r i n gm e t h o d i nd e t a i l ，a n dp r o v e st h a tt h i sm e t h o di se f f e c t i v ei ns o f t w a r e m i g r a t i o n k e yw o r d ss o f t w a r er e f a c t o r i n g ， p l a n n i n g ，s c h e m ei n t e r p r e t e r 玎 s o f t w a r em i g r a t i o n ，p a r t i a lo r d e r 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：生竺壅苎日期：笪旺月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名： 菇喇戈 导师签名 日期：2 丝幺年月盟日 硕士学位论文第一章绪论 1 1 研究背景及意义 第一章绪论 在过去的几十年里，计算机技术在社会各行各业中得到广泛的应用，软件技 术也得到快速的发展，这当中产生了大量优秀的应用软件。但这些软件往往要求 特定的软、硬件环境下运行，为了扩大它们的使用范围就需要对它们进行移植以 支持不同的软硬件环境。这也是现在软件提供商增强软件竞争力、增加市场占有 率的一个办法。另一方面软件产业发展到今天，商业环境的急剧变化对软件提出 了随需应变的迫切要求，软件系统变成遗留系统的周期已大大缩短。部分成熟的 软件遗留软件系统变得脆弱、不灵活、不可扩展，无法满足不断变换的业务需求， 急需维护和演进，权衡风险、费用和效果企业通常会从重新开发，封装和移植三 种策略n 1 中选择软件移植。 软件移植研究的目的是促进现有应用软件系统在新环境下的重用幢h 3 1 软件 重用则是实现一个软件系统中的软件制品在多种情况下的、广泛的重复使用。显 然移植可以看作是重用的一种形式。 重构是在一些原因( 如提高效率和可维护性) 促使下，将一面向对象的设计 在不改变其外部行为的条件下，以不同的方式进行重新安排使之更灵活并且或 者可重用性更强的过程。从这个意义上来说重构可以看作实现或增强软件重用的 一种手段h 1 。所以可以充分地发挥重构不改变软件外部可观察行为的特点来实现 软件的移植。 在面向软件移植的重构实践中，虽然用户能较清晰提出最终的重构需求，但 是现有的重构方法及工具，为确保软件重构的安全，单个重构操作对软件改动的 规模往往非常小。这些特点使得用户难以从每个较小的改动中评估系统最终的改 变，这往往会导致用户盲目地选择重构操作，降低重构效率。特别是在面向大型 软件移植的重构实践中，这种问题将更加突出。于是，如何合理地选择小步骤的 重构操作完成对软件产品的大规模的改动已成为软件移植工程实践中亟待解决 的问题。 基于以上背景，为了适应软件移植中复杂的重构过程，本文提出了基于重构 偏序规划的软件移植方法。 硕士学位论文第一章绪论 1 2 研究水平与现状 1 2 1 软件移植 软件移植就是通过一定的转换修改工作在现有版本的基础上，生成软件单元 的一个可在新的环境下运行的版本。软件单元一词在这里主要指应用程序、系统 程序或一个程序的组件。一个软件系统是软件单元的集合。环境在这里具体指在 安装过程中与所移植的软件产生相互作用的一切基础设施，通常包括处理器和操 作系统，也可能包括i o 设备、各种软件库、网络或更大的人文和物理系统。目 前软件移植研究的焦点主要集中于应用系统的移植。从软件工程的角度来看，软 件移植属于软件生命周期中的维护阶段，它是一种为适应变化了的环境而修改软 件的活动。 有调查显示，目前企业用于新业务开发的i t 投入仅占到整个i t 投入的3 0 左 右，有近7 0 的投入用于维护现有的i t 系统。而在理想状态下，企业要有4 5 左右 的投入用于开发新业务和新功能。占如此比重的软件维护包括四种维护活动，即 校正性维护、适应性维护、完善性维护以及预防性维护，其中的适应性维护就是 本文所说的软件移植。软件工程认为，软件移植是一种为适应变化的环境而修改 软件的活动，既是必需的，也是平常的。实际上很多企业正是选用了软件移植方 法通过利用原有的系统来满足新的需求哺删，这种需求有可能出于数据量增大对 系统性能要求的提高，有可能出于管理的方便直观，也有可能出于增强软件的广 泛适应性，当然还有其他各种理由。 当前，对软件开发的研究日趋完善，随着软件工程化，瀑布、螺旋、迭代等 方法已经深入人心，这些开发模型提供了软件开发全部过程、活动和任务的结构 框架，它直观明确地规定了要完成的主要活动和任务。然而对于软件移植只有实 例中产生的一些零碎的经验和建议，还没有成熟的模型可以采用，因此软件移植 的流程指导性、可控性不高。软件移植的另一个问题是自动化程度较低，人力代 价大。所以软件移植的研究不仅是必要的而且必须更深入更广泛。 软件移植不同于新的软件开发，它是建立在现有系统之上，并且新系统还需 要继承现有系统的功能或方法哺1 ，所以对于软件的移植，有一些另外的原则需要 遵守。首先移植必须忠实于原版软件，不能任意增加或删除原版软件的任何功能， 不能改变原版软件的设计风格，要使熟悉原版软件的用户对新版软件无陌生感， 不需重新培i j q e p 可使用。其次，移植后的软件必须完整反映原版软件的所有特性， 即达到内涵上的等同。再次，移植后的软件要不拘泥于原件，对不同机型、不同 软件平台灵活采用有效的编程技术，从而充分发挥新的软硬件平台的优点。 2 硕士学位论文第一章绪论 软件移植通常分为二进制移植( 可执行程序移植) 和源代码移植。虽然二进 制移植是人们所希望的，但由于其对移植环境的较大约束所以往往只能在极其相 似的应用环境下实现。源代码移植的前提是源代码可获得，但它提供了修改软件 单元以适应各种环境的可能性，所以大部分软件移植研究都是针对源代码移植 的。 现有的软件移植研究重点主要集中以下几个方面： 1 软件可移植性分析与度量 可移植性嘲一词指一个软件单元适应一个新的给定环境的能力。它是一种人 们日益期望的软件属性，是软件质量要素之一。良好的可移植性可以延长软件的 生命周期，拓展软件的应用环境。如果一个程序能够运行于一个新的环境，并且 其费用低于重新开发一个系统的费用，则说它具有可移植性。软件单元移植代价 越小，可移植性越大。 总的来说移植的代价主要取决于要移植的程序( p 1 b p ) 的大小、特征，同时 也受环境的影响。影响可移植性的主要因素可以划分成两类：移植的阻碍因素， 这里指决定程序是否需要修改的因素，主要包括源环境和目标环境的差异以及程 序本身特性；移植的代价因素，主要包括人的因素和环境因素。 2 软件移植实践 软件移植实践是从实际系统出发，针对不同的移植类型以及移植环境以具体 的实现为目的建立与之相类似工程的普适过程，为同类型的软件移植过程提供具 体的方法支持n o 】f 1 。 由于系统运行平台的多样性和特殊性，现有的对于软件移植方法的研究大多 集中在针对两个或多个特定平台之间的移植。而对于未指定具体平台的移植过程 还是缺乏实用的工具或方法。 1 2 2 软件重构 当今的软件开发多是在己有的一些工作基础上进行的，对软件复用的要求越 来越高，软件维护工作在软件开发周期中占的比例越来越大。重构方法和工具的 使用是达到这一目的的有效手段2 1 n 引。 重构是在一些原因( 如提高效率和可维护性) 促使下，将一面向对象的设计 以不同的方式进行重新安排使之更灵活并且或者可重用型更强的过程劓。 而m a r t i nf o w l e r 给出更一般的定义u 5 1 ： 重构( r e f a c t o r i n g ，名词) ：是对软件的内部结构所作的一种调整，目的 是在不改变软件可观察行为( o b s e r v a b l eb e h a v i o r ) 的前提下提高其可理解性、 降低其修改的成本。 3 硕士学位论文第一章绪论 重构( r e f a c t o r ，动词) ：使用一系列的重构动作，在不改变软件可观察之 行为的前提下调整其结构( r e s t r u c t u r e ) 。 在重构定义中，最关键的是不改变软件系统的可观察行为，并且改变软件结 构是朝着更好的设计和更能理解，而且可重用的方向进行。可以说重构提供的是 一种有效的、受控的清理代码的技术n 5 1 。 软件重构有利于简化设计，增进软件可理解性，利于快速编程，利于调试， 降低测试复杂度。 较早提出重构方法的是o p t y k e ，在文献n 们中，他在c + + 程序结构改变的研究 中，识别了保持c + + 行为的七个不变特性。l a n c et o k u d a 在o p t y k e 研究的基础上， 在用重构进化面向对象设计方面进一步取得进展n 刀。他针对由被变换语言引入的 复杂性而导致的源到源变换系统行为不能保持的缺陷，提出了四个附加的不变 式。这些不变式条件，为定义重构操作的研究提供了最基本的约束，并为后续的 自动重构工具的研究奠定了理论基础。随后，d o n a l db r a d l e yr o b e r t s 在他开发 的商品化重构工具_ s m l l t a l kr e f a c t o r i n gb r o w s e r 中通过增加后置条件， 扩展了o p d y k e 的重构定义n 射。为组合重提供了理论基础。 现阶段关于重构的研究主要集中在：基本重构方法n 9 1 乜和组合重构方法的 研究n 町：不良程序结构的探查和整理唿1 ；程序理解方法和工具1 ；面向典型设计 的重构方法n 町乜朝和软件重构辅助工具汹的实现等方面。 i 目前在软件重构实践中，一方面，对于重构操作的定义大多采用描述性的语 言，不利用重构操作的具体实例化阱1 ：另一方面，在重构中对于重构操作的选择 往往还是基于程序员的经验，这样将很容易造成导致重构操作的冗余，影响重构 的效率。 1 2 3 智能规划 智能规划是人工智能一个重要的领域，人们对它的研究已经有半个世纪之 多。在人工智能领域，规划目前还没有一个统一的定义。m c d e r m o t t 和j a m e s h e n d e l e r 认为“规划就是设计某个( 组) 实体( e n t i t y ) 的动作序列，其结果被称为 规划解( p l a n ) 川捌。直观地说，一个规划解实质上就是一个动作序列，此序列能 够实现某一目标，智能规划就是设计这个动作序列的过程，也就是说它主要解决 怎么做，而不解决为什么它是一种问题求解技术，从某个特定的问题状态出发 寻求一系列行为动作，并建立一个操作序列直到求得目标状态为止。规划技术一 般用如何将原问题分解成适当的子问题，以及如何记录并处理在问题求解过程中 发现子问题间的相互关系。近年来，有关智能规划的研究在问题描述和问题求解 两方面得到了新的突破，使得智能规划已成为一个热门的人工智能研究领域，由 4 硕士学位论文第一章绪论 于智能规划研究对象和研究方法的转变，极大地扩展了智能规划的应用领域，使 近年来智能规划的理论和应用研究有了长足的进展1 。智能规划的主要思想是： 对周围环境进行认识与分析，根据自己要实现的目标，对若干可供选择的动作及 所提供的资源限制施行推理，综合制定出实现目标的规划( p l a n ) 3 0 o 与普通的标 准搜索算法所面对的问题相比，智能规划面向的是更加复杂困难的问题( 一般都 是规模相对较大，并且求解最优解是n p 问题) 智能规划技术源于对七十年代通 用问题解决的研究，在早期有很多研究原型，但鲜有可应用的系统。随着几十年 来多种规划技术熔合性的发展，规划在性能上有了多个数量级的提高，到现在能 解决的已经不再是积木世界之类的玩具问题，而是应用在太空船自主控制、火星 探测器，企业的生产线调度，智能棋牌选手等真正改变人们的生产生活和对智能 认识的领域。 目前，智能规划理论已经成为人工智能领域研究的中心问题之一。关于智能 规划的论文是主流人工智能期刊和会议的重要来源。有关智能规划理论的国际学 术会议包括：“人工智能规划系统国际会议”( a i p s ，i n t e r n a t i o n a lc o n f e r e n c e o na ip l a n n i n gs y s t e m ) 、“空间规划和调度国际专题研讨会”( i p s s ， i n t e r n a t i o n a lw o r k s h o po np l a n n i n ga ns c h e d u l i n gf o rs p a c e ) 以及“欧洲 规划会议 ( e c p ，e u r o p e a nc o n f e r e n c eo np l a n n i n g ) 3 1 1 。 规划算法是规划理论的核心内容，典型的规划算法有：状态空间搜索规划、 偏序规划、图规划、基于知识分层任务网络规划、自适应规划和不完全信息规划 等，这些算法被大量的使用于如工业制造、智能机器人、路由选择等方面。 1 3 论文主要研究工作 现有的软件移植工作大多基于开发人员的经验完成，不能很好的保留原有软 件功能特性，经常导致移植项目失败；同时由于大规划的软件移植需要对原系统 的多个方面进行修改，在修改操作的选择上存在一定的盲目性，导致移植效率低 下。针对以上两个方面的问题，本文从智能规划理论出发，将软件重构的方法引 入到软件移植中，并对软件移植中重构操作的智能规划方法展开了研究，本文的 主要工作体现在以下几个方面。 1 实现了一个基于e c l i p s e 插件平台的s c h e m e 语言解释器，并在其之上完 成了偏序规划算法的s c h e m e 语言实现。 2 提出了基于重构的软件移植方法。分析了软件移植与软件重构之间的联 系与区别。 3 将偏序规划理论引入到重构之中，提出了一个基于重构偏序规划算法， 5 硕士学位论文 第一章绪论 以智能规划的思想来指导重构的操作选择，提高重构效率。同时为了实现对重构 的规划提出了基于谓词逻辑的软件结构和重构操作描述方法。 4 说明了基于重构偏序规划的软件移植方法的实现，并通过条件接收系统 的移植项目实现了基于重构规划方法的软件移植。 1 4 论文组织结构 本文分为五章，具体安排如下： 第一章为绪论。介绍研究目的及研究意义，综述了软件移植、软件重构和智 能规划概念及研究现状，指明本文主要的研究工作。 第二章为e c l i p s e 平台下的偏序规划设计。首先介绍了偏序规划方法中各关 键部分的概念，介绍了一个偏序规划算法。然后实现了一个基于e c l i p s e 插件的 s c h e m e 语言接收器，并在此基础上给出偏序规划方法的s c h e m e 语言描述。 第三章为基于偏序规划方法的软件移植方法研究。首先介绍了该方法的研 究背景及概述，阐述了方法的基本思想，然后定义了软件结构与重构操作的谓词 逻辑描述，最后提出基于偏序规划的软件重构算法，并提出改进对算法执行效率 的方法。 第四章为重构偏序规划方法在软件移植中的应用。简单介绍了条件接收系 统，分析了uc o s i i 操作系统的特点，针对目标移植系统的特点以偏序规划的 软件重构方法完成了条件接收系统移植的重构操作序列规划。 第五章为总结与展望。回顾论文所做的工作，并展望了论文进一步的研究 方向及目标。 6 硕士学位论文 第二章e c l i p s e 平台下的偏序规划设计 第二章e ci p s e 平台下的偏序规划设计 2 1e c l i p s e 平台概述 e c l i p s e 是一个开放源代码的、基于j a v a 的可扩展开发平台啪1 它诞生于 2 0 0 1 年1 1 月，最初是由i b m 开发，目的是成为一个为所有i b m 开发工具产品提供支 持的平台，之后i b m 把它交由e c l i p s e 基金会管理。e c l i p s e 不局限于某种具体语 言的开发环境，它作为一个所有开发工具共用的基础平台存在。为了成为一个普 适的开发环境，e c l i p s e 提供了一套插件开发环境( p l u g - i nd e v e l o p m e n t e n v i r o n m e n tp d e ) 隅1 ，p d e 允许开发者构建与e c l i p s e 环境无缝集成的工具。 e c l i p s e 是一种类似于“总线”的体系结构，如图2 - 1 所示。它的核心部分( p l a t f o r m r u n t i m e ) 非常小，它提供了许多的“插槽”( 扩展点：e x t e n s i o n p o i n t ) ，其它 功能都基于此核心写成插件。e c l i p s e 还对这些插件的协同工作提供了良好的支 持，不仅安装简单，还可以实现插件之间的无缝结合。 ij a v a 开发环 境( 臌p 0 e 环) 方插件l 境插件( j d t ) e c l i p s e 图形界面 工作台( w o r k b e n c h ) j f a c e s w t 图2 1e c l i p s e 的体系结构 e c l i p s e 可以通过集成任意语言的开发插件，成为多种语言的综合开发平台， 同时将这些开发工具集成在一个统一的开发平台界面之下m 1 例如，最新的 e c l i p s e 开发平台就综合了诸如w e b 站点、嵌入式j a v a 程序、c + + 程序和e j b 等不同 程序的开发工具。 现有的e c l i p s e 开发平台具有以下的特性：支持多种应用开发工具的构建： 能独立地开发处理各种内容的插件：开发者可以自己独立地开发工具，并与其他 7 硕士学位论文第二章e c l i p s e 平台下的偏序规划设计 标准工具无缝集成；可以在多种平台上运行等。 由于e c li p s e 平台可以通过插件系统方便地实现对不同种语言程序开发，所 以本文中采用e c l i p s e 插件的形式实现s c h e m e 语言解释器，一方面可以将人工智 能语言引如到流行的开发环境之中，另一方面可以通过插件的扩展或集成实现 s c h e m e 语言程序与其他语言程序的集成开发，方便实现统一的工具。 2 2 偏序规划方法 偏序规划最初由出现于2 0 世纪7 0 年代，t w e a k 系统采用偏序规划来进行 逻辑重建和难题简化，可以清楚地对对象进行形式化表示，允许证明规划问题的 各种不同形式与方法的完备性和可操作性。c h a p m a n 的工作啪1 论证了偏序规划器 完备性、简单性和可读性。随后s n l p 偏序规划算法的实现广为流传，并首次允 许其它研究者参与对偏序规划的理解和验证汹1 1 9 9 4 年，w e l d 在文献 4 0 1 中提 出了一种新的偏序规划方法叫i c p o p ，它采用a d l 描述规划操作，证明了一个 完备有效的偏序规划算法 偏序规划搜索问题的状态是规划( 大多数是未完成的规划) 。后继函数在行 动b 上任意选择一个开发前提p ，并在得n p 的行动a 的每个可能的一致性选择方式 上产生一个后继规划。目标测试仅需要检验没有实现的开放前提。生成的解是一 个偏序规划：无环有向图。偏序规划的优点：能够将问题分成子问题。用一个偏 序规划图就可以生成所有的全序规划。因果连接导致了早期对因不能解决的冲突 而不包含解的搜索空间部分进行剪枝。目前，对如何计算精确的启发式的了解， 偏序规划比全序规划要少。 偏序规划利用独立目标来分解原始问题，再利用了规划来求解，最后合并这 些了规划。偏序规划从一个空规划开始，寻找改进规划的途径，直到找到一个能 够解决问题的完整规划。 在规划的定序约束中没有循环而且与因果连接无冲突的规划称为一致性规 划。偏序解的每个线性化都是一个从初始状态执行后会到达目标状态的全序解。 这意味着可以把执行规划的概念从全序扩展到偏序。一个偏序规划是通过反复选 用任何可能的下一个行动来执行的。智能体在处理偏序规划的灵活性问题和环境 不协调时非常有用，灵活的定序也可以方便地将小规划合并到大规划中去，因为 每个小规划能够重新对它的行动排序以避免同其它规划发生冲突。 偏序规划的重要意义首先在于可以对搜索空间进行剪枝，删除冲突。其次， 规划解是一个偏序解，其规模较小。 偏序规划器能够先进行明确和重要的决策，而不是被追按历时顺序的步骤进 8 硕士学位论文第二章e c l i p s e 平台下的偏序规划设计 行决策。偏序规划器可以并行处理各个了规划序列，而不必指定序列的严格的先 后顺序。 2 2 1 偏序关系定义 所谓偏序关系是指，若集合x 上的二元关系r 同时满足以下三个性质： 1 r 是自反的，即坛x ，则必有x r x ； 2 r 是反对称的，即v x , y x ，若x r y 且y r x ，则必有x = y ； 3 r 是传递的，即v x , y ，z x ，若x r y 且y r z ，则必有x p , z ； 则称r 是集合x 上的偏序关系，简称偏序，记作“刀。 带有偏序的集合叫做偏序集合。只要上下文中不涉及其他种类的次序，术语 有序集合有时也可用于偏序集合。 偏序规划算法实质上是一种按偏序序列搜索算法。搜索一个动作步骤序列， 使得经过这个动作步骤的作用后，世界状态由初始状态变化为目标状态。算法应 包含以下功能： 1 选择动作：选择当前状态下能够执行的动作。 2 变量绑定( 匹配) ：根据当前状态，对动作中的变量进行约束。 3 回溯：发现死锁状态后，可以回退到以前的某个状态。 2 2 2 规划问题描述 规划问题由于其自身的特点，它至少包括三个部分：初始状态、目标状态和 动作。初始状态和目标状态是规划问题的起点和终点，动作是可能由初始状态到 达目标状态的一系列可执行的动作。初始状态和目标状态属于规划的世界状态， 一般用谓词逻辑或命题逻辑来表示。动作( 操作) 主要包括三部分：动作名称、 动作前提和动作结果。经典的s t r i p s 规划问题一般可以定义为一个三元组： ，其中，i n i t 是初始状态描述的集合，即初始世界；g o a l 是目 标状态描述的集合，即目标世界；o 是规划操作( 动作) 的集合。一个完全实例 化的操作序列称为s t r i p s 规划问题的一个解，即一个规划解，此时每一个操作称 为一个步骤，而整个规划解可以看做一个以初始状态为前提以目标状态为结果的 动作。 如图2 - 2 ，这是一个典型的规划问题，它的规划问题描述如下： 9 硕士学位论文第二章e c l i p s e 平台下的偏序规划设计 ，、 b ? a ：一 t f _ 。 l n i t 图2 - 2 典型规划问题示意图 7 7 ，i a b 一： 。： t 、 g o a l 初始状态：o n ( t a b l e ，a ) ，o n ( a ，b ) ，c l e a r ( b ) 目标状态：o n ( b ，a ) ，o n ( t a b l e ，b ) ，c l e a r ( a ) 动作：m o v e ( ? o b j ，? d e s t ) p r e c o n d i ti o n ：c l e a r ( ? o b j ) e f f e c t ：d e l e t e ：o n ( ? s r c ，? o b j ) a d d ：o n ( ? d e s t ，? o b j ) ，c l e a r ( ? s r c ) 可以看出初始状态与目标状态主要描述了规划世界中各元素之间的关系，我 们可以将这些关系的描述称之为命题，而初始状态与目标状态的描述集合称之为 命题集。命题集是规划实施的基础，一方面命题为规划操作的选择提供了依据， 另一方面规划操作也能相应地产生新的命题。最后，需要指出由于例子是一个固 定封闭的世界，所以在初始状态与目标状态描述中，没有对世界中存在的物体进 行描述，但是在一个开放世界中，这一部分也是必不可少的。 在这个例子中由于实现从初始状态到目标状态的操作比较简单，所以只定义 了一个动作m o v e ，它包含两个参数，前一个表示移动的物体，后一个表示移动的 目的。该动作完成将目标移动到目的之上的功能。在规划中，每一个动作都包含 有若干前置与后置条件，前置条件为规划操作行为提供约束，后置条件则是规划 操作行为的结果。对于一个实例化的操作而言，它的前置条件与后置条件都是命 题，只有在前置命题满足的条件下该规划动作才能够执行，作为规划操作结果的 后置命题则将对原有命题集进行增加或删除，改变原有的世界状态。我们可以通 过m o v e 这个动作分析实例化的操作对世界状态的影响，假设这个例子中，m o v e 被实例化为m o v e ( b ，t a b l e ) ，因为c l e a r ( b ) 是初始状态中存在的，那么m o v e ( b ，t a b l e ) 将执行，世界状态将被改写为o n ( t a b l e ，a ) ，o n ( t a b l e ，b ) ， c 1 e a r ( a ) ，c l e a r ( b ) 。 l o 硕士学位论文 第二章e c l i p s e 平台下的偏序规划设计 2 2 3 因果连接与规划冲突 规划算法实质上是一种搜索算法。搜索一个动作步骤序列，使得经过这个动 作步骤的作用后，世界状态由初始状态变化为目标状态。因果连接与规划冲突是 规划过程中规划操作最常出现的两种关系。 若一个操作后置条件的一部分为另一操作提供了一部分的前置条件，那么我 们说这两个操作构成一个因果连接。一个因果连接可以用研三b $ 表示，其中 & ，簿是两个规划，e 是s i 的一个后置条件，r 是s j 的一个前置条件，e 、r 存在 最一般的合一集。 以上面的规划问题为例，m o v e ( b ，t a b l e ) 的一个后置条件是c l e a r ( a ) ， 而c l e a r ( a ) 又是m o v e ( a ，b ) 的一个前置条件，那么m o v e ( b ，t a b l e ) 和m o v e ( a ，b ) 可以构成为一个因果连接。 冲突则是指一个因果链被规划中的其它某些动作破坏的情况。 设存在因果链研三：o $ 和另一个动作船，如果踮可以在和$ 之间执 行，且鼹的后置条件之一将破坏e 、r 的合一集，那么就称鼬为研三与蹄的一 个威胁，当鼹在& 和两之间执行时将发生冲突。 规划中冲突将威胁到规划的正确性，同时冲突也会导致规划无法正常实施， 规划中对冲突的消除称为冲突消解。消解冲突的方法就是在规划之间添加新的约 束，破坏冲突产生的条件。冲突消解技术一般包括“升级”、“降级”、“分离”和 “引入修复”四种。 设动作繇的一个效果u 威胁到因果连接三与蹄，那么下面任何一个约束 对于消解这个冲突都是充分的： 1 升级：加入顺序约束s j s k ； 2 降级：加入顺序约束s k s i ： 3 分离：加入新的变量约束使得e 甜： 4 引入修复：选择某个规划中已有动作或者新动作& ，其一个效果为1 ， 使得珈瓦，s k s t s j 而且v e 或者 ，跏砧。 2 2 4 偏序规划描述 偏序规划的结果( 解) 是一个基于偏序的从初始状态到目标状态的因果连接 顺序序列。偏序规划一般用一个四元组 表示，s 是一个动作的集合， b 是所有绑定到s 上的自由变量的集合，0 是顺序约束集合，l 是因果连接集合 偏序规划是通过不断修改未完成的规划直到所有目标和后续子目标都被满 足的过程。修改包括向其中加入新动作步骤，向其中加入等价或不等价绑定来约 硕士学位论文第二章e c l i p s e 平台下的偏序规划设计 束自由变量，向中加入顺序约束来安排动作步骤的先后顺序。 偏序规划方法从目标状态出发，采用逆向搜索方法。它首先从目标集中选择 一个目标状态，检索操作库中一个后置条件与该目标状态相符合的操作，通过变 量绑定实例化该操作，如果在变量绑定过程中存在冲突则认为该操作不能被执 行，否则判断该操作是否与现有的因果连接冲突，若出现因果连接冲突，则采用 升级或降级的方法来消解冲突；若不存在冲突则将该操作加入到顺序约束集0 中，并建立由该操作到目标状态的因果连接。然后将该操作的前提条件与初始世 界状态做比较，如果该操作的前提条件均可以在世界初始状态中找到，则认为该 操作可以由初始状态直接导出，否则，将不满足初始状态的前提条件加入到目标 状态中，以期望其他操作满足该条件。同时将该操作中除满足目标状态的后置条 件加入到初始条件集中，表示该操作实现后的世界状态。至此一个规划步骤完成， 最后返回该次规划之后的结果，重新开始目标条件的选择，开始下一个规划操作 选择。 通过上面的过程描述，偏序规划可以看作是对规划集的一个递归实现的过 程，通过选择目标、匹配操作，满足世界初始状态或者产生新的目标集，一直到 目标集被完全满足则认为规划成功，而一旦出现目标无法被操作满足则认为规划 无法实现，规划失败。 偏序规划建立了一个从目标集出发到初始集的过程，在这个过程建立中能够 先进行明确和重要的决策，而不是被迫按历时顺序的步骤进行决策。同时，可以 并行处理各个子规划序列，而不必指定序列严格的先后顺序。原始问题通过规划 操作的实例化被分解为独立的子目标，最后通过满足这些子目标的操作来完成对 整个规划任务的实现。 2 3 偏序规划工具实现 由前文对与偏序规划方法的介绍中可以看出，作为一种智能规划的方法，偏 序规划的目标状态与初始状态描述是以状态空间表示法描述的。所以在规划算法 的实现中，需要完成大量的事实匹配和操作实例化的过程，而现有的商业软件开 发语言( 如c ，j a v a 等) 实现这种过程往往比较复杂。所以需要人工智能语言的 支持。人工智能语言具备如下特点：具有较强的符号处理能力( 即非数值处理能 力) ：适合于结构化程序设计，编程容易；具有递归功能和回溯功能；具有人机 交互能力；适合于推理：既有把过程与说明式数据结构混合起来的能力，又有辨 别数据、确定控制的模式匹配机制。 与传统的完全在程序制导下按着预先安排好的步骤一步一步( 逐条) 执行的 1 2 硕士学位论文第二章e c l i p s e 平台下的偏序规划设计 方法相比，人工智能技术要解决的问题，往往无法把全部知识都体现在固定的程 序中。通常需要建立一个知识库( 包含事实和推理规则) ，程序根据环境和所给 的输入信息以及所要解决的问题来决定自己的行动，所以它是在环境模式指导下 的推理过程。这种方法有极大的灵活性、对话能力、有自我解释能力和学习能力。 这种方法对解决一些条件和目标不大明确或不完备，( 即不能很好地形式化，不 好描述) 的非结构化问题比传统方法好，它通常采用启发式、试探法策略来解决 问题。 典型的人工智能语言主要有l i s p 、p r o l o g 、s c h e m e 等，在本文中选取s c h e m e 作为规划工具实现的语言，同时为了利于规划工具和其他软件开发工具的集成， 所以选取e c l i p s e 平台作为s c h e m e 语言解释器实现的基础。 2 3 1 s c h e m e 语言的特点 s c h e m e 是一种系统设计语言，由l i s p 语言发展而来，属于l i s p 的一种方 言。与其他l i s p 方言相比，s c h e m e 是可以被编译成机器码的，也就意味着，它 具有更高的运行效率。s c h e m e 的一个主要特性是可以像操作数据一样操作函数 调用。 s c h e m e 最早于1 9 7 5 年出现在m i t 人工智能实验室嘲。作为一个多用途的编 程语言，它可以作为脚本语言使用，也可以作为应用软件的扩展语言来使用，它 具有元语言的特性，还有很多独到的特色，如：词法定界( l e x i c a ls c o p i n g ) 、 动态类型( d y n a m i ct y p i n g ) 、良好的可扩展性、尾递归( t a i lr e c u r s i v e ) 、函 数可以作为值返回、算术运算相对独立等。其中尾递归作为s c h e m e 中的一个核 心概念始终贯穿于s c h e m e 语言之中。它的设计目标是拥有异常清晰、简明的语 义和较少的表达式异构方式。包括命令式、函数式和消息传递式风格在内的绝大 多数程序设计模型都可以用s c h e m e 方便地表述。s c h e m e 是最早的像在l a m b d a 演算里一样提供了第一级过程的程序设计语言之一，并由此在动态类型的语言中 提供了有用的静态作用域规则和块结构的特征。在l i s p 的主要方言中，s c h e m e 第一次使过程有别于l a m b d a 表达式和符号，为所有变量使用单一的词法环境， 在确定运算符的位置时采用与确定运算对象位置一样的方式。 s c h e m e 是一种静态作用域的程序设计语言。对变量的每一次使用都对应于 该变量在词法上的一个明显的绑定。s c h e m e 中采用的是隐式类型而非显式类型。 类型与值( 也称对象) 相关联，而非与变量相关联。 尾递归是s t e e l e 和s u s s m a n 最初版本的s c h e m e 中的核心概念之一n 引。它是 s c h e m e 指定一段代码重复执行的最有效的工具，如下面的阶乘过程定义： ( d e f i n e ( f u nx ) 1 3 硕士学位论文第二章e c li p s e 平台下的偏序规划设计 递归同