Context-aware multi-agent planning in intelligent environments

Abstract

In ambient intelligence, systems should interact intelligently with users and assist them in integrated and almost transparent way. Hence, planning and context awareness is crucial for building such systems. To cope with the high dynamics and the openness of ambient intelligence environments, representation formalism allowing a run-time analysis and monitoring of plans is required. In this paper, we focus on context awareness and planning ability on ambient environments. First, we outline a formal modeling approach for context-aware planning based upon a hierarchical colored Petri nets formalism. The approach enables the specification of plans through many levels of abstractions. Second, we address the problem of assigning tasks to groups of agents; we describe the use of resulted model in conjunction with contract net protocol to form the collaborative agent networks. Again we show how the formal foundation of this framework allows plan verification and execution monitoring. Finally, we highlight the main aspects of the approach through an assisted healthcare system case study.

Keywords

Context awareness Petri nets multi-agents systems planning ambient intelligence

1. Introduction

Ambient intelligence describes situations in which computing and communication ability is spread ubiquitously, among almost every object in our environment. The main desired benefits of this paradigm are; increase our quality of life by promoting safety and comfort, and facilitate our daily activities by creating smart environments. In short, ambient intelligence is a vision about the future when the Artificial Intelligence (AI) will become ambient. However, realizing such vision is very challenging issues; part of the challenge is the need to combine expertise from a multitude of disciplines. From computer science discipline, ambient intelligence combines features and adopts solutions of many researches areas, such as; distributed artificial intelligence, robotics, machine learning, mobile computing, context-aware computing, semantic web, etc.

To anticipate the user’s needs and to provide them with suitable services in integrated and transparent way, ambient intelligence-based systems need to be context-aware. Several definitions of the context have been suggested in the literature. Xin et al. explore the main proposed definitions of this concept [20]. In this paper, we hold the definition given by Dey [9] which looks the more general. Dey et al. define the context as “the set of suitable environmental states and settings concerning a user, which are relevant for a situation sensitive application in the process of adapting the services and information offered to the user”. So context is any information considered relevant to describe the situation of an entity (a person, a place or an object) [10]. A system is context-aware if it uses context to provide relevant services to the user [20].

Apart from being context awareness, ambient intelligence based systems are distributed, embedded with our daily environments and must react in proactive and adaptive way to meet users’ needs. Considering agents and multi-agents characteristics, MAS paradigm is predominantly appropriate to meet ambient intelligence requirements. In fact, an agent has four properties: autonomy, reactivity, pro-activeness and social ability [18]. A multi-agent system is a federation of agents interacting in a shared environment that cooperate and coordinate their actions to achieve their own goals or the global system goals. A MAS design can be beneficial in many domains, particularly when a system is composed of several entities that are distributed or spatially functionally [12].

Planning is an important ability in the design of any intelligent system; it consists of selecting and organizing a set of actions to achieve some goal. Planning is a desired feature in ambient intelligence systems in order to achieve a goal-oriented behavior. In fact, context-aware planning is particularly required to meet ambient intelligence requirements; e.g., allowing systems interacting intelligently, proactively and unobtrusively. Undoubtedly, ambient intelligence can find proper solutions in the adoption of a Multi-Agent planning; where a team of agents cooperates by combining their knowledge, information, and capabilities in order to complete activities they are not able to accomplish individually.

Certainly, the efficiency of planning systems is strongly dependent on the representation of planning problem. When focusing on planning in ambient intelligent environments, a number of issues need to be addressed, among them; i) First, it concerns context modeling given that context must be a part of planning problem representation. Though Context modeling is a key factor in building context-aware and a variety of modeling approaches have been proposed, it is still an open and challenging issue, ii) ambient intelligence are typically very dynamic and open systems, thus, agents have to be able to perform a run-time plans analysis and must be able to monitor theirs execution, iii) When considering ambient intelligence environments contextual planning for multiple agents requires efficient reasoning approach to deal with complex situation that need to plan at a higher level first, then refine after.

In this paper, we focus on context awareness and planning issue on smart environments. We contribute with a context-aware multi-agent planning approach. In this approach we exploit the use of multi-agent systems in ambient intelligence environment and we focus on representing plans using abstraction and decomposition form, by adopting hierarchical task networks (HTN). HTN planning representations [11] allow a distributed planning agent to successively refine its plans as it has more information (about the environment, or about other agents’ plans). Planning is split up into several levels. For each level of abstraction (refinement) the planner generates a plan for a set of cooperative agents. Using this approach, the plan is iteratively constructed by the refinement of a very general plan to a very specific one. Indeed, HTN is suitable for ambient intelligence systems; it offers a natural and flexible way of representation and reasoning to deal with complex situations and incomplete information. We also exploit the capabilities of Petri nets as modeling and analyzing approach for both context–aware systems and multi-agent planning problem. Hence, we outline a formal modeling approach for context-aware planning based upon a hierarchical colored Petri nets formalism. This approach allows a run-time analysis and monitoring of plans. Furthermore, we address the problem of assigning tasks to groups of agents; we describe the use of proposed plan model in conjunction with contract net protocol to form the collaborative agent networks.

The main reasons behind the use of hierarchical colored Petri nets formalism are summarized as follows: First of all, it offers an explicit description of both states and actions. Their semantics are clearly very close to set-theoretic planning domain, where states and actions are the basic ingredients [24]. Secondly, the main advantage of hierarchical colored Petri nets over the other Petri Nets is the possibility to attach data values to tokens, called colors. So that, each token can be associated with attributes. As contextual information is often represented by collection of attributes, by analogy, the adoption of such representation by hierarchical colored Petri nets will be very intuitive using color notion. Furthermore, hierarchical colored Petri nets formal definition of the execution semantics allows the monitoring of the global/local plan and the extraction of relevant information about plan evolution. Plan execution is monitored through tracking the net marking and interprets it (e.g. blocked situation, successful termination). Finally, HTN approach is simply applied through the use of abstract and elementary transitions to represent abstract and primitive tasks.

The remaining part of this paper is organized as follows: the following section briefly discusses main relevant works which are related to our topic. In Section 3, we highlight our modeling and reasoning approach. In Section 4, we demonstrate and highlight the main aspects of the approach through an assisted healthcare system scenario. Section 5 describes the validation and the analysis of implemented case study with CPN tools. Finally, we recapitulate the main arguments and present some outline of our future work.

2. Literature review

In this section we briefly present relevant works which are related to our focus. We are interested particularly in works on Petri Net-based context modeling and planning for ambient intelligence systems.

Given that, ambient intelligence is multidisciplinary and a new computing paradigm, it has attracted the intention of a large range of researches. However, only few works were interested explicitly on planning ability for ambient intelligence systems. Planning is essential for building any intelligent system. Amigoni and al in have proposed the first solution for planning in ambient intelligence[2]. They have proposed the D-HTN (Distributed Hierarchical Task Network) planner as the most appropriate planner for ambient intelligence systems. The planning is carried by a single agent. They argue that centralized planning is suitable since devices usually have low computational capabilities. Really, for the required flexibility of the system and the number of devices involved, it is obvious that centralized control is not viable.

Ferrando et al. in [25] have presented Context-Aware Multi-Agent Planning (CAMAP) an approach for multi-agent planning based upon an argumentation-based defeasible logic. CAMAP is applied to ambient intelligence environment in the field of healthcare to get the most appropriate course of action based on the contextual information distributed among the agents. This approach is considered as distributed planning since each agent act as planning agent that hold different beliefs written in the form of defeasible facts and rules, and capabilities presented as planning actions. In CAMAP approach, context and ambient intelligence environment is represented based on a state variable representation. Bidot and Biundo in [5] propose an approach for the composition of services for ambient intelligence environments. They introduce the Planning Agent (PA) which encapsulates a search engine for hybrid planning i.e.combination of hierarchical task network planning and partial-order causal-link planning. The ontology is used to describe the smart environment. Like these works [9, 25, 5], we focus on planning ability for ambient intelligence environment. In [5], they focus on using artificial intelligence planning in the context of a distributed, ontology-based framework with a service-oriented architecture approach. In [25], they use the argumentative logic; Again, all the above-mentioned approaches don’t address the plan verification and monitoring problem.

Context modeling and reasoning approaches are required to realize context-aware systems. Over the years, a variety of context modeling approaches have been proposed, the most popular and surveyed ones are; Key-Value Models [27], Graphical Models such as the Unified Modeling Language (UML) [3], Object Oriented Models [28]. Logic Based Models [22] and Ontology Based Models [31]. Each of them has its advantages and also presents certain limitations [30, 4]. Key-value pairs were widely used in many research and distributed services frameworks; this is due to their simplicity and ease of use. However, it lacks capabilities for sophisticated structuring for enabling efficient context retrieval algorithms. Unlike, Key-value pair’s models, concepts and diagrams enabled by Unified Modeling Language (UML) and Object Oriented Models are able to specify relationships. Compared to all these cited approaches, Logic based context models offer a high degree of formality. In this model, context is defined as facts, expressions and rules. It may be composed distributed, but it remains the least used, this is due to the difficulty to maintain partial validation and to the high level of formality. In summary, each of these context modeling approaches has its advantages and also presents certain limitations [30, 4]. From our point of view, contextual information are no more than environmental information which are often called world state or belief state in set-theoretic planning domain [24]. Consequently, when considering planning problem, the Key-value pairs seems to be the closer approach for modeling contextual information.

Recently further emerging approaches using Petri Nets were proposed and they have been recognized as promising context modeling approaches [15]. This is due mainly to both formal and graphical nature, expressiveness, and analytical property of Petri Nets. Modeling with Petri Nets inherently satisfies the requirements of context model, especially the usability of modeling formalisms and representation of relationships among context information [15].

Kwon in [7] have proposed Amended CPN, an extension of Colored Petri Net [19] to model and to analyze the context-aware systems. In this work the system is decomposed into several subsystems as a pattern. Amended CPNs consist on multiple CPNs. Haiouni and Maamri [14] adopt the Colored Petri nets for context aware systems. The formalism was adopted to avoid conflict that can occur among resources sharing. Another Petri nets based approach was proposed by Wang and Zeng [32]. They have also concentrated on resource in context-aware systems. The approach allows the estimation of the minimum and maximum duration time of each activity when the model is built. Petri nets have been adopted in [26] to built context-aware interfaces. Riahi and Moussa proposed a formal approach based on Petri Net to model Human-Computer interactions [26]. Both context and the user’s task are modeled through Petri Net. All these networks supposed to be exploited for the specification of accurate interfaces. The Petri Net used in this approach is the Interpreted Petri Nets. Although these researches [7, 14, 32, 26] have proposed promising Petri net based context modeling approaches, none of these works used the resulted model to tackle the problem of execution monitoring nor tasks allocation among a group of ambient agents.

A part of being a proposing approach for context aware systems, Petri Nets has already been proven useful in more and more domains. Petri Nets come with a set of extensions; with powerful modeling capability and a strong mathematical foundation. It has proven to be effective as modeling and analysis tool for multi-agent systems, e.g. for plan modeling and verification [6], for agent cooperation and resource allocation [17], for modeling the behavior of agents and their interactions [21], …etc. In dynamically changing environments, it is necessary to adopt continual planning approaches in which the activities of planning and execution are interleaved. Thus, to cope with the high dynamics and the openness of ambient intelligence environments, representation formalism allowing a run-time analysis and monitoring of plans is required. Given these raised facts, we believe that formal method based on Petri nets formalism can be beneficial for context aware planning field.

3. Plan modeling and monitoring approach

Adopting a plans models having hierarchical structure shows promise and flexible way of representation and reasoning. It produces a natural representation for many real-world domains. In addition, as the complexity of planning applications increases, we think that, adopting such structure is more and more needed. Consequently, our plan model used in this paper is based on the hierarchical task network (HTN) approach [7]. In HTN planning, tasks can be either compound or primitive. The plan is represented through many level of abstraction.

Each level contains sub plans or compound tasks to be refined. The lower level contains only primitive tasks which can be executed directly by using planning operators. Higher and intermediate levels contain at least one compound task to be decomposed into predefined sub plans using decomposition methods. As shown in Fig. 1, planning is split up into several levels. For each level of abstraction (refinement) the planner generates a plan for a set of cooperative agents. Using this approach, plan is iteratively constructed by the refinement of a very general plan to a very specific one.

Figure 1.

HTN multi-agent planning.

3.1 Modeling principles

The original Petri Nets proposed by Carl Adam Petri [23] is a directed bipartite graph with two types of nodes places nodes and transitions nodes. Directed arcs are used to connect places to transitions and vice versa. Places represent pre-condition and post-conditions whereas transitions are used to represent actions. Places my contain tokens represented by black dots. The state of the PN is determined by its marking which represent the number of tokens in each place. The modeling with PN offers many advantages such as the possibility to validate certain properties likes vivacity, re-initialization, freedom from deadlock, etc. Tokens are used to define the execution of a net.

There are several extensions of Petri Net where Colored Petri Net [19] is one of Petri net extensions. In contrast to ordinary PN, in which a token are uniform, CPNs can carry complex information by allowing data typing (color sets) and sets of values for each place. The notion of data associated to tokens, offers more natural, flexible and compact description to model many complex systems such as context-aware systems. In the other hand, adding the hierarchical aspect to PN allows complex systems to be naturally represented in a hierarchical manner as a set of sub-modules.

In this paper, we propose an approach based on Hierarchical Colored Petri Net formalism to model and monitor tasks plan. A Plan is a sequence of actions that refer to contextual situation. The planning problem representation is formed by a description of the world, a description of the goal and a description of the possible actions [8]. We define a Context-Aware Task Plan Net $\Pi$ as a connected acyclic marked graph. Transitions are used to represent tasks (elementary/abstract). Elementary transitions are depicted by simple bars and abstract ones are depicted by double bars. Places depicted by circles are used to represent tasks states (pre-conditions and post-conditions). Figure 2 shows an example of Hierarchical net.

Figure 2.

Hierarchical net.

3.1.1 Context modelling

To enable the context-aware planning, the first step is to present the planning domain. Presenting context is crucial in any context-aware planning. As it was mentioned in [16], we argue that contextual information are no more than environmental information often called world state or belief stat (contextual information). Consequently, we present context information in terms of context variables. In what follow, we give some important representations and concepts definition used in our approach. We consider the planning problem as relation between states and actions, so some of the following definitions are adopted from a set-theoretic planning domain [24] which is basically based on two notions, belief states and actions.

Definition 1. Context as color set.

Our representation of context is equivalent to a classical planning representation [24]. So the context is represented as a set of variables mapping to a finite domain of values. With the flexibility of token definition, we argue that CPN is a suitable model to represent context and to reason about. Hence a context is a finite and non-empty set of data types, modeled as color sets or colors, this set is noted by $\Sigma$ .

Definition 2. World state variables.

The environment is a collection of context which is modeled as a set of discrete variables. Each variable is a tuple (Vi, Val) such as:

•
TYPE $[V]\in\Sigma$ ;
•
Val takes values in its domain:

$\displaystyle\textit{DOM (Vi)}.\varepsilon=\forall i\otimes V_{i},$ (1)

3.1.2 Plan modeling

Definition 3. Task plan net.

The sequence of agent tasks in multi-agent systems is described by plans. Based on Colored Petri Nets formal definition [19], we define the Task Plan-Net as a connected acyclic graph having the following structure $\Pi=(P,T,A,\Sigma,V,C,CF,E,G)$ , where:

•
P: A finite set of places denote the states within a plan.
•
$T=T_{e}\cup T_{a}\cup T_{o}$ a finite set of transitions, partitioned in three sets; $T_{e}$ : elementary transitions, $T_{a}$ ; abstract transitions. $T_{e}$ and $T_{a}$ denote both tasks of the plan. $T_{o}$ : is a set of transitions used as operator to build the net.
•
$A$ : A finite set of arcs linking places and transitions such as $A\sqsubseteq P\times T\cup T\times P$ .
•
$\Sigma$ : Is a finite and non-empty set of data types, also called color sets or colors to define context.
•
$V$ : Is finite set of typed variables representing world state variables such as: TYPE [V] $\in\Sigma$ ;
•
CF: Is a color set function. It assigns a color type (set) to each place: $P\to\Sigma$ ;
•
E: A $\to$ Expression (a) of type C (p(a)), is the arc function. It maps each arc to an expression called an arc expression such

$\displaystyle\forall a\in A:[\mathrm{Type}(E(a))=C(p(a))_{MS}\wedge\mathrm{% Type}(\mathrm{Var}(E(a)))\subseteq\Sigma]$ (2)

where $p(a)$ is the place of $N(a)$ ;
•
$G$ : Is a guard function. It assigns a guard to each transition. It is defined from $T$ into Boolean expressions such that

