Proceedings of INTELLIGENT SYSTEMS AND AGENTS 2009 [PDF]

call for papers

IADIS MULTI CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS

21 - 23 June Algarve, Portugal

Proceedings of INTELLIGENT SYSTEMS AND AGENTS 2009

Edited by: António Palma dos Reis

international association for development of the information society

IADIS INTERNATIONAL CONFERENCE

INTELLIGENT SYSTEMS AND AGENTS 2009

part of the IADIS MULTI CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS 2009

ii

PROCEEDINGS OF THE IADIS INTERNATIONAL CONFERENCE

INTELLIGENT SYSTEMS AND AGENTS 2009

part of the IADIS MULTI CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS 2009

Algarve, Portugal JUNE 21 - 23, 2009

Organised by IADIS International Association for Development of the Information Society iii

Copyright 2009 IADIS Press All rights reserved This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in Fuzzy sets". Information and Control 8 (3), pp. 338-353.

107

ISBN: 978-972-8924-87-4 © 2009 IADIS

COORDINATED MULTI-AGENT BASED FRAMEWORK FOR PATIENT AND RESOURCE SCHEDULING E. Grace Mary Kanaga Assistant Professor, Department of Computer Science and Engineering, Karunya University 64114, Coimbatore, Tamil Nadu, India (Phone: 9994298003; fax:+91-422-2615615)

M.L. Valarmathi Assistant Professor, Department of Computer Science and Engineering, Government College of Technology 641013, Coimbatore, Tamil Nadu, India

Preethi S.H. Darius Masters student, Department of computer Science and Engineering, Karunya University, 64114, Coimbatore, Tamil Nadu, India.

ABSTRACT The increasing complexities of the hospital scheduling domain makes traditional scheduling techniques employed in hospitals today inadequate. We present a novel agent-based coordinated framework for patient and resource scheduling in hospitals. The objective of this framework is to minimize patient waiting time and to improve resource utilization. This framework simulates the distributed environment in hospitals by representing each resource and patient as an individual agent. Scheduling is done via an auction process that uses a dual-level decision making scheme. The resource agent auctions its timeslots and makes resource-level decision for bid selection, evaluation and price adjustment. The patient agents bid for a combination of resources and makes patient-level decisions to choose the resource that minimizes its waiting time. In case of emergencies or unforeseen circumstances, rescheduling is opted. The distinctive feature of our framework is that it captures exclusively the dynamics of hospital scheduling. It also produces an optimal schedule when compare to traditional scheduling techniques. A fault-tolerant and robust system is produced that is capable of handling disruptions. KEYWORDS Multi-agents, Coordination Technique, Auction, Hospital Scheduling.

1. INTRODUCTION For the past decade, the agent paradigm has been applied to many traditional problems that were considered difficult to solve. The reactive and proactive nature of an agent and the ability to represent a distributed and decentralized environment has spurred the interests of applying multi-agents to solve the scheduling problems in various domains. The result, which is a highly fault-tolerant and adaptable system as proved by Liu et al (2007) and Zhang et al (2007) has been the major motivation for an agent based solution. A novel framework is presented in this paper where agents conduct and participate in auctions to produce a schedule for the respective hospital resources and patients that they represent. The prime objective of this framework is to minimize the waiting time for patients and also to improve resource utilization in hospitals. As explained by Chien, Tseng and Chen (2007), the relationship between patients and hospitals has become more customer-oriented which are forcing many hospitals to improve service quality. Hence, this innovative framework is employed to reduce the waiting times of all the patients. Scheduling has been the instinctive response of humankind whenever there is a resource with contending users. The scheduling theory defined by Karger et al (1997) is concerned with the optimal allocation of scarce resources to activities over time. The complexity of the patient scheduling problem arises from the

108

IADIS International Conference Intelligent Systems and Agents 2009

fact that modern hospitals are divided into various departments with each division professing a high degree of independence and authority. The previous scheduling techniques employed to solve the patient scheduling problem can be broadly classified into two categories – traditional and agent-based. The coordinated framework for patient scheduling uses a specialized category of agent-based scheduling implementing auction. The resource and patient entities are modeled as resource agent (RA) and patient agent (PA) along with a common agent (CA) that controls the overall activities. Scheduling is achieved by an auction mechanism where the PA places bids to request for the required RA’s. This paper is organized as follows. The overview of the patient scheduling problem and the nature therein is presented in Section 2 followed by an analysis of the traditional and agent-based scheduling techniques of the past. Our coordinated multi-agent framework for patient and resource scheduling is presented in Section 3. Some simulation and results are given in Section 4. The scope of the framework, the prominent characteristics and conclusions drawn are discussed in Section 5.

2. LITERATURE SURVEY The problem we are trying to tackle is the patient scheduling problem. A general overview of the patient care model and its implications will be presented. The literature on previous patient scheduling methods used will be discussed and analyzed.

2.1 Problem Description The model presented in our paper is a high level generalized model of the patient care scenario in many hospitals. Each patient, upon arrival, goes through a process of diagnosis after which an initial treatment plan is produced for each patient. This treatment plan is subject to refinement which is an iterative and highly dynamic process in the patient scheduling problem. The hospital scheduling problem can be classified by using 3D’s, distributed, dynamic and decentralized. It is inherently distributed because the hospitals are divided into several autonomous wards and ancillary units as described by Paulussen et al (2003). The scheduling problem is also dynamic due to the reasons given by Paulussen et al (2003) such as inevitable changes and disturbances such as emergencies and complications. Vermeulen et al (2007) describe the nature of hospitals are decentralized because each department has authority over own schedule. The hospital scheduling problem is diverse and many papers have addressed different aspects of the hospital scheduling problem (Figure 1). Some of the major problems addressed in literature are, patient/medical appointment scheduling as seen in Vermuelen et al (2007), Hannebauer et al (2001) and Kaandorp and Koole (2007). Another type is the specialized case of Surgical Case Scheduling (SCS) found in Pham and Klinkert (2008) / Operating Room (OR) scheduling as given by Becker and Navarro (2003) and Kaandorp and Koole (2007). Patient test scheduling in laboratories as given by Marinagi et al (2000) and other specific scheduling for specific treatment plans such as scheduling for treatment of radiotherapy by Kapamara et al (2006) is another aspect of the hospital scheduling problem. The problems specified can be solved using either a patient-centered approach or resource-centered approach. We don’t take into account staff scheduling in our description because it involves additional constraints such as shifts. When we consider a resource such as MRI Scan, we assume that the required human operator for the machine is also present.

109

ISBN: 978-972-8924-87-4 © 2009 IADIS

Medical Appointment Scheduling

Operating Room Scheduling and Surgical Case Scheduling

Hospital Scheduling

Scheduling Patient Tests

Staff Scheduling

Figure 1. Aspects of Hospital Scheduling.

2.2 Scheduling Techniques Traditional scheduling algorithms have been developed for both static and dynamic environments. Haupt (1989) has given a list of 26 different scheduling rules. Some of the popular dispatching rules are FCFS (First Come First Serve), MS (Minimum Slack), SPT (Shortest Processing Time), LPT (Longest Processing Time), WPT (Weighted Processing Time), EDD (Earliest Due Date) and WSPT (Weighted Shortest Processing Time). Scheduling can also be agent-based where agents can reach an agreement by auctions, negotiation, argumentation or a combination of these techniques as explained by Wooldridge (2002). In literature, the auction mechanism is usually used to produce a ranking of the tasks that result in a schedule. Auction-based scheduling has been proposed by Liu et al (2007), Oueldhadj et al (2004) and Lau et al (2007). The negotiation approach is usually used during rescheduling an already existing schedule with the intention of improving the produced schedule. In the medical domain, auction protocols have been used to solve operating room scheduling as given by Becker and Navarro (2003), and negotiation has been used in rescheduling medical appointments, and planning of patient tests.

2.3 Performance Evaluation There are several performance metrics for the scheduling problem. The objective of patient scheduling problem is to minimize the patient waiting time and improve the resource utilization in the hospitals. The most useful metric used in the evaluation of the patient scheduling mechanism is total weighted tardiness where a minimal value is an indicator of the patient waiting time being minimized. Total weighted tardiness is given by the formula n

∑ w ×T i =1

i

i

(1)

which multiplies with the weight of the patient i that is a value assigned based on the priority of the patient with the tardiness which is the lateness of the patient i. Other performance metrics include, the maximum waiting time, total waiting time and number of patients scheduled late.

2.4 Analysis of Current Approaches to Patient Scheduling The traditional approaches to patient scheduling have obvious disadvantages which are summarized below: Lack of decentralization: A centralized environment is stimulated in the case of traditional scheduling approach. A truly distributed and decentralized environment that will aptly represent the hospital scheduling environment is never fully realized in a typical traditional scheduling approach.

110

IADIS International Conference Intelligent Systems and Agents 2009

Inflexibility: Traditional scheduling algorithms do not cater to the high level of dynamism and disruptions in a typical hospital scheduling scenario. Hence, they do not handle disruptions well in an event when a resource breaks down, or the patient is not available. The present agent based approaches to patient scheduling also have several drawbacks: Lack of a generalized framework: In literature, specific aspects of scheduling in hospitals such as medical appointment scheduling or surgical case scheduling or patient test scheduling are tackled. A different set of variables and constraints accompany each aspect of patient scheduling. Lack of an optimal schedule: The application of agents to patient scheduling is a relatively new field in research and several developments merely focus on the use of a particular agent-based technique such as GPGP (Generalized Partial Global Planning) or the Contract Net Protocol to solve the patient scheduling problem. The optimization of a schedule using agents is still inadequate in the patient scheduling domain.

3. PROPOSED FRAMEWORK FOR PATIENT SCHEDULING The framework we propose uses patient agents to represent the patient entities and resource agents to represent resource thereby simulating the distributed environment in the patient scheduling domain. An auction mechanism is used to create a schedule for both the patient and resource agents. As can be seen in Figure 2, the patient and resource scheduling framework consists primarily of the Patient Agent (PA), the Resource Agent (RA) and the Common Agent (CA). RS1

RSm

RS2

RA1

RA2

RAm [AUCTIONEERS]

… MRI Scan

Specialist

{PriceAdjustment}

Blood Test

Prices (Combinatorial Auction) [BIDDERS] Bids PS1

T21 PA2

PA1

T22 T2l

PS2

T11

PAn PSn

T12 T1k

T31 CA

RS i: Schedule for resource i RAi: Resource Agent Tij : Task j for patient i

…

T32 T3p

PAi : Patient Agent CA: Common Agent PSi : Patient Schedule produces

Figure 2. Framework for Coordinated Multi-agent Patient and Resource Scheduling.

Each Patient Agent, PAi has a set of tasks Ti1,Ti2,…,Tim. These tasks represent the treatment plan prescribed for each patient. Each Resource Agent, RAj conducts an auction at a decision point, tc. Each Patient Agent PAi participates in a combinatorial auction where a patient agent bids for multiple timeslots of resources at the same time as explained by Kutanoglu and Wu (1999). The result of this auction is the resource schedules RS1,RS2,…,RSm for resource agents RA1,RA2,…RAm and the patient schedules, PS1,PS2,…,PSn for the patient agents PA1, PA2,…,PAn.

111

ISBN: 978-972-8924-87-4 © 2009 IADIS

3.1 Multi-agent Types The agent types deployed in the patient scheduling framework are the Common Agent (CA), Patient Agent (PA) and the Resource Agent (RA). A brief description of each type of agent is given below: Common Agent (CA): In our system, the common agent has multiple responsibilities as seen in figure 3. The common agent corresponds to the physical entity that registers a patient or resource to the system and maintains the patients and resources registered in the system. It is also responsible in some cases for prescribing an initial treatment plan for a patient. Common Agent Common Agent GUI

Directory Facilitator

Patient Registration and Control

Publish Bids

Prescribe initial treatment plan Resource Monitoring and Control

PA

Look-Up Bids Monitor Auctions

RA

Figure 3. The services of the Common Agent.

Patient Agent (PA): The patient agents represent individually each instance of the patient entity. Patient agents are bidders in the auction process. Both inpatients and outpatients are represented by a Patient Agent (PA). The patient agent is diagnosed and prescribed a treatment plan. Resource Agent (RA): The resource agent represents the various non-sharable resources in the hospital such as X-Rays, CT Scans, Lab tests, and also specialists and other physicians. Resource agents are subject to various machine constraints imposed by the physical limitations as well as organizational policies and goals. Each resource agent has multiple timeslots of a specified duration. These timeslots are integer values and will be allocated to the winning task in a patient agent. Resource agent acts as the auctioneer in the auction process of patient scheduling.

3.2 Auction-based Scheduling Mechanism The framework described in this paper aims to overcome the drawbacks in current agent based approaches in patient scheduling domain as well as to incorporate the best features of the approaches in agent-based scheduling in other domain. The auction-based scheduling mechanism separates the decision-making process into two levels, at the patient-level and at the resource-level. The patient-level decision-making refers to the local decisions made by the patient agent when calculating the bid for a particular task. The objective of the bid is reducing the waiting time for the individual agent. The logic at this level also involves choosing the best bid accepted by a resource agent for the particular timeslot. A task incurs a tardiness cost if it is not accepted for the required timeslot in a given auction. This mechanism ensures that patients with a low priority level do not keep waiting indefinitely. The resourcelevel decision making refers to the decision made by the resource agent when calculating the initial price, evaluating the bids and calculating the price adjustment and selecting the bid. The objective for a resource agent is to maximize its utilization and profits. It will choose the highest bidder for a particular timeslot. The various steps of the auction process are explained below: Price Calculation: The resource agent calculates the initial price for the various timeslots. This initial price determines the entry point of all the bids. Price Announcement: The announcement of the initial price of the timeslots is sent to all the patient agents available at the current decision point by means of a Call For Proposal (CFP) message. Bid Calculation: Following the CFP received by the patient agents, the patient agents enter into the local decision making scheme. This bid aims to minimize the waiting time of the patient. At decision point, tc, the patient agents calculate the bids for all of the tasks which have a release date that is equal to or earlier than tc.

112

IADIS International Conference Intelligent Systems and Agents 2009

Bid Submission: The bid submission by patients is done via publishing the bids for various timeslots in multiple resources by using the directory facilitator service of the Common Agent. Each ‘advertisement’ identifies the bidding agent, the bidding amount and the resource timeslot for which the bid is placed. Bid Evaluation: The resource agent now performs the secondary level decision making. It ‘looks-up’ the current bidding amounts placed by all the patient agents for its various timeslots. It selects the highest bid and then checks the stopping criterion. If the stopping criterion is not met, then a price adjustment is made to the particular timeslot and the auction enters another round of bidding. The new price is again sent to all the patient agents. The patient agents can either drop out of the auction or bid a higher amount. Bid Selection: In the case when the stopping criterion is met, the resource agent selects the winning patient agent and allocates its timeslot to the agent. The auction ceases, but is resumed if there are further contending agents with higher bids for the particular timeslot. Bid Acceptance: Finally, the resource agent sends a message of acceptance to the winning patient agent informing the agent that the bid is accepted. The patient agent will send a message of confirmation back to the resource agent.

4. SIMULATION AND RESULTS The proposed framework’s auction mechanism was simulated using the JADE (Java Agent Development) platform. It is a software framework fully implemented in Java language. It simplifies the implementation of multi-agent systems through a middle-ware that complies with the FIPA specifications and through a set of tools that supports the debugging and deployment phase. A simple simulation of two patient agents and resource agents and message passing that takes place is shown in Figure 4. These messages passed were captured using the sniffer agent feature in JADE.

Figure 4. Simulation of Auction mechanism in JADE

The simulation was also done by varying the number of patients on 3 resources from 3 patients to 20 patients with different arrival times and priority levels. The weighted tardiness from our mechanism as compared against the results of several traditional scheduling rules giving in 2.2 is given in Figure 5. At number of patients = 20, the proposed framework performs 30% better than SPT, 27% better than LPT and 15% better than FCFS from the analysis in Table 1.

Total Weighted Tardiness

3500 3000

FCFS

2500

EDD LPT

2000

SPT

1500

WSPT

1000

MS

500

Proposed framework

0 0

5

10

15

20

25

Number of Patients

Figure 5. Total Weighted Tardiness of proposed framework and other traditional scheduling rules (Section 2.2).

113

ISBN: 978-972-8924-87-4 © 2009 IADIS

Table 1. Performance Improvement of the proposed framework as compared to other scheduling for 20 patients.

Total Weighted Tardiness

Performance Improvement of Proposed Framework (%)

2396 2454 2802 2900 2502 2384

15.11 17.11 27.41 29.86 18.71 14.68

FCFS EDD LPT SPT WSPT MS

5. CONCLUSION The traditional scheduling approaches in hospital scheduling are fast becoming obsolete in the face of the increasing complexities and the high level of dynamism evident in the present hospitals scheduling problem. Hence, an agent-based solution is chosen due to the flexibility, robustness and adaptability of agents as compared to the traditional scheduling algorithms. Our proposed framework adapts the technique used in industry scheduling to produce an optimal schedule while also making it suitable for the patient scheduling domain. The prominent features of our framework are that: • This system architecture is purely distributed. • Handles the emergencies and unforeseen disturbances in the hospital scheduling domain. • Exclusively models the patient scheduling domain using traditional industry scheduling concepts • Produces an optimal schedule both initially and after rescheduling. • Uses auction-based market mechanism to allocate resources such that patient waiting times are minimized. This framework has the ability to handle the dynamic nature of patient scheduling quite effectively. It also permits agents to enter or exit the scheduling system flexibly thus achieving robustness and adaptability. Since the system architecture is purely distributed, it naturally inherits the advantages of decentralized models, such as flexibility and high fault tolerance. The patient scheduling domain is a highly dynamic domain and an effective solution will improve the quality of life of the society. A schedule that minimizes the patient waiting times may even aid in saving a person’s life and improve the service quality of modern hospitals.

