Transcript Andrew_Costa_-_A_Hyb.. - LES PUC-Rio

A Hybrid Diagnostic-Recommendation
Approach for Multi-Agent Systems
Andrew Diniz da Costa1
Carlos J. P. de Lucena1
Viviane T. da Silva2
1Pontifícia
Universidade Católica do Rio de Janeiro, Rio de Janeiro, Brazil
2Universidad Complutense de Madrid, Madrid, Spain
{acosta, lucena}@inf.puc-rio.br, [email protected]
Motivation
•
Multi-agent systems are societies with autonomous and heterogeneous
agents
– Achieve common goals or
– Different goals
•
Competitions based on agents (TAC / ART-Testbed)
•
Agents are interactive and goal-oriented entities
– Agents execute plans in order achieve their goals
– Agents interact with other agents while executing their plans
•
After deciding which goal it will try to achieve, the agent selects one of its
plans that may help it to achieve the goal
•
However, it may be the case that the agent could not achieve the goal by
executing such a plan
•
There are several reasons for an agent fails while trying to achieve a goal
Andrew D. Costa © LES/PUC-Rio
Motivation
• Interesting scenarios are based on ubiquitous computing
• A client requests a service from a mobile device (i.e. cell
phone or PDA) to a set of provider agents of the service.
• If the service was not provided correctly
– It becomes important to understand why such failures occurred
– and to seek a solution to the problem by recommending other
plans that will attempt to achieve the goal
Andrew D. Costa © LES/PUC-Rio
Hybrid Diagnostic-Recommendation System
• Our approach: a system to help agents on diagnosis the
failures and to recommend alternative plans
• Diagnosis is assumed as the process of determining the
reasons that caused the failures while trying to achieve a
goal
• Recommendation is an alternative plan select based on the
diagnosis that could be used to try to achieve the same goal
Andrew D. Costa © LES/PUC-Rio
Proposal (I/II)
• Defining strategies that allow performing different
diagnoses.
• Defining strategies that provide recommendations to agents
in order to achieve the desired goals.
• Providing strategies of diagnosis and recommendation that
can be used in different domains.
• Representing new strategies of diagnosis and
recommendation.
Andrew D. Costa © LES/PUC-Rio
Proposal (II/II)
• Providing a set of data that can be used in diagnoses and
recommendations.
• Extending the set of data from the characteristics of the
domain.
• Providing different kinds of reputation used to distinguish
which agents should be used in interactions.
Andrew D. Costa © LES/PUC-Rio
Difficulties of Diagnosing and Providing Alternative
Executions
1. Deciding how to analyze the behavior of the agents
– To determine an appropriate way to analyze the behavior of
the agents. Two possible ways: (i) the execution of each agent
would be monitored (privacy would be violated), (ii) each
agent detects the failures and is able to provide related
information
2. Selecting data for diagnosing
– To define the data needed to perform diagnoses on the
executions of agents
– A list with such data was defined
3. Determining strategies to diagnoses
– To define strategies that could be used in different domains
Andrew D. Costa © LES/PUC-Rio
Difficulties of Diagnosing and Providing Alternative
Executions
4. Determining trustworthy agents
– The information received by an agent can influence on the
achievement of its goals
– Partners can cause the failures. How can I trust my partners?
5. Providing recommendations
– To define strategies that could cope with the different
diagnosis
6. Representing profiles of agents
– To consider the agents profiles while providing
recommendations
Andrew D. Costa © LES/PUC-Rio
General Idea
(2)
<<create>>
Mediator
Agent
(1)
Request name of the
Diagnosis Agent
(3)
Send the
Recommendation name
Diagnostic
Agent
(5)
Provide name of the
Diagnosis Agent
Requester
Agent
Recommendation
Agent
Andrew D. Costa © LES/PUC-Rio
General Idea
Diagnostic
Agent
(2)
Provide diagnosis
result
(3)
Provide advices
Recommendation
Agent
Plan data
base
Requester
Agent
Andrew D. Costa © LES/PUC-Rio
General Idea
Diagnosis Type 1
request
Requester A
provide
Diagnosis
Agent A
Diagnosis Type 2
Mediator A
Diagnosis
Agent B
request
Recommendation Types
provide
Requester B
Mediator B
Recommendation
Agent B
Recommendation
Agent A
Andrew D. Costa © LES/PUC-Rio
The DRP-MAS object-oriented framework
DRP-MAS
Mediation
Diagnosis
Recommendation
Artificial Intelligence
Toolkit
Reputation
Andrew D. Costa © LES/PUC-Rio
Mediation Module
• Goal: Define Mediator agent that is the responsible for
creating an exclusive Diagnostic and Recommendation agent
to the Requester.
• Different mediators can be defined.
• Avoid Requesters wait for a long time. Valid approach when
the system supports the amount of agents.
• It is possible to combine different strategies of diagnosis
and recommendation.
Andrew D. Costa © LES/PUC-Rio
Information Set
Information that can be provided:
• Goal
– The goal that was not achieved
• Plan executed
– The plan executed by the agent
• Resources:
– it may be the case that the resource could not be found, could
not be used, the amount was not sufficient, …
• Profile
– The agent’s profile
• Quality of service
– A degree used to qualify the execution of the plan
Andrew D. Costa © LES/PUC-Rio
Information Set
• Partners
– The agents with whom the agent has interacted
• Services used
– Services requested while the plan was executed.
• Belief Base
– Knowldge base used by the requester agent.
Andrew D. Costa © LES/PUC-Rio
Diagnosis Module
• Goal: to perform diagnosis
• Such analyses are performed based on a set of information
provided by the Requester agent (application agent)
• Strategy of diagnosis is a hot spot (flexible point)
• Diagnosis can be classified as:
– Main Diagnosis: met from the information set provided by the
Requester agent.
– Inferred Diagnosis: met from inferences. Data that were not provided
by the Requester agent.
• DRP-MAS framework helps in the inference process from the
artificial intelligence model.
Andrew D. Costa © LES/PUC-Rio
Artificial Intelligence Module (I/III)
• Goal: Provide algorithms in order to create strategies of
diagnosis and recommendation.
Joseph P. Bigus, Jennifer Bigus; Constructing Intelligent Agents Using Java, second edition.
Andrew D. Costa © LES/PUC-Rio
Artificial Intelligence Module (II/III)
• Algorithms:
– backward chaining
– forward chaining
– fuzzy logic
• Inferred service from the forward chaining.
– Verify which variables on the rule base were used in some
execution.
– The variables, which were not used, are now used. It considers
like the data had been provided by the Requester.
Andrew D. Costa © LES/PUC-Rio
Artificial Intelligence Module (III/III)
Met diagnosis from data provided
by the Requester agent.
Inferred Diagnoses from data did not provided
by the Requester agent
Andrew D. Costa © LES/PUC-Rio
Providing Recommendations
• The Recommendation agent incorporates the process of
advising alternative ways to achieve some goal.
• It is composed of three steps:
– (i) selecting plans,
– (ii) verifying the plans need for agents to request information,
– (iii) choosing good agents
Andrew D. Costa © LES/PUC-Rio
Selecting Plans (I/II)
• Goal: Choose alternative plans in order to achieve the
desired goal of the Requester agent.
• The strategy used to select plans is a hot-spot (flexible
point)
• Plan base used
• Each plan should be associated with a set of information
that describes:
– resources used during the execution, desired goal, profiles of
agents that accept executing the plan, quality of service, etc.
Andrew D. Costa © LES/PUC-Rio
Selecting Plans (II/II)
• DRP-MAS provides two services that help on the
recommendation process:
– Selecting plans that are related with provided data
– Selecting plans that are not related with a set of data
• When no plan is met, a message is sent to the Requester
and the process is finished.
• When some plan is met, the second step of the process is
executed
Andrew D. Costa © LES/PUC-Rio
Verifying Selected Plans
• Goal: It verifies if the selected plans need of agents.
• When no plan needs to request services, a message is
provided to the Requester agent with the recommendations
• If the plan indicates that the agent will need to interact with
other agents, it is necessary to choose trustful agents
• In order to choose trustful agents, the recommendation
requests to the Reputation agent a set of candidate agents
– Necessary services
– Requester profile
Andrew D. Costa © LES/PUC-Rio
Choosing Agents
• Goal: It selects agents that will be recommended from the
candidate agents provided by the Reputation agent.
• When a plan does not have agents to recommend, then the
plan is not considered.
• When the plan has some agent, it is recommended.
• Strategy of recommendation is a hot-spot of the framework,
because different reputation models and profiles can be
used.
• At the end the plans are recommended to the Requester
agent.
Andrew D. Costa © LES/PUC-Rio
Reputation Module
• Goal: Represent the reputation concept of agents.
• Provide two models: centralized and decentralized.
• Centralized model is based on Report1 system created in the
Governance Framework2.
• Decentralized model based on Fire model3.
1) Guedes, J., Silva, V., Lucena, C., 2008. A Reputation Model Based on testimonies. In: Agent Oriented Information
Systems IV: Proc. of the 8th International Bi-Conference Workshop (AOIS 2006 post-proceedings), LNCS (LNAI) 4898,
Springer-Verlag, pp. 37-52.
2) Silva, V.; Duran, F.; Guedes, J., Lucena, C., 2007. Governing Multi-Agent Systems, In Journal of Brazilian Computer
Society, special issue on Software Engineering for Multi-Agent Systems, n. 2 vol. 13, pp. 19-34.
3) Huynh, T. D., Jennings, N. and Shadbolt, N., 2004, FIRE: an integrated trust and reputation model for open multi-agent
systems. In Proceedings of the 16th European Conference on Artificial Intelligence, 2004, Valencia, Spain.
Andrew D. Costa © LES/PUC-Rio
Reputation Module
Decentralized
base
Decentralized
base
Centralized
base
Decentralized
base
Decentralized
base
Andrew D. Costa © LES/PUC-Rio
Reputation Module
• Centralized model
– Global reputations
– It is possible to define different strategies
– Some default strategies are provided
• Decentralized model
– Interaction trust, Witness reputation, Certified reputation
– Offer standard calculation proposed in the Fire model
– Change calculations
– Define other decentralized reputations
Andrew D. Costa © LES/PUC-Rio
Providing Support to Ubiquitous Computing
• DRP-MAS framework relates two new concepts.
• Device used: Different characteristics of the available
devices: (i) type of device, (ii) model, (iii) language that
the data must be provided by the agent.
• Connections: Characteristics of connections, i.e., (i) speed,
(ii) tecnology (ex: wireless, LAN, WAN, etc.) and (iii) IP
address.
Andrew D. Costa © LES/PUC-Rio
Desenvolvimento DRP-MAS
• Jadex1 + Report system (centralized model) + Fire
(decentralized model)
• ASF2 + Report system (centralized and decentralized model)
– Easy to adapt with the approach proposed.
1) Poukahr, A. and Braubach, L., 2007c, Jade Tutorial, Distributed System Group University of Hamburg, Germany,
Release 0.96. Acceded at: http://vsis-www.informatik.uni-hamburg.de/projects/jadex
2) Costa, Andrew D., Lucena, Carlos J. P., Silva, Viviane T., Azevedo, Sérgio C., Soares, Fábio A., 2008, Computing Reputation
in the Art Context: Agent Design to Handle Negotiation Challenges, Trust in Agent Societies workshop, The Seventh
International Conference on Autonomous Agents and Multiagent System (AAMAS’08), Estoril, Portugal.
Andrew D. Costa © LES/PUC-Rio
Scenarios of Use
• Four scenarios.
• Two based on the intelligent home domain1.
• Two scenarios based on ubiquitous computing.
1) Horling, B., Lesser, V., Vincent, R., Bazzan, A. Xuan, P., 2000. Diagnosis as an Integral Part of Multi-Agent Adaptability,
DARPA Information Survivability Conference and Exposition, DISCEX’00, Proceedings, Volume 2, pp. 211-219.
Andrew D. Costa © LES/PUC-Rio
Scenarios – Intelligent Home
• Intelligent home domain is composed for agents that control
different appliances.
• Two scenarios:
– Washing dishes
– Making 20 cups of strong coffee
Andrew D. Costa © LES/PUC-Rio
Washing Dishes
DRP-MAS
Forward Chaining
Agents
Request
Recommendations
Reputation
Provide
Recommendations
Request hot water
Request hot water
Water Heater
Water Heater
Dishwasher
Andrew D. Costa © LES/PUC-Rio
Making 20 cups of strong coffee
DRP-MAS
Forward Chaining
Agents
Reputation
Request
Recommendations
Provide
Recommendations
Send coffee
Tester
Send result
Coffee Maker
Andrew D. Costa © LES/PUC-Rio
Mobile Process Service
Expert people
on the world
requesting information
Expert people
on the world
requesting information
Agent Team 1
Agent Team 2
Expert
Expert person Madrid
Rio de Janeiro person
Brazil
Spain
Web
requesting
information
requesting
information
requesting information
requesting information
Waterloo Expert person
Canada
Expert person London
England
Agent Team 3
Andrew D. Costa © LES/PUC-Rio
Scenarios – Ubiquitous Computing
• Two scenarios
– Translation (Portuguese to English)
– Music Market Place
• Using mobile devices: cell phones (Jade Leap1) and
computers.
1) Caire, G., 2003, LEAP User Guide, Copyright (C) TILAB, LEAP3.1, December.
Andrew D. Costa © LES/PUC-Rio
Scenario - Translation
DRP-MAS
Forward Chaining
Agents
Reputation
Request Recommendation
Customer
Translator
Translator
Expert
Customer
Andrew D. Costa © LES/PUC-Rio
Scenario– Music Market Place
DRP-MAS
Forward Chaining
Agents
Request
Recommendations
Reputation
Provide
Recommendations
Seller
(Cheap)
Request CD from the music
Buyer
Expert
Andrew D. Costa © LES/PUC-Rio
Seller
Final Considerations – Main Contributions
•
Identifying challenges in order to propose a generic solution to
define diagnoses and recommendations.
•
Defining a set of information in order to identify diagnoses and
recommendations. Such data can be used in different domains.
•
Defining strategies of diagnosis and recommendation that can be
used in different domains.
•
Proposing an approach that allows creating different strategies of
diagnosis and recommendations from a generic structure.
•
Integrating the reputation, diagnosis and recommendation
concepts.
Andrew D. Costa © LES/PUC-Rio
Final Considerations – Trabalhos Futuros
• Adaptation of agents.
• Provide a better support to ubiquitous computing.
• Problems of performance.
Andrew D. Costa © LES/PUC-Rio
Final Considerations - Papers
•
Third Workshop on Software Engineering for Agent-oriented Systems
(SEAS 2007)
•
3th International Conference on Software and Data Technologies (ICSOFT
2008)
•
Workshop Trust in Agent Societies: AAMAS’08
•
Fourth Workshop on Software Engineering for Agent-oriented Systems
(SEAS 2008) – 2 papers
•
ACM Transactions on Computer Systems (ACM TOCS) – Journal (submitted)
•
Trust, Reputation, Evidence and Other Collaboration Know-how – 5th ACM
SAC TRECK Track (submitted)
•
Springer book in LNCS/LNAI (submitted)
Andrew D. Costa © LES/PUC-Rio
A Hybrid Diagnostic-Recommendation
System for Agent Execution
in Multi-Agent Systems
Andrew Diniz da Costa1
Carlos J. P. de Lucena1
Viviane T. da Silva2
Thanks !!
{acosta, lucena}@inf.puc-rio.br, [email protected],