CS代考 Ve492: Introduction to Artificial Intelligence

Ve492: Introduction to Artificial Intelligence
Classical Planning

UM-SJTU Joint Institute Some slides adapted from CMU

Learning Objectives
❖ How to implement a logical agent based on FOL?
❖ What are the limitations of using a formal logic
language for planning?
❖ What is the STRIPS language?
❖ How to perform planning with STRIPS?

❖ Logical agent based on FOL
❖ Classical planning ❖ Language
❖ Algorithms

Spectrum of representations
Search, game-playing MDP, RL
CSPs, planning, propositional logic, Bayes nets, neural nets, RL with function approx.
First-order logic, databases, probabilistic programs

Robot Block Stacking
Start state: A, B, C on table Goal: Block B on C and C on A Plan: ?

Modeling Block Stacking States
Start state: A, B, C on table Goal: Block B on C and C on A Plan: ?

Goals in the World
Goal States
completely specified
Goal Statements partially specified
Preference models objective function
Increasing Generality

Block Stacking States

States are Atomic

Initial and Goal States

Plan from Initial to Goal State

Goals in the World
Goal States
completely specified
Goal Statements partially specified
Preference models objective function
BFS, DFS, A*
Increasing Generality

Reward Function
Living cost = -1
Large positive reward in goal state

Goals in the World
Goal States
completely specified
Goal Statements partially specified
Preference models objective function
BFS, DFS, A*
A*, MDP, RL
Increasing Generality

Goals in the World
Goal States
completely specified
Goal Statements partially specified
Preference models objective function
BFS, DFS, A*
Logic, CSP
A*, MDP, RL
Increasing Generality

Logical Agents with FOL
Create a Knowledge Base (KB)
Constants (objects) Predicates
Initial state and a priori knowledge
Domain knowledge and “Physics” of the domain

Block World Example: Objects and Predicates
Constants: A, B, C
Create a KB with predicates:
On-Table(X, t) On-Block(X,Y, t) In-Hand(X, t) Hand-Empty(t) Pick(X, t), Put(X,Y, t)

Block World Example: Initial State
Constants: A, B, C
Create a KB with predicates:
On-Table(X, t) On-Block(X,Y, t) In-Hand(X, t) Hand-Empty(t) Pick(X, t), Put(X,Y, t)
Initial State:
On-Table(A,0) On-Table(B,0) On-Table(C,0) Hand-Empty(0)

Block World Example: « Physics »
Create a KB rules:
When is On-Block(X,Y) true or false? Use successor-state axioms!
On-Block(X,Y,t)
(On-Block(X,Y,t-1) ∧ ¬ Pick(X,t-1)) ∨
(In-Hand(X,t-1) ∧ Put(X,Y,t-1)
∧ Clear(Y,t-1))
Don’t forget domain knowledge and common knowledge! e.g., Hand-Empty

Logical Agents
Create a Knowledge Base (KB)
Objects Predicates
Initial state and a priori knowledge
Domain knowledge and “Physics” of the domain
ASK whether KB entails a query
e.g., On(B,C,t) ∧ On(C,A,t)?
Hybrid approach is also possible
e.g., KB used to infer knowledge about world state and decisions made by other module

Challenges of Logic Planning
Need time-dependent symbols (PL) or predicates (FOL)
A state (i.e., model or possible world) is fully-specified by knowing the truth value of all symbols/atomic sentences
Actions (e.g., picking a block) are represented with successor-state axioms, which are difficult to specify
Easy to incorrectly specify an axiom (e.g., Hand-Empty(t)) Very hard to debug

Language for Classical Planning
Stanford Research Institute Problem Solver

Classical Planning (with STRIPS)
Partially-specified goals
Create a Knowledge Base Using STRIPS language
Predicates for describing states Operators for describing actions
Using KB, find plan to reach any goal state
Goal = conjunction of predicates