REFERENCES Becker, M, Navarro, M, Krempels & Panchenko, A 2003, ‘Agent based scheduling of operation theatres,’ in EU-LAT eHealth Workshop on Agent Based Scheduling of Operation Theatres. Chien, C F, Tseng, F P & Chen, C H 2008, ‘An evolutionary approach to rehabilitation patient scheduling: A case study,’ in European Journal of Operational Research, vol.189, no.3, pp.1234-1253. Hannebauer, M & Müller, S 2001, ‘Distributed constraint optimization for medical Appointment scheduling,’ in Proceedings of the fifth international conference on Autonomous agents, pp. 139-140. Hans, E, Wullink, G, van Houdenhoven, M & Kazemier, G 2008, ‘Robust surgery loading’, European Journal of Operational Research, vol.185, no.3, pp.1038-1050, Mar. Haupt, R 1989, ‘A survey of priority rule-based scheduling,’ OR Spectrum, vol.11, no. 1. Kaandorp, G & Koole, G 2007, ‘Optimal outpatient appointment scheduling,’ Health Care Management Science, vol. 10, no. 3, pp. 217-229. Kapamara, T, Sheibani, K, Hass, O C L, Reeves, C R & Petrovic, D 2006, ‘A review of scheduling problems in radiotherapy,’ in Proceedings of 18th International Conference on Systems Engineering, , pp. 207-211. Karger, D, Stein, C, & Wein, J 1997, Scheduling Algorithms, 1997. Kutanoglu, E, Wu, S D 1999, ‘On combinatorial auction and Lagrangean relaxation for distributed resource scheduling,’ IIE Trans., Vol.31, No.9.

114

IADIS International Conference Intelligent Systems and Agents 2009

Lau, H C, Cheng, S F, Leong, TY, Park, J H & Zhao, Z. 2007, ‘Multi-Period Combinatorial Auction Mechanism for Distributed Resource Allocation and Scheduling,’ in IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology, pp. 407-411. Liu, N, Abdelrahman M, A & Ramaswamy, S 2007, ‘A Complete Multiagent Framework for Robust and adaptable dynamic job Shop Scheduling,’ IEEE Trans. On Systems Man and Cybernetics Part C Applications and Reviews, vol.37, no.5. Marinagi, C C, Spyropoulos, C D, Papatheodorou, C & Kokkotos, S 2000, ‘Continual planning and scheduling for managing patient tests in hospital laboratories,’ Artificial Intelligence in Medicine, vol.20, no.2, pp.139-154. Ouelhadj, D, Petrovic, S, Cowling, P I & Meisels, A 2004, ‘Inter-agent cooperation and communication for agent-based robust dynamic scheduling in steel production,’ Advanced Engineering Informatics, vol.18, no.3, pp. 161-172. Paulussen, T O, Jennings, N R, Deckerm, K S & Heinzl, A 2003, ‘Distributed patient scheduling in hospital,’International Joint Conference on Artificial Intelligence, vol. 18, pp. 1224-1232. Pham, D-N & Klinkert A, 2008 ‘Surgical case scheduling as a generalized job shop scheduling problem,’ European Journal of Operational Research, vol.185, no.3, pp.1011-1025. Vermeulen, Bohte, S, Somefun, K & Poutré, H.La 2007, ‘Multi-agent Pareto appointment exchanging in hospital patient scheduling,’ Service Oriented Computing and Applications, vol.1, no.3, pp.185-196. Wooldridge, M 2002, An Introduction to MultiAgent Systems, John Wiley and Sons. Zhang, F, Santos, E & Luh, P B 2007, ‘A Performance Study on a Multiagent E-Scheduling and Coordination Framework for Maintenance Networks,’ IEEE Trans. Systems, Man, and Cybernetics-Part C: Applications and Reviews, Vol. 37, Issue 1, pp.52-65.

115

ISBN: 978-972-8924-87-4 © 2009 IADIS

MASITS – A MULTI-AGENT BASED INTELLIGENT TUTORING SYSTEM DEVELOPMENT METHODOLOGY Egons Lavendelis, Janis Grundspenkis Riga Technical University, Department of Systems Theory and Design Kalku 1, LV-1658, Riga, Latvia

ABSTRACT During the last decades intelligent agents integrated in multi-agent systems are accepted as a suitable technology to implement mechanisms of Intelligent Tutoring Systems (ITS), so facilitating ITS development. Still, no adequate methodological support is available for agent based ITS development. Regardless of the fact that general agent-oriented software engineering methodologies are the most suitable for this purpose, ITSs have specific characteristics that need to be taken into consideration during the development process. Additionally, ITSs have their own field of research with important knowledge gained, that is useful during the ITS development. The paper presents the specific ITS development methodology named MASITS to support agent based ITS development. The methodology integrates results of ITS research into the most appropriate techniques used in agent-oriented software engineering methodologies. The paper presents also the corresponding tool for support of the methodology and gives a brief description of case study of the methodology and the tool. KEYWORDS Agent-Oriented Software Engineering Methodology, Intelligent Tutoring System, Multi-Agent System Application

1. INTRODUCTION During the last decades a large number of Intelligent Tutoring System (ITS) prototypes have been built, for example, FLUTE (Devedzic et al., 2000), ABITS (Capuano et al., 2000), Passive Voice Tutor (Virvou and Tsiriga, 2001), AGT (Matsuda & VanLehn, 2005), Slide Tutor (Crowley & Medvedeva, 2005) and Ines (Hospers et al., 2003). However, the ITS development is still a complex process, because functionality of ITSs is intelligent and complicated. At the same time sufficient methodological support to manage complexity during the ITS development is not available. Agents and Multi-Agent Systems (MAS) have become one of the most popular technologies to implement ITSs during the last years. Well known examples of agent based ITSs are the ITS for enhancing e-learning (Gascuena & Fernández-Caballero, 2005), ABITS and Ines. Agents are so popular, because they are autonomous, reactive, proactive, and they are capable to plan, reason and make decisions (Grundspenkis & Anohina, 2005). Additionally, MASs are open. These characteristics of agents help to implement intelligent mechanisms into ITSs. Agents allow decomposition of large monolithic modules of ITSs. Consequently, the architecture of agent based ITS may consist of smaller entities which are easier to develop then large-scale modules. Thus, agents help to reduce complexity of ITS development process. However, development of agent based ITS in an ad-hoc manner without usage of any methodology can be done only as a research and not as an industrial software development. This is one of the main obstacles for agent based ITSs to become more widespread. To facilitate adoption of Agent-Oriented Software Engineering (AOSE) by software developers a large number of agent-oriented software engineering methodologies have been developed during the last decades. The well known examples of AOSE methodologies are Gaia (Zambonelli et al., 2005), Prometheus (Winikoff & Padgham, 2004), MaSE (De Loach, 2001), Tropos (Giunchiglia et al., 2001), MAS-CommonKADS (Iglesias C. et al., 1998) and RAP (Taveter & Wagner, 2005). Two types of methodologies can be distinguished. First, general purpose agent-oriented methodologies aim to support development of any agentoriented software. Gaia is one of the most popular examples of this type. Second, specific purpose methodologies for some specific agent-oriented software are proposed, for example, ADELFE methodology

116

IADIS International Conference Intelligent Systems and Agents 2009

for adaptive MAS development (Picard & Gleizes, 2004). General purpose methodologies aim to support as many different agent systems as possible by providing high level techniques that support different agents. Contrary, specific purpose methodologies provide particular techniques that can be used more effective to develop systems with specific characteristics. In case if the merely distinguishing characteristic is the chosen agent development platform, only detailed design, implementation and deployment phases can be adopted to the platform. Such approach is used in the Prometheus methodology. Additionally, a methodology for systems in specific domain can include appropriate techniques for analysis and early design. Thus, specific methodologies can facilitate development of respective agent-oriented systems. At the same time our study of large number of publications reveals that a specific methodology for agent based ITS does not exist. This fact motivated an effort to develop such methodology called MASITS which is described in this paper. The remainder of the paper is organized as follows. In Section 2 distinguishing characteristics of ITS and their influence on the development process are given. Section 3 includes description of the MASITS methodology. Section 4 describes the MASITS tool that supports ITS development using the MASITS methodology. Section 5 is dedicated to a case study of the MASITS methodology and tool. Section 6 concludes the paper.

2. SPECIFIC CHARACTERISTICS OF AGENT-BASED INTELLIGENT TUTORING SYSTEM DEVELOPMENT The ITSs aim is simulation of a human tutor during the learning process. To do it, ITSs have to generate curriculum for particular learner to learn the course, realize different teaching strategies, generate tasks, problems and questions to evaluate learner’s knowledge as well as give feedback to explain learner’s mistakes and offer appropriate remedial actions. All these activities have to be done in adaptive manner to implement one-to-one tutoring and meet needs of different learners. To carry out these activities ITSs use three types of knowledge: domain knowledge, knowledge about a learner and pedagogical knowledge (Grundspenkis & Anohina, 2005). The ITS architecture consists of three modules corresponding to the knowledge types used: an expert module, a tutoring module and a student diagnosis module. Additionally a communication module is used to communicate with a learner. Grundspenkis & Anohina (2005) offer a set of agents that are used to implement all modules of ITS: an interface and animated pedagogical agent for communication module; one or more teaching strategy agents, a curriculum agent, a feedback and explanation agent for pedagogical module; a psychological agent, a knowledge evaluation agent, a cognitive diagnosis agent and an interaction registering agent for student diagnosis module; and one or more expert agents for expert module. Complementary Lavendelis and Grundspenkis (2008) offer the holonic multi-agent architecture for agent based ITS implementation. Thus, different ITS researches have provided significant knowledge that can be used during the development process. However, if general purpose methodology is used it is hard to integrate the results of ITS research into the development process. Agent based ITSs are agent-oriented systems with specific characteristics that should be taken into consideration during the development process. The main characteristics are the following. Firstly, ITSs are weakly integrated into organization and have very few types of users (learners, teachers and administrators if latter one needed). Thus, any organizational analysis techniques are not applicable during ITS requirements analysis. Agents and their tasks are treated as requirements in many AOSE methodologies, but it is reasonable only if agents are created to represent someone. It is not the case considering the ITS. So, ITS requirements analysis has to be based on the functional requirements and not organizational structure or agents. Secondly, a set of agents, used for implementation of ITS, is well known. Therefore, instead of agent definition during the design the already existing set of agents may be used and modified if needed. Thirdly, majority of agents, that are used to implement an ITS, are reactive agents, whose development must be as simple as possible. At the same time some agents have to be proactive, for example, a feedback agent has to interfere if the learner has difficulties to solve a problem. Moreover, all intelligent mechanisms needed in an ITS have to be implemented in agents. As a result, support of heterogeneous agents is needed. Fourthly, MASs that are used to implement ITS, are cooperative, they have to achieve a common goal – to teach the learner. Fifthly, our research has shown that the agents for the ITS development communicate using single messages and no explicit protocols are used. Thus, the most appropriate form to design interactions among

117

ISBN: 978-972-8924-87-4 © 2009 IADIS

agents is single messages, not protocols. Sixthly, ITSs can be effectively developed using holonic MASs (Lavendelis & Grundspenkis, 2008). So, a specific methodology for agent based ITS development can address the main characteristics of ITS in a more appropriate way in comparison with general ones and as a consequence be more effective. This motivates working out a specific methodology for the ITS development. The specific ITS development methodology has to: • Integrate knowledge from ITS research, like known set of agents and architecture; • Include suitable techniques to support main characteristics of ITS and exclude techniques that deal with aspects of agents that are not important in agent based ITS.

3. MASITS METHODOLOGY The MASITS (MAS for ITS) is a full life cycle methodology for agent based ITS development. The MASITS methodology includes the most important results of ITS development research and AOSE methodologies. The most appropriate techniques from existing AOSE methodologies are used during steps where existing techniques allow to integrate specific knowledge for the ITS development. Additionally new techniques are introduced in steps where known techniques do not allow to integrate ITS knowledge. The process of ITS development consists of the following phases: analysis, design (divided into two stages: external and internal design), implementation, testing, deployment and maintenance. These phases are presented sequentially, although the development process is iterative. Iterations are used both inside the phases and across different phases. A developer of the system is allowed to return to any previous phase and refine the previously created models. Phases of the development process and steps included in these phases are shown in Figure 1. The remainder of Section 3 gives a brief overview of steps done during all phases of development, for details, see (Lavendelis & Grundspenkis, 2009a) and (Lavendelis & Grundspenkis, 2009b).

3.1 Analysis Phase During the analysis phase two consecutive steps are performed. The first step is the goal modelling resulting in the goal diagram that depicts the goal hierarchy of the system. At first, the higher level goals of the system are defined. Then each goal is decomposed into subgoals using “AND” and “OR” decompositions. Goals are decomposed until the lower level goals can be achieved by simple actions. A goal description is written for each goal, including an actor that needs the goal to be achieved, a brief description of the goal and conditions that must be met to achieve the goal. Goals identified during this step are used to define corresponding use cases and to crosscheck models created during the later phases against goals. At the second step the use case model is created. During the goal modelling initial actors have been defined, by specifying actors that need to achieve goals. At the beginning of the use case modelling the set of actors is refined by adding all actors that participate in use cases, but do not have corresponding goals. When all actors are defined, use cases are created corresponding to the lower level goals of the goal hierarchy. One or more use cases are created to achieve each lower level goal. Use cases are added to the use case diagram and the use case description is created for each use case. The main part of the description is the use case scenario, denoting consecutive steps that have to be executed during the use case. The consecutive scenario steps are used in design phase to define tasks done by agents and interaction among agents. At the end of the use case modelling use cases are checked against goals by creating interdiagram relationships from goals to use cases that are defined to achieve the goal. If any lower level goal is not linked to any use case, then the goal is not supported and use cases have to be refined.

118

IADIS International Conference Intelligent Systems and Agents 2009

Figure 1. Structure of MASITS methodology

3.2 External Design of Agents The ITS design phase has been divided into two stages – the external and the internal design of agents. During the first one (the external design) agents are designed in terms of their functionalities and interactions among agents. The external design of agents answers the question what agents have to do. This stage consists of the following steps: the task definition, the task allocation to agents, the interaction design and the ontology design. The first step of the external design is the task definition. Tasks are defined according to the steps of use case scenarios. A task is defined either according to a single step or a few consecutive steps. After the task definition, a crosscheck of tasks against goals is done. It is carried out by creating relationships among goals and tasks that are accomplished to achieve the goal. After such relationships are created any unlinked lower level goal indicates that the goal is not achieved by the previously created tasks and the tasks must be refined. When a set of tasks that is sufficient to achieve all goals is created, the second step is started. During this step tasks are organized into the hierarchy and assigned to agents. The task hierarchy is created by linking together tasks that are accomplished by the same agent resulting in the task diagram. So, the hierarchy in the task diagram is different from the goal hierarchy. The MASITS methodology contains informal rules describing tasks that must be allocated to agents from the set of agents used to implement the ITS. For example, the following tasks are allocated to the student modelling agent: (1) learner’s level of knowledge and skills model building tasks; (2) learner’s psychological characteristics modelling tasks; (3) learner’s interaction with the system registering tasks; (4) determining tasks of learner’s mistakes and their causes; (5) full student model creation task (for details, see Lavendelis & Grundspenkis, 2009b). Designer only has to decide which description of tasks is the most appropriate for each task. The task-agent diagram is created as a result of this activity. This diagram contains a hierarchy of tasks and an agent responsible for each task is specified.

119

ISBN: 978-972-8924-87-4 © 2009 IADIS

After defining tasks and assigning them to agents interaction among agents has to be designed. The goal of interaction design is to create the interaction diagram. Interactions among agents are specified in terms of sent messages. The interaction diagram consists of agents, actors representing users and links among them. Links among two agents denote messages and are labelled by predicates sent in the messages. Links from an actor to an agent denote events perceived by an agent and links from an agent to an actor denote methods of user interface that are invoked to communicate with an actor. Interactions are designed according to use case scenarios. If tasks that correspond to two consecutive steps in the use case scenario are realized by different agents, then a message has to be sent after completion of the first step of the use case scenario. In most cases a designer is able to define interactions by using use case scenarios and the task-agent diagram. However, these artefacts do not explicitly show interactions among agents and identification of interactions that are needed to implement complicated use cases is difficult. Thus, use case maps are created for most complicated use cases before the interaction design. Use case maps denote control passing among entities. In AOSE they show sequence of tasks done by agents explicitly showing required interactions among agents: each link among tasks that are assigned to different agents means that a message among these agents must be sent. Thus, after creating the use case map a designer merely has to add message content. During the interaction design message contents are designed using predicates from the domain ontology. So, the domain ontology has to be designed to specify message contents. The domain ontology in the MASITS methodology is a class diagram with two superclasses: “Concept” and “Predicate”. All other classes are subclasses of these two superclasses. The domain ontology is used in communication among agents and to represent agents’ beliefs.

