Search

Failures in plan execution can be attributed to errors in the execution of plan steps or violations of the plan structure. The structure of a plan prescribes which actions have to be performed and which precedence constraints between them have to be respected. Especially in multi-agent environments violations of plan structure might easily occur as the consequence of synchronization errors. While in previous work we have concentrated on the first type of failures, in this paper we introduce the idea of diagnosing plan structure violations. Using a formal framework for plan diagnosis, we describe how Model-Based Diagnosis can applied to identify these violations of plan structure specifications and we analyze their computational complexity. [ABSTRACT FROM AUTHOR]

In real-life multi-agent planning problems, long-term plans will often be invalidated by changes in the environment during or after the planning process. When this happens, short-term operational planning and scheduling methods have to be applied in order to deal with these changed situations. In addition to the dynamic environment, in such planning systems we also have to be aware of sometimes conflicting interests of different parties, which render a centralized approach undesirable. In this paper we investigate two agent-based scheduling architectures where stakeholders are modelled as autonomous agents. We discuss this approach in the context of an interesting airport planning problem: the planning and scheduling of deicing and anti-icing activities. To coordinate the competition between agents over scarce resources, we have developed two mechanisms: one mechanism based on decommitment penalties, and one based on a more traditional (Vickrey) auction. Experiments show that the auction-based mechanism best respects the preferences of the individual agents, whereas the decommitment mechanism ensures a fairer distribution of delay over the agents. [ABSTRACT FROM AUTHOR]

The most common reason for plan repair are the violation of a plan's temporal constraints. Air Traffic Control is an example of an area in which violations of the plan's temporal constraints is rather a rule than an exception. In such domains there is a need for identifying the underlying causes of the constraint violations in order to improve plan repairs and to anticipate future constraint violations. This paper presents a model for identifying the causes of the temporal constraint violations. [ABSTRACT FROM AUTHOR]

Diagnosis of plan failures is an important subject in both single- and multi-agent planning. Plan diagnosis can be used to deal with plan failures in three ways: (i) it provides information necessary for the adjustment of the current plan or for the development of a new plan, (ii) it can be used to point out which equipment and/or agents should be repaired or adjusted so they will not further harm the plan execution, and (iii) it can identify the agents responsible for plan-execution failures. We introduce two general types of plan diagnosis: primary plan diagnosis identifying the incorrect or failed execution of actions, and secondary plan diagnosis that identifies the underlying causes of the faulty actions. Furthermore, three special cases of secondary plan diagnosis are distinguished, namely agent diagnosis, equipment diagnosis and environment diagnosis. [ABSTRACT FROM AUTHOR]

Unexpected events during the execution of a plan may lead to conflicts: we then say that the plan execution is unhealthy. This paper presents a new model that enables agents (1) to control plan-execution health and (2) to regain health when necessary. The agents can utilize the model to predict consequences of occurring disruptions and thus detect unhealthy situations. With the help of the model's predictions, agents can correct the execution of tasks within the plan to regain health. The applicability of the presented model is demonstrated by introducing two multi-agent protocols to keep the plan execution healthy. Finally, we investigate the solving capabilities and the efficiency of our method in experiments using randomly generated plans. Our conclusion is that a reasonable proportion of unhealthy situations can be solved adequately by corrections in the plan execution instead of performing a replanning procedure. [ABSTRACT FROM AUTHOR]

We discuss the application of Model-Based Diagnosis in (agent- based) planning. Here, a plan together with its executing agent is considered as a system to be diagnosed. It is assumed that the execution of a plan can be monitored by making partial observations of the results of actions. These observations are used to explain the observed deviations from the plan by qualifying some action instances that occur in the plan as behaving abnormally. Unlike in standard model-based diagnosis, however, in plan diagnosis we cannot assume that actions fail independently. We focus on two sources of dependencies between failures: such failings may occur as the result of malfunctioning of the executing agent or may be caused by dependencies between action instances occurring in a plan. Therefore, we introduce causal rules that relate health states of the agent and health states of actions to abnormalities of other action instances. These rules enable us to determine the underlying causes of plan failing and to predict future anomalies in the execution of actions. [ABSTRACT FROM AUTHOR]