Propositional Logic
A-on-Table_t, A-In-Hand_t,
B-on-Table_t, B-In-Hand_t, C-on-Table_t, C-In-Hand_t, Hand-Empty_t, A-on-B_t, B-on-A_t, A-on-C_t, C-on-A_t, B-on-C_t, C-on-B_t Clear-A_t, Clear- B_t, Clear-C_t
Predicates
First-Order Logic
Constants: A, B, C Predicates:
Constants: A, B, C Predicates:
In-Hand(A,t)
On-Table(B,t) On-Block(B,C,t) HandEmpty(t)
Clear(A,t) ……
In-Hand(A) On-Table(B) On-Block(B,C) HandEmpty() Clear(A)

❖ STRIPS inspired by FOL
❖ In STRIPS
❖ No functions!
❖ States are represented by conjunctions of positive predicates
❖ If a predicate doesn’t appear in this conjunction, it is false
❖ Predicates don’t depend on time
❖ Actions don’t need any predicates, they are represented as operators
❖ Trade-off between expressivity of language and efficiency of solving algorithms

How to Describe this State?
Instances: A, B, C Propositions:
1) In-Hand(A)
2) In-Hand(B)
3) In-Hand(C)
4) On-Table(A) 5) On-Table(B) 6) On-Table(C) 7) On-Block(B,C) 8) On-Block(A,B) 9) HandEmpty()

Quiz: Check all that apply
Instances: A, B, C Propositions:
1) In-Hand(A)
2) In-Hand(B)
3) In-Hand(C)
4) On-Table(A) 5) On-Table(B) 6) On-Table(C) 7) On-Block(B,C) 8) On-Block(A,B) 9) HandEmpty()

Block Stacking
States: Conjunctions of Predicates How about actions?

Actions can be applied only if some conditions are met Represented as conjunctions of positive predicates
Actions change the state of the world
Represented as effects that add/delete predicates
Operator = precondition, delete list, add list Operators can have parameters and are given names
e.g., pick-up(o), put-down(o)

Actions for Block Stacking
Blocks are picked up and put down by the hand Blocks can be picked up only if they are clear
Hand can pick up a block only if the hand is empty Hand can put down blocks on blocks or on the table

Pick Up Block from Table Example
Preconditions?

Pick Up Block from Table Example
Preconditions HandEmpty
On-Table(b) Clear(b)

Pick Up Block from Table Example
Preconditions Effects? HandEmpty
On-Table(b) Clear(b)

Pick Up Block from Table Example
Preconditions HandEmpty
On-Table(b) Clear(b)
Add: Holding(b)
Delete: On-Table(b) HandEmpty

Pick Block from Block Example
Preconditions Effects

Operators for Block Stacking
Pickup_from_Table(b):
Pre: HandEmpty, Clear(b), On-Table(b)
Add: Holding(b)
Delete: HandEmpty, On-Table(b)
Pickup_from_Block(b,c):
Pre: HandEmpty, On(b,c) Add: Holding(b), Clear(c) Delete: HandEmpty, On(b,c)

Operators for Block Stacking
Pickup_from_Table(b):
Pre: HandEmpty, Clear(b), On-Table(b)
Add: Holding(b)
Delete: HandEmpty, On-Table(b)
Putdown_on_Table(b): Pre: Holding(b)
Add: HandEmpty, On-Table(b) Delete: Holding(b)
Pickup_from_Block(b,c):
Pre: HandEmpty, On(b,c) Add: Holding(b), Clear(c) Delete: HandEmpty, On(b,c)
Putdown_on_Block(b,c):
Pre: Holding(b), Clear(c) Add: HandEmpty, On(b,c) Delete: Clear(c), Holding(b)