3.3 Internal Design of Agents During the internal design of agents, the internal structure of agents must be defined. This stage must give an answer to the question, how agents achieve their behaviour specified during the external design. Two approaches of external design exist in AOSE methodologies. First, agents are designed using high level design concepts. These methodologies (for example, Gaia) provide designs that are independent from the agent development platform and thus have wider usage. However, transformation from high level design concepts to implementation ones is almost unique for each combination of methodology and agent development platform (Masonet, 2002). Second, agents are designed using low level concepts that correspond to the selected implementation platform. This approach enables easy transition to implementation phase and easy code generation. This is why it is followed in the MASITS methodology. JADE (Java Agent DEvelopment Framework, http://jade.tilab.com/) has been selected as the agent development platform. Therefore, agents must be designed in terms of messages sent and received, events perceived and actions done by agents. In the MASITS methodology agents are designed in the internal view of agents that is created iteratively by adding all elements corresponding to single action or single incoming message (event).The agent’s internal view consists of: • The agent diagram, showing incoming and outgoing interactions (denoted by links and contacts), actions performed by agents and relationships among them denoting sequence of actions (as it is shown in Figure 2). • Message receiving and start-up IF-THEN rules. Message receiving rules specify agent’s reaction to the received messages. Start-up rules specify agent’s actions during the start-up. • A list of agent’s beliefs that are specified by name and type of the belief. • Implementation details of actions. In JADE actions are implemented as behaviours. Thus, the name of the behaviour class and the type of the JADE behaviour are specified for every action. As shown in (Lavendelis & Grundspenkis, 2008), holonic agents have the following advantages in ITS development. Firstly, holonic architecture consists of small-scale agents that are easier implementable and reusable than large-scale agents. Secondly, holonic architecture enables easier change implementation allowing to modify the system to meet the needs of different courses. Thus, the MASITS methodology supports design of holonic MASs where each agent can be implemented as lower level MAS. If an agent is implemented as a holon, interaction design of the lower level MAS and internal design of each holon’s agent carried out done using above mentioned techniques.

120

IADIS International Conference Intelligent Systems and Agents 2009

Figure 2. The agent diagram

3.4 Implementation, Testing, Deployment, and Maintenance The holonic multi-agent architecture supported by the MASITS and described in (Lavendelis & Grundspenkis, 2008) consists of small scale agents that can be reused in systems with similar functionality. For example, if there is an agent that is capable to generate some kind of problems, then it can be reused in all systems that need to generate problems of that kind. The implementation phase consists of the following three steps. During the first step the abovementioned small scale agents are reused from previous projects. To facilitate the reuse process developers are advised to create a library consisting of all previously created lower level agents. The second step is code generation using the MASITS tool for agents that can not be reused from previously created systems. All classes of domain ontology, agents and their behaviours are generated. During the third step a programmer has to complete action() methods of behaviour classes generated by the system and create user interface of the system. During the testing phase JADE test suite (Cortese et al., 2005) is used to develop and execute tests. Three steps of testing are realized. Firstly, separate agents are tested by creating a test group for each agent and executing it. Secondly, each holon is tested as an integral entity, i.e., as an agent. Thirdly, the functionality of the whole system is tested using traditional testing methods. Deployment is accomplished by using modified version of the UML deployment diagram that shows JADE containers and agent instances deployed in each container. Agent instances are defined by names of agents and a class that is instantiated by an agent. The deployment diagram is used by the MASITS tool to generate a batch file that starts the JADE platform, containers, and all agents’ instances. The MASITS methodology supports change implementation into the system during the maintenance phase. The first step of change implementation is requirements analysis and identification of changes’ types. Three types of changes are distinguished: (1) modification of functionality corresponding to an open holon. In such case changes are implemented by adding/removing agents to the holon; (2) changes that have to be made inside one holon, but existing code has to be changed. In this case only one holon is redesigned and changed; (3) changes that must be made in higher level holon. The holonic multi-agent architecture for the ITS development does not help to implement this type of changes and a whole system must be redesigned.

4. TOOL SUPPORT The MASITS methodology is supported by the MASITS tool. The tool supports development of all diagrams that are used in the MASITS methodology. The user interface of the tool is shown in Figure 3. The tool enforces correct notation of each diagram and a consistency among all diagrams. A consistency is ensured by interdiagram relationships among elements with the same semantics in different diagrams. Each design element that is included in different diagrams can be changed only in one diagram and in case of any changes all other instances of that element are changed automatically. For example, an agent can be deleted or its name can be changed only in the interaction diagram. In case of any changes all other occurrences of the agent are changed. This enables an iterative approach during the development: a developer is allowed to return to previously created diagrams and refine them. When any diagram is refined, all later diagrams are changed according to changes made in the refined diagram. Above mentioned interdiagram relationships are created automatically. Additional interdiagram relationships are used for crosschecks among models. These relationships are created manually using specific

121

ISBN: 978-972-8924-87-4 © 2009 IADIS

user interface in the MASITS tool. Manually created interdiagram relationships are defined to analyse how elements of one diagram are supported by other diagrams.

Figure 3. MASITS tool

The MASITS tool helps developers by automatically generating parts of diagrams that can be inferred from other diagrams. For example, incoming and outgoing messages in the agent’s diagram are generated when a message is added to the interaction diagram. Additionally, the holon hierarchy diagram showing all holons in the system is completely generated from holon diagrams. The most important functionality of the MASITS tool is code generation from the design diagrams. JADE agents, behaviours and ontology classes are generated. The ontology is completely generated from the ontology diagram. Agents and their behaviours are generated from agents’ internal views. After code generation a programmer has to complete action() methods of each behaviour. In addition, the user interface has to be developed independently from the MASITS tool. For details about the MASITS tool and code generation from MASITS diagrams, see (Lavendelis & Grundspenkis, 2009c).

5. CASE STUDY The MASITS methodology and tool have been used to develop the ITS for the first year graduate course “Fundamentals of artificial intelligence”. The course teaches several different algorithms. Thus, an important part of the course is practical usage of learned algorithms. The ITS for such course should concentrate on the practical execution of algorithms. The developed system supports the following learning process. When a learner registers in the system, a curriculum is generated for him/her. A curriculum consists of modules that, in their turn, consist of themes. In each theme a learner is supplied with a learning material. After finishing studying the material, a learner receives a problem to solve according to the theme. When the learner has finished solving the problem, his/her solution is evaluated by the system and feedback to the learner is given. Problems given to a learner are of different type: various kinds of tests (single choice tests, multiple choice tests and fill in blanks), search algorithm execution tasks and two person game algorithm execution tasks are used in the current version of the system. The following criteria are used to choose the problem for a learner: (1) adequacy of the level of complexity of the task to the learner’s knowledge level, (2) adequacy to learner’s preferences like size of the problem, practicality of the problem and (3) frequency of similar tasks given to a learner. Such approach allows to provide unique problems to each learner and to adapt problems to all individual learners. The holonic multi-agent architecture for ITS development (proposed in (Lavendelis & Grundspenkis, 2008)) is used to implement the system. The higher level holon consists of the following agents: an interface agent, a curriculum agent, a teaching strategy agent, a student modelling agent, a problem generation agent, a knowledge evaluation agent, an expert agent and a feedback generation agent. A problem generation agent, an interface agent, an expert agent and a knowledge evaluation agent are developed as holons that include a

122

IADIS International Conference Intelligent Systems and Agents 2009

body agent for each type of problems to allow easy modifying a set of used problems. A new type of problem can be added by extending the domain ontology with concepts and predicates that correspond to the added type of the problem and adding agents to the above mentioned second level holons corresponding to the new type of problems. This allows modifying a set of available types of problems without modifying the rest of the system. It can be used either during the further development of the system for current course or by adapting the system to other similar courses. As mentioned in Section 3.4, agents that can be reused are added to the library of reusable agents. All agents from lower level holons correspond to specific type of problems and, as a consequence, can be reused in other ITSs that include the same type of problems. The only limitation of agents’ reuse is the need to use same ontology classes (concepts and predicates) describing the problem and its solutions. Code of all agents and ontology was generated by the MASITS tool. The ontology was completely generated. Agent classes (more precisely their behaviours) were completed manually. The relative amount of manually written code varied from 20 to 60 percent in different agent classes (60 percent were manually written for problem visualisation agents that have to build appropriate parts of user interface). Additionally, user interface and ?> . . Figure 5. Selected segment OWL code for car rental ontology.

Professional agent layer: According to the TAS example and the goal layer, there are three professional agents see Figure 6. The main elements of the agent inter-structure have to be developed for every agent. Skill agent Layer: The Skill agent layer is concerned with three aspects of the process: the professional agent under which it performs, the execution sequence, and which services it executes. The plan and the database of the TAS are also considered at this stage as it shown in Figure 7.

Figure 6. Professional agent and goals.

Figure 7. Professional agent to skill agent under Package goal.

5. CONCLUSION AND FUTURE WORK The agent-based system has introduced a new feature that adds challenges to software engineering. Many tools and methodologies have been developed to engineer agent behaviour, and all have their advantages and disadvantages. An ideal agent-based system must allow agents to be autonomous behaviour and to cooperate. The ATM architecture is an agent-based system architecture that is cooperative, goal-oriented, loosely coupled, and dynamic. Implementing these features requires partitioning the system’s characteristics from the agent’s actions. In ATM, the system characteristics are partitioned from the agent’s acts by using a servicesrelated semantic approach and web ontology tools like OWL, RDF, RDF-S, and XML. This technique provides an efficient methodology for developing cooperative software agent-based systems. ATM is currently in the implementation phase. The ATM architecture will be used as a framework for a new agent-based development methodology, and the result of this project will be reported in the near future.

223

ISBN: 978-972-8924-87-4 © 2009 IADIS

REFERENCES Aglet Development Toolkit http://aglets.sourceforge.net/ 23/07/2008 Alhashel, E. (2008) A Conceptual Agent Cooperation Model for Multi-agent Systems' Team Formation Process. Proceedings of the 2008 Third International Conference on Convergence and Hybrid Information Technology Volume 01. IEEE Computer Society Alhashel, E., Balachandran, B. & Sharma, D. (2007) Comparison of Three Agent-Oriented Software Development Methodologies: ROADMAP, Prometheus, and MaSE. KES2007. ITALY, Springer Alhashel, E. & Mohammadain, M. (2008), Illustration of Multi-agent Systems. CIMCA, Austria - Vienna, Vol., pp. Bellifemine, F., Caire, G. & Greenwood, D. (2007) Developing Multi-agent Systems with JADE, West Sussex England, Wiley. Braubach, L., Pokahr, A. & Lamersdorf, W. (2005) Jadex: A BDI-Agent System Combining Middleware and Reasoning. Software Agent-Based Applications, Platforms and Development Kits. Birkhäuser Basel 143 - 168. Bresciani, P., Giorgini, P., Giunchiglia, F., Mylopoulos, J. & Perini, A. (2004), Tropos: An Agent-Oriented Software Development Methodology. Autonomous Agents and Multi-Agent Systems, Netherlands, Vol.: 8, pp: 203-236. Cognitive Agent Architecture (Cougaar) Project http://www.cougaar.org/ 17/04/2009 OWL-S: Sementic Markup for Web Services http://www.w3.org/Submission/OWL-S/ 10/04/2009 JACK Development Toolkit http://www.agent-software.com/ 07/07/2008 Jennings, N. R. (2000), On Agent-based Software Engineering. International Joint Conference on Artificial Intelligance (IJCAI), Stockholm, Vol.: 117, pp: 277-279. Juan T., A. S. L. (2003) The ROADMAP Meta-Model for Intelligent Adaptive Multi-Agent Systems in Open Environments. Kinny, D., Georgef, M. & Rao, A. (1996), A Methodology and Modelling Technique for System of BDI Agents. Modelling Autonomous Agents in a Multi-Agent World MAAMAW'96, Germany, Vol.: LNAI 1038, pp. Luck, M., Ashri, R. & D'inverno, M. (2004) Agent-Based Software Development, London, Artec House Inc. Luck, M. & D'inverno, M. (1996a), Engagement and Cooperation in Motivated Agent Modelling. Distributed Artificial Intelligence Architecture and Modelling, Australia, Vol., pp. Luck, M. & D'inverno, M. (1996b), A Formal Framework for Agency and Autonomy. International Conference on MultiAgent Systems, Vol., pp: 254--260. Padgham, L. & Michael, W. (2004) Developing Intelligent Agent Systems, England, John Wiley & Sons, Ltd 23 82. RETSINA Development Toolkit http://www.ri.cmu.edu/projects/project_76.html 24/06/2008 Wood, M. F. & Deloach, S. A. (2001), An Overview of the Multi-agent System Engineering Methodology. First International Workshop on Agent-Oriented Software Engineering, Limerick Ireland, Vol.: 1957, pp: 207-221. Wooldridge, M., Jennings, N. & Kinny, D. (2000), The Gaia Methodology for Agent-Oriented Analysis and Design. Autonomous Agents and Multi-Agent Systems, Netherland, Vol.: 3, pp: 285 - 312. development toolkit http://labs.bt.com/projects/agents/zeus/ 12/09/2008

224

IADIS International Conference Intelligent Systems and Agents 2009

FINITE, REASONING AND INTERACTING AGENTS Michal Walicki, Paul Simon Svanberg1 University of Bergen, Department of Informatics

ABSTRACT We present a framework for modeling and reasoning about interactions between finite agents with arbitrary reasoning capabilities. The framework is sound, complete and decidable whenever the agents themselves have sound, complete and decidable logics to reason with. KEYWORDS Epistemic logic, knowledge representation, temporal reasoning, interactive agents, logical omniscience, security protocols.

1. INTRODUCTION Software agents manipulate symbolic representations. Following Eberle [1974]; Moore & Hendrix [1979]; Halpern & Moses [1990] and, especially, variants of syntactic structures, Fagin et al. [1995]; Ågotnes [2004]; Ågotnes & Alechina [2007], we represent agents as syntactic units: at any point, the state of an agent is a set of formulae which it has available for further manipulation. This representation allows us to propose a generic framework in which agents can be equipped with arbitrary rules, allowing them to draw consequences from the available formulae. The semantics of an agent is not the totality of its implicit knowledge, but the finite states which it can reach. Thus, avoiding the omniscience problem, we do not weaken the agent’s reasoning capacities. Its finite state represents its explicit knowledge, distinct from all reachable states representing, together, its implicit knowledge. This distinction, following, e.g., Levesque [1984]; Lakemeyer [1987]; Fagin & Halpern [1988]; Duc [1997], seems to us a better way around the omniscience problem than limiting agents’ reasoning or using nonstandard logics, e.g., Fagin et al. [1996]. In addition to internal reasoning, agents can change their states by interaction with the environment. This aspect is modeled with sequence logic, introduced by Bezem et al. [2007]. Using it, Walicki et al. [2009] gave a preliminary model for interaction of reasoning agents. The present paper provides a complete framework in which arbitrary reasoning agents can be modeled as finite entities, interacting in sequences of communication steps. In section 2 we define the format of agent logics; section 3 introduces a logic to describe the reasoning of finite agents and the corresponding calculus; section 4 introduces sequence logic and illustrates a possible application of the whole framework. Due to space limitations, examples of applications of the framework and proofs of propositions have been left out. These can be obtained by contacting the authors.

2. FINITE REASONING AGENTS Let denote a set of agent names, each associated with some reasoning mechanism, namely a language, , and a set of axioms and rules. Reasoning mechanisms for different agents may be different, but we simplify the presentation by making them all identical.

1 The work has been funded by the Norwegian Research Council, under the project Secure Heterogeneous Information Presentation (SHIP).

225

ISBN: 978-972-8924-87-4 © 2009 IADIS

An agent’s state is always a finite subset of , , to which new formulae, derivable from , can be added. Agent logic is assumed given in a natural deduction style (allowing to reason from assumptions) by rules, , where and extends (the basis of its definition) with a disjoint set of formula-variables. Definition 2.1 (Agent Logics).

Obviously, for every , where denotes derivability of the rules . In the following, we do not distinguish these two relations.

from

using

3. DESCRIBING REASONING AGENTS To reason about specifications of agents and to verify whether some agents can achieve particular goals, we introduce description language for specification of (formulae derivable by) agents, and the associated logic (not to be confused with the description logic from Baader et al. [2003]). Definition 3.2 (Description Logic).

The other propositional connectives, and and , can be defined in the usual way, and will be used for convenience. Assuming a fixed, common set of rules, we usually drop the rules and agent subscripts and . A formula can be read as “agent can derive each formula in ” or “agent i knows at least x”. The model class of such a formula is the set of finite states from which all formulae in can be derived. Notwithstanding this, say, dynamic or modal aspect, the definition preserves the usual connections between the propositional connectives and the set operations on the model classes.

226

IADIS International Conference Intelligent Systems and Agents 2009

3.1 “Only Knowing” and Minimal Models When describing agents, we specify their explicit knowledge with the often implicit assumption that the description covers all that the agents actually know. In standard modal logics, such a restriction would require infinitely many formulae, each stating that agent does not know some formula. Various attempts have been made to capture the notion of knowledge’s upper bound, “only knowing”, e.g., Moore [1983]; Halpern & Moses [1985]; Levesque [1990]; Halpern & Lakemeyer [1996]; Halpern [1997]; Ågotnes [2004]. We achieve this by restricting the models to the minimal model class, containing only states corresponding exactly to the description of the agent. Assume that in a specification of a cryptographic protocol, we state that an agent knows the message encoded with the key , . The agent can only access from if it has the key . The description should not entail the conclusion – in fact, it should entail , since knowing only , the agent is not able to reach a state containing . However, as but , such a conclusion does not follow. Restriction to the minimal model class, on the other hand, gives the intended interpretation since . Definition 3.3

Note the clause  2(b). Restriction to minimal models releases the specifier from stating negative information – it follows from the positive one. Under this restriction, the single formula implies . On the other hand, trying to reason about the agent from negative information only, e.g., only from , does not entitle us to assume that the agent knows anything at all, i.e., allows us only to reason from the tautology that it knows at least nothing, .

3.2 Reasoning about Reasoning Agents The agent description acts as a specification, from which one wants to conclude that every agent satisfying this description can reach a certain goal, a state satisfying some desired (or undesired) properties. Such a relation between a specification and a goal is given in form of a sequent, , where are finite sets of formulae in . Its intuitive reading is “any agent who, as far as we know, knows only whatever is prescribed by the specification , can reach the goal ”. For instance, can be read as “if knows (only) , it can reach a state containing ”, and as “if knows (only) , it cannot reach a state containing ”. Consequently, we define validity of a sequent by: Definition 3.4 (Validity).

indicates that processing one side of a sequent by The use of different model classes on both sides of the reasoning system should be independent from the processing the other side. For each side we have a set on the left as conjunction and, on of rules for one-sided sequents, with the propositional rules treating the right, as disjunction. In the following reasoning system, the logic of individual agents is a parameter used to determine if a given sequent is axiomatic or not. Definition 3.5 (Description Calculus).

227

ISBN: 978-972-8924-87-4 © 2009 IADIS

Standard rules for other propositional connectives can be added in the usual way. The following proposition is easily proved using standard techniques. Proposition 3.6. Description logic is sound, complete, and, given a decidable , decidable.

4. INTERACTIONS AS STATE TRANSITIONS Description logic allows us to verify reachability of one state from another by means of an agent’s reasoning. Communication amounts to updating a state with new information acquired from the outside (another agent, the environment, etc.) We express this as a transition between subsequent agent descriptions which, , the transition semantically, amounts to a transition between agents’ states. For instance, if may represent agent’s reasoning, but when , it reflects an input from the environment. Following Walicki et al. [2009], for specification of communication sequences we use sequence logic, introduced by Bezem et al. [2007]. Although it is only a subset of LTL, its parameterization by an arbitrary and . Sequence logic is interpreted over logic gives a flexible and expressive tool. As parameter, we use total orderings (with a start, but no end point). Definition 4.7 (Sequence Logic).

228

IADIS International Conference Intelligent Systems and Agents 2009

From the variants of orderings considered by Bezem et al. [2007], we present only the case of dense orderings. Definition 4.8 (Sequence Calculus). and is either an ‐formula or empty.

The sideconditions in square brackets are called proof obligations. Proposition 4.9 Sequence logic over dense orderings is sound, complete and decidable, provided that the parameter logic also has these properties. The generic character of the presented framework can be appreciated as follows. Any kind of reasoning agent can be modeled faithfully, in the sense that its reasoning capacities, when embedded into the framework, are exactly the same as when it is considered in isolation. A variety of linear time models is available through the choice of the appropriate variant of sequence logic, while concurrent actions of several agents are represented by conjunctions of the formulae describing the state of each single one.

4.1 Example: Learning a Key, Decrypting a Message To illustrate how the separate pieces of the framework comes together as a whole, we consider a simple example motivated by security protocols. is in this case the language of unencrypted messages , keys and encrypted messages . The rule of decryption, , is here the only rule defining agent reasoning ( ). We verify that if an agent knowing learns the key by interacting with the environment in some unspecified way, e.g., communication, looking it up in a table, etc, it will eventually be able to know the message . I.e., we verify the sequence , where the left hand side sequence, , means that the agent initially knowing only comes to learn , and the right hand side sequence, , means that after some time has passed, the agent will be able to know . (1.) We first derive

in the sequence calculus:

(2.) We must verify the proof-obligations and trivially. We verify the latter using the description calculus:

(3.) On the level of agent reasoning, the proof-obligation . This completes the verification.

. The first holds

is easily verified as

229

ISBN: 978-972-8924-87-4 © 2009 IADIS

5. CONCLUSION We have introduced a three-tiered framework for modeling finite, reasoning and interacting agents and given an example of how the different modules work together. The modular nature of the framework ensures a high degree of genericity. The problem of logical omniscient agents is avoided. The framework lifts soundness, completeness and decidability of agent reasoning to a temporal, epistemic setting, and has applications to, e.g., verification of properties of security protocols and analysis of distributed information systems.

REFERENCES T. Ågotnes (2004). A Logic of Finite Syntactic Epistemic States. Ph.D Thesis, Department of Informatics, University of Bergen. T. Ågotnes & N. Alechina (2007). ‘The dynamics of syntactic knowledge’. Journal of Logic and Computation 17(1). F. Baader, et al. (2003). The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK. M. Bezem, et al. (2007). ‘Completeness and decidability in sequence logic’. In Proceedings of LPAR’07, vol 4970 of LNAI. H. N. Duch (1997). ‘Reasoning about rational, but not logically omniscient, agents’. Journal of Logic and Computation 7. R. A. Eberle (1974). ‘A logic of believing, knowing and inferring’. Synthese 26:356-382. R. Fagin & J. Halpern (1988). ‘Belief, awareness and limited reasoning’. Artificial Intelligence 34:39-76. R. Fagin, et al. (1995). Reasoning about Knowledge. The MIT Press, Cambridge, Massachusetts. R. Fagin, et al. (1996). ‘A nonstandard approach to the logical omniscience problem’. Artificial Intelligence 79(2): 203240. J. Halpern (1997). ‘A theory of knowledge and ignorance for many agents’. Journal of Logic and Computation 7(1): 79108. J. Halpern & G. Lakemeyer (1996). ‘Multi-agent only knowing’. In Y. Shoham (ed.), Proceedings of the 6-th TARK, pp. 251-265. Morgan Kaufmann. J. Halpern & Y. Moses (1985). ‘Towards a theory of knowledge and ignorance’. In K. Apt (ed.), Logic and Models of Concurrent Systems, pp. 459-476. Springer. J. Halpern & Y. Moses (1990). ‘Knowledge and common knowledge in a distributed environment’. Journal of the ACM 37(3):549-587. G. Lakemeyer (1987). ‘Tractable meta-reasoning in propositional logic of belief’. In J. McDermott (ed.), Proceedings of the 10-th IJCAI, pp. 401-408. Morgan Kaufmann. H. J. Levesque (1990). ‘All I know: a study in autoepistemic logic’. Artificial Intelligence 42:263-309. R. Moore (1983). ‘Semantical considerations on nonmonotonic logic’. In A. Bundy (ed.), Proceedings of the 8-th IJCAI, pp. 272-279. Morgan Kaufmann. M. Walicki, et al. (2009). ‘Developing Bounded Reasoning’. Journal of Logic, Language and Information 18(1):97-129.

230

IADIS International Conference Intelligent Systems and Agents 2009

AMBIENT ACTIVITY RECOGNITION: A POSSIBILISTIC APPROACH Patrice C. Roy*, Bruno Bouchard†, Abdenour Bouzouane† and Sylvain Giroux* *

Domus Laboratory Université de Sherbrooke, Sherbrooke, Canada † LIAPA Laboratory Université du Québec à Chicoutimi, Chicoutimi, Canada

ABSTRACT The development towards ambient computing will stimulate research in many fields of artificial intelligence, such as activities recognition. To address this challenging issue, we present a formal framework based on possibility theory which is largely different from the majority of all recognition models proposed that usually use probability theory and its extension. To validate this novel alternative, we are developing an ambient agent for the cognitive assistance of an Alzheimer’s patient within a smart home, in order to identify the various ways of supporting him in carrying out his activities of daily living. KEYWORDS Ambient Intelligence, Activity recognition, Possibilistic Description logic, Smart Homes, Cognitive assistance

1. INTRODUCTION Combining ambient assisted living with techniques from activities recognition greatly increases its acceptance and makes it more capable of providing a better quality of life for elderly people with or without disabilities (Casas et al., 2008). Activity recognition aims to recognize the action and goals of one or more agents from a series of observations on the environmental conditions. Research addressing recognition problem in smart environments refer to activity recognition as plan recognition, which relates behaviors to the performer’s goals. The plan recognition problem has been an active research topic (Augusto and Nugent, 2006; Kautz et al., 2003) for a long time and still remains very challenging. The keyhole, adversarial or intended plan recognition problem (Geib, 2007) is usually based on a probabilistic-logical inference for the construction of hypotheses about the possible plans, and on a matching process linking the observations with some plans included in a library or model of activities related to the application domain. Since there can be many possible plans that can explain the observations, and thus the behavior of the observed agent, the challenge is then to disambiguate these concurrent hypotheses. (Kautz, 1991) presented the first formal model of plan recognition, using first-order logic and McCarthy’s circumscription theory in order to formalize the recognition plans by a deduction process. The recognition agent explains the observed actions by using a collection of plan schemes and minimal covering sets as principles for disambiguation. A significant limitation to their approach comes from the equiprobability problem, where a hypothesis cannot be privileged within the set of possible activities. To deal with this problem as well as the uncertainty inherent in activities recognition in a dynamic environment, probabilistic models have been proposed for defining plan recognition as probabilistic reasoning based primarily on some bayesian or markovian models (Liao et al., 2004; Philipose et al., 2004). The basic idea consists of generating a belief network from observed actions and world states according to some conditional probability distributions, which govern the transition states and thereby the explanation of the behavior. Emerging hybrid models (Geib, 2007; Roy et al., 2009) combine these two different avenues of research, in order to disambiguate more efficiently the possible hypotheses that can explain the observations. Besides the logico-probabilistic approaches, some researchers (Avrahami-Zilberbrand and Kaminka, 2007) view plan recognition as inferring the decisionmaking strategy of the observed agent based on utility theory. Their approaches explicitly take the observed

231

ISBN: 978-972-8924-87-4 © 2009 IADIS

agent’s preferences into consideration, and compute the estimated expected utilities of plans to disambiguate competing hypotheses based on the maximization principle. Though it seems interesting, in the case where the exact utility function is difficult to estimate, such as in the context of cognitive assistance, the recognizing process will be compromised. The vast majority of previous works focused on probabilistically oriented solutions based primarily on some markovian models. The limitations of these approaches emanate from the extensive use of the concept of probability, where the inference itself requires large numbers of prior and conditional probabilities. For example, in the context of assistive cognition within smart homes, requiring humans to specify the habitat’s object involvement probabilities is time consuming and difficult when we consider all the potential objects involved in each stage of an activity, given the large numbers of activities performed. Moreover, probabilities do not allow representing complete ignorance. There are numerous situations where it is not possible to give the agent a set of probabilities based on statistical measures, but only qualitative information provided by experts or deduced from previous experiences. At our lab, we investigate possibility theory (Dubois and Prade, 1988) to address this issue of recognizing behaviors classified according to cognitive errors. These recognition results are used to identify the various ways a smart home may help an Alzheimer’s occupant at early-intermediate stages to carry out his activities of daily living (ADL). This context increases the recognition complexity in such a way that the presumption of the observed agent’s coherency, usually supposed in the literature, cannot be reasonably maintained. We propose a formal framework for activities recognition based on Possibilistic Description Logic (Qi et al., 2007), which transforms the recognition problem into a possibilistic classification of ADLs. The measurements of necessity and possibility of the activities will depend on the correlation between the data collected through the various distributed sensors of the smart home. From these measurements, we will deduce the confidence interval of the normal and abnormal behaviors. We can primarily justify the use of a confidence interval rather than a point probability, as previous approaches traditionally used, since all is possible in the case of Alzheimer’s behavior. Hence, unusual behavior is not considered as the residual result of normal behavior. More precisely, measurements of possibilities of the erroneous and normal activities can converge respectively towards the maximum value of the confidence interval. It’s one of the aspects that the theory of probability cannot take into account. The paper is organized as follows. Section 2 presents our new possibilistic recognition model. Section 3 shows our advances in the implementation of this model in the Domus smart home laboratory, to concretely address ADL recognition of Alzheimer’s patients. We also discuss how this new model will increase the recognition accuracy under our previous results, obtained with a set of real case scenarios. Finally, we conclude the paper by insisting on future perspectives of this work.

2. POSSIBILISTIC RECOGNITION MODEL OVERVIEW Possibility theory is an uncertainty theory that is devoted to handling incomplete information (Dubois and Prade, 1988). Like probability theory, it is based on set functions, but differs from it by using a pair of set functions (possibility and necessity measures) instead of only one. In addition, unlike the probability theory, where the probability of disjoined events is the sum of their probabilities, the possibility of such events is the maximum event’s possibility. The observer agent has knowledge concerning the resident’s environment, which is represented by using a formalism in description logic(DL). DL is a family of knowledge representation formalisms that may be viewed as a subset of first-order logic, and its expressive power goes beyond propositional logic, although reasoning is still decidable (Baader et al., 2007). In a possibilistic DL, the terminological and assertional axioms have a possibility degree value associated with them. Let S be the set of environment states. A context can be defined as a set of environment properties that are true at some point in time. Semantically, a context represents a subset of the set S of environment states. The possibilistic recognition model uses an action ontology A in order to represent the basic actions that an observed agent is able to perform in the environment. In order to take into account the uncertainty and the imprecision related to the environment observation, two possibility distributions concerning the environment state context are defined for each action: the degree of possibility that a context allows the initiation of an action and the degree of possibility that a transition between two contexts results from the execution of a particular action. Each possibility distribution must be normalized, which means that at least one value is fully possible (= 1). By using a sequence relation ◦, subsets of actions are partially ordered with the aim to define an ontology of activities P, which consists of the known activities of the observed agent. An activity is defined as a plan

232

IADIS International Conference Intelligent Systems and Agents 2009

structure, which consists of a sequence of actions that allows one to accomplish the activity goal. This sequence relation ◦ allows to define a temporal and an order constraints between the actions in the activity. The temporal constraint consists to the minimum and maximum delays between the two actions execution in the activity. The recognition process uses the observed actions to evaluate which activities could be carried out and if errors are associated with the realization of them. Since several actions can explain the changes observed in the environment, we must define possibility and necessity measures to be able to disambiguate them. When events from an action occurrence are detected with the sensors in the environment at a time t, a low-level agent generates the current state, which can be partial, of the environment with assertions in DL, according to the terminology of the environment. This set of assertions is labeled obst. By using this observation obst, the action recognition agent evaluates, for each action a, the possibility and necessity measures of action prediction (Πinit(a) and Ninit(a)) and action recognition (Πrec(a) and Nrec(a)) according to the contexts that are entailed the observation obst. The possibility (necessity) of action prediction indicates the possibility (necessity) that an action a will be performed according the observation obst of the environment’s current state. The possibility (necessity) of action recognition indicates the possibility (necessity) that an action a was performed according to the observations obst and obst - 1 of the environment’s current and previous states. Then, for each observation obst of the environment, we have a possible action observation set Ot, which consists to the set of actions that is partially ranked according to the possibility and necessity values of action prediction and action recognition. Each possible action observation set Ot is inserted into the set O of all possible action observation sets by using the observation addition operation ⊕obs, which allows to adjust the possibilities and necessities of action recognition according to those of action prediction in the previous possible action observation set Ot-1. The set of possible action observations O allows us to select the most possible and necessary actions for each observation obst in order to have a set of recognized actions AO, which is used to generate hypotheses concerning the behavior of the observed agent.

2.1 Behavior Recognition This set AO allows us to generate a set of possible performances of the activities, such that we have activity execution paths that could explain subsets of possible recognized actions in AO. These possible execution paths Pathexe are used to generate normal or erroneous behaviors interpreting the performance of the patient. A partial execution path Pathexe,i consists of a subset of an activity’s actions, each one with a time tag t, that respects the order and time constraints defined in the activity. Thus, a partial execution path represents a coherent execution of a part of the activity, according to the set of recognized actions AO. Also, the set of partial execution paths Pathexe can contain different execution paths for the same activity. For each new AO, the set Pathexe is updated by removing the partial paths that become temporally inconsistent, by extending the existing partial paths in Pathexe, and by inserting new partial paths that take into account the last observation. With the set of execution paths Pathexe, we define a set of action paths Path, where each action path Pathi is generated by selecting partial execution paths of different activities, aiming to have normal behaviors that could explain the recognized actions. In an action path Pathi, each observation time tag t must have only one action that is associated and all actions in the partial execution paths Pathi must be associated to an observation time tag t. Also, several partial paths can share the same action for an observation time tag t in an action Pathi. We have an incomplete path Pathinc,j when the partial paths cannot cover all the observation time tags t. For each time tag t that is not covered by a partial path, the set of recognized actions AOt associated with t in the set of recognized actions AO is used instead. The set of complete action paths Path represents the hypotheses concerning different normal behaviors BevN. A normal behavior represents a coherent partial execution of one or several activities where each action between the first action and the last observed action in each activity must be observed (order constraint) and all recognized actions in each activity must respect the minimal and maximal delays between each action realization (time constraint). The set of incomplete action paths Pathinc represents the hypotheses concerning erroneous behaviors BevE. An erroneous behavior represents an erroneous occurrence of some activities while others can be carried out in a coherent way. From this point, the recognition agent has determined the set of plausible hypotheses, BevN and BevE, concerning the behavior of the observed patient. By defining possibility and necessity measures on these behaviors, we are able to circumscribe them before sending these hypotheses to an assistance agent. The possibility ΠBev(BevNi) (necessity NBev(BevNi)) of a normal behavior

233

ISBN: 978-972-8924-87-4 © 2009 IADIS

BevNi is obtained by taking the maximum (minimum) action recognition possibility (necessity) value of actions of the longest partial path in the behavior. Thus, we obtain an interval of confidence [NBev(BevNi), ΠBev(BevNi)] concerning the normal behavior BevNi. The possibility ΠBev(BevEj) (necessity NBev(BevEj)) of an erroneous behavior BevEj is obtained by taking the maximum (minimum) between the maximum (minimum) action recognition possibility (necessity) value of actions of the longest partial path and the maximum (minimum) action recognition possibility (necessity) value of the actions in the AOt sets in the behavior. Thus, we obtain an interval of confidence [NBev(BevEj), ΠBev(BevEj)] concerning the occurrence of the erroneous behavior BevEj. Then, for each new observation obst, we generate a set of normal behaviors BevN and a set of erroneous behaviors BevE, which are ranked according to the possibilities and necessities of each behavior. By using the formal tools previously presented, we can formulate Algorithm 1, which describes the principal steps in the recognition process. procedure RECOGNITION(obst, O, A, P, Pathexe) Ot ← evaluateActionPossibility(obst, A) O ← insertObservedAction(O, Ot) AO ← selectRecognizedAction(O) Pathexe ← updateExecutionPath(Pathexe, AO, P) (Path, Pathinc) ← getBehavior(Pathexe) BevN ← evaluateNormalBehaviorPossibility(Path) BevE ← evaluateErroneousBehaviorPossibility(Pathinc) return (BevN, BevE) end procedure Algorithm 1. Recognition process algorithm

Let us summarize the progress of Algorithm 1 in order to further illustrate the process of behavior recognition. To recognize the behavior of the observed agent at t, the recognition agent uses the environmental observations obst, to generate behavioral hypotheses. By using obst, the actions in A are ranked according to the possibility and necessity of their prediction and recognition, constituting thereby the possible action observation Ot. This Ot is then inserted into the set of possible action observations O by using the addition operation ⊕obs. By selecting the recognized actions AO in O, using the possibility and necessity of action recognition, the recognition agent evaluates all possible partial realizations Pathexe of the activities in P and uses them to evaluate possible normal behaviors Path and erroneous behaviors Pathinc. These behaviors, which can implicate several activities, can be a normal (erroneous) occurrence of all (some) of them. The normal and erroneous behaviors Path and Pathinc are then ranked according to the possibility and necessity values in BevN and BevE. By using the behaviors ranked by the recognition agent, the assistance agent will be able to plan an assistance task if needed.

3. VALIDATION The experimental infrastructure of our lab consists of an apartment equipped with sensors, smart tags (RFID), pressure mats, localization and identification systems for objects and people, audio and video devices, etc. The software architecture works as follows. Basic events are generated by sensors and are directly sent to a low level activity recognition (LAR) agent, which has a virtual representation of the habitat’s environment encoded in a Powerloom description logic knowledge base. When a low-level action is detected, the LAR agent notifies the High-Level Recognition (HLR) agent by sending the action’s type (Bouchard et al., 2007). This HLR is actually implemented with the former version of our recognition model (Roy et al., 2009), which exploited probabilistic DL. We are currently implementing the possibilistic model presented in this paper in the software framework of the smart home infrastructure. We conducted a efficiency study on our former probabilistic model, where the objective was to evaluate in what proportion that model was able to recognize the behavior of an Alzheimer’s patient in a simulation context. This experimentation shown promising results, presented in (Roy et al., 2009), but remains limited and unable to recognize some specific erroneous patterns. We expect several improved results with the new approach. For instance, a limitation of the previous model concerns the fact that only one action could explain the environmental changes, which is a strong assumption in environment where information is uncertain and imprecise. By using possibility theory,

234

IADIS International Conference Intelligent Systems and Agents 2009

the proposed model will be able to suppose that we can have more than one action with the highest possibility and necessity measures concerning which action can explain the observed changes in the environment. Recognition results will then be refined by using this qualitative evaluation of the imprecision concerning the performance of a basic action. Therefore, we expect that the new results will show that the possibilistic approach is better suited than the probabilistic one for our applicative context, where the patient often changes his habits and has, most of the time, an inconsistent behavior over a long period.

4. CONCLUSION This paper has presented a formal framework for activities recognition based on possibilistic DL as the semantic model of the agent’s behavior. This framework constitutes a first step towards a more expressive ambient agent recognizer, which will facilitate to support the fuzzy and uncertainty constraints inherently to the smart environment. Moreover, the next logical step consists in conducting an extension of this framework in order to simultaneously deal with the vagueness of an activity’s duration and the noises of the sensors. The measurements of necessity and possibility will depend on the correlation between these constraints, allowing us to further refine the explanation of the activities. Finally, we believe that considerable future work and large scale experimentations will be necessary, in a more advanced stage, to help evaluate the effectiveness of the model.

REFERENCES Augusto, J. C. and Nugent, C. D. (eds) , 2006. Designing Smart Homes: The Role of Artificial Intelligence. Vol. 4008 of LNAI, Springer-Verlag, Berlin, Germany. Avrahami-Zilberbrand, D. and Kaminka, G. A. , 2007. Utility-based plan recognition: an extended abstract. Proc. of the 6th int. joint conf. on Autonomous agents and multiagent systems, Honolulu, Hawaii, USA, pp. 858-860. Baader, F. et al. (eds), 2007. The Description Logic Handbook: Theory, Implementation, and Applications, Second edition. Cambridge University Press, Cambridge, UK. Bouchard, B. et al., 2007. A keyhole plan recognition model for Alzheimer’s patients: First results. Applied Artificial Intelligence: An Int. J., Vol. 22, No. 7, pp. 623-658. Casas, R. et al., 2008. User modelling in ambient intelligence for elderly and disabled people. Proc. of the 11th int. conf. on Computers Helping People with Special Needs, Linz, Austria, pp. 114-122. Dubois, D. and Prade, H., 1988. Possibility Theory: An Approach to Computerized Processing of Uncertainty. Plenum Press, New York, USA. Geib, C., 2007. Plan recognition, in A. Kott and W. M. McEneaney (eds), Adversarial Reasoning: Computational Approaches to Reading the Opponent’s Mind, Chapman & Hall/CRC, Florida, USA, pp. 77-100. Kautz, H. A., 1991. A formal theory of plan recognition and its implementation. in J. F. Allen, H. A. Kautz, R. N. Pelavin and J. D. Tenenberg (eds), Reasoning About Plans, Morgan Kaufmann Pub., San Francisco, CA, USA, pp. 69-126. Kautz, H. et al., 2003. Foundation of assisted cognition system. Technical Report CSE-02-AC-01. U. of Washington. Liao, L. et al., 2004. Learning and inferring transportation routines. In Proc. of the 19th National Conf. on Artificial Intelligence (AAAI’04), San Jose, CA, USA, pp. 348-353. Philipose, M. et al., 2004. Inferring activities from interactions with objects. IEEE Pervasive Computing, Vol. 3, No. 4, pp. 50-57. Qi, G. et al., 2007. Extending description logics with uncertainty reasoning in possibilistic logic. In Proc of the 9th ECSQARU, Hammamet, Tunisia, pp. 828-839. Roy, P. et al., 2009. A hybrid plan recognition model for Alzheimer’s patients: Interleaved–erroneous dilemma (accepted for publication). Web Intelligence and Agent Systems: An International Journal Vol. 7, No. 4, pp. 1-23.

235

ISBN: 978-972-8924-87-4 © 2009 IADIS

EVACUATION BEHAVIORS IN AN EMERGENCY STATION BY AGENT-BASED APPROACH Kazuki Satoh *1, Toru Takahashi *, Takashi Yamada *, Atsushi Yoshikawa * Takao Terano * Tokyo Institute of Technology* 4259 Nagatsuta-cho, Midori-ku, Yokohama, Kanagawa, 226-8502 Japan.*

ABSTRACT We build an agent-based evacuation simulation model to measure the roles and effects of station staffs when passengers face emergency situations in an underground station. For this purpose, first we take up an actual station as a simulation space and classify passengers into three patterns, emergency escape pattern, return back pattern, and follower pattern. Then we implement computer simulations with or without station guidance in case of exit damage or fire. Our computational results confirm that sheltering at the nearest exit is not always a suitable decision-making for passengers and that the guidance of station staffs decreases the number of victims in spite that the total evacuation time increases. KEYWORDS Agent-based simulation, Evacuation in emergency model, Guidance.

1. INTRODUCTION When an earthquake or terrorism occurs in a crowded but narrow area, extensive damage is generated. The possible reason is that there is a lack of emergency exits or that passengers do not know the structure where they are. However, an intensive evacuation drill costs and spends a lot. Therefore, it is necessary to grasp the behavior of people in emergency and to establish the way to evacuate safely. In order to analyze what happens in case of emergency, simulations with computers are usually used. Among these, an agent-based simulation (hereafter ABS) enables us to express behavior of heterogeneous agents and thereby to analyze overall evacuation conditions (e.g. Kiyono et al. (1998), Morishita and Nakatsuka (2001), Luo et al. (2008), and Ohi and Onogi (2008)); For instance, Kirchner and Schadshneider (2002), and Maury and Venel (2009) have independently simulated the behavior of people around building exits and recreated the build up that occurs when a great number of people rush to the exit. Okazaki and Matsushita (1993) have modeled the acts of evacuation in order to simulate the whole evacuation events. Hori et al. (2005) have shown the effects of path damage on evacuation in their simulation of a station building during an earthquake. Masuda et al. (2004) have considered the effects of smoke when simulating evacuation simulations in subway stations with fire. However, it seems that those earlier studies have only investigated problems incurred during evacuation. This paper hence simulates the states of a station in emergency and investigates how station staffs should work in the station precincts. Here we take into account exit damage, and fire and smoke by taking up an actual station in Japan.

1

Now at ITOCHU Techno-Solutions Corporation.

236

IADIS International Conference Intelligent Systems and Agents 2009

2. EVACUATION MODEL 2.1 Station The station consists of stairs, walls, entrances/exits, and boarding points and is defined as a set of cells with a square of side 0.6 meters (Figure 1). We assume that the stairs decrease walking speed of passengers by half. The walls are inflammable and are placed in open cells in case of path damage. Walkers may make it their destination when an open entrance/exit exists, and vice-versa. In emergency situations, fire/smoke moves from its present cell to neighboring open cells based on a given fire/smoke spreading probability. When a walker agent is in a cell with smoke, she goes to a wrong direction with a certain probability.

2.2 Walker Agents 2.2.1 Definitions A walker agent is represented as a circle with a radius of 0.3 meters with the following objects; standard walking speed V, View, MyDirection, and destination G; V [m/s] is the maximum walking speed if there are no obstacles around the agent, defined as V = 1.4 + 1.55exp(-2.17 / K) + eps where K stands for crowd density and eps follows the standard normal distribution 2 . View is the recognition range regarding the existence of obstacles around the agent. Agents recognize obstacles within a radius of View [m], defined as View = 1 + 0.25V, and 300-degree field of view in the direction of movement. MyDirection refers to her direction of movement taking a value 0 and 360 degrees. G shows the destination for an agent taking the angle of the current location and destination as the direction of movement.

2.2.2 Moving Rules Before moving, the walker agents should determine her destination and know the obstacles within her field of vision. Note that the obstacles in this study are the walls created in a disaster or other walkers. When a walker agent is in the station, she moves to her determination, an exit if she gets off the train or a ticketing gate if she gets on it. In this study, we assume that every walker agent knows the structure of the station and that she selects the shortest route or the one with the lowest cost by the Dijkstra method. In other words, the walker agents consider the station as a network. If an emergency situation occurs, she has to select a route to her determination according to her moving pattern which will be explained later. In this case there are two additional conditions postulated: The one is that the routes with fire or damage are impassable. The other is that the routes with smoke are passable but require a cost of five steps each when she is there. Next, she needs to recognize obstacles within her field of vision. Since MyDirection is her direction of movement, we set MyDirection as standard, 0 degree, and divide her field of vision into three sub-fields, front, left, and right. Within a radius of View [m] and 300-degree field of view in the direction of movement, obstacles inside a 60-degree field of view in the direction of movement are recognized when in front. A 120degree front field of view on both sides is recognized as left and right. A walker agent considers one obstacle with the smallest distance from her as corresponding one for each direction (Figure 2). Then she moves based on the following moving rules: First, she goes straight in MyDirection. When she faces an obstacle in front of her, then she moves where there is no obstacle. When there are obstacles both in front and to both sides, the agent does not move and stays at the present location. In emergency situations, the walker agents are classified into the following three patterns: “Return back pattern” walker agents go to their usual entrance/exit. “Follower pattern” ones move in the direction multiple walkers in their field of view are 2 The calibration method is as follows: First, we make a simulation rectangle of 18[m] in height and 12[m] in width and set the number of initial walker agents as 10. During this simulation, the number of walker agents increases by 10 every 100 steps until the population density reaches 2.0, and we calculate the average walk speed. After this simulation, we estimate the coefficients of the following five models from the simulation results: V = p / K (V is inversely related to population density, K.), V = p1 + (p2 / K – p3) ^ 0.5 (This model takes into account the intervals between a walker and others.), V = p1(K ^ p2) (V is exponentially related to K.), V = p1 log(p2 / K) (V is inversely related to log. of K.), and V = p1 + p2 exp(p3 / K) (V is exponentially related to negative value of log. of K.) where p, p1, p2, and p3 are coefficients. Finally, we employ the one with least mean absolute errors.

237

ISBN: 978-972-8924-87-4 © 2009 IADIS

moving. When there are no walkers to follow, they search for a close exit and move. “Emergency evacuation pattern” agents head toward the nearest open entrance/exit. Note that the “return back pattern” and “emergency evacuation pattern” agents try to find another evacuation exit when the original evacuation exit is found to be unusable.

Figure 1. Outline of the station

(The upper panel is the station precincts and the lower panel is the platform.)

2.2.3 Other Setups Moreover, we make the additional two assumptions: First, the walker agents in the vicinity stop for a set number of steps when crowd density exceeds five people per square meter. Second, when the exit damage happens, the walker agents who happen to be there are killed. Likewise, when they are at the cells with fire, they become victims.

2.3 Walker Guidance There is another kind of agent in this study, station staffs. They know what happens in the station and are expected to help passengers. Their roles in this study is 1) to guide to a certain exit, 2) to stop walkers evacuating from both the ascending and descending stairs every 30 seconds, then guide to the closest exit alternately, or 3) decide on the least dense ticket barrier and carry out dispersive guidance. The station staff agents stand inside the right-hand ticket gate and guide for guidance methods 1) and 3), whereas they do inside the left-hand ticket gate and guide with 2).

