Hierarchical Multi-Agent Plans Using Model-Based Petri Net

Hierarchical Multi-Agent Plans Using Model-Based Petri Net

Said Brahimi (Computer Science Department, University of Guelma, Guelma, Algeria & LIRE Laboratory, University of Constantine 2, Constantine, Algeria), Ramdane Maamri (LIRE Laboratory, University of Constantine 2, Constantine, Algeria) and Zaidi Sahnoun (LIRE Laboratory, University of Constantine 2, Constantine, Algeria)
Copyright: © 2013 |Pages: 30
DOI: 10.4018/jats.2013040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Agents evolving in complex and dynamic multi-agent systems need to plan their tasks and to adapt their behavior in order to react to unpredictable events. Therefore they must have plans that remain subject to continual updating, even during its execution. Although this property is important in dynamic environments, it is difficult to have a trade-off between the convergence towards the goal to be reached and the reaction to unanticipated events. To cope with this issue, it is needed to have a model allowing to represent plans less sensitive to execution contexts, and to support flexible execution. This paper aims to provide an adequate plan representation, by taking advantage of hierarchical plans and extensions to Petri net. The authors extend the Petri net to take into account the different abstraction levels of plans and the resources required by tasks. To cope with the interdependence of tasks, the authors include in the model, a synchronization mechanism between concurrent transitions. The proposed model can be used to reason on abstract levels of plans and to analyze, in a dynamic way, situations in which the execution of the plan can be performed in any ways, in some ways, or cannot be performed.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 8: 1 Issue (2016): Forthcoming, Available for Pre-Order
Volume 7: 3 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing