（计算机软件与理论专业论文）基于资源约束的智能课程路径配置问题的研究.pdf

中山人学埘! i 学位论义捧十资源约束的智能讲程路径配冒问题的研究 基于资源约束的智能课程路径配置问题的研究 专业：计算机软件与理论 硕十生：黄超仪 指导老师：姜云e 教授 摘要 终身学习、异质化学习的新观念兴起了自主学习、非学历教学的热潮，而日 益进步的远程教学通信技术带来了极其丰富的共享课程资源和现场感强的远程 实时教学模式。由此引出了学习者应该如何按照自身的知识结构、学习目标，在 时间、费用和承受能力的限制内寻找全程最优学习路径的规划问题。 以往有关教学规划的研究，只考虑了知识因果关系对学习路径的影响，没有 综合考虑学习者多方面、多层次的需求。本文在了解现实需求的基础上，扩展了 课程路径配置课题的范围，引入多种硬约束和软约束，并对此进行了系统的、形 式化的定义，把课程路径配置定位为具有资源约束、涉及一定智能调度的智能规 划问题。 以往关于具有资源约束的智能规划的研究，主要集中于规划器内部的处理细 节，对于如何利用标准细节进行资源建模、实现现实和模型的语义一致研究得比 较少。本文提出了一套进行领域建模的流程方法，并根据资源的不同特性进行分 类，根据p d d l 2 1 标准给出各类资源的建模方案，特别提出运用预约机制解决 资源优先权问题。基于以上的基础，以及对各种规划方法如何处理时间和资源的 研究比较，选择l p g 的局部图搜索的技术进行了模型求解，对于不同的约束情 况得到优化的结果，证明了模型映射的正确性，并设计了自动化建模的程序，真 正意义上实现了把学生看作是知识的主动建构者，把学习的过程看作知识构建的 过程。从本文实践中总结的渐增型建模步骤、资源分类建模方案、预约机制等， 对于具有资源约束的领域建模有一定的启示作用。 关键词：智能规划资源约束课程路径配置领域建模方法论资源建模 中山人学倾i 学位论文 筚十资源约束的智能课程路托配置问题的研笕 r e s e a r c ho fi n t e l l i g e n tc o u r s e s p a t hc o n f i g u r a t i o n u n d e rr e s o u r c e sc o n s t r a i n t s 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 ：h u a n gc h a o y i s u p e r v i s o r ：p r o f e s s o rj i a n gy u n f e a b s t r a c t a st h en e wt r e n do fs e l f - l e a r na n dl i f e - l e a r n a sw e l la st h ec o m m u n i c a t i o n t e c h n o l o g yo fl o n g - d i s t a n c ee d u c a t i o nw h i c hb r i n g su sa b u n d a n ts h a r a b l ec o u r s e sa n d r e a l t i m es t u d ym o d e ，ap r o b l e mc o m e su pt h a th o wt of i n dt h es u i t a b l es t u d yp a t h s d u et oo n e sk n o w l e d g es t r u c t u r e ，s t u d yt a r g e t s ，s c h e d u l ea r r a n g e m e n t ，f e ea n da b i l i t y t h ef o r m e rs t u d i e sa b o u tt e a c h i n g p l a no n l y f o c u so nt h e k n o w l e d g e c o n s e q u e n c eo fs t u d yp a t h ，w i t h o u tc o n s i d e r a t i o no f v a r i o u sr e s t r i c t i o n sa n d r e q u i r e m e n t s a f t e rf i n d i n go u ts t u d e n t s f a c ts i t u a t i o n ，m yt h e s i se x t e n d st h et o p i c a r e ai n t r o d u c i n gs e v e r a ls o f tc o n s t r a i n sa n dh a r dc o n s t r a i n s b a s e do nt h es y s t e m a t i c a n df o r m a l i z e da n a l y s i s ，w ed e f i n et h ec o u r s e s - p a t hc o n f i g u r a t i o na sa na ip l a n n i n g p r o b l e mw i t hr e s o u r c e sc o n s t r a i n s ，w h i c ha l s or e l a t e dt oa is c h e d u l i n g t h ef o r m e rs t u d i e so fa ip l a n n i n gu n d e rr e s o u r c e sc o n s t r a i n sm a i n l ya t t a c ht h e i r a t t e n t i o no nt h ed e t a i l e ds o l v i n gt e c h n o l o g yi n s i d et h ep l a n n e r , t h e r ea r el i t t l es t u d y a b o u th o wt om o d e lt h er e s o u r c e sa c c o r d i n gt ot h es t a n d a r da n dh o wt oe n s u r et h e c o n s i s t e n c yb e t w e e nf a c ta n dm o d e l h e r ep u t sf o r w a r dag r a d u a lf l o wm e t h o d o l o g y t om o d e lt h ed o m a i n ，a l s ot h ec l a s s i f i c a t i o na n dm o d e ls c h e m e sf o rd i f f e r e n tr e s o u r c e s c o n s t r a i n s ，e s p e c i a l l yt h eb o o k i n gm e c h a n i s mt os o l v ep r i o r i t yo fc o m p e t i n gr e s o u r c e s b a s e do nt h ew o r ka b o v ea n dt h es t u d yt h a th o wd i f f e r e n tp l a n n i n gm e t h o d sh a n d l e t e m p o r a la n dn u m e r i cr e s o u r c e s ，h e r es e l e c t sl p g ( 1 0 c a ls e a r c hf o rp l a n n i n gg r a p h ) t e c h n o l o g y t os o l v et h em o d e l t h eo p t i m i z e de x p e r i m e n tr e s u l t s p r o v e t h e c o r r e c t n e s so fm o d e lm a p p i n g h e r ea l s ob n i l d su pas y s t e mf o ra u t o m a t i cm o d e l i n g a n dr e a l l ya c c o m p l i s ht h es e l f - d e t e r m i n a t i o no fs t u d e n t s t h eg r a d u a lf l o wm o d e l i n g m e t h o d o l o g y , t h er e s o u r c e sm o d e l i n gs c h e m e sa n dt h eb o o k i n gm e c h a n i s mg i v eg r e a t r e f e f e n c ea n dv a l u et ot h ea r e ao f a ip l a n n i n gu n d e rr e s o u r c e sc o n s t r a i n s k e y w o r d s ：a ip l a n n i n g ，r e s o u r c ec o n s t r a i n s ，c o u r s e s - p a t hc o n f i g u r a t i o n ，d o m a i n m o d e l i n gm e t h o d o l o g y ，r e s o u r c e sm o d e l i n g 中山人学坝i 学位论义壮十资源约束的智能谍程路衽配智问题的研究 第1 章引言 1 1课题背景 1 1 1 自主学习、非学历单科教育的发展趋势 在竞争激烈、瞬息万变的社会中，越来越多的劳动者顺应工作的需要，选择 在工作的同时重新学习，不断更新自己的知识结构和技能，提高就业能力和创业 能力。而在庞大的成人继续学习的队伍中，学习者的知识基础、己备技能是千差 万别的，不能僵硬地塞给他们同一套学习课程。 随着批量生产的流水线培养方式，同质化的人才危机表现得越来越明显。市 场对少量几种类型人才的需求出现饱和，大量同质化的人才最终只能陷入价格战 斗中。人们越来越意识到，要进行异质化的教育，针对不同人才的兴趣、天赋和 基础进行针对性的知识构建，以避免自身陷入同质化危机中。 因此新阶段的教学趋势提倡自主学习、因材施教，尽可能地摈弃传统教学模 式。传统模式中，教师预先规定教学迸度，学生不管资质如何、基础如何、条件 如何，都严格根据同一套流程学习同样的知识，这样会导致学习困难、兴趣减退。 新趋势把学生看作是知识的主动建构者，把学习的过程看作是个人根据个人情况 进行知识构建的过程，而不是硬性传授的过程。【1 】【2 】 在现实情况下，通常的学历教育由于需要确保学习者毕业时符合学历硬性要 求，专业课程设置一般是较为固定的必修课，可以根据本人情况进行选择的余地 不多。 但在多种形式的成人非学历教育中，由于学习一般带有非学历的明确目标， 或者是为了职业技能的培训、或者是为了兴趣爱好，在课程的选择和设置上有较 大的空间，学生往往可以根据自己的实际情况在各种各样的课程资源中不断地进 行单科的选修，获得单科的选修合格证书。由于这种方式充分体现了终身教育、 终身学习思想，必将成为现代教育模式的新发展趋势，占据教育市场的越来越大 的份额。 1 1 2 实时教学模式 非学历教育的形式一般分现场面授和远程教育两种类型。 一些演示性质或训练性质的课程，例如家电维修，非常需要师生之间的实时 双向交流，教师根据不同学生给予不同的指导，所以以夜校等形式的现场面授仍 然会占有非学历教育市场的一定份额，这种实时教学模式受到时间因素的约束。 而远程教育方面，由于可以打破空间限制，实现资源共享，使知识以前所未 耳：j _ 资源约束的智能酬程路径蚍詈问题的蝴允 有的速度爆炸。出现很多内容相似，但针列不同层次学习者，或者针对相同层次 学习者，但课程培训的目标有高低之分的多形式、多层次、多规格的教学课程资 源，使学习者的选择空例大大扩宽。远程教育中的f _ 【_ l 视广播形式，是从教师到学 生的实时单向教学。而即使在其他通过卫星通信和计算机网络的远程教学中，随 着技术的发展，以及收费降低，学习者也已经不满足于互联网课件点击等非实时 方式的教学模式，更趋向于选择实时的教学模式，例如卫星课堂、视频讨论等。 特别是双向、交互性质的需要学生参与的课程，比如外语口语教学等，更需要双 向的实时通信电路，使教学模式更具有现场感。 1 1 3 面l 临的问题 本文关注的是实时的、非学历教育。对比起学历教育，非学历教育由于提供 单科选修等形式，学生在课程选择上更具有自主性，而实时教育对比起非实时教 育，具有现场感、双向交流等优势。由于成人或在职者自身知识条件、时间条件， 在课程选择中存在很多的约束。主要存在咀下几点急需解决的问题： 1 、面对“知识爆炸”带来的庞大的教学资源，根据学习者自身千差万别的自身知 识基础，以及提高某儿项工作能力、实际技能等具体目标，如何高效地选择 学习的进度和课程路径。 2 1 学习者利用工作之余的时间进行学习，所以规划学习的课程路径时需要考虑 时间因素、以及学习者的课程承受能力。 3 ) 学习者一股还要把费用负担等因素考虑在内。 既要考虑学习者的多样知识基础、多重学习目标，又要考虑学习者空闲时问 的许可，甚至要考虑学习者的吸收能力和费用支付能力，在浩瀚的课程资源中进 行选择，甚至要是最优选择。对于人手而言是困难、耗时的。而本文1 f 是针对这 些问题，提出用计算机特有的速度和逻辑解决能力，高效、准确、优质地解决这 个智能课程路径配置问题。 中山人学坝i 学位论文早十资源约束的智能课程路张配置问题的研究 1 2相关工作 以往关于智能教学系统方面的研究，主要集中在下图中的五大模块1 3 用 户 接 口 幽1 一l 其中的教学与控制模块，主要功能是根据学科知识结构、学习要求和学生知 识基础，为学生学习某些知识点制定适合个体情况的学习计划。 根据对多篇有关智能教学的文章进行分析，以往此模块的研究可以分为两种 类型： 1 1 目标细化型： 只从总目标开始进行规划，重视目标的逐层细化，直至到达对应一门课的最 低层原予目标，找到对应的教学内容即完成规划，没有多选性。主要针对学科内 部某一知识点的掌握。 例如检测型课程规划。当控制模块检测到学生在某知识点的练习中出现某一 错误，将自动生成辅导目标，采用类似i f t h e n 的形式，一步步利用条件组合细 化辅导内容。只顾及学生出错的问题，辅导目标，不考虑学生出错原因，不考虑 最终辅导内容是否适合学生知识基础。1 4 2 ) 动作规划型： 根据学生现有知识点集合和目标知识点集合，在很多可选的课程路径中进行 挑选，可以根据时间或费用等因素最小化标准进行最优路径配置，通常配置出来 的学习路径包括多个因果关系上相继学习的课程或组件、并行学习的课程或组 件。主要针对学生全局的、长期的学习路径，本质上是从学生出发的规划。 斗十资源约求的智能谍程蹈静吼：置川题的圳亢 1 3本文研究思路和重点 根掘课题背景中面临的问题，本文研究的课程蹄径配置问题类似于上述的动 作规划型，但又扩展了以往研究的范围，是根据学生多样的基础条件、多种可能 资源、多种限制所配置的学生全局课程学习路径。 研究重点在于两方面的转化： 1 ) 如何把课程路径配置的现实情况和多重限制转化为形式化的定义和约束，侵 其可以理解为一个带有智能调度的智能规划应用问题。 2 1 如何把系统化的定义根据p d d l 建模标准和具体规划策略转化为规划所需 的领域模型和问题模型。 根据研究重点，本文对如下问题进行了研究： 1 ) 如何对一个现实问题，例如多重资源限制的课程路径配置问题，进行严格、 逻辑的定义。 2 ) 怎么样的应用问题适合应用智能规划方法进行求弁犁。 3 ) 对复杂的资源约束规划问题，进行领域建模、特别是资源建模的方法论。 4 ) p d d l 2 1 建模标准和l p g 局部搜索图规划技术，以及它们对动作并行、资 源约束建模的影n 向。 5 ) 列于上文| g 以确定下文某动作具有资源优先权的问题，如何建模实现。 6 ) 如何选择晶合适本文资源约束模型的规划技术，进行求解。 本文的研究成果是对课程路径配置问题及其资源限制进行了系统、形式化的 描述，定义此为同时涉及规划和调度的问题，运用基于操作的智能规划方法进行 求解。由于资源约束本身和p d d l 2 1 标准细节复杂性，创造性地提出渐增性的、 先动作后条件、先因果事件后资源约束的建模方法，并把其复杂的资源约束按照 互斥关系和可再生性质划分为四大类型分别给出建模的方案。在此基础上选择 l p g 的图局部搜索技术进行求解。通过渐增式的测试例子，证明了本文提出的 建模方法的正确性、完备性。并且设计了系统实现建模过程的自动化，解决了非 学历自主学习和实时模式带来的如何针对性选择学习路径的问题。 本文创新处在于提出更有现实意义的多重资源约束地课程路径配置问题，并 为其找出了智能规划求解和资源建模方法，解决了以往方法所没有考虑的多利，复 杂资源约束并存问题，丰富了智能教学系统的功能。所提出的渐增型建模步骤、 根据p d d l 2 1 和l p g 细节的资源分类建模方案，以及如何为动作在资源竞争中 争取优先权的机制，对于其他具有资源约束的领域建模有一定的启示作_ e j 。 中山人学坝i j 学位论义娃十资源约束的智能训程路竹酣冒问题的l i | _ 究 1 4文章结构 本文共分为七个章节，具体结构如下： 第1 章：为引言，介绍了本课题提出的的由来和意义，以往智能教学系统的 相关研究工作，本文包括的内容要点、创新之处以及文章结构。 第2 章：为本文研究基于的智能规划知识背景。主要介绍了与课程路径配置 领域有关的经典规划、半序规划、图规划知识，重点介绍了各种基于资源约束的 智能规划处理方法。 第3 章：为本文课程路径配置问题的细节的详细阐述，大大扩展了以往求解 方法的研究范围，给出形式化定义，继而把课程路径配置问题定位为涉及复杂资 源调度的智能规划问题。 第4 章：为智能规划建模标准p d d l 2 1 内部细节的探讨，其对时间资源、 数值资源和规划评价函数的原则性规定，是第5 章建模的基础。 第5 章：为课程路径配置领域模型和问题模型的设计。首先提出本文总结的 一套建模流程方法论：根据渐增式流程进行三因素划分、动作划分、定序设计、 事件谓词建模、以及各类资源的各种建模，完成现实课程路径配置问题到规划模 型的正确映射。 第6 章：为利用l p g 图局部搜索技术进行模型求解。首先介绍了图局部搜 索技术，以及本文运用的求解工具l p g 规划器技术，利用规划器对模型进行渐 增的测试，给出优化的测试结果。最后介绍本文设计的实现建模自动化的系统。 第7 章为小结，对本文所阐述的内容进行了总结，并对进一步的研究工作进 行了展望。 早十资源约柬n 勺智能谍程蹿静州冒问题的 i j | 究 第2 章智能规划方法与技术 2 1智能规划与问题求解 智能规划实质上是根据初始状态和目标状态，在可供选择的动作集中进行逻 辑推理选择，在满足一定的时间和资源约束下求解动作序列或半序的过程。它至 少包括三个部分： 初始状态，以一阶逻辑或命题逻辑等形式化语言描述。 目标状态，以阶逻辑或命题逻辑等形式化语言描述。 动作，也称为算子，主要包括三部分：动作名称、动作6 口提和动作效果。 有时还需要考虑动作的开销( c o s t ) 或占用资源的情况等。 规划也属于一类问题求解的方法，但问题求解偏重理淦研究，规划旨在解决 实际问题，因此规划的理论在很多方面都进行了扩展，例如： 1 ) 规划领域中不同动作问的前件后件存在复杂的依赖或冲突关系，一个动作的 选取往往对整个动作序列产生牵一发而动全身的影响，因此许多规划方法的 研究都会集中在动作和互斥依赖关系的表示上。 2 ) 现实问题需要规划可以产生动作的半序，即允许动作串行和并行，不只可以 从所有问题统一出发严格线性排序动作，还可以利用问题分解，独立在子目 标上产生子规划，最后对子规划进行合并。 3 ) 对于某些不确定领域，规划可以执行监控，进行条件规划或重新规划。1 6 1 2 2智能规划与智能调度 智能调度，研究的是如何把有限互斥的但又可重用的资源在时间上分配给不 同的任务，从而优化地实现某些目标。j o b - - s h o p 问题是一类经典的智能调度r o j 题。 智能规划与智能调度有区别也有联系： 1 ) 智能规划注重的是根据因果或互斥关系推理动作的次序。而智能调度的重点 在于对时间和资源的分配推理。智能规划考虑的是动作逻辑关系上应该在什 么位置执行某个动作，智能调度考虑的是什么时候执行一个动作，才能满足 资源方面的约束。 2 ) 由于智能调度中，往往是事先固定下某些相关动作的次序，只是逊行资源分 配，所以智能规划的结果可以作为智能调度的输入，也可以把智能渊度的优 化技术运用到智能规划器中，从而优化规划解。 3 ) 智能规划中的新领域具有资源约束的规划6 q 题，不但需要利用动作的逻 辑关系进行次序的推理，也需要考虑时问和资源的约哜 ，足智能规划技术和 中山人学碳i 学位论文 堆十资源约束的智能谢程路径酣置问题的研究 智能调度技术的结合运用。 本文所需要解决的谍程路径配置问题，币是一个较为复杂的具有资源约束的 规划问题，学习者的学习路径不仅决定于他们的初始知识基础、目标知识、不同 课程的依赖关系，还取决于学习者的承受能力、费用支付能力、学习时间等资源。 另外，对于一个现实问题，学习者要求得出的是晟优化规划路径，所以本文研究 的问题既是智能规划的领域，又由于时间和费用增加了规划的复杂性，需要引入 具有资源约束的规划技术。 从本文领域的应用范围、细节逻辑拙述、规划方法的选取上可以得出，用于 课程路径配置的智能规划方法涉及到经典规划、半序规划、图规划、基于资源约 束的智能觌划等几个概念，下面具体进行介绍。 2 3经典半序规划 2 3 1 经典规划 对于何谓经典规划，一般有以下三点假设【6 j = 环境的状态改变完全r h a g e n t 的动作造成的，排除外界的影响和干扰。 动作的执行前提、执行效果是确定的。 a g e n t 自, u ：够感知环境和它的动作的效果。 最初的经典规划还有一些细节的约束，例如动作执行的时间是原子时间、瞬 间完成的。但随着智能规划研究日益具有应用性，经典规划中添加不少实用元素， 例如动作可以有瞬问动作和持续动作之分，添加时序和资源约束，具有各种目标 优化策略等。 2 3 2 半序规划 如果状态空间的搜索方法是全序规划搜索，得到的规划解是严格的线性动作 序列。这样的规划遇到两个问题：一、从问题领域求出的不一定是完全有序的动 作规划解，即在某些现实情况下，由于目标是集合，可能会出现各为其主的不相 关动作，而不相关的动作不应该硬性规定前后顺序。二、不能利用问题分解，强 硬限制只能从所有问题出发，导致效率问题。 半序规划正是为了解决这两个问题所提出来的。任何能够将两个行动放在一 个规划中而不指定哪一个在前的规划算法都可以称为半序规划方法l ”。它对目标 进行分解，独立地在不同子目标上进行规划，最后合并规划解。与搜索算法不同 之处在于，搜索算法从一个状态搜索到另一个状态，而半序规划则是从一个规划 解改进到另一个规划解的过程。 半序规划的一般步骤如下： 址十资滋约束1 1 智能醒棵路纾削置闸艇 i j f 纯 ：“8 ”8 “，t 二j 勰” c 智蛹零二! i ! 一一王一生 l 竺兰竺= 哪一 图2 。1 半序规划过程中运用了两个莺要的策略： 最小承诺策略：在搜索和动作选择过程中，选择约束尽可能少的动作，或推 迟进行选择，直到规划中的某个其他步骤为我们做出选择。 求精策略：即一个规划解到另一个规划解的改进，满足完备性以确保不丢失 解，满足前进性以确保有效剪枝，满足系统性以确保不对候选解重复考虑。 2 4 图规划 2 4 1 规划图基本概念 1 1 规划图( p l a n n i n gg r a p h ) 规划图中包括了两种节点：动作节点和命题节点，两种层次；动作层和命题 层，三种边：前提条件边( p r e c o n d i t i o ne d g e s ) 、添加边( a d d e d g e s ) 和删除边 ( d e l e t e - - e d g e s ) 。 动作层只包括动作节点，命题层只包括命题节点，整个规划图就是动作层和 命题层交替的序列。一个命题层和它所产生的动作层组合为一个开、j 间步t 。t 层的 动作节点a 代表动作i a 】可以在t 时间步规划，l 层的命题节点f 代表命题f f _ 】作为t 层动作的前提或t l 层动作的效果。规划图从初始命题层增量地扩展，直到一 个不动点层( f i x e d - - p o i n tl e v e l ) ，此层再扩展的每层节点和互斥关系都维持不变。 t 层的动作节点a 以前提条件边连接t 层它的前提节点，以添加边连接t + 1 层的 l f 效果节点，以删除边连接t + 1 层的负效果节点。f 3 5 】 中山人学坝l 。学位论立桀十资源约束的智能谢程踣符配冒问题的 i j 究 两个动作节点的互斥关系有以下三种： 一个动作否定另一个动作的效果( i n c o n s i s t e n te f f e c t s ) 。 一个动作的效果之一否定了另一个动作的前提之一( i n t e r f e r e n c e ) 。 一个动作的一个前提与另一个动作的一个前提互斥( c o m p e t i n gn e e d s ) 。 两个命题互斥关系有以下两种：它们互为否定或获得这两个命题的可能动作 两两互斥。【7 】 2 ) 动作图( a c t i o ng r a p h s ) 【3 5 动作图：动作图a 是规划图的的予图，包括动作 a 。】和动作【。】，如果 一个动作节点在a 中，其前提节点、正负效果节点及对应边都在a 中。 3 ) 规划解图( s o l u t i o ng r a p h s ) f 3 5 】 是一个动作图，其中所有动作的前提都满足，且动作之间不存在互斥。 4 ) 伪动作( n o - - o p ) ：f 3 5 】 命题从一个命题层到下一个命题层都保持为真，在规划图中是通过一组伪动 作来实现。 5 ) 带传播的动作图( a c t i o ng r a p hw i t hp r o p a g a t i o n ) ：【3 5 一个动作图中，如果存在位于t 层的动作正效果节点，其伪动作( n o - - o p ) 在t 以后的层次存在，除非有动作节点与这个伪动作互斥。 2 4 2 图规划流程 图规划过程可以分为规划图扩展和规划解提取两部分，这里假设规划图层的次序 已为s ( o ) 、a ( o ) 、s ( 1 ) 、a ( 1 ) 中i ij 人学坝i 学位沦史 拈十资源约柬的智能议程踏许乩：箭旧题的训氕 、0 n b t y v 衙毒；。主裔碚、 、 1 。母要= 罗j i 一 日”【* m 。 r l 。 一， 图2 - 2 及图2 - 3 2 5 各种基于资源约束的智能规划实现方法 从2 0 0 2 的第三届国际规划大赛开始，资源约束的情况已经出现在各种测试 问题中。而规划的通用语言p d d l 2 1 标准中也增加了对于资源约束的处理：扩 展了对数值表达式的处理方法，提出时刻和持续时间的明确表达方式，以及为时 态规划提出完整的语法。这些都让基于资源约束的规划问题的定义更系统化、形 式化，具有良好的应用前景。 资源的处理方法经历了一个发展的过程，从开始时对所有资源进行统一处 理，到后来划分为两大分支：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 领域主要处理带有执行期的动作。 在时间的表示和摊理方面，主要的方法有使用p o i n ta l g e b r a 和i n t e r v a l a l g e b r a 对时间建模。而对于非时间的资源的表示和推理，则多参考智能凋度的 技术进行处理。以下介绍几种基于资源约束的智能规划模型和处理方法，包括用 于逻辑建模| 1 勺r o m a nb a r t a k 模型，基于状态空问搜索的放宽式规划估值方法 和日_ j 间戳方法，基于图规划的r e s o u r c et i m em a p 方法和l p g 方法，其中l p g 方法 为本文所选方法，于6 2 节中再进行详细阐述： t j ”4 = i t i c r 、 ” n ， 早十资源约束的智能谍程路槿配冒问题的研究 2 5 1r o m a nb a r t a k 模型 1 ) r o m a nb a r t a k 模型将规划问题和调度问题整合起来，参考【6 1 【8 】文献， 总结其具以下特点： 对规划问题和调度问题综合起来考虑进行建模，对时问和其他资源建立 统一的模型。认为时间是隐藏在动作的语义里面的，因为动作都需要花 费时问，状态资源则阱公式的方式出现在动作的前提和效果中。 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 和r e c i p e s 。a c t i v i t y 是调度或者规划的基本对象，即 称为活动，它通常会占用定的时间和资源。而r e s o u r c e 定义了动作需 要的资源，r e c i p e 描述了动作与事件之间的联系。 r o m a nb a r t a k 模型只是逻辑建模，给出资源约束领域的框架，没有 具体的实现方法。 2 ) 资源( r e s o u r c e ) 的模型如图所示： 图2 4 由资源的状态集( 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 ) 。状态的容量限制了可以一 起执行的活动的数目。 3 ) 活动( a c t i v i t i e s ) 的模型如图所示： 图2 5 活动的资源需求列表( 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 ) ，而另些 麓 中t t l 人学坝i 学位论义毕十资源约束的智能谍糕踹符龇置问题的1 1 j f 究 资源只是被使用，我们称之为可持续的资源( r e n e w a b l er e s o u r c e s ) 。除了资源， 活动的基本属性还有它的执行刚问( d u r a t i o n ) ，我们可以用时阳j 窗口( t i m e w i n d o w s ) 来表示执行日_ j 问的范围。 4 1 r e c i p e f j ：模型如图所示： 幽2 6 r e c i p e 主要描述的是活动与事件之间的联系，以及由此引起的活动与活动之 间的关系。每一个活动都需要一些事件来引发它，而每一个活动又可能产生了一 些新的事件。一个三元组( a c t i v i t y ，c u n s u m e de 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 c g r a p h ) ，它的节点是活动或者事件，图中的边要么从一个活动指向它所产生的事 件，要么从事件指向消耗该事件的活动。 2 5 2r e s o u r c et i m em a p 方法 j a n ak o e h l e r 在规划系统r e s o u r c e i p p ( 以下简称r i p p ) 中运用r e s o u r c et i m e m a p 表示资源的取值界限，实现了对资源的处理。参考 6 1 1 9 文献，总结r e s o u r c e t i m em a p 方法如下： 1 1 对时间资源的处理 和普通的资源一样，都用“资源变量”来表示，但是时间资源的运算和其他资 源的运算是不一样的。时间资源只有累加的运算，而其他的资源变量可以变多、 变少、或者重新赋值。 2 ) r e s o u r c et i m em a p ( r t m ) 利用r e s o u r c et i m em a p 及以r 的三科定义来记录资源：初始状态和目标 状态中资源的取值范围：资源变量在某时间步n 上可能的取值范围， r e s o u r c e t i m em a p 是这种记录的集合；动作a 的资源需求。 3 ) 动作的可达性定义 动作可达当日仅当它的逻辑前提在n 中是非互斥的；它的所有资源需求在n 中都是可能满足的；它的简单资源效果中没有一个是不可能的。 4 1 规划图的扩展： r 1 p p 规划器是基于圈规划方法的。在规划图扩展阶段主要工作是在每一个 中山人学 i l i il 学位论殳早十资源约束的智能诫程龉静眦置问题的矾究 h 1i 刮步进行r t m 的计算。规则如下： 先用n 时间步的资源敬值范围初始化1 1 + 1 步的资源取值 如果是时i 刮资源，则下界不变，上界用执行所有动作后最大的时间赋值。 如果是其他普通资源，取影响此资源的最大非互斥动作集进行计算，取 交集。 当规划图被扩展到逻辑目标第一次非互斥地达到，以及r t m 值和所有的目 标界限的交集非空，就开始进行规划图搜索寻找规划解阶段。 5 1 规划解提取 动作选择阶段：选择每一个动作前，都进行两个步骤：判断其和己选动作有 没有互斥，判断其是否可达。 当冲突产生时，规划系统根据冲突消解策略，通过增加更多的动作来消解冲 突，使得最后动作集的目标落在资源声明的范围内，并且使得r t m 值与每 个动作的资源需求一致。 虽然r i p p 所提出的r t m 方法是在图规划的基础上相对完备的处理数值资 源的方法，但是由于它重新定义了动作的互斥关系，并且在每一步计算中都考虑 到资源的影响，因此使得它的实现非常的复杂。在a i p s 0 0 中，r i p p 在给定的二 十多个问题只有7 个问题在规定的时间内找到规划解。 2 5 3 放宽式规划估值 作为f f 规划器的扩展版本，m e t r i c f f 规划器增加了对数值资源的处理，运 用放宽式规划的方法可以快速求解具有数值资源约束的规划问题。参考 6 1 1 1 0 1 文献，m e t r i c f f 的规划方法特点总结如下： 1 ) m e t r i c f f 只能处理数值资源约束，不能处理另一分支的时态资源约束问题。 2 1m e t r i c f f 仍然是基于前向状态空间搜索。状态空间搜索的方法对于增加了资 源调度、目标包含调度优化的规划问题，可能会导致搜索空间迅速膨胀的问 题，需要采取特殊的策略尽量压缩搜索空问。 3 ) 和f f 规划器样，在m e t r i c - f f 中仍然使用放宽式规划，不仅忽略了动作的删 除效果，而且还忽略了数值的减少效果。所以只适用于变量值倾向于变大的 单调规划任务。在r i p p 规划方法中对数值设定上下界，在m e t r i c f f 中只设定 上界。 4 ) 为了找到更优化的解，m c t r i c f f 采取增强型的爬山法，不是选取与当前搜索 状态直接相邻的估值最好的一个后继节点，而是采用宽度优先搜索，找到一 推十资婚约束的智能潍程蹄静酣胃问题的训究 个严格意义上更好的。 5 ) 为了压缩搜索空问，建立希望动作集( h e l p f u la c t i o n s ) 的剪枝技术。一个动 作被认为是有希望的，是指它至少能够到达放宽式规划中最低层的一个目 标，搜索只扩展希望动作集中的动作产生的节点。 6 ) 为了解决增强型的爬山法和希望动作集剪枝技术带来的不完备性，规划系统 在规划失败后会自动启动一种没有剪技技术的完备的搜索策略贪心最 佳搜索。 2 5 4 引入时间戳( t i m es t a m p ) s a p a 规划系统中采用新的状态描述，把时问戳( t i m es t a m p ) 和数值函数值 等引入到状态描述中，是能够同时处理m e t r i c 和t e m p o r a l 的前向状态空间搜索 规划系统1 1 1 1 【1 2 l 。从a i p s 0 2 赛果看，s a p a 在n u m e r i c 问题中表现不如t c m p o r a l 问题中表现得出色。参考【6 】文献，s a p a 规划方法特点总结如下： 1 1 带时间戳的状态描述如下：s = ( p ，m ，1 1 _ ，o ，t ) ， p = ( lt i t ) 是谓词p i 的集合，p i 在时 f i j t i 为真，l 是它为真的最 后瞬问；m 是表示数值约束的所有函数的值的集合；n 是动作前提中持续条 件的集合；q 是事件( e v e n t ) 队列，是未来某一时刻将要发生的变化的集合， 这种变化会改变p 、m i i i ：t 是s 的时间戳。 2 ) 目标状态是由n 个二元组的集合表示：g = ( ) ，p i 是第 i 个目标，t i 是p i 必须实现的时刻。 3 ) 在每个状态中，s a p a 都把所有可应用的动作应用到当前状态中，如果不是目 标：状态，就把结果状态放在排序队列中。然后循环从状态队列中取状态进行 作用。而队列中的状态又会根据从当前状态到达目标状态困难度的启发式函 数进行排序。 4 ) 为了提高效率，启发式估值时使用放宽的时态规划图r t p g ，通过忽视动作 的删除效果和数值部分来建立。整个规划过程采取的是先放宽规划，后调整 的策略。 5 ) 虽然引入时间戳可以处理t e m p o r a l 问题，实现动作的并行性。但由于启发式 仙值时构建的是放宽规划，忽视所有与资源有关的效果，所以可能失去一些 动作，这些动作的唯一目的是为其他动作提供足够的与资源有关的条件。凶 此，s a p a 通过增加一些对资源服务的动作，来列放宽式规划估值做调整。 中山人学坝i 。学位硷文坫十资源约束的智能课程路径配置问题的例兜 第3 章课程路径配置问题的定义 3 1知识点、课程、后续课程、课程路径配置概念 3 1 1 知识点k 对一定领域范围知识内容的表示，是课程内容的组成部分，具有局部完整性， 不可再分。知识点之间内容不存在交叉。知识点集合为k 。关于知识点的划分粒 度问题【1 3 】不是本文的讨论范围。 3 1 2 课程c 从旧知识点获取新知识点的过程。一门课程c 是一个4 元组( k _ c o m p o n e n t t i m e ，d u r a t i o n ，c o s t ) ，课程的集合为c 。 1 ) 组件k _ c o m p o n e n t 应该包括课程的前提和目标1 1 4 】，这里设为3 元组( t c ，r k ，a k ) 。 t c ：是门课程名称。 r k ：是学这门课程前必须掌握的前提知识点集合。r k _ k 。 a k ：学这门课程后可以掌握的新知识点集合。a k k ，r k na k = 彩。 由于课程是由不同的老师设置的，他们只能看到课程模型的片断，所以对于 一门课程，其r k 中的知识点可能出现以下情况：c j 一c o m p o n e n t r k 存在两个 知识点真子集s u b k l ，s u b k 2 ，它们同时出现在另- - f 课程t 的k c o m p o n e n t 中，其中s u b k l kc o m p o n e n t r k a n ds u b k 2 kc o m p o n e n t ：a k ，也就是 晓一门课程的前提知识之间也可能有知识的继承关系，而不是处于同等级。 同理，一个课程的a k 中的知识点也会出现类似情况。 2 1 上课时间t i m e 解释为一周中哪一天上课，有以下假设： 每一天只有一个时间段开课。一周中七天定义为w = t l ，t 2 t 7 ，。 根据实际需要，同一门课可以在一周中的多天开课。即一个课程组件的 t i m e 是一个集合，t i m e l w 。例如，语文课可以在周三和周四都开课，都是实时 的，内容一样。即如果要学习语文，可以根据学生的具体情况选周三或周四之一 就可以。 在一个时间段中，不同的学校或网络频道可以同时提供几门不样的课。 牡十资泺约求的智能雌程路静叭罱问题的州究 也就是| 兑不同课程的t i m e 集合有交集，例如语文和数学都在周三上。所以当要 上语文和数学课时，需要处理时f 日j 冲突问题。 3 1 课时d u r a t i o n 解释为一门谍要上l ) n 。木文根据实际情况作以下假没：假设每门课的持续 时间都是固定的周数nw e