$\displaystyle\forall t\in T:[\mathrm{Type}(G(t))=\mathrm{boolean}\wedge\mathrm% {Type}(\mathrm{Var}(G(t)))\subseteq\Sigma]$ (3)

Definition 4. Initial configuration.

The initial configuration is modeled by one or more sources places $Pi\in P$ . $P i$ is the source place (initial place) of the net such as:

$\displaystyle\begin{cases}\text{$\bullet$ $Pi=$ \'{\O} (Ps does not have any % incoming arc);}\\ \text{Each node (place/transition) $\in P\cup T$/\{$Pg,Pi$\} has a path from $% Pi$.}\end{cases}$ (4)

Definition 5. Goal configuration.

The goal configuration is modeled by one (or more) end place (s) $Pg\in P$ . $P g$ is the end place in the net such as:

$\displaystyle\begin{cases}\text{$\bullet$ $Pg<>$ \'{\O} and $Pg$ $\bullet=$ \'% {\O} (Pg does not have any out coming arc);}\\ \text{Each node (place/transition) $\in P\cup T$/\{$Pi,Pg$\} has a path to $Pg% $.}\end{cases}$ (5)

Definition 6. Enabled tasks.

Each task plan $T_{n}$ is denoted by a transition in the net. Elementary transitions are used to denote elementary tasks handled by the planning agent. However, abstract ones are used to denote composed tasks needed to be refined or accomplish by other agents.

A task modeled by a transition $t$ is enabled if each place $p_{i}$ (i.e. $(p_{i},t_{i})\in A)$ has token with appropriate colors satisfying constraints that are specified on input arcs $w$ ( $p_{i},t_{i}$ ). Abstract transition is enabled if $p_{i},p_{ia}^{\prime}$ have appropriate tokens, meaning respectively that all environmental precondition (context) of this task are valid (token in $p_{i}$ ), and there is an agent how handle this task (token in $p_{ia}$ ) see Fig. 3a. Note that for elementary transition like $t_{i}$ in Fig. 3b, the place $P_{ia}^{\prime}$ is omitted, since the executor agent is the agent itself.

Figure 3.
Enabled task: (a) elementary transition, (b) abstract transition.

Definition 7. Firing transition.

An elementary transition fires if:

(ii) (i)
It is enabled,
(ii)
The task $t_{i}$ has successfully been executed. The successfully execution of elementary tasks is modeled by putting tokens in place $p_{ia}$ (or generating event on transition $t_{i}$ ).

3.2 Tasks allocation and coalition formation

Task allocation problem in dynamic systems such as ambient intelligent ones, is the problem of assigning a set of tasks to a set of agents, where the agents can enter and leave the system over the time. The contract net protocol is suitable to deal with this opening and dynamic. In this section, we describe the use of resulted model in conjunction with contract net protocol to form the collaborative agent networks.

Contract net protocol [29] enables dynamic and recursive distribution of tasks and resources in an open network of agents and determining their organizational structure. Agents in contract net protocol may play two roles: manager or bidder. For each task the manager searches for bidders to do it. A bidder tables bids to the manager. The manager after evaluating all received bids chooses the most suitable bidder and awards the contract to it.

The contract net protocol is a broadly applicable mechanism and it is one of the important paradigms developed in distributed artificial intelligence for decentralized task allocation. This algorithm has the advantages of conceptual simplicity and proven effectiveness in many real-world applications. However it lacks a formal model for performing bidding and awarding decision. To cover this shortfall, the adoption of Petri nets formalism seems a suitable solution [17].

In applying contract net protocol, we consider that each tasks has to be allocated to only one agent, however an agent can carried out more than one task of tasks plan model. We note that each task and all proposals submitted by agents are also modeled with colored Petri nets.

3.2.1 Call for proposals and bidder’s proposal models

We assume that each proposal concern one task (Fig. 4a). Proposal net and bidder’s proposals net have the following structure: an initial state $P_{ia}$ to denote the allocation of the task to an agent, a transition denoting the tasks to be performed, and a final state denote the termination of the task. Each bidder’s proposal net is denoted by BPN ${}_{i}$ . Figure 4b depicts an example of bidder’s proposal. Bids may contain many attributes characterizing the tasks. Details about each bid (including identifier of the agent that will perform the task) are described by tokens as a set of attributes in $P_{ia}$ place (Fig. 4b).

Figure 4.

Call for proposals and bidder’s proposal models; (a) BPN: bidder’s proposal net, (b) call for proposal.

3.2.2 Collaborative tasks plan model

The Collaborative Tasks Plan model (Fig. 5c) is obtained by merging all selected bidder’s proposals nets (Fig. 5a) and the tasks plan net (Fig. 5b). The Collaborative Tasks Plan net is no more than tasks plan net having additional coordination places ( $P_{a1},P_{a2},\ldots P_{an}$ ) instantiated with the result of contract net protocol. Planner agent uses the Collaborative Tasks Plan net to verify and analyze plan features before execution. A plan is feasible if goal can be reached and liveness property is maintained.

Definition 8. Collaborative tasks plan.

We obtain the Collaborative Tasks Plan model by merging i) all transitions having the same label into one transition, and ii) all the places having the same label into one place whose marking is equal to the sum of markings of these places. We use the operator to denote the merging of two or more Petri net models;

$\mathrm{CTPN}=\oplus(\mathrm{TPN;BPN1;BPN2}\ldots;\mathrm{BPNn})\hfill\text{(6)}$

Figure 5.

Merging tasks plan model and proposal models; (a) selected bid’s net, (b) tasks plan net, (c) collaborative tasks plan net.

3.3 Net analysis and monitoring

The proposed Task Plan Net is appropriate to handle the following assumptions, usually needed in many multi-agent societies:

