Design of Cooperative Agents for Mobile Devices Juan M. Corchado1, Emilio S. Corchado2 and M. A. Pellicer1 1Dep. Informática y Automática Universidad de Salamanca Plaza de la Merced s/n 37008, Salamanca, Spain corchado@usal.es http://gsii.usal.es/ 2Department of Civil Engineering, University of Burgos, Spain. C/ Francisco de Vitoria s/n 09006, Burgos, Spain Abstract. The paper presents an agent-based engineering system developed for mobile devices. The proposed system has been used for constructing a wireless tourist guide application that incorporates cooperative agents with the learning capabilities. It is shown how to construct cooperative agents with a goal driven design using a case-based reasoning methodology . The resulting architecture has been tested by real users during six months and the results obtained are here presented. 1 Introduction Agents for mobile devices have introduced an interesting an exciting new paradigm in the telecommunication industry. In the competitive telecommunication world multi- agent systems have been success the drive for new and sophisticated services is fundamental. The new challenges of this field require new technology that facilitates the construction of more cooperative, dynamic and flexible applications, capable of working in a real time environment. Agent-based solutions intend to cope with such requirements. The development of agent for wireless devices is characterized by very limited, variable and asymmetric technology and bandwidth, frequent and prolonged disconnections, geographical mobility, severe resource restrictions and complex data management issues. In addition to these familiar issues there is also the crucial element of dynamism. Agent technology has already been proposed as a possible solution to many of these problems. When the terms "cooperation" or "intelligent" is used it is clear the user means the software to be something more than a mere server, mobile or not. Often, the term is only a reference to a context of a community and technology. With respect to agents, the "intelligent" label in this case refers to a concern with abstract, domain-independent theories of agent architecture and communication and/or aspects of human characteristics. The terms cooperation and autonomy are essential in the development of distributed agent-based systems for wireless devices. The amount of information available to users via wireless systems is changing and increasing continuously. Existing applications need to be continuously updated. In this context the use of dynamic agents based systems may help to reduce the developed costs and to facilitate the use of this technology. We propose the use of cooperative agents that use case-based reasoning (CBR) systems [1, 3]. The proposed architecture combines reactive and deliberative agents. The architecture used by the second ones includes the use of Beliefs, Desires, and Intentions (BDI). Under this model, agents have a mental state that consists of informational, motivational, and deliberative states respectively. Beliefs represent the information about the environment, the internal state the agent may hold, and the actions it may perform. The agent will try to achieve a set of goals, and will respond to certain events [9, 11]. The deliberative agents are built on a case-based reasoning system [3,6]. The proposed method starts by identifying agent roles and goals , and the design and implementation of the agent architecture follows the form of CBR systems, which facilitates learning and adaptation, and therefore a greater degree of autonomy than with a pure BDI architecture. This is made by mapping the three mental attitudes of BDI agents into the information manipulated by a CBR system. This direct mapping between the agent conceptualisation and its implementation is the main difference with respect to other proposals that have also tried to combine BDI and CBR [2, 7, 8, 10]. A tourist guide service through mobile devices has been used to validate the system. The system has been validated by users who have used it when vis iting the city of Salamanca. The system is able to program a tourist route, and modify it according to the conditions of the places to visit and the available time for the tourist. The following section describes the agent based architecture. The conclusions are finally presented and the results evaluated. 2 Agent-based architecture A tourist guide application has been developed using a multiagent architecture. The agents assist potential tourists in the organization of their tourist routes and enable them to modify their schedules on the move using wireless communication systems. This system has been constructed using an engineering framework developed to design and implement an agent-based tool, as well as integrating existing state of the art in order to create an open, flexible, global anticipatory system with mobile access for the promotion and management of inland and cultural tourism, which will be user- friendly, cost-effective and secure. The integrated, multi-platform computer system is composed of a guide agent (Planner Agent) that assesses the tourists and helps them to identify tourist routes in a city with a given visiting period of time and under a number of restrictions related to cost, tourist interest, etc. There is one assistant agent for each user of the system, the Performer Agents. Each user willing to use the system has to register and solicit one of these agents. Finally, there is a third type of agent, the Tracker agent, which maintains updated information about the monuments, the restaurants, public transport conditions, etc. This agent maintains horizontally and vertically compiled information on hotel accommodation, restaurants, the commercial sector and transport, in order to meet the needs of the potential visitor on an individually customized basis, and responds to requests for information, reservations and purchases in the precise moment that they are expressed. The user may decide whether to install the corresponding Performer Agent on a mobile phone or PDA, or run it on the server and interact with it via its mobile device. The first choice supposes a reduction of the cost, since the tourist can interact with his agent as much as needed at no cost because it is installed in the wireless device. Nevertheless, the agent will have to contact regularly with the Planner Agent. Fig. 1. describes the system architecture from a very high abstraction level. Users may interact either with their performer agents installed in their wireless devices or in an internet server. Fig. 1. System architecture Agree Inform-Whenever (Changes on the environment) AgTracker AgPlanner:K-base Fig. 2. Sequence diagram for the Tracker agent and the planner agent The performer agents interact with the planner agent looking for plans, and the tracker agent interacts with the planner agent to exchange information. The planner agent is the only CBR-BDI agent in this architecture. The performer agents can be considered assistant agents and the tracker agent is a reactive agent. Figure 2 and 3 show the sequence diagram for the multiagent system. Tracker agent Internet Searches for Performer agent [us001] Internet User Interfaz Planner agent Internet Generates T. Performer agent [us002] Internet User Interfaz Performer agent [us001] Wireless net. User Interfaz Performer agent [us002] Wireless net. User Interfaz Performer agent [us00x] Wireless net. User Interfaz A g P e r f o r m e r / Q u e s t i o n e r A g P e r f o r m e r / E x e c u t e r A g P l a n n e r : V C B P A g P l a n n e r : K - b a s e Reques t (Ob jec t i ves , Resources ) <> Inform (Base of Posible Solutions) <> In fo rm (Mos t Rep lann ing-Ab le So lu t ion , n s teps) Que ry I f (S tep i == t r ue ) asser t (n s teps) < < r o l e c h a n g e > > re fuse [ t rue == Be l i eve ] Con f i rm [ f a l se == Be l i eve ] D i scon f i rm Request (Objectives - Sum(Objectives,i), Resources - Sum(Resources,i) <> Inform (Base of Posible Solutions) <> Inform (Most Replanning-Able Solution, m steps) Query I f (Se rend ip i t y i s Poss ib l e ) D iscon f i rm <> Inform (Base of Posible Solutions) <> x x x [ i : 1 . . n | | i : 1 . . m ] S t e p s * [ m o r e p l a n n s ] Fig. 3. Sequence diagram for the performer agents and the planner agent The planning agent incorporates a CBR system [1]. The relationship between CBR systems and BDI agents can be established implementing cases as beliefs, intentions and desires which led to the resolution of the problem. When the agent starts to solve a new problem, with the intention of achieving a goal, it begins a new CBR reasoning cycle, which will help to obtain the solution. The retrieval, reuse and revise stages of the CBR system facilitate the construction of the agent plan. The agent’s knowledge- base is the case-base of the CBR system that stores the cases of past believes, desires and intentions. The agents work in dynamic environments and their knowledge-base has to be adapted and updated continuously by the retain stage of the CBR system. Based on this relationship, agents can be implemented using CBR systems. This means, a mapping of agents into CBR systems. The advantage of this approach is that a problem can be easily conceptualised in terms of agents and then implemented in the form of a CBR system. So once the beliefs, desires and intentions of an agent are identified, they can be mapped into a CBR system. To set up an agent using the CBR-BDI agent architecture [3] we need to identify an initial set of beliefs, desires and intentions and include them in the case-base of the agent in the form of cases. Then, a number of metrics for the retrieval, reuse, revise and retain steps has to be defined. Besides, rules that describe the Expert’s knowledge must be established, if available. Once the agent has been initialised it starts the reasoning process and the four steps of the CBR system are run sequentially and continuously until its goal is achieved (or there is enough evidence for a failure situation). -<> -K-base -Update Believes/Intentions -<> -VCBP <> Planner -Input -Request ACL for service (Give MRS) -(ACL content = {O, R, hi, UsedBel} ) -O = Objetivos -R = Recursos -hi : int -UsedBel <> K-base -Description -Given a set of Preferences about a problem P -this service offers the Most Replanning-able Solution <> Give MRS Type Inform, Failure Protocol: Request-Best Solution for a dynamic environment Agent Comunication Language FIPA ACL Ontology Planning ontology Content Language FIPA SL -Input -{ S(p) } S1(p),S2(p),S3(p),..Sn(p) : Posible Solutions <> VCBP Output: Sf(p) : MRS (Most Replanning-able Solution) Description: This capability provides the most replanning-able solution to the performer Agent Output: S1(p),S2(p),S3(p),..Sn(p) : Posible Solutions Description: This capability provides solutions that fulfill a set of given preferences -Input -Inform ACL for Update Believes/Intentions -(ACL Content = -b1(t),b2(t),...bn(t) : Believe -t : time ) <> Update Believes/Intentions Output: bi(t-1) <- bi(t) : Believe I[bi(t-1) <- bi(t)] : Intentions Description: This capability Updates believes and intentions Fig. 4. Planner Agent class diagram Fig. 4 shows the AUML class diagram (www.auml.org) of the Planner Agent. In these types of diagrams, the roles and goals of the agents are represented as Capabilities that may change with the time. In particular, the roles of the Planner Agent are to update the believes and intentions, which are stored in the form of cases, to identify those believes and intentions that can be used to generate a plan n, and to provide adequate plans to the Performer Agent given a number of conditions. These roles allow the agent to generate the closest to the optimum plan, which in this case has also to be the most replan-able solution. In this context, when the Performer Agent asks for a tourist route, given a number of constraints such as the money the tourist is willing to spend, the number of monuments to visit, the type of restaurants to eat, the time availability for the holiday, etc. the Planner Agent generates a plan that fulfils such conditions. This plan is easy to modify at execution time if the user changes of mind. The Planner Agent is a CBR-BDI agent, where the first role is carried out during the Retain stage of the CBR life cycle, the second role is the Retrieval step, and the third role is the Reuse stage. -Input -Preferences = { O <- O', R <- R', hi, UsedBel} -O' = Objetivos Pendientes -R' = Recursos Disponibles -hi : Int -UsedBel = {b1, b2, b3..bk} : Believe <> Request for Replanning -<> -Wait Preferences -<> -Questioner,Executer -Request for Replanning <> Performer -Input True <> Wait Preferences Description: This Capability waits preferences {O = Objectives, R = Resources } to solve a Problem p -Input -Request : Preferences = { O, R, hi, UsedBel={} } for S(p) <> Questioner -Input -MRS : Most Replanning-able Solution {b1,b2,..bm} :Believe <> Executer Output: a) Query If Replanning (For All Believe E MRS , Believe == true) b) Query If Replanning (if Any Believe E MRS , Believe==false ) c) Failure Replanning Description: This capability executes the MRS solution and it checks proposed believes are true. Otherwise it is capable of replanning to get other solutions Output: Request ACL for service (Give MRS) to Ag Planner (ACL content = {O, R, hi, UsedBel} ) Description: This capability request for the best posible solution to Planner Agent in a dynamic environment Output: Request ACL for service (Give MRS) to Ag Planner (ACL content = {O’, R’, hi, UsedBel} ) Input Constraint: O' > 0 R’ > 0 Output: Wait Preferences : { O, R , hi , UsedBelieves= { } } for S(p) Description: If all objectives have not been achieved and there are available resources, this capability request for the service “Give MRS” to Planner Agent to finish the plan Fig. 5. Performer agent class diagram -<> -Search Changes -Store Changes <> Tracker -Input -b1(t),b2(t),.. .bn(t) : Believe -t : time <> Search Changes Output: { b i ( t ) } / b i ( t ) <> b i ( t -1) : Be l ieve Description: This capabi l i ty f inds the changed bel ieves on the environment -Input -{bi(t)} : Believe -t : time <> Store Changes Output: bí(t-1) <- bi(t) Description: This capabi l i ty stores new values for the changed believes -Descr ip t ion -This serv ice not i f ies changes on the -environment automatical ly <> Not i fy Changes Type Inform Protocol : Agent Comunication Language F I P A A C L Onto logy Planning ontology Content Language F I P A S L Fig. 6. Tracker agent class diagram The Performer agents are assistant agents. Each of them is associated to one user and contact the Planner Agent to request a plan. These agents may be in waiting mode, waiting for a request from the user, may ask to the Planner Agent for a plan, or request a modification in a plan (replanning) to the Planner Agent. Fig. 5 shows the AUML class diagram for the Performer agent. The Tracker Agent is always looking for changes in the visiting conditions of the different sites, and keeps a record of them. The Planner Agent regularly contacts the Tracker Agent looking for changes in the environment. Fig. 6 shows the AUML class diagram for the Tracker agent. 3 Conclusions The previously introduced architecture has been implemented using JADE and JADE- LEAP. This initial prototype has been successfully tested in Salamanca during the past few months. The tourists could use mobile devices to contact their agents and to indicate their preferences such as monuments to visit, visits duration, dinner time, amount of money to spend, etc. The cases store information about the environment, for example the opening and closing times of monument. This type of information can be seen as agents believe, for example, and average dinner in the casino restaurant costs around thirty five Euros. Cases can also be previous successful routes (plans), that includes the monuments to visit, the time to spend visiting each monument, information about the cost of the visit, the time required for going to one place to another, the characteristics of the route (museum route, family route, university route, roman route, gothic route, etc.), etc. Once a tourist contacts the system he has to describe his profile, to select the type of visit in which he is interested in, to determine how much money he wants to spend and for how long, and the type of restaurants he, she or a family like more. This information is used to construct the problem case. Then the reasoning mechanism of the planning agent generates the plan [5,6]. Table 1. Tourists evaluation. % Evaluation - degree of satisfaction Tourists that… 8-10 6-8 4-6 0-4 No answer Used the help of the agent 18 % 63,8 4,2 3,1 12,6 16,3 Used the help of a tourist guide 37 % 65,7 15,2 9,4 5,8 3,9 The initial system was tested during the fist four moths of 2004. The case base was initially filled with information collected during ten months. Local tourist guides provided the agent with a number of standard routes. Three hotels of the city offered the option to their 3410 guests to use the help of the agent or a professional tourist guide, around 18% of them decided to use the agent based system and 37% of them used the help of a tourist guide. The Planner agent had stored in its memory 2234 instances of tourist circuits, which covered a wide range of all the most common options that offers the city. On the arrival to the hotel the tourists were asked to evaluate their visit and the route. Table 1 shows the responses given by the tourists after their visit. The tourists that used the help of the agent-based tourist guide provided the answer directly to the agent. As it can be seen, in Table 1, the degree of satisfaction of the tourist that used the help of a professional tourist guide is higher that in the other two cases. Nevertheless, the percentage of the tourists whose degree of satisfaction was very high (between 8 and 10) is very similar in the case of the tourists that use the help of the agent and in the case of the tourists that use the tourist guide. 16,3% of the tourists that used the agent based system did not answer the test or let us know that the system did not work successfully due to technical reasons (possibly the server was down, there was a lack of coverage, the tourist did not use the wireless system adequately, etc.) If we take this into consideration, we can say that most of the tourist (81,24%) that used the help of the agent and did not have technical problems had a high or very high degree of satisfaction (6-10). This degree of satisfaction is similar to the one of the tourist that used the help of professional tourist guides. The CBR component of the architecture provides a straight and efficient way for the manipulation of the agents knowledge and past experiences. The proposal presented in this paper reduces the gap that exists between the formalization and the implementation of BDI agents. Acknowledgements This work has been supported by the MCyT project TIC2003-07369-C02-02. References 1. Aamodt A. and Plaza E. (1994). Case-Based Reasoning: foundational Issues, Methodological Variations, and System Approaches, AICOM. Vol. 7. No 1, March. 2. Bergmann, R., Muñoz-Ávila, H., Veloso, M. and Melis, E. (1998). CBR Applied to Planning. In Lenz, M. Bartsch-Sporl, B., Burkhard, H. and Wess, S. (Eds.) Case-Based Reasoning Technology: From Foundations to Applications. Lecture Notes in Computer Science 1400, pp. 169-200. Springer 1998, ISBN 3-540-64572-1. 3. Corchado J. M. And Laza R. (2003). Constructing Deliberative Agents with Case-based Reasoning Technology , International Journal of Intelligent Systems. Vol 18, No. 12, December. 4. Corchado J. M. and Lees B. (2001). A Hybrid Case-based Model for Forecasting. Applied Artificial Intelligence. Vol 15, no. 2, pp.105-127. 5. Glez-Bedia M. and Corchado J. M. (2002) A planning strategy based on variational calculus for deliberative agents. Computing and Information Systems Journal. Vol 10, No 1, 2002. ISBN: 1352-9404, pp: 2-14. 6. Glez-Bedia M., Corchado J. M., Corchado E. S. and Fyfe C. (2002) Analytical Model for Constructing Deliberative Agents, Engineering Intelligent Systems, Vol 3: pp. 173-185. 7. Martín F. J., Plaza E., Arcos J.L. (1999). Knowledge and experience reuse through communications among competent (peer) agents. International Journal of Software Engineering and Knowledge Engineering, Vol. 9, No. 3, 319-341. 8. Olivia C., Chang C. F., Enguix C.F. and Ghose A.K. (1999). Case-Based BDI Agents: An Effective Approach for Intelligent Search on the World Wide Web, AAAI Spring Symposium on Intelligent Agents, 22-24 March 1999, Stanford University, USA. 9. Rao, A. S. and Georgeff, M. P. (1995). BDI Agents: From Theory to Practice. First International Conference on Multi-Agent Systems (ICMAS-95). San Franciso, USA. 10. Wendler J. and Lenz M. (1998). CBR for Dynamic Situation Assessment in an Agent- Oriented Setting. Proc. AAAI-98 Workshop on CBR Integrations. Madison (USA) 1998. 11. Wooldridge, M. and Jennings, N. R. (1995) Agent Theories, Architectures, and Languages: a Survey. In: Wooldridge and Jennings, editors, Intelligent Agents, Springer-Verlag, pp. 1- 22.