Towards a Generic Multiagent Model for Decision Support: Two Case Studies

Towards a Generic Multiagent Model for Decision Support: Two Case Studies* Sascha Ossowski1, José Luís Pérez de la Cruz2, Josefa Z. Hernández3, José-Manuel Maseda4, Alberto Fernández1, María-Victoria Belmonte2, Ana García-Serrano3, Juan-Manuel Serrano1, Rafael León2, and Francesco Carbone3 1

Dpt. of Computer Science, Universidad Rey Juan Carlos, Calle Tulipán s/n, 28933 Móstoles (Madrid), Spain {sossowski,al.fernandez,jserrano}@escet.urjc.es 2 ETSI Informática, Univ. Málaga Málaga, Spain {perez,mavi,leon}@lcc.uma.es 3 Dpt. of Artificial Intelligence, Technical Univ. of Madrid, Campus de Montegancedo s/n 28660 Boadilla del Monte (Madrid), Spain {phernan,agarcia,fcarbone}@isys.dia.fi.upm.es 4 LABEIN, Parque Tecnológico Edif. 101 48170 Zamudio (Vizcaya), Spain [email protected]

Abstract. This paper describes how agent and knowledge technology can be used to build advanced software systems that support operational decisionmaking in complex domains. In particular, we present an abstract architecture and design guidelines for agent-based decision support systems, illustrate its application to two real-world domains - road traffic and bus fleet management - and discuss the lessons learnt from this enterprise.

1 Introduction Decision Support Systems (DSS) provide assistance to humans involved in complex decision-making processes. Early DSS were conceived as simple databases for storage and recovery of decision relevant information [23]. However, it soon became apparent that the key problem for a decision-maker (DM) is not to access pertinent data but rather to understand its significance. Modern DSS help decision-makers explore the implications of their judgements, so as to take decisions based on understanding [12]. Knowledge-based DSS are particularly relevant in domains where human operators have to take operational decisions regarding the management of complex industrial or environmental processes [13,14]. Due to the inherent (spatial, logical and/or *

Work supported by the Spanish Ministry of Science and Technology (MCyT) under grant TIC2000-1370-C04.

R. Conejo et al. (Eds.): CAEPIA-TTIA 2003, LNAI 3040, pp. 597–607, 2004. © Springer-Verlag Berlin Heidelberg 2004

598

Sascha Ossowski et al.

physical) distribution of these domains, a distributed approach to the construction of DSS has become popular [1]. Decision-support agents are responsible for parts of the decision-making process in a (semi-)autonomous (individually) rational fashion: they collect and facilitate decision relevant data [23], but also provide advanced reasoning services to analyse the meaning of this information [19]. However, despite recent advances in the field of agent-oriented software engineering [15,17,24], a principled approach to the design of knowledge-based multiagent systems for decision support is still to come. This paper reports on an attempt to overcome this shortcoming. Section 2 introduces an abstract multiagent DSS architecture, and outlines how it is used to guide the construction of agent-based DSS. Section 3, describes its application to a problem of road traffic management in the greater Bilbao area, as well as its use for bus fleet management scenarios pertinent to the town Malaga. We conclude this paper summarising the lessons learnt and pointing to future work.

2 Agent-Based Decision Support: The SKADS Approach In this section we describe the Social Knowledge Agents for Decision Support (SKADS) approach for the design and application of DSS. In line with the Gaia methodology [25], SKADS first models agent-based DSS in terms of organisational concepts [8,26], that are then further refined, so as to give rise to an agent-centred model. SKADS is particularly concerned with issues of agent interoperability, so it follows closely the FIPA standard for agent systems [11], paying special attention to FIPA’s Agent Communication Language (ACL) and its abstract architecture [9]. In the sequel, we first outline the social and communicative roles that need to be supported by a DSS so as to cope with typical decision support interactions. Then, classes of agents are identified that should be present in any knowledge-based DSS. Finally, we come up with an abstract multiagent architecture and outline support for its implementation as DSS for particular domains. Organisational Model The key point in modern DSS is to assist the DM in exploring the implications of her judgements, so we first analyse typical “exploratory dialogues” between DM and DSS. Based on their (macro-level) functionality, we have identified the following types of social interaction [22] involving DSS: information exchange, explanation, advice, action performing. In DSS with multiple DM, additional brokering and negotiation interactions are often present, which identify potential partners to solve a given problem, and establish the conditions under which a certain action is performed, respectively. Roles usually describe different types of (micro-level) functionalities for classes of agents [25], so we introduce the concept of communicative rol to describe the communicative competence of agents in social interactions [21]. Communicative roles are characterised by the Communicative Actions (CA) [1] that they can perform (e.g.: an information seeker role is characterised by the FIPA CAs query-if, query-ref and subscribe), and may take part in one or more interaction pro-