238

IADIS International Conference Intelligent Systems and Agents 2009

Figure 2. A walker agent’s field of vision and the corresponding obstacles for her

3. SIMULATIONS AND RESULTS 3.1 Initial Conditions We suppose that the disaster occurs during rush hours. Both the up-train and the down-train arrive simultaneously and 300 people get off each. 200 walkers are set as moving from the entrance/exit to the platform, and the evacuation simulation was run with a total of 800 people. The disaster is set to occur 100 seconds after the beginning of simulation. Other parameters are shown in Table 1.

3.2 Station without Guidance First, we implemented evacuation simulations in case of either exit damage or outbreak of fire five times, but no guidance for evacuation. Here we measured the total evacuation time and the number of victims.

3.2.1 Exit Damage Here, we implemented simulation with one of the three exits 1, 2, or 3 damaged. Table 2 presents the time until each evacuation finishes and the victims resulting from damage. Also, this table has evacuation time in case of no incident as a benchmark. The evacuation time when the exit 1 or 3 is damaged is longer than usual whereas that shortens only when the exit 2 is damaged. The former case is because the walker agents use the right-hand ticket gate and rush to one of the two usable exits, exit 2. Since the exit 2 is the nearest from the right-hand ticket gate, a crowd began gathering around this exit. As a result, the population density around exit 2 takes to some extent that it takes much time to finish evacuation. On the other hand, it takes shorter time to evacuate when exit 2 is damaged. In this case, a large number of walkers evacuate to the further exit, exit 3. This is because differences in the walking speeds of the walkers caused variations in the time taken to reach exit 3. In other words, no matter how many getting off passengers there may be, not all of them reach their destination at the same time in a longer walkway. Therefore, there is no build up, allowing for smooth evacuation. This leads to shorten evacuation time as a result.

