论文部分内容阅读
规划是对某个即定目标给出实现它的策略。它是人工智能领域的一个重要研究方向。根据规划方法的不同可以将规划分为直接和间接两类。Blackbox采用了直接求解的规划方法,而基于案例的规划方法(CBP)则是间接求解的代表。CBP基于以往的求解信息获取规划。其求解过程可以归纳为规划匹配、规划重用、规划修正和规划存储四个步骤。规划匹配、重用和修正时往往需要使用相关领域的常识性知识以提高匹配和重用的精确度,这使得CBP系统通常领域相关。另外,规划修正的研究起步较晚,现有的CBP系统一般无法保证求解出确实存在的规划,有的CBP系统甚至不进行规划修正。因此,这类规划系统也往往被作为规划辅助系统。
Blackbox将规划求解过程中扩展和搜索状态空间的步骤分别用扩展规划图和求模型的方式实现,具有较高的求解效率和灵活、可扩展的特点。但是,Blackbox系统的灵活性为使用者带来新的难题:由于不同搜索工具适合求解的规划问题也不相同,搜索工具的选择直接关系到系统求解规划的效率,这导致使用者必须熟悉各种搜索工具。
本文提出一个基于CBP改进的Blackbox规划系统CBB。它通过规划匹配的方式,根据规划求解状态选择适用的规划工具。这样,CBB既可以简化系统使用,又可以利用各种工具间的差异来提高规划求解效率。同时,新增的规划存储模块将把本次规划求解情况记入知识库,以作为规划匹配的依据。特别地,对于新的规划工具,规划存储可以确认其适用的状态,使系统自动适应新增工具。总体而言,CBB在保留原系统灵活性和可扩展性的同时,具有较高求解效率和对规划工具的自适应能力。对使用者而言,CBB系统可以完全屏蔽规划求解过程,是真正的“黑箱”。
另一方面,CBB采用新的面向“状态”的方式比较不同的模型搜索工具,其知识库更能体现模型搜索工具在不同状态下的一般求解效率。在传统的面向“例子”的比较方式下,不同模型搜索工具“擅长”求解的规划问题类型不尽相同,因此比较算法时往往仅考察基准规划问题的总求解时间。而CBB的知识库不仅记录模型搜索工具的期望求解时间,还包括状态信息和求解情况等信息,可以更详细地考察工具间的差异。事实上,CBB系统将面向“状态”的比较方式运用于基准规划问题,可以有效利用基准规划问题对规划求解状态的覆盖力,并避免基准规划问题的可能差异。
在实现CBB系统时,本文主要针对规划匹配模块的效率进行优化。为此,知识库设计和规划存储算法设计时也着重考虑了对规划匹配的影响。实验结果证明,CBB在一定程度上提高求解效率。