程序代写代做代考 algorithm Java AI go data structure Lecture 4: Practical Reasoning

Lecture 4: Practical Reasoning
Professor Michael Luck michael.luck@kcl.ac.uk

Practical Reasoning
• Practical reasoning is reasoning directed towards
actions — the process of figuring out what to do:
• “Practical reasoning is a matter of weighing conflicting considerations for and against competing options, where the relevant considerations are provided by what the agent desires/values/cares about and what the agent believes.” (Bratman)
• Practical reasoning is distinguished from theoretical reasoning – theoretical reasoning is directed towards beliefs
4
https://nms.kcl.ac.uk/michael.luck/

Practical Reasoning
• Human practical reasoning consists of two activities:
• deliberation
deciding what state of affairs we want to achieve
• means-ends reasoning
deciding how to achieve these states of affairs
• The outputs of deliberation are intentions
5
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Intentions pose problems for agents, who need to determine ways of achieving them.
If I have an intention to φ, you would expect me to devote resources to deciding how to bring about φ.
6
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Agents track the success of their intentions, and are inclined to try again if their attempts fail.
If an agent’s first attempt to achieve φ fails, then all other things being equal, it will try an alternative plan to achieve φ.
7
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Intentions provide a “filter” for adopting other intentions, which must not conflict.
If I have an intention to φ, you would not expect me to adopt an intention ψ such that φ and ψ are mutually exclusive.
Helps to constrain space of possible intentions agent needs to consider
8
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Agents believe their intentions are possible.
That is, they believe there is at least some way that the intentions could be brought about.
• Agents do not believe they will not bring about their intentions. It would not be rational of me to adopt an intention to φ if I believed φ was not possible.
• Under certain circumstances, agents believe they will bring about their intentions.
It would not normally be rational of me to believe that I would bring my intentions about; intentions can fail.
Moreover, it does not make sense that if I believe φ is inevitable that I would adopt it as an intention.
9
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Agents need not intend all the expected side effects of their intentions.
If I believe φ→ψ and I intend that φ, I do not necessarily intend ψ also. (Intentions are not closed under implication.)
This last problem is known as the side effect or package deal problem. I may believe that going to the dentist involves pain, and I may also intend to go to the dentist — but this does not imply that I intend to suffer pain!
10
https://nms.kcl.ac.uk/michael.luck/

Intentions in Practical Reasoning
• Notice that intentions are much stronger than mere desires:
“My desire to play basketball this afternoon is merely a potential influencer of my conduct this afternoon. It must
vie with my other relevant desires [. . . ] before it is settled what I will do. In contrast, once I intend to play basketball this afternoon, the matter is settled: I normally need not continue to weigh the pros and cons. When the afternoon arrives, I will normally just proceed to execute my intentions.” (Bratman, 1990)
11
https://nms.kcl.ac.uk/michael.luck/

Practical Reasoning
• Human practical reasoning consists of two activities:
• Deliberation
• Deciding what state of affairs we want to achieve • Outputs are intentions
• Means-ends reasoning
• Deciding how to achieve these states of affairs
• Outputs are plans
12
https://nms.kcl.ac.uk/michael.luck/