3.2.2 Outbreak of Fire There are two patterns of fire occurrence, fire in the vicinity of exit 1 or exit 2. Fire spreading probability and smoke dispersion ratio were set as 0.02 and 0.2 respectively. The time until each evacuation finishes and the victims resulting from fire are shown in Table 3. In this table, if a fire occurs in the vicinity of exit 1, there is no great difference in evacuation time in comparison with the usual cases. However, the number of victims is 53.3 people on average. This is because the passengers from the left-hand ticket gate have to face fire and smoke because the gate is near the exit 1.

239

ISBN: 978-972-8924-87-4 © 2009 IADIS

Therefore, if the passengers are either return back pattern or follower pattern, then they are likely to move together to the undesirable exit and be killed afterwards. In contrast, when there is an outbreak of fire around exit 2, the passengers from the right-hand ticket gate safely rush to the open exit, 3. In short, as well as the previous simulation, it is not optimal to rush to the nearest exit in case of emergency. Table 1. Parameters Parameter Nos. original passengers (Return back pattern) (Follower pattern) (Emergency evacuation pattern) Passengers getting off each train per second Passengers from each exit per second

Value 800 (400) (240) (160) 0.1 0.7

Table 2. Evacuation time [seconds] and the number of victims [agents] in case of exit damage (without guidance) Damaged exit 1 2 3 Without incident

Emergency evacuation 208.56 190.40 205.75 202.00

Return back

Follower 214.06 189.90 205.85 208.10

221.38 191.80 215.50 218.70

Victims 26.0 14.0 18.0 --

The bold numbers mean the time for completion. Table 3. Evacuation time [seconds] and the number of victims [agents] in case of fire (without guidance) Exit with fire 1 2 Without incident

Emergency evacuation 207.44 190.30 202.00

Return back

Follower 217.00 189.90 218.70

214.06 187.10 208.10

Victims 26.0 5.0 --

The bold numbers mean the time for completion.

3.3 Station with Guidance Second, we implemented the simulations with guidance for evacuation. Likewise, we measured the total evacuation time and the number of victims and compared them to those in the previous section. Exit damage was set as in section 4.2.1 and fire is set to occur in the vicinity of exit 1. Tables 4 and 5 show the evacuation time and the number of victims in case of exit damage or fire respectively. Since the victims listed in Table 4 as well as Table 2 are all when the corresponding exit is damaged, it does not matter whether the numbers increased or decreased. Instead, appropriate guidance methods help the passengers, especially return back pattern, evacuate sooner, namely, this is because the flow of evacuees is stopped and started per staircase, limiting the amount of people evacuating from the ticket gate at one time, preventing from build up. It can be seen that guidance method 2) allows for smooth evacuation even when fire occurs and the width of passable paths are narrowed, leading to a reduction in victims. The same is said for the outrage of fire; The number of victims decreased much smaller because the station staffs lead the passengers originally going through the left ticket gate to the distance one, the right ticket gate for fear of fire and smoke. Thus, it took them longer to finish evacuation, but they safely escaped danger. Table 4. Evacuation time [seconds] and the number of victims [agents] in case of exit damage (with guidance) Damaged exit 1 2 3

240

Guidance 1 (exit 2) and 2 1 (exit 3) and 2 1 (exit 1) and 2 1 (exit 3) and 2 1 (exit 1) and 2 1 (exit 2) and 2

Emergency evacuation 200.50 196.63 190.90 197.75 187.45 197.40

Return back 199.70 195.69 188.23 197.63 181.85 197.00

Follower

Victims 201.65 195.81 186.57 195.88 187.65 195.70

24.4 26.0 15.9 16.0 19.8 14.6

IADIS International Conference Intelligent Systems and Agents 2009

The bold numbers mean the time for completion. Table 5. Evacuation time [seconds] and the number of victims [agents] in case of fire (with guidance) Exit with fire 1

Guidance 1 (exit 3) 1 (exit 3) and 2

Emergency evacuation 220.90 200.25

Return back 222.40 210.00

Follower

Victims 210.00 210.00

1.4 1.2

The bold numbers mean the time for completion.

4. CONCLUDING REMARKS This study investigates the roles and effects of station guidance on evacuation behavior of passengers in a station by agent-based simulation in case of exit damage, fire and smoke. For this purpose, firstly we take up an actual station in Japan and define exit damage and spreads of fire and smoke. Then, the detailed behaviors of passengers and the roles of station guidance are modeled. Thirdly, evacuation simulations with or without station staffs in case of exit damage or fire are run for comparative purposes. Our computational results confirm the following two points: First, sheltering at the nearest exit is not always a suitable decision-making for passengers. Second, the guidance of station staffs decreases the number of victims in spite that the total evacuation time increases.

