MERGING SEPARATELY GENERATED PLANS WITH RESTRICTED INTERACTIONS

Generating action sequences to achieve a set of goals is a computationally difficult task. When multiple goals are present, the problem is even worse. Although many solutions to this problem have been discussed in the literature, practical solutions focus on the use of restricted mechanisms for planning or the application of domain dependent heuristics for providing rapid solutions (i.e., domain-dependent planning). One previously proposed technique for handling multiple goals efficiently is to design a planner or even a set of planners (usually domain-dependent) that can be used to generate separate plans for each goal. The outputs are typically either restricted to be independent and then concatenated into a single global plan, or else they are merged together using complex heuristic techniques. In this paper we explore a set of limitations, less restrictive than the assumption of independence, that still allow for the efficient merging of separate plans using straightforward algorithmic techniques.
In particular, we demonstrate that for cases where separate plans can be individually generated, we can define a set of limitations on the allowable interactions between goals that allow efficient plan merging to occur. We propose a set of restrictions that are satisfied across a significant class of planning domains. We present algorithms that are efficient for special cases of multiple plan merging, propose a heuristic search algorithm that performs well in a more general case (where alternative partially ordered plans have been generated for each goal), and describe an empirical study that demonstrates the efficiency of this search algorithm.     

Coordinating Self-interested Planning Agents

We consider planning problems where a number of non-cooperative agents have to work on a joint problem. Such problems consist in completing a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. Since the agents are non-cooperative, they insist on planning independently and do not want to revise their individual plans when the joint plan has to be assembled from the individual plans. We present a general formal framework to study some computational aspects of this non-cooperative coordination problem and we establish some complexity results to identify some of the factors that contribute to the complexity of this problem. Finally, we illustrate our approach with an application to coordination in multi-modal logistic planning.     

Ranking radiotherapy treatment plans using decision-analytic and heuristic techniques.

Radiotherapy treatment optimization is done by generating a set of tentative treatment plans, evaluating them, and selecting the plan closest to achieving a set of conflicting treatment objectives. The evaluation of potential plans involves making trade-offs among competing possible outcomes. Multiattribute decision theory provides a framework for specifying such trade-offs and using them to select optimal actions. Using these concepts, we have developed a plan-ranking model which ranks a set of tentative treatment plans from best to worst. Heuristics are used to refine this model so that it reflects the clinical condition of the patient being treated and the practice preference of the physician prescribing the treatment. A figure of merit is computed for each tentative plan and is used to rank the plans. The approach described is very general and can be used for other medical domains having similar characteristics. The figure of merit can also be used as an objective function by computer programs that attempt to automatically generate an optimal treatment plan.     

A heuristic search approach to planning with temporally extended preferences

Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan—i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.     

网络容错与安全研究述评

在当今的研究开发、设计、制造和建设中，“网络”、“容错”和“安全”是三个不同的领域，但是它们相互交叉，密不可分，三个领域的研究工作者需要协同合作，才能达到用户对安全可靠的实用要求，该文用若干具体技术问题说明这种交叉和融合，这一趋势从国际研究与发展中看得越来越清楚，需要引起国内专家和管理部门的重视。     

Structural plan similarity based on refinements in the space of partial plans

Plan similarity measures play a key role in many areas of artificial intelligence, such as case‐based planning, plan recognition, ambient intelligence, or digital storytelling. In this paper, we present 2 novel structural similarity measures to compare plans based on a search process in the space of partial plans. Partial plans are compact representations of sets of plans with some common structure and can be organized in a lattice so that the most general partial plans are above the most specific ones. To compute our similarity measures, we traverse this space of partial plans from the most general to the most specific using successive refinements. Our first similarity measure is designed for propositional plan formalisms, and the second is designed for classical planning formalisms (including variables and types). We also introduce 2 novel refinement operators used to traverse the space of plans: an ideal downward refinement operator for propositional partial plans and a finite and complete downward refinement operator for classical partial plans. Finally, we evaluate our similarity measures in the context of a nearest neighbor classifier using 2 datasets commonly used in the plan recognition literature (Linux and Monroe), showing good results in both synthetic and real data.     

基于限定的规划识别问题求解

该文把McCarthy的限定理论同规划识别结合起来，在限定中研究规划识别问题，证明了在一定的限制下，由观察到的现象求出的最小规划集与对这些现象作限定获得的解集是一样的，以此为基础，文中提出了一种用限定求解规划识别问题的方式，这种方法把Kautz提出的规划识别表示形式做了某些改变，求解的过程中把二阶限定的表示形式转化为一阶形式，这种一阶形式的限定结果可以用逐点限定的方法直接求得，因为利用了逐点限定的这一特点，该文的方法对限定的计算过程中可以用机器自动完成。     

Hierarchically merging plans 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. We have developed a plan merging methodology that merges partial-order plans based on the notion of plan fragments. In contrast to previous works, mergeability classes no longer necessarily form a partition over the set of actions in the input plans. This methodology applies to a class of planning domains which are decomposable. 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, and a novel approach is presented for removing cyclic dependencies that may result during the plan merging process. We provide theoretical analyses of several algorithms for computing the minimum cost cover of plan fragments, a central component of the methodology. We support the theoretical analysis of these algorithms with experimental data to show that a greedy approach is near-optimal and efficient     

Which sort orders are interesting?

Sort orders play an important role in query evaluation. Algorithms that rely on sorting are widely used to implement joins, grouping, duplicate elimination and other set operations. The notion of interesting orders has allowed query optimizers to consider plans that could be locally sub-optimal, but produce ordered output beneficial for other operators, and thus be part of a globally optimal plan. However, the number of interesting orders for most operators is factorial in the number of attributes involved. Optimizer implementations use heuristics to prune the number of interesting orders, but the quality of the heuristics is unclear. Increasingly complex decision support queries and increasing use of query-covering indices, which provide multiple alternative sort orders for relations, motivate us to better address the problem of choosing interesting orders. We show that even a simplified version of the problem is NP-hard and provide a 1/2-benefit approximation algorithm for a special case of the problem. We then present principled heuristics for the general case of choosing interesting orders. We have implemented the proposed techniques in a Volcano-style cost-based optimizer, and our performance study shows significant improvements in estimated cost. We also executed our plans on a widely used commercial database system, and on PostgreSQL, and found that actual execution times for our plans were significantly better than for plans generated by those systems in several cases.     

Coordination by design and the price of autonomy

We consider a multi-agent planning problem as a set of activities that has to be planned by several autonomous agents. In general, due to the possible dependencies between the agents’ activities or interactions during execution of those activities, allowing agents to plan individually may lead to a very inefficient or even infeasible solution to the multi-agent planning problem. This is exactly where plan coordination methods come into play. In this paper, we aim at the development of coordination by design techniques that (i) let each agent construct its plan completely independent of the others while (ii) guaranteeing that the joint combination of their plans always is coordinated. The contribution of this paper is twofold. Firstly, instead of focusing only on the feasibility of the resulting plans, we will investigate the additional costs incurred by the coordination by design method, that means, we propose to take into account the price of autonomy: the ratio of the costs of a solution obtained by coordinating selfish agents versus the costs of an optimal solution. Secondly, we will point out that in general there exist at least two ways to achieve coordination by design: one called concurrent decomposition and the other sequential decomposition. We will briefly discuss the applicability of these two methods, and then illustrate them with two specific coordination problems: coordinating tasks and coordinating resource usage. We also investigate some aspects of the price of autonomy of these two coordination methods.     

A CSP model for simple non-reversible and parallel repair plans

