论文摘要
智能规划是人工智能的重要研究领域之一。1995年Blum和Furst提出了一种基于规划图的快速规划方法——图规划,第一次采用图的方式来解决规划问题,在智能规划领域中取得了革命性进展。灵活图规划(FGP)采用了图规划中图扩张与逆向解搜索结合的求解方式,在此基础上,引入了命题真值度和目标满意度的概念,打破了图规划中严格的约束限制。每个问题中,约束与问题目标各对应一个数值来表示其重要程度,通过这些数值计算出灵活规划的满意度,从而来衡量一个规划的质量优劣。解决问题时,灵活规划器产生满意度不同的多个规划,用户可以根据自己实际情况的需要来选择规划解。但灵活图规划中的动作为瞬时动作,规划器无法处理规划领域定义语言PDDL2.1中所定义的持续操作,即无法产生时序规划。本文提出了路径图和可移动动作的概念,并提出了一种算法,能够解决带有持续动作的灵活规划问题。其基本过程是先通过灵活规划图扩张与逆向解搜索结合的方法求解出由瞬时动作组成的灵活规划解,再从灵活规划图中提取出包含灵活规划解的路径图。通过时序压缩算法对灵活规划解中动作的性质进行分析,找出可移动动作,使此类动作与其它层次动作并行以缩短规划执行时间。同时分析前后层动作之间的关系,为存在因果关系和互斥关系的动作设置时序约束条件。对动作的起止时间进行赋值,使其满足所有约束,从而获得灵活时序规划解。灵活图规划框架下的灵活时序规划算法,拓展了解决问题的范围,具有处理持续动作和生成灵活时序规划的能力,使生成的规划解在时间上更加合理。本文用Java语言在eclipse平台下对算法进行了实现,并对“logistics”域的问题进行了实验,实验结果表明灵活时序规划算法能够比较快速有效地处理持续动作,生成灵活时序规划解。带有持续动作的灵活规划问题得到解决,将使灵活规划问题更加准确地描述及解决现实世界中的问题。灵活图规划是一个较新的研究领域,虽然灵活图规划是国内外研究的热点,但目前国内外还没有关于怎样在灵活规划框架下处理持续动作的研究。所以本文的研究工作在理论上具有很高的学术价值;而且在实际的应用中,也将会有很好的应用前景。