STRIPS规划领域中动作效果关系的研究

以规划领域中的动作为研究对象,提出了描述动作前提条件和效果之间关系的方法,定义了动作前提和效果之间的基本关系:直接伴随关系、条件伴随关系和直接阻碍关系等,这些基本关系反映了规划动作中所隐含的领域知识.对动作效果的基本关系,定义了进行关系组合的运算,产生出间接阻碍关系和绝对阻碍关系.间接阻碍关系反映出动作前提条件的传递性;绝对阻碍关系表达出实现一个谓词对其他谓词实现的影响.最后给出动作效果关系在规划求解过程中的具体运用,这些动作效果关系为目标实现顺序的排序、目标状态可解性的判定以及动作选择策略的优化等提供了必要的理论依据.     

在部分观测环境下的不确定动作模型学习

近年来,动作模型学习引起了研究人员的极大兴趣.可是,尽管不确定规划已经研究了十几年,动作模型学习的研究仍然集中于经典的确定性动作模型上.提出了在部分观测环境下学习不确定动作模型的算法,该算法可应用于假定人们对转移系统一无所知的情形下进行,输入只有动作-观测序列.在现实世界中,这样的场景很常见.致力于动作是由简单逻辑结构组成的、且观测以一定频率出现的一类问题的研究.学习过程分为3个步骤：首先,计算命题在状态中成立的概率;然后,将命题抽取成效果模式,再抽取前提;最后,对效果模式进行聚类以去除冗余.在基准领域上进行的实验结果表明,动作模型学习技术可推广到不确定的部分观测环境中.     

An Approach for Merging Plans Hierarchically in Decomposable Domains

Recent works in domain‐independent plan merging have shown that the optimal plan‐merging problem is NP-hard, and heuristic algorithms have been proposed to generate near‐optimal solutions. These works have shown heuristic algorithms which assume that the mergeability of two actions can be determined by considering only the actions themselves. In this paper, we show that it is often that case that the surrounding actions in the plan must also be considered when determining the mergeability of two or more actions; therefore, the context in which the actions are used affects their mergeability. To address this problem, we have developed a plan-merging methodology that merges partial-order plans based on the the notion of plan fragments, which encapsulate actions with the context in which they are being utilized. This methodology applies to a class of planning domains, called decomposable domains, which consist of actions that follow all or some portion of a type sequence. Merging is performed hierarchically by action type. We also investigate the previously unexplored notion of alternative actions in domain-independent plan merging, which can improve the quality of the resulting merged plan. A novel approach is presented for removing cyclic dependencies that may occur during the plan-merging process.
A key part of the methodology is the computation of a minimum cost cover of plan fragments. We provide theoretical analyses of two optimal algorithms and a greedy-based algorithm for computing the minimum cost cover. We support the theoretical analysis of these algorithms with experimental data to show that the greedy approach is near-optimal and efficient.     

A simplified problem reduction format

Some new approaches to mechanical theorem proving in the first-order predicate calculus are presented. These are based on a natural deduction system which can be used to show that a set of clauses is inconsistent. This natural deduction system distinguishes positive from negative literals and treats clauses having 0, 1, and 2 or more positive literals in three separate ways. Several such systems are presented. The systems are complete and relatively simple and allow a goal to be decomposed into subgoals, and solutions to the subgoals can then be searched for in the same way. Also, the systems permit a natural use of semantic information to delete unachievable subgoals. The goal-subgoal structure of these systems should allow much of the current artificial intelligence methodology to be applied to mechanical theorem proving.     

Localized event-based reasoning for multiagent domain1

This paper presents the GEM concurrency model and GEMPLAN, a multiagent planner based on this model. Unlike standard state-based AI representations, GEM is unique in its explicit emphasis on events and domain structure. In particular, a world domain is modeled as a set of regions composed of interrelated events. Event-based temporal-logic constraints are then associated with each region to delimit legal domain behavior. The GEMPLAN planner directly reflects this emphasis on domain structure and constraints. It can be viewed as a general-purpose constraint satisfaction facility which constructs a network of interrelated events (a “plan”) that is subdivided into regions (“subplans”), satisfies all applicable regional constraints, and also achieves some stated goal. GEMPLAN extends and generalizes previous planning architectures in the range of constraint forms it handles and in the flexibility of its constraint satisfaction search strategy. One critical aspect of our work has been an emphasis on localized reasoning—techniques that make explicit use of domain structure. For example, GEM localizes the applicability of domain constraints and imposes additional “locality constraints” on the basis of domain structure. Together, constraint localization and locality constraints provide semantic information that can be used to alleviate several aspects of the frame problem for multiagent domains. The GEMPLAN planner reflects the use of locality by subdividing its constraint satisfaction search space into regional planning search spaces. Utilizing constraint and property localization, GEMPLAN can pinpoint and rectify interactions among these regional search spaces, thus reducing the burden of “interaction analysis” ubiquitous to most planning systems. Because GEMPLAN is specifically geared towards parallel, multiagent domains, we believe that its natural application areas will include scheduling and other forms of organizational coordination.     

