Goal Arguments (which justify agents' adoption of certain goals) in the paper 'Towards Interest-Based Negotiation' (TIBN) by Iyad Rahwan et al take the form ((SuperG,B,SubG):G), i.e. an agent adopts (intends) a goal (G) because it believes G is instrumental to achieve its supergoal (SuperG), believes the context (B) which justifies G to be true and believes the plan (SubG) for achieving G to be achievable.
We identify here a few forms of attacks allowed (in TIBN) on these Goal Arguments for which we have equivalents in our multi-agent setting of 'On the Benefits of Argumentation for Negotiation' (OBAN).
(1)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬b where b is a belief in B, i.e. disqualifying a context condition.
- Similar attack in OBAN: Agent Y argues "I do not have resource R", where "you have resource R" is a belief agent X has (& utters) as part of either requesting R from Y or requesting R2 from Y. In the latter case, X's prior argument would be: "Y does not need R2 because Y has R (which alone is sufficient for fulfilling Y's goal)".
(2)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬p where p is a goal in SubG, i.e. a subgoal is unachievable.
- Similar attack in OBAN: Agent Y argues "I need to retain resource R (and hence your (sub)goal of obtaining R is unachievable)", where R is a resource agent X requests from Y.
(3)
- Attack: For a Goal Argument ((SuperG,B,SubG):R), show set of goals P such that achieve(P,G) where G is a goal in SuperG and R is not a goal in P, i.e. there is an alternative plan P which achieves the supergoal G and does not include R.
- Similar attacks in OBAN (in the case where R is a resource ("goal" in the language of TIBN) agent X requests from agent Y):
--- X argues "you do not need resource R (since you have a resource R2 that alone is sufficient for fulfilling your supergoal G)".
--- X argues "you do not need resource R (since I have a resource R2 that alone is sufficient for fulfilling your supergoal G and I will exchange with you R2 for R)".
Showing posts with label dialogues. Show all posts
Showing posts with label dialogues. Show all posts
Sunday, 28 December 2008
Monday, 22 December 2008
44, Towards Interest-Based Negotiation
Some thoughts following on from reading 'Towards Interest-Based Negotiation' (2003) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:
The paper contains some nice ideas about goal selection which would (/could!) be useful in a (larger) context of multi-agent negotiation (/resource allocation) and in building a generative model (as I intend), but the work here leaves much unspecified and is not generative in and of itself. What is presented in Section 5 ("Dialogues about Goals") is a protocol. No policy or strategy is defined. This is left for future work. I will read the authors' newer paper ('An Empirical Study of Interest-Based Negotiation') to see if this is done and also any other related (later papers) by the authors.
In addition, the framework deals with agent systems consisting of two agents only.
Content of the paper: "Arguing about goals vs Arguing about beliefs", "Agents and goal support" (goals and beliefs/subgoals/supergoals/roles/adoption), "How to attack a goal" (attacking beliefs/subgoals/supergoals), "Dialogues about goals".
"Goal arguments" are presented to be of the form (H:G), where H is the triple support (SuperGoal,Beliefs,SubGoals) for G.
An interesting question, identified as outside the scope of this paper, is: How does an agent, given a top-level goal, generate (from the various options) the set of (sub-) goals to achieve? Suggested approaches: consider the costs of adopting different plans as well as the utilities of the goals achieved, or, identify the goal(s) with the strongest support.
The paper contains some nice ideas about goal selection which would (/could!) be useful in a (larger) context of multi-agent negotiation (/resource allocation) and in building a generative model (as I intend), but the work here leaves much unspecified and is not generative in and of itself. What is presented in Section 5 ("Dialogues about Goals") is a protocol. No policy or strategy is defined. This is left for future work. I will read the authors' newer paper ('An Empirical Study of Interest-Based Negotiation') to see if this is done and also any other related (later papers) by the authors.
In addition, the framework deals with agent systems consisting of two agents only.
Content of the paper: "Arguing about goals vs Arguing about beliefs", "Agents and goal support" (goals and beliefs/subgoals/supergoals/roles/adoption), "How to attack a goal" (attacking beliefs/subgoals/supergoals), "Dialogues about goals".
"Goal arguments" are presented to be of the form (H:G), where H is the triple support (SuperGoal,Beliefs,SubGoals) for G.
An interesting question, identified as outside the scope of this paper, is: How does an agent, given a top-level goal, generate (from the various options) the set of (sub-) goals to achieve? Suggested approaches: consider the costs of adopting different plans as well as the utilities of the goals achieved, or, identify the goal(s) with the strongest support.
27, On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation
Some thoughts following on from re-reading 'On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation' (2007) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:
- What is presented is a protocol and not a generative model as such.
- The negotiation framework consists of (/is limited to) two agents.
- Agents' preferences over (sets of) resources is specified as a (pre-given) numerical utility function. "Deals" between agents (to reallocate resources) make use of "side payments" based on this utility function.
- The relationship "sub" (linking a goal to "sub" -goals and/or -resources needed to achieve it) seems shared between all agents (though agents have no prior knowledge of each other's main goals or preferences).
- Much in this paper rests on the existence/allowance of "partial plans" (wherein leaf nodes may be goals as well as resources) and the setting of positive interaction between agents' "shared"/"common" goals such that an agent may benefit from a common goal (or sub-goal) achieved by the other agent.
Monday, 11 February 2008
40, The Problem of Retraction in Critical Discussion
Contents of 'The Problem of Retraction in Critical Discussion' (2001), by Erik C. W. Krabbe
In many contexts a retraction of commitment is frowned upon... But on the other hand, the very goal of critical discussion - resolution of a dispute - involves a retraction, either of doubt, or of some expressed point of view...
1, The Problem
2, Ingredients for a Solution
(i) Among the rules of dialogue there must be a number of retraction rules that determine, in each dialogical situation, which retractions are permissible...
(ii) If a retraction is permissible the rule should stipulate what, exactly, are the consequences of the retraction...
(iii) ... there must be different stipulations for different types of dialogue.
(iv) ... Retraction rules should take into account the type of persuasion dialogue in which they are to function...
(v) Even within one type of dialogue, there is a need for distinct retraction rules for each type of commitment that occurs within dialogues of that type...
(vi) Another distinction between types of commitment is that between light-side and dark-side commitments...
(vii) ... have a number of different models of dialogue for different types and situations...
(viii) ... it is advisable, in model construction, to make retraction just a bit costly. As was noted above, one might stipulate that retractions lead to further retractions...
3, A Survey of Commitment Types and Constraints on Retraction
- Assertions
- Concessions (Presumptions, Fixed Concessions, Free Concessions)
4, On how to run the hare and hunt with the hounds
In many contexts a retraction of commitment is frowned upon... But on the other hand, the very goal of critical discussion - resolution of a dispute - involves a retraction, either of doubt, or of some expressed point of view...
1, The Problem
2, Ingredients for a Solution
(i) Among the rules of dialogue there must be a number of retraction rules that determine, in each dialogical situation, which retractions are permissible...
(ii) If a retraction is permissible the rule should stipulate what, exactly, are the consequences of the retraction...
(iii) ... there must be different stipulations for different types of dialogue.
(iv) ... Retraction rules should take into account the type of persuasion dialogue in which they are to function...
(v) Even within one type of dialogue, there is a need for distinct retraction rules for each type of commitment that occurs within dialogues of that type...
(vi) Another distinction between types of commitment is that between light-side and dark-side commitments...
(vii) ... have a number of different models of dialogue for different types and situations...
(viii) ... it is advisable, in model construction, to make retraction just a bit costly. As was noted above, one might stipulate that retractions lead to further retractions...
3, A Survey of Commitment Types and Constraints on Retraction
- Assertions
- Concessions (Presumptions, Fixed Concessions, Free Concessions)
4, On how to run the hare and hunt with the hounds
Friday, 8 February 2008
39, The Eightfold Way of Deliberation Dialogue
Contents of 'The Eightfold Way of Deliberation Dialogue' (2007), Peter McBurney, David Hitchcock, Simon Parsons
"Deliberation dialogues occur when two or more participants seek to jointly agree on an action or a course of action in some situation..."
1, Introduction
2, Deliberation Dialogues
3, A Formal Model of Deliberations
The following types of sentences are defined: Actions, Goals, Constraints, Perspectives, Facts, Evaluations
The presented formal dialogue model consists of eight stages: Open, Inform, Propose, Consider, Revise, Recommend, Confirm, Close
4, Locutions for a Deliberation Dialogue Protocol
The permissible locutions in the dialogue game are as follows: open_dialogue, enter_dialogue, propose, assert, prefer, ask_justify, move, reject, retract, withdraw_dialogue
5, Example
6, Assessment of the DDF Protocol: Human Dialogues, Deliberation Process, Deliberation Outcomes
7, Discussion: Contribution, Related Work, Future Research
8, Appendix: Axiomatic Semantics
"Deliberation dialogues occur when two or more participants seek to jointly agree on an action or a course of action in some situation..."
1, Introduction
2, Deliberation Dialogues
3, A Formal Model of Deliberations
The following types of sentences are defined: Actions, Goals, Constraints, Perspectives, Facts, Evaluations
The presented formal dialogue model consists of eight stages: Open, Inform, Propose, Consider, Revise, Recommend, Confirm, Close
4, Locutions for a Deliberation Dialogue Protocol
The permissible locutions in the dialogue game are as follows: open_dialogue, enter_dialogue, propose, assert, prefer, ask_justify, move, reject, retract, withdraw_dialogue
5, Example
6, Assessment of the DDF Protocol: Human Dialogues, Deliberation Process, Deliberation Outcomes
7, Discussion: Contribution, Related Work, Future Research
8, Appendix: Axiomatic Semantics
Monday, 26 November 2007
37, An implementation of norm-based agent negotiation
Notes taken from 'An implementation of norm-based agent negotiation' (2007), by Peter Dijkstra, Henry Prakken, Kees de Vey Mestdagh
1, Introduction
2, The Problem of Regulated Information Exchange
3, Requirements for the Multi-Agent Architecture
Knowledge: In order to regulate distributed information exchange, agents must have knowledge of the relevant regulations and the local interpretations of those regulations, their goals and the likely consequences of their actions...
Reasoning: ... the agents should be capable of generating and evaluating arguments for and against certain claims and they must be able to revise their beliefs as a result of the dialogues. Finally, in order to generate conditional offers, the agents should be able to do some form of hypothetical reasoning.
Communication: ...
4, Formalisation
Dialogical interaction: Communication language; Communication protocol
5, Agent Architecture
Description of the Components: User communication module; Database communication module; Agent communication language; Execution cycle module; Negotiation policy module; Argumentation system module
Negotiation Policy: ... Our negotiation policies cover two issues: the normative issue of whether accepting an offer is obligatory or forbidden, and the teleological issue whether accepting an offer violates the agent's own interests. Of course these policies can be different for the requesting and the responding agent... In the negotiation policy for a reject, the policy returns a why-reject move which starts an embedded persuasion dialogue. The specification and implementation of embedded persuasion dialogues will be the subject of future research.
Agent execution cycle: The agent execution cycle processes messages and triggers other modules during the selection of the appropriate dialogue moves. First, the speech act, locution and content are parsed from the incoming message, then depending on the locution (offer, accept, withdraw or reject) the next steps are taken... The execution cycle can be represented in Java pseudo-code...
6, Illustration of the Agent Architecture
Knowledge base: Knowledge is represented in the prolog-like syntax of the ASPIC tool...
Dialogue from example 2: ...
7, Conclusion
1, Introduction
2, The Problem of Regulated Information Exchange
3, Requirements for the Multi-Agent Architecture
Knowledge: In order to regulate distributed information exchange, agents must have knowledge of the relevant regulations and the local interpretations of those regulations, their goals and the likely consequences of their actions...
Reasoning: ... the agents should be capable of generating and evaluating arguments for and against certain claims and they must be able to revise their beliefs as a result of the dialogues. Finally, in order to generate conditional offers, the agents should be able to do some form of hypothetical reasoning.
Communication: ...
4, Formalisation
Dialogical interaction: Communication language; Communication protocol
5, Agent Architecture
Description of the Components: User communication module; Database communication module; Agent communication language; Execution cycle module; Negotiation policy module; Argumentation system module
Negotiation Policy: ... Our negotiation policies cover two issues: the normative issue of whether accepting an offer is obligatory or forbidden, and the teleological issue whether accepting an offer violates the agent's own interests. Of course these policies can be different for the requesting and the responding agent... In the negotiation policy for a reject, the policy returns a why-reject move which starts an embedded persuasion dialogue. The specification and implementation of embedded persuasion dialogues will be the subject of future research.
Agent execution cycle: The agent execution cycle processes messages and triggers other modules during the selection of the appropriate dialogue moves. First, the speech act, locution and content are parsed from the incoming message, then depending on the locution (offer, accept, withdraw or reject) the next steps are taken... The execution cycle can be represented in Java pseudo-code...
6, Illustration of the Agent Architecture
Knowledge base: Knowledge is represented in the prolog-like syntax of the ASPIC tool...
Dialogue from example 2: ...
7, Conclusion
Wednesday, 21 November 2007
36, Towards a multi-agent system for regulated information exchange in crime investigations
Notes taken from 'Towrds a multi-agent system for regulated information exchange in crime investigations' (2006), by Pieter Dijkstra, Floris Bex, Henry Prakken, Kees de Vey Mestdagh
1, Introduction
... we define dialogue policies for the individual agents, specifying their behaviour within a negotiation. Essentially, when deciding to accept or reject an offer or to make a counteroffer, an agent first reasons about the law and then about the interests that are at stake: he first determines whether it is obligatory or permitted to perform the actions specified in the offer; if permitted but not obligatory, the agent next determines whether it is in his interests to accept the offer...
2, The problem of regulated information exchange
3, Examples
4, Requirements for the multi-agent architecture
(Knowledge; Reasoning; Goals; Communication)
5, Outline of a computational architecture
Dialogical Interaction: communication language; communication protocol
The Agents: representation of knowledge and goals; reasoning engine; dialogue policies
6, Illustration of the proposed architecture
7, Conclusion
1, Introduction
... we define dialogue policies for the individual agents, specifying their behaviour within a negotiation. Essentially, when deciding to accept or reject an offer or to make a counteroffer, an agent first reasons about the law and then about the interests that are at stake: he first determines whether it is obligatory or permitted to perform the actions specified in the offer; if permitted but not obligatory, the agent next determines whether it is in his interests to accept the offer...
2, The problem of regulated information exchange
3, Examples
4, Requirements for the multi-agent architecture
(Knowledge; Reasoning; Goals; Communication)
5, Outline of a computational architecture
Dialogical Interaction: communication language; communication protocol
The Agents: representation of knowledge and goals; reasoning engine; dialogue policies
6, Illustration of the proposed architecture
7, Conclusion
Monday, 12 November 2007
Modelling Dialogue Types
Taken from 'Dialogue Frames in Agent Communication' (1998), by Chris Reed
Clearly the various types of dialogue are not concerned with identical substrate: persuasion, inquiry and information-seeking are epistemic, negotiation is concerned with what might generally be called 'contracts', and deliberation with 'plans'. The model presented [] does not aim to restrict either the agent architecture or the underlying communication protocol to any particular formalism...
Thus the foundation of the model is a set of agents, A, each of whom have a set of beliefs, B, contracts, C, and plans, P...
... it is possible to define the set of dialogue types, where each type is a name-substrate pair,
D = {(persuade,B), (negotiate,C), (inquire,B), (deliberate,P), (infoseek,B)}
From this matrix, a dialogue frame is defined as a tuple with four elements...
A dialogue frame is thus of a particular type, t, and focused on a particular topic, tau, - a persuasion dialogue will be focused on a particular belief, a negotiation on a contract, a deliberation on a plan, and so on. A dialogical frame is initiated by a propose-accept sequence, and terminates with a characteristic utterance indicating acceptance or concession to the topic on the part of one of the agents...
Clearly the various types of dialogue are not concerned with identical substrate: persuasion, inquiry and information-seeking are epistemic, negotiation is concerned with what might generally be called 'contracts', and deliberation with 'plans'. The model presented [] does not aim to restrict either the agent architecture or the underlying communication protocol to any particular formalism...
Thus the foundation of the model is a set of agents, A, each of whom have a set of beliefs, B, contracts, C, and plans, P...
... it is possible to define the set of dialogue types, where each type is a name-substrate pair,
D = {(persuade,B), (negotiate,C), (inquire,B), (deliberate,P), (infoseek,B)}
From this matrix, a dialogue frame is defined as a tuple with four elements...
A dialogue frame is thus of a particular type, t, and focused on a particular topic, tau, - a persuasion dialogue will be focused on a particular belief, a negotiation on a contract, a deliberation on a plan, and so on. A dialogical frame is initiated by a propose-accept sequence, and terminates with a characteristic utterance indicating acceptance or concession to the topic on the part of one of the agents...
Tuesday, 30 October 2007
Requirements on Commitment in Dialogue
Taken from 'Fundamentals of Critical Argumentation' (2006), by Douglas Walton
Three General Requirements on Commitment in Dialogue
1, If a proponent is committed to a set of statements, and the respondent can show that another statement follows logically as a conclusion from that set, then the respondent is committed to that conclusion.
2, The respondent has the right to retract commitment to that conclusion, but she must also retract commitment to at least one of the premises. For otherwise it has been shown that she has inconsistent commitments.
3, If one party in a dialogue can show that the other party has inconsistent commitments, then the second party must retract at least one of those commitments.
Inconsitency is generally a bad thing in logic. If a set of statements is inconsistent, they cannot all be true. At least one must be false...
Three General Requirements on Commitment in Dialogue
1, If a proponent is committed to a set of statements, and the respondent can show that another statement follows logically as a conclusion from that set, then the respondent is committed to that conclusion.
2, The respondent has the right to retract commitment to that conclusion, but she must also retract commitment to at least one of the premises. For otherwise it has been shown that she has inconsistent commitments.
3, If one party in a dialogue can show that the other party has inconsistent commitments, then the second party must retract at least one of those commitments.
Inconsitency is generally a bad thing in logic. If a set of statements is inconsistent, they cannot all be true. At least one must be false...
Monday, 3 September 2007
29, Protocol Conformance for Logic-based Agents
'Protocol Conformance for Logic-based Agents' (2003), by Ulrich Endriss, Nicolas Maudet, Fariba Sadri and Francesca Toni
... In non-cooperative interactions (such as negotiation dialogues) occurring in open societies it is crucial that agents are equipped with proper means to check, and possible enforce, conformance to protocols. We identify different levels of conformance (weak, exhaustive, and robust conformance)...
1, Introduction
2, Representing Protocols
(Legality, Expected inputs, Correct responses)
3, Levels of Conformance
(Weak conformance, Exhaustive conformance, Robust conformance)
4, Logic-based Agents
(Checking conformance (Response space), Enforcing conformance, Examples)
5, Conclusion
... In non-cooperative interactions (such as negotiation dialogues) occurring in open societies it is crucial that agents are equipped with proper means to check, and possible enforce, conformance to protocols. We identify different levels of conformance (weak, exhaustive, and robust conformance)...
1, Introduction
2, Representing Protocols
(Legality, Expected inputs, Correct responses)
3, Levels of Conformance
(Weak conformance, Exhaustive conformance, Robust conformance)
4, Logic-based Agents
(Checking conformance (Response space), Enforcing conformance, Examples)
5, Conclusion
Wednesday, 29 August 2007
Example Dialogue (Safe Car)
Taken from 'Dialogue Games for Ontological Commitment' (2003), Robbert-Jan Beun and M. van Eijk
We give an example of a dialogue (somewhat adorned in natural language) that is generated by the rules [presented in the paper]:
A1: Is this a safe car?
A2's ontology defines the non-basic concept 'safety' in terms of 'having airbags' and 'having a good crash test'. According to this interpretation the car is indeed believed to be safe, but since A2 does not know the meaning is shared it responds... :
A2: Yes, it has air bags and a good crash test.
This response is pushed on the stack of A1. Agent A1, however, has a different view on 'safety of cars', and it manifests this discrepency by responding ... :
A1: To my opinion, a safe car would also have traction control.
Agent A2 now knows A1's interpretation of 'safety' ... and since it believes that this particular car does not have traction control it gives the following answer to the initial question ... :
A2: Mhm, if safety also amounts to having traction control then this car is not safe.
This response is pushed on the stack of A1. Agent A1 has received an acceptable answer to its question and ends the dialogue ... :
A1: OK, thank you.
Note that if in the second turn, A2 would not have manifested its interpretation of 'safety', the ontological discrepency would have remained unnoticed, possibly leading A1 to draw incorrect conclusions from the answer.
We give an example of a dialogue (somewhat adorned in natural language) that is generated by the rules [presented in the paper]:
A1: Is this a safe car?
A2's ontology defines the non-basic concept 'safety' in terms of 'having airbags' and 'having a good crash test'. According to this interpretation the car is indeed believed to be safe, but since A2 does not know the meaning is shared it responds... :
A2: Yes, it has air bags and a good crash test.
This response is pushed on the stack of A1. Agent A1, however, has a different view on 'safety of cars', and it manifests this discrepency by responding ... :
A1: To my opinion, a safe car would also have traction control.
Agent A2 now knows A1's interpretation of 'safety' ... and since it believes that this particular car does not have traction control it gives the following answer to the initial question ... :
A2: Mhm, if safety also amounts to having traction control then this car is not safe.
This response is pushed on the stack of A1. Agent A1 has received an acceptable answer to its question and ends the dialogue ... :
A1: OK, thank you.
Note that if in the second turn, A2 would not have manifested its interpretation of 'safety', the ontological discrepency would have remained unnoticed, possibly leading A1 to draw incorrect conclusions from the answer.
Tuesday, 26 June 2007
26.4-6, Argument-based Negotiation among BDI Agents
Notes taken from 'Argument-based Negotiation among BDI Agents' (2002), by Sonia V. Rueda, Alejandro J. Garcia, Guillermo R. Simari
4, Collaborative Agents
Collaborative MAS: A collaborative Multi-Agent System will be a pair of a set of argumentative BDI agents and a set of shared beliefs.
(Negotiating Beliefs; Proposals and Counterproposals; Side-effects; Failure in the Negotiation)
5, Communication Languages
(Interaction Protocol; Interaction Language; Negotiation Primitives)
6, Conclusions and Future Work...
4, Collaborative Agents
Collaborative MAS: A collaborative Multi-Agent System will be a pair of a set of argumentative BDI agents and a set of shared beliefs.
(Negotiating Beliefs; Proposals and Counterproposals; Side-effects; Failure in the Negotiation)
5, Communication Languages
(Interaction Protocol; Interaction Language; Negotiation Primitives)
6, Conclusions and Future Work...
26.3, Argument-based Negotiation among BDI Agents
Notes taken from 'Argument-based Negotiation among BDI Agents' (2002), by Sonia V. Rueda, Alejandro J. Garcia, Guillermo R. Simari
3, Planning and Argumentation
Argumentative BDI Agent: The agents desires D will be represented by a set of literals that will also be called goals. A subset of D will represent a set of committed goals and will be referred to as the agent intentions... The agent's beliefs will be represented by a restricted Defeasible Logic Program... Besides its beliefs, desires and intentions, an agent will have a set of actions that it may use to change its world.
Action: An action A is an ordered triple (P, X, C), where P is a set of literals representing preconditions for A, X is a consistent set of literals representing consequences of executing A, and C is a set of constraints of the form not L, where L is a literal.
Applicable Action...
Action Effect...
3, Planning and Argumentation
Argumentative BDI Agent: The agents desires D will be represented by a set of literals that will also be called goals. A subset of D will represent a set of committed goals and will be referred to as the agent intentions... The agent's beliefs will be represented by a restricted Defeasible Logic Program... Besides its beliefs, desires and intentions, an agent will have a set of actions that it may use to change its world.
Action: An action A is an ordered triple (P, X, C), where P is a set of literals representing preconditions for A, X is a consistent set of literals representing consequences of executing A, and C is a set of constraints of the form not L, where L is a literal.
Applicable Action...
Action Effect...
26.1-2, Argument-based Negotiation among BDI Agents
Notes taken from 'Argument-based Negotiation among BDI Agents' (2002), by Sonia V. Rueda, Alejandro J. Garcia, Guillermo R. Simari
"... Here we propose a deliberative mechanism for negotiation among BDI agents based in Argumentation."
1, Introduction
In a BDI agent, mental attitudes are used to model its cognitive capabilities. These mental attitudes include Beliefs, Desires and Intentions among others such as preferences, obligations, commitments, etc. These attitudes represent motivations of the agent and its informational and deliberative states which are used to determine its behaviour.
Agents will use a formalism based in argumentation in order to obtain plans for their goals represented by literals. They will begin by trying to construct a warrant for the goal. That might not be possible because some need literals are not available. The agent will try to obtain those missing literals, regarded as subgoals, by executing the actions it has available. When no action can achieve the subgoals the agent will request collaboration...
2, The Construction of a BDI Agent's Plan
Practical reasoning involves two fundamental processes: decide what goals are going to be pursued, and choose a plan on how to achieve them... The selected options will make up the agent's intentions; they will also have an influence on its actions, restrict future practical reasoning, and persist (in some way) in time...
... Abilities are associated with actions that have preconditions and consequences...
"... Here we propose a deliberative mechanism for negotiation among BDI agents based in Argumentation."
1, Introduction
In a BDI agent, mental attitudes are used to model its cognitive capabilities. These mental attitudes include Beliefs, Desires and Intentions among others such as preferences, obligations, commitments, etc. These attitudes represent motivations of the agent and its informational and deliberative states which are used to determine its behaviour.
Agents will use a formalism based in argumentation in order to obtain plans for their goals represented by literals. They will begin by trying to construct a warrant for the goal. That might not be possible because some need literals are not available. The agent will try to obtain those missing literals, regarded as subgoals, by executing the actions it has available. When no action can achieve the subgoals the agent will request collaboration...
2, The Construction of a BDI Agent's Plan
Practical reasoning involves two fundamental processes: decide what goals are going to be pursued, and choose a plan on how to achieve them... The selected options will make up the agent's intentions; they will also have an influence on its actions, restrict future practical reasoning, and persist (in some way) in time...
... Abilities are associated with actions that have preconditions and consequences...
Friday, 22 June 2007
Requesting
Taken from 'Reasoning About Rational Agents' (2000), by Michael Wooldridge
Request speech acts (directives) are attempts by a speaker to modify the intentions of the hearer. However, we can identify at least two different types of requests:
- Requests to bring about some state of affairs: An example of such a request would be when one agent said "Keep the door closed." We call such requests "requests-that".
- Requests to perform some particular action: An example of such a request would be when one agent said "Lock the door." We call such requests "requests-to".
Requests-that are more general than requests-to. In the former case (requests-that), the agent communicates an intended state of affairs, but does not communicate the means to achieve this state of affairs... In the case of requesting to, however, the agent does not communicate the desired state of affairs at all. Instead, it communicates an action to be performed, and the state of affairs to be acieved lies implicit within the action that was communicated...
Request speech acts (directives) are attempts by a speaker to modify the intentions of the hearer. However, we can identify at least two different types of requests:
- Requests to bring about some state of affairs: An example of such a request would be when one agent said "Keep the door closed." We call such requests "requests-that".
- Requests to perform some particular action: An example of such a request would be when one agent said "Lock the door." We call such requests "requests-to".
Requests-that are more general than requests-to. In the former case (requests-that), the agent communicates an intended state of affairs, but does not communicate the means to achieve this state of affairs... In the case of requesting to, however, the agent does not communicate the desired state of affairs at all. Instead, it communicates an action to be performed, and the state of affairs to be acieved lies implicit within the action that was communicated...
Tuesday, 12 June 2007
Conformance to Protocols
A protocol specifies the "rules of encounter" governing a dialogue between agents. It specifies which agent is allowed to say what in a given situation.
There are different levels of (an agent's) conformance to a protocol, as follows:
- Weak conformance - iff it will never utter an illegal dialogue move.
- Exhaustive conformance - iff it is weakly conformant and it will utter at least one dialogue move when required by the protocol.
- Robust conformance - iff it is exhaustively conformant and it utters the (special) dialogue more "not-understood" whenever it receives an illegal move from the other agent.
There are different levels of (an agent's) conformance to a protocol, as follows:
- Weak conformance - iff it will never utter an illegal dialogue move.
- Exhaustive conformance - iff it is weakly conformant and it will utter at least one dialogue move when required by the protocol.
- Robust conformance - iff it is exhaustively conformant and it utters the (special) dialogue more "not-understood" whenever it receives an illegal move from the other agent.
Tuesday, 15 May 2007
21, Commitment in Dialogue
Notes taken from 'Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning' (1995), by Douglas N. Walton and Erik C. W. Krabbe
0, Introduction
1, The Anatomy of Commitment
(Action Commitment, Propositional Commitment)
2, The Dynamics of Commitment
(Incurring of commitment, Loss of commitment, Relations between commitments, Clashing commitments and inconsistency)
3, Dialogues: Types, Goals, and Shifts
(Types and goals of dialogue, Complex dialogue, Dialectical shifts, Illicit shifts and fallacies)
4, Systems of Dialogue Rules
(Tightening up and dark-side commitment, permissive persuasion dialogue, Rigorous persuasion dialogue, Complex persuasion dialogue)
5, Conclusions and Prospects
0, Introduction
1, The Anatomy of Commitment
(Action Commitment, Propositional Commitment)
2, The Dynamics of Commitment
(Incurring of commitment, Loss of commitment, Relations between commitments, Clashing commitments and inconsistency)
3, Dialogues: Types, Goals, and Shifts
(Types and goals of dialogue, Complex dialogue, Dialectical shifts, Illicit shifts and fallacies)
4, Systems of Dialogue Rules
(Tightening up and dark-side commitment, permissive persuasion dialogue, Rigorous persuasion dialogue, Complex persuasion dialogue)
5, Conclusions and Prospects
Friday, 11 May 2007
20, Argumentation Schemes for Presumptive Reasoning
Notes taken from 'Argumentation Schemes for Presumptive Reasoning' (1995), by Douglas N. Walton
1, Introduction
In accepting the (presumptive) premises, the participants are bound to tentatively accept the conclusion, for the sake of argument or discussion, unless some definite evidence comes that is sufficient to indicate rejecting it.
Such presumtively based arguments can be very useful and important in cases where action must be taken, but firm evidence is not presently available.
Practical reasoning is a kind of goal-directed, knowledge-based reasoning that is directed to choosing a prudent course of action for an agent that is aware of its present circumstances. These circumstances can change, and practical reasoning is therefore to be understood as a dynamic kind of reasoning that needs to be corrected or updated as new information comes in.
2, Presumptive Reasoning
We need to distinguish between ``concessions'' and ``substantive commitments''. A substantive commitment is a proposition that a participant in dialogue is obliged to defend, or retract, if challenged by the other party to give reasons to support it. In a word, it has a burden of proof attached to it. This is the type of commitment to a proposition that goes along with having asserted it in a dialogue. A concession is a commitment where there is no such obligation to defend, if challenged. Concessions are assumptions agreed to ``for the sake of argument''. By nature, they are temporary, and do not necessarily represent an arguer's position in a dialogue.
We note the difference between pure supposition and assertion as kinds of speech acts. Assertion always carries with it a burden of proof, becuase assertion implies substantive commitment to the proposition asserted. Supposition (or assumption) however, requires only the agreement of the respondent, and carries with it no burden of proof on either side. Presumption, as a speech act, is halfway between mere supposition and assertion. Presumption essentially means that the proponent of the proposition in question does not have a burden of proof, only a burden to disprove contrary evidence, should it arise in the future sequence of dialogue. The burden here has three important characteristics - it is a future, conditional, and negative burden of proof. It could perhaps be called a burden to rebut, in approriate circumstances.
Presumption is functionally opposed to burden to proof, meaning that presumption removes or absolves one side from the burden, and shifts the burden to the other side.
Presumption is understood as a kind of speech act that is halfway between assertion and mere assumption. An assertion normally carries with itself in argument a burden of proof: ``He who asserts must prove!'' By contrast, if a participant in argumentation puts forward a mere assumption, he or she (or anyone in the dialogue) is free to retract it at any subsequent point in the dialogue without having having to give evidence or reasons that would refute it. Assumptions are freely undertaken and can be freely rejected in a dialogue.
In order to be useful, presumptions must have a certain amount of ``sticking power'', but by their nature, they are tentative and subject to later retraction.
For example, in a potentially hazardous situation, it may be prudentially wise to tilt the burden of proof in the direction of safety. The maxim is to ``err on the side of safety'', where doubt creates the potential for danger.
A simple case is the accepted procedure for handling weapons on a firing range. The principle is always to assume a weapon is loaded, unless you are sure that it is not loaded. The test of whether you are sure of this is that you have, just before, inspected the chamber and perceived clearly that it is empty.
The same kind of example shows also, however, how tied to the specifics of a context or situation this kind of reasoning is. Suppose you are a soldier in wartime getting ready to defend your position against an imminent enemy assualt. Here, reasoning again on practical grounds of safety or self-preservation, you act on a presumption that your weapon may be empty, by checking to see that it is not empty.
Customs, fashions, and popularly accepted ways of doing things, are another important source of presumptions. With many choices on how to do things in life, in the absence of knowledge that one way of doing something is any better or more harmful than another, people often tend to act on the presumption that the way to do something is the popularly accepted way of doing it.
3, The Argumentation Schemes
Walton describes and analyses 25 different argumentation schemes. For each argumentation scheme, a matching set of critical questions is given. This pairing brings out the essentially presumptive nature of the kind of reasoning involved in the use of argumentation schemes, and at the same time reveals the pragmatic and dialectical nature of how this reasoning works. The function of each argumentation scheme is to shift a weight of presumption from one side of a dialogue to the other. The opposing arguer in the dialogue can shift this weight of presumption back to the other side again by asking any of the appropriate critical questions matching that argumentation scheme. To once again get the presumption on his or her side, the original arguer (who used the argumentation scheme in the first place) must give a satisfactory answer to that critical question.
Some of the argumentation schemes are basic or fundamental, whereas others are composites made up from these basic schemes.
4, Argument from Ignorance
The arguments associated with these argumentation schemes are typically used in a balance of considerations type of case, where knowledge or hard information is lacking, of a kind that would enable the problem to be resolved or the dispute to be settled on that basis. In other words, these presumption-based arguments are generally arguments from ignorance. The logic of these arguments could be expressed by the phrase, ``I don't know that this proposition is false, so until evidence comes in to refute it, I am entitled to provisionally assume that it is true.'' All of the argumentation schemes previously studied tend to take this general form.
In some cases, the argument from ignorance is a correct (nonfallacious) argument because we can rightly assume that our knowledge base is complete. If some proposition is not known to be in it, we can infer that this proposition must be false.
5, Ignoring Qualifications
6, Argument from Consequences
The argument from consequences may be broadly characterised as the argument for accepting the truth (or falsehood) of a proposition by citing the consequences of accepting (rejecting) that proposition
1, Introduction
In accepting the (presumptive) premises, the participants are bound to tentatively accept the conclusion, for the sake of argument or discussion, unless some definite evidence comes that is sufficient to indicate rejecting it.
Such presumtively based arguments can be very useful and important in cases where action must be taken, but firm evidence is not presently available.
Practical reasoning is a kind of goal-directed, knowledge-based reasoning that is directed to choosing a prudent course of action for an agent that is aware of its present circumstances. These circumstances can change, and practical reasoning is therefore to be understood as a dynamic kind of reasoning that needs to be corrected or updated as new information comes in.
2, Presumptive Reasoning
We need to distinguish between ``concessions'' and ``substantive commitments''. A substantive commitment is a proposition that a participant in dialogue is obliged to defend, or retract, if challenged by the other party to give reasons to support it. In a word, it has a burden of proof attached to it. This is the type of commitment to a proposition that goes along with having asserted it in a dialogue. A concession is a commitment where there is no such obligation to defend, if challenged. Concessions are assumptions agreed to ``for the sake of argument''. By nature, they are temporary, and do not necessarily represent an arguer's position in a dialogue.
We note the difference between pure supposition and assertion as kinds of speech acts. Assertion always carries with it a burden of proof, becuase assertion implies substantive commitment to the proposition asserted. Supposition (or assumption) however, requires only the agreement of the respondent, and carries with it no burden of proof on either side. Presumption, as a speech act, is halfway between mere supposition and assertion. Presumption essentially means that the proponent of the proposition in question does not have a burden of proof, only a burden to disprove contrary evidence, should it arise in the future sequence of dialogue. The burden here has three important characteristics - it is a future, conditional, and negative burden of proof. It could perhaps be called a burden to rebut, in approriate circumstances.
Presumption is functionally opposed to burden to proof, meaning that presumption removes or absolves one side from the burden, and shifts the burden to the other side.
Presumption is understood as a kind of speech act that is halfway between assertion and mere assumption. An assertion normally carries with itself in argument a burden of proof: ``He who asserts must prove!'' By contrast, if a participant in argumentation puts forward a mere assumption, he or she (or anyone in the dialogue) is free to retract it at any subsequent point in the dialogue without having having to give evidence or reasons that would refute it. Assumptions are freely undertaken and can be freely rejected in a dialogue.
In order to be useful, presumptions must have a certain amount of ``sticking power'', but by their nature, they are tentative and subject to later retraction.
For example, in a potentially hazardous situation, it may be prudentially wise to tilt the burden of proof in the direction of safety. The maxim is to ``err on the side of safety'', where doubt creates the potential for danger.
A simple case is the accepted procedure for handling weapons on a firing range. The principle is always to assume a weapon is loaded, unless you are sure that it is not loaded. The test of whether you are sure of this is that you have, just before, inspected the chamber and perceived clearly that it is empty.
The same kind of example shows also, however, how tied to the specifics of a context or situation this kind of reasoning is. Suppose you are a soldier in wartime getting ready to defend your position against an imminent enemy assualt. Here, reasoning again on practical grounds of safety or self-preservation, you act on a presumption that your weapon may be empty, by checking to see that it is not empty.
Customs, fashions, and popularly accepted ways of doing things, are another important source of presumptions. With many choices on how to do things in life, in the absence of knowledge that one way of doing something is any better or more harmful than another, people often tend to act on the presumption that the way to do something is the popularly accepted way of doing it.
3, The Argumentation Schemes
Walton describes and analyses 25 different argumentation schemes. For each argumentation scheme, a matching set of critical questions is given. This pairing brings out the essentially presumptive nature of the kind of reasoning involved in the use of argumentation schemes, and at the same time reveals the pragmatic and dialectical nature of how this reasoning works. The function of each argumentation scheme is to shift a weight of presumption from one side of a dialogue to the other. The opposing arguer in the dialogue can shift this weight of presumption back to the other side again by asking any of the appropriate critical questions matching that argumentation scheme. To once again get the presumption on his or her side, the original arguer (who used the argumentation scheme in the first place) must give a satisfactory answer to that critical question.
Some of the argumentation schemes are basic or fundamental, whereas others are composites made up from these basic schemes.
4, Argument from Ignorance
The arguments associated with these argumentation schemes are typically used in a balance of considerations type of case, where knowledge or hard information is lacking, of a kind that would enable the problem to be resolved or the dispute to be settled on that basis. In other words, these presumption-based arguments are generally arguments from ignorance. The logic of these arguments could be expressed by the phrase, ``I don't know that this proposition is false, so until evidence comes in to refute it, I am entitled to provisionally assume that it is true.'' All of the argumentation schemes previously studied tend to take this general form.
In some cases, the argument from ignorance is a correct (nonfallacious) argument because we can rightly assume that our knowledge base is complete. If some proposition is not known to be in it, we can infer that this proposition must be false.
5, Ignoring Qualifications
6, Argument from Consequences
The argument from consequences may be broadly characterised as the argument for accepting the truth (or falsehood) of a proposition by citing the consequences of accepting (rejecting) that proposition
Wednesday, 4 April 2007
17, Information-seeking agent dialogs with permissions and arguments
Notes taken from ‘Information-seeking agent dialogs with permissions and arguments’ (2006), by Sylvie Doutre et al.
“… Many distributed information systems require agents to have appropriate authorisation to obtain access to information… We present a denotational semantics for such dialogs, drawing on Tuple Centres (programmable Tuple Spaces)…”
1, Introduction
… we present a formal syntax and semantics for such information-seeking dialogs involving permissions and arguments…
2.1, Dialog systems
The common elements of dialog systems are…
A typology of human dialogs was articulated by Walton and Krabbe, based upon the overall goal of the dialogue, the participants’ individual dialog goals, and the information they have at the commencement of the dialog (the topic language and the context)…
2.2, Tuple spaces
… a model of communication between distributed computational entities… The essential idea is that computational agents connected together may create named object stores, called tuples, which persist, even beyond the lifetimes of their creators, until explicitly deleted… They are stored in tuple spaces, which are black-board-like shared data stores, and are normally accessed by other agents by associative pattern matching… There are three basic operators on tuple spaces: out, rd, in…
2.3, LGL as a semantics for dialog systems
… (We) show how Law-Governed Linda (LGL) can be used as a denotational semantics for these systems, by associating elements of an LGL 5-tuple to the elements of the dialog system. Note that the dialog goal and the outcome rules have no associated elements in LGL…
3, Secure info-seek dialogue
3.1, Motivating example…
3.2, Protocol syntax
… In this system, an argument must be provided by an agent to justify it having permission to access some information. If access to information for agent x is refused by agent y, then agent x must try to persuade agent y that it should be allowed permission. This persuasion is made using arguments. If agent y yields to agent x’s arguments, then y provides x the information requested.
(Definitions given for Participants, Dialog goal, Context, Topic language, Communication language, Protocol, Effect rules, Outcome rules)
3.3, LGL semantics
(Associations to elements of an LGL 5-tuple given for elements of the dialog system: Participants, Context, Communication language, Protocol, Effect rules)
3.4, Illustration…
4, Implementation
In Section 1, we stated that our primary objective was the development of a semantics for these Information-seeking dialogs which facilitated implementation of the protocol. In order to assess whether the protocol and semantics of Section 3 met this objective, we undertook an implementation…
5, Related work and conclusions
… Our contribution in this paper is a novel semantics for information-seeking agent communications protocols involving permissions and arguments, in which utterances under the protocol are translated into commands in Law-Governed Linda and, through them, into actions on certain associated tuple spaces…
“… Many distributed information systems require agents to have appropriate authorisation to obtain access to information… We present a denotational semantics for such dialogs, drawing on Tuple Centres (programmable Tuple Spaces)…”
1, Introduction
… we present a formal syntax and semantics for such information-seeking dialogs involving permissions and arguments…
2.1, Dialog systems
The common elements of dialog systems are…
A typology of human dialogs was articulated by Walton and Krabbe, based upon the overall goal of the dialogue, the participants’ individual dialog goals, and the information they have at the commencement of the dialog (the topic language and the context)…
2.2, Tuple spaces
… a model of communication between distributed computational entities… The essential idea is that computational agents connected together may create named object stores, called tuples, which persist, even beyond the lifetimes of their creators, until explicitly deleted… They are stored in tuple spaces, which are black-board-like shared data stores, and are normally accessed by other agents by associative pattern matching… There are three basic operators on tuple spaces: out, rd, in…
2.3, LGL as a semantics for dialog systems
… (We) show how Law-Governed Linda (LGL) can be used as a denotational semantics for these systems, by associating elements of an LGL 5-tuple to the elements of the dialog system. Note that the dialog goal and the outcome rules have no associated elements in LGL…
3, Secure info-seek dialogue
3.1, Motivating example…
3.2, Protocol syntax
… In this system, an argument must be provided by an agent to justify it having permission to access some information. If access to information for agent x is refused by agent y, then agent x must try to persuade agent y that it should be allowed permission. This persuasion is made using arguments. If agent y yields to agent x’s arguments, then y provides x the information requested.
(Definitions given for Participants, Dialog goal, Context, Topic language, Communication language, Protocol, Effect rules, Outcome rules)
3.3, LGL semantics
(Associations to elements of an LGL 5-tuple given for elements of the dialog system: Participants, Context, Communication language, Protocol, Effect rules)
3.4, Illustration…
4, Implementation
In Section 1, we stated that our primary objective was the development of a semantics for these Information-seeking dialogs which facilitated implementation of the protocol. In order to assess whether the protocol and semantics of Section 3 met this objective, we undertook an implementation…
5, Related work and conclusions
… Our contribution in this paper is a novel semantics for information-seeking agent communications protocols involving permissions and arguments, in which utterances under the protocol are translated into commands in Law-Governed Linda and, through them, into actions on certain associated tuple spaces…
Tuesday, 3 April 2007
16, Dialogues for Negotiation
Notes taken from ‘Dialogues for Negotiation: Agent Varieties and Dialogue Sequences’ (2001), by Fariba Sadri, Francesca Toni and Paolo Torroni
“… (The proposed solution) relies upon agents agreeing solely upon a language of negotiation, while possibly adopting different negotiation policies, each corresponding to an agent variety. Agent dialogues can be connected within sequences, all aimed at achieving an individual agent’s goal. Sets of sequences aim at allowing all agents in the system to achieve their goals…”
1, Introduction
… Many approaches in the area of one-to-one negotiation are heuristic-based and, in spite of their experimentally proven effectiveness, they do not easily lend themselves to expressing theoretically provable properties. Other approaches present a good descriptive model, but fail to provide an execution model that can help to forecast the behaviour of any corresponding implemented system…
… Note that we do not make any concrete assumption on the internal structure of agents, except for requiring that they hold beliefs, goals, intentions and, possibly, resources.
2, Preliminaries
2.1, A performative or dialogue move is an instance of a schema tell(X, Y, Subject, T)… e.g. tell(a, b, request(give(nail)), 1)…
2.2, A language for negotiation L is a (possibly infinte) set of (possibly non ground) performatives. For a given L, we define two (possibly infinte) subsets of performatives, I(L) and F(L)…, called respectively initial moves and final moves. Each final move is either successful or unsuccessful.
2.3, An agent system is a finite set A, where each x in A is a ground term, representing the name of an agent, equipped with a knowledge base K(x).
3, Dialogues
3.4, Given an agent system A, equipped with a language for negotiation L, and an agent x in A, a dialogue constraint for x is a (possibly non-ground) if-then rule of the form: p(T) & C => p’(T + 1), where… The performative p(T) is referred to as the trigger, p’(T + 1) as the next move and C as the condition of the dialogue constraint.
3.5, A dialogue between two agents x and y is a set of ground performatives, {p0, p1, p2, …}, such that… A dialogue {p0, p1, … pM)… is terminated if pM is a ground final move…
3.6, A request dialogue wrt a resource R and an intention I of agent x is a dialogue… such that…
3.7, (Types of terminated request dialogues) Let I be the intention of some agent a, and R be a missing resource in I. Let d be a terminated resource dialogue wrt R and and I, and I’ be the intention resulting from d. Then, if missing(Rs), plan(P) are in I and missing(Rs’), plan(P’) are in I’:
i) d is successful if P’ = P, Rs’ = Rs \ {R};
ii) d is conditionally or c-successful if Rs’ /= Rs and Rs’ /= Rs \ {R};
iii) d is unsuccessful if I’ = I.
Note that, in the case of c-successful dialogues, typically, but not always, the agent’s plan will change (P’ /= P).
3.8, An agent x in A is convergent iff, for every terminated request dialogue of x, wrt some resource R and some intention I, the cost of the returned intention I’ is not higher than the cost of I. The cost of an intention can be defined as the number of missing resources in the intention.
4, Properties of Agent Programs
4.9, An agent x in A is deterministic iff, for each performative p(t) which is a ground instance of a schema in L(in), there exists at most one performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in the agent program S and ‘K & p(t)’ entails C.
4.10, An agent program S is non-overlapping iff for each performative p which is a ground instance of a schema in L(in), for each C, C’in S(p) such that C /= C’, then C ^ C’ = false.
(Theorem 1) If the (grounded) agent program of x is non-overlapping, then x is deterministic.
4.11, An agent x in A is exhaustive iff, for each performative p(t) which is a ground instance of a schema in L(in) \ F(L), there exists at least one performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in S and ‘K & p(t)’ entails C.
4.12, Let L(S) be the set of all (not necessarily ground) performatives p(T) that are triggers in dialogue constraints:
L(S) = {p(T) | there exists ‘p(t) & C => p’(t+1)’ in S}. (Obviously, L(S) is a subset of L(in)). Then, S /= {} is covering iff for every performative p which is a ground instance of a schema in L(in), the disjunction of C’s in S(p) is ‘true’ and L(S) = L(in) \ F(L).
(Theorem 2) If the (grounded) agent program of x is covering, then x is exhaustive.
5, Agent Varieties: Concrete Examples of Agent Programs…
6, Dialogue Sequences
6.13, A sequence of dialogues s(I) wrt an intention I of an agent x with goal(G) in I is an ordered set {d1, d2, …, dn, …}, associated with a sequence of intentions I1, I2, …, In+1, … such that…
6.14, A sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is terminated iff there exists no possible request dialogue wrt In+1 that x can start.
6.15, (Success of a dialogue sequence) A terminated sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is successful if In+1 has an empty set of missing resources; it is unsuccessful otherwise.
6.16, Given an initial intention I of agent x, containing a set of missing resources Rs, the agent dialogue cycle is the following…
(Theorem 3) Given an agent x in A, if x’s agent dialogue cycle returns ‘success’ then there exists a successful dialogue sequence wrt the initial intention I of x.
(Theorem 4) Given an agent x with intention I, and a successful dialogue sequence s(I) generated by x’s dialogue cycle, if x is convergent, then the number of dialogues in s(I) is bounded by m.|Rs|, where missing(Rs) is in I and |A \ {x}| = m, A being the set of agents in the system.
7, Using Dialogue Sequences for Resource Reallocation
7.17, (Resource reallocation problem – rrp)
Given an agent system A, with each agent x in A equipped with a knowledge base K(x) and an intention I(x),
- the rrp for an agent x in A is the problem of finding a knowledge base K’(x), and an intention I’(x) (for the same goal as I(x)) such that missing({}) is in I’(x).
- the rrp for the agent system A is the problem of solving the rrp for every agent in A.
A rrp is solved if the required (sets of) knowledge base(s) and intention(s) is (are) found.
(Theorem 5) (Correctness of the agent dialogue cycle wrt the rrp) Let A be the agent system, with the agent programs of all agents in A being convergent. If all agent dialogue cycles of all agents in A return ‘success’ then the rrp for the agent system is solved.
7.18, Let A be an agent system consisting of n agents. Let R(A) be the union of all resources held by all agents in A, and R(I(A)) be the union of all resources needed to make all agents’ initial intentions I(A) executable. A is weakly complete if, given that R(I(A)) is a subset of R(A), then there exist n successful dialogue sequences, one for each agent in A, such that the intentions I’(A) returned by the sequences have the same plans as I(A) and all have an empty set of missing resources.
8, Conclusions…
“… (The proposed solution) relies upon agents agreeing solely upon a language of negotiation, while possibly adopting different negotiation policies, each corresponding to an agent variety. Agent dialogues can be connected within sequences, all aimed at achieving an individual agent’s goal. Sets of sequences aim at allowing all agents in the system to achieve their goals…”
1, Introduction
… Many approaches in the area of one-to-one negotiation are heuristic-based and, in spite of their experimentally proven effectiveness, they do not easily lend themselves to expressing theoretically provable properties. Other approaches present a good descriptive model, but fail to provide an execution model that can help to forecast the behaviour of any corresponding implemented system…
… Note that we do not make any concrete assumption on the internal structure of agents, except for requiring that they hold beliefs, goals, intentions and, possibly, resources.
2, Preliminaries
2.1, A performative or dialogue move is an instance of a schema tell(X, Y, Subject, T)… e.g. tell(a, b, request(give(nail)), 1)…
2.2, A language for negotiation L is a (possibly infinte) set of (possibly non ground) performatives. For a given L, we define two (possibly infinte) subsets of performatives, I(L) and F(L)…, called respectively initial moves and final moves. Each final move is either successful or unsuccessful.
2.3, An agent system is a finite set A, where each x in A is a ground term, representing the name of an agent, equipped with a knowledge base K(x).
3, Dialogues
3.4, Given an agent system A, equipped with a language for negotiation L, and an agent x in A, a dialogue constraint for x is a (possibly non-ground) if-then rule of the form: p(T) & C => p’(T + 1), where… The performative p(T) is referred to as the trigger, p’(T + 1) as the next move and C as the condition of the dialogue constraint.
3.5, A dialogue between two agents x and y is a set of ground performatives, {p0, p1, p2, …}, such that… A dialogue {p0, p1, … pM)… is terminated if pM is a ground final move…
3.6, A request dialogue wrt a resource R and an intention I of agent x is a dialogue… such that…
3.7, (Types of terminated request dialogues) Let I be the intention of some agent a, and R be a missing resource in I. Let d be a terminated resource dialogue wrt R and and I, and I’ be the intention resulting from d. Then, if missing(Rs), plan(P) are in I and missing(Rs’), plan(P’) are in I’:
i) d is successful if P’ = P, Rs’ = Rs \ {R};
ii) d is conditionally or c-successful if Rs’ /= Rs and Rs’ /= Rs \ {R};
iii) d is unsuccessful if I’ = I.
Note that, in the case of c-successful dialogues, typically, but not always, the agent’s plan will change (P’ /= P).
3.8, An agent x in A is convergent iff, for every terminated request dialogue of x, wrt some resource R and some intention I, the cost of the returned intention I’ is not higher than the cost of I. The cost of an intention can be defined as the number of missing resources in the intention.
4, Properties of Agent Programs
4.9, An agent x in A is deterministic iff, for each performative p(t) which is a ground instance of a schema in L(in), there exists at most one performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in the agent program S and ‘K & p(t)’ entails C.
4.10, An agent program S is non-overlapping iff for each performative p which is a ground instance of a schema in L(in), for each C, C’in S(p) such that C /= C’, then C ^ C’ = false.
(Theorem 1) If the (grounded) agent program of x is non-overlapping, then x is deterministic.
4.11, An agent x in A is exhaustive iff, for each performative p(t) which is a ground instance of a schema in L(in) \ F(L), there exists at least one performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in S and ‘K & p(t)’ entails C.
4.12, Let L(S) be the set of all (not necessarily ground) performatives p(T) that are triggers in dialogue constraints:
L(S) = {p(T) | there exists ‘p(t) & C => p’(t+1)’ in S}. (Obviously, L(S) is a subset of L(in)). Then, S /= {} is covering iff for every performative p which is a ground instance of a schema in L(in), the disjunction of C’s in S(p) is ‘true’ and L(S) = L(in) \ F(L).
(Theorem 2) If the (grounded) agent program of x is covering, then x is exhaustive.
5, Agent Varieties: Concrete Examples of Agent Programs…
6, Dialogue Sequences
6.13, A sequence of dialogues s(I) wrt an intention I of an agent x with goal(G) in I is an ordered set {d1, d2, …, dn, …}, associated with a sequence of intentions I1, I2, …, In+1, … such that…
6.14, A sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is terminated iff there exists no possible request dialogue wrt In+1 that x can start.
6.15, (Success of a dialogue sequence) A terminated sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is successful if In+1 has an empty set of missing resources; it is unsuccessful otherwise.
6.16, Given an initial intention I of agent x, containing a set of missing resources Rs, the agent dialogue cycle is the following…
(Theorem 3) Given an agent x in A, if x’s agent dialogue cycle returns ‘success’ then there exists a successful dialogue sequence wrt the initial intention I of x.
(Theorem 4) Given an agent x with intention I, and a successful dialogue sequence s(I) generated by x’s dialogue cycle, if x is convergent, then the number of dialogues in s(I) is bounded by m.|Rs|, where missing(Rs) is in I and |A \ {x}| = m, A being the set of agents in the system.
7, Using Dialogue Sequences for Resource Reallocation
7.17, (Resource reallocation problem – rrp)
Given an agent system A, with each agent x in A equipped with a knowledge base K(x) and an intention I(x),
- the rrp for an agent x in A is the problem of finding a knowledge base K’(x), and an intention I’(x) (for the same goal as I(x)) such that missing({}) is in I’(x).
- the rrp for the agent system A is the problem of solving the rrp for every agent in A.
A rrp is solved if the required (sets of) knowledge base(s) and intention(s) is (are) found.
(Theorem 5) (Correctness of the agent dialogue cycle wrt the rrp) Let A be the agent system, with the agent programs of all agents in A being convergent. If all agent dialogue cycles of all agents in A return ‘success’ then the rrp for the agent system is solved.
7.18, Let A be an agent system consisting of n agents. Let R(A) be the union of all resources held by all agents in A, and R(I(A)) be the union of all resources needed to make all agents’ initial intentions I(A) executable. A is weakly complete if, given that R(I(A)) is a subset of R(A), then there exist n successful dialogue sequences, one for each agent in A, such that the intentions I’(A) returned by the sequences have the same plans as I(A) and all have an empty set of missing resources.
8, Conclusions…
Subscribe to:
Posts (Atom)