ACTION FAILURE RECOVERY VIA MODEL‐BASED DIAGNOSIS AND CONFORMANT PLANNING

A plan carried on in the real world may be affected by a number of unexpected events, plan threats, which cause significant deviations between the intended behavior of the plan executor (i.e., the agent) and the observed one. These deviations are typically considered as action failures. This paper addresses the problem of recovering from action failures caused by a specific class of plan threats: faults in the functionalities of the agent. The problem is approached by exploiting techniques of the Model‐Based Diagnosis (MBD) for detecting failures (plan execution monitoring) and for explaining these failures in terms of faulty functionalities (agent diagnosis). The recovery process is modeled as a replanning problem aimed at fixing the faulty components identified by the agent diagnosis. However, since the diagnosis is in general ambiguous (a failure may be explained by alternative faults), the recovery has to deal with such an uncertainty. The paper advocates the adoption of a conformant planner, which guarantees that the recovery plan, if it exists, is executable no matter what the actual cause of the failure. The paper focuses on a single agent performing its own plan, however the proposed methodology takes also into account that agents are typically situated into a multiagent scenario and that commitments between agents may exist. The repair strategy is therefore conceived to overcome the causes of a failure while assuring the commitments an agent has agreed with other team members.     

Verifying plans for multiple agents

Abstract

Research in distributed artificial intelligence planning has historically focused on two distinct classes of problems. One paradigm has been that of 'planning for multiple agents', which considers issues inherent in centrally directed multi-agent execution. The second paradigm has been 'distributed planning', where multiple agents more autonomously participate in coordinating and deciding upon their own actions. The work described in this paper is in the first category, planning for multiple agents. Taking the STRIPS representation of actions, and directed acrylic graphs (DAGs) as plan representations particularly well suited to parallel execution, it formally analyses the following question: how can a DAG plan be verified (i.e. how can we be sure such a plan will be correct, given our uncertainty about exactly when unconstrained parallel actions will be performed)? A method is presented for verifying the correctness of plans for multiple agents, represented as DAGs. The technique allows for the efficient analysis of a plan, despite its many potential execution histories.     

A logic-based agent that plans for extended reachability goals

Planning to reach a goal is an essential capability for rational agents. In general, a goal specifies a condition to be achieved at the end of the plan execution. In this article, we introduce nondeterministic planning for extended reachability goals (i.e., goals that also specify a condition to be preserved during the plan execution). We show that, when this kind of goal is considered, the temporal logic ctl turns out to be inadequate to formalize plan synthesis and plan validation algorithms. This is mainly due to the fact that the ctl’s semantics cannot discern among the various actions that produce state transitions. To overcome this limitation, we propose a new temporal logic called α-ctl. Then, based on this new logic, we implement a planner capable of synthesizing reliable plans for extended reachability goals, as a side effect of model checking.     

Planning and execution through variable resolution planning

Generating sequences of actions–plans–for robots using Automated Planning in stochastic and dynamic environments has been shown to be a difficult task with high computational complexity. These plans are composed of actions whose execution might fail due to different reasons. In many cases, if the execution of an action fails, it prevents the execution of some (or all) of the remainder actions in the plan. Therefore, in most real-world scenarios computing a complete and sound (valid) plan at each (re-)planning step is not worth the computational resources and time required to generate the plan. This is specially true given the high probability of plan execution failure. Besides, in many real-world environments, plans must be generated fast, both at the start of the execution and after every execution failure. In this paper, we present Variable Resolution Planning which uses Automated Planning to quickly compute a reasonable (not necessarily sound) plan. Our approach computes an abstract representation–removing some information from the planning task–which is used once a search depth of $k$ steps has been reached. Thus, our approach generates a plan where the first $k$ actions are applicable if the domain is stationary and deterministic, while the rest of the plan might not be necessarily applicable. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future actions that probably will not be executed, since in most cases it will need to replan before executing the end of the plan; and takes into account some information of the far future, as an improvement over pure reactive systems. We present experimental results on different robotics domains that simulate tasks on stochastic environments.     

Reasoning about plan revision in BDI agent programs

Facilities for handling plan execution failures are essential for agents which must cope with the effects of nondeterministic actions, and some form of failure handling can be found in most mature agent programming languages and platforms. While such features simplify the development of more robust agents, they make it hard to reason about the execution of agent programs, e.g., to verify their correctness. In this paper, we present an approach to the verification of agent programs which admit exceptional executions. We consider executions of the BDI-based agent programming language 3APL in which plans containing non-executable actions can be revised using plan revision rules, and present a logic for reasoning about normal and exceptional executions of 3APL programs. We provide a complete axiomatization for the logic and, using a simple example, show how to express properties of 3APL programs as formulas of the logic.     

