智能规划中子目标排序关系的评价机制与提取方法研究

Subgoal ordering is to recognize and describe the achievement orderings among subgoals in planning problems, so as to construct global or local orderings of subgoals. The problem is of great theoretical significance and practice value to solve large-scale complicated planning problems. It has broadly been applied in planning problem decomposition, heuristic derivation, heuristic search algorithms, and so on. Existing research on the one hand restricts to the STRIPS planning model and is lack of effective approach to classification and evaluation on the other. This project plans to study theoretic evaluation model of subgoal ordering and extension of ordering extraction in non-STRIPS framework. We analyze the theory properties and classification criterion of subgoal ordering, and establish its theoretic evaluation criterions. We then extend the formalized definitions of subgoal ordering in non-STRIPS framework and design effective extraction algorithms. Typical prototypes of subgoal ordering will be provided to show performance of the proposed approaches.

子目标排序指的是对规划问题子目标之间存在的顺序实现关系进行识别和描述，进而构造子目标之间的全局或局部顺序关系。该问题对求解大规模复杂规划问题具有重要理论意义和应用价值，已广泛运用在规划问题分解、启发式构造、启发式搜索算法中。已有研究一方面主要局限于STRIPS规划模型下的子目标排序关系，另一方面缺乏有效方法对子目标排序关系进行分类与评价。本课题拟围绕子目标排序关系的理论评价模型、子目标排序关系的提取与扩展方法等内容展开研究。分析子目标排序关系的理论性质和分类准则，建立评价子目标排序关系的理论评价模型；扩展子目标排序关系在非STRIPS模型下的形式化定义，设计有效的算法提取子目标排序关系；根据子目标排序关系的特点，研发子目标排序关系的典型应用。本课题将为研究和提取新的子目标排序关系提供理论依据和方法论指导，并为深入应用子目标排序关系提供决策依据。

大规模复杂规划问题的主要特征是其搜索空间非常庞大，致使规划求解异常困难。子目标排序是一种采用离线方法分解规划问题的有效手段，通过对规划问题子目标之间存在的顺序实现关系进行识别和描述，进而构造子目标之间的全局或局部顺序关系，对求解大规模复杂规划问题具有重要理论意义和应用价值。本课题围绕子目标排序关系的理论评价模型、子目标排序关系的提取与扩展方法、智能体路径规划、仿人机器人步态规划等方面展开研究并取得如下的研究成果：1). 提出了ADL模型下可纳排序关系的形式化定义，并提出了一种有效的算法提取ADL模型下的可纳排序关系；优化了判定任意子目标原子之间是否存在非依赖关系/可纳关系的算法和代码，提高了算法效率。2). 提出了评价子目标排序关系的关键性质和理论模型，从而可以从正确性、最优性/次优性等方面有效评价和分析各种子目标排序关系的特点；针对FDR规划表示，提出了基于FDR规划表示的子目标排序关系。3). 相继开发了ASOP2.0（可处理二元变量表示的ADL规划问题的可纳排序关系）和ASOP-FDR（可处理FDR表示的多种类型的规划问题）。完整测试了1998年IPC-1到2014年IPC-8的全部STRIPS规划领域，实验结果表明，我们在大部分规划领域提取到子目标排序关系并改进了规划性能，在很多领域其性能提升达到2-3个数量级。4). 改进了自适应遗传算法应用于自治智能体动态路径规划，提出了新的交叉概率和变异概率调节公式。克服了传统遗传算法和一般自适应遗传算法的早熟收敛问题，提高了进化效率，在收敛速度和输出全局最优解的概率上都有较明显的提高。5). 提出了一种新的仿人机器人参数化跑步步态优化方法。将机器人步态优化问题转化为对步态参数的多目标寻优问题，采用基于对位学习的遗传算法对机器人参数化跑步步态进行多目标寻优，有效降低能耗并保证其稳定性。.本课题将为研究和提取新的子目标排序关系提供理论依据和方法论指导，并为深入应用子目标排序关系提供决策依据。