Article Preview
Top1. Introduction
The distributed planning constitutes an inherent element in the study and use of multi-agents systems. It is interested in the question of how to organize and coordinate (often in an automatic manner) the actions of agents evolving in dynamic systems in order to accomplish complex tasks. To deal with this issue, several areas have been investigated, especially the interleaving of planning and execution. Different approaches have been proposed in this context. In (Pappachan & Durfee, 2000; Alami et al., 1998; Durfee & Lesser, 1991; Brenner & Nebel, 2009) the authors have proposed solutions focused on incremental merging of short term plans that can be executed firstly. However, other works such as (Tsamardinos et al., 2000) are based on conditional paradigms that search for plans that deal with all potential situations. The aim of these works is to reduce the time between the planning and the execution, either by advancing the execution (before the global plan is completely elaborated) or by retarding decision about the selection of some actions (least commitment strategy) to the execution step. Unfortunately, these approaches are suitable to solve simple and small-scale problems only.
To overcome this drawback, researchers have exploited the concept of abstraction to define adequate representations of plans, and also to provide algorithms for planning, coordination, and execution. By ignoring some less important details when dealing with a big problem, a solution can be found more easily (Sacerdott, 1973; Clement et al., 2007). Many works (Erol et al., 1994b,a; Corkill, 1979; desJardins & Wolverton, 1999; Hayashi, 2007) have adopted a plans models having hierarchical structure, each level in the hierarchy represents an abstraction level. The highest level includes the compound (or abstract) tasks and the lower level includes the primitive (or elementary) tasks. The intermediate levels include less abstract tasks. Links between different levels represent the abstract tasks decomposition (or refinement). Other approaches such as (Clement & Durfee, 1999; Clement et al., 2007; Thangarajah et al., 2003; Lotem & Nau, 2000) have proposed extended models of hierarchical plans by introducing so called summary information. Annotating the abstract tasks, this information summarizes pre, post conditions, and resources needed of tasks at lower levels. The use of these extended models allows the reasoning on abstract tasks and the analysis of the interdependency of concurrent tasks. This ability can have the following advantages:
- •
Reduce the complexity of planning and coordination: As the agents' plans are hierarchically represented, their analysis can be performed in a multi-level way. In each level some less important details are ignored;
- •
Make the interleaving of local planning and execution: The coordination of agents’ plans in an abstract level can produce flexible plans that allow agents to deal with several situations. Agents can dynamically adapt their behavior according to the current context by selecting the suitable alternative.
Despite positive aspects that characterize the used models, these approaches remain not suitable to address the dynamic aspect of tasks and plans, especially where coordination must be interleaved with the execution.
In this paper, we are expected to provide a model of hierarchical plans that takes into account the representation of flexible plans, and that offers the necessary features allowing the monitoring of agents’ plans in planning, coordination, and execution. We mean by “flexible plans” those which are less sensitive to the execution context, and can support flexible execution. The model must also domain-independent and can aid the handling dynamically plans interaction and interdependency, and the control of resources evolution at run time.