CS代考 1. Introduction and JUnit – cscodehelp代写
1. Introduction and JUnit
Planning
1
To exhibit intelligent (rather than random or else rigid) behavior, agents must plan.
1
Examples: Plan …
2
… a wedding
… a trip
… a project
… a move
between apartments
between houses
from one business location to another
… a robot’s course of action
Robots, and agents in general, are much more effective if they have a plan rather that following a purely greedy algorithm.
2
Planning: Learning Objectives
Recognize actions applicable in states
Plan forward or backward
Apply to programming
3
By the end of this module, you will be able to observe states as the mode for a plan, distinguish the creation of a plan by beginning with the initial state, or else with a final desired state.
The ideas are applicable to programs, which are a kind of plan.
3
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
In this section we discover what’s involved in planning.
Example: Outcome
Consider the problem of finding a way to manufacture an item, such as the one shown made from a single flat piece of metal. This is backward planning.
The problem of assembling items (creating molecules, packing a box etc.) is similar.
5
Example: Plan Folding Operations
The figure shows a way to do this. The question is: can this plan be arrived at through an (AI planning) algorithm. The advantages include faster manufacturing, less waste, and labor saving.
6
Example Source
The figure shows an abstract of this particular paper.
7
Planning for Extraterrestrials
8
Planning is also required for the increasing autonomy of vehicles, just as humans exercise as much foresight as they can in operating them. This is especially true of extraterrestrial vehicles, which cannot be controlled in real time.
8
What is a Plan?
9
A sequence of actions.
e.g., to get to NYC
Obtain from action inventory indexed by state.
the initial state
e.g., (agent is) in JP, Boston or agent1 in …. and agent2 in …
…
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
9
What is a Plan?
10
A sequence of actions.
e.g., to get to NYC
Obtain from action inventory indexed by state.
the initial state
e.g., (agent is) in JP, Boston or agent1 in …. and agent2 in …
the actions available in a state
the result of applying an action
the goal test
(agent is) in NYC?
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
10
States
Source: Russell and Norvig
Each state is represented as a conjunction of “fluents”: ground, functionless atoms.
For example,
Poor ∧ Unknown,
In_JP ∧ Have_car
In general, a state is defined by values of variables. For example, the state “Late for Work” is defined by t > K where t is the variable time to get to work and K is minimum time to get to work without being late. In this example, the variable (t) is continuous.
Russell and Norvig simplify this by considering only a discrete variable (sometimes called state)—that can only take a set of values from a finite set. These values are called fluents, and are given names. An example is
state = {Poor, Unknown}
11
A State Example …
Source: Russell and Norvig
The simplified version of states are often expressed in planning as predicates, such as those in the figure. This is like a variable At, whose values are pairs.
12
Closed World Assumption
13
Anything not provable is assumed to be false.
Example…
In AI, we often choose to make the closed world assumption. Think of it as ultra-science-based: assume that anything unprovbable within a system is actually false within that system.
13
Apply Closed World Assumption
14
Anything not provable is assumed to be false.
Example: Plan a driving vacation between Denver and LA.
If steep roads are en route can’t be established from the given environments,
assume that there are none.
The CWA is by no means foolproof, as the example in the figure suggests.
14
Action Schemas
15
A set of actions may be represented by a single action schema.
…
Source: Russell and Norvig
So far, our discussion of planning has involved simple states (e.g., At(Truck, Melbourne)) and actions. This is addressed with schemas—set of actions.
15
Action Schemas
16
A set of actions may be represented by a single action schema.
Lifts level of reasoning from propositional logic to first-order logic.
For example, …
Source: Russell and Norvig
So far, our discussion of planning has involved simple states (e.g., At(Truck, Melbourne)) and actions. This is addressed with schemas—set of actions.
16
Action Schemas
17
A set of actions may be represented by a single action schema.
Lifts level of reasoning from propositional logic to first-order logic.
For example, an action schema for flying a plane from one location to another:
Action(
Fly(p, from, to),
PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
EFFECT: ¬At(p, from) ∧ At(p, to)
)
Source: Russell and tell what the effects (the postconditions) are for an action—under what preconditions.
17
Recall a Plan
18
A sequence of actions, given …
the initial state
the actions available in a state
the result of applying an action
the goal test
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
18
Plan Example: Spare Tire
19
Source: Russell and
Consider the goal At(Spare, Axle) (the spare tire is installed), given Tire(Flat) (the regular tire is flat) etc. What plan (sequence of schemas) accomplishes this?
We show the beginning of the first schema of such as sequence: Action(PutOn(t, Axle) …
19
Plan Example: Spare Tire
20
Source: Russell and Norvig
The sequence of actions is Remove(Tire, Axle), PutOn(Spare, Axle), LeaveOvernight, and each is defined above with their pre- and postconditions. Notice that we can’t assume any common sense: for example, the logic has to be explicit, in the last Action, that the Spare is not at specific locations—other than the axle.
20
21
(Classical) Blocks World
Source: Russell and Norvig
A simple example shows the principles: such is the purpose of the blocks shown in the figure.
21
22
Blocks World
Source: Russell and Norvig
The figure shows the totality of initial conditions.
22
23
Blocks World
Source: Russell and Norvig
The Action needed to accomplish the goal are instances of Move, as defined in the figure.
23
Plan Example
24
There is cargo at San Francisco, which we want at JFK.
There is cargo at JFK which we want at San Francisco.
We have a plane at San Francisco and one at JFK.
Develop a plan (at the level of load/unload/fly).
WHAT PDDL* INPUT DOES THIS TRANSLATE TO?
* Planning Domain Definition Language
The figure poses a practical planning example. It refers to PDDL (the Planning Domain Definition Language), which Russell and Norvig translate into logic notation as in the figures.
24
PDDL
25
“The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages.” (Wikipedia)
Can specify
the initial state
the actions available in a state
the result of applying an action
the goal test
https://github.com/pellierd/pddl4j/wiki/A-tutorial-to-start-with-PDDL
An available action schema
The figure specifies the initial conditions, the goal, and the first action of the plan.
26
The plan is completed in this figure.
27
PDDL (Code) Examples
28
https://github.com/pellierd/pddl4j/wiki/Logistics:-a-simple-running-example
(logistic application)
http://kcl-planning.github.io/ROSPlan//demos/robot_pages/squirrel.html
(demo)
https://github.com/pellierd/pddl4j/wiki/Logistics:-a-simple-running-example
(code but no demo)
The figure lists a PDDL de mo, code base, and (essentially) a marketing example. The syntax of PDDL is rooted in LISP.
28
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
In this section we compare the two principal poles of planning: forwards from the initial conditions, and backward from the goal.
Forward Planning
30
Source: Russell and Norvig
Start with initial state
In (pure, un-pruned) forward planning, we generate all possible permissible actions until the goal is encountered. A beginning is shown in the figure.
30
Backwards Planning
31
Source: Russell and Norvig
Start with goal state
In backward planning, we begin with the goal, and generate all actions that result in that goal, noting their preconditions, which become a new set of goals on which to (recursively) apply the same process. In principle, this is performed until the given initial conditions are obtained.
31
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which …
* Weakest Preconditions and Cumulative Subgoal Fulfillment by . Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
(Often … CG1 = OG1, CG2 = OG2, …, CGn = Ogn)
A computer program is analogous to a plan. In the Cumulative Goal Fulfillment approach to programming, we fulfill a set of goals (CG1, CG12, … CGn, say) which are at least as strong as the set of postconditions. We write code that fulfills the first goal; then code that fulfills the second, but which maintains the validity of the first etc.).
32
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which are cumulative i.e.,
fulfilling CGi maintains CG1CG2 … CGi-1
Example: Towers of Hanoi: CG1 = “??”
Example: Repair flat: CG1 = “??”
* Weakest preconditions and cumulative subgoal fulfillment by .Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
The property of fulfilling goals while maintaining prior ones is “cumulative.” Cumulative goals are helpful in being specific about the purpose of each block of code.
33
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which are cumulative i.e.,
fulfilling CGi maintains CG1CG2 … CGi-1
Example: Towers of Hanoi: CG1 = “Largest on target”
Example: Repair flat: CG1 = “New inner tube on rim”
* Weakest preconditions and cumulative subgoal fulfillment by .Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
There are techniques for identifying goals, and the code (the actions in planning lingo) that fulfills them. But they are arrived at by practice, and selected from a very wide set of legal programming constructs whereas in planning, the set of actions is very limited, and we can often use heuristics to identify potentially successful ones.
34
15-Puzzle Postcondition(s)
A conjunction of fluents (maybe location_of_1, location_of_2, …
Which selection is useful?
To solve the famous Fifteen Puzzle, for example, what would be a useful cumulative goal for the plan? What fluents or predicates?
35
15-Puzzle Cumulative Goal # 1
. Braude “Dijkstra’s Counting Arguments, Puzzles, and Cumulative Subgoal Fulfillment”, Computer Science and Education in Computer Science 9/2013 Issue No: 1 pp 41-45 https://www.ceeol.com/search/article-detail?id=465085
A useful fluent to take as a goal:
A useful—and, it turns out—practical goal is to have the required outer ring in its required order. The point here is that there is apparently no limit on how imaginative useful goal fluents and predicates can be.
36
Unsolved … (non-final) Goal: Dad’s Puzzle
37
