分层法求最小权值强规划解

在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。     

一种快速求强规划解的算法

为提高求解效率,设计一种求强规划解的简化分层算法。以传统分层算法为基础,引入贪心选择策略,对每个非目标状态的动作进行筛选,去除对求解强规划解无益的动作,加快状态向下搜索的速度,并在改进分层的基础上,优化求强规划解策略,由于在求解过程中会存在大量重复搜索,因此建立一个集合保存已访问状态的信息,避免对状态的重复搜索。分析结果表明,在初始状态到达目标状态路径都不重合的情况下,改进算法的时间复杂度为O( nm)( n为初始状态个数,m为层数),在都重合情况下为O( m),优于普通正向搜索算法与反向搜索算法。     

求强规划解的快速状态分层算法

在求强规划解时,通过状态分层可以大幅减少问题规模,提高搜索效率,并能得到规划路径较短的强规划解。但现有分层算法本身有一定的复杂度,在状态较多时开销较大。为此,通过改进已有分层算法,设计一种适用于求强规划解的快速状态分层算法。采用链式双向图结构保存数据,在分层时修改已遍历的状态动作序偶,并根据修改结果直接进行分层判断,使得分层时只需要判断前一层状态而不是所有已分层状态,避免对非必要状态转移的搜索以及对必要状态转移的重复搜索。实验结果表明,该算法的分层速度优于已有的矩阵乘分层算法。     

模型检测规划中的状态分层方法

基于模型检测的规划方法是最近发展起来的新方法,它可以处理带有不确定性的规划问题.分别设计了对求弱规划解、强规划解和强循环规划解的问题中的状态进行分层的方法.状态被分层后,求规划解只需要在从上层到其下一层状态之间寻找状态动作序偶就可以了,其他状态动作序偶都可以去掉.分别获得了求弱规划解、强规划解和强循环规划解时状态被分层后的一些重要性质,这些性质是关于一些状态动作序偶是否可以不参与构成弱规划解、强规划解和强循环规划解的结论.通过所获得的性质可以将大量的状态动作序偶直接去掉,从而减少问题规模.以往的对基于模型检测规划的研究都是采用从目标状态开始的反向搜索方法,在状态被分层以后可以采用正向搜索技术展开相应的研究.     

正向搜索方法求强规划解

以规划领域中的不确定状态转移系统作为研究对象,设计了求强规划解问题中的状态分层方法,状态被分层以后,求强规划解只需要从初始状态出发,逐次向下层状态转移到目标状态就可以了,在此基础上,设计了用正向搜索方法求强规划解的算法。实验结果表明：所设计的算法比用反向搜索方法求强规划解算法的效率高。     

不确定规划中的多Agent带权值强规化算法

在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。     

多agent规划领域中的观察信息约简

观察信息约减是近年来不确定规划中的研究热点,但研究集中于单个agent的环境,在多agent规划环境下的研究不足。面对多agent环境下的规划问题,设计了一种用于不确定规划领域中多agent求解协同规划解的ORMAP算法。该算法首先根据基于模型检测的不定规划中的状态分层思想,将问题领域的所有状态进行分层,以此来减少不同的agent的冲突,再利用以最小代价优先的回溯法搜索协同规划解,同时在解的搜索过程中选择最小的观察信息集,使求出的协同规划解在众多符合条件的协同规划解中所需要的观察信息最少或接近最少,这样就达到了信息约简的目的。最后通过实验证明,在考虑了观察信息约简的限制条件后,这种算法的效率较高。     

不确定规划中状态循环可达关系的求解方法

在不确定规划领域中, 不确定状态转移系统求规划解常常会搜索大量无用的状态和动作, 造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算, 为系统提供引导信息。以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了求循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系, 在求规划解的过程中可以删除大量无用的状态动作序偶, 降低问题规模, 提高求解规划问题的效率。     

一种求解最小权值强规划的方法

以规划领域中的不确定状态转移系统作为研究对象,给出最小权值强规划解的概念,提出一种求最小权值强规划解的方法.该方法可以求解与动作代价相关的数值规划问题,在不确定状态转移系统的执行动作上增加权值来表示动作的代价,在此基础上设计求解最小权值强规划解的算法.实验结果表明,该算法能有效求解最小权值强规划解,且比用反向搜索方法求...     

确定树求强规划解

定义了确定树,设计了求确定树的方法。基于该方法设计了求强规划解的算法,找到每个初始状态对应的确定树,在找到确定树之后,求强规划解不需要从目标状态一直搜索到初始状态,只需要从目标状态反向找到确定树的任意一个节点,再通过这个节点在确定树中反向搜索到初始状态从而得到一个强规划解。实验结果表明：所设计的算法比用反向搜索方法求强规划解的算法的效率高。     

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.     

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.     

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.     

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

动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束: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.     

过度规划、部分可满足规划及简单偏好综述*

智能规划是人工智能的重要分支,它从某个特定问题的初始状态出发,寻找达到解决该问题的目标状态的动作序列,但是在许多真实问题中,往往没有足够的资源来实现所有目标。因此,智能规划中对软目标的研究包括过度规划、部分可满足规划和简单偏好,已成为近年来的热点。将对过度规划、部分可满足规划和简单偏好的主要研究成果进行综述,包括这几类问题的差异比较、主要解决方案以及对将来的展望。