基于启发式搜索的灵活规划的算法研究与系统实现

  本文关键词：基于启发式搜索的灵活规划的算法研究，由笔耕文化传播整理发布。

计算机科学２００８Ｖ０１．３５№．４

基于启发式搜索的灵活规划的算法研究与系统实现＊）

李杨１ ２陈佳豫１ ２韩诚山１孙焱３谷文祥３

（中国科学院长春光学精密机械与物理研究所长春１３００３３）１（中国科学院研究生院北京１０００４９）２

（东北师范大学计算机学院长春１３０１１７）３

摘要随着智能规划研究的深入，经典规划已不能满足实际应用的需要。本文分析了经典规划无法满足实际应用要求及产生灵活规划的原因。在对启发式搜索和灵活规划深入研究的基础上，提出了利用启发式搜索的方法来处理灵活规划问题的思想，并给出了基于启发式搜索的灵活规划算法和求解模型。采用智能规划中的基准问题对该算法进行测试，实验表明该方法在处理很多领域问题上都可以得到非常好的效果。

关键词人工智能，智能规划，灵活规划，启发式搜索

ＲｅｓｅａｒｃｈｏｆＦｌｅｘｉｂｌｅＰｌａｎｎｉｎｇＡｌｇｏｒｉｔｈｍａｎｄＳｙｓｔｅｍＩｍｐｌｅｍｅｎｔＢａｓｅｄｏｎＨｅｕｒｉｓｔｉｃＳｔａｔｅＳｅａｒｃｈ

ＬＩＹａｎ９１ ２ＣＨＥＨＪｉａ－Ｙｕ１，２ＨＡＮＣｈｅｎｇ－Ｓｈａｎ＇ＳＵＮＹａｎ３ＧＵＷｅｎ－Ｘｉａｎｇｚ

（ＣｈａｎｇｃｈｕｎＩｎｓｔｉｔｕｔｅｏｆＯｐｔｉｃｓ，ＦｉｎｅＭｅｃｈａｎｉｃｓａｎｄＰｈｙｓｉｃｓ，Ｃ１１ｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｃｈａｎｇｃｈｕｎ１３００３３）１

（ＧｒａｄｕａｔｅＳｃｈｏｏｌｏｔｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００４９）２

（Ｓｃｈ００ＩｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＮｏｒｔｈｅａｓｔＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３０１１７）３

ＡｂｓｔｒａｃｔＴｒａｄｉｔｉｏｎａｌｌｙ，ｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｓａｒｅｃａｓｔｉｎｔｅｒｍｓｏｆｉｍｐｅｒａｔｉｖｅｃｏｎｓｔｒａｉｎｔｓｔｈａｔａｒｅｅｉｔｈｅｒｗｈｏｌｌｙｓａｔｉｓｆｉｅｄｏｒｗｈｏｌｌｙｖｉｏｌａｔｅｄ．Ｉｎｔｈｉｓｐａｐｅｒ．ｗｈｙｃｌａｓｓｉｃａｌｐｌａｎｎｉｎｇｃａｎｎｏｔｃａｐｔｕｒｅｔｈｅｆｕｌｌｓｕｂｔｌｅｔｙｏｆｍａｎｙｒｅａｌｐｒｏｂｌｅｍｓｉｓａｒｇｕｅｄ．Ａｎｅｗｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｉｓｄｅｆｉｎｅｄｗｈｉｃｈｓｕｐｐｏｒｔｓｔｈｅｓｏｆｔｃｏｎｓｔｒａｉｎｔｓｏｆｔｅｎｆｏｕｎｄｉｎｒｅａｌｉｔｙ．Ａｎｅｗｃｏｎｃｅｐｔｕ－ｓｉｎｇｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈｔｈｅｏｒｙｔＯｓｏｌｖｅｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｉｓｄｅｓｃｒｉｂｅｄ．Ｔｈｉｓｐａｐｅｒａｌｓｏｉｎｔｒｏｄｕｃｅｓａｎｏｖｅｌｓｏｌ—ｖｉｎｇｍｏｄｅｌｏｆｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｕｓｉｎｇｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈｔｈｅｏｒｙａｎｄｅｘｐｌｏｉｔｓｔｈｅａｌｇｏｒｉｔｈｍｆｒａｍｅｗｏｒｋｏｆｆｌｅｘｉｂｌｅｐｌａｎ－１１ｉＴｌｇｂａｓｅｄｏｎｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈ．

ＫｅｙｗｏｒｄｓＡＩ，Ｉｎｔｅｌｌｉｇｅｎｔｐｌａｎｎｉｎｇ，Ｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇ，Ｓｔａｔｅｈｅｕｒｉｓｔｉｃｓｅａｒｃｈ

Ｉ引言于Ｇｒａｐｈｐｌａｎ和ＣＳＰ的。

本文提出了基于启发式搜索的灵活规划的算法。启发式

智能规划是一门涉及知识表达、知识推理、非单调逻辑、搜索是在搜索中加入了与问题有关的启发式信息，用以指导情景演算、人机交互和知识挖掘等各个方面知识的多领域交搜索朝着最有希望的方向前进，加速问题的求解过程并最终叉性学科［１］，被广泛运用于航空航天技术、机器人控制、后勤找到最优解。在多次国际规划器比赛中发现，采用启发式知调度、游戏角色设计、系统建模等方面，，带来的成果有目共睹。识的规划器比没有采用启发式知识的规划器得到的效果要近几年来，随着客观条件的改善，世界上特别是一些发达国家好，表现出了很强的问题求解能力。基于以上启发式搜索和在此领域获得了长足的发展，在国防和空间技术领域中得到灵活规划的优点，把启发式思想运用到了灵活规划中，产生了成功应用，取得了巨大的经济和社会效益。新的有效算法，为灵活规划的求解开辟了新的途径。

９０年代，规划系统的研究达到高潮。目前解决规划问题本文的其它部分安排如下：第２节是本文的研究基础，主主要有三种方法：第一种方法是Ｂｌｕｍ和Ｆｕｒｓｔ提出的Ｇｒａｐｈ－要介绍灵活规划的提出背景及灵活规划的相关知识和启发式ｐｌａｎ方法［ｚ１；第二种方法是Ｋａｕｔｚ和Ｓｅｌｍａｎ提出的约束可满搜索的知识；第３节提出基于启发式搜索的灵活规划的算法足方法［３］；第三种方法是Ｂｏｎｅｔ和Ｇｅｆｆｅｒ提出的启发式搜索和求解模型；第４节是实验结果分析；最后是总结。

规划方法［４］。用启发式函数产生规划实例的说明，用来指导

规划在状态空间中的搜索。２研究基础

随着规划的不断深入研究，经典规划存在的不足越来越２．１灵活规划（ＦｌｅｘｉｂｌｅＰｌａｎｎｉｎｇ）概述

明显。它对现实世界的许多问题，例如一些复杂的航空航天现实世界非常复杂，很多实际问题的约束条件灵活。经问题，都无法有效地刻画，因此产生了一种新的规划即灵活规典规划是一种强约束问题，即对于约束条件或者完全满足或划。用于处理这种灵活规划的规划器称为灵活规划器。规划者完全不满足，操作的可用性在特定情况下是布尔的。这种器实际上是一个软件，在这里规划算法无疑成为规划器的核框架对于刻画现实世界的很多问题太过于严格。为了解决上心，目前用于解决灵活规划的规划器所使用的算法多数是基述情况，产生了灵活规划。灵活规划描述支持软约束，是对经＊）国家自然科学基金项目（编号为：６０５７３０６７和６０４７３０４２）。李杨博士研究生，主要研究方向为智能规划与规划识别、软件可靠性、软件工程；陈佳豫博士研究生，主要研究方向为软件工程；韩诚山研究员，硕士生导师，主要研究方向为空间相机控制方法研究；孙焱硕士研究生，主要研究方向为图像处理；谷文祥教授，博士生导师，主要研究方向为智能规划与规划识别、形式语言与自动机理论、模糊数学及其应用。万　方数据 ２０７

  本文关键词：基于启发式搜索的灵活规划的算法研究，由笔耕文化传播整理发布。