Planning Algorithms
Knowle?dge Base Inference
Environment

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O)
Pickup_from_Block(b,c):
Pre: HandEmpty, On(b,c), b!=c
Add: Holding(b), Clear(c) Delete: HandEmpty, On(b,c)
Pickup_from_Table(b):
Pre: HandEmpty, Clear(b), On-Table(b)
Add: Holding(b)
Delete: HandEmpty, On-Table(b)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
Pickup_from_Block(b,c):
Pre: HandEmpty, On(b,c), Clear(c), b!=c
Add: Holding(b), Clear(c) Delete: HandEmpty, On(b,c)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O)
Pickup_from_Block(b,c):
Pre: HandEmpty, On(b,c), Clear(c), b!=c
Add: Holding(b), Clear(c)
Delete: HandEmpty, On(b,c)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Holding(T) ∧ Clear(R) Putdown_on_Table(T)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Clear(R)
Putdown_on_Table(b): Pre: Holding(b)
Add: HandEmpty, On-Table(b)
Delete: Holding(b)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Holding(T) ∧ Clear(R) Putdown_on_Table(T)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Clear(R) ∧ HandEmpty ∧ On- Table(T)
Putdown_on_Table(b): Pre: Holding(b)
Add: HandEmpty, On-Table(b)
Delete: Holding(b)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Holding(T) ∧ Clear(R) Putdown_on_Table(T)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Clear(R) ∧ HandEmpty ∧ On- Table(T)
Pickup_from_Table(O)
Pickup_from_Table(b):
Pre: HandEmpty, Clear(b), On-Table(b)
Add: Holding(b)
Delete: HandEmpty, On-Table(b)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Holding(T) ∧ Clear(R) Putdown_on_Table(T)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Clear(R) ∧ HandEmpty ∧ On- Table(T)
Pickup_from_Table(O)
On-Table(R) ∧ Clear(T) ∧ Clear(O) ∧ Clear(R) ∧ On-Table(T) ∧ Holding(O)
Pickup_from_Table(b):
Pre: HandEmpty, Clear(b), On-Table(b)
Add: Holding(b)
Delete: HandEmpty, On-Table(b)

Example Plan of Actions
HandEmpty ∧ On-Table(R) ∧ On(T,R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) Pickup_from_Block(T,R)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Holding(T) ∧ Clear(R) Putdown_on_Table(T)
On-Table(R) ∧ Clear(T) ∧ On-Table(O) ∧ Clear(O) ∧ Clear(R) ∧ HandEmpty ∧ On- Table(T)
Pickup_from_Table(O)
On-Table(R) ∧ Clear(T) ∧ Clear(O) ∧ Clear(R) ∧ On-Table(T) ∧ Holding(O) Putdown_on_Block(O,R)
On-Table(R) ∧ Clear(T) ∧ Clear(O) ∧ On-Table(T) ∧ On(O,R) ∧ HandEmpty

Planning is a Search Problem
Planning problem can be represented as a graph:
States: Conjunctions of Predicates
Arrows = Actions
Space complexity in terms of # predicates 𝑝 Search algorithm can be applied!

❖ Any search algorithm (BFS, DFS, IDS…) could be used
❖ Here, search can also be performed backward!
❖ From a given state 𝑋! ∧ ⋯ ∧ 𝑋” , consider relevant and consistent actions
❖ An action is relevant if it achieves one of the 𝑋!’s
❖ An action is consistent if it doesn’t undo one of the 𝑋!’s
❖ An operator can easily be reversed by modifying the current state:
❖ Remove its positive effects
❖ Add its preconditions (unless it already appears in the state)
❖ Stop backward search when reaching state that is satisfied by initial state
❖ However, as STRIPS allow to describe compactly very large problems, A* is needed with very good heuristics

Efficient Algorithms
❖ STRIPS planning is PSPACE-complete
❖ Forward or backward A*
❖ Domain-independent heuristics ❖ # of unsatisfied literals in goal
❖ Relaxed problem
❖ sum of costs for achieving each literal in goal
❖ may be inadmissible
❖ Specialized algorithms
❖ e.g., Graphplan (See 10.3 in AIMA)

Properties of Planners
❖ A planning algorithm is sound if all solutions found are legal plans Completeness
❖ A planning algorithm is complete if a solution can be found whenever one actually exists
Optimality
❖ A planning algorithm is optimal if the solution optimizes some measure of plan quality

Concluding Remarks
❖ Language
❖ Various extensions of STRIPS exist, e.g., PDDL.
❖ Once problem is formalized, generic algorithms can be applied.
❖ Can solve very large planning problem.
❖ For more information:
❖ AIMA, Chapter 10 for Classical Planning

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts