›
›

Bài giảng Trí tuệ nhân tạo - Chapter 10: Planning

Download
Planning  
Chapter 10  
Overview  
The blocks world  
B
C B  
A D  
A C D  
start  
goal  
How to achieve the goal from the start?  
2
Overview  
• Problem-solving is searching and moving through a  
state space.  
3
Overview  
• Problem-solving is searching and moving through a  
state space.  
• Planning is searching for sucessful paths through a  
state space.  
4
Overview  
• Planning is the process of computing several steps of  
a problem-solving procedure before executing them.  
• Planning = problem sloving in advance.  
5
Overview  
• Planning is important if solutions cannot be undone.  
• If the universe is not predictable, then a plan can fail  
⇒ dynamic plan revision.  
6
The Blocks World  
B
C B  
A C D  
A D  
start  
goal  
Planning = generating a sequence of actions to  
achieve the goal from the start  
7
The Blocks World  
Actions:  
• UNSTACK(A, B)  
• STACK(A, B)  
• PICKUP(A)  
• PUTDOWN(A)  
8
The Blocks World  
Conditions and results:  
• ON(A, B)  
• ONTABLE(A)  
• CLEAR(A)  
• HOLDING(A)  
• ARMEMPTY  
9
The Blocks World  
Specification of actions:  
• PRECONDITION: list of predicates that must be true  
for an operator to be applied.  
• ADD: list of new predicates that an operator causes  
to become true.  
• DELETE: list of old predicates that an operator  
causes to become false.  
• Predicates not in ADD nor DELETE are unaffacted.  
10  
                        
                          
                       
                                
                       
                          
                        
The Blocks World  
Specification of actions:  
STACK(x, y):  
P: CLEAR(y) ∧ HOLDING(x)  
D: CLEAR(y) ∧ HOLDING(x)  
A: ARMEMPTY ∧ ON(x, y)  
UNSTACK(x, y):  
P: ON(x, y) ∧ CLEAR(x) ∧ ARMEMPTY  
D: ON(x, y) ∧ ARMEMPTY  
A: HOLDING(x) ∧ CLEAR(y)  
11  
                        
                                    
                          
                          
The Blocks World  
Specification of actions:  
PICKUP(x):  
P: CLEAR(x) ∧ ONTABLE(x) ∧ ARMEMPTY  
D: ONTABLE(x) ∧ ARMEMPTY  
A: HOLDING(x)  
PUTDOWN(x):  
P: HOLDING(x)  
D: HOLDING(x)  
A: ONTABLE(x) ∧ ARMEMPTY  
12  
                        
                                                 
                           
                                                 
                           
                                                    
                           
                                                    
The Blocks World  
B
C B  
A C D  
A D  
start: ON(B, A) ∧  
ONTABLE(A) ∧  
ONTABLE(C) ∧  
ONTABLE(D) ∧  
ARMEMPTY  
goal: ON(C, A) ∧  
ON(B, D) ∧  
ONTABLE(A) ∧  
ONTABLE(D) ∧  
13  
Goal Stack Planning  
Stack  
Database  
Goals  
Current situation  
+
Operators to  
satisfy  
the Goals  
Specification of  
Operators/Actions  
14  
Goal Stack Planning  
Push the original goal to the stack. Repeat until the  
stack is empty:  
– If stack top is a compound goal, push its unsatisfied  
subgoals to the stack.  
– If stack top is a single unsatisfied goal, replace it by an  
operator that makes it satisfied and push the operator’s  
precondition to the stack.  
– If stack top is an operator, pop it from the stack, execute it  
and change the database by the operation’s affects.  
– If stack top is a satisfied goal, pop it from the stack.  
15  
                        
                                                 
                           
                                                 
                           
                                                    
                           
                                                    
Goal Stack Planning  
B
C B  
A C D  
A D  
start: ON(B, A) ∧  
ONTABLE(A) ∧  
ONTABLE(C) ∧  
ONTABLE(D) ∧  
ARMEMPTY  
goal: ON(C, A) ∧  
ON(B, D) ∧  
ONTABLE(A) ∧  
ONTABLE(D) ∧  
16  
                   
                            
                    
                   
                   
                            
Goal Stack Planning  
Stack  
Database  
ON(C, A)  
ON(B, A)  
OTACD  
ON(B, D)  
ON(C, A) ∧ ON(B, D) ∧ OTAD  
ARMEMPTY  
CLEAR(A)  
ON(B, A)  
OTACD  
HOLDING(C)  
CLEAR(A) ∧ HOLDING(C)  
STACK(C, A)  
ARMEMPTY  
ON(B, D) ∧  
ON(C, A) ∧ ON(B, D) ∧ OTAD  
17  
Goal Stack Planning  
Plan  
1. UNSTACK(B, A)  
2. STACK(B, D)  
3. PICKUP(C)  
4. STACK(C, A)  
18  
                        
                                                 
                           
                           
Goal Stack Planning  
A
B
C
A B  
C
start: ON(C, A) ∧  
goal: ON(A, B) ∧  
ONTABLE(A) ∧  
ON(B, C)  
ONTABLE(B) ∧  
ARMEMPTY  
Sussman Anomaly (1975)  
19  
Goal Stack Planning  
Plan  
1. UNSTACK(C, A)  
2. PUTDOWN(C)  
3. PICKUP(A)  
4. STACK(A, B)  
5. UNSTACK(A, B)  
6. PUTDOWN(A)  
7. PICKUP(B)  
8. STACK(B, C)  
9. PICKUP(A)  
10. STACK(A, B)  
20  
Tải về để xem bản đầy đủ
pdf 24 trang myanh 20160 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Chapter 10: Planning", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_tri_tue_nhan_tao_chapter_10_planning.pdf