不确定层次任务网络规划研究综述

层次任务网络(Hierarchical task network, HTN)规划作为一项重要的智能规划技术被广泛应用于实际规划问题中, 传统的HTN规划无法处理不确定规划问题.然而, 现实世界不可避免地存在无法确定或无法预测的信息, 这使许多学者开始关注不确定规划问题, 不确定HTN规划研究也成为HTN规划研究的前沿.本文从HTN规划过程出发分析了不确定HTN规划问题中涉及的三类不确定, 即状态不确定、动作效果不确定和任务分解不确定; 总结了系统状态、动作效果和任务分解等不确定需要扩展确定性HTN规划模型的工作, 以此对现有不确定HTN规划的研究工作加以梳理和归类; 最后,对不确定HTN规划研究中仍需要解决的问题和未来的研究方向作了进一步展望.     

一种利用工作流模型的分层任务网络规划领域建模方法

为了有效地获取和利用领域知识,提高规划效率,分析了工作流模型和分层任务网络(HTN)规划领域模型的相似性,提出了一种采用工作流模型进行规划领域建模,对领域知识进行获取和表达的方法.工作流模型中的行动和工作流模式,转换为HTN规划中的行动和任务分解;另外,引入了循环(Loop)工作流模式,转换为HTN规划中的递归调用,扩展了工作流模式对规划领域知识的表达能力.在典型的几个规划领域中,引入领域知识后大大提高了规划器的求解效率,从而验证了应用工作流模型进行规划领域建模的有效性.     

FPS游戏中基于HTN的Anytime规划器的研究

动态性和实时性电脑游戏世界的两个关键特征。Anytime规划是能够产生满足上述两个特征的行为的规划方法。分层任务网络（Hierarchical Task Network,HTN）是表示分层规划的一种形式,它非常适合于表达电脑游戏中非玩家角色（non-player character,NPC）复杂的目标。以著名的第一人称射击（First-Person Shooter,FPS）游戏虚幻竞技场2004（Unreal Tournament 2004）作为游戏平台,为NPC设计实现了一个基于HTN规划的anytime规划器,并使用遗传算法调整规划目标的优先级。该规划器可以根据环境变化随时中断规划并给出可用的规划结果,同时具有一定的适应性。实验表明它能够使NPC的行为更智能。     

基于HTN的供应链优化策略

HTN(Hierarchical Task Network，层次任务网络)具有任务描述和分解、任务分派、任务完成的能力以及约束机制和冲突解决机制，可以高效地对复杂问题进行规划。文章就HTN在供应链优化中的应用进行了初步地探讨，结合多代理系统，针对供应链库存管理业务提出其任务网络模型，指出任务分解方法及共约束关系和任务在代理间的分派关系，并给出应用实例。     

规划的形式表示技术研究

智能规划是人工智能研究领域中的一个富有挑战性的课题.同时,智能规划问题具有广泛的实际应用背景.而自动规划问题面临的首要问题是规划问题的形式表示问题.本文系统地分析了情景演算,STRIPS,PDDL,HTN等各种规划形式表示技术,比较了各种形式表示技术的优缺点,并指出了进一步研究设计高效智能规划系统的方向.     

基于OWL-S和HTN的Web服务组合原型系统的研究

Web服务是近年发展的一种分布式技术,引起了越来越多研究者的关注.随着网络上Web服务技术描述的信息系统数量的不断增加,将现有的业务流程进行组合以满足较为复杂的业务系统成为当前发展的主要趋势.此外,由于Web服务所处环境的复杂性和动态性,使得Web服务组合任务变得非常困难.因此,Web服务组合逐渐成为语义Web服务领域研究的热点和难点.描述了一个基于OWL-S和HTN的Web服务组合框架,并详细介绍了如何利用HTN规划解决Web服务组合问题的算法思想.通过学生选课服务实验,验证了该方法的可行性.     

基于预案模板的HTN规划知识建模方法及其应用

