【基於最少冒险思想的部分序规划生成算法研究】廉维.pdf

提要规划是人工智能中的一种问题解决技术和方法。使用最少冒险思想的部分序规划是它的重要方面。本文给出了生成部分序规划的主要数据结构和算法。对威胁的处理是部分序规划的重要环节之一。我们提出了新的判断威胁中次序关系的算法,与计算传递闭包相比较,该算法的时间复杂性从o(n)降到o(n)。另外,我们对部分序规划中的回溯进行了深入探讨,给出了可避免回溯的几个判定条件。我们引入了一种启发式方法,并结合我们给定的判定条件,给出了部分序规划的生成算法。在文章的最后,我们给出了使用部分序的层次规划算法。

第一章引言第一章引言第一节发展历史规划(planning)是人工智能领域里的重要分支之一。通常的规划是指人们为达到某个目的,而制定的一个动作序列。我们这里的规划是特指人工智能领域里的一种问题解决技术.规划技术由来已久。它是从搜索技术和通用问题解决技术逐渐演变而来。早在六十年代末,七十年代初,第一个主要的规划系统STRIPS[1].就诞生了。STRIPS主要用于机器人SHAKEY的软件中。STRIPS的成功,大大推动了规划技术的发展。整个七十年代,规划技术沿着两条主线发展:一个是动作间的次序关系从完全序(即任意两个动作间都有次序)到部分序(允许动作间无次序关系).

第一章引言第二节当前规划研究的若干方向进入九十年代以来,国际上对规划的研究越来越热。每两年一次的 IJCAI会议都有关于规划的专题。另外,从1992年开始,每两年召开一次lConferenceonA.I.PlanningSystems,简称AIPS。前三次会议分别在美国的马里兰大学,芝加哥大学,苏格兰的爱丁堡大学举办.从最近几年的会议文献看,人们研究的兴趣更多地在非经典规划上,也就是说世界知识不能被完全了解,动作产生什么效果不能被完全确定,而且环境可能随时在变化.下面我们简要介绍几个比较新的规划系统。