REFERENCES Hori, M. et al., 2005. Study on Developing Simulation Method for Prediction of Evacuation Processes after Earthquake (in Japanese). In Sociotechnica, Vol. 3, pp. 138-148. Kirchner, A. and Schadschneider, A., 2002. Simulation of Evacuation Processes using a Bionics-inspired Cellular Automaton Model for Pedestrian Dynamics. http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0203461 . Kiyono, J. et al., 1998. Simulation of Evacuation Behavior in a Disaster by Distinck Element Method (in Japanese). In Journal of Structural Mechanics and Earthquake Engineering, Vol. 591, No. I-43, pp. 365-378. Luo, L. et al. 2008. Agent-based Human Behavior Modeling for Crowd Simulation. Computer Animation and Virtual Worlds, Vol. 19, No. 2, pp. 271-281. Masuda et al. 2004. Building an Evacuation Simulation Model in a Subway Station by Multi-agent Simulation (in Japanese). Japan Society for Safety Engineering Symposium, Tokyo, Japan, . Maury, B. and Venel, J., 2009. Handling of Contacts on Crowd Motion Simulations. In Traffic and Granular Flow '07. Springer, to appear. Morishita, S. and Nakatsuka, N., 2001. Simulation of Refuge in Emergency by Cellular Automata (in Japanese). Cellular Automata 2001, Yokohama, Japan, pp. 237-241. Ohi, F. and Onogi, M., 2008. A Simulation of Evacuation Dynamics of Pedestrians in Case of Emergency by a 2Dimensional Cellular Automation Method (in Japanese). In Transactions of the Operations Research Society of Japan, Vol. 51, pp. 94-111. Okazaki, S. and Matsushita, S., 1993. A Study of Simulation Model for Pedestrian Movement with Evacuation and Queuing. Proceeding of the International Conference on Engineering for Crowd Safety, London, United Kingdom, pp. 271-280.

241

ISBN: 978-972-8924-87-4 © 2009 IADIS

DOC-OPT A NEW METHOD FOR DISTRIBUTED CONSTRAINT SATISFACTION AND OPTIMIZATION PROBLEMS RESOLUTION Kais Ben Salah, Khaled Ghedira LI3

ABSTRACT In this paper, we present DOC-Opt, a new method based on Multi-Agent Systems (MAS), solving Distributed Constraint Satisfaction and Optimization Problems (DCSOP). DOC-Opt is based on three classes of agents, Decision-Maker agents, Advisor Agents and finally the Interface Agent. These agents will interact and cooperate in order to satisfy first, the inter and intra-agent constraints and to optimize the goal function. The MAS Architecture, dynamic and the experimentations are discussed. KEYWORDS DAI, SMA, DCSP and DCSOP.

1. INTRODUCTION A Distributed Constraint Satisfaction and Optimization Problem (DCSOP) can be defined as a Distributed Constraint Satisfaction Problem (DCSP) with one goal function in the case of centralized optimization, or several goal functions, in the case of distributed Optimization. In this paper, we deal with the first case, i.e., where the optimization process is centralized. As a matter of fact, the DCSP are defined as a number of Constraint Satisfaction Problems connected by external constraints or a CSP in which variables and constraints are distributed among multiple automated agents [14]. So, our first task is to find all the possible solutions in order to determine, as the second and final task, the global optimum. The agents have knowledge, behavior and they interact with each other to reach local and global objectives, they constitute the main research issue of the DCSP. Hence, the most efficient algorithms in the literature are based on the Multi-Agent Systems, like the asynchronous Backtracking, the asynchronous weak-commitment search [6] and the asynchronous aggregation search [16]. But in the case of DCSOP, there is no well known method, more over, when we deal with optimization in distributed environment, it’s always about constraint optimization (Distributed Constraint Optimization Problems) [3, 8, 15, 19]. So, we propose in this paper a new method for Distributed Constraint Satisfaction and Optimization Problems (DCSOP) resolutionA template is a set of styles and page layout settings that determine the appearance of a document

2. DOC DOC is our new meta-model that deals with Distributed Optimization under Constraint problems (see figure 1). More precisely we solve geographically or naturally distributed problems. In the case of Distributed Constraint Satisfaction Problems, many synchronous algorithms and asynchronous algorithms [2, 4, 6, 14, 15] have been proposed, but one of the most effective approaches in these cases is the Multi-Agent systems [1, 6, 14, 15]. DOC consists of 3 classes of agents, The Interface agent, the “Decision-Maker” agents and the “Advisor” agents.

242

IADIS International Conference Intelligent Systems and Agents 2009

3. THE VERSION DOC-OPT DOC-Opt is the version of DOC dealing with Distributed Constraint Satisfaction and Optimization Problems with the optimization process is centralized. As we explained in the previous section, in order to determine the optimal solution (in the case of complete methods), we have to explore all the solutions. So, the DecisionMakers and Advisors will cooperate in order to determine all the solutions (instantiations satisfying all the inter and intra-agent constraints) and communicate them to the Interface agent, that will start the optimization process.

3.1 Constraint Satisfaction Process We apply DOC-SAT [10, 11, 12, 13], the version of DOC limited to constraint satisfaction to solve the DCSP (to satisfy all the constraints). With regards to Multi-Agent systems, all the proposed algorithms are based on DCSP formalism: distributed consistency achieving [1, 2], and ABT-Like algorithms, namely, asynchronous backtracking algorithm, Weak-Commitment search algorithm [6, 14], and the Asynchronous aggregation search (AAS) [15] or Hybrid algorithms [17]. Let’s remark that DOC doesn’t rely on any centralized algorithm. Moreover, DOC can use any CSP technique which allows us the use of various algorithms at the level of the same system. In DOC-SAT, Decision-Maker and Advisors cooperate and interact by exchanging requests in order to satisfy intra-Decision-Makers constraints and inter-Decision-Makers constraints (see figure 3). Before giving more details about the structure and the behavior of the Decision-Maker and Advisor agents, we have to know that is very difficult, if not impossible, to ensure that an algorithm is complete and terminates in a distributed environment without establishing an order between the agents [5, 8]. The communication of the Decision-Maker with its Advisors is based on two sent messages and three received ones (see figure 4). A Decision-Maker can have, one of two states: satisfied or unsatisfied. It is satisfied in two cases. When its frontier and its interior are instantiated in a consistent manner. This means that there is a local solution and when it finishes browsing all the possible search directions. The first message received by a Decision-Maker is a request from one of its Advisors; comprising a search partial direction (partDir) to browse. This message is in the form: ((“ExploreDirection”, partDir), ADj, DMi). The second message comes also, from its Advisors: ((“NogoodPartialDirection”, partDir), ADj, DMi) and induces an update of the Explored Search Directions List: ExplDSet(DMi), i.e. the deletion of the search directions that involve a tuple or a combination of tuples that becomes “Nogood” (the term nogood means that this partial direction doesn’t lead to a consistent instantiation. The third message is an answer to the “InfoDecision” message. It has the following form: ((“AnswerInfoDecision”, partDir, Decision (OK/Not OK)), ADj, DMi). When the Decision-Maker has several Advisors, the list of non-requested Advisors ensures that the Decision-Maker (DMi) will visit all the possible search directions (which is necessary to find all the solutions). Hence, if the DMi can’t find a possible consistent instantiation (i.e. satisfying all the internal constraints), it sends to the first Advisors existing in his set of non requested Advisors (SetNonReqAD(DMi)) (having the highest level of priority), a message “ChangeDirection” and updates as usual, in this case, the SetNonReqAD(DMi). If the Decision-Maker (DMi) finds a local solution, it request all its Advisors about the values affected to variables of its frontier (variables involved in external constraints), if they are valid (consistent) at the global level and this via a message: ((“InfoDecision”), partDir), DMi, ADj). In the opposite cases (i.e. the Decision-Maker can’t find any local solution), after visiting all the existing directions, when the size of ExplDSet(DMi) becomes equal to ND(DMi), the Decision-Maker informs the Interface agent, about its state of satisfaction, and the absence of solution. This behavior will be repeated until the size of the ExplDSet(DMi) reaches the ND(DMi). An Advisor can receive two kinds of message from its Decision-Makers. The first one is a request to change the partial direction called “ChangeDirection” message. This message can also involve a partial direction qualified as nogood (can lead, in any case, to a local solution), so, it will be ranged in the nogood partial direction list. An Advisor is satisfied when it hasn’t received a request to change partial direction, or when all the partial directions received in the “InfoDecision” messages are consistent (satisfying all the external constraints supervised by the Advisor ADj). In this case, it sends a message to all its DecisionMakers, informing them about the consistency of their partial direction, via a message called “AnswerInfoDecision” with “OK” as parameter. In order to reduce the complexity, we present two ideas. The first one is the “CTNT” program (Create and

243

ISBN: 978-972-8924-87-4 © 2009 IADIS

Test New Tuples) and the second one is a new parameter called “PotentialSet” added to the “ChangeDirection” message. The “CTNT” program is an efficient heuristic to accelerate the search of the solutions at the local level of Decision-Maker. This program will be applied after the reception of each new “ExploreDirection” message and this when the size of the ExplDSet(DMi) exceeds two. This program uses the ExplDSet and the “ExploreDirection” message (particularly the PartDir), to create new instantiations (tuples) and tests if they satisfy all the local constraints. In the positive case, that means the presence of new solutions. In the other case, that means that the program has explored new directions. Hence, the acceleration of search is reached. The sub-program Change, will create new directions (using the history of the search, i.e. the explored directions set and the new partial directions), replacing the newly received partial direction (PartDir), in its position (p), in the first (size (ExplDSet (DMi))-2) directions belonging to the explored Directions set. The “potentialSet” is a new parameter added by the Decision-Maker to the “ExploreDirection” message and sent to one of its Advisors. This “PotentialSet” can be a singleton or a set and that depends on the nature of the “frontier” of each Decision-Maker. This set is formed in a way that if the partial direction (PartDir) sent by the Advisor, belongs to this set, the “interior” of the Decision-Maker (DMi) can be instantiated in a consistent way (i.e. at least one local solution will be found). Thus, the “PotentialSet” presents two advantages. The Advisors will send to their Decision-Maker agents, partial directions easily extensible to local solutions and the absence of solutions is quickly detected (when the Advisor doesn’t have partial directions that belong to this set).

CPU Time (S)

Comparison (20 variables) 4000

DOC-SAT

3000

DOC-SAT + PotentialSet

2000 1000

DOC-SAT + CTNT

0 0,3

0,4

0,5

0,6

0,7

0,8

Tightness

Asynchronous Backtracking

Figure 1. General comparison (problems with 20 variables) Comparison (24 Variables)

CPU Time (S)

5000

DOC-SAT

4000 3000

DOC-SAT + PotentialSet

2000 1000

DOC-SAT + CTNT

0 0,3

0,4

0,5

0,6

0,7

0,8

Tightness

Asynchronous Backtracking

Figure 2. General comparison (problems with 24 variables)

CPU Time (S)

Comparison (28 Variables) 7000 6000 5000 4000 3000 2000 1000 0

DOC-SAT DOC-SAT + PotentialSet DOC-SAT + CTNT Asynchronous Backtracking

0,3

0,4

0,5

0,6

0,7

0,8

Tightness

Figure 3. General comparison (problems with 28 variables)

244

IADIS International Conference Intelligent Systems and Agents 2009

As it shown in the figures 1, 2 and 3, the Asynchronous Backtracking is more efficient in the lower levels of tightness and when the size of the problems is smaller (contrarily to the cases of large problems and high levels of tightness). That can be explained by the fact that the Asynchronous Backtracking is simpler, each agent is responsible of one and only one variable and it uses only two messages to communicate (“OK?” message to communicate its value and “Nogood” message to communicate a new constraint) [6, 14, 15]. But, with the application of two new heuristics, our method becomes more efficient in almost all the levels.

3.2 The Optimization After the Constraint Satisfaction Process, each Decision maker will communicate the local values correspondent to the global solutions detected by the Interface agent. When all the values are received, the interface agent will execute a linear program that will detect the optimal solution, or the solutions that share the best (optimal value). We choose to generate a goal function by choosing randomly two variables from each Decision-Maker. Moreover, we tried two possible cases, a goal function without weights and a goal function with a weight for each variable, going from 1 to 9. We represent in the table below the list of the median values of the number of solutions, obtained by experimentation: Table 1. Median Values Of The Number Of Solutions tightness 20 variables problems 0,3 6 0,4 5 0,5 4 0 ,6 2 0,7 1 0,8 0

24 variables problems 4 4 3 2 2 0

28 variables problems 4 5 3 3 1 0

4. CONCLUSION In this paper we presented our new method DOC-Opt that deals with Distributed Constraint Satisfaction and Optimization Problems (DCSOP). In fact, our method can deal also with DCSP using DOC-SAT. The communication between our agents doesn’t only rely on values exchanging. And we believe that improve significantly the quality of our model. In fact, many papers studied the impact of agent’s communications on the performance of distributed algorithms. Fernandez et al. investigated the effect of communication delays on the performance of DCSP algorithms [7]. Another very interesting paper [4] has proved that DCSP strategies with additional information-exchange can lead to big speedups. Moreover, our method can be easily improved by Heuristics. We presented new heuristics that we presented have optimized significantly the search of the solutions in our distributed environment Finally, our model is the first one that can deal with DCSP and DCSOP without changing its Multi-agent architecture or Dynamic.

REFERENCES [1] Ahlem Ben Hassine and Khaled Ghédira 2002, “How to establish Arc- Consistency by reactive Agents”, ECAI 2002, Lyon. [2] B.Burg, “Parallel Forward Checking”, 1990,TR-594, Institute for New Generation Computer Technology, Japan, 1990. [3] E. Bowring, M. Tambe and Makoto Yokoo, 2006, “MultiplyConstrained Distributed Constraint Optimization”, AAMAS 2006, Autonomous Agents and Multi-Agent Systems, Hakodate Japan, May 8-12.

245

ISBN: 978-972-8924-87-4 © 2009 IADIS

[4] Fernandez, C., Bejar, R., Krishnamachari, B., Gomes, C., Selman, B., 2003, “Communication and computation in distributed csp algorithms”. In Lesser, V., Ortiz, C., Tambe, M., eds.: Distributed Sensor Networks. Kluwer Academic Publishers (2003) [5] Glover F. , 1990 “Tabu search”, ORSA Journal on computing 2, 4-32. [6] Hirayama Katsutoshi et Makoto Yokoo 2000, « An Approach to Over-Constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction”, ICMAS 2000. [7] Hyuckchul Jung and Milind Tambe 2005, “On Communication in Solving Distributed Constraint Satisfaction Problems”, CEEMAS O5, 15-17 September 2005, Budapest, Hungary. [8] Jonathan P. Pearce and Milind Tambe, 2007, “Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems”, IJCAI, Twentieth International Joint Conference on Artificial Intelligence, january 6-12 2007, Hydrabad, India. [9] Ionel Muscalagiu, Jose M.Vidal, Vladimir Cretu, Popa Horia Emil and Manuela Panoiu, 2007; “The effects of Agent Synchronization in Asynchronous Search Algorithms”, KES-AMSTA 2007, Wroclaw, Poland, May 31 – June 1, 2007. [10] KAIS Ben Salah and KHALED Ghédira, 2002. « Foundations of DOC-SAT ». AAMAS, Autonomous Agents & MultiAgent Systems 2002. Workshop 12: Distributed Constraint reasoning. [11] KAIS BEN SALAH and KHALED Ghédira 2008. “An efficient method for Distributed Constraint Satisfaction Problems resolution”. EUROSIS-ISC : ( The European Multidisciplinary Society for Modelling and Simulation Technology- Industrial Simulation Conference). Lyon, France, 2008. [12] KAIS BEN SALAH and KHALED Ghédira 2008. “DOC: A new Multi- Agent Approach for DCSP resolution”. NOTERE 2008. Lyon, France, 2008. [13] KAIS BEN SALAH and KHALED Ghédira 2008. “Using heuristics to optimize the research in a distributed environment”. EUMAS 2008, Bath, UK, 18-19 December 2008. [14] Makoto yokoo and Katsutoshi hirayama, “Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems” Second International Conference on Multi-agent Systems 1996. [15] Marius C. Silaghi , Makoto Yokoo, 2006, “Nogood based asynchronous distributed optimization (ADOPT ng)”, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (AAMAS), May 08-12, 2006, Hakodate, Japan. [16] M.C.Sialagui, D. Sam-Haroud and B. Faltings, 2000, « Asysnchronous Search with Agregation ».Proceedings of AAAI 2000, pp.917-922, Austin, August 2000. [17] P.G.Hendry and G.Y.Luo, 1992, “A Hybrid Algorithm for Distributed Constraint Saisfaction Problems”, parallel computing : From theory to practice, IOS Press 1992. [18] Ruben Fuentes Fernandez, Jorge J. Gomez-Sanz and Juan Pavon 2007, “Model integration in agent-oriented development”. International Journal of Agent-Oriented Software Engineering, volume 1, No. 1, 2007. Publisher’s website: www.inderscience.com. [19] Sycara Katia and Anton Chechetka 2006, “NoCommitment Branch and Bound Search for Distributed Constraint Optimization”, (AAMAS), May 08-12, 2006, Hakodate, Japan.

246

IADIS International Conference Intelligent Systems and Agents 2009

AN HYBRID APPROACH FOR FAULT RESISTANCE IN MULTI-AGENT SYSTEMS Mounira Bouzahzah, Ramdane Maamri. Lire Laboratory, Mentouri University, Constantine, Algeria.

ABSTRACT In this paper, we introduce an original hybrid approach for fault resistance in dynamic multi-agent systems. This approach is based on two concepts which are: replication and teamwork. Through this work we propose to evaluate the agent criticality using two different levels: the local level where the agent criticality is calculated according to its local plan of actions and the external level that concerns the different relations between the concerned agent and the other agents. The criticality evaluation makes it possible to divide the agents of the system into two main groups. The critical group uses the active replication, and the non critical group uses the passive replication. Three other gents are added to the system in order to guarantee the approach efficiency. KEYWORDS Agent local criticality, agent external criticality, hybrid approach, action initial criticality, action dynamic criticality.