应急决策是应急管理的基础和核心,H TN( Hierarchy Mask Nct)规划为应急决策提供了一种有效手段,是目前研究的热点问题。针对基于HTN规划求解应急决策问题存在领域知识难于建模的问题,在利用基于PetriNet的工作流模型对应急预案进行建模的基础上,提出了一种将预案模板转化为H`I'N规划领域知识模型的方法。在此基础上,将基于预案模板的应急决策问题建模为应急任务规划问题,利用HTN规划系统SHOP2 (Simple Hierarchical Ordered Planner 2)进行规划求解,实现复杂应急态势条件下通过选择和组织应急计划片段科学制定应对方案,并以某区域洪灾应急响应为例开展了应用研究。     

基于OWL—S和HTN的Web服务组合原型系统的研究

Web服务是近年发展的一种分布式技术,引起了越来越多研究者的关注。随着网络上Web服务技术描述的信息系统数量的不断增加,将现有的业务流程进行组合以满足较为复杂的业务系统成为当前发展的主要趋势。此外,由于Web服务所处环境的复杂性和动态性,使得Web服务组合任务变得非常困难。因此,Web服务组合逐渐成为语义Web服务领域研究的热点和难点。描述了一个基于OWL—S和HTN的Web服务组合框架,并详细介绍了如何利用HTN规划解决Web服务组合问题的算法思想。通过学生选课服务实验,验证了该方法的可行性。     

星地一体化路由规划建模及仿真

针对目前在星地信息传输中全局路由规划不合理及其引起的传输大时延等问题,通过考虑星地资源的优化利用及地面网络拥塞状态,提出全局优化技术给出较佳的路由策略.根据一体化的全局规划方案及树形搜索算法,由于考虑了卫星与接收站的资源可利用状态和整个地面网络的通信负载状态,建立符合实际需求的一体化路由规划模型.仿真结果表明,给出较佳的一体化传输路由,保证从卫星到接收站到处理中心能进行实时的信息传输.证明建立的模型能得出次优的规划方案,可在网络突发状况下应急使用,具有较强的适应能力.     

基于SOS技术的多项式非线性系统鲁棒控制综合

针对一类具有多项式向量场的仿射不确定非线性系统,借助多项式平方和(Sum of Squares, SOS)技术,研究其状态反馈鲁棒控制综合问题。给出了该类系统鲁棒镇定控制、以及带有保性能和H性能目标的优化控制问题的充分可解性条件。所给出的条件均被描述为由状态依赖线性矩阵不等式(LMI)组成的SOS规划,可由SOS技术直接求解。此外,通过引入附加变量给出了描述多项式矩阵的逆以及有理式矩阵的方法。最后,通过数值仿真验证了方法的有效性     

Learning Hierarchical Task Models from Input Traces

We describe HTN‐MAKER , an algorithm for learning hierarchical planning knowledge in the form of task‐reduction methods for hierarchical task networks (HTNs). HTN‐MAKER takes as input a set of planning states from a classical planning domain and plans that are applicable to those states, as well as a set of semantically annotated tasks to be accomplished. The algorithm analyzes this semantic information to determine which portion of the input plans accomplishes a particular task and constructs task‐reduction methods based on those analyses. We present theoretical results showing that HTN‐MAKER is sound and complete. Our experiments in five well‐known planning domains confirm the theoretical results and demonstrate convergence toward a set of HTN methods that can be used to solve any problem expressible as a classical planning problem in that domain, relative to a set of goal types for which tasks have been defined. In three of the five domains, HTN planning with the learned methods scales much better than a modern classical planner.     

BioDKM: Bio-inspired domain knowledge modeling method for humanoid delivery robots’ planning

A bio-inspired human domain knowledge modeling method, BioDKM, is proposed and developed to make delivery robots think more humanly and act more effectively. This presented method focused on feasible fusion between artificial intelligent and bionics in the field of tasks planning or scheduling in delivery robots. BioDKM is designed and implemented with several components, in terms of human knowledge, workflow (WF), hierarchical task network (HTN), and planner. In detail, WF is utilized as the human domain knowledge modeling tool, because of its convenient applications, friendly user interface and explicit representation. Moreover, WF can effectively complement conventional HTN planning with great convenience to formalize human domain knowledge. Translation from WF to HTN is also considered and established to make task planning smooth. Finally, examples and simulations are carried out to validate the effectiveness of this proposed bio-inspired domain knowledge modeling method.     

Complexity results for HTN planning

Most practical work on AI planning systems during the last fifteen years has been based on Hierarchical Task Network (HTN) decomposition, but until now, there has been very little analytical work on the properties of HTN planners. This paper describes how the complexity of HTN planning varies with various conditions on the task networks, and how it compares to STRIPS-style planning.This work was supported in part by NSF Grant NSFD CDR-88003012 to the Institute for Systems Research, and NSF grant IRI9306580 and ONR grant N00014-91-J-1451 to the Computer Science Department.     

Automatic generation of temporal planning domains for e-learning problems

AI Planning & Scheduling techniques are being widely used to adapt learning paths to the special features and needs of students both in distance learning and lifelong learning environments. However, instructors strongly rely on Planning & Scheduling experts to encode and review the domains for the planner/scheduler to work. This paper presents an approach to automatically extract a fully operational HTN planning domain and problem from a learning objects repository without requiring the intervention of any planning expert, and thus enabling an easier adoption of this technology in practice. The results of a real experiment with a small group of students within an e-Learning private company in Spain are also shown.     

A resource enhanced HTN planning approach for emergency decision-making

Hierarchical resource reasoning is one of the key issues to successfully apply Hierarchy Task Network (HTN) planning into emergency decision-making. This paper proposes a Resource Enhanced HTN (REHTN) planning approach for emergency decision-making with the objective to enhance the expressive power and improve the processing speed of hierarchical resource reasoning. In the approach, resource timelines are defined to describe various resource variables and constraints. Top-down resource reasoning is used for decomposing the resource constraints of upper-level tasks into those of lower-level tasks. Meanwhile, resource and temporal constraints of tasks in different branches are processed by causal links. After the tasks are decomposed into primitive tasks, resource profiles of consumable resources and reusable resources are checked by separate resource allocation processes. Furthermore, a constraint propagation accelerator is designed to speed up hierarchal resource reasoning. The effectiveness and practicability of REHTN are confirmed with some experiments from emergency logistics distribution problems.