This work presents a constraint satisfaction problem (CSP) model for the planning and scheduling of disassembly and assembly tasks when repairing or substituting faulty parts. The problem involves not only the ordering of assembly and disassembly tasks, but also the selection of them from a set of alternatives. The goal of the plan is the minimization of the total repairing time, and the model considers, apart from the durations and resources used for the assembly and disassembly tasks, the necessary delays due to the change of configuration in the machines, and to the transportation of intermediate subassemblies between different machines. The problem considers that sub-assemblies that do not contain the faulty part are nor further disassembled, but allows non-reversible and parallel repair plans. The set of all feasible repair plans are represented by an extended And/Or graph. This extended representation embodies all of the constraints of the problem, such as temporal and resource constraints and those related to the selection of tasks for obtaining a correct plan.     

图规划框架下的规划合成与分解

提出了原子规划、独立规划、子规划以及父规划等概念,给出了图规划框架下的规划分解算法,有效地解决了在现实世界中求出有效规划后,初始条件发生改变的情况。定义了相关动作、相关规划以及相关规划的判定方法,提出了规划合成算法。几个有效规划的单独执行会浪费资源,针对这种情况该文提出了解决方案。     

FOX-GA: a genetic algorithm for generating and analyzing battlefield courses of action

This paper describes FOX-GA, a genetic algorithm (GA) that generates and evaluates plans in the complex domain of military maneuver planning. FOX-GA's contributions are to demonstrate an effective application of GA technology to a complex real world planning problem, and to provide an understanding of the properties needed in a GA solution to meet the challenges of decision support in complex domains. Previous obstacles to applying GA technology to maneuver planning include the lack of efficient algorithms for determining the fitness of plans. Detailed simulations would ideally be used to evaluate these plans, but most such simulations typically require several hours to assess a single plan. Since a GA needs to quickly generate and evaluate thousands of plans, these methods are too slow. To solve this problem we developed an efficient evaluator (wargamer) that uses course-grained representations of this problem domain to allow appropriate yet intelligent trade-offs between computational efficiency and accuracy. An additional challenge was that users needed a diverse set of significantly different plan options from which to choose. Typical GA's tend to develop a group of "best" solutions that may be very similar (or identical) to each other. This may not provide users with sufficient choice. We addressed this problem by adding a niching strategy to the selection mechanism to insure diversity in the solution set, providing users with a more satisfactory range of choices. FOX-GA's impact will be in providing decision support to time constrained and cognitively overloaded battlestaff to help them rapidly explore options, create plans, and better cope with the information demands of modern warfare.     

Optimistic Byzantine fault tolerance

The primary concern of traditional Byzantine fault tolerance is to ensure strong replica consistency by executing incoming requests sequentially according to a total order. Speculative execution at both clients and server replicas has been proposed as a way of reducing the end-to-end latency. In this article, we introduce optimistic Byzantine fault tolerance. Optimistic Byzantine fault tolerance aims to achieve higher throughput and lower end-to-end latency by using a weaker replica consistency model. Instead of ensuring strong safety as in traditional Byzantine fault tolerance, nonfaulty replicas are brought to a consistent state periodically and on-demand in optimistic Byzantine fault tolerance. Not all applications are suitable for optimistic Byzantine fault tolerance. We identify three types of applications, namely, realtime collaborative editing, event stream processing, and services constructed with conflict-free replicated data types, as good candidates for applying optimistic Byzantine fault tolerance. Furthermore, we provide a design guideline on how to achieve eventual consistency and how to recover from conflicts at different replicas. In optimistic Byzantine fault tolerance, a replica executes a request immediately without first establishing a total order of the message, and Byzantine agreement is used only to establish a common state synchronization point and the set of individual states needed to resolve conflicts. The recovery mechanism ensures both replica consistency and the validity of the system by identifying and removing the operations introduced by faulty clients and server replicas.     

Consensus when all processes may be Byzantine for some time