Towards a Generic Multiagent Model for Decision Support: Two Case Studies

599

Table 1. Organizational Concepts for Decision Support. Type of Social Interaction Action performing

Communicative Role requester, requestee

Information exchange

informer, informee

Explanation Advice Negotiation (or: action performing II)

explainer, explainee advisor, advisee negotiation. requester, negotiation requestee

Brokering

Brokering requester, broker

Protocol FIPA-request-protocol FIPA-request-when- protocol FIPA-query-protocol FIPA-subcribe-protocol Explanation-protocol Advisory-protocol FIPA-Propose-protocol, FIPA-CNET-protocol, ... FIPA-brokering-protocol FIPA-recruiting-protocol

tocols. We have analysed FIPA ACL on the basis of these concepts, and determined the generic types of social interactions that it supports [22]. As Table 1 indicates, with respect to DSS there was only a need for extensions to Advice and Explanation interactions (and their respective communicative roles). Still, roles in agent-based DSS require domain competence as well, so we specialise communicative roles into social roles based on the elements of a domain ontology of which they inform, or that they explain. A minimum domain competence of a DSS will be centred on the following concepts: • system problems: identify situations with decision-making options (classification). • problem causes: express system problems in terms of causal features of the situation (diagnosis). • control actions: represent the various decision alternatives (action planning). • foreseeable problems: simulate potential consequences of decisions (prediction). Fig. 1 summarises our organisational analysis of knowledge-based multiagent DSS in UML notation. Agent Model Social roles need to be mapped onto types of agents that will eventually play these roles in the DSS. Especially for knowledge-based agent systems, it is important that this process adequately reflects the a priori distribution present in the particular DS domain [20]. Usually, both of the following cases are present: a. one role – several agents: In complex domains, it is often necessary (or desirable), to let different agents play the same role, but in different “parts” of a system. In this way, the agent model may better reflect a human organization, reduce communication requirements, or simply decrease the complexity of the necessary reasoning processes. b. one agent – several roles: Knowledge-oriented design approaches, such as KSM [4], suggest that some types of domain knowledge can serve a number of purposes, and therefore may be used by agents to play different roles. Obvi-

600

Sascha Ossowski et al.

Fig. 1. Communicative and Social Roles in DSS.

ously, it would make no sense to replicate such knowledge bases among different agents. Based on the social roles that we have identified previously, we have come up with the following agent types for DSS: • Data agents (DA): DAs play the informer role with respect to the current state of a certain part of the system. As such, it is in charge of information retrieval from different information sources like sensors or databases, and its distribution. • Management Agents (MA): MAs play the remaining informer roles as well as the advisor and explainer roles. By consequence, they need to be endowed with knowledge models that allow them to report on (and justify) problems, causes, potential future states etc, as well as to suggest potential management actions. • Action Implementation Agent (AIA): these agents play the requestee role and are in charge of actually executing the actions that the DM has chosen to take. • User Interface Agent (UIA): UIAs plays the remaining roles (informee, requester, etc.) on behalf of the user. Note that by conveniently sequencing and/or interleaving conversations, they are capable of answering a variety of questions (e.g., “What is happening in S?”, “What may happen in S if event E occurs?”, etc) [19]. Furthermore, notice that the finer the level of decomposition of social informer roles, the bigger the space of potential conversations that the UIA can engage in. The SKADS approach requires at least one instance of these agent types to be presented in the DSS but, due to different a priori distributions in corresponding problem domain (see above), often several instances of the aforementioned agent types will coexist. In DSS that support multiple decision-makers, additional Coordination Facilitators (CF) may be present; these are agents providing negotiation and matchmaking (recruiting, brokering) support [7].

Towards a Generic Multiagent Model for Decision Support: Two Case Studies

Conne ction Agents

Interface Agents

M anagem e nt Age nts

DA 1

UIA 1

...

MA1 MA2

DAk AIA 1

601

...

UIA 2

...

MAn AIA i

Pe riph eral Agents

...

UIA m

AM S

DF

...

PA 1

...

PA j

Fig. 2. SKADS abstract architecture.

SKADS Abstract Architecture and Platform Fig. 2 shows the resulting abstract agent-based DSS architecture according to the SKADS approach. Notice that, depending on the level of detail in the definition of social roles (e.g. informer for problems, diagnosis, prediction, etc.) and their subsequent mapping to agent types, the MAs may be subdivided into several agents. Also note that the abstract architecture shown in Fig. 2 comprises a set of so-called peripheral agents: this includes Directory Facilitators (DF) and an Agent Management Systems (AMS) as required by the FIPA abstract architecture [7], but may also include third-party peripheral agents (PA) that supply added value services [10]. We provide support for implementations of agent-based DSS for particular domains through extensions of the FIPA-compliant JADE agent platform [1]. Respecting the communicative part of social roles that DSS agents play, we supply a set of software components that encapsulate the corresponding dialogical behaviour for its use by JADE agents [22]. Regarding domain reasoning, we have encapsulated many of the knowledge presentation and inference schemes of the KSM knowledge modelling environment [4] (so-called knowledge units), and made them available to JADE [18]. Finally, we aim at rendering support for the implementation of coordination matchmaking and decision-making based on the results of [3].

3 Case Studies In this section we illustrate the instrumentation of our approach by two case studies in the domain of transportation management. The present research is the continuation of a long line of previous work in this field [4,6,10,13]. 3.1 The Road Traffic Management Domain We have used the SKADS architecture to develop a prototype DSS, aimed at assisting the operators at the Malmasin Traffic Control Centre in their task of managing

602

Sascha Ossowski et al.

traffic flows within the high-capacity road network of the Bilbao metropolitan area. Operators receive information about the current traffic state by means of loop detectors, and may decide to display messages on VMS panels above the road, so that drivers are warned about incidents and may avoid crossing congested areas. When applying the SKADS approach to this problem, we had to take into account that operators conceive the road network in terms of so-called problem areas, defined according to geographical criteria and one-way sense of traffic. As a result, the relation between the abstract architecture and the actual structure of the DSS prototype is as follows: • As many DAs as problem areas: Every DA is responsible for collecting the state information of the VMS panels and the data recorded by the loop detectors. It may complete and/or filter noisy data (e.g. due to transmission problems) making use of historical data series and transform the quantitative values observed into qualitative data (e.g. high speed, low occupancy). • Two kinds of MAs: problem detection agents (PDAs) and control agents (CAs). PDAs are responsible for monitoring the traffic flow in a problem area, understanding the traffic behaviour and detecting problems. If a problematic situation is detected from the analysis of the data sent by the corresponding DA, the PDA requests a CA to solve it. Every CA is responsible for solving/minimising problems detected by one or several PDAs and with this aim it can communicate with other PDAs to get information about the state of their problem area and diagnose the congestion. From the information obtained in the areas surrounding the congestion, the CA generates control proposals. A control proposal consists of a collection of messages to be displayed on VMS panels with warnings or recommendations for alternative routes for drivers approaching the congestion. When several congestions are detected and two or more CAs compete for the use of the same VMS panels, the corresponding CAs communicate to reach an agreement on a consistent joint proposal. • One UIA that interacts with the traffic operators in the control centre respecting traffic problems, control proposals etc. • One AIA that executes the operators’ decisions: once a traffic operator accepts a control proposal, the AIA displays the corresponding messages on the VMS. The two types of Management Agents, PDAs and CAs, are the key components of our DSS for traffic management. They are endowed with knowledge bases that use either JESS rules or KSM frames [4]. In particular, PDAs require two kinds of knowledge: • Physical Structure: knowledge representing both static and dynamic information about the network. The static information is a physical description of the problem area (nodes, sections, position of the sensors, etc.). The dynamic aspects allow the PDA to have abstract information derived from the basic data (e.g. traffic excess). • Traffic Problems: knowledge about detection and diagnosis of the traffic state of the area. A problem is seen as an imbalance between capacity and traffic demand in a road, being the quantitative value of this imbalance the so-called traf-

