基于与状态无关的激活集的包含派生谓词的规划问题求解

派生谓词是PDDL2．2语言的新特性之一。在2004年的规划大赛IPC-4上，许多规划系统都无法求解包含派生谓词的两个标准竞赛问题。在经典规划中，派生谓词是指不受领域动作直接影响的谓词，它们在当前状态下的真值是在封闭世界假设中由某些基本谓词通过领域公理推导出来的。本文提出一种新的方法来求解包含派生谓词的规划问题，即用与状态无关的激活集来取代派生谓词用于放宽式规划中。     

从规划解中学习一阶派生谓词规则

派生谓词是描述动作非直接效果的主要方式.但是由人类专家设计的派生谓词规则(即领域理论)不能保证总是正确或者完备的,因此有时很难解释一个观察到的规划解为什么是有效的.结合归纳学习与分析学习的优点,文中提出一种称为FODRL(First-Order Derived Rules Learning)的算法,在不完美的初始领域理论的引导下从观察到的规划解中学习一阶派生谓词规则.FODRL基于归纳学习算法FOIL(First-Order Inductive Learning),最主要的改进是可以使用派生谓词的激活集来扩大搜索步,从而提高学习到的规则的精确度.学习过程分为两个步骤:先从规划解中提取训练例,然后学习能够最好拟合训练例和初始领域理论的一阶规则集.在PSR和PROME-LA两个派生规划领域进行实验,结果表明,在大部分情况下FODRL比FOIL(甚至包括其变型算法FOCL)学习到的规则的精确度都要高.     

自动获取派生谓词规划领域的通用规划

通用规划(解)是针对某个领域的像算法一样的规划解,通过对其的解释可以直接得出具体问题的规划解,而不需要调用任何规划系统.但是目前通用规划的提取只能在一些简单或者特殊的领域中进行,没有推广到复杂或者一般的规划领域.该文提出在包含派生谓词的规划领域自动获取通用规划的方法.与已有获取方法不同的是:首先,基于派生谓词规则,文中方法明确指出派生谓词目标与动作效果之间的依赖关系,用以完善通用规划中动作应用的目的;其次,在提取过程中借助角色来帮助识别规划解中的循环结构.实验结果表明,文中方法不仅容易在派生谓词规划领域中获取通用规划,而且还能够以较好的性能求解一类以派生谓词为主要目标的规划"难"题.该文是在派生谓词规划领域中提取通用规划的首创性工作.     

基于多值表示的并行规划方法

Fast Downward规划系统是第四届国际规划竞赛的冠军.以高效的串行规划系统Fast Downward为基础,设计并实现了并行规划系统Parallel Downward.首先提出4个并行规划的相关定义;之后提出多值规划任务下动作互斥的定义、充要条件,并实现了动作互斥判断算法;在此基础上设计了候选并行动作集的生成算法;然后为提高系统求解质量重新设计了新的搜索控制策略;最后,给出剪枝策略来抑制并行规划状态空间的指数级膨胀.通过对国际规划竞赛测试问题的实验,Parallel Downward表现出良好的规划效率和规划质量,相比Sapa规划系统Parallel Downward具有较好的可扩展性.     

基于缩减信念状态的Conformant 规划方法

Conformant 规划问题通常转化为信念状态空间的搜索问题来求解.提出了通过降低信念状态的不确定性来提高规划求解效率的方法.首先给出缩减信念状态的增强爬山算法,在此基础上,提出了基于缩减信念状态的Conformant 规划方法,设计了CFF-Lite 规划系统.该规划器的求解过程包括两次增强爬山过程,分别用于缩减信念状态和搜索目标.首先对初始信念状态作最大程度的缩减,提高启发函数的准确性;然后从缩减后的信念状态开始执行启发式搜索.实验结果表明,CFF-Lite 规划系统通过快速缩减信念状态降低了问题的求解难度,在大多数问题上,求解效率和规划解质量与Conformant-FF 相比,都有显著的提高.     

基于模态逻辑D公理系统的Conformant规划方法

2006年,conformant规划问题成为国际规划竞赛不确定性问题域中的标准测试问题,得到研究人员的广泛关注.目前,conformant规划系统都是将其看成信念状态空间上的启发式搜索问题予以求解.通过分析conformant规划问题的语法和语义,提出新的基于模态逻辑的规划框架.将其转换为模态逻辑D公理系统的一系列定理证明问题.提出2种基于模态逻辑的编码方式.构造相应的公理与推理规则形成模态公式集,保证对于D系统的定理证明过程等同于原问题的规划过程.并通过问题实例验证该方法的有效性.继基于SAT、CSP、线性规划、模型检测等求解技术的规划方法后,该规划框架是基于转换的规划方法的一种新的尝试.     

基于模型检测的领域约束规划

基于模型检测的智能规划是当今通用的智能规划研究的热点,其求解效率比较高.但是,目前基于模型检测的智能规划系统没有考虑到利用领域知识来提高描述能力和求解效率.为此,研究了增加领域约束的基于模型检测的智能规划方法,并据此建立了基于模型检测的领域约束规划系统DCIPS(domain constraints integrated planning system).它主要考虑了领域知识在规划中的应用,将领域知识表示为领域约束添加到规划系统中.根据"规划=动作+状态",DCIPS将领域约束分为3种,即对象约束、过程约束和时序约束,采用对象约束来表达状态中对象之间的关系,采用过程约束来表达动作之间的关系,采用时序约束表达动作与状态中对象之间的关系.通过在2002年智能规划大赛AIPS 2002上关于交通运输领域的3个例子的测试,实验结果表明,利用领域约束的DCIPS可以方便地增加领域知识,更加实用化,其效率也有了相应的提高.     

基于派生谓词的STRIPS领域知识提取策略

领域知识的获取是智能规划研究中的重要内容之一.派生规则是一种基于逻辑推理的领域知识表示方法.在对动作模型和派生规则综合分析的基础上提出了基于派生谓词的STRIPS领域知识提取策略,并给出了该提取策略的算法描述.在规划求解过程中,利用提取所得的领域规则可减少派生规则的逻辑推导,从而提高规划效率.对任意一个规划领域,利用提...     

利用派生谓词和偏好处理OSP 问题的目标效益依赖

在过渡规划问题(over-subscribed planning,简称 OSP)研究中,如果目标之间不是相互独立的,那么目标坚定效益依赖比单个目标效益更能提高规划解的质量.但是,已有的描述模型不符合标准规划描述语言(planning domain descrion language,简称PDDL)的语法规范,不能在一般的OSP规划系统上进行推广,提出了用派生谓词规则和目标偏好描述效益依赖的方法,这二者均为ＰDDL语言的基本要素.实质上,将已有的GAI模型转化为派生谓词规则和目标偏好,其中派生谓词规则显式描述目标子集的存在条件,偏好机制用来表示目标子集的效益,二者缺一不可.该转换算法既可以保持在描述依赖关系时GAI模型的易用性和直观性上,又可以扩展一般的OSP规划系统处理目标效益依赖的能力.从理论上可以证明该算法在转化过程中的语义不变性,子啊基准领域的实验结果表明其可行性和规划解质量的改善能力.提出符合PDDL语言规范的目标效益依赖关系的描述形式,克服了已有模型不通用的缺点.     

在部分观测环境下学习规划领域的派生谓词规则

文中提出了一种在部分观测环境下学习规划领域的派生谓词规则的方法。在规划领域描述语言（PDDL）中,派生谓词用来描述动作的非直接效果,是规划领域模型和搜索控制知识的重要组成部分。然而,对于大多数规划领域而言,从无到有地构造派生谓词规则是不容易的。因此,研究自动获取派生谓词的推导规则是有意义的。已有研究工作提出通过修订一个初始的不完备的领域理论来获取推导规则的方法,但是它们的主要缺点在于待学习谓词的训练例的数量非常少,这是因为训练例按照非常有限的方式来生成。而更本质的原因在于它们假设环境是不可观测的。其实,在现实生活中很多动作的非直接效果是可以观测的,或者通过简单的目测或者通过专门的工具。因此文中提出增加观测来反映动作的非直接效果,以便增加待学习谓词的训练例数目从而改善学习的精准度。此外,为了补充一些在归纳学习过程中学习不到的谓词,文中还提出了一个后处理方法来使得学习到的规则在语义上更完整。通过在派生谓词基准领域上的实验表明,文中所提出的方法是可行有效的。更深远的意义在于,文中的研究工作有利于规划领域的自动建模或者控制知识的自动获取的研究与实现。     

CBPOP: A Domain-Independent Multi-Case Reuse Planner

The reuse of multiple cases to solve a single planning problem presents a promise of better utilization of past experience over single-reuse planning, which can lead to better planning performance. In this paper, we present the theory and implementation of CBPOP, and show how it addresses the multi-reuse planning problems. In particular, we present novel approaches to retrieval and refitting. We also explore the difficult issue of when to retrieve in multi-reuse scenarios, and we empirically compare the results of several solutions we propose. Results from our experiments show that the best ranking function for pure generative planning is not necessarily the best ranking function for multi-reuse planning. The surprising result in the reuse scenarios is that the single-goal case library performed better than larger case libraries consisting of solutions to multi-goal problems.     

A survey on coverage path planning for robotics

Coverage Path Planning (CPP) is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. This task is integral to many robotic applications, such as vacuum cleaning robots, painter robots, autonomous underwater vehicles creating image mosaics, demining robots, lawn mowers, automated harvesters, window cleaners and inspection of complex structures, just to name a few. A considerable body of research has addressed the CPP problem. However, no updated surveys on CPP reflecting recent advances in the field have been presented in the past ten years. In this paper, we present a review of the most successful CPP methods, focusing on the achievements made in the past decade. Furthermore, we discuss reported field applications of the described CPP methods. This work aims to become a starting point for researchers who are initiating their endeavors in CPP. Likewise, this work aims to present a comprehensive review of the recent breakthroughs in the field, providing links to the most interesting and successful works.     