•
Each agent has incomplete information about the world,
•
Data and capabilities are distributed over agents composing the whole system,
•
Since each agent has a limited point of view and limited capabilities, they must collaborate to achieve a global goal,
•
There is no global system control.

Having represented the plan into an equivalent Task Plan Net model, we now discuss how to use the obtained net to monitor plan execution.

The state of the plan is given by the marking of the plan net. The marking of places is updated by monitoring the environment conditions, and/or by firing transitions (means tasks execution).

Each agent monitors a sub plan modeled by a sub net, including a set of tasks for which it is responsible for (no global system control). Plan execution monitoring is realized by controlling the sequences of firing via token passing over the net. State of sub plan execution is communicated with the direct supervisor agent in the hierarchy (Fig. 6 step 2). Obviously, to communicate with appropriate agent, each agent maintains knowledge about a part of its organization.

Figure 6.
Using task plan net to model and monitor plan.

The monitoring consists of the following repeated cycle:

(1) (1)
Create an instance of Task Plan net.
(2)
Put appropriate tokens in start places if necessary.
(3)
Fire the Petri net until no more transitions are enabled.
(4)
Examine the Petri nets and interpret the current result.

Abstract transitions represent composed tasks, or tasks assigned to other agents. Abstract transition fires if: 1) it is enabled, 2) the tasks T is successfully being accomplished by the executor agent. This latter condition is modeled by the reception of the event (confirmation message) from the executor agent to confirm that a task has successfully been executed.

Firing an enabled transition $T$ , consume $w$ ( ${pi,t}$ ) tokens from each input place ${pi}$ and produce w ( ${t,po}$ ) tokens on each output place po such that ( ${t,po}$ ) $\in F$ . The net is in terminal state when there is no enabled or fired transition.
4. Illustrative scenario: Smart home healthcare system

Ambient intelligence can be applied in any dynamic environment where there is a need to manage tasks and automate services (e.g., hospitals, schools, homes, offices). Home is one of the ideal places to apply ambient intelligence vision. Smart homes represent the ideal solution for individuals with different needs and abilities (e.g. child, old, blind, People with reduced mobility). One of the main expected benefits of this technology can be Increasing safety, e.g., by automating specific tasks that old persons or individuals with disabilities can’t perform them, offering a permanent peoples monitoring, and so on. In this section we try to illustrate our approach through smart home healthcare systems, a simple typical example that requires a context aware multi-agent planning and highlight the essential points proposed in our approach.

4.1 Scenario

Let us consider the following situation; Adam, the owner of the home, is an elderly person living alone and suffering from many chronic diseases. The home is equipped with smart devices and sensors forming an ambient intelligence system embedded to monitor the health state of this person. The system detects the following anomaly information: the person is hypoglycemic (i.e., the glucose level is too low). This critical situation claim an automated planning process, that: i) call an emergency center (this task is represented by a transition T2 ii) inform the closest family member or friend (represented by transition T1), iii) the Emergency medical personnel staff offers an emergency pre-hospital medical care services and move the patient to the hospital if necessary (represented by transition T3). As we can see, this situation needs the intervention of many entities, each one has a limited point of view and limited capabilities; accordingly they must collaborate to achieve a global goal. However, all collaborated agents must communicate to direct supervisor agent some relevant information about their partial plan in which they are responsible. Planning agent has to collaborate with other agents to accomplish the tasks T1, T2 and T3. T1, T2, T3 are represented by abstract transitions, since they will be allocated to other agents having the required knowledge and capacities to carry out these sub-goals. Two synchronization transitions T0, T4 are added to denote the starting and the terminating events of plan. The transitions of Fig. 8 are listed in Table 1.

4.2 Plan modeling

Figure 10a shows the initial Task Plan model (first level of abstraction) of the above described situation (created and simulated using CPN Tools1). This net is defined as follows: $P=$ {P1, P2, P3, P4}, $T=$ {T0, T1, T2, T3, T4}, $A=$ {(P1, T0), (T0, P2), (T0, P3), (P2, T2), (P3, T1), (T1, P6), (T2, P4), (P4, T3) (T3, P5), (P5, T4), (T4, P7)}. Note that transitions T1, T2, T3 are abstract ones; they represent tasks which will be allocated to other agents.

$\Sigma=\{\textit{US, Task, Agent, user},\ldots\textit{etc}\}$ , is a set of color set for this model, such as, User color represents the user name. S color represents the current situation. US color is used to represent user situation, tokens of this color hold information including user name and the current detected situation (context information). Agent color represents agent identification. Task color includes a set of attributes to describe each abstract task. An overview of the net declaration section is given in Fig. 8c.

Table 1
Transitions meaning

T0	Synchronization transition
T1	Call his family
T2	Call emergency center
T3	Examine the person and make decision
T4	Synchronization transition

Figure 7.

Selected bid’s nets.

4.3 Forming and analyzing of collaborative tasks plan net

To achieve tasks denoting by the abstract transitions T1, T2 and T3, planning agent tries to map from a set of these tasks to the set of agents. Applying the contract net protocol, the planning agent plays the role of a manager and searches for bidders to do each composed task. A bidder tables bids to the manager. The manager, after evaluating all received bids chooses the most suitable bidder and awards the contract to it. Three agents; Ag2, Ag3, Ag4 have been selected to execute respectively T1, T2 and T3. Figure 9 illustrates the three selected bids using colored Petri nets.

The places P’2a, P’3a and P’4a encapsulate information about an agent who will refine or execute the abstract transition. This information is represented as token containing agent identification, task identification; The marking of these places is given as follows: $M(P_{a1})=$ 1’ (“Ag2”, “T1”, “Affected”), $M[P_{a2}]=$ 1’ (“Ag3”, “T2”, “Affected”), $M[P_{a3}]=$ 1’ (“Ag4”, “T3”, “Affected”).