Design and evaluation of a fault-tolerant mobile-agent system

The mobile agents create a new paradigm for data exchange and resource sharing in rapidly growing and continually changing computer networks. In a distributed system, failures can occur in any software or hardware component. A mobile agent can get lost when its hosting server crashes during execution, or it can get dropped in a congested network. Therefore, survivability and fault tolerance are vital issues for deploying mobile-agent systems. This fault tolerance approach deploys three kinds of cooperating agents to detect server and agent failures and recover services in mobile-agent systems. An actual agent is a common mobile agent that performs specific computations for its owner. Witness agents monitor the actual agent and detect whether it's lost. A probe recovers the failed actual agent and the witness agents. A peer-to-peer message-passing mechanism stands between each actual agent and its witness agents to perform failure detection and recovery through time-bounded information exchange; a log records the actual agent's actions. When failures occur, the system performs rollback recovery to abort uncommitted actions. Moreover, our method uses checkpointed data to recover the lost actual agent.     

An abstract knowledge based approach to diagnosis and recovery of plan failure in multi-agent systems

Open multi-agent systems (MAS) are decentralised and distributed systems that consist of a large number of loosely coupled autonomous agents. In the absence of centralised control they tend to be difficult to manage, especially in an open environment, which is dynamic, complex, distributed and unpredictable. This dynamism and uncertainty in an open environment gives rise to unexpected plan failures. In this paper we present an abstract knowledge based approach for the diagnosis and recovery of plan action failures. Our approach associates a sentinel agent with each problem solving agent in order to monitor the problem solving agent’s interactions. The proposed approach also requires the problem solving agents to be able to report on the status of a plan’s actions.Once an exception is detected the sentinel agents start an investigation of the suspected agents. The sentinel agents collect information about the status of failed plan abstract actions and knowledge about agents’ mental attitudes regarding any failed plan. The sentinel agent then uses this abstract knowledge and the agents’ mental attitudes, to diagnose the underlying cause of the plan failure. The sentinel agent may ask the problem solving agent to retry their failed plan based on the diagnostic result.     

Coach planning with opponent models for distributed execution

In multi-agent domains, the generation and coordinated execution of plans in the presence of adversaries is a significant challenge. In our research, a special “coach” agent works with a team of distributed agents. The coach has a global view of the world, but has no actions other than occasionally communicating with the team over a limited bandwidth channel. Our coach is given a set of predefined opponent models which predict future states of the world caused by the opponents’ actions. The coach observes the world state changes resulting from the execution of its team and opponents and selects the best matched opponent model based on its observations. The coach uses the recognized opponent model to predict the behavior of the opponent. Upon opportunities to communicate, the coach generates a plan for the team, using the predictions of the opponent model. The centralized coach generates a plan for distributed execution. We introduce (i) the probabilistic representation and recognition algorithm for the opponent models; (ii) a multi-agent plan representation, Multi-Agent Simple Temporal Networks; and (iii) a plan execution algorithm that allows the robust distributed execution in the presence of noisy perception and actions. The complete approach is implemented in a complex simulated robot soccer environment. We present the contributions as developed in this domain, carefully highlighting their generality along with a series of experiments validating the effectiveness of our coach approach.     

A Resource Logic for Multi-Agent Plan Merging

In a multi-agent system, agents are carrying out certain tasks by executing plans. Consequently, the problem of finding a plan, given a certain goal, has been given a lot of attention in the literature. Instead of concentrating on this problem, the focus of this paper is on cooperation between agents which already have constructed plans for their goals. By cooperating, agents might reduce the number of actions they have to perform in order to fulfill their goals. The key idea is that in carrying out a plan an agent possibly produces side products that can be used as resources by other agents. As a result, an other agent can discard some of its planned actions. This process of exchanging products, called plan merging, results in distributed plans in which agents become dependent on each other, but are able to attain their goals more efficiently. In order to model this kind of cooperation, a new formalism is developed in which side products are modeled explicitly. The formalism is a resource logic based on the notions of resource, skill, goal, and service. Starting with some resources, an agent can perform a number of skills in order to produce other resources which suffice to achieve some given goals. Here, a skill is an elementary production process taking as inputs resources satisfying certain constraints. A service is a serial or parallel composition of skills acting as a program. An operational semantics is developed for these services as programs. Using this formalism, an algorithm for plan merging is developed, which is anytime and runs in polynomial time. Furthermore, a variant of this algorithm is proposed that handles the exchange of resources in a more flexible way. The ideas in the paper will be illustrated by an example from public transportation.     

INTEGRATING PLANNING,EXECUTION, AND LEARNING TO IMPROVE PLAN EXECUTION