Complete and Rapid Regrasp Planning with Look-up Table

A pick-and-place operation in a 3-dimensional environment is a basic operation for humans and multi-purpose manipulators. However, there may be a difficult problem for such manipulators. Especially, if the object cannot be moved with a single grasp, regrasping, which can be a time-consuming process, should be carried out. Regrasping, given initial and final poses of the target object, is a construction of sequential transition of object poses that are compatible with two poses in the point of grasp configuration. This paper presents a novel approach for solving the regrasp problem. The approach consists of a preprocessing and a planning stage. Preprocessing, which is done only once for a given robot, generates a look-up table which has information on kinematically feasible task space of the end-effector throughout the entire workspace. Then, using this table, the planning automatically determines a possible intermediate location, pose and regrasp sequence leading from the pick-up to put-down grasp. With a redundant robot, it is shown experimentally that the presented method is complete in the entire workspace and can be implemented in real-time applications due to rapid regrasp planning time. The regrasp planner was combined with an existing path.     

Successful strategic information systems planning

Abstract. Strategic information systems planning (SISP) is the process of ensuring alignment between business plans and objectives and information systems plans and objectives and/or the process of identifying information systems which will provide the organization with a competitive edge. This paper distinguishes SISP from both tactical and operational information systems planning, discusses the reasons for management concern with SISP, summarizes problems which may be encountered with the planning process and resultant plant implementation and then focuses on the issue of SISP success. Specifically, success is considered not only in terms of how it may be achieved but also in terms of how it can be defined (i.e. what constitutes SISP success) and how SISP success can be measured. Specific research questions addressing the measurement of SISP success are identified.     

A privacy-preserving model for multi-agent propositional planning

Abstract

Over the last years, the planning community has formalised several models and approaches to multi-agent (MA) propositional planning. One of the main motivations in MA planning is that some or all agents have private knowledge that cannot be communicated to other agents during the planning process and the plan execution. We argue that the existing models of the multi-agent planning task do not maintain the agents’ privacy when a (strict) subset of the involved agents share confidential knowledge, or when the identity/existence of at least one agent is confidential. In this paper, first we propose a model of the MA-planning tasks that preserves the privacy of the involved agents when this happens. Then we investigate an algorithm based on best first search for our model that uses some new heuristics providing a trade-off between accuracy and agents’ privacy. Finally, an experimental study compares the effectiveness of using the proposed heuristics.     

不确定可逆规划的强循环规划解

动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束:1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.     

Information systems planning: Lessons from strategic planning

IS planning has changed considerably since its inception as an operational planning tool, expanding its scope to address key business objectives and forging a link with strategic business planning. A great deal of attention is currently focused on identifying and developing strategic information systems. Strategic planning has also become more broadly-focused over time, as simple forecasting techniques have been replaced by a variety of adaptive approaches that emphasize industry structure analysis and environmental dynamics. However, strategic planning has come under fire recently for failing to live up to its promises. As these two disciplines become more closely aligned, planners can learn from the experiences of strategic planners and, hopefully, avoid a similar crisis of confidence.     

Optimum motion planning in joint space for robots using genetic algorithms

The optimum motion planning in joint space (OMPJS) for robots, which generally consists of two subproblems, optimum path planning and optimum trajectory planning, was considered as a whole in the paper. A new method for optimum motion planning problem based on an improved genetic algorithm is proposed, which is more general, flexible and effective. This approach incorporates kinematics constraints, dynamics constraints, and control constraints of robotic manipulator. The simulation results for a two and a three degrees of freedom robots are presented and discussed. The simulations are based on genetic algorithm class library WGAClass 1.0 developed by us with Borland C++ 3.1.     

分层法求强循环规划解

设计了一种求解强循环规划问题的状态分层算法。从目标状态开始,首先进行强规划分层,然后对剩余状态进行弱规划分层,并记录相应信息,最后用该信息作启发因子,在弱规划分层结果中搜索强循环规划分层。分层结束后利用分层时记录的信息可以直接得到强循环规划解。所设计的算法在求解状态动作较多的强循环规划问题时有较高的效率;且当强规划解存在时,求解效率更高,并能保证得到质量更优的强循环规划解——强规划解。实验表明,所设计的算法能够以较少的重复搜索得到强循环规划解,求解效率比反向搜索高。     

领域知识优化的蚁群规划算法

在智能规划领域的传统图规划算法中,规划解的提取是从规划图的最后一层不断向前提取。提取过程中要不断进行大量状态互斥判断。提取过程中一旦发生失败就要回溯,即使再遇到相同的互斥情形也要重新计算,大量判断互斥的计算被带入主循环搜索过程,极大地影响了搜索效率。将领域知识通过禁忌连接集的形式加入蚁群规划算法中,相邻动作层的很多互斥信息通过禁忌连接集只需计算一次,不带入主循环计算中,可以较好地提升算法的执行效率,实例分析表明这一策略是有效的。