goal/ intention/ task
state of possible environment action
planner plan to achieve goal
13
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• A first pass at an implementation of a practical reasoning agent:
Agent Control Loop Version 1
1. while true
2. observe the world;
3. update internal world model;
4. deliberate about what intention to achieve next;
5. use means-ends reasoning to get a plan for the intention;
6. execute the plan
7. end while
• (We will not be concerned with stages (2) or (3))
14
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Problem: deliberation and means-ends reasoning processes are not instantaneous.
They have a time cost.
• Suppose the agent starts deliberating at t0, begins means-ends reasoning at t1, and begins executing the plan at time t2. Time to deliberate is
tdeliberate = t1 – t0
• and time for means-ends reasoning is tme =t2 –t1
15
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Further suppose that deliberation is optimal in that if it selects some intention to achieve, then this is the best thing for the agent. (Maximizes expected utility.)
• So at time t1, the agent has selected an intention to achieve that would have been optimal if it had been achieved at t0.
But unless tdeliberate is vanishingly small, then the agent runs the risk that the intention selected is no longer optimal by the time the agent has fixed upon it.
• This is calculative rationality.
• Deliberation is only half of the problem: the agent still has to determine how to achieve the intention.
16
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• So, this agent will have overall optimal behavior in the following circumstances:
• When deliberation and means-ends reasoning take a vanishingly small amount of time; or
• When the world is guaranteed to remain static while the agent is deliberating and performing means-ends reasoning, so that the assumptions upon which the choice of intention to achieve and plan to achieve the intention remain valid until the agent has completed deliberation and means-ends reasoning; or
• When an intention that is optimal when achieved at time t0 (the time at which the world is observed) is guaranteed to remain optimal until time t2 (the time at which the agent has found a course of action to achieve the intention).
17
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
18
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Assign B as the initial beliefs
19
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Observe the world to get percept p
20
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Apply belief revision function to current beliefs and percept p to generate new beliefs
21
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Apply deliberate function to current beliefs to generate intentions
22
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Apply plan function to current beliefs B and intentions I to return a plan pi
23
https://nms.kcl.ac.uk/michael.luck/

Implementing Practical Reasoning Agents
• Let’s make the algorithm more formal:
Execute plan pi
24
https://nms.kcl.ac.uk/michael.luck/

Deliberation
• How does an agent deliberate?
• begin by trying to understand what the options
available to you are
• choose between them, and commit to some
• Chosen options are then intentions
25
https://nms.kcl.ac.uk/michael.luck/

Deliberation
• The deliberate function can be decomposed into two distinct functional components:
• option generation
in which the agent generates a set of possible alternatives; Represent option generation via a function, options, which takes the agent’s current beliefs and current intentions, and from them determines a set of options (= desires)
• filtering
in which the agent chooses between competing alternatives, and commits to achieving them.
In order to select between competing options, an agent uses a filter function.
26
https://nms.kcl.ac.uk/michael.luck/

Deliberation
27
https://nms.kcl.ac.uk/michael.luck/

Deliberation
Apply options function to current beliefs and intentions to generate new desires D
28
https://nms.kcl.ac.uk/michael.luck/

Deliberation
Apply filter function to current beliefs, desires and intentions to generate new intentions I
29
https://nms.kcl.ac.uk/michael.luck/

Deliberation
30
https://nms.kcl.ac.uk/michael.luck/

Commitment Strategies
“Some time in the not-so-distant future, you are having trouble with your new household robot. You say “Willie, bring me a beer.” The robot replies “OK boss.” Twenty minutes later, you screech “Willie, why didn’t you bring me that beer?” It answers “Well, I intended to get you the beer, but I decided to do something else.” Miffed, you send the wise guy back to the manufacturer, complaining about a lack of commitment. After retrofitting, Willie is returned, marked “Model C: The Committed Assistant.” Again, you ask Willie to bring you a beer. Again, it accedes, replying “Sure thing.” Then you ask: “What kind of beer did you buy?” It answers: “Genessee.” You say “Never mind.” One minute later, Willie trundles over with a Genessee in its gripper. This time, you angrily return Willie for overcommitment. After still more tinkering, the manufacturer sends Willie back, promising no more problems with its commitments. So, being a somewhat trusting customer, you accept the rascal back into your household, but as a test, you ask it to bring you your last beer. Willie again accedes, saying “Yes, Sir.” (Its attitude problem seems to have been fixed.) The robot gets the beer and starts towards you. As it approaches, it lifts its arm, wheels around, deliberately smashes the bottle, and trundles off. Back at the plant, when interrogated by customer service as to why it had abandoned its commitments, the robot replies that according to its specifications, it kept its commitments as long as required — commitments must be dropped when fulfilled or impossible to achieve. By smashing the bottle, the commitment became unachievable.”
31
https://nms.kcl.ac.uk/michael.luck/

Commitment Strategies
• The following commitment strategies are commonly discussed in the literature of rational agents:
• Blind commitment
A blindly committed agent will continue to maintain an intention until it believes the intention has actually been achieved. Blind commitment is also sometimes referred to as fanatical commitment.
• Single-minded commitment
A single-minded agent will continue to maintain an intention until it believes that either the intention has been achieved, or else that it is no longer possible to achieve the intention.
• Open-minded commitment
An open-minded agent will maintain an intention as long as it is still believed possible.
32
https://nms.kcl.ac.uk/michael.luck/

Commitment Strategies
• An agent has commitment both to ends (i.e., the wishes to bring about), and means (i.e., the mechanism via which the agent wishes to achieve the state of affairs)
• Currently, our agent control loop is overcommitted, both to means and ends Modification: replan if ever a plan goes wrong
33
https://nms.kcl.ac.uk/michael.luck/

34
https://nms.kcl.ac.uk/michael.luck/

While pi is not an empty plan
35
https://nms.kcl.ac.uk/michael.luck/

Action 1 } Action 2 Action 3

Action n
Head
Tail
https://nms.kcl.ac.uk/michael.luck/

Set alpha as the head of (which is the first action in) the plan pi
37
https://nms.kcl.ac.uk/michael.luck/

Execute action alpha
38
https://nms.kcl.ac.uk/michael.luck/

Update the plan so that it is now the tail of the original plan (so, remove alpha from the start of it)
39
https://nms.kcl.ac.uk/michael.luck/

Check the environment again
40
https://nms.kcl.ac.uk/michael.luck/

Revise the beliefs again based on the input from the environment
41
https://nms.kcl.ac.uk/michael.luck/

Check whether the plan still makes sense to achieve the intention given the new beliefs
42
https://nms.kcl.ac.uk/michael.luck/

If not, make a new plan based on the updated beliefs
43
https://nms.kcl.ac.uk/michael.luck/

Commitment Strategies
• Still overcommitted to intentions: Never stops to consider whether or not its intentions are appropriate
• Modification: stop to determine whether intentions have succeeded or whether they are impossible: (Single-minded commitment – maintain an intention until it believes that either the intention has been achieved or that it is no longer possible to achieve the intention)
44
https://nms.kcl.ac.uk/michael.luck/

45
https://nms.kcl.ac.uk/michael.luck/

Stop performing actions if believe intentions already achieved
46
https://nms.kcl.ac.uk/michael.luck/

… or impossible
47
https://nms.kcl.ac.uk/michael.luck/

Intention Reconsideration
• Our agent gets to reconsider its intentions once every time around the outer control loop, i.e., when:
• it has completely executed a plan to achieve its current intentions; or
• it believes it has achieved its current intentions; or
• it believes its current intentions are no longer possible.
• This is limited in the way that it permits an agent to reconsider its intentions
• Modification: Reconsider intentions after executing every action (open minded)
48
https://nms.kcl.ac.uk/michael.luck/

49
https://nms.kcl.ac.uk/michael.luck/

Now reconsiders desires after every action performed
50
https://nms.kcl.ac.uk/michael.luck/

… and intentions
51
https://nms.kcl.ac.uk/michael.luck/

Intention Reconsideration
• But intention reconsideration is costly! A dilemma:
• an agent that does not stop to reconsider its intentions sufficiently often will continue attempting to achieve its intentions
even after it is clear that they cannot be achieved, or that there is no longer any reason for achieving them
• an agent that constantly reconsiders its attentions may spend insufficient time actually working to achieve them, and hence runs the risk of never actually achieving them
• Solution: incorporate an explicit meta-level control component, that decides whether or not to reconsider
52
https://nms.kcl.ac.uk/michael.luck/

53
https://nms.kcl.ac.uk/michael.luck/

Evaluates to true if apropriate to reconsider intentions given beliefs B and intentions I, false otherwise
54
https://nms.kcl.ac.uk/michael.luck/

Possible Interactions
• The possible interactions between meta-level control and deliberation are:
55
https://nms.kcl.ac.uk/michael.luck/

Intention Reconsideration
• In situation (1), the agent did not choose to deliberate, and as consequence, did not choose to change intentions. Moreover, if it had chosen to deliberate, it would not have changed intentions. In this situation, the reconsider(…) function is behaving optimally.
• In situation (2), the agent did not choose to deliberate, but if it had done so, it would have changed intentions. In this situation, the reconsider(…) function is not behaving optimally.
• In situation (3), the agent chose to deliberate, but did not change intentions. In this situation, the reconsider(…) function is not behaving optimally.
• In situation (4), the agent chose to deliberate, and did change intentions. In this situation, the reconsider(…) function is behaving optimally.
• An important assumption: cost of reconsider(…) is much less than the cost of the deliberation process itself.
56
https://nms.kcl.ac.uk/michael.luck/

Optimal Intention Reconsideration
• Kinny and Georgeff experimentally investigated effectiveness of intention reconsideration strategies
• Two different types of reconsideration strategy were used:
• bold agents
never pause to reconsider intentions, and
• cautious agents
stop to reconsider after every action
• Dynamism in the environment is represented by the rate of world change, γ
57
https://nms.kcl.ac.uk/michael.luck/

Optimal Intention Reconsideration
• Results (not surprising):
• If γ is low (i.e., the environment does not change quickly), then bold agents do well compared to cautious ones. This is because cautious ones waste time reconsidering their commitments while bold agents are busy working towards — and achieving — their intentions.
• If γ is high (i.e., the environment changes frequently), then cautious agents tend to outperform bold agents. This is because they are able to recognize when intentions are doomed, and also to take advantage of serendipitous situations and new opportunities when they arise.
58
https://nms.kcl.ac.uk/michael.luck/

Implemented BDI Agents: IRMA
• IRMA – Intelligent Resource-bounded Machine Architecture – Bratman, Israel, Pollack
• IRMA has four key symbolic data structures: • a plan library
• explicit representations of
• beliefs: information available to the agent — may be
represented symbolically, but may be simple variables
• desires: those things the agent would like to make true — think of desires as tasks that the agent has been allocated; in humans, not necessarily logically consistent, but our agents will be! (goals)
• intentions: desires that the agent has chosen and committed to
59
https://nms.kcl.ac.uk/michael.luck/

IRMA
• Additionally, the architecture has:
• a reasoner for reasoning about the world; an
inference engine
• a means-ends analyzer determines which plans might be used to achieve intentions
• an opportunity analyzer monitors the environment, and as a result of changes, generates new options
• a filtering process determines which options are compatible with current intentions
• a deliberation process responsible for deciding upon the ‘best’ intentions to adopt
60
https://nms.kcl.ac.uk/michael.luck/

Implemented BDI Agents: PRS
• Another BDI-based agent architecture: the PRS – Procedural Reasoning System (Georgeff, Lansky)
• In the PRS, each agent is equipped with a plan library, representing that agent’s procedural knowledge: knowledge about the mechanisms that can be used by the agent in order to realize its intentions
• The options available to an agent are directly determined by the plans an agent has: an agent with no plans has no options
• In addition, PRS agents have explicit representations of beliefs, desires, and intentions, as above
61
https://nms.kcl.ac.uk/michael.luck/

PRS
62
https://nms.kcl.ac.uk/michael.luck/

PRS Architecture
• In general, an agent cannot achieve all its desires. • Must therefore fix upon a subset.
• Commit resources to achieving them.
• Chosen desires are intentions.
• Agents continue to try to achieve intentions until either
• believe intention is satisfied, or
• believe intention is no longer achievable.
63
https://nms.kcl.ac.uk/michael.luck/

PRS Plans
• BDI model is operationalised in PRS/dMARS agents by plans.
• Plans are recipes for courses of action. • Each plan contains:
• invocation condition: circumstances for plan consideration;
• context: circumstances for successful plan execution;
• maintenance condition: must be true while plan is executing, in order for it to succeed; and
• body: course of action, consisting of both goals and actions.
64
https://nms.kcl.ac.uk/michael.luck/

PRS
• Agents respond to internal and external events by selecting an appropriate plan in the plan base whose invocation condition and context are both true
• When a plan is adopted it becomes an intention
• This intention becomes part of the agent’s intention structure.
65
https://nms.kcl.ac.uk/michael.luck/

PRS Plan Structure
Start ?g1
P1
?g2 (otherwise)
P2
Plan
Invocation
Context
Body
?g3
P3
End1
?g4
*a1 End3
Maintenance
Success
!g1
P4
End2
!g2
Failure
66
https://nms.kcl.ac.uk/michael.luck/

More simply, a plan looks like…
Action 1 Goal 1 Action 2 Action 3 Goal 2 … Action n
https://nms.kcl.ac.uk/michael.luck/

PRS Operation 1
• Observe world and agent state, and update event queue to reflect observed events.
• Generate new possible goals (tasks), by finding plans whose trigger matches event queue.
• Select matching plan for execution (an intended means).
68
https://nms.kcl.ac.uk/michael.luck/

PRS Operation 2
• Push the intended means onto the appropriate intention stack in the current set.
• Select an intention stack and execute next step of its topmost plan (intended means):
• if the step is an action, perform it;
• if it is a subgoal, post it on the event queue.
Intention
Plan Instance(m)
Plan Instance (m-1)
Plan Instance(1)
69
https://nms.kcl.ac.uk/michael.luck/

PRS Operation 3
Plan Library
Intention
Event Queue
Plan Instance(m)
Plan Instance(m)
Plan Instance(m-1)
Plan Instance(m-1)
Plan Instance(1)
Intention
Plan Instance(1)
70
https://nms.kcl.ac.uk/michael.luck/

Jason
• Jason implements the operational semantics of a variant of AgentSpeak
• Various extensions aimed at a more practical programming language
• Platform for developing multi-agent systems
• Developed by Jomi F. Hübner and Rafael H.
Bordini
• Jason is available Open Source under GNU LGPL at: http://jason.sf.net
71
https://nms.kcl.ac.uk/michael.luck/

BDI4 JADE
• http://www.inf.ufrgs.br/prosoft/bdi4jade/Implementation of the BDI architecture
• Highlights
• JADE extension • “Pure” Java
• Capabilities
• Java generics for beliefs
• Plan bodies as instances of JADE behaviors
• Future extensions • Persistent beliefs
• Control of intention/goal owners • Indexes for plan libraries
72
https://nms.kcl.ac.uk/michael.luck/

3APL
• 3APL is a programming language for implementing cognitive agents
• It provides programming constructs for implementing
• agents’ beliefs
• goals
• basic capabilities (such as belief updates, external actions, or communication actions)
• set of practical reasoning rules through which agents’ goals can be updated or revised.
• http://www.cs.uu.nl/3apl/
73
https://nms.kcl.ac.uk/michael.luck/

Hybrid Architectures
• Many researchers have argued that neither a completely deliberative nor completely reactive approach is suitable for building agents
• They have suggested using hybrid systems, which attempt to marry classical and alternative approaches
• An obvious approach is to build an agent out of two (or more) subsystems:
• a deliberative one, containing a symbolic world model, which develops plans and makes decisions in the way proposed by symbolic AI
• a reactive one, which is capable of reacting to events without complex reasoning
74
www.inf.kcl.ac.uk/staff/mml

Agents: Technologies, Design & Simulation
83
www.dcs.kcl.ac.uk/staff/mml

Agents as Design
• Agent oriented software engineering • Agent architectures
• Mobile agents
• Agent infrastructure
• Electronic institutions
84
www.dcs.kcl.ac.uk/staff/mml

Agent Technologies
• Multi-agent planning
• Agent communication languages
• Coordination mechanisms
• Matchmaking architectures
• Information agents and basic ontologies • Auction mechanism design
• Negotiation strategies
• Learning
86
www.dcs.kcl.ac.uk/staff/mml

www.dcs.kcl.ac.uk/staff/mml

Agents as Simulation
• For representing complex and dynamic real- world environments.
• simulation of economies, societies and biological environments
• To provide answers to complex physical or social problems otherwise unobtainable
• modelling of the impact of climate change on biological populations
• modelling impact of public policy options on social or economic behaviour
94
www.dcs.kcl.ac.uk/staff/mml

Agents as Simulation
• Agent-based simulation:
• social structures and institutions to develop plausible explanations of observed phenomena to inform policy or managerial decisions
• physical systems, including intelligent buildings, traffic systems and biological populations
• software systems including eCommerce and information management systems
• Multi-agent simulation models thus effectively provide a new set of tools for the management of complex adaptive systems
95
www.dcs.kcl.ac.uk/staff/mml

www.dcs.kcl.ac.uk/staff/mml