Transcript Part 1 Search and Planning

Sessions 1 & 2
Introduction to AI;
Planning & Search
CSE 592
Applications of Artificial
Intelligence
Henry Kautz
Winter 2003
What is Intelligence?
What is Artificial Intelligence?
What is Artificial Intelligence?
• The study of the principles by which
natural or artificial machines
manipulate knowledge:
–
–
–
–
how knowledge is acquired
how goals are generated and achieved
how concepts are formed
how collaboration is achieved
. . . Exactly what the computer
provides is the ability not to be rigid
and unthinking but, rather, to behave
conditionally. That is what it means
to apply knowledge to action: It
means to let the action taken reflect
knowledge of the situation, to be
sometimes this way, sometimes that,
as appropriate. . . .
-Allen Newell
• Classical AI
Disembodied Intelligence
• Autonomous Systems
Embodied Intelligence
Classical AI
• The principles of intelligence are separate
from any hardware / software / wetware
implementation
– logical reasoning
– probabilistic reasoning
– strategic reasoning
– diagnostic reasoning
• Look for these principles by studying how
to perform tasks that require intelligence
Success Story: Medical Expert
Systems
• Mycin (1980)
– Expert level performance in diagnosis of
blood infections
• Today: 1,000’s of systems
– Everything from diagnosing cancer to
designing dentures
– Often outperform doctors in clinical trials
– Major hurdle today – non-expert part –
doctor/machine interaction
Success Story:
Chess
I could feel – I
could smell – a
new kind of
intelligence
across the table
- Kasparov
•Examines 5 billion positions /
second
•Intelligent behavior emerges
from brute-force search
Autonomous Systems
• In the 1990’s there was a growing concern
that work in classical AI ignored crucial
scientific questions:
– How do we integrate the components of
intelligence (e.g. learning & planning)?
– How does perception interact with
reasoning?
– How does the demand for real-time
performance in a complex, changing
environment affect the architecture of
intelligence?
• Provide a standard
problem where a wide
range of technologies
can be integrated and
examined
• By 2050, develop a team
of fully autonomous
humanoid robots that
can win against the
human world champion
team in soccer.
Started: January 1996
Launch: October 15th, 1998
Experiment: May 17-21
courtesy JPL
Speed & Capacity
Not Speed Alone…
• Speech Recognition
• “Word spotting” feasible today
• Continuous speech – rapid progress
• Turns out that “low level” signal not as
ambiguous as we once thought
• Translation / Interpretation / Question-answering
• Very limited progress
The spirit is willing but the flesh is weak. (English)
The vodka is good but the meat is rotten. (Russian)
Varieties of Knowledge
What kinds of knowledge required to understand –
• Time flies like an arrow.
• Fruit flies like a banana.
• Fruit flies like a rock.
1940's - 1960's: Artificial neural networks
• McCulloch & Pitts 1943
1950's - 1960's: Symbolic information processing
• General Problem Solver – Simon & Newell
• "Weak methods“ for search and learning
• 1969 - Minsky's Perceptrons
1940’s – 1970’s: Control theory for adaptive (learning) systems
• USSR – Cybernetics – Norbert Weiner
• Japan – Fuzzy logic
1970's – 1980’s: Expert systems
• “Knowledge is power" – Ed Feigenbaum
• Logical knowledge representation
• AI Boom
Historic
Perspective
1985 – 2000: A million flowers bloom
•
•
•
•
Resurgence of neural nets – backpropagation
Control theory + OR + Pavlovian conditioning = reinforcement learning
Probabilistic knowledge representation – Bayesian Nets – Judea Pearl
Statistical machine learning
2000’s: Towards a grand unification
• Unification of neural, statistical, and symbolic machine learning
• Unification of logic and probabilistic KR
• Autonomous systems
… In sum, technology can be
controlled especially if it is
saturated with intelligence to watch
over how it goes, to keep accounts,
to prevent errors, and to provide
wisdom to each decision.
-Allen Newell
Course Mechanics
Topics
•
•
•
•
•
•
•
•
•
What is AI?
Search, Planning, and Satisfiability
Bayesian Networks
Statistical Natural Language Processing
Decision Trees and Neural Networks
Data Mining: Pattern Discovery in Databases
Planning under Uncertainty and Reinforcement Learning
Autonomous Systems Case Studies
Project Presentations
Assignments
• 4 homeworks
• Significant project & presentation
Information
• http://www.cs.washington.edu/education/courses/592/03wi/
Planning & Search
Search – the foundation for all work in AI
• Deduction
• Probabilistic reasoning
• Perception
• Learning
• Game playing
• Expert systems
• Planning
R&N Ch 3, 4, 5, 11
Planning
• Input
– Description of set of all possible states of the world
(in some knowledge representation language)
– Description of initial state of world
– Description of goal
– Description of available actions
• May include costs for performing actions
• Output
– Sequence of actions that convert the initial state into
one that satisfies the goal
19
– May wish to minimize length or cost of plan
Classical Planning
• Simplifying assumptions
–
–
–
–
–
Atomic time
Actions have deterministic effects
Agent knows complete initial state of the world
Agent knows the effects of all actions
States are either goal or non-goal states, rather
than numeric utilities or rewards
– Agent is sole cause of change
• All these assumptions can be relaxed, as we
will see by the end of the course…
Example:
Route
Planning
Input:
• State set
• Start state
• Goal state test
• Operators
Output:
Example: Robot Control
(Blocks World)
Input:
• State set
• Start state
• Goal state test
• Operators (and costs)
Output:
Implicitly Generated Graphs
• Planning can be viewed as finding paths in a graph, where the graph is
implicitly specified by the set of actions
• Blocks world:
How many
– vertex = relative positions of all blocks
states for K
– edge = robot arm stacks one block
blocks?
stack(blue,table)
stack(green,blue)
stack(blue,red)
stack(green,red)
stack(green,blue)
Missionaries and Cannibals
• 3 missionaries M1, M2, M3
• 3 cannibals C1, C2, C3
• Cross in a two person boat, so that
missionaries never outnumber
cannibals on either shore
• What is a state? How many states?
M1 M2 M3
C1 C2 C3
24
STRIPS Representation
• Description of initial state of world
Set of propositions that completely describes a world
{ (block a) (block b) (block c) (on-table a)
(on-table b) (clear a) (clear b) (clear c)
(arm-empty) }
• Description of goal (i.e. set of desired worlds)
Set of propositions that partially describes a world
{ (on a b) (on b c) }
• Description of available actions
How Represent Actions?
• World = set of propositions true in that world
• Actions:
– Precondition: conjunction of propositions
– Effects: propositions made true & propositions made
false (deleted from the state description)
operator: stack_B_on_R
precondition: (on B Table) (clear R)
effect: (on B R) (:not (clear R))
Action Schemata
• Compact representation of a large set of actions
(:operator pickup
:parameters ((block ?ob1))
:precondition (:and (clear ?ob1) (on-table ?ob1)
(arm-empty))
:effect (:and (:not (on-table ?ob1))
(:not (clear ?ob1))
(:not (arm-empty))
(holding ?ob1)))
Search Algorithms
Backtrack Search
1. DFS
2. BFS / Dijkstra’s Algorithm
3. Iterative Deepening
4. Best-first search
5. A*
Constraint Propagation
1. Forward Checking
2. k-Consistency
3. DPLL & Resolution
Local Search
1. Hillclimbing
2. Simulated annealing
3. Walksat
Depth First Search
• Maintain stack of nodes to visit
• Evaluation
– Complete?
Not for infinite spaces
a
– Time Complexity?
O(b^d)
b
– Space Complexity?
c
O(d)
d
e
f
g
h
Breadth First Search
• Maintain queue of nodes to visit
• Evaluation
– Complete?
Yes
a
– Time Complexity?
O(b^d)
b
– Space Complexity?
c
O(b^d)
d
e
f
g
h
Iterative Deepening Search
• DFS with limit; incrementally grow limit
• Evaluation
– Complete?
Yes
– Time Complexity?
a
O(b^d)
– Space Complexity?
b
c
O(d)
d
e
f
g
h
Dijkstra’s Shortest Path
Algorithm
• Like breadth-first search, but uses a priority queue
instead of a FIFO queue:
– Always select (expand) the vertex that has a lowest-cost
path from the initial state
• Correctly handles the case where the lowest-cost
path to a vertex is not the one with fewest edges
– Handles actions planning with costs, with same
advantages / disadvantages of BFS
Pseudocode for Dijkstra
•
•
•
•
Initialize the cost of each vertex to 
cost[s] = 0;
heap.insert(s);
While (! heap.empty())
n = heap.deleteMin()
For (each vertex a which is adjacent to n along edge e)
if (cost[n] + edge_cost[e] < cost[a]) then
cost [a] = cost[n] + edge_cost[e]
previous_on_path_to[a] = n;
if (a is in the heap) then heap.decreaseKey(a)
else heap.insert(a)
Important Features
• Once a vertex is removed from the head, the cost
of the shortest path to that node is known
• While a vertex is still in the heap, another shorter
path to it might still be found
• The shortest path itself from s to any node a can
be found by following the pointers stored in
previous_on_path_to[a]
Edsger Wybe Dijkstra
(1930-2002)
• Invented concepts of structured programming,
synchronization, weakest precondition, and semaphores
• 1972 Turing Award
• “In their capacity as a tool, computers will be but a ripple
on the surface of our culture. In their capacity as
intellectual challenge, they are without precedent in the
cultural history of mankind.”
Heuristic Search
• A heuristic is:
– Function from a state to a real number
• Low number means state is close to goal
• High number means state is far from the goal
An Easier Case
• Suppose you live in Manhattan; what do you do?
S
52nd St
G
51st St
50th St
2nd Ave
3rd Ave
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
10th Ave
Best-First Search
• The Manhattan distance ( x+  y) is an estimate
of the distance to the goal
– a heuristic value
• Best-First Search
– Order nodes in priority to minimize estimated distance
to the goal h(n)
• Compare: BFS / Dijkstra
– Order nodes in priority to minimize distance from the
start
Best First in Action
• Suppose you live in Manhattan; what do you do?
S
52nd St
G
51st St
50th St
2nd Ave
3rd Ave
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
10th Ave
Problem 1: Led Astray
• Eventually will expand vertex to get back on the
right track
S
52nd St
G
51st St
50th St
2nd Ave
3rd Ave
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
10th Ave
Problem 2: Optimality
• With Best-First Search, are you guaranteed a
shortest path is found when
– goal is first seen?
– when goal is removed from priority queue (as with
Dijkstra?)
Sub-Optimal Solution
• No! Goal is by definition at distance 0: will be
removed from priority queue immediately, even if
a shorter path exists!
(5 blocks)
52nd St
S
51st St
h=4
h=2
h=5
G
h=1
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Synergy?
• Dijkstra / Breadth First guaranteed to find optimal
solution
• Best First often visits far fewer vertices, but may
not provide optimal solution
– Can we get the best of both?
A* (“A star”)
• Order vertices in priority queue to minimize
• (distance from start) + (estimated distance to
goal)
•
•
•
•
f(n) = g(n)
+ h(n)
f(n) = priority of a node
g(n) = true distance from start
h(n) = heuristic distance to goal
Optimality
• Suppose the estimated distance (h) is
always less than or equal to the true distance to the
goal
– heuristic is a lower bound on true distance
– heuristic is admissible
• Then: when the goal is removed from the priority
queue, we are guaranteed to have found a shortest
path!
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
50th St
vertex
g(n)
h(n)
f(n)
52nd & 9th
0
5
5
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
50th St
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
51st & 9th
1
4
5
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
50th St
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
51st & 8th
2
3
5
50th & 9th
2
5
7
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
51st & 7th
3
2
5
50th & 9th
2
5
7
50th & 8th
3
4
7
50th St
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
51st & 6th
4
1
5
50th & 9th
2
5
7
50th & 8th
3
4
7
50th & 7th
4
3
7
50th St
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
51st & 5th
5
0
5
50th & 9th
2
5
7
50th & 8th
3
4
7
50th & 7th
4
3
7
50th St
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
Problem 2 Revisited
52nd
St
(5 blocks)
S
G
51st St
50th
vertex
g(n)
h(n)
f(n)
52nd & 4th
5
2
7
50th & 9th
2
5
7
50th & 8th
3
4
7
50th & 7th
4
3
7
St
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
DONE!
What Would Dijkstra Have
Done?
52nd St
(5 blocks)
S
G
51st St
50th St
49th St
48th St
4th Ave
5th Ave
6th Ave
7th Ave
8th Ave
9th Ave
47th St
Proof of A* Optimality
•
•
•
•
A* terminates when G is popped from the heap.
Suppose G is popped but the path found isn’t optimal:
priority(G) > optimal path length c
Let P be an optimal path from S to G, and let N be the last vertex on that
path that has been visited but not yet popped.
There must be such an N, otherwise the optimal path would have been
found.
priority(N) = g(N) + h(N)  c
So N should have popped before G can pop. Contradiction.
non-optimal path to G
S
portion of optimal
path found so far
G
N
undiscovered portion
of shortest path
What About Those Blocks?
• “Distance to goal” is not always physical distance
• Blocks world:
– distance = number of stacks to perform
– heuristic lower bound = number of blocks out of place
# out of place = 1, true distance to goal = 3
3-Blocks State
Space Graph
ABC
h=2
A
BC
h=1
A
CB
h=2
B
AC
h=2
B
CA
h=1
C
AB
h=3
C
BA
h=3
C
A
B
h=3
B
A
C
h=2
C
B
A
h=3
A
B
C
h=0
B
C
A
h=3
A
C
B
h=3
start
goal
3-Blocks
Best First
Solution
ABC
h=2
A
BC
h=1
A
CB
h=2
B
AC
h=2
B
CA
h=1
C
AB
h=3
C
BA
h=3
C
A
B
h=3
B
A
C
h=2
C
B
A
h=3
A
B
C
h=0
B
C
A
h=3
A
C
B
h=3
start
goal
3-Blocks BFS
Solution
ABC
h=2
expanded, but not
in solution
A
BC
h=1
A
CB
h=2
B
AC
h=2
B
CA
h=1
C
AB
h=3
C
BA
h=3
C
A
B
h=3
B
A
C
h=2
C
B
A
h=3
A
B
C
h=0
B
C
A
h=3
A
C
B
h=3
start
goal
3-Blocks A*
Solution
ABC
h=2
expanded, but not
in solution
A
BC
h=1
A
CB
h=2
B
AC
h=2
B
CA
h=1
C
AB
h=3
C
BA
h=3
C
A
B
h=3
B
A
C
h=2
C
B
A
h=3
A
B
C
h=0
B
C
A
h=3
A
C
B
h=3
start
goal
Maze Runner Demo
Other Real-World Applications
• Routing finding – computer networks, airline
route planning
• VLSI layout – cell layout and channel routing
• Production planning – “just in time” optimization
• Protein sequence alignment
• Many other “NP-Hard” problems
– A class of problems for which no exact polynomial time
algorithms exist – so heuristic search is the best we can
hope for
Importance of Heuristics
7 2
4 1
8 5
3
6
• h1 = number of tiles in the wrong place
• h2 = sum of distances of tiles from correct location
D
2
4
6
8
10
12
14
18
24
IDS
10
112
680
6384
47127
364404
3473941
A*(h1)
6
13
20
39
93
227
539
3056
39135
A*(h2)
6
12
18
25
39
73
113
363
1641
A* STRIPS Planning
• Is there some general way to automatically create a
heuristic for a given set of STRIPS operators?
1. Count number of false goal propositions in current
state
Admissible?
2. Delete all preconditions from actions, solve easier
relaxed problem (why easier?), use length
Admissible?
3. Delete negative effects from actions, solve easier
relaxed problem, use length
Admissible?
Planning as A* Search
• HSP (Geffner & Bonet 1999), introduced
admissible “ignore negative effects” heuristic
• FF (Hoffman & Nebel 2000), used a modified
non-admissible heuristic
– Often dramatically faster, but usually non-optimal
solutions found
– Best overall performance AIPS 2000 planning
competition
Search Algorithms
Backtrack Search
1. DFS
2. BFS / Dijkstra’s Algorithm
3. Iterative Deepening
4. Best-first search
5. A*
Constraint Propagation
1. Forward Checking
2. k-Consistency
3. DPLL & Resolution
Local Search
1. Hillclimbing
2. Simulated annealing
3. Walksat
Guessing versus Inference
All the search algorithms we’ve seen so far are
variations of guessing and backtracking
But we can reduce the amount of guesswork by
doing more reasoning about the
consequences of past choices
• Example: planning a trip
Idea:
• Problem solving as constraint
satisfaction
• As choices (guesses) are made,
propagate constraints
Map Coloring
CSP
• V is a set of variables v1, v2, …, vn
• D is a set of finite domains D1, D2, …, Dn
• C is a set of constraints C1, C2, …, Cm
Each constraint specifies a restriction over
joint values of a subset of the variables
E.g.:
v1 is Spain, v2 is France,
v3 is Germany, …
Di = { Red, Blue, Green} for all i
For each adjacent vi, vj
there is a constraint Ck
(vi,vj)  { (R,G), (R,B), (G,R), (G,B), (B,R), (B,G) }
Variations
• Find a solution that satisfies all constraints
• Find all solutions
• Find a “tightest form” for each constraint
(v1,v2)  { (R,G), (R,B), (G,R), (G,B), (B,R), (B,G) }