Among all classes of faults, Byzantine faults form the most general modeling of value faults. Traditionally, in the Byzantine fault model, faults are statically attributed to a set of up to t processes. This, however, implies that in this model a process at which a value fault occurs is forever “stigmatized” as being Byzantine, an assumption that might not be acceptable for long-lived systems, where processes need to be reintegrated after a fault.We thus consider a model where Byzantine processes can recover in a predefined recovery state, and show that consensus can be solved in such a model. Our model admits executions where over time every process is faulty as long as there are always enough correct processes.     

基于多维加权贴近度方法的方案优选

在决策支持系统中经常遇到从以前的方案库中优选方案进行决策。方案选择会对决策结果影响很大，常常有一定的模糊性。用多维加权贴近度方法可以很好的计算出方案库中的方案与目标方案的相似程度，相似程度最高的方案即为最优方案。此方法分析了三种类型的定量特征以及模糊特征的隶属度函数的设定，两种常用贴近度的使用，用权重分析系统进行特征权重的设置。实例证明该方法比一般加权和方法选出的最优方案更准确、更有效。     

Sequential attributes sampling: Inspection error effects and compensation

Sequential sampling represents the logical limit in lot-by-lot multiple acceptance sampling. Sequential plans are generally developed in order to fit a desired operating characteristic curve. The basic premise is that items are observed one at a time and classified as good or bad. Following each sampled item, and based upon the current cumulative results a decision is made to accept the lot, reject the lot, or sample another item from the lot.

Inspection error severely distorts the operating characteristic performance measure of a sequential sampling plan. Yet, we continue to design sequential plans under the assumption of perfect assessment, even though the fact that inspection errors are common is well documented. This paper examines and illustrates the effects of error on the sequential sampling OC curve. These effects are developed mathematically beginning with Wald's formulation of the sequential probability ratio. The results are computerized and a typical sequential plan is analyzed under several type 1 and type 2 inspection error pairs to determine the resulting OC curves.

Additionally, a method of sampling plan design is developed which compensates for the effects of known inspection error. That is, it provides the complete sampling plan which, iffollowed in an error prone environment, yields the OC curve actually desired. This compensating method of sampling plan design has also been computerized. A copy of the entire program appears in the Appendix at the end of the paper.     

A prototype of a feature-based multiple-alternative process planning system with scheduling verification

The primary objective of this research was to develop a prototype feature-based multiple-alternative process planning system in which the process plan would be generated directly from design and available factory facility information. An overall removable volume is generated by graphically comparing the 3D part and 3D workpiece blank. The manufacturing features are decomposed into a series of general manufacturing features by using a mixed graph-based and rule-based algorithm. The multiple-alternative process plan generation is based on recognized manufacturing features and various production rules. After generating multiple process plans, each process plan is allocated the possible manufacturing scheduling time and the candidate process plans are retrieved based on the required due day. An example problem is presented to illustrate the functionality of the prototype system. This research presents an alternative method that provides useful information to the factory planner and controller to facilitate production.     

Recovering from execution errors in SIPE

In real-world domains (e.g., a mobile robot environment), things do not always proceed as planned, so it is important to develop better execution-monitoring techniques and replanning capabilities. This paper describes these capabilities in the SIPE (System for Interactive Planning and Execution Monitoring) planning system. The motivation behind SIPE is to place enough limitations on the representation so that planning can be done efficiently, while retaining sufficient power to still be useful. This work assumes that new information given to the execution monitor is in the form of predicates, thus avoiding the difficult problem of how to generate these predicates from information provided by sensors.
The replanning module presented here takes advantage of the rich structure of SIPE plans and is intimately connected with the planner, which can be called as a subroutine. This allows the use of SIPE's capabilities to determine efficiently how unexpected events affect the plan being executed and, in many cases, to retain most of the original plan by making changes in it to avoid problems caused by these unexpected events. SIPE is also capable of shortening the original plan when serendipitous events occur. A general set of replanning actions is presented along with a general replanning capability that has been implemented by using these actions.