Algorithms for planning under uncertainty require accurate action models that explicitly capture the uncertainty of the environment. Unfortunately, obtaining these models is usually complex. In environments with uncertainty, actions may produce countless outcomes and hence, specifying them and their probability is a hard task. As a consequence, when implementing agents with planning capabilities, practitioners frequently opt for architectures that interleave classical planning and execution monitoring following a replanning when failure paradigm. Though this approach is more practical, it may produce fragile plans that need continuous replanning episodes or even worse, that result in execution dead‐ends. In this paper, we propose a new architecture to relieve these shortcomings. The architecture is based on the integration of a relational learning component and the traditional planning and execution monitoring components. The new component allows the architecture to learn probabilistic rules of the success of actions from the execution of plans and to automatically upgrade the planning model with these rules. The upgraded models can be used by any classical planner that handles metric functions or, alternatively, by any probabilistic planner. This architecture proposal is designed to integrate off‐the‐shelf interchangeable planning and learning components so it can profit from the last advances in both fields without modifying the architecture.     

Goal-driven automation of a deep space communications station: a case study in knowledge engineering for plan generation and execution

Abstract: This paper describes the application of Artificial Intelligence techniques for plan generation, plan execution, and plan monitoring to automate a Deep Space Communication Station. This automation allows a communication station to respond to a set of tracking goals by appropriately reconfiguring the communications hardware and software to provide the requested communications services. In particular this paper describes: (1) the overall automation architecture, (2) the plan generation and execution monitoring AI technologies used and implemented software components, and (3) the knowledge engineering process and effort required for automation. This automation was demonstrated in February 1995, at the DSS13 Antenna Station in Goldstone, CA on a series of Voyager tracks and the technologies demonstrated are being transferred to the operational Deep Space Network stations.     

An Automated Teamwork Infrastructure for Heterogeneous Software Agents and Humans

Agent integration architectures enable a heterogeneous, distributed set of agents to work together to address problems of greater complexity than those addressed by the individual agents themselves. Unfortunately, integrating software agents and humans to perform real-world tasks in a large-scale system remains difficult, especially due to three main challenges: ensuring robust execution in the face of a dynamic environment, providing abstract task specifications without all the low-level coordination details, and finding appropriate agents for inclusion in the overall system. To address these challenges, our Teamcore project provides the integration architecture with general-purpose teamwork coordination capabilities. We make each agent team-ready by providing it with a proxy capable of general teamwork reasoning. Thus, a key novelty and strength of our framework is that powerful teamwork capabilities are built into its foundations by providing the proxies themselves with a teamwork model.Given this teamwork model, the Teamcore proxies addresses the first agent integration challenge, robust execution, by automatically generating the required coordination actions for the agents they represent. We can also exploit the proxies' reusable general teamwork knowledge to address the second agent integration challenge. Through team-oriented programming, a developer specifies a hierarchical organization and its goals and plans, abstracting away from coordination details. Finally, KARMA, our Knowledgeable Agent Resources Manager Assistant, can aid the developer in conquering the third agent integration challenge by locating agents that match the specified organization's requirements. Our integration architecture enables teamwork among agents with no coordination capabilities, and it establishes and automates consistent teamwork among agents with some coordination capabilities. Thus, team-oriented programming provides a level of abstraction that can be used on top of previous approaches to agent-oriented programming. We illustrate how the Teamcore architecture successfully addressed the challenges of agent integration in two application domains: simulated rehearsal of a military evacuation mission and facilitation of human collaboration.     

Learning to diagnose failures of assembly tasks

An architecture for execution supervision of Robotic Assembly Tasks is presented. This architecture provides, at different levels of abstraction, functions for dispatching actions, monitoring their execution, and diagnosing and recovering from failures. Modeling execution failures through taxonomies and causal networks plays a central role in diagnosis and recovery. A discussion on the knowledge acquisition process, through the use of machine learning techniques, is made. Preliminary results in this area are presented and planned extensions discussed.     

The rescheduling arc routing problem

In this paper, the rescheduling arc routing problem is introduced. This is a dynamic routing and scheduling problem that considers adjustments to an initial routing itinerary when one or more vehicle failures occur during the execution stage and the original plan must be modified. We minimize the operational and schedule disruption costs. Formulations based on mixed‐integer programming are presented to compare different policies in the rerouting phase. A solution strategy is developed when both costs are evaluated and it is necessary to find a solution quickly. Computational tests on a large set of instances compare the different decision‐maker policies.     

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.     

The optimal used period of repairable product with leadtime after the warranty expiry

