（计算机应用技术专业论文）面向任务的软件过程控制方法研究.pdf

摘要 面向任务的软件过程控制方法研究 摘要 随着信息技术的发展，在软件产品的开发过程中，软件过程控制 显得日趋重要。因为软件是一种逻辑产品，不能直接使用c m m c m m i ， i s 0 9 0 0 0 等质量标准对软件过程进行控制。因此，需要建立专门的针 对软件过程的控制方法。 本文对软件过程的控制方法进行研究，提出面向任务的软件过程 控制模型t s p m 。该模型采用面向任务的项目计划，将软件过程划分 为一系列的任务。采用有限域约束规划建立约束模型，生成任务调度 方案。具体研究内容如下： 首先定义t s p m 模型的组织标准软件过程模型o s s p ，形式化描 述软件定义过程p d p 和软件执行过程p e p ，在此基础上提出软件项目 计划算法。通过度量数据的分析，确定如何对执行过程进行控制，以 及对组织标准过程进行改进，实现t s p m 模型的循环使用。 此外，t s p m 中的任务调度问题是一个n p 问题。n p 问题具有高 复杂、动态随机等特点。本文通过对约束规划原理、已有的资源约束 问题的求解算法和约束规划算法分析，提出在启发式算法和一致性算 法的基础上，采用整数有限域的优化和搜索策略解决t s p m 中的任务 调度问题。对t s p m 的全局变元、约束类型及约束条件进行讨论，建 立面向任务的软件过程控制约束模型。最后通过实验证明约束规划算 北京化工大学硕上学位论文 法解决软件过程中的任务调度问题的可行性和有效性。 关键词：软件过程，控制模型，面向任务的调度，约束规划 h 摘要 r e s e a r c ho nt a s k o r i e n t e ds o f t w a r e p r o c e s sc o n t r o l a b s t r a c t w i t ht h ei n c r e a s e m e n to fs o f t w a r es i z e ，s o f t w a r ep r o c e s sc o n t r o li s b e c o m i n gm o r ea n dm o r ei m p o r t a n t as o f t w a r ep r o c e s si saf r a m e w o r k f o r t h et a s k st h a ta r er e q u i r e dt ob u i l dh i g h q u a l i t ys o f t w a r e ad e c a d e s l o n g g o a l h a sb e e nt of i n dr e p e a t a b l e ，p r e d i c t a b l ep r o c e s s e st h a t i m p r o v e p r o d u c t i v i t ya n dq u a l i t y t h i st h e s i sp r o p o s e dat a s k - o r i e n t e ds o f t w a r ep r o c e s sc o n t r o lm o d e l f o rr e d u c i n gs o f t w a r ec o s t sa n dr i s k s ，i m p r o v i n gt h ee f f i c i e n c yo ft h e s o f t w a r ep r o c e s sw i t h o u ts a c r i f i c i n gs o f t w a r eq u a l i t y t a s k - o r i e n t e dp r o j e c t p l a ni sm a d et op a r t i t i o nt h es o f t w a r ep r o c e s si n t oas e r i e so ft a s k s t h e n c o n s t r a i n t so ft a s k sa r eb u i l tw i t hf i n i t ed o m a i nl o g i cp r o g r a m m i n ga n d s c h e d u l i n gs o l u t i o ni ss o l v e d f i r s t l y , w ed i s c u s st h eb a c k g r o u n do fs o f t w a r ep r o c e s sm o d e l i n ga n d r e l a t e dw o r k s t h e nw ep r o p o s et s p mw h i c hi ss h o r tf o rat a s k o r i e n t e d s o f t w a r ep r o c e s sc o n t r o lm o d e l o r g a n i z a t i o n ss e to fs t a n d a r dp r o c e s s ， i i i 北京化工大学硕上学位论文 p r o je c td e f i n i t i o np r o c e s sa n dp r o je c te x e c u t i o np r o c e s sa r ed e f i n e do n w h i c hw eg e tt h ep r o j e c tp l a na l g o r i t h mb a s e do nt h ed e f i n i t i o n f i n a l l y , w ed i s c u s st h ec o n t r o la n di m p r o v e m e n to ft h em o d e l i na d d i t i o n ，h o wt os c h e d u l et h et a s k si nt h et s p mi sa nn p p r o b l e m ， w h i c hi sd y n a m i cs t o c h a s t i ca n dc o m p l i c a t e d ，a f t e rc o m p a r a t i v ea n a l y s i s o fv a r i o u sa l g o r i t h m s ，c o n s t r a i n tp r o g r a m m i n gi sc h o s e nt om o d e lt h e p r o b l e m e x p e r i m e n t a lr e s u l t ss h o wt h a tc pw o r k sw e l l k e yw o r d s ： s o f t w a r e p r o c e s s ，c o n t r o lm o d e l ，t a s ko r i e n t e d s c h e d u l i n g ，c o n s t r a i n tp r o g r a m m i n g i v 北京化工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名： 笪旦竭 日期： 幽：l ：3 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 导师签名： 日期：盟：! ：三 日期：掣扛 第一章绪论 1 1 研究背景 第一章绪论 由于传统的软件产品开发大多属于个体化软件开发方法，随着软件规模和数 量的增加，许多计算机软件的开发和维护遇到了一系列严重问题。这种“软件就 是程序”的错误观念最终导致了软件危机的产生。1 9 6 8 年北大西洋公约组织的 计算机科学家在联邦德国召开国际会议，讨论软件危机问题。这次会议正式提出 “软件工程 概念并促进了这门新兴工程学科的发展。软件过程控制正是基于软 件工程学理论，以获得高效率和高质量的软件产品为目标，对软件过程的各项任 务和工作步骤进行协调控制。 软件开发过程是一个为建造高质量软件所需完成的任务的框架，即形成软件 产品的一系列步骤，包括中间产品、资源、角色及过程中采取的方法、工具等范 畴。传统的项目计划方法是面向产品的，典型的项目计划方式是先把软件系统分 成若干子系统，然后把子系统分解为若干模块，再把模块开发作为任务列入项目 计划并分配给相关人员。以这样的方式制订项目计划要求项目人员对软件过程的 理解较为透彻才能确保软件产品是依据软件过程的要求开发的。但项目成员对软 件过程的理解总是有差异的，因此，面向产品的项目计划方法不能保证软件过程 得以有效执行，进而影响软件过程的实施效果【1 1 。 同时，从面向过程的角度来看，软件过程意味着开发一个软件系统的任务集 合，这些任务由有组织的人员依赖一系列工具，高效地利用人力、物力资源，在 保证软件质量的前提下，在要求的时间内完成软件的开发。从这个角度，软件过 程可以设计成面向任务的软件控制模型。面向任务的软件过程控制面临的主要问 题是约束条件复杂，条件在不断变化，并且要通过变元和约束条件安排出合理优 化的任务分配。 以往的情况都是软件开发管理人员要对任务集合根据已有资源进行手动安 排，确定任务的时序以及资源的分配，一旦需要安排的任务和资源约束过多，那 么这将十分繁琐，耗费大量的精力和体力。软件项目开发过程中，外界环境的变 化是不可避免的。比如需求变化，时间变化，资源( 如仪器) 损坏等。外界环境 发生变化时，项目管理人员必须采取一定的方法对当前情况进行评估，以确定是 否需要对已有的开发计划进行调整。 在实际中发现大规模的软件项目开发过程中，面对不断变化的复杂的约束条 北京化工大学硕士学位论文 件，要通过变元和约束条件安排出合理优化的任务分配，在有限的时间和精力下， 无法完成。如何调配资源，分配任务才能满足项目需求，保证软件项目能够如期 完成，且能保证软件质量。进一步，如何才能得到资源的最优配置，在最短的时 间内完成所有的任务，是大规模软件开发必须解决的问题。 本论文在此背景下，研究了面向任务的软件过程控制模型及开发过程中任务 和资源的自动化配置，使用约束规划算法对任务资源进行调度，并通过实验，证 明该模型算法的有效性和可行性。 1 2 软件过程概述 1 ) 软件过程的产生 在计算机系统发展的早期时代( 2 0 世纪6 0 年代中期以前) ，通用硬件相当普 遍，软件却是为每个具体应用而专门编写的。这时的软件通常是规模较小的程序， 编写者和使用者往往是同一个人或者同一组人。这种个体化的软件环境，使得软 件设计通常是在人们头脑中进行的一个隐含的过程，除了程序清单之外，没有其 他文档资料保存下来。 从2 0 世纪6 0 年代中期到7 0 年代中期是计算机系统发展的第二代时期，这 个时期的一个重要特征是出现了软件作坊，广泛使用产品软件。但是，软件作坊 仍然沿用早期形成的个体化软件开发方法。随着计算机应用的日益普及，软件数 量急剧膨胀。在程序运行时发现的错误必须设法改正；用户有了新的需求时必须 相应地修改程序；硬件或者操作系统更新时，通常需要修改程序以适应新的环境。 上述种种软件维护工作，以令人吃惊的比例耗费资源。更严重的是，许多程序的 个体化特征使得它们最终成为不可维护的。“软件危机”就这样出现了。1 9 6 8 年 北大西洋公约组织的计算机科学家在联邦德国召开国际会议，讨论软件危机问 题，在这次会议上正式提出并使用了“软件工程”这个名词，一门新兴的工程学 科就这样开始了【2 】。 软件危机就是指在计算机软件的开发和维护中所遇到的一系列严重问题。这 些问题绝不仅仅是不能正常运行的软件才具有的，实际上，几乎所有的软件都不 同程度地存在这些问题。 概括地说，软件危机包含下述两方面的问题：如何开发软件，以满足对软件 日益增长的需求；如何维护数量不断膨胀的已有软件。主要有以下一些典型表现： a ) 对软件开发成本和进度的估计常常很不准确； b ) 用户对已完成的软件系统不满意的现象经常发生： 曲软件产品的质量往往靠不住； d ) 软件通常没有适当的文档资料： 2 第一章绪论 e ) 软件成本在计算机系统总成本中所占的比例逐年上升； d软件开发生产率提高的速度，远远赶不上计算机应用普及深入的趋势。 消除软件危机，就应该彻底消除在计算机系统早期发展阶段形成的“软件就 是程序”的错误观念。一个软件必须由一个完整的配置组成，事实上，软件是程 序、数据及相关文档的完整集合。其中，程序是能够完成预定功能和性能的可执 行的指令序列；数据是使程序能够适当地处理信息的数据结构；文档是开发、使 用和维护程序所需要的图文资料。 软件工程是采用工程的概念、原理、技术和方法来开发和维护软件，把经过 时间考验而证明正确的管理技术和当前能够得到的最好的技术结合起来，以经济 地开发出高质量的软件并有效地维护它。软件工程包括技术和管理两方面内容， 管理就是通过计划、组织和控制等一系列活动，合理地配置和使用各种资源，以 达到既定目标的过程。通常把在软件生命周期全过程中使用过的一整套技术方法 的集合称为方法学，也称为范型。在软件过程领域中，这两个术语的含义基本相 同【2 1 。 软件工程方法学包含三要素：方法、工具和过程。其中，方法是完成软件开 发的各种任务的技术方法，回答“怎样做 的问题；工具是为运用方法而提供的 自动的或半自动的软件工程支撑环境；过程是为了获得高质量的软件所需要完成 的一系列任务的框架，它规定了完成各项任务的工作步骤，由此产生了软件过程 的概念弘j 。 软件过程是为了获得高质量软件所需要完成的一系列任务的框架，它规定了 完成各项任务的工作步骤。 在完成开发任务时必须进行一些开发活动，并且使用适当的资源( 例如，人 员、时间、计算机硬件、软件工具等) ，在过程结束时将把输入( 例如，软件需 求) 转化为输出( 例如，软件产品) 。因此，i s 0 9 0 0 0 把过程定义为使用资源将 输入转化为输出的活动所构成的系统。此处，系统的含义是广义的：系统是相互 关联或相互作用的一组要素。 过程定义了运用方法的顺序、应该交付的文档资料、为保证软件质量和协调 变化所需要采取的管理措施，以及标志软件开发各个阶段任务完成的里程碑。为 获得高质量的软件产品，软件过程必须科学、有效。 没有一个适用于所有软件项目的任务集合。因此，科学、有效的软件过程应 该定义一组适合于所承担的项目特点的任务集合。通常，一个任务集合包括组 软件工程任务、里程碑和应该交付的产品【l , 2 1 。 北京化工大学硕：卜学位论文 2 ) 软件过程研究现状 自从提出软件危机的概念以来，人们从改善开发技术措施( 方法、工具) 和 组织管理措施两方面进行了大量研究，但是没有完全解决软件开发中普遍面临的 问题。为了经济地开发出高质量的软件并有效地维护它，国内外的专家进行了大 量的研究和探讨。 2 0 世纪8 0 年代末，借鉴制造业通过控制和改进工艺流程提高产品质量的方 法，软件工程界提出通过控制和改进软件过程来提高产品质量的思想。国际标准 组织建立了一系列质量管理标准，如i s 0 9 0 0 0 3 , 4 族、c m m c m m i 5 1 、p m b o k ( p r o j e c tm a n a g e m e n tb o d yo f k n o w l e d g e ) 【6 】等。这些研究各有侧重，采用的技术 标准也不完全相同。基于过程技术的质量平台，多数注重过程建模理论，形式化 或半形式化方法较多，技术稍显复杂，多数面向工业化大生产，在人机工程和产 品化方面尚需改进。而且多数的质量保证平台，以覆盖i s 0 9 0 0 1 质量基本要素或 c m m 关键过程域为目标，应用缺乏灵活性；或是提供过程建模工具，但没有导 入质量体系，应用缺乏指导性【7 】。 纵观软件工程领域的研究和实践，分析目前现状和存在的问题，可以归纳为 如下几方面瞵j ： a ) 软件过程模型缺乏“柔性”，不适应多变的开发环境 软件过程建模技术已经有十几年的发展历史，这期间提出了很多软件过程建 模方法和软件过程模型。传统的软件过程建模方法沿用了制造工业过程的建模方 法对软件过程进行建模，例如，有限状态自动机、p e t r i 网等。但是，软件过程 与传统制造业的过程有着很大的不同。软件过程具有明显的不确定性，过程能力 和人、环境、技术以及对用户需求的理解都有很大的依赖性和相关性，传统的软 件过程模型大多是静态的、机械的、被动的，它们要求软件工程人员在描述软件 过程时预期所有可能发生的情况，并且显式地定义这些问题的解决方案。当软件 过程所处的环境发生变化时，这种软件过程难以自适应地对这些变更作出相应的 调整，只能依赖软件工程人员的干预而对其进行修改，这就使得软件工程人员不 得不将大量的时问和精力浪费在软件过程的变更上，加大了软件组织( 企业) 的管 理成本。 解决软件过程模型被动问题的一个有效途径是在软件过程模型中引入自适 应特性，即模型对应的软件过程能够自治地调整自身的行为以适应软件过程环境 的变化，并确保在性能测度最大的条件下实现软件开发的目标。国内学者提出了 基于a g e n t 的自适应软件过程模型，在这种软件过程模型中，软件过程被描述为 一组相互独立而对等的实体软件过程a g e n t 。这些软件过程a g e n t 能够对软 件过程环境的变化主动地、自治地作出反应，动态地确定和变更其行为以实现软 4 第一章绪论 件开发的目标【8 】。但是这样的a g e n t 本身又应该如何约束才能充分体现现实的软 件过程，也是值得研究的课题。 b ) 管理与技术的脱节，造成实施上的困难 项目管理协会p m i 提出的项目管理知识体系( p r o j e c tm a n a g e m e n tb o d yo f k n o w l e d g e ，p m b o k ) 为项目管理提供了较为系统的方法。体系中的项目计划方 法通常是面向产品的，计划的任务要与中间或最终工作产品相关联。但这样做的 问题是，执行任务的负责人只关注能够开发出产品的工程过程，容易造成管理与 技术的脱节。避免出现这样问题的方法是，由过程改进的专门机构，如s e p g ( s o t t w a r ee n g i n e e r i n gp r o c e s sg r o u p ) ，即软件工程过程组对全体成员培训，直至 项目相关成员完全理解软件过程，并能够在项目中灵活使用。但这样一来，软件 过程实施效果又过分取决于人员能力、对过程的理解和支持程度。 基于此，国内学者提出了一种基于p d c a 的软件过程控制与改进模型。即遵 循p d c a 的原则，提出了基于p d c a 的软件过程控制与改进模型。模型采用面 向过程的方式制订项目计划，利用度量数据的分析对软件过程的执行进行控制， 并对组织标准过程进行改进【l 】。 另一方面，大量的研究关注更多的是软件开发技术，如系统建模技术、体系 结构技术、程序设计技术等等。而忽视了软件过程管理技术，造成技术与管理的 脱节。目前使用的项目管理工具、配置管理工具以及测试工具，特别是项目管理 工具与开发技术是不相关的，而软件过程却依赖于业务领域模型与开发技术。 c ) 标准的滥用与质量管理的脱位 截至2 0 0 5 年底，我国共有3 0 0 多家软件企业进行了近4 0 0 次c m m c m m i 评估。相比我国众多的软件企业而言，实施c m m c m m i 的软件企业不多，约占 全国软件企业的2 。为了探索制约c m m c m m i 实施的因素，我们针对实施 c m m c m m i 的软件企业进行了调查。调查中发现，虽然企业通过实施c m m c m m i 取得了一些收益。如促进了规范化管理、提高了项目控制能力和产品质 量等，但存在的问题也较为突出。流程繁琐僵化、实施成本高是两个主要问题。 调查还发现，造成流程繁琐的原因是很多企业的软件过程只关注c m m c m m i 模型要求，而不注意符合企业实际情况。这样的软件过程尽管可以通过高层管理 者强制推广开来，但由于缺乏有效的手段，如灵活的裁剪和度量分析、问题反馈 分析机制等，不能及时调整和改进过程，使得过程繁琐且僵化，无法适应软件企 业所面对的动态环境。执行这样的软件过程，要么付出很高的代价，要么开发人 员绕开管理过程，使得管理与技术脱节。无论是哪种情况，实施效果都不尽如人 意。c m m i 实施效果不佳而形成的过程改进“不成功”经验在软件产业内产生了负 面效应，降低了其他软件企业实施c m m c m m i 的积极性。 北京化工大学硕士学位论文 调查数据显示，随着各地政府已经降低甚至暂停了对实施c m m c m m i 的奖 励，中小型软件企业无力承担实施c m m c m m i 的各项费用。而另一方面，我国 大型软件企业数量不多，且不少已经通过了c m m c m m i 评估。而没有中小型软 件企业广泛参与c m m c m m i 的实施，扩大c m m c m m i 在我国软件业的实施规 模、促进我国软件企业全面走向规范化发展轨道是不可想象的。 3 ) 论文的主要研究内容 软件过程控制就是满足所有约束并为每一个任务分派工具，安排时间表。其 中的关键问题是数学模型的建立，包括变元的选择和变元问逻辑关系的建立。根 据数学模型，选择具体的算法搜索问题的答案。该数学模型可简化为约束规划问 题。在软件过程中，任务集合的不确定性使得软件开发管理人员必须了解软件的 开发细节，制定详细的软件开发计划。如果任务分解决策不当，将造成软件项目 开发的过程冲突和资源冲突。如某资源工作任务繁重而有些资源却处于空闲状 态，本应该先完成的任务却被安排在时间下游，导致其他相关联任务等待，无法 开始进行，延误工期。因此，在软件过程中必须采取有效地措施，保证任务和资 源的合理配置。 本论文研究提出了面向任务的软件过程控制模型，这种控制模型的思路是： 采用面向任务的计划方法，将软件过程中的各项活动转化为计划中需要完成的一 系列任务，形成任务调度方案并根据方案执行任务。当外部环境发生变化时或者 在项目执行过程中的某一时刻，决策人判断过程的实际执行能否满足项目成本 ( 人力、物力资源) 和进度要求。如果发现过程的实际执行不能满足项目计划的 要求，则必须采取措施对项目执行过程进行调整。这些措施作为任务添加到计划 中，实现软件过程的动态控制。 为了求解这个模型以得到优化结果，论文还研究建立了软件过程的任务约 束模型。面向任务的软件过程控制模型是一个约束满足问题，通过约束规划的算 法对其进行求解。软件过程中任务的安排和调度是一个排程问题，采用有限域程 序设计的模型。首先对软件过程控制模型中的的任务进行分析，确定了全局约束 变元和约束条件，总结了约束类型，并且对分支和搜索策略进行了讨论，从而建 立软件过程控制模型中的任务约束模型。 最后以b u c t p m 平台的开发为例，对软件过程任务调度进行实验，采用面 向任务的计划方法，对软件开发过程进行分析，将开发过程分解成若干个任务， 并分析了任务中的约束，建立约束模型，通过约束规划方法进行了求解。 6 第一章绪论 1 3 论文的组织结构 为了便于描述和说明，本论文主要分成六个内容相对独立的章节。主要组 织结构如下： 第一章简述了论文研究的背景，同时介绍了论文主要的研究内容。 第二章首先讨论智能规划的基本概念及其发展，然后对智能规划中的资源 约束规划原理，讨论了资源约束问题及常用算法并对其进行分析。 第三章对约束规划算法算法进行分析，并对约束规划的变量压缩事件进行 了探讨。这部分是后续模型求解的算法基础。 第四章详细介绍了面向任务的软件过程控制，建立了软件过程控制模型 t s p m 。研究了t s p m 的标准软件过程，项目计划算法以及过程改进与控制。 第五章根据软件过程控制模型中的任务特点，采用有限域约束规划算法， 建立了面向任务的软件控制的约束模型，对约束模型的变元和约束条件进行了分 析，并给出模型的求解方法。 第六章以b u c t p m 平台开发为实例，采用t s p m 的过程控制方法，对软件 开发过程进行建模和求解，实验证明约束规划算法可以快速有效地完成任务调 配，使资源得到优化配置，同时也证明了软件过程控制模型项目计划算法的可以 实现模型的循环使用。从而验证了控制模型的可行性和有效性。 7 第二章约束规划 第二章约束规划原理分析 作为本文工作的理论基础，本章首先对资源问题进行介绍，然后概述了求解 资源约束规划问题需要用到的搜索算法。在后面的章节中，在需要时将直接引用 这些基本的理论和基本概念，不再赘述。 2 1 智能规划问题 传统上的人工智能，规划被形式化为演绎推理【乳1 2 】。虽然各种形式化方法的 在细节上存在差异，但它们都用使用公理。公理陈述的是如果动作的前提成立， 则动作的发生蕴含动作的效果。这种方法将规划问题形式化为寻找一个命题的演 绎证明过程，这个命题是关于初始化条件和一个动作序列蕴含目标条件的一个推 理断言。 经典规划问题的形式化描述为：给定规划一般性模型= ( s ，a ，y ) ，其中： s = “，岛，) 为状态有限集或者递归可数集；a = “，a 2 ，) 为动作有限集或者递 归可数集；，：s a - - 2 5 为状态转换函数，以及给定初始状态瓯，目标状态s ， 的子集，求解动作序列 ，对应于状态转换序列( ，s ：，s 。) ，使得 五r ( s o ，口1 ) ，如y ( j i ，口2 ) ，s o y ( & ，口) ，且& ，贝 为 的一个规划解【l3 1 。简单地说，给出一个任务的初始状态、目标状态和所有可行的 操作，规划问题就是如何自动找到实现从初始状态到目标状态这一任务的动作序 列【1 4 1 。 因为演绎问题是非常困难的，人们开始寻找其它方法。最先发展起来的是基 于规划问题的状态空间搜索【l 。图搜索中应用目标手段分析，产生了前向搜索、 反向搜索、双向搜索，s t r i p s 搜索等等经典方法，这些方法最大困难在于状态 空间的组合的剧烈增加。在状态空间上定义启发知识，使用启发式搜索【l5 】是解决 困难的主要策略并一直应用在主流的方法中，但与领域无关的规划中的规划器很 难使用具体问题特有的知识。 后来发展的基于规划空间搜索方法具有更高的效率，将规划空间划分成不同 的层次，每一层内的规划要相对容易，且高层的计划能够为下层的规划搜索，可 在总体上提高效率，可以实现部分序列计划的循环规划、循环使用和计划修正， 增加时态推理【l6 1 。但是，规划空间结构抽象不能由规划器自动获得，而且在规划 状态空间中更难以构造启发知识，目前国内学者也正在对此进行研究【l7 1 。 从上个世纪九十年代开始规划问题的解决方法有了很大有发展，以图规划、 9 北京化工大学硕士学位论文 s a t 规划和c s p 规划为主的新的规划方法有了令人振奋的效率【1 8 。2 2 1 。 图规划使用了有效的规划图搜索空间，从规划图中产生动作集序列，相当于 层次规划中的高层部分序规划，再根据动作互斥分析搜索计划。基于规划图的规 划方法使规划效率达到了空前的水平。 c s p 规划方法是基于约束可满足性技术。c s p 是一种通用的问题求解方法， 已有许多形式化方法【2 3 1 ，约束满足问题中，变元集和相关约束随变元取值的选择 而改变。使用加速搜索的某些策略，如变元动态排序、前向检查、记忆以及冲突 定向回溯等，c s p 问题的求解已可以实际应用【2 4 1 。利用规划图，规划问题同样可 以高效地编码为c s p 问题【2 5 1 ，再用已有的c s p 算法进行求解。 s a t 规划方法的基础是可满足性问题的算法。s a t 规划方法中，经典规划问 题编码为一个命题公式，该公式具有这样的一个性质：任意模型都对应了一个计 划，且该计划是规划问题的解。s a t 规划的主要步骤是：规划问题形式化为s a t 问题，对s a t 问题进行简化并求解，然后进行抽取【2 引。 c s p 规划方法是规划问题的三种描述形式之一，它是一种面向大规模应用的 问题类型，这种类型的描述中未明确定义动作或者任务，而是将动作以事件形式 隐含在系统状态变化的过程中。事件认为是使变量值发生改变的动作，如图2 1 所示。 2 2 资源约束规划的研究 图2 1c s p 规划 f i g 2 - 1c s pp l a n n i n g 基于资源约束的规划是在1 9 9 8 年由a l b e r tl u d w i g su n i v e r s i t y 的j a n ak o e h l e r 在 她的文章( ( p l a n n i n gu n d e rr e s o u r c ec o n s t r a i n t s ) ) 中最先提出来的，在这篇文章里， 资源( r e s o u r c e ) 定义为动作活动的场所或者载体【2 7 】。例如汽车运行要消耗燃料， 这个问题中的燃料就是资源。再如在g r i d 问题中，一个机械手可以把小球从一个 房间拿到另一个房间，在这里机械手就是一种资源，它每次能携带的小球数量就 是一种资源约束。实际上，资源约束在我们的生活中也是很常见的。然而，虽然 1 0 第二章约束规划 j a n ak o e h l e r 给出了资源的定义，但是这个定义是很模糊的。因为同是在g r i d 问 题中，房间也可以看成是资源，它的空间容量也是一种资源的约束。因此，对于 具体的问题，我们不能无限制地考虑资源的影响，只选取与要求解问题相关的部 分，其它资源的影响可以忽略不计。但是在1 9 9 8 年的第四届国际规划大赛之前( 包 括这次大赛) ，资源约束的情况并没有成为一个测试问题出现。因为当时比赛所 用的标准语言s t r i p s 只能处理谓词的表述形式，而不能处理函数运算和时间关 系等等。 在2 0 0 0 年第二届国际规划大赛中，基于资源约束的规划问题第一次以m i c l 0 e l e v a t o rw o r l d 的一个子问题出现在测试问题中。m i c l 0e l e v a t o rw o r l d 是一个复 杂的电梯调度问题，它可以响应各种顾客的需求，如v i p 、n o n s t o p 、c o n f l i c tg r o u p 等等。在这个问题领域的第四个测试版本中，电梯有人数的限制。例如有8 个人 都需要从l 楼上到3 楼，如果规定电梯的限乘人数是6 ，那么电梯正确的调度动作 应该是先让6 个人上电梯，从l 楼升到3 楼，然后再回到1 楼，接剩下的两个人上3 楼。这个版本的测试问题就是一个带有资源约束的规划问题，它把电梯当成一个 资源，考虑到电梯的容纳空间，所以要求电梯每次承载的人数都不能超过它的限 定人数。在a i p s 0 0 上，只有两个规划系统能够对这个问题进行求解。一个是基 于o b d d 优化状态空间i 拘p r o p p l a n t 2 引，另一个是需要手动添加搜索控制知识的 t l p i a n 2 9 1 。 但是在2 0 0 2 的第三届国际规划大赛中，资源约束的情况已经普遍出现在各种 测试问题中，分为两大方向：m e t r i c 领域和t e m p o r a l 领域。m e t r i c 领域主要处理 数值资源的运算和约束，t e m p o r a l 领域主要处理有执行期的动作。比赛用的大 部分测试问题，例! t n z e n o t r a v e l 要求用飞机来运送乘客到达目的地，可以选用快 速飞行和慢速飞行两种方式，再女i s e t t l e r s 是在森林里砍伐木材，好的木材用车运 走，剩下的废屑盖一个简单的小房子等等。这些都包含s t r i p s 、n u m e r i c 、t i m e 、 s i m p l e t i m e 等版本。n u m e r i c 对应于m e t r i c 领域，s i m p l e t i m e 和t i m e 都属t e m p o r a l 领域，而s t r i p s 版本是为了与以前的规划问题的描述形式相兼容。n u m e r i c 版本可 以在动作的前提以及效果中处理函数及数值间的加、减、乘、除等运算， s i m p l e t i m e 在动作中加入常数执行时间，而t i m e 版则加入可变的执行时间。因为 前面已提过，可以把时间当成一种特殊的资源考虑，因此为了称呼上的方便，统 一地把它们称为“资源约束的处理 【3 0 j 。 虽然资源约束在生活中很常见，但是在规划中依然是难题【3 卜35 1 。因为不管是 图规划的扩展回溯求解，还是前向状态空间的启发式估值，所有符合条件的动作 都可应用到当前状态，因此数值变量的值往往是不确定的，人们只能估计它所能 取到值的范围。并且到目前为止，规划中的m e t r i c 领域并没有包含复杂的数学运 北京化工大学硕j ：学位论文 算，它只能处理形如y = a x + b 这样的线性方程，以及数值变量的加、减、乘、除、 赋值等运算。而在t e m p o r a l 领域，原则上动作的前提和效果可以在执行期中的任 一时间点为真，但是为了不使问题太复杂，只允许动作的前提和效果有三种时间 上的意义： a ts t a r t ：表示在动作开始执行的瞬间为真； a te n d ：表示在动作结束的瞬间为真； o v e ra l l ：表示在动作的整个执行过程中为真。 另外，a i p s 0 2 上所用的规划领域描述语言也由原来的p d d l l 0 版升级到 p d d l 2 1 版，主要是扩展了对时态的处理。p d d l 2 1 与它的一个更新的版本p d d l + 是非常相似的。p d d l + 共分为五层：第一层对应于p d d l 的命题和a d l 层， 为了与以前的语言标准兼容，没有任何的增改。第二层增加了数值变量，且可以 在瞬间访问和修改它们的值。第三层和第四层都包括了持续性动作，即动作的效 果发生在动作开始执行后的一段时间，不同的是，第三层的持续性动作在时间上 是离散的，而第四层的持续性动作可以有连续的效果。因为持续性动作只限制对 它们所影响的变量的状态的访问，所以第四层实际上是简化了实时域的模型。第 五层是第四层的一种自然扩充，表示了一种富有表达力的规划领域描述语言的设 计方式，可以表示任意的、离散时间和连续时间相混合的领域【3 6 1 。 2 3 资源约束问题的求解方法 智能规划的求解是困难的，规划问题的时间、空间复杂度都是n p 完全蒯了7 1 。 如资源约束问题本身的发展样，对它的求解方法也经历了一个发展的过程，先 是趋向于对资源进行统一的处理，然后改用不同的方法来分别处理m e t r i c 和 t e m p o r a l 。资源约束最初是由j a n ak o e h l e r 提出来的，同时她也给出了一个求解的 方法，成为以后不少规划系统用来处理m e t r i c 的基础。但是在j a n ak o e h l e r 的方法 中，动作仍然是瞬间的，动作的执行时间被视为普通的资源用资源变量的形式来 表示，不符合动作并行的需求。同时又有不少学者用建模的方法来处理资源，但 是这些方法本身大相径庭难以形成定论，并且都很少实现。因此自a i p s 0 0 以后， 人们倾向于把数值资源和时间资源分开来，用各自适合的方法来进行处理。下面 我们介绍一些有代表性的方法【3 0 】。 2 3 1 基于时间和资源的模型 r o m a nb a r t a k 将规划问题和调度问题整合起来，并且对其中的时间和资 源建立统一的模型，注意这里把时间和普通资源分开了。他认为时间是隐藏在动 1 2 第二章约束规划 作的语义后面的，因为每个动作都需要花费时间，而资源可以以公式的方式出现 在动作的前提条件和效果中。r o m a nb a r t a k 认为对前提和效果中的资源进行 编码是为经典的规划问题进行资源建模的一种标准方法。然而，这种技术只能处 理被称之为状态资源( s t a t er e s o u r c e s ) 的这样一种有限的资源形式，在前提中描 述了动作所需要的资源状态，例如“机械手空着”，而效果则描述了执行动作后 资源的状态，例如“机械手举着木块 。 时间和资源在调度( s c h e d u l i n g ) 领域中也非常重要。调度问题是在可用的 资源上分配已知的活动( a c t i v i t i e s ) 集，同时还要考虑时间进程、资源能力和其 他约束的影响。调度问题和规划问题的主要区别在于在调度问题中我们知道所使 用的活动集，而在规划问题中我们正是需要寻找这个活动集。但是在现实问题中， 很多是规划和调度问题整合在一起的【3 8 】。一般人们所做的是：先用规划的方法 来决定哪些活动可以满足需求，然后再在可用的资源上调度这些活动。所以 r o m a nb a r t a k 考虑在规划和调度问题中对资源进行统一的建模。 r o m a nb a r t a k 认为，领域( d o m a i n ) 是由三个基本要素组成的：a c t i v i t i e s 、 r e s o u r c e 矛i r e c i p e s 。a c t i v i t y 是调度或者规划的基本对象，类似于我们前面所说 的a c t i o n ，它通常会占用一定的时间和空间。而r e s o u r c e 定义了动作执行的场所， r e c i p e 描述了动作与动作之间的联系。首先，资源的模型如图2 2 所示。一般的， 资源的模型由状态集( s t a t e s ) 和状态之间的转换关系( t r a n s i t i o n s ) 组成。资源 的生命期，也就是资源随着时间的变化过程，可以用一系列的状态序列来表示。 而转换关系则描述了资源的状态如何改变。当然我们还可以定义状态的持续时 间、转换时间等等。因为资源也定义了活动所需要的空间，我们还可以描述在每 一个资源状态有多少活动的空间可得，也就是状态的容量( s t a t ec a p a c i t y ) 。状 态的容量限制了可以一起执行的活动的数目。其次，活动的模型如图2 3 所示。 活动的基本属性是它的执行时间( d u r a t i o n ) ，我们可以用时间窗口( t i m e w i n d o w s ) 来表示执行时间的范围。在大多数情况下，活动都需要处理一些资源。 例如，一次上课需要教室和老师，或者在工业活动中一次加热的活动需要烘箱、 炉灶等等。我们可以为每一个活动设置一个资源需求表( r e s o u r c er e q u i r e m e n t ) ， 在其中描述资源使用的方式。一些资源可以被消费或者生产，我们称之为可消耗 的资源( c o n s u m a b l er e s o u r c e s ) ，而另一些资源只是被使用，我们称之为可持续 的资源( r e n e w a b l er e s o u r c e s ) 。因此我们需要描述资源是可以消耗的 ( c o n s u m a b l e ) 、使用的( u s a b l e ) 还是生产的( p r o d u c a b l e ) 。在指定了动作 的资源需求以后，通常会有多种资源可供选择来满足这样的需求，因此我们还要 在每个需求后面增加可用资源列表。最后，r e c i p e 的模型如图2 4 所示：r e c i p e 表 示的是动作与动作之问的联系。我们先引入一个事件( e v e n t ) 的概念。每一个 1 3 北京化工人学硕士学位论文 活动都需要一些事件来引发它，我们称活动产生了这些事件，每一个活动又可能 产生了一些新的事件，我们称活动生产了事件。一个三元组( a c t i v i t y ，c u n s u m e d e v e n t s ，p r o d u c e de v e n t s ) 称为动作环境( a c t i v i t ye n v i r o n m e n t ) 。一个r e c i p e 是一 个d a g ( d i r e c t e da c y c l i cg r a p h ) ，它的节点是活动或者事件，图中的边要么从 一个活动指向它所产生的事件，要么从事件指向消耗该事件的活动。在活动之间 或者事件之间并没有直接相连的边，一个活动必须与它产生的事件和消耗的事件 相连( 对于每一个活动环境) 。r e c i p e 又可以看成是m e 喧aa c t i v i t y ，因此可以在一 个r e c i p e 的内部包含另个r e c i p e 。 图2 2 资源的模型 f i g 2 - 2m o d e lo fr e s o u r c e 图2 - 3 活动的模型 f i g 2 - 3m o d e lo f a e t i v i t y 图2 - 4r e c i p e 的模型 f i g 2 - 4m o d e lo fr e c i p e 另外，相应的，我们需要在初始条件和目标条件中设置资源的初始状态和目 标状态。在这种情况下，当目标中的其他条件都满足，并且资源的约束也成立时， 才称找到了规划问题的解。从上面的论述可以看出，r o m a nb a r t a k 是从模型 的角度来对资源进行处理的，他的贡献在于给出了资源