A heuristic technique for multi‐agent planning

The subject of multi‐agent planning has been of continuing concern in Distributed Artificial Intelligence (DAI). In this paper, we suggest an approach to multi‐agent planning that contains heuristic elements. Our method makes use of subgoals, and derived sub‐plans, to construct a global plan. Agents solve their individual sub‐plans, which are then merged into a global plan. The suggested approach reduces overall planning time and derives a plan that approximates the optimal global plan that would have been derived by a central planner, given those original subgoals. We explore three different scenarios. The first involves a group of agents with a common goal. The second considers how agents can interleave planning and execution when planning towards a common, though dynamic, goal. The third examines the case where agents, each with their own goal, can plan together to reach a state in consensus for the group. Finally, we consider how these approaches can be adapted to handle rational, manipulative agents. This revised version was published online in June 2006 with corrections to the Cover Date.     

动态描述逻辑的Tableau判定算法

动态描述逻辑在描述逻辑的基础上引入了动态维,用于描述和推理动态领域的知识,但目前缺少有效的判定算法作为支撑.文中以描述逻辑ALCO的动态扩展为例,构建出动态描述逻辑D-ALCO.以D-ALCO的构建过程为基础,将ALCO的Tableau算法、命题动态逻辑的Tableau算法以及对可能模型途径的处理有机地结合起来,给出了D-ALCO的Tableau判定算法,证明了算法的可终止性、可靠性和完备性.应用该算法,可以在采用开世界假设的情况下对D-ALCO中公式的可满足性进行判定.对于D-ALCQO、D-ALCQIO等具有更强描述能力的动态描述逻辑,可以对该算法扩展后得到相应的Tableau判定算法.     

A planning model with problem analysis and operator hierarchy

A planning model described in terms of its goal analysis and hierarchical operator representation is presented. With this system, successful plans have been made for nonlinear problems that are described as a conjunction of subgoals. The system uses heuristic rules to analyze the problem, and thus achieves an ordered sequence of subgoals and constraints that can be achieved successively without interfering with each other. The operators are designed in a goal-oriented fashion and are stored in operator hierarchies. During the plan generation phase, each subgoal is mapped into a goal operator, which is further refined to meet details and specific conditions of the problem. As the generation phase follows the analysis, conflicts among subgoals are eliminated implicitly     

Improving concurrency in temporal plans

There is an increasing interest in solving temporal planning problems. Identification and propagation of mutual exclusion relations between actions can significantly enhance the efficiency of a planner. Current definitions of mutually exclusive actions severely restrict their concurrency. In this paper, we report on thirteen groups of permanently mutually exclusive PDDL 2.1, Level 3 actions. We report on sixteen types of potentially-conflicting interactions between two actions where concurrency may be maximized by adjusting starting time of one of the two actions. We discuss several examples where actions can overlap despite conflicting preconditions and/or effects. The processes executing these actions are mostly independent. We report on a new domain-rewriting technique called “baiting” in order to improve the concurrency in temporal plans. Baiting actions lure a temporal planner into improving concurrency. The technique involves splitting user-identified operators. We report on three types of baiting (standard, double and nested) and show their suitability for various types of action interactions. Baiting requires minimal modification to the planning code. Baiting does not increase the branching in search trees. Baiting does not affect the soundness and completeness of a temporal planner. Our empirical evaluation shows that the makespans of plans generated by efficient planner Sapa with baited domain are significantly lower than makespans of plans generated without baiting.     

智能规划中的可纳子目标排序

提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能.     

IPSS: A Hybrid Approach to Planning and Scheduling Integration