1. INTRODUCTION Several researches are addressed to solve the problem of fault tolerance in multi-agent systems using different strategies. The most important ones are based on the concept of replication. There are different strategies to apply replication, the static strategy which decides and applies replication at design time like in [Kum00], [Hag96] and [Fed02]. The dynamic strategy applies replication during the processing time. It introduces the notion of agent criticality and used by various works such as [Gue04] and [Alm05]. According to the relation between the agent and its replicas there are two different types of replication. The passive replication that is defined as the existence of one active replica that processes all input messages and transmits periodically its current state to the other replica in order to maintain coherence and to constitute a recovery point in case of failure [Wei00]. The active replication is defined as the existence of several replicas that process concurrently all input messages [Mar02]. This article introduces an approach for fault resistance in dynamic multi-agent systems. Our approach is based on the criticality calculation using agent's plan to determine the agent local criticality. The interdependence relations are used to calculate the agent external criticality. According to their criticalities agents will be affected to two different groups: the critical group managed by an agent called the supervisor, this group uses the active replication strategy. The other group uses the passive replication strategy and it is managed by an agent called the controller. The rest of this paper is organized as follows: section2 covers the related works in the field of fault tolerance. Section3 gives a description to the proposed approach based on dynamic replication. Section4 describes the different parts that constituted our system, and finally, Section5 that gives an insight into our future directions and concludes the paper.

2. THE HYBRID APPROACH We propose an approach to introduce fault tolerance in dynamic multi-agent systems by the use of two main concepts which are: replication and teamwork.

247

ISBN: 978-972-8924-87-4 © 2009 IADIS

3. THE AGENT CRITICALITY The agent criticality evaluation in our approach is realized at two main levels: • The local level: That concerns the agent’s plan of actions. • The external level: Concerns the agent relations within the other agents. The agent criticality denoted Cagent is considered is calculated by the agent directly using the relation: Cagent = CL qgent + Cex qgent

3.1 Agent Local Criticality According to the model proposed in [Sic94]. An agent is composed of the following elements: • Goals: the goals an agent wants to achieve. • Actions: the actions the agent is able to perform. • Resources: the resources an agent has control on. • Plans: the sequence of actions that the agent has to execute in order to achieve a certain goal.

3.1.1 Agent Plan This work uses an agent's plan inspired from that proposed by [Alm06]. The agent plan is represented by a graph where the nodes represent actions and edges represent relations between actions. A node n which is connected to k other nodes (n1, n2... nk) using AND edges represents an action that will be achieved only if all its following actions are executed. However, a node n connected to its k followers using OR edges represents an action that is achieved if only one following action is executed. The work proposed in [Alm05] uses a different description concerning the agent plan and it proposes the existence of internal and external actions. Thus, according to our description an agent X will be represented as follows (Figure 1). Agent X A AND AND B1 OR C1

AND

B2

C2

Bk OR Ck

Figure 1. Agent X plan.

3.1.2 Action Initial Criticality We admit that a critical agent is the one which executes critical actions. And we propose the following criteria to define the initial criticality of an action: • An action which can be done by several agents can be regarded as being not too critical, but if an other action is done by few agents it will be regarded as a critical one. • The number of necessary resources that are required for the execution of an action can be also a factor to determine the initial criticality of an action. • According to the application field, the designer can define various semantic informations that can determine the initial criticality. Thus, at the design time each action has a value called the initial criticality denoted CI.

248

IADIS International Conference Intelligent Systems and Agents 2009

3.1.3 Action Dynamic Criticality The dynamic criticality of an action denoted CD is defined as the value affected to an action according to its position in the agent plan. There is one factor that can influence the action criticality which is the set of its following actions. We use the function MULTIPLICATION to represent the following actions influence on the considered action when they are connected using AND edges. The criticality of the action A denoted CA is calculated as follows: CA = initial criticality + dynamic criticality CA= CIA + CDA CA = CIA + (CB1 * CB2 *...* CBK) One other function MAX is used to represent the case where one action is connected to its followers by OR edges. Thus, B2 criticality is calculated as follows: CB2 = CIB2 + MAX (CC1, CC2 ,...,CCn) An action which has no follower is called a terminal action. The dynamic criticality of a terminal action equals to 0.

3.1.4 Agent Local Criticality Calculation In order to determine the agent local criticality, we admit that each agent knows at an instant t the actions sequence which it has to execute to achieve its current goal. The local criticality of agent CL agent is calculated as follows: CL agent = Sum ( Caction1 +....+ Caction n).

3.2 Agent External Criticality Each agent’s plan is formed of a sequence of actions that the agent has to execute in order to achieve its goal. These actions do not necessarily belong to the agent set of actions; therefore, an agent may depend on other agents in order to carry on a certain plans. We are interested to two main dependence relations: • The cooperative relation when an agent infers that he and other agents are depending on each other to realize the same current goal. • The adoptive relation the situation when an agent infers that he and other agents are depending on each other to realize the different current goal. The relation between agents is defined in our model using the following set: Set = {T, P, N} T: represents the relation type, it can be cooperative or adoptive. P: is the relation weight, here it represents the sum of the initial criticalities of the actions that are executed using this relation: P = Sum Ci of the actions executed using the relation N: the number that represent the agents having the same current goal. The external criticality in this case is calculated as follows: Cex agent = p/N In adoptive case N = 1.

3.3 Determine the Most Critical Agents Each agent must pass the calculated criticality at the instant t to an agent called the decision agent. This later determines the most critical agents following this algorithm. Algorithm: decision Begin Sumcriticalities 0 For each agent I do Read Cagent i /* Cagent i the criticality of the agent I*/ /* the sum of agents criticalities calculation*/ Sumcriticalities Sumcriticalities + Cagent i

249

ISBN: 978-972-8924-87-4 © 2009 IADIS

For each agent I do If (Cagent i >= Sumcriticalities / number of the agents) Then GT =1 Else GT=2 /* GT is an agent property, if GT=1 then the agent is affected to the critical group, else it is in the other group*/ End.

3.4 Criticality Re-Evaluation The criticality calculated must be updated throughout the execution according to two strategies: • Time strategy: the decision agent has a clock that gives alarms to re-evaluate agents' criticalities at each fixed time interval ∆t. • Event strategy: There are many events that act on the system and caused criticality revision such as: an agent failure, a machine failure.

4. THE SYSTEM DESCRIPTION The system consists of the dynamic multi-agent system and the three added agents:

4.1 The Decision Agent This agent offers two fundamental services. First it determines critical agents the fact that allows the division of the whole system into two main groups. And it initializes the agents to the process of criticality reevaluation following the dynamicity of the system.

4.2 The Supervisor Is the critical group manager, It allows the active replication. Each critical agent will have only one active replica called the follower. This latter is an agent that has the same plan and executes the same actions processed by the critical agent but after the reception of a permission message sent from the supervisor. This agent allows, also, failure detection, and the system can check if an agent is still alive and that it does not function in a synchronous environment [Fis85]. The supervisor achieves this service within the use of a clock that initialized the control messages sent to the critical agents. Each activated (critical replica) has a timer called failure – timer which gives the max time used by the agent to answer. If the agent does not give an answer a failure is detected.

4.3 The Controller Is the non critical agent group's manager it allows agent replication using the passive strategy. Each non critical agent will have only one passive replica. The non critical agent executes all actions and transmits its current state to its replica. If the active agent is lost its replica is activated. The controller verifies and detects failure among its group's agents using the same technique employed by the supervisor. The criticality revision is done by the decision agent according to two factors: time-driven factor and event-driven factor .When an agent is considered as critical at a given time t. It establishes a contract with the supervisor agent. So, the agent will have an active replica. If at the instant t + ∆t, the re-evaluation of the criticality considered the same agent as no critical its contract will be deleted. And one other contract will be established within the controller.

250

IADIS International Conference Intelligent Systems and Agents 2009

5. CONCLUSION This article proposes a rich approach for fault resistance in dynamic multi-agent systems based on replication and teamwork. We use the two strategies (active and passive) within the existence of one strong replica at one time; this fact allows the decreasing of charges. In order to guarantee failure detection and system controlling three other agents are added. In further work, we are interesting to validate our approach trough implementation.

REFERENCES [Alm05]Almeida, A., Aknine, S., et al, 2005. Méthode de réplication basée sur les plans pour la tolérance aux pannes des systèmes multi-agents. JFSMA. [Alm06] Almeida, A., et al, 2006. Plan-Based Replication for Fault Tolerant Multi-Agent Systems. IEEE. [Fed02] Fedoruk, A., Deters, R., 2002. Improving fault – tolerance by replicating agents. Proceedings AAMAS-02, Bologna, Italy, P. 144-148. [Fis85] Fischer, M., Lynch, N., Patterson, M.,1985. Impossibility of distributed consensus with one Faulty process. JACM. [Gue04] Guessoum, Z., Briot, J-P., et al, 2004. Un mécanisme de réplication adaptative pour des SMA tolérants aux pannes. JFSMA. [Hag96] Hagg, S., 1996. A sentinel Approach to Fault Handling in Multi-Agent Systems. Proceedings of the second Australian Workshop on Distributed AI. Cairns, Australia. [Kum00] Kumar, S., Cohen, P. R., Levesque, H.J., 2000. The adaptive agent architecture : achieving fault-tolerance using persistent broker teams. The Fourth International Conference on Multi-Agent Systems (ICMAS 2000), Boston, MA, USA. [Mar02] Marin, O., .Tolérance aux Fautes. Laboratoire d'Informatique de Paris6, Université PIERRE & MARIE CURIE. [Sic94] Sichman, J-S., Conte, R., et al, 1994.A Social Reasoning Mechanism Based On Dependence Network. 11th European Conference On Artificial Intelligence, ECAI 94. [Wie00] Wiesmann, M., Pedone F., et al, 2000. Database replication techniques: a three parameter classification. Proceedings of 19th IEEE Symposium on Reliable Distributed Systems (SRDS2000), Nüenberg Germany, IEEE Computer Society.

251

Posters

IADIS International Conference Intelligent Systems and Agents 2009

CONTEXT MANAGEMENT AND USER PREFERENCE LEARNING IN SMART HOME ENVIRONMENTS Víctor M. Peláez Martínez, Luis Ángel San Martín Rodríguez Roberto González Rodríguez, Vanesa Lobato Rubio Fundación CTIC – R&D department Parque Científico Tecnológico de Gijón, Edificio Centros Tecnológicos s/n, 33203, Gijón, Asturias, Spain.

ABSTRACT Ubiquitous computing concept was introduced by Weiser in 1991. Since then, advances have been made in computational development from traditional PC to wearable computing and embedded computation. Context-aware environments will become truly proactive and will allow the user to concentrate on tasks and activities with no concern for the computing resources and tools needed to perform them. This work presents an architecture, currently in development, to manage the context information and user preferences based on ontologies, component oriented architectures and machine learning techniques. The architecture will allow the development of context-aware applications for the home environment that will adjust it proactively depending on the user preferences. This kind of application will contribute to the development of ambient assisted living and therefore to the improvement of quality of life. KEYWORDS Ambient intelligence, context awareness, environmental user preferences, machine learning

1. INTRODUCTION Advances in electronic devices and communication networks are providing the hardware infrastructure necessary to achieve ubiquitous computing paradigm (Weiser 1991). This paradigm will result in new services, wearable computers and ubiquitous environments that will use natural user interfaces and context awareness (Dey 2001), providing intelligent behaviour aligned to user preferences. Intelligence is understood as adaptability and autonomy. Nowadays, research is focusing on smart homes and home environments (Meyer & Rakotonirainy 2003) (Magerkurth 2006) (Cook & Das 2007), and the use of artificial intelligence techniques to achieve the properties of context awareness, adaptability and autonomy (Cook & Das 2007). In an intelligent, context-aware, user-centered environment it is necessary to identify and extract data related to user preferences from global contextual information. In the state of the art, some approaches try to solve this point using static rules (Magerkurth et al. 2006), and others propose the use of machine learning for modelling user behaviour (Youngblood 2005) or user preferences (Hagras et al. 2004) (Ngoc et al. 2005). In the first case it is not possible to configure or adapt the system automatically depending on the user requirements and the current context. Works based on the second approach are not usually independent of the applications or dynamic regarding the number and type of the information sources used in the learning process. In order to overcome these drawbacks, this work proposes a system capable of modelling contextual information not only independently of the underlying physical infrastructure, but also taking into account different degrees of abstraction. The integration of machine learning systems as autonomous mechanisms to infer the environmental user preferences is also considered in the proposed architecture. These preferences will be combined with the rest of the contextual information in order to simplify the design and creation of context-aware applications that can, if the user wants, provide proactive actions aligned with his or her environmental preferences.

255

ISBN: 978-972-8924-87-4 © 2009 IADIS

2. USE CASES The main use case to be achieved with this work is a proactive environment where the user does not need to set any configuration parameters for the environment, since the system learns his or her preferences and applies them autonomously. In contrast to the approach presented here, most of the current domotic systems are based on predefined behaviour and scenes that can not be adapted automatically to the user. For example, instead of turning on the lights automatically when a person enters in a room, it is proposed that the system should provide a light level according to the tastes of the person and the contextual information. The system aims to learn the aspects for which the user has manually set the desired value. Thus, the above example could be extended to other environmental conditions such as temperature or background music. In this way, the system will evolve autonomously and will learn the user-explicit interactions in order to act in advance, proactively, in the future.

3. CONTEXT MANAGEMENT ARCHITECTURE According to the layered architecture for the development of context-aware applications presented by (Baldauf et al. 2007), the framework proposed in this work is characterized as follows: • The context is defined as a set of entities, such as users, physical locations or automated elements, which have certain attributes and are linked (e.g. a user is located in a room). • The model of the context information uses an OWL ontology based on that presented by (Magerkurth 2006). This ontology models all the common entities in a home environment, users, devices, furniture, etc., and their properties and relationships. Ontologies are a suitable approach in this kind of system because they improve inter-operability, have a great degree of formalism and allow reuse of existing knowledge (Strang & Linnhoff-Popien 2004). • The central element of the proposed architecture is the context server, a central repository of all the context information received from the different context sources (see Figure 1). An RDF database will be used to implement the context server. Context sources are software abstractions of any element capable of producing relevant information, for example sensors. In addition, any element capable of receiving commands, for example actuators, will be represented not only as a context source but also as a service. We define context processor as an entity that produces new context information (e.g. obtained from an inference or reasoning process), taking previous context information into account. In this way, a preference learning system is interpreted as a context processor. Finally, context-aware applications can consult the information available through the SPARQL query language or be subscribed to receive events concerning changes in the context. The information managed by the context server is independent of the underlying physical architecture, because context sources produce an RDF fragment which represents the information acquired by the physical devices according to the ontology model. This information will always characterize the current state of the environment by combining the latest data coming from each context source. All entities in the architecture are producers or/and consumers of context data; they only interact with the context server interface, without being connected directly with other entities. This feature will facilitate the dynamism required in intelligent environments, making context sources, processors and context-aware applications dynamic in number and type.

256

IADIS International Conference Intelligent Systems and Agents 2009

Figure 1. Proposed general architecture