Towards a Generic Multiagent Model for Decision Support: Two Case Studies

603

fic excess. The severity of the problem is a qualitative value obtained from traffic excess. Each CA subscribes to certain PDAs, so as to be informed about the location and severity of traffic problems. It is endowed with the following four types of knowledge to generate coherent control proposals: • PDAs interdependence. The causes of a congestion notified by a PDA can be related to the traffic state in surrounding problem areas that send the incoming flow to the congested section. The PDAs interdependence knowledge represents the relationship between problem areas and allows the CA to know which areas can be involved in the generation of the problem. Using this knowledge, the CA asks the corresponding PDAs for a description of the general state of their problem areas. • Control actions. Once the control agent has received all the necessary information from the different PDAs, it generates control proposals. It uses its Control Actions knowledge base to determine coherent sets of VMS messages, and their expected impact on the drivers’ behaviour. This makes it possible to rank alternative control proposal in terms of the estimated reduction of traffic excess in the problem area. • Conflict detection. Each CA knows, for every VMS panel that it uses, which are the CAs it has to communicate with in order to agree on the use of the panel. • Conflict resolution. Every CA involved in the agreement process sends and receives from the other CAs the panels they want to use and the severity of the different problems they are trying to solve. Conflict resolution rules assign priorities for the use of the panels based on the location and severity problems. The road network of the Bilbao metropolitan area has been subdivided into 12 problem areas, so the prototype DSS application comprises 12 DAs and 12 PDAs. In addition, 5 CAs have been defined: • Atena: solves problems for PDAs 2 and 6 and communicates with PDA 11 • Briseide: solves problems for PDAs 1, 4 and 8 • Cassandra: solves problems for PDAs 5, 7 and 10 and communicates with PDA 1

Physical Structure

Fig. 3. Problem Detection Agent (left) and of a Control Agent (right).

604

Sascha Ossowski et al.

• Demetra: solves problems for PDA 11 and communicates with PDAs 7 and 2 • Elena: solves problems for PDAs 3, 9 and 12 and communicates with PDA 7 Note that the association between PDAs and CAs is induced by both, topological and traffic behaviour criteria. Fig. 4 summarises the different Management Agents of our DSS prototype for traffic control, and outlines their interrelation. 3.2 The Bus Fleet Management Domain In this section, we report on the use of the SKADS abstract architecture for the design and implementation of a prototype DSS for bus fleet management, an enterprise undertaken in collaboration with the Malaga urban bus company (EMT). EMT transportation services are structured into lines. There is a set of buses assigned to each line that are to deliver services according to a fixed schedule. Still, a variety of incidents can (and usually do) occur, so there is a line inspector for each line who takes decisions (in the main stop of the line) in order to adjust services to unforeseen circumstances, and a control centre where a supervisor is in charge of taking broader and more complex management decisions. Our prototype DSS aims at providing both, the inspectors and the supervisors, with the necessary information and recommendations to support their decision making processes. The first stage in the definition of the prototype has been the identification of the required agents in terms of the SKADS abstract architecture: • Data Agents (DA) provide information about the state of the buses: where and how are they? There will be one DA for each line. • There is just one class of MAs in charge of the supervision of each line, so agents of this type are called Line Management Agents (LMA). • User Interface Agents (UIA) display selected information to human operators on board or at the control centre (and also to line inspectors). • Peripheral Agents are reused from other platforms and/or systems (yellow pages, etc.). The generic communication model between these agents can be described as follows: • LMAs subscribe to the information made available by the corresponding DAs; • UIAs subscribe to incidents, problems, and recommendations detected by the UIA; • LMAs may negotiate deals with each other respecting the exchange of vehicles. In addition, the agents’ basic capabilities can be described as follows: • A DA knows about the state of a bus or a set of buses. It can gather information concerning the state of a bus. • An LMA knows about the goals and constraints of the service and about the ways to fix the malfunctions. It can identify a problem, diagnose a problem, plan a set of actions and predict future behaviour of the line.