Recently, the areas of planning and scheduling in artificial intelligence (AI) have witnessed a big push toward their integration in order to solve complex problems. These problems require both reasoning on which actions are to be performed as well as their precedence constraints (planning) and the reasoning with respect to temporal constraints (e.g., duration, precedence, and deadline); those actions should satisfy the resources they use (scheduling). This paper describes IPSS (integrated planning and scheduling system), a domain independent solver that integrates an AI planner that synthesizes courses of actions with constraint-based techniques that reason based upon time and resources. IPSS is able to manage not only simple precedence constraints, but also more complex temporal requirements (as the Allen primitives) and multicapacity resource usage/consumption. The solver is evaluated against a set of problems characterized by the use of multiple agents (or multiple resources) that have to perform tasks with some temporal restrictions in the order of the tasks or some constraints in the availability of the resources. Experiments show how the integrated reasoning approach improves plan parallelism and gains better makespans than some state-of-the-art planners where multiple agents are represented as additional fluents in the problem operators. It also shows that IPSS is suitable for solving real domains (i.e., workflow problems) because it is able to impose temporal windows on the goals or set a maximum makespan, features that most of the planners do not yet incorporate     

Action dependencies in privacy-preserving multi-agent planning

Collaborative privacy-preserving planning (CPPP) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information. In many CPPP algorithms, the individual agents reason about a projection of the multi-agent problem onto a single-agent classical planning problem. For example, an agent can plan as if it controls the public actions of other agents, ignoring any private preconditions and effects theses actions may have, and use the cost of this plan as a heuristic estimate of the cost of the full, multi-agent plan. Using such a projection, however, ignores some dependencies between agents’ public actions. In particular, it does not contain dependencies between public actions of other agents caused by their private facts. We propose a projection in which these private dependencies are maintained. The benefit of our dependency-preserving projection is demonstrated by using it to produce high-level plans in a new privacy-preserving planner, and as a heuristic for guiding forward search privacy-preserving algorithms. Both are able to solve more benchmark problems than any other state-of-the-art privacy-preserving planner. This more informed projection does not explicitly expose any private fact, action, or precondition. In addition, we show that even if an adversary agent knows that an agent has some private objects of a given type (e.g., trucks), it cannot infer the number of such private objects that the agent controls. This introduces a novel form of strong privacy, which we call object-cardinality privacy, that is motivated by real-world requirements.     

GP——基于规划图的遗传规划算法

图规划是智能规划领域近年来出现的一种新的规划方法,对智能规划的发展有着重要的影响.图规划的规划产生过程分为两个主要步骤,首先用动作的前提条件和效果产生一个谓词和动作交错出现的图--规划图,然后在规划图中抽取规划解.而第二步往往更为困难和耗时.文章依据遗传算法对规划图提出一种新的解抽取方法,以一种简明、直观的形式给出染色体的编码方式,并在此基础上定义了各种遗传操作算子,将遗传算法引入图规划算法,充分利用遗传算法的并行全局搜索能力实现规划解的搜索.实验表明,在求解大规模的规划问题时,文中的遗传规划算法在求解速度和找到的规划解的质量两方面均显示出优越性.     

Real time planning in N-dim state space

This paper presents the actual work in real-time planning as search [1] [2]. Based in this work we tried to solve the path planning in numerical state space. We found that precision, performance, and time were very linked. In real-time problem solving, the agent can fall in traps made of forbidden zones and to go out it, have to spend too much computing time. To solve this problem we propose a multilayer inference based in subgoals computation. An architecture based in two agents, one for low level task with the maximum precision and other for subgoals computation is proposed here.     

部分观测环境下的时态动作模型学习方法

已有的动作模型学习方法针对确定的或不确定的瞬时动作，而未考虑动作模型中的时态关系。提出了在部分观测环境下自动学习时态动作模型的方法。设计了学习动作持续时间表达式一般形式的两阶段线性回归方法。通过分析命题时间戳设计了动作前提、效果与动作之间时态关系算子的构建算法。在“国际智能规划竞赛”的规划问题集上进行了实验，结果表明了该方法的有效性。     

Learning and plan refinement in a knowledge-based system for automatic speech recognition

This paper shows how a semiautomatic design of a speech recognition system can be done as a planning activity. Recognition performances are used for deciding plan refinement. Inductive learning is performed for setting action preconditions. Experimental results in the recognition of connected letters spoken by 100 speakers are presented.     

Planning with Multistep Forward Search with Forced Goal‐Ordering Constraints

To solve a real‐world planning problem with interfering subgoals, it is essential to perform early detection of subgoal dependencies and achieve the subgoals in the correct order. This is also the case for planning problems with forced goal‐ordering (FGO) constraints. In automated planning, forward search with FGO constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. Many existing methods such as goal agenda manager and ordered landmarks cannot detect the FGOs accurately, and thus, the undiscovered ordering relationship may cause the forward search to suffer from deadlocks. In this article, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the FGOs. We make use of an atomic goal‐achievement graph in a look‐ahead search under the FGO constraints. This allows a forward search strategy to plan forward efficiently in multiple steps toward a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches. We also prove several formal properties for search that are related to FGO detection.