4. USER PREFERENCE LEARNING To infer user preferences we propose a system based on machine learning with two clear objectives: the construction of a database of examples to generate training sets without user intervention; and learning the user preferences depending on the context, or physical location, of the user. To build a valid set of examples, it is necessary to label each example properly. Each example will be considered as an n-tupla made up of a set of attributes such as time, user, activity and sensor values. This ntupla defines the context at any given moment. Each n-tupla will be labelled combining the class of the user preference and its value (e.g. Temperature-23). The n-tuplas to be stored will be acquired by monitoring the user non-intrusively. When a user sets a parameter through the interfaces available in the home (e.g. set light level to 75%), a new n-tupla is created and stored as relevant data, including not only the configured parameter, but also information about the environment at that moment. In order to learn the preferences of a group of users, the system will also store the state of other users who share the same location with the user who changed the preference. This is because environmental preferences are specific to the location. The stored data can be used by a supervised machine learning technique to infer user preferences. As there are two very different approaches, lazy and eager algorithms, it is necessary to study the advantages and drawbacks of each approach to solve the environmental user preferences learning problem. The proposed modular architecture make possible to use different learning algorithms. As starting point a lazy approach algorithm has been considered (the K-nearest neighbours algorithm KNN, based on WEKA implementation, http://www.cs.waikato.ac.nz/~ml/). Lazy learning algorithms reduce the stored data used, so an improvement in learning accuracy is expected. This feature is implemented using heuristic knowledge characterized by current context conditions: user activity, user location and information about others users located in the same place. In this way, only data relevant to the current context is recovered from the data base and used as a training set. Training sets are built dynamically. All the stored information is clustered by the preferences that should be learnt, and each cluster, or group, will be used as training set in order to obtain the user preferences in a specific context state. When the user activity changes, the preference learning mechanism is triggered, and the current context is labelled once for each preference to be learned. When the user activity changes, preferences are inferred and stored in the context server with the rest of the information available for all the applications. In this way, every time that the context information changes the preferences will be updated. With this approach it is not necessary to model user preferences as a set of rules with restrictions concerning the situation in which they are applied, because only preferences for the current situation are available. The contextual data used in the learning process may change over time, thus, new contextual information not initially present forms part of the stored data. The data structures are modified dynamically in order to store this new information and use it in the learning process.

257

ISBN: 978-972-8924-87-4 © 2009 IADIS

5. FINAL REMARKS The architecture presented is intended to serve as the basis for the development of context-sensitive applications in the home environment. Its main advantages are: • independence of the underlying physical infrastructure, due to a data-centric approach based on a central information repository. • possibility of having different levels of abstraction to the same information, allowed by the ontology modelling approach. • dynamic coupling of new context sources, elements of information processing and applications (the components in the system are not directly linked). In the proposed approach a user preference learning system is defined as a context processor. It is able to work with individual user preferences and user group preferences, and it allows the dynamic inclusion of new types of contextual information in the learning process (dynamic training sets). It is also possible to use various learning algorithms and evaluate them depending on each situation. The learned preferences will be used in context-aware applications built on top of the infrastructure provided, in order to provide automatic environmental adaptation to users’ preferences, thus improving their quality of life. When the implementation is completed, tests will be carried out to determine the accuracy, performance and robustness of the approach. This learning approach is expected to have some limitations. As the learning process is driven by the current user activity, accuracy will depend on the quality of the user activity recognition. Future work also includes evaluating whether isolating learning preferences is appropriated in those services for which the different options and parameters have some inter-dependency. In addition, work will be done to prevent the bottleneck produced by the central element used as a context repository and to address privacy and security issues.

ACKNOWLEDGEMENTS To the companies involved in the CETICA project, especially to ArcelorMittal, Satec and Getlab for their support. The project CETICA is a Spanish R&D initiative funded by CDTI.

REFERENCES Baldauf, M. et al., 2007, A survey on context-aware systems. International Journal of Ad Hoc and Ubiquitous Computing.Vol. 2, No. 4, pp. 263-277. Cook, D.J. and Das, S.K., 2007, How smart are our environments? An updated look at the state of the art. Pervasive and Mobile Computing, Vol. 3, No. 3, pp. 53-73. Dey, A.K., et al., 2001, A Conceptual Framework and a Toolkit for Supporting the Rapid Prototyping of Context-Aware Applications. Human Computer Interaction, Vol. 16, No. 2-4, pp. 97-166. Hagras, H. et al., 2004, Creating an ambient-intelligence environment using embedded agents, Intelligent Systems, IEEE, Vol. 19, pp 12-20. Magerkurth, C., et al, 2006, An intelligent user service architecture for networked home environments. 2nd IET International Conference on Intelligent Environments. Athens, Greece. Meyer, S., Rakotonirainy, A., 2003, A survey of research on context-aware homes. Proceedings of the Australasian information security workshop conference on ACSW frontiers 2003-Volume 21, Darlinghurst, Australia, pp. 159-168 Ngoc, K.A.P., et al, 2005, OWL-Based User Preference and Behavior Routine Ontology for Ubiquitous System. Lecture notes in computer science, Vol. 3761, pp. 1615-1622. Strang, T. and Linnhoff-Popien, C., 2004, A context modeling survey. Workshop on Advanced Context Modelling, Reasoning and Management, The Sixth International Conference on Ubiquitous Computing. Nottingham, England. Weiser, M., 1991, The Computer for the 21st Century. Scientific American. Vol. 265, No. 3, pp 94-104. Youngblood, G.M., 2005, Automating inhabitant interactions in home and workplace environments through data-driven generation of hierarchical partially-observable Markov decision processes, University of Texas at Arlington, Arlington, TX, USA.

258

IADIS International Conference Intelligent Systems and Agents 2009

ROSES: AN EXPERT SYSTEM FOR DIAGNOSING SIX NEUROLOGIC DISEASES IN CHILDREN Sayed Yousef Monir Vaghefi Department of Computer Science, Sheikh Bahaee University.

Touran Mahmoudian Isfahani Department of Medicine, Isfahan University of Medical Sciences.

ABSTRACT In this paper we introduce a project that aims to design and develop an expert system, by the name “Roses”, which can diagnose six neurologic diseases in children. KEYWORDS Expert System, Neurologic Disease, Children.

1. INTRODUCTION Most parents don’t have enough information about neurologic diseases in children. It’s crucial to inform the parents if their child suffers from a neurologic disease. In a joint project between Isfahan University of Medical Sciences and Sheikh Bahaee University, we are trying to design and develop a system for diagnosing six neurologic diseases in children. The diseases are seizure, cerebral hypotonia, myopathy, tic paralysis, microcephaly, and macrocephaly. The system is a web-based expert system that diagnoses a neurologic disease in a child by questioning the parents. The project has been initiated in 2005 and the first version of the system has been developed in Java. This version has a client-server architecture and uses JESS (Java Expert System Shell) (Friedman-Hill 2003) and JEServlet technology at the server side and Macromedia Flash at the client side. We are now working on the second version of Roses.

2. PROBLMES TO SOLVE The first version of Roses has five major problems. The first problem is the system’s low reliability. The probability of a correct diagnosis is 65 percent. The second problem is the system’s high response time. The system is slow and cannot answer multiple clients. The third problem is that the system doesn’t inform the user about the severity of the disease. The fourth problem is the system’s poor modifiability. The system needs a graphical user interface (GUI) through which an expert can modify the knowledgebase. The fifth problem is the lack of learning ability. The system has no learning subsystem.

3. WORK IN PROGRESS Figure 1 shows a part of the decision tree which we have designed for the first version. We are trying to improve the probability of a correct diagnosis by updating our decision tree. We will carefully revise the questions and extend the options.

259

ISBN: 978-972-8924-87-4 © 2009 IADIS

One of the problems of the first version is that it supposes that the user inputs are precise despite the fact they can be inaccurate. We are planning to employ a Bayesian network (Russell 2002) in the design of the second version to deal with uncertainty and we hope to increase the probability of a correct diagnosis by 20 percent. The first version doesn’t report the result of the diagnosing process, which is the name of the disease, to the user. It just tells the user whether or not the child suffers from a neurologic disease. The second Figure 1. A part of the decision tree version will also follow the same policy, but it will inform the user about the severity of the disease. It will also advise the user to take the child to a hospital if it diagnoses an acute problem. The second version will offer a GUI, by System Architecture the name “Doctors GUI”, through which an Client Side Server Side expert -a pediatric neurologist- can open the knowledgebase and modify the rules. This Learning JEServlet End-user GUI GUI uses a login subsystem in order to Subsystem identify an expert user. Figure 2 shows the system architecture. Doctors GUI Knowledgebase JESS We are designing a learning subsystem for the second version. This subsystem creates a record for each user in a database. At the end   of each month, it examines the records and Figure 2. The system architecture generates a number of new rules for the knowledgebase. Each new rule will be inserted into the knowledgebase if the system’s administrator agrees to the insertion.

4. EXPECTED RESULTS We expect the second version of Roses to have low response time and high reliability. We hope to increase the probability of a correct diagnosis to 85 percent. The second version will offer a new GUI through which an expert can update the knowledgebase. It will also offer a learning subsystem.

REFERENCES Friedman-Hill, Ernest, 2003. Jess in Action: Java Rule Based Systems. Manning Publications Co, Connecticut, USA. Russell, Stuart. Norvig, Peter, 2002. Artificial Intelligence: A Modern Approach (2nd Edition). Prentice-Hall, Upper Saddle River, New Jersey, USA.

260

IADIS International Conference Intelligent Systems and Agents 2009

NEURAL NETWORKS AS IMPROVING TOOLS FOR AGENT BEHAVIOR Alketa Hyso, Eva Çipi Department of Computer Science and Electrical Engineering, University of Vlora, Albania

Betim Çiço Informatics Engineering Department, Polytechnic Universiyt, Tirana, Albania

ABSTRACT One of the most interesting issues in agent technology has always been the modeling and enhancement of agent behavior. In this paper we are focused on the intersection of agent technology and machine learning techniques for producing intelligent agents. Our application shows that using neural network techniques we improve the reasoning mechanism of our agent supplying to it a new behavior which it did not possess from the beginning. The learning process can be applied initially to train ‘dummy’ agent to further improve agent reasoning. The machine learning algorithms allow for an agent to adequately respond to environment changes and improve the behavioral rules or acquire intelligent behavior. A case study will be given to demonstrate such enhancement. KEYWORDS Intelligent agent, machine learning techniques, multilayer perceptron

1. INTRODUCTION Agent and multi-agent system technologies, methods and theories are currently contributing in many diverse domains. This is not only a very promising technology, it is emerging as a new way of thinking a conceptual paradigm for analyzing problems and for designing systems, for dealing with complexity, distribution and interactivity, and perhaps a new perspective on computing and intelligence[8]. Numerous approaches exist, attempting to optimally reflect both the inner states as well as perceived environment of an agent in order to provide it either with reactivity or proactivity [6]. Learning is a crucial ability of intelligent agents. Machine Learning tools and techniques enable an agent to get knowledge from observations or experiences. It can be contrasted to programming an agent - we do not have to provide all knowledge to an agent, which may be infeasible in case the programmer or designer has incomplete knowledge about an environment. Instead, by learning the necessary knowledge we provide the agent with an additional degree of autonomy - an agent's behavior is completely determined by its own experiences. The machine learning algorithms allow an agent to learn from its past history in a human similar way; by induction, we can choose to create agents with the ability to compute rules and strategies and evolve according to the environment in which they act [3]. We demonstrate the use of neural network techniques to extract models to generate predictions or new behaviors in agents.

2. MULTILAYER PERCEPTRON NEURAL NETWORK AS FUNCTION APPROXIMATION The field of neural networks covers a very broad area. We will concentrate on the most common neural network architecture – the multilayer perceptron (MLP); how it can be used for function approximation.

261

ISBN: 978-972-8924-87-4 © 2009 IADIS

Two-layer networks, with sigmoid transfer functions in the hidden layer and linear transfer functions in the output layer, are universal approximators. Hornik, Stinchcombe and White, [1] present a proof that multilayer perceptron networks are universal approximators. Pinkus, [2] gives a more recent review of the approximation capabilities of neural networks.

3. APPLICATION Our application aims to present the importance of the synergy of machine learning methods and agent technology, in building more intelligent agents. In order to exemplify this idea we consider a case study. We shall take into consideration an agent which is able to calculate time and to move. After getting the signal from a given sensor, the agent moves through a straight line without obstacles, departing from a position of “waiting”, to which corresponds a 0 moment of time. Its moving accelerate with a given acceleration that our agent is not able to calculate. We suppose that in equal distances our agent should leave a print. We should have the agent learn the process of calculating the road it does, only based on its capacity to calculate time. In order to solve the above mentioned problem, we use rows of data extracted during the movement of the agent. These rows include data about movement: time intervals, the speed of movement in that moment, acceleration and distance. Acceleration: 2 m/s2; Time in seconds (0; 1; 2; 3; 4; 5; 6; 7) and distance in meters (0; 1; 4; 9; 16; 25; 36; 49).

Figure 1. Architecture of neural network

On these data we apply machine learning method – multilayer perceptron neural network, to find a model, which in the following step we will incorporate to our agent. Our neural network has an input layer that sets the values of elements in the hidden layer with 3 nodes with sigmoidal activation function. They set values for the output layer element which is a linear unit, Figure 1. Among the learning algorithm the one that gives the best solution is the backpropagation algorithm (BP) of neural networks which is supported by Multilayer Perceptron method [7] [4] [5]. The final model shows clearly the weights. The knowledge model that we get is a non-linear function of the type: 1 d = − 20761 . 777221 ⋅ + − ( a ⋅3.983986 + t ⋅( -0.077077) + (-7.592238 )) 1 + exp + 335.640279

− 705.166631

1

⋅

1 + exp

+ t ⋅ 0.378405

1

+ (-1.142265

))

+

+ + t ⋅ 0.335880 + (-2.606184 )) 1 + exp + a ⋅ 4967.10318 2 + t ⋅ ( -363.81504 ) + 2483.55159 In a second phase we build an application which simulates the behavior of the agent where the reasoning mechanism is realized according to the final model obtained from the neural network. Now, our agent can measure the distance of movement based on the low which it discovered through the training process. Figure 2, presents the tracks that our agent leaves during his movement, based on completed distances every second. The upper tracks (1) are left by our agent based on the measurement according the knowledge it won from the training process (approximation function). They are based on the distance our agent calculates every

262

⋅

− ( a ⋅ 0.226480

− ( a ⋅ 0.912341

IADIS International Conference Intelligent Systems and Agents 2009

second. The tracks below are left based on the time – every second. We see that for the first 50 m that correspond 7 seconds, distance measured from the agent is equal with the distance it accomplishes. Further, we see that tracks do not fit together. This shows that the function of calculation the completed distance is valid only for the range of data included in the training process of the agent. This function is not valid for the uncovered data from the training process.

Figure 2. The tracks that agent leaves based on the calculated distance every second (1), and based on the time(2).

By the experiment we see that the agent displays a new behavior: it is able to realize an approximate calculation of distance; by developing an intelligent behavior of the agent.

4. CONCLUSION This paper aims to present how machine learning methods can be integrated with agent technology in building more intelligent agents. Using machine learning techniques makes it possible to develop agents able to learn from and adapt to their environment. In this way, the performance of these agent systems can be improved. We demonstrate the use of learning techniques to extract models to generate predictions or new behaviors. By using a neural network as a reasoning mechanism and by analyzing input and output, our agent will acquire a new intelligent behavior which it did not possess from the beginning. This paper is a brief summary of what we have done in the practice of combining agents and machine learning techniques. We will make more efforts to explore this new trend of research.

REFERENCES [1.] Hornik, K. et al 1989, ‘Multilayer feedforward networks are universal approximators,’ Neural Networks, vol. 2, no. 5, 359–366. [2.] Pinkus A., 1999, ‘Approximation theory of the MLP model in neural networks,’ Acta Numerica, 143–195 [3.] Remondino, M., et al, 2005, Data Mining Applied to Agent Based Simulation, Proceedings 19th European Conference on Modelling and Simulation Merkuryev Y, Zobel R, Kerckhoffs E, ECMS. [4.] Rumelhart, D. E., et al, 1986, ‘Learning representations by back-propagating errors,’ Nature, vol. 323, 533–536. [5.] Russell, S., et al, P., 1995, Artificial Intelligence A Modern Approach, Prentice Hall, 581. [6.] Symeonidis, A. et al , 2005, Methodology for Predicting Agent Behavior by the Use of Data Mining Techniques, International Workshop AIS-ADM 2005 Russia, Proceedings. [7.] Werbos, P. J., ‘Beyond regression: New tools for prediction and analysis in the behavioral sciences,’ Ph.D. Thesis, Harvard University, Cambridge, MA, 1974. Also published as The Roots of Backpropagation, John Wiley & Sons, New York, 1994. [8.] Zhang. et al, 2005, Agents and Data Mining: Mutual Enhancement by Integration, (Eds) Gorodetsky V, Liu J, Skormin V.A, Autonomous Intelligent Systems: Agents and Data Mining, 50-61, Springer.

263

ISBN: 978-972-8924-87-4 © 2009 IADIS

264

AUTHOR INDEX AL-Akhras, M. .................................................93 Alhashel, E. ...................................................219 Arriaga, I. ......................................................159 Ávila, I. ..........................................................167 Azizi, A. ..........................................................53 Balachandran, B. ...........................................219 Berlea, A. .........................................................19 Bittencourt, E. .......................................... 27, 209 Bouchard, B. ..................................................231 Bousfield, P. .......................................... 195, 209 Bouzahzah, M. ...............................................247 Bouzouane, A. ................................................231 Boyd, R...........................................................189 Burrell, P. .......................................................215 Caises, Y. ...................................................77, 85 Casey, D. .......................................................215 Chauvin, C......................................................100 Çiço, B............................................................261 Çipi, E. ...........................................................261 Darius, P. ........................................................108 Das, S. ...............................................................3 Devogele, T. ..................................................100 Dimou, C. ......................................................125 Döhring, M. .....................................................19 Drias, H. ........................................................133 Gallardo, M. ..................................................204 Ganske, C. ......................................................195 García, C. .......................................................204 Ghedira, K. .....................................................242 Giroux, S. .......................................................231 Gómez, J. .......................................................204 González, R. .................................................255 González, A. ..............................................77, 85 González, C. ..................................................159 Grundspenkis, J. .............................................116 Harada, Y. ......................................................149 Hassan, Y. ........................................................69 Hindi, K. ..........................................................93 Holanda, G. ....................................................167 Honkaranta, A. .................................................43 Hyso, A. .........................................................261 Isfahani, T.......................................................259 Jing, Y. ...........................................................189 Kambayashi, Y. .............................................149 Kanaga, E. .....................................................108

Kazemian, H. ................................................. 189 Landmann, R............................................ 27, 209 Lavendelis, E.................................................. 116 Leyva, E. .................................................... 77, 85 Li, J. ............................................................... 189 Liu, S. .............................................................. 43 Lobato, V. ..................................................... 255 Maamri, M. .................................................... 247 Mahmoud, M.................................................... 61 Mahuna, A........................................................ 35 Maña, A. ........................................................ 141 Martín, L. ....................................................... 255 Mateos, J. ...................................................... 159 Menacer, D. ................................................... 133 Mitkas, P. ....................................................... 125 Mohammadian, M. ........................................ 219 Molinero, F. ................................................... 204 Montenegro, M............................................... 141 Morcos, K. ........................................................ 3 Muñoz, A. ..................................................... 141 Oliveira, P. ...................................... 27, 195, 209 Ouazzane, K. ................................................. 189 Pang, C............................................................. 11 Peláez, V. ...................................................... 255 Pérez, R. ..................................................... 77, 85 Pors, T. - ........................................................ 100 Pourreza, H. ..................................................... 53 Reuschling, N................................................... 19 Rolim, L. ....................................................... 167 Roy, P. ........................................................... 231 Royakkers, L. ................................................. 177 Salah, K. ........................................................ 242 Satoh, K. ........................................................ 236 Schossland, S. .................................. 27, 195, 209 Seo, K............................................................... 11 Sharma, D. ..................................................... 219 Shiraki, Y. ...................................................... 200 Sibertin-Blanc, C............................................ 133 Svanberg, P. ................................................... 225 Symeonidis, A................................................ 125 Takahashi, T................................................... 236 Temprado, Y. ................................................. 204 Terano, T........................................................ 236 Torrens, E. ....................................... 27, 195, 209 Tzima, F. ....................................................... 125

Vaghefi, S. .....................................................259 Valarmathi, M. ..............................................108 Vallejo, D. .....................................................159 Verkerk, M. ....................................................177 Vincent, T. .......................................................35 Wahlstedt, A.....................................................43 Walicki, M. ....................................................225 Welch, S. ............................................................3 Wyrebski, J.......................................................27 Yamada, T. ....................................................236 Yoshikawa, A. ...............................................236 Zanottelli, C. ..................................................195