This paper considers the two-phase warranty models for repairable products. It defines the time-interval [0,?W] as the first phase (warranty period) and the time interval (W,?T?+?W) as the second phase (buyer survival period). The products have two types of failures: type I failures (minor failures) and type II failures (catastrophic failures). In the model, type I failures are also removed by minimal repairs in the first and the second phases, and type II failures are removed by replacements in the first phase. If type II failures take place in the second phase, then it is supposed the life of products will be ended. To buy a new product is conducted at time T+W or upon the type II failure. Whenever each replacement takes place, the spare unit is ordered and then delivered. Therefore, the lead-time is considered. This thesis considers three warranty and maintenance models for seller, buyer and the society. The objective is to obtain the optimal T?*. Finally, a numerical example is provided.     

Answer set programming for collaborative housekeeping robotics: representation, reasoning, and execution

Answer set programming (ASP) is a knowledge representation and reasoning paradigm with high-level expressive logic-based formalism, and efficient solvers; it is applied to solve hard problems in various domains, such as systems biology, wire routing, and space shuttle control. In this paper, we present an application of ASP to housekeeping robotics. We show how the following problems are addressed using computational methods/tools of ASP: (1) embedding commonsense knowledge automatically extracted from the commonsense knowledge base ConceptNet, into high-level representation, and (2) embedding (continuous) geometric reasoning and temporal reasoning about durations of actions, into (discrete) high-level reasoning. We introduce a planning and monitoring algorithm for safe execution of plans, so that robots can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. Some of the recoveries require collaboration of robots. We illustrate the applicability of ASP on several housekeeping robotics problems, and report on the computational efficiency in terms of CPU time and memory.     

Deliberation dialogues for reasoning about safety critical actions

In this paper we present the argument-based model proCLAIM, intended to provide a setting for heterogeneous agents to deliberate over safety critical actions. To achieve this purpose proCLAIM features a Mediator Agent with three main tasks: (1) guiding the participating agents in what their valid dialectical moves are at each stage of the dialogue; (2) deciding whether submitted arguments should be accepted on the basis of their relevance; and finally, (3) evaluating the accepted arguments in order to provide an assessment of whether the proposed action should or should not be undertaken. The main focus in this paper is the proposal of a set of reasoning patterns, represented in terms of argument schemes and critical questions, intended to automatise deliberations on whether a proposed action can safely be performed. We aim to motivate the importance of these schemes and critical questions for: (a) the Mediator Agent’s guiding task that allows for a highly focused deliberation; (b) the effective participation of heterogeneous agents; and (c) enabling the reuse of previous similar deliberations in order to evaluate arguments on an evidential basis.     

一类扩展的动态描述逻辑

作为描述逻辑的扩展,动态描述逻辑为语义Web服务的建模和推理提供了一种有效途径.在将语义Web服务建模为动作之后,动态描述逻辑从动作执行结果的角度提供了丰富的推理机制,但对于动作的执行过程却不能加以处理.借鉴Pratt关于命题动态逻辑的相关研究,一方面,对动态描述逻辑中动作的语义重新进行定义,将每个动作解释为由关于可能世界的序列组成的集合;另一方面,在动态描述逻辑中引入动作过程断言,用来对动作的执行过程加以刻画.在此基础上提出一类扩展的动态描述逻辑EDDL(X),其中的X表示从ALC(attributive language with complements)到SHOIN(D)等具有不同描述能力的描述逻辑.以X为描述逻辑ALCQO(attributive language with complements,qualified number restrictions and nominals)的情况为例,给出了EDDL(ALCQO)的表判定算法,并证明了算法的可终止性、可靠性和完备性.EDDL(X)可以从动作执行过程和动作执行结果两个方面对动作进行全面的刻画和推理,为语义Web服务的建模和推理提供了进一步的逻辑支持.     

Models and methods for plan diagnosis

We consider a model-based diagnosis approach to the diagnosis of plans. Here, a plan performed by some agent(s) is considered as a system to be diagnosed. We introduce a simple formal model of plans and plan execution where it is assumed that the execution of a plan can be monitored by making partial observations of plan states. These observed states are used to compare them with states predicted based on (normal) plan execution. Deviations between observed and predicted states can be explained by qualifying some plan steps in the plan as behaving abnormally. A diagnosis is a subset of plan steps qualified as abnormal that can be used to restore the compatibility between the predicted and the observed partial state. Besides minimum and subset minimal diagnoses, we argue that in plan-based diagnosis maximum informative diagnoses should be considered as preferred diagnoses, too. The latter ones are diagnoses that make the strongest predictions with respect to partial states to be observed in the future. We show that in contrast to minimum diagnoses, finding a (subset minimal) maximum informative diagnosis can be achieved in polynomial time. Finally, we show how these diagnoses can be found efficiently if the plan is distributed over a number of agents.