We are now forming the collaborative task plan by merging the three proposed bids in Fig. 7 with the task plan of Fig. 8a. The obtained net will be verified and analysis before awarding contract agents Ag2, Ag3 and Ag4. The obtained net is given in Fig. 8b.

Figure 8.

Task plan model (first level of abstraction); (a) the task plan net, (b) the collaborative task plan, (c) the corresponding declarations in CPNTools.

Figure 9.

Task plan model: second level of abstraction.

4.4 Plan monitoring

After creation of the Task Plan model, planning (Ag1) puts the current contextual information as a token into a start place of CPN model (initialize the net). Ag2, Ag3 and Ag4, in their turn, create their local plans net. Each local plan model contains details about how accomplishing T1, T2 and T3 (Fig. 9b, c, d).

Note that each task plan has one ready state, one finished state and several processing states. For example, the Petri net model for step 1 consists of one ready state (P1); one finished state (P7) and following processing states (P2, P3, P4, P5, P6).

Each agent maintains and monitors just its local plan which represents a part of global one. The monitoring consists of interpreting the current marking net. All plan models now are generated, the execution is triggered. The beginning of the execution is denoted by putting tokens in starting places.

The marking of starting stats is: M (P1,P2, Pa2, Pd2, P3, Pa3, Pd3, P4, Pa4, Pd4, P5, P6, P7) $=$ ((“Adam”, “H-Hypoglycemia”), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0). By putting a token 1’ (“Adam”, “H Hyphoglismia”) in P1, Two tokens will be produced in both P2 and P3 (Fig. 9a). Coordination is realized by passing messages. Fairness of T1 and T2 are conditioned by putting tokens in Pa1 and Pa2. Changing the marking of the places Pa1 and Pa2 is conditioned by reception of messages from executor agents (respectively Ag2 and Ag3) to confirm that T1 and T2 have successfully been executed. Likewise, fairness of T4 is conditioned by receiving a confirmation message from Ag4. Fairing all the transitions in the net and having a token in final state denote that the goal has been successfully achieved.

5. Discussion

One of the major strengths of Petri nets is that allows analysis of many properties of modeled systems. Analysis permit to prove that certain required properties are satisfied (e.g liveness, reachability of a specific marking) or some undesired ones are absent (e.g., deadlocks). Based on their formal representation, it is possible to check at run-time the soundness property. The plan net is sound if: i) all generated tasks remain executable starting from initial state; ii) the plan is finite and iii) the plan is feasible.

The first requirement is guaranteed by verifying liveness property of the net. A net is said to be 1-live if every transition can become enabled and fired from the initial marking $M_{0}$ through some firing sequences at least one time. The plan is finite means that each task is not performed infinitely, or the execution is authorized for some specified number of times. In our presented example, all tasks should not be performed more than once. Regarding the acyclic structure of Context-Aware Task Plan Net, the finiteness of the plan can be checked based on boundness property. the net is k-bounded if $\forall p\in P,M(p)\leqslant k$ , i.e., no matter what will be the evolution of the net, the number of tokens in each place does not exceed the finite number $k$ . which means that all the markings (set of states) which can be reached from the initial marking by firing transitions are finite. A plan is feasible if the goal state denoted by MG marking is reachable. MG, is the only acceptable dead marking which corresponds to the state in which the plan is completely executed. MG is reachable if a firing sequence exist, from initial marking M0 to MG denoted by M0 [ $\sigma$ M0. With respect to our plan net, the goal marking is MG ((P1, P2, Pa2, Pd2, P3, Pa3, Pd3, P4, Pa4, Pd4, P5, P6, P7) $=$ (0, 0, 0, 1’ (“Call emergency center”, “Ag2”, “Ececuted”), 0, 1’ (“call family”, “Ag3”, “Ececuted”), 0, 1’ (“examine patient”, “Ag5”, “Ececuted”), 0, 0, 0, 1‘ (“Adam”, “secured”))).

Table 2
Summary of the related work

	Ambient intelligence	MAS-planning	Plan monitoring	Tasks allocation	Variant of petri nets	HTN approach
[6]	$-$	$+$	$+$	$-$	$+$	$+$
[17]	$-$	$-$	$-$	$+$	$+$	$-$
[25]	$+$	$+$	$-$	$-$	$-$	$-$
[5]	$+$	$+$	$-$	$-$	$-$	$-$
[2]	$+$	$+$	$-$	$-$	$-$	$+$
[32]	$+$	$-$	$-$	$-$	$+$	$-$
[7]	$+$	$-$	$-$	$-$	$+$	$-$
[26]	$+$	$-$	$-$	$-$	$+$	$-$
[14]	$+$	$-$	$-$	$-$	$+$	$-$
Our approach	$+$	$+$	$+$	$+$	$+$	$+$

Figure 10.

An extract from CPN tools state space report.

These properties can be verified using state space method [19]. The generated state space report under CPN tools shows that the obtained model satisfy the required properties, indeed, the model is bounded, reachable, and no “dead transition is detected. An extract from a state space report is shown on Fig. 10.

This paper demonstrates how to use Petri nets for context-aware multi-agent planning. Context-awareness refers to an application’s ability to adapt to changing circumstances and respond based on the context of use. In the existing literature, different methodologies for the design of context-aware systems have been proposed. Although some works like [7, 14, 32, 26] have already proposed Petri net based context modeling approach, our work is differentiated from them. In this work we focus on planning ability and we address different and/or additional issues, e.g. task allocation among agents or plan monitoring.

A highly dynamic and open system necessitates run-time analysis, validation and monitoring of systems behaviors. The major benefits of our approach lie in the formal foundation of Petri nets. The formal definition of the execution semantics allows the monitoring of the global/local plans. By using Petri nets, plan execution is monitored through tracking the net marking and interpreting it. Similar to our approach, [2, 25, 5]focused on planning ability for ambient intelligence environment. However, we note that none of them has addressed the plan verification or monitoring problem.

Furthermore, unlike these approaches[2, 25, 5] our approach offers the possibility of using the resulted models in allocating tasks to agents and forming the collaborative agent networks. Similar to our proposed approach, [17] combined the capability of collaboration and coordination offered by contract net protocol with the advantages of Petri net theory in the modeling and analysis concurrent, synchronous and/or asynchronous activities. The aim of the work presented in [17] was to augment the contract net framework with a cooperation mechanism. Hence, they focused only on cooperation mechanism for manufacturing systems instead of planning. Finally, we point out that the formal foundation of our approach make the extension possible to address others issues, e.g. how to efficiently use the available agents and their resources (such as energy reserves) when allocation tasks to agents.

Table 2 summarizes the common axes between our work and the works explored in this section and including others mentioned in Section 2. To the best of our knowledge, none of the existing approaches considered all of these topics. The novelty of this work is the combination of all the topics into the same framework. In this paper, we focus on planning ability; we define a Task Plan Net based on hierarchical colored Petri nets modeling language to model and monitor plans. We show how the proposed scheme allows agents to cooperate to achieve a global plan in agent-based ambient systems. Then we use the resulted plan model in conjunction with contract nets protocol to form the collaborative tasks plan net. This latter allows planner agent to verify the main properties of the plan, and to talk relevant information about its evolution and about a set of agents involved on.

6. Conclusion and future work

Supporting users in their daily lives by creating digital environment that react in smart, proactive and transparent manner is becoming more and more important in our days. Collecting and representing contextual information and reasoning techniques are important to build such systems. In this paper, we have proposed a context multi-agent planning approach for ambient intelligence environments. We have defined a Task Plan Net based to model contextual information and reason about. Hierarchical aspect of plan allows a dynamic decomposition of a global plan in a distributed manner through many levels of abstraction and among several collaborative agents. By this way, we allow the planning agent, running in partially known environments, to built incomplete plans now, and searching for other agents to be responsible of part of planning problem. To find these agents, contract net protocol has been adopted in this work. The contract net protocol has proven to be effective in a wide range of real-world applications. It enables dynamic and recursive distribution of tasks and resources in an open network of agents. So we think that it is a suitable technique that can deal with the openness of ambient intelligence systems, where the number and type of agents (devices) can change continuously in the system.

Petri Net formalism and its extensions have also been successfully used for modeling and analysis behavior of various complex dynamic systems. Adopting such formal formalism for plan modeling is suitable, since it allows the verification of some interesting properties of the generated plan. Other benefit is the possibility to monitor plan evolution. Plan monitoring is needed in open and dynamically changing environments such as those proposed by the ambient intelligence paradigm. Execution monitoring is so needed to deal with new discovered information providing conflicts between planning decisions and environmental reality.

In this paper we have focused on how representing and monitoring plan. There are some issues that need further consideration. One of the challenging issues is how to expend the proposed approach to deal with the challenges represented by dynamic changes in contextual information. How the planner computes the relevant changes of the environment regarding the current plan to decide whether a plan net repair is needed [13], and how a plan net repair process can be addressed, are still open problems.

Footnotes

CPN Tools: http://cpntools.org/.

Authors’ Bios

Houda Haiouni is an assistant professor at University of Mentouri-Constantine 1 (Algeria). She has received her Master degree in computer science from the University of Constantine – Algeria, in 2010. At present, she is a PhD candidate in the LIRE Laboratory (Constantine 2 University – Algeria). Her research interests include: ambient intelligence, multi-agent systems, formal methods and eHealth.

Ramdane Maamri is a full Professor of Computer Science at University of Constantine 2, Algeria. He received his master from the University of Minnesota, USA and his Ph.D in computer science from university of Mentouri Constantine, Algeria. He has participated in a lot of national and international research projects and supervised a lot of masters and Ph.D students. He is currently the head of software technologies and information systems department at university of Constantine 2. His research interests include software engineering, verification and validation, web services, multi-agent systems and ambient systems.

References

Abowd

G.D.

Dey

A.K.

Brown

P.J.

Davies

Smith

and Steggles

, Towards a Better Understanding of Context and Context-Awareness, in: Proceedings of the 1st International Symposium on Handheld and Ubiquitous Computing. London, UK, UK: Springer-Verlag, (1999), 304–307. (HUC 99). Available from: http://dl.acm.org/citation.cfm?id=647985.743843.

Amigoni

Gatti

Pinciroli

Roveri

, What planner for ambient intelligence applications? IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans 35(1) (Jan 2005), 7–21.

Bauer

Kutsche

R.D.

and Ehrmanntraut

, Identification and modeling of contexts for different information scenarios in air traffic, Technische Universita, Berlin, Diplomarbeit (2003), 1–104.

Bettini

Brdiczka

Henricksen

Indulska

Nicklas

Ranganathan

et al., A survey of context modelling and reasoning techniques, Pervasive and Mobile Computing 6(2) (Apr 2010), 161–80.

Bidot

and Biundo

, Artificial Intelligence Planning for Ambient Environments, in: Next Generation Intelligent Environments. Springer, New York, NY, (2011), 195–225.

Brahimi

Maamri

and Sahnoun

, Hierarchical Multi-Agent Plans Using Model-Based Petri Net, International Journal of Agent Technologies and Systems (IJATS) 5(2) (2013), 1–30.

Kwon

O.B.

, Modeling and generating context-aware agent-based applications with amended colored Petri nets, Expert Systems With Applications 27(4) (2004), 609–21.

de Weerdt

and Clement

, Introduction to planning in multiagent systems, Multiagent and Grid Systems 5 (2009), 345–355.

Dey

A.K.

, Understanding and Using Context, Personal Ubiquitous Comput 5(1) (Jan 2001), 4–7.

10.

Dey

A.K.

Abowd

G.D.

and Salber

, A conceptual framework and a toolkit for supporting the rapid prototyping of context-aware applications, Human-Computer Interaction 16(2–4) (Dec 2001), 97–166.

11.

Erol

Hendler

and Nau

D.S.

, HTN planning: Complexity and expressivity, in: Proceedings of the Twelfth National Conference on Artificial Intelligence, Menlo Park, CA, USA: American Association for Artificial Intelligence, (AAAI’94), 1994, pp. 1123–1128.

12.

Ferber

, Multi-agent systems: An introduction to distributed artificial intelligence, Harlow: Addison-Wesley, 1999, 509.

13.

Haiouni

and Maamri

, Context-aware planning for intelligent environments, in: International Conference on Advanced Aspects of Software Engineering (ICAASE). Presented at the 2016, International Conference on Advanced Aspects of Software Engineering (ICAASE), 2016, pp. 1–5.

14.

Haiouni

and Maamri

, Context-aware automatic service selection mechanism for ambient intelligent environments, in: Ambient Intelligence – Software and Applications Novais

R.C.P.

Nihan

C.E.

Corchado Rodríguez

J.M.

, eds, Cham: Springer International Publishing, (2014), 1–11.

15.

Han

and Youn

H.Y.

, Petri net-based context modeling for context-aware systems, Artif Intell Re 37(1) (1 Jan 2012), 43–67.

16.

Heinrich

and Schön

, Automated planning of context-aware process models, Twenty-Third European Conference on Information Systems (ECIS), Münster, Germany, (26–29 May 2015), 422–431.

17.

Hsieh

F-S.

, Developing cooperation mechanism for multi-agent systems with Petri nets, Engineering Applications of Artificial Intelligence 22(4–5) (Jun 2009), 616–627.

18.

Jennings

N.R.

and Wooldridge

M.J.

, eds, Agent technology, Berlin, Heidelberg: Springer Berlin Heidelberg, 1998.

19.

Jensen

and Kristensen

L.M.

, Coloured petri nets, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.

20.

Eckert

Martinez

J-F.

and Rubio

, Context aware middleware architectures: Survey and challenges, Sensors 15(8) (20 Aug 2015), 20570–607.

21.

Lopes

Benevides

and Haeusler

E.H.

, Reasoning about multi-agent systems using stochastic petri nets, in: Trends in Practical Applications of Agents, Multi-Agent Systems and Sustainability Bajo

Hernández

J.Z.

Mathieu

Campbell

Caballero

F.-A.

Moreno

M.N.

, et al., eds, Cham: Springer International Publishing, 2015, pp. 75–86.

22.

McCarthy

, Notes on formalizing contexts, in: Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, San Mateo, California Bajcsy

, ed., Morgan Kaufmann, 1993, pp. 555–560.

23.

Murata

, Petri nets: Properties, analysis and applications, Proceedings of the IEEE 77(4) (Apr 1989), 541–80.

24.

Nau

Ghallab

and Traverso

, Automated planning: Theory & practice. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2004.

25.

Pajares Ferrando

and Onaindia

, Context-aware multi-agent planning in intelligent environments, Information Sciences 227 (Apr 2013), 22–42.

26.

Riahi

and Moussa

, A formal approach for modeling context-aware Human – Computer System, Computers & Electrical Engineering 44 (May 2015), 241–261.

27.

Schilit

Adams

and Want

, Context-aware computing applications, in: IEEE, 1994, pp. 85–90. Available from: http://ieeexplore.ieee.org/document/4624429/.

28.

Schmidt

Beigl

and Gellersen

, There is more to context than location, Computers and Graphics 23 (1998), 893–901.

29.

Smith, The contract net protocol: High-level communication and control in a distributed problem solver, IEEE Transactions on Computers, (Dec 1980) C–29(12) 1104–13.

30.

Strang

and Linnhoff-Popien

, A context modeling survey, in: Workshop on Advanced Context Modelling, Reasoning and Management, UbiComp 2004 – The Sixth International Conference on Ubiquitous Computing, DLR Electronic Library, 2004, pp. 31–41.

31.

Uschold

and Gruninger

, Ontologies: Principles, methods and applications, The Knowledge Engineering Review 11(2) (Jun 1996), 93.

32.

Wang

and Zeng

, Modeling analysis for workflow constrained by resources and nondetermined time: An approach based on petri nets, IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans 38(4) (Jul 2008), 802–817.

Context-aware multi-agent planning in intelligent environments

Abstract

Keywords

1. Introduction

2. Literature review

3. Plan modeling and monitoring approach

• TYPE [ V ] ∈ Σ ; • Val takes values in its domain: DOM (Vi) . ε = ∀ i ⊗ V i , (1) 3.1.2 Plan modeling

3.2.1 Call for proposals and bidder’s proposal models

4.1 Scenario

4.2 Plan modeling

Table 1 Transitions meaning

5. Discussion

Table 2 Summary of the related work

Footnotes

Authors’ Bios

References

•
TYPE $[V]\in\Sigma$ ;
•
Val takes values in its domain:

$\displaystyle\textit{DOM (Vi)}.\varepsilon=\forall i\otimes V_{i},$ (1)

3.1.2 Plan modeling

Table 1
Transitions meaning

Table 2
Summary of the related work