(v1,v2)  { (R,G), (R,B), (B,G) }
• Find a solution that minimizes some
additional objective function
Chinese Dinner Constraint Network
Must be
Hot&Sour
Soup
Appetizer
Chicken
Dish
No
Peanuts
Vegetable
No
Peanuts
Total Cost
< $30
Pork Dish
Not Both
Spicy
Seafood
Rice
Not
Chow Mein
Exploiting CSP Structure
Interleave inference and guessing
• At each internal node:
• Select unassigned variable
• Select a value in domain
• Backtracking: try another value
– Branching factor?
• At each node:
• Propagate Constraints
Running Example: 4 Queens
Constraints:
Variables:
Q1  {1,2,3,4}
Q2  {1,2,3,4}
Q3  {1,2,3,4}
Q3  {1,2,3,4}
Q
Q
Q
Q
Q1
Q2
1
3
1
4
2
4
3
1
4
1
4
2
Constraint Checking
x
Q
Q
Q x
x
x
x
Q x
Q x
x
Q
Q
Q
x
x
x
x
x
x
x
Q
x
Q x
Q x
Q x
x
Q x
x
Takes 5 guesses to determine first guess was wrong
x
Forward Checking
x
x
x
Q x
x
x
x
x
Q x
x
x
x
x
Q x
x
x
Q x
x
x
Q x
Q x
x
x
x
x
x
x
Q x
x
Q x
x
x
x
When variable is set,
immediately remove
inconsistent values from
domains of other variables
x
x
Takes 3 guesses to determine first guess was wrong
Arc Consistency
x
x
x
x
x
Q x
x
x
x
x
Q x
x
x
x
x
x
x
x
x
x
x
x
Q x
x
Q x
x
Iterate forward checking
Propagations:
1. Q3=3 inconsistent with Q4  {2,3,4}
2. Q2=1 and Q2=2 inconsistent with Q3  {1}
Inference alone determines first guess was wrong!
Huffman-Clowes
Labeling
+
+
+
-
+
+
+
Waltz’s Filtering: ArcConsistency
•Lines: variables
•Conjunctions: constraints
•Initially Di = {+,-, ,  )
•Repeat until no changes:
Choose edge (variable)
Delete labels on edge not
consistent with both
endpoints
No labeling!
Path Consistency
Path consistency (3-consistency):
• Check every triple of variables
• More expensive!
• k-consistency:
| V |k k-tuples to check
Worst case: each iteration eliminates 1 choice
| D || V | iterations
| D || V |k 1 steps! (But usually not this bad)
• n-consistency: backtrack-free search
Variable and Value Selection
• Select variable with smallest domain
– Minimize branching factor
– Most likely to propagate: most constrained variable
heuristic
• Which values to try first?
– Most likely value for solution
– Least propagation! Least constrained value
• Why different?
– Every constraint must be eventually satisfied
– Not every value must be assigned to a variable!
• Tie breaking?
– In general randomized tie breaking best – less likely to
get stuck on same bad pattern of choices
CSPs in the real world
• Scheduling Space Shuttle Repair
• Transportation Planning
• Computer Configuration
– AT&T CLASSIC Configurator
• #5ESS Switching System
• Configuring new orders: 2 months  2 hours
Quasigroup Completion
Problem (QCP)
Given a partial assignment of colors (10 colors in
this case), can the partial quasigroup (latin square)
be completed so we obtain a full quasigroup?
Example:
32% preassignment
(Gomes & Selman 97)
CPGomes - AAAI00
QCP Example Use: Routers in
Fiber Optic Networks
Dynamic wavelength routing in Fiber Optic Networks can be
directly mapped into the Quasigroup Completion Problem.
•each channel cannot be repeated in the same input port
(row constraints);
• each channel cannot be repeated in the same output
port (column constraints);
1
2
3
4
Output ports
Output Port
1
2
3
4
Input ports
Input Port
CONFLICT FREE
LATIN ROUTER
(Barry and Humblet 93, Cheung et al. 90, Green 92, Kumar et al. 99)
CPGomes - AAAI00
QCP as a CSP
• Variables -
•
O(n2)
x color of cell i, j; i, j 1, 2, ...,n.
i, j
x  {1, 2, ...,n}
i, j
Constraints - O(n)
alldiff (x , x ,..., x ); i 1, 2, ...,n.
i,n
i,1 i,2
row
alldiff (x , x ,..., x ); j 1, 2, ...,n. column
n, j
1, j 2, j
CPGomes - AAAI00
Hill Climbing
• Idea
– Always choose best child,
no backtracking
• Evaluation
– Complete?
– Space Complexity?
– Complexity of random restart hillclimbing, with success
probability P
Simulated Annealing / Random Walk
• Objective: avoid local minima
• Technique:
– For the most part use hill climbing
– Occasionally take non-optimal step
– Annealing: Reduce probability (non-optimal) over time
• Comparison to Hill Climbing
– Completeness?
– Speed?
Temperature
– Space Complexity?
Objective
Time 
Backtracking with Randomized
Restarts
• Idea:
– If backtracking algorithm does not find solution quickly,
it is like to be stuck in the wrong part of the search space
• Early decisions were bad!
– So kill the run after T seconds, and restart
• Requires randomized heuristic, so choices not always the same
– Why does it often work?
• Many problems have a small set of “backdoor” variables – guess them on a
restart, and your are done! (Andrew, Selman, Gomes 2003)
– Completeness?
Demos!
• N-Queens
Backtracking vs. Local Search
• Quasigroup Completion
Randomized Restarts
• Travelling Salesman
Simulated Annealing
Exercise
Peer interviews: Real-world constraint
satisfaction problems
1. Break into pairs
2. 7 minute interview – example of needing to
solve a CSP type problem (work or life).
Interviewer takes notes:
•
•
•
Describe problem
What techniques actually used
Any techniques from class that could have been used?
3. Switch roles
4. A few teams present now
5. Hand in notes (MSR – have someone collect
and mail to me at dept)
Planning as CSP
• Phase 1 - Convert planning problem in a CSP
• Choose a fixed plan length
• Boolean variables
– Action executed at a specific time point
– Proposition holds at a specific time point
• Constraints
– Initial conditions true in first state, goals true in final state
– Actions do not interfere
– Relation between action, preconditions, effects
• Phase 2 - Solution Extraction
• Solve the CSP
Planning Graph Representation of CSP
Precondition
constraints
Proposition
Init State
Effect
constraints
Action
Time 1
Proposition
Time 1
Action
Time 2
91
Constructing the planning graph…
• Initial proposition layer
– Just the initial conditions
• Action layer i
– If all of an action’s preconditionss are in i-1
– Then add action to layer I
• Proposition layer i+1
– For each action at layer i
– Add all its effects at layer i+1
Mutual Exclusion
• Actions A,B exclusive (at a level) if
– A deletes B’s precondition, or
– B deletes A’s precondition, or
– A & B have inconsistent preconditions
• Propositions P,Q inconsistent (at a level) if
– All ways to achieve P exclude all ways to achieve Q
• Constraint propagation (arc consistency)
– Can force variables to become true or false
– Can create new mutexes
93
Solution Extraction
• For each goal G at last time slice N:
•
Solve( G, N )
• Solve( G, t ):
CHOOSE action A making G true @t that is not
mutex with a previously chosen action
If no such action, backtrack to last choice point
For each precondition P of A:
Solve(P, t-1)
94
Graphplan
• Create level 0 in planning graph
• Loop
– If goal  contents of highest level (nonmutex)
– Then search graph for solution
• If find a solution then return and terminate
– Else Extend graph one more level
95
Dinner Date
Initial Conditions: (:and (cleanHands) (quiet))
Goal:
(:and (noGarbage) (dinner) (present))
Actions:
(:operator carry :precondition
:effect (:and (noGarbage) (:not (cleanHands)))
(:operator fire :precondition
:effect (:and (noGarbage) (:not (paper)))
(:operator cook :precondition (cleanHands)
:effect (dinner))
(:operator wrap :precondition (paper)
:effect (present))
Planning Graph
noGarb
carry
cleanH
cleanH
fire
paper
paper
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Are there any exclusions?
noGarb
carry
cleanH
noop
fire
cleanH
paper
noop
cook
paper
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Do we have a solution?
noGarb
carry
cleanH
noop
fire
cleanH
paper
noop
cook
paper
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Extend the Planning Graph
noGarb
carry
cleanH
paper
noop
fire
cleanH
noop
cook
paper
dinner
wrap
present
0 Prop
1 Action
2 Prop
noop
carr
y
noop
fire
noop
cook
noop
wrap
noop
3 Action
noGarb
cleanH
paper
dinner
present
4 Prop
One (of 4) Solutions
noGarb
carry
cleanH
paper
noop
fire
cleanH
noop
cook
paper
dinner
wrap
present
0 Prop
1 Action
2 Prop
noop
carr
y
noop
fire
noop
cook
noop
wrap
noop
3 Action
noGarb
cleanH
paper
dinner
present
4 Prop
Search Algorithms
Backtrack Search
1. DFS
2. BFS / Dijkstra’s
Algorithm
3. Iterative Deepening
4. Best-first search
5. A*
Constraint Propagation
1. Forward Checking
2. k-Consistency
3. DPLL & Resolution
Local Search
1. Hillclimbing
2. Simulated
annealing
3. Walksat
Representing Knowledge in
Propositional Logic
R&N Chapter 7
Basic Idea of Logic
By starting with true assumptions, you can
deduce true conclusions.
Truth
Francis Bacon (1561-1626)
No pleasure is comparable to
the standing upon the
vantage-ground of truth.
Blaise Pascal (1623-1662)
We know the truth, not only
by the reason, but also by the
heart.
Thomas Henry Huxley (18251895)
Irrationally held truths may be
more harmful than reasoned
errors.
François Rabelais (c. 14901553)
Speak the truth and shame
the Devil.
John Keats (1795-1821)
Beauty is truth, truth beauty;
that is all
Ye know on earth, and all ye
need to know.
Daniel Webster (1782-1852)
There is nothing so powerful
as truth, and often nothing so
strange.
Propositional Logic
Ingredients of a sentence:
1. Propositions (variables)
2. Logical Connectives , , , 
literal = a variable or a negated variable
•
•
•
A possible world assigns every proposition the
value true or false
A truth value for a sentence can be derived from
the truth value of its propositions by using the truth
tables of the connectives
The meaning of a sentence is the set of possible
worlds in which it is true
Truth Tables for Connectives


0
0
1
1
0
1

0
0
1
1
0
1
0
1
0
1
0
1

0
0
1
1
0
1
0
1
Special Syntactic Forms
• General PL:
((q r)  s))   (s  t)
• Conjunction Normal Form (CNF)
( q  r  s )  ( s   t)
Set notation: { ( q, r, s ), ( s,  t) }
empty clause () = false
• Binary clauses: 1 or 2 literals per clause
( q  r)
( s   t)
• Horn clauses: 0 or 1 positive literal per clause
( q   r  s ) ( s   t)
(qr)  s
(st)  false
Satisfiability, Validity, & Entailment
• S is satisfiable if it is true in some world
• Example:
• S is unsatisfiable if it is false all worlds
• S is valid if it is true in all worlds
• S1 entails S2 if wherever S1 is true S2 is true
Reasoning Tasks
•
•
Model finding
KB = background knowledge
S = description of problem
Show (KB  S) is satisfiable
A kind of constraint satisfaction
Deduction
S = question
Prove that KB  S
Two approaches:
1. Rules to derive new formulas from old (inference)
2. Show (KB   S) is unsatisfiable
Inference
• Mechanical process for computing new
sentences
• Resolution
{ (p  ), ( p  ) } R (  )
• Correctness
If S1 R S2 then S1  S2
• Refutation Completeness:
If S is unsatisfiable then S R ()
Resolution
If the unicorn is mythical, then it is immortal, but if it
is not mythical, it is a mammal. If the unicorn is
either immortal or a mammal, then it is horned.
Prove: the unicorn is horned.
M = mythical
I = immortal
A = mammal
H = horned
( A  H)
(M  A)
(I  H)
( H)
(A)
(I)
(M)
( M  I)
( M)
()
New Variable Trick
Putting a formula in clausal form may increase its
size exponentially
But can avoid this by introducing dummy variables
(abc)(def) {(ad),(ae),(af),
(bd),(be),(bf),
(cd),(ce),(cf) }
(abc)(def)  {(gh),
(abcg),(ga),(gb),(gc),
(defh),(hd),(he),(hf)}
Dummy variables don’t change satisfiability!
DPLL
Davis Putnam Loveland Logmann
• Model finding: Backtrack search over space
of partial truth assignments
DPLL( wff ):
Simplify wff: for each unit clause (Y)
Remove clauses containing Y
if no clause left then return true (satisfiable)
Shorten clauses contain  Y
if empty clause then return false
Choose a variable
Choose a value (0/1) – yields literal X
if DPLL( wff, X ) return true (satisfiable)
else return DPLL(wff,  X)
DPLL
Davis Putnam Loveland Logemann
• Backtrack search over space of partial truth
assignments
DPLL( wff ):
Simplify wff: for each unit clause (Y)
Remove clauses containing Y
if no clause left then return true (satisfiable)
Shorten clauses contain  Y
if empty clause then return false
Choose a variable
Choose a value (0/1) – yields literal X
if DPLL( wff, X ) return true (satisfiable)
else return DPLL(wff,  X)
unit propagation
= arc consistency
Horn Theories
Recall the special case of Horn clauses:
{ ( q   r  s ), ( s   t) }
{ ((qr)  s ), ((st)  false) }
Many problems naturally take the form of such
if/then rules
• If (fever) AND (vomiting) then FLU
Unit propagation is refutation complete for Horn
theories
• Good implementation – linear time!
DPLL
• Developed 1962 – still the best complete algorithm for
propositional reasoning
• State of the art solvers use:
Smart variable choice heuristics
“Clause learning” – at backtrack points, determine
minimum set of choices that caused
inconsistency, add new clause
Limited resolution (Agarwal, Kautz, Beame 2002)
Randomized tie breaking & restarts
• Chaff – fastest complete SAT solver
Created by 2 Princeton undergrads, for a summer
project!
Superscaler processor verification
AI planning - Blackbox
CPGomes - AAAI00
Exercise
• How could we represent the Quasigroup
Completion Problem as a Boolean formula in
CNF form?
(take 10 minutes to sketch solution)
CPGomes - AAAI00
WalkSat
Local search over space of complete truth
assignments
With probability P: flip any variable in any
unsat clause
With probability (1-P): flip best variable in
any unsat clause
Like fixed-temperature simulated annealing
• SAT encodings of QCP, N-Queens, scheduling
• Best algorithm for random K-SAT
Best DPLL: 700 variables
Walksat: 100,000 variables
CPGomes - AAAI00
Random 3-SAT
 Random 3-SAT
sample uniformly from
space of all possible 3clauses
n variables, l clauses
 Which are the hard
instances?
around l/n = 4.3
Random 3-SAT
 Varying problem size, n
 Complexity peak
appears to be largely
invariant of algorithm
backtracking algorithms
like Davis-Putnam
local search procedures
like GSAT
 What’s so special about
4.3?
Random 3-SAT
 Complexity peak
coincides with solubility
transition
l/n < 4.3 problems underconstrained and SAT
l/n > 4.3 problems overconstrained and UNSAT
l/n=4.3, problems on
“knife-edge” between
SAT and UNSAT
Real-World Phase Transition
Phenomena
Many NP-hard problem distributions show
phase transitions job shop scheduling problems
TSP instances from TSPLib
exam timetables @ Edinburgh
Boolean circuit synthesis
Latin squares (alias sports scheduling)
Hot research topic: predicting hardness of a
given instance, & using hardness to control
search strategy (Horvitz, Kautz, Ruan 2001-3)
Logical Reasoning
about Time &
Change
AKA
Planning as
Satisfiability
Salvidor Dali, Persistance of Memory
Actions
We want to relate changes in the world over
time to actions associated with those
changes
How are actions represented?
1. As functions from one state to another
2. As predicates that are true in the state
in which they (begin to) occur
Actions as Functions:
“Situation Calculus”
On(cat, mat, S0)
Happy(cat, S0)
 On(cat, mat, kick(S0))
 Happy(cat, kick(S0))
Happy(cat, pet(kick(S0)))
Branching time:
kick
kick
pet
S0
pet
kick
pet
Actions as Predicates:
“Action Calculus”
On(cat, mat, S0)  Happy(S0)
Kick(cat, S0)
 On(cat, mat, S1)  Happy(CAT99, S1)
Pet(CAT99, S1)
 On(CAT99, MAT37, S2)  Happy(CAT99, S2)
Linear time:
S0
S1
kick
pet
S2
Relating Actions to
Preconditions & Effects
Strips notation:
Action: Fly( plane, start, dest )
Precondition: Airplane(plane), City(start), City(dest),
At(plane, start)
Effect: At(plane, dest),  At(plane, start)
Pure strips: no negative preconditions!
Need to represent logically:
•
•
•
•
An action requires it’s predications
An action causes it’s effects
Interfering actions do not co-occur
Changes in the world are the result of actions.
Preconditions & Effects
 plane, start, dest, s . Fly(plane, start, dest, s) 
[ At(plane, start, s) 
Airplane(plane,s)  City(start)  City(dest) ]
• Note: state indexes on predicates that never change
not necessary.
 plane, start, dest, s . Fly(plane, start, dest, s) 
At(plane, dest, s+1)
• In action calculus, the logical representation of
“requires” and “causes” is the same!
• Not a full blown theory of causation, but good
enough…
Interfering Actions
Want to rule out:
Fly( PLANE32, NYC, DETROIT, S4) 
Fly( PLANE32, NYC, DETROIT, S4)
Actions interfere if one changes a precondition or effect
of the other
They are mutually exclusive – “mutex”
 p, c1, c2, c3, c4, s .
[Fly(p, c1, c2, s)  (c1  c3  c2  c4) ] 
 Fly(p, c3, c4, s)
(Similar for any other actions Fly is mutex with)
Explanatory Axioms
• Don’t want world to change “by magic” – only
actions change things
• If a proposition changes from true to false (or
vice-versa), then some action that can change it
must have occurred
 plane, start, s . [ Airplane(plane)  City(start)
At(plane,start,s)  At(plane,city,s+1) ] 
 dest . [ City(dest)  Fly(plane, start, dest, s) ]
 plane, dest, s . [ Airplane(plane)  City(start)
At(plane,dest,s)  At(plane,dest,s+1) ] 
 start . [ City(start)  Fly(plane, start, dest, s) ]
The Frame Problem
General form of explanatory axioms:
[ p(s)  p(s+1) ]  [ A1(s)  A2(s)  …  An(s) ]
As a logical consequence, if none of these actions
occurs, the proposition does not change
[A1(s)  A2(s)  …  An(s) ]  [ p(s)  p(s+1) ]
This solves the “frame problem” – being able to
deduce what does not change when an action
occurs
Frame Problem in AI
• Frame problem identified by
McCarthy in his first paper on the
situation calculus (1969)
667 papers in researchindex !
• Lead to a (misguided?) 20 year effort
to develop non-standard logics
where no frame axioms are required
(“non-monotonic”)
7039 papers!
• 1990 - Haas and Schubert
independently pointed out that
explanatory axioms are pretty easy to
write down
Planning as Satisfiability
•
•
•
Idea: in action calculus assert that initial state holds at
time 0 and goal holds at some time (in the future):
• Axioms  Initial   s . Goal(s)
Any model that satisfies these assertions and the
axioms for actions corresponds to a plan
Bounded model finding, i.e. satisfiability testing:
1. Assert goal holds at a particular time K
2. Ground out (instantiate) the theory up to time K
3. Try to find a model; if so, done!
4. Otherwise, increment K and repeat
Reachability Analysis
• Problem: many irrelevant propositions, large
formulas
• Reachability analysis: what propositions
actually connect to initial state or goal in K
steps?
• Graphplan’s plan graph computes reachable
set!
• Blackbox (Kautz & Selman 1999)
• Run graphplan to generate plan graph
• Translate plan graph to CNF formula
• Run any SAT solver
Translation of Plan Graph
Pre1
Act1
Fact
Pre2
Act2
Fact  Act1  Act2
Act1  Pre1  Pre2
¬Act1  ¬Act2
Improved Encodings
Translations of Logistics.a:
STRIPS  Axiom Schemas  SAT
• 3,510 variables, 16,168 clauses
• 24 hours to solve
STRIPS  Plan Graph  SAT
(Blackbox)
• 2,709 variables, 27,522 clauses
• 5 seconds to solve!
Model-Based Diagnosis
Idea:
• Create a logical model
of the correct
functioning of a device
• When device is broken,
observations + model is
inconsistent
• Create diagnosis by
restoring consistency
Simplified KB
Knowledge Base:
SignalValueA  ValveAok  ValveAopen
SignalValueB  ValveBok  ValveBopen
SignalValueC  ValveCok  ValveCopen
ValveAopen  EngineHasFuel
ValveBopen  EngineHasFuel
ValveCopen  EngineHasOxy
EngineHasFuel  EngineHasOxy  EngineFires
Normal Assumptions:
ValveAok, ValveBok, ValveCok
Direct Actions (cannot fail):
SignalValveA, SignalValveB, SignalValveC
Observed:
 EngineFires
Diagnosis: 1
Knowledge Base:
SignalValueA  ValveAok  ValveAopen
SignalValueB  ValveBok  ValveBopen
SignalValueC  ValveCok  ValveCopen
ValveAopen  EngineHasFuel
ValveBopen  EngineHasFuel
ValveCopen  EngineHasOxy
EngineHasFuel  EngineHasOxy  EngineFires
Normal Assumptions:
ValveAok, ValveBok, ValveCok
Direct Actions (cannot fail):
SignalValveA, SignalValveB, SignalValveC
Observed:
 EngineFires
Inconsistent by Unit
Propagation
Diagnosis: 2
Knowledge Base:
SignalValueA  ValveAok  ValveAopen
SignalValueB  ValveBok  ValveBopen
SignalValueC  ValveCok  ValveCopen
ValveAopen  EngineHasFuel
ValveBopen  EngineHasFuel
ValveCopen  EngineHasOxy
EngineHasFuel  EngineHasOxy  EngineFires
Normal Assumptions:
ValveAok, ValveBok, ValveCok
Direct Actions (cannot fail):
SignalValveA, SignalValveB, SignalValveC
Observed:
 EngineFires
Still Inconsistent
Diagnosis: 3
Knowledge Base:
SignalValueA  ValveAok  ValveAopen
SignalValueB  ValveBok  ValveBopen
SignalValueC  ValveCok  ValveCopen
ValveAopen  EngineHasFuel
ValveBopen  EngineHasFuel
ValveCopen  EngineHasOxy
EngineHasFuel  EngineHasOxy  EngineFires
Normal Assumptions:
ValveAok, ValveBok, ValveCok
Direct Actions (cannot fail):
SignalValveA, SignalValveB, SignalValveC
Observed:
 EngineFires
Consistency Restored!
Diagnosis: Valve A and Valve B
broken (double fault)
Diagnosis: 4
Knowledge Base:
SignalValueA  ValveAok  ValveAopen
SignalValueB  ValveBok  ValveBopen
SignalValueC  ValveCok  ValveCopen
ValveAopen  EngineHasFuel
ValveBopen  EngineHasFuel
ValveCopen  EngineHasOxy
EngineHasFuel  EngineHasOxy  EngineFires
Normal Assumptions:
ValveAok, ValveBok, ValveCok
Direct Actions (cannot fail):
SignalValveA, SignalValveB, SignalValveC
Observed:
A different way to restore
 EngineFires
consistency
Diagnosis: Valve C broken
(single fault)
Diagnostic Engine for
NASA’s Deep Space One
•2,000 variable CNF formula
•Real-time planning and diagnosis
Beyond Logic
• Often you want most likely diagnosis rather
than all possible diagnoses
• Can assign probabilities to sets of fault, and
search for most likely way to restore
consistency
• But suppose observations and model of the
device are also uncertain?
• Next: Probabilistic Reasoning in Bayesian
Networks