Formal specification of agent behaviour through environment scenarios

Formal Specification of Agent Behaviour through Environment Scenarios Hong Zhu School of Computing and Mathematical Sciences, Oxford Brookes University Gipsy Lane, Headington, Oxford, OX3 0BP, England hzhu@brookes.ac.uk, Tel:++44 1865 483670, Fax:483666 Abstract. Scenarios are typical situations that may occur in the operation of a software system. Scenario analysis plays an important role in software requirements analysis and design. This paper introduces a formal notation for the specification of scenarios in agent-based systems. The autonomous and collaborative behavior of an agent can be formally specified by a set of rules describing its activity in various scenarios. The power of the approach is illustrated by the formal specification of Maes` personal assistant agent Maxims. The paper also shows that agents` social behavior, such as speech act, can also be formally specified as scenario-reaction rules. 1 Introduction Being autonomous, proactive and adaptive, an agent-based system may demonstrate emergent behaviours, which are neither designed nor expected by the developers or users of the system. Whether or not such emergent behaviours are advantageous, methods for the specification of agent behaviours should be developed to enable software engineers to analyse the behaviour of agent-based systems. The past few years have seen a rapid growth in the research on formal models of agent-based systems specified in various formalisms and logics, such as temporal logics, first order logics, and game theories, etc., see e.g. [1, 2, 3]. However, there are few researches on the language facilities and features that support the formal specification and verification of agent-based systems, although efforts have been made to define new formal specification languages, for example, LW [4], DESIRE [5] and ETL [6]. This paper reports our research in progress on a formal method for the specification, proof and analysis of the behavior of agent-based systems. The basic idea is to specify an agent`s behaviour by a set of rules that govern its reactions to various scenarios in its environment. A formal specification language, called SLAB, is being designed to facilitate such formal specifications and analysis of multi-agent systems. Instead of giving a complete definition of the language, this paper presents the language facilities that we identified and the rationale behind the design decisions. We also illustrate by examples the use of the facilities in the specification of autonomous and collaborative behaviors of multi-agent systems. 1 2 SLAB – A Formal Specification Language of Agent Behaviour It is widely recognised that formal methods are difficult to scale up. Modularity and composibility are among the solutions to this problem advanced in the literature. The question is then what are the `modules` in a formal specification of an agent-based system and how to compose them together into a system. In search for an answer to these questions, we turned to more fundamental questions like what is the essence of agent-based computing and what makes agents an appealing and powerful approach. As Jennings pointed out [7], such questions can be tackled from many different perspectives ranging from the philosophical to the pragmatic. In the design of the SLAB language, we have taken a pragmatic approach in order to obtain a practical solution. We are concerned with the language facilities that support the specification and reasoning of agent-based systems from a software engineering point of view. In this section, we discuss how such a view led to our design decisions. 2.1 Agents as Encapsulations of Behaviour Of course, agent is the most basic concept of agent-oriented or agent-based computing. Although there is much debate about exactly what constitute agenthood, we believe that Jennings` definition represents a common view from many researchers. It reads `an agent is an encapsulated computer system that is situated in some environment, and that is capable of flexible, autonomous action in that environment in order to meet its design objectives` [7]. According to this definition, an agent is an entity that observes its environment and takes its action (or reaction) according to its internal state, which can be driven by its believe, desire and intention and to follow a plan to achieve a specific goal. Thus, agents are active and persistent. They execute concurrently and autonomously. Therefore, an agent has a set of variables represents its internal state and a set of actions it can take. Being an active entity, an agent`s internal state is persistent in the sense that there is always a value bound to the variables. In contrast, actions are temporal in the sense that it is possible that no action is taken at a particular time. Another difference between state variables and actions is that state variables can vary continuously as time changes. In other words, a state variable can be a function of time. To communicate with the outside world, an agent must have some actions that are observable by other agents, and be able to show its state to the outside world. For example, Maes` Maxims agents have facial expressions to communicate with the users. However, an agent also needs to be able to hide some of its internal state and actions. The state variables and actions are, therefore, divided into two types, those visible from the outside and those internal and invisible from the outside. The most important feature that distinct agents from objects in the object-oriented paradigm is the so-called autonomous behaviour. Although an object also has internal states and a set of actions (which are called methods in object-oriented terminology), it has no control over whether and when to take an action. A method must be executed when a message is received. In contrast, an agent can decide whether or not and when to take an action when a message is received or a certain event happens in the environment. Its capability of controlling over its internal state and action is the 2 characteristics of autonomous behaviour. In other words, an agent`s behaviour is determined by its design rather than by the environment. In this sense, we say that an agent is an encapsulation of states, action and behaviour, or shortly, an encapsulation of behaviour. We believe that the power of agent-oriented approach comes from the encapsulation of behaviour, which enable an agent to achieve its design objectives in dynamic and unknown environment by controlling its behavior and adapting its behavior according to the environment, rather than controlled by the environment. Therefore, in the design of an agent, the complexity of the problem due to the dynamic nature and unknown characteristics of the environment can be reduced to the minimum. This understanding of the concept of agent led us to the first design decision in the development of the formal specification language SLAB. That is, the basic building block in an agent-oriented specification language should be agent, which encapsulates four interrelated parts: (1) the specification of state space, (2) the specification of actions, (3) the specification of behaviour, and (4) the specification of the part of environment that it observes. The following gives SLAB`s syntax in EBNF of specifications of agents. It can also be equivalently represented in a graphic form similar to the schema in Z [8]. agent-description ::::== agent name [: { class-name,}] {instantiation}*; Visible state-variables and actions [ structure-description; ] Invisible state-variables and actions structure-description ::::== Environment Behaviour-specification [ Var {[ * ] identifier: type; }+ ] [Action {action}+] action ::::== [*] identifier; | identifier ({ [parameter:] type,}+) In SLAB, the state space of an agent is described by a set of variables with keyword VAR. The set of actions is described by a set of identifiers with keyword ACTION. An action can have a number of parameters. An asterisk before the identifier indicates invisible variables and actions. The power of agent-based system can be best demonstrated in a dynamic environment [9, 10] because an agent can adapt its behaviour into the environment to achieve its designed purpose. Therefore, the specification of an agent-based system must also specify how the environment affects the behaviour of the agent. To do so, we must first answer the question what is the environment of an agent. A simple answer to this question is that in a multi-agent system, the environment of an agent consists of a number of agents and a number of objects. However, having defined agents as encapsulations of behaviours, we regard object as a degenerated form of agent. The behaviour of an object is simply to respond to every message sent to the object by executing the corresponding method. Based on this understanding of the relationship, our second design decision is to specify a multi-agent system as a set of agents, nothing but agents. System ::= {Agent-description | class-description}* The environment of an agent is a subset of the agents in the system that may influence its behaviour. The syntax for the description of environments is given below. Environment-description ::= { name | All: class-name | variable : class-name }*, 3 where a name indicates a specific agent in the system. `All` means that all the agents of the class have influence on its behavior. A variable is a parameter in class specification. When instantiated, it indicates an agent in the class. 2.2 Classes of Agents as Birds of a Feather In object-oriented languages, a class is considered as the set of objects of common structure and function. Similarly, a class in SLAB is considered as a set of agents of same structural and behavioral characteristics. If an agent is specified as an instance of a class, it inherits the structure and behaviour descriptions from the class. However, in addition to those inherited structure and behaviour, an agent can also have additional behaviour and structure descriptions of its own. The syntax and graphic representation of class specification is given below. class-description ::::== Name <= Classes classi name i[ <= {class-name} ] Visible state-variables and actions [ environment-description;] Invisible state-variables and actions [ structure-description; ] end [ behavior-description; ] description Behaviour-specification For example, consider a system of mice in a maze. The maze consists of 10 by 10 squares. Each square can either be occupied by a rock or has a bean, or be empty. A mouse can move from one square to its adjacent square if the square is not occupied by a rock. It can pick up a bean if the square has a bean. The structure of the system can be specified by a class Mice and an agent Maze as below. The agent Maze represents the maze. It can be understood as the manager of the maze to up date the state of the maze when a mouse in the system picks up a bean. The specification of the dynamic behaviour will be given later. Maze VAR Bean: {1,..,10} ´ {1,..10} ® Boolean Rock: {1,..,10} ´ {1,..10} ® Boolean All: Mice Behavior-description Mice VAR Position: {1,..,10} ´ {1,..10} ACTION Pick-bean ({1,..,10}, {1,..10}) Move ({West, east, south, north}) Maze Behaviour-description As a template of agents, a class may have parameters. The variables specified in the form of “identifier: class-name” in the environment description are parameters. Such an identifier can be used as an agent name in the behaviour description of the class. When class name(s) are given in an agent specification, the agent is an instance of the 4 classes. The instantiation clause gives the details about how the parameters are instantiated. A class can also be defined as a subclass of existing classes by indicating the super-classes. A subclass inherits the structure and behaviour descriptions from its super-classes. It may also have some additional actions and obey some additional behaviour rules if they are specified in the subclass declaration. Some of the parameters of the super-class may also be instantiated in a subclass. As shown in section 3.2, the class and inheritance facilities provide a powerful vehicle to describe the normality of a society of agents. Multiple inheritances are allowed in the SLAB language to allow an agent to belong to more than one society and play more than one role in the system at the same time. 2.3 Scenarios as Patterns of Behaviours The notion of scenario has been used in a number of areas in computing with different meanings. For example, in UML, scenarios are described as the sequences of messages passing between the system and the objects that represent the users. In the application of scenarios in testing software requirements [11], a scenario is described as an activity list that represents a task of human computer interaction. Generally speaking, a scenario is a set of situations that might occur in the operation of a system [12]. No matter how scenarios are described, its most fundamental characteristic is to put events in the context of the history of behaviour. Here, in a multi-agent system, we consider a scenario as a set of typical combinations of the behaviours of related agents in the system. The use of scenarios and use cases in requirements analysis and specification has been an important part of object-oriented analysis, see for example, [13]. However, because an object must respond in a uniform way to all messages that call a method, there is a huge gap between scenarios and requirements models. The object-oriented paradigm is lack of a method to analyse the consistency between use cases (or scenarios) and requirements models and a method to synthesise requirements models from use cases or scenarios, although such methods exist for structured analysis [12]. As extensions to OO methodology, the use of scenarios in agent oriented analysis and design has been proposed by a number of researchers, for example [14, 15, 16]. In the design of SLAB, we recognised that scenarios can be more directly used to describe agent behaviour. The gap between scenarios and requirements models no longer exists in agent-based systems because the agent itself controls the its behaviour. Its responses can be different from scenario to scenario rather than be uniform to all messages that call a method. In SLAB, a basic form of scenario description is a set of patterns. Each pattern describes the behaviour of an agent in the environment by a sequence of observable state changes and observable actions. A pattern is written in the form of [p1, p2, ..., pn] where n³0. Table 1 gives the meanings of the patterns. pattern ::::== [ { event || [ constraint ] } ] event ::= [ time-stamp: ] [ action] [ ! state-assertion ] action ::::== atomic-pattern [ ^ arithmetic-expression ] atomic-pattern ::::== $ | ~ | action-variable | action-identifier [ ( { arithmetic-expression } ) ] 5 ... - tailieumienphi.vn