Transcript Agent - LES PUC-Rio

A Hybrid Diagnostic-Recommendation
System for Agent Execution
in Multi-Agent Systems
Master Student: Andrew Diniz da Costa
Advisor: Carlos J. P. de Lucena
[email protected]
[email protected]
Roadmap
• Motivation
• Related Works
• Difficulties of Diagnosing and Providing Recommendations
• Proposal
• Case Study: Intelligent Home
• Conclusions
© LES/PUC-Rio
Motivation
• Open multi-agent systems are societies with autonomous and
heterogeneous agents, which can work together to achieve similar
or different goals.
• The agents have behaviors which determine the steps to achieve
the goals.
• In order to cope with the heterogeneity, autonomy and diversity of
interests among the different agents, governance (or law
enforcement) systems have been defined.
• Governance systems enforce that agents must respect the set of
norms that describe actions that agents are prohibited, permitted
or obligated to do
© LES/PUC-Rio
Motivation
• The Governance Framework was created.
• It is based on testimonies provided by witnesses about facts or
events that they know are related with norms violated.
• The architecture of the framework defines three modules:
– Judgment
• It is responsible for receiving the testimonies and for providing a verdict to
the punishment module
– Reputation
• It is responsible for calculating the reputation of the agents and provides
them to the judgment module and to other application agents
– Punishment
• It is the responsible to determine the penalties to the agents which have
violated the norms of the environment
1- Fernanda Duran, Viviane Torres da Silva, and Carlos J. P. de Lucena (2006), Using Testimonies to Enforce the Behavior of Agents.
2- Guedes, José de Souza Pinto; Silva, Viviane Torres; Lucena, Carlos José Pereira de: A Reputation Model Based on Testimonies, AOIS2006@CAiSE
workshop, Luxembourg, Grand-Duchy of Luxembourg, June 6, 2006.
© LES/PUC-Rio
Motivation
© LES/PUC-Rio
Motivation
• The reason for some agent not to achieve some goal, not
necessarily can be some information provided by another
agent.
• In software systems in general and in particular, in open
multi-agent system, understanding the reason for the
occurrence of failures is a very important goal.
• We decided to propose a new hybrid diagnosticrecommendation system of agents’ called Diagnosing and
Recommending Plans in Multi-Agent Systems (DRP-MAS).
© LES/PUC-Rio
Motivation
• Diagnosis is assumed as the process of determining the
reason why agents do not achieve their goals
• Recommendations are provided on how to achieve the
desired goals that agents have failed to achieve.
• A set of proposals in the literature suggest different ways for
agents to perform diagnostic executions
© LES/PUC-Rio
Related Work - Application of Multi-Agent in Control
and Fault Diagnosis Systems
• A monitor (Monitoring
Agent) for each component
in the system.
• It is the responsible for
collecting information
about each component.
• When obtained, the data is
provided to agents.
• Agents work together to
provide the final diagnosis
without conflicts.
Tie-Jun Li, Yu-Qing Peng, Hai-Wen Zhao, Kai Li; Application of Multi-Agent in Control and Fault Diagnosis Systems, China, 2004
© LES/PUC-Rio
Related Work - Diagnosis as an Integral Part of
Multi-Agent Adaptability
• This work proposes to examine how an independent domain of
diagnosis can behave in multi-agent systems
• An initial step to perform some diagnosis is to indicate the correct
hoped behavior from an agent.
• To compare the hoped result on an execution with the result
obtained.
• To represent this idea, a decomposition’s language of goals/tasks
called TAEMS was used.
• It allows modeling the goals, the possible sub-goals, methods
which can be executed to achieve them, besides the resources
used.
Bryan Horling, Victor Lesser, Régis Vincent, Ana Bazzan, Ping Xuan; Diagnosis as an Integral Part of Multi-Agent Adaptability, 1999
© LES/PUC-Rio
Related Work - Diagnosis as an Integral Part of
Multi-Agent Adaptability
• The work used as case study was the intelligent home.
– This environment has appliances, such as, dishwasher, water heater,
coffee maker, etc., which are controlled by an individual autonomous
agent.
• A scenario used by the environment involves a dishwasher and a
water heater that exist in a house.
• Dishwasher requests hot water from the water heater
– The dishwasher sometimes can not have sufficient resources to
perform its task.
Réis Vicent, Bryan Horling; Experiences in Simulating Multi-Agent Systems Using TAEMS, University of Massachusetts, 2000
© LES/PUC-Rio
Related Work - Diagnosis as an Integral Part of
Multi-Agent Adaptability
• Lacking diagnosis or monitoring, the dishwasher could:
– perform the same execution repeatedly doing a poor job in washing the
dishes,
– or even not to washing anything due to insufficient amounts of hot
water.
• Using diagnosis, the dishwasher could determine through internal
sensors or user feedback that a required resource is missing, and
then that the resource was not being coordinated over.
• Diagnoses are related with other diagnoses.
• In other words, a diagnosis met previously can help to find other
diagnoses.
• A relation between the diagnoses has also been proposed
© LES/PUC-Rio
Difficulties of Diagnosing and Providing Alternative
Executions
• We analyzed a set of points that deserved our attention
during the creation of the new module
1. Deciding how to analyze the behavior of the agents
– The execution of each agent would be monitored (privacy
would be violated)
– Each agent analyzes its own execution
2. Diagnosing agents
– A big challenge was to define which data was necessary to
perform diagnoses on executions of agents.
– A list with such data was defined.
3. Determining strategies to diagnoses
– The challenge was to define services or strategies which could
be used by the different domains
© LES/PUC-Rio
Difficulties of Diagnosing and Providing Alternative
Executions
4. Determining trustworthy agents
– The information received by an agent can determine whether it
will achieve its goal.
– An agent is guilty or innocent, or good or bad with respect to
some request.
5. Providing alternative plans
– A challenge was to decide when a plan would be appropriate to
be executed, and when it should be provided.
6. Representing profiles of agents
– We believe that agents can have profiles, which define
important characteristics, such as, the minimum reputation of
the agents to negotiate.
© LES/PUC-Rio
General Idea
(2)
<<create>>
Mediator
Agent
(1)
Request name of the
Diagnosis Agent
Diagnostic
Agent
(3)
Provide name of the
Diagnosis Agent
Requester
Agent
Master
Agent
© LES/PUC-Rio
General Idea
Diagnostic
Agent
(2)
Provide diagnosis
result
(3)
Provide advices
Master
Agent
Requester
Agent
Plan base
© LES/PUC-Rio
Architecture
Reputation
Governance Framework
Judgment
Reputation
Punishment
DRP-MAS
Diagnosis
Mediation
Recommendation
Artificial Intelligence
Toolset
Application
© LES/PUC-Rio
Performing Diagnosis
• The diagnosis is performed by the Diagnostic agent offered
by the proposed framework
• Such analyses are performed based on a set of information
provided by the Requester agent
• This set can be used in
– Different diagnosing processes
– Recommendation processes
© LES/PUC-Rio
Performing Diagnosis – Information Set
• Resources*
– In some situations the reason for an execution not to be
successfully performed can be the absence of some resource,
or maybe the insufficient amount of resources used to perform
something.
• Norm violated
– If a goal was not achieved, the reason could be a violated
norm. Related data: (i) the agent responsible for the failure,
(ii) degree of violation
• Quality of execution
– To define a degree (as defined by TAEMS**) to an execution
performed by an agent can be useful to diagnoses.
• Goal
– Goal not achieved by the Requester agent.
*Bryan Horling, Victor Lesser, Régis Vincent, Ana Bazzan, Ping Xuan; Diagnosis as an Integral Part of Multi-Agent Adaptability, 1999
**Réis Vicent, Bryan Horling; Experiences in Simulating Multi-Agent Systems Using TAEMS, University of Massachusetts, 2000
© LES/PUC-Rio
Performing Diagnosis – Information Set
• Plan executed
– Plan executed by the requester agent that not achieved the
desired goal
• Agents negotiated
– The diagnosis can indicate some agent as guilty of some
execution.
• Roles of the agents negotiated
– They can be important to update reputations, and to advice
other agents which play the same roles.
• Profile
– Profile of the requester agent
• Other problems
– Other problems perceived by the requester agent, and not
mapped into none above-mentioned data
© LES/PUC-Rio
Performing Diagnosis
•
Strategy of making the diagnoses was defined as a hot spot (flexible point)
in the module.
•
Default strategy. To verify:
– Resource used (to compare with the desired – plan base)
– Norm violated
• It damaged the execution (degree of violation), responsible agents for happing the failure
– Quality of execution, etc
•
Plans in the plan base can be related with a set of data (ex: goal, resource,
norms, etc).
•
The fixed part defined was the process of communication between the
agents.
•
The module is integrated with an API*:
– backward chaining,
– forward chaining and
– reasoning with fuzzy logic
*Joseph P. Bigus, Jennifer Bigus; Constructing Intelligent Agents Using Java, second edition.
© LES/PUC-Rio
Providing Advices
• The Master agent incorporates the process of advising
alternative ways to achieve some goal. It is composed of
three steps: (i) to select plans, (ii) to verify the plans need
for agents to request information, (iii) to choose good
agents
Selecting Plan
Verifying Selected Plans
Choosing agents
© LES/PUC-Rio
Selecting Plans
• The action Selecting Plans is the responsible for choosing
alternative plans to achieve the desired goal.
• A lot of different strategies can be defined to perform some
selection (Strategy pattern).
• Methods are provided to offer support to the strategies created
– To search plans related with an information set
– Method which supplies all the plans which achieve the same goal
(except the plan executed by the requester agent), etc.
• Default strategy
– To select plans from the plan base that achieve the same desired goal
excluding the plan used by the Requester agent
© LES/PUC-Rio
Verifying Plans
• After the selection of the alternative plans, it is verified
whether some plan needs information provided by other
agents.
• Each plan has a list with the roles of the agents which need
to perform some communication.
• If the lists of all the plans are empty,
– Without communication with other agents.
• If the list of some plan is not empty
– Request the reputation of the candidate agents.
© LES/PUC-Rio
Choosing agents
• After the Master agent receives the messages provided by
the reputation module of the Governance Framework, this
action is executed.
• Profile of the Requester agent can be used.
• Different kinds of recommendations can be provided:
– Alternative plan, which does not need agents and resources to
be executed.
– Plan with a list of possible agents to request information.
– Plan with a list of agents and with a list of resources, which can
be used.
– Plan with a plan and a list of resources.
© LES/PUC-Rio
The Extended Governance Framework
© LES/PUC-Rio
Case Study: Intelligence Home
• This environment, appliances, such as the dishwasher, water
heater, coffee maker, etc., are controlled by an individual
autonomous agent.
• An interesting aspect of this application are the possible
conditions which allow the creation of scenarios involving
cooperative interactions, different kinds of conflicts and
constrained resources.
• Two cases were chosen:
– The first case is about a dishwasher, which tries to achieve its
goal of washing the dishes.
– The second case is about a coffee maker, which has the goal of
making 20 cups of strong coffee.
© LES/PUC-Rio
Case Study: Intelligence Home
• Agents
– Coffee maker
– Tester of coffee
• Goal
– To make 20 cups of strong coffee
Provides coffee
Bad coffee
Tester
Coffee Maker
© LES/PUC-Rio
Case Study: Intelligence Home
(2)
<<create>>
Mediator
Agent
(1)
Request name of the
Diagnosis Agent
Diagnostic
Agent
(3)
Provide name of the
Diagnosis Agent
Coffee Maker
Master
Agent
© LES/PUC-Rio
Case Study: Intelligence Home
Rule Base – Forward Chaining
It verifies the amount
of necessary
Quality
of
the
plan=0
resources to
make 20 cups of strong
Problem_Strong_Coffee
_20_Cups:
Amount of water=600
(mL)
IF conclusion_coffee=
weak_coffee
AND
coffee
conclusion_water
Amount of powder=20
(grams) = Coffee_Incorrect_Water
AND
quality_service
<10 THEN
Goal:
to make other
20 cups
of with the
It searches
plans
same goal
problem= problem_amount_powder_and_cups
strong coffee
Weak_Coffee:
… selected
With the
plans, the correct
Diagnostic
Agent
IF amount_powder <30 THEN
quantity of powder
and waterweak_coffee
to make the
conclusion_coffee=
coffee is informed in the plans.
Strong_Coffee:
IF amount_powder >29 THEN
conclusion_coffee= strong_coffee
(2)
Provide diagnosis:
problem_amount_powder_and_cups
Coffee_Correct_Water:(3)
Provide
advices
IF amount_water=1000
THEN
Conclusion_water= Coffee_Correct_Water
Coffee ‘Maker
Coffee_Incorrect_Water:
IF amount_water!=1000 THEN
Conclusion_water= Coffee_Incorrect_Water
problem_amount_powder_and_cups
© LES/PUC-Rio
Master
Agent
Case Study: Intelligence Home
Provides coffee
Good coffee
Tester
Coffee Maker
© LES/PUC-Rio
Conclusions and Future Works
• Paper: A Hybrid Diagnostic-Recommendation System for
Agent Execution in Multi-Agent Systems
• To apply the approach in a case study more complex.
• DRP-MAS to mobile
• Scenario using Mobile Process Service concept
© LES/PUC-Rio
Expert people
on the world
Expert people
on the world
requesting information
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
© LES/PUC-Rio
Conclusions And Future Works
• Applying diagnoses
– If some agent did not complete its execution
– If some device did not receive the desired service
• Possible problems: space of memory, connection, etc
• Applying reputation to provide advices of execution
– In agents / experts
• provide bad information
• have problems with its execution
• delay a long time to provide some information
– Services / Products
• Prices
• Quality
© LES/PUC-Rio
References
•
•
•
•
•
•
•
•
Nicholas R. Jennings, Michael Wooldridge (1999), Agent- Oriented Software
Engineering; Proceedings of the 9th European Workshop on Modelling Autonomous
Agents in a Multi-Agent World : Multi-Agent System Engineering (MAAMAW-99), Vol.
1647, Springer-Verlag: Heidelberg, Germany, oo. 1-7.
Michael Wooldridge, Paolo Ciancarini, P. (2000) Agent-Oriented Software
Engineering: The State of the Art, in First Int. Workshop on Agent-Oriented
Software Engineering, Vol. 1957, Springer-Verlag, Berlin, pp. 1-28
López, F.: Social Powers and Norms: Impact on Agent Behaviour. PhD thesis.
University of Southampton. UK (2003).
Boella, G.; van der Torre, L.: Regulative and Constitutive Norms in Normative MultiAgent Systems. In Proceeding of 9th International Conference on the Principles of
Knowledge Representation and Reasoning. California (2004).
Singh, M.: An Ontology for Commitments in Multiagent Systems: Toward a Unification
of Normative Concepts. Artificial Intelligence and Law v. 7 (1) (1999) 97-113.
Tie-Jun Li, Yu-Qing Peng, Hai-Wen Zhao, Kai Li; Application of Multi-Agent in
Control and Fault Diagnosis Systems, China, 2004 IEEE
Bryan Horling, Victor Lesser, Régis Vincent, Ana Bazzan, Ping Xuan; Diagnosis as an
Integral Part of Multi-Agent Adaptability, 1999
Nico Roos, Annette tem Teije, André Bos, Cees Witteveen; An Analysis of MultiAgent Diagnosis, AAMAS’02, 2002
© LES/PUC-Rio
References
•
•
•
•
•
•
•
•
•
•
•
Fernanda Duran, Viviane Torres da Silva, and Carlos J. P. de Lucena (2006), Using Testimonies to
Enforce the Behavior of Agents.(referência incompleta)
Guedes, José de Souza Pinto; Silva, Viviane Torres; Lucena, Carlos José Pereira de: A Reputation
Model Based on Testimonies, AOIS2006@CAiSE workshop, Luxembourg, Grand-Duchy of
Luxembourg, June 6, 2006.
Patel, J., Teacy, W., Jennings, N., Luck, M., Chalmers, S., Oren, N., Norman, T., Preece, A., Gray, P.,
Shercliff, G., Stockreisser, P., Shao, J., Gray, W., Fiddian, N., Thompson, S.: Monitoring, Policing and
Trust for Grid-Based Virtual Organisations. In Proc. of the UK e-Science All Hands Meeting 2005 UK
(2005).
Victor Lesser, Bryan Horling, and et al. The TAEMS whitepaper / envolving specification.
http://dis.cs.umass.edu/research/taems/white/. Last access in November, 2007.
Réis Vicent, Bryan Horling; Experiences in Simulating Multi-Agent Systems Using TAEMS,
2000 IEEE.
Tom Wagner, Valerie Guralnik, John Phelps; TAEMS Agents: Enabling Dynamic Distributed
Supply Chain Management.
Silva, V., Cortês, M., Lucena, C. J. P.: An Object-Oriented Framework for Implementing Agent
Societies, MCC32/04. Technical Report, Computer Science Department, PUC-Rio. Rio de Janeiro, BR
(2004).
Andrew D. Costa, Carlos J. P. Lucena, Viviane T. Silva: Remodelando e Estendendo o Agent Society
Framework. Techical Report, Computer Science Department, PUC-Rio. Rio de Janeiro, BR (2006).
The Foundations of Intelligent Physical Agents; Official web site; http://www.fipa.org/; February,
2008.
Gamma, E.; Helm, R.; Johnson, R.; Vlissides, J.: Design Patterns: Elements of Reusable ObjectOriented Software.
Joseph P. Bigus, Jennifer Bigus; Constructing Intelligent Agents Using Java, second edition.
© LES/PUC-Rio
The End 