Towards a Generic Multiagent Model for Decision Support: Two Case Studies CA Briseide

PDA 8

PDA 4

Area 8

Area 4

CA Cassandra

PDA 1 Area 1

CA Demetra

PDA 10

PDA 5

PDA 7

PDA 11

Area 10

Area 5

Area 7

Area 11

CA Elena

PDA12 Area 12

PDA 9 Area 9

605

CA Atena

PDA 3

PDA 2

PDA 6

Area 3

Area 2

Area 6

Fig. 4. MA agents for the road traffic management scenario.

The communication model has been implemented on top of the JADE platform, making use of FIPA concepts such as yellow and white pages, FIPA protocols, etc., as presented in section 2. Although in a final version the DSS will rely on DAs that use GPS to detect the position of the buses (and also other kinds of data sources to determine occupation, etc.), our prototype DAs have been implemented by means of simulators capable of generating location data that replicates the many problematic situations that may arise in a line. LMA knowledge has been represented by means of sets of rules. The corresponding reasoning services are carried out by forward chaining inference engines. We have chosen CLIPS/JESS for these tasks. The ontology of the system, as shown in Fig. 5, has been modelled and instrumented by means of the PROTEGE-II tool. These design decisions have been applied to a particular part of the EMT local transportation network. In particular, our prototype DSS is based on a faithful reproduction of the real operating conditions of three concrete lines (3, 12 and 15, which cover a sector in western Malaga) of the company EMT; in fact, several elicitation interviews have been performed in order to extract the knowledge and logs of real situations, and have been analysed in order to simulate and solve real problems. The main window of our prototype is shown in Fig. 6. Line 12 has been selected for visualization: the schematic layout of this line appears on the Fig. 5. BFM Ontology. left. Six buses are serving the line, which appear in the scheme together with their computed delays: in this case, five buses are delivering their service in time, while another one has suffered a breakdown. At the right of the window a decision support dialogue is shown: in the example, the DSS recommends to ask line 3 for a reserve vehicle. Finally, the bottom part of the window contains status information of the line and its simulator.

606

Sascha Ossowski et al.

Fig. 6. Screenshot of the bus fleet management UIA.

4 Conclusions In this paper we have presented the SKADS approach to the design of operational decision support systems based on agent and knowledge technology. Setting out from organisational and agent models, we have come up with an abstract multiagent architecture for DSS. The instrumentation of this architecture has been illustrated by two case studies in real-world transportation management domains. We are currently proceeding with the implementation of the demonstrators for the two case studies. Despite initial problems with the integration of the different technologies, first results are encouraging. In the future, we are planning to extend our approach so as to cope with more open, large-scale service environments.

References 1. Austin, J.L. (1962): How to do Things with Words. Clarendom Press, Oxford. 2. Bellifemine, F.; Poggi, A.; Rimassa, G.; Turci, P. (2000): An Object Oriented Framework to Realize Agent Systems. Proc. WOA 2000 Workshop, 52–57. 3. Belmonte, M.V. (2002): Formación de Coaliciones en Sistemas Multiagente – Una Aproximación Computacionalmente Tratable Basada en Teoría de Juegos. Ph.D. Thesis, Univ. de Málaga. 4. Cuena J., Molina M. (1997): KSM – An Environment for Design of Structured Knowledge Models. Knowledge-Based Systems (Tzafestas, editor). World Scientific. 5. Cuena J., Ossowski S. (1999): Distributed Models for Decision Support. In: Multi-Agent Systems — A Modern Approach to DAI (Weiß, editor). MIT Press, 459–504.

