基于顺序多尺度的智能规划问题模型及其求解方法.pdf

《基于顺序多尺度的智能规划问题模型及其求解方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第51卷第4期吉林大学学报(理学版)Vo1．51No．42Ol3年7月JournalofJilinUniversity(ScienceEdition)July2013基于顺序多尺度的智能规划问题模型及其求解方法刘晓峰，李欣，曾志勇。(1．吉林省教育学院综合部，长春130022；2．东北师范大学计算机科学与信息技术学院，长春130117)摘要：针对规划定义域语言不支持对多尺度规划问题的建模，提出一种顺序多尺度的规划问题模型，设计了新的规划定义语言，并通过构造一个基于贪婪最好优先搜索法的基本方法求解顺序多尺度规划问题，证明了顺序多尺度规

2、划模型的可解性．关键词：智能规划；问题建模；顺序多尺度中图分类号：TP301．6文献标志码：A文章编号：1671—5489(2013)04—0671—05ModelandSolutionofMulti-scaleBasedIntelligentPlanningwithOrdinalMetricsLIUXiao—feng，LIXin，ZENGZhi—yong(1．DepartmentofC0，户rPsP，JilinProvincialInstituteofEducation，Changchun130022，China；2．School

3、ofComputerScienceandInformationTechnology，NortheastNormalUniversity，Changchun130117，(M)Abstract：Aimingatthestate—of-the—artplanningdomaindefinitionlanguageunsupportingmultiplemetrics，wepresentedaplanningproblemmodelwithordinalmetricanddesignedanewlanguage．Abasicsolving

4、methodbasedongreedybest—firstsearchwasproposedtoshowthesolvabilityofourproposedplanningproblem．Keywords：AIplanning；probleInmodeling；ordinalmetrics在智能规划问题中，用规划尺度(planmetric)描述衡量规划解的质量．如“能量消耗最少”是一个尺度，根据该尺度能量消耗为5O单位的规划解优于能量消耗为60单位的规划解．带有规划尺度的问题要求规划算法在多个可行规划中找到较优甚至最优的规划解．一

5、个尺度M为任一规划解隐式定义了一个尺度值计算函数CM(通常CMOr)∈)和该函数值域上的全序关系<，使规划算法能比较多个规划解的优劣．然而，当规划问题存在多个尺度时，衡量规划解的优劣存在困难．假设存在两个尺度M。和M2，两个规划解7r和7r具有如下特征：CM(丌1)

6、．作者简介：刘晓峰(1962-)，男，汉族，副教授，从事计算机应用技术的研究，E—mail：jledu@126．com．基金项目：国家自然科学基金(批准号：11226275)．吉林大学学报(理学版)第5l卷2)仅能表达尺度的相对重要性，不能表达尺度的绝对重要性．对于问题1)，由于每个尺度所评估的特征实际含义不同，因此将多尺度线性组合的实际含义难理解．此外，在上述线性组合中如果一个尺度的权重大，则表明该尺度值的变化量对混合尺度的影响大，但权重的相对大小无法表示最希望优化的尺度．为解决上述问题，本文提出一种使用顺序(ordinalord

7、er)建模多尺度规划问题的方法将多个尺度按顺序排列表示它们均有顺序性的相对重要性：排列在前的尺度最重要，如对于前述的规划解和丌，如果尺度M排在M前，则丌优于丌；如果M。排在M前，则7r优于7r．基于顺序的方法能处理各尺度值计算函数值域不同的情况，从而有更强的建模能力，并能表示尺度的绝对重要性，使规划算法优先根据重要的尺度寻找较优的规划解．基于本文提出的顺序排序多尺度方法，可以将“规划解长度最短”这个尺度加入到目前带动作代价的规划问题(planningwithactioncosts)]和带数值变量的规划问题(planningwithn

8、umericvariables)[5]中．规划算法将“规划解长度最短”作为默认的尺度能避免多数规划系统面临的当规划解代价为零时陷入宽度优先搜索的问题[6]．1智能规划的基本概念一个规划任务(planningtask)表示为，厂=(，A