Towards a Generic Multiagent Model for Decision Support: Two Case Studies

607

6. Cuena, J.; Hernández, J.; Molina, M. (1996): Knowledge-Oriented Design of an Application for Real Time Traffic Management. In: Proc. Europ. Conf. on Artificial Intelligence (ECAI-96), Wiley & Sons, 217–245. 7. Decker, K.; Sycara, K.; Williamson, M. (1997): Middle-agents for the internet. In: Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), Morgan Kaufmann, 578–583. 8. Ferber, J.; Gutknecht, O.; Jonker, C.; Müller, J.P.; Treur, J. (2000): Organization Models and Behavioural Requirements Specification for Multi-Agent Systems. In: Proc. ECAI 2000 Workshop on Modelling Artificial Societies and Hybrid Organizations. 9. Fernández, A.; Ossowski, S. (2002): El estándar FIPA para sistemas inteligentes basados en agentes: una panorámica. ALI Base Informática No 38. 10. Fernández, A.; Ossowski, S.; Alonso, A. (2004): Multiagent service architecture for bus fleet management. Int. Journal on Integrated Computer-Aided Engineering 10 (2). 11. FIPA - The Foundation for Intelligent Physical Agents. http://www.fipa.org/ 12. French, S. (2000): Decision Analysis and Decision Support. John Wiley & Sons. 13. Hernández, J.; Ossowski, S.; García-Serrano, A. (2002): Multiagent Architectures for Intelligent Traffic Management Systems. Transportation Research C 10 (5). Elsevier. 14. Hernández, J.; Serrano, J. (2000): Environmental Emergency Management Supported by Knowledge Modelling Techniques. AI Communications 14 (1). 15. Iglesias, C.A.; Garijo Ayestarán, M.; González, J.C. (1999): A Survey of Agent-Oriented Methodologies. In: Intelligent Agents V. Springer-Verlag. 16. Klein, M.; Methlie, L. (1995): Knowledge-Based Decision Support Systems. John Wiley. 17. Hoa Dam, K.; and Winikoff, M. (2003): Comparing Agent-Oriented Methodologies. In: Proc Workshop on Agent-Oriented Information Systems (AOIS-2003). 18. Ortíz Martín, R.; Saugar García, S. (2002): Agentificación del entorno KSM. Technical Report, Universidad Rey Juan Carlos de Madrid. 19. Ossowski, S.; Hernández, J.; Iglesias, C.A.; Fernández, A. (2002): Engineering Agent Systems for Decision Support. In: Engineering Societies in an Agent World III (Petta, Tolksdorf & Zambonelli, editores), Springer-Verlag. 20. Ossowski, S.; Omicini, A. (2003): Coordination Knowledge Engineering. Knowledge Engineering Review 17 (4), Cambridge University Press. 21. Serrano, J.M. (2004): La Pragmática de los Agentes Software – Análisis y Diseño de los Lenguages Artificiales de Comunicación Artificiales. Ph.D. Thesis, Univ. Rey Juan Carlos. 22. Serrano, J.M.; Ossowski, S.; Fernández, A. (2003): The Pragmatics of Software Agents – Analysis and Design of Agent Communication Languages. Intelligent Information Agents – An AgentLink Perspective (Klusch et al., editores). LNAI 2586, Springer, p. 234–274. 23. Silver, M. (1991): Systems that Support Decision Makers. John Wiley & Sons. 24. Sturm, A.; Shehory, O. (2003): A Framework for Evaluating Agent-Oriented Methodologies. In: Proc Workshop on Agent-Oriented Information Systems (AOIS-2003). 25. Wooldridge, M.; Jennings, N.; Kinny, D. (2000): The Gaia Methodology for Agentoriented Analysis and Design. Autonomous Agents and Multiagent Systems 3(3). Kluwer Academic Publishers, 285–312. 26. Zambonelli, F.; Jennings, N.R.; Wooldridge, M. (2000): Organizational Abstractions for the Analysis and Design of Multi-agent Systems. In: Agent-Oriented Software Engineering (Ciancarini y Wooldridge, editors), Springer-Verlag, 235-252.