intelegensia semu - planning

MATAKuliah

Inteligensia Semu

“PLANNING”

Clasical Paradigm (Serial)

En

vir

on

men

t

Sense

Model

Plant

Act

Targ

et/

Goal

Planning

• Planning dalam Artificcial Intelligent (AI) adalah bagaimana kita merencanakan setiap langkah untuk mengatasi masalah-masalah yang sewaktu-waktu dapat terjadi dalam suatu pengembangan sistem kecerdasan buatan.

• Cara yang kita pakai untuk mendapatkan sebuah goal atau solusi pemecahan masalah.

• Selain itu adapula yang kita sebut sebagai Classical Planning yang mencakup ke semua ruang lingkup, determinasi, observasi dan diskrit dimana hal tersebut berhubungan dengan waktu, tindakan serta efek yang di timbulkan dalam pencarian suatu cara,suatu keputusan atau solusi terbaik.

Planning

1. Employ to avoid calculation of the entire problem state when we move from one state to the next (consider only parts of the state that may have changed)

2. Decomposition : divide a single difficult problem into several, hopefully easier, sub-problems.

So …what is planning

1. In everyday usage, planning refers to the process of computing several steps of a problem solving procedures before executing any of them

2. To be more specific, planning is the use of decomposition methods including ways of recording and handling interaction among the subparts

Examples of Planning Systems

• Spacecraft assembly, integration and verification

• Job shop scheduling

• Space mission scheduling

• Building construction

• Operations on a flight deck of an aircraft carrier

• For demos: blocks world

State of the Art

• Planning and scheduling: NASA• Game playing: Deep Blue• Autonomous control: ALVINN• Diagnosis• Logistics planning: DART• Robotics: HipNav• Language understanding and problem-

solving: PROVERB

Boeing Company

Boeing 787 Dreamliner™.Aurora Intelligent Planning & Scheduling System

Scheduling vs. Planning

Planning is deciding what to do.Scheduling is deciding when to do it.

Contoh Planning

The Blocks World

Operator :• UNSTACK(A,B) Ambil block A dari posisi saat ini di atas

block B. Arm (tangan) harus empty (kosong) dan block A harus kosong di atasnya.

• STACK(A,B) Tempatkan block A di atas block B. Arm harus sudah holding (memegang) A dan permukaan B harus clear (kosong).

• PICKUP(A) Ambil block A dari meja dan pegang. Arm harus empty dan harus tidak ada apa-apa di atas block A.

• PUTDOWN(A) Letakkan block A ke atas meja. Arm harus sudah holding block A.

The Block World

Predicates :• ON (A,B) – Block A is on block B

• ONTABLE (A) – Block A is on the table

• CLEAR (A) – There is nothing on top of block A

• HOLDING (A) – The arm is holding block A

• ARMEMPTY – The arm is holding nothing

Components of a Planning System

1. Choose the best rule to apply next based on the best available heuristic information (examine representation)

2. Applying rules (divide and conquer) : (If actions only affect small parts of state, solve sub-goal independently and merge sub-plans)

A B C D

A

DB

C

Problem : Sub-goals can interfere

A B C

A

B

C

Getting A on B interferes with getting B on C

We might even have to undo satisfied sub-goals, e.g. :

A

B C

A

B

C

STRIPS -Style Operator1. STACK(x,y) : place x on y, the arm must already

be holding x and the surface of y must be clear

1. P : CLEAR(y) HOLDING(x)2. D : CLEAR(y) HOLDING(x)3. A : ARMEMPTY ON(x,y)

2. UNSTACK(x,y) : pick up x from y, the arm must be empty and x must have no blocks on top of it

1. P : ON(x,y) CLEAR(y) ARMEMPTY2. D : ON(x,y) ARMEMPTY3. A : HOLDING(x) CLEAR(y)

STRIPS, STanford Research Institute Planning Systems

STRIPS-Style Operator(cont’d)

3. PICKUP(x) : pick up x from the table and hold it. The arm must be empty and there must be nothing on top of block x.

P : CLEAR(x) ONTABLE(x) ARMEMPTYD : ONTABLE(x) ARMEMPTY A : HOLDING(x)

4. PUTDOWN(x) : put x down on the table, the arm must have been holding x

P : HOLDING(x)D : HOLDING(x)A : ONTABLE(x) ARMEMPTY

P, Precondition ; D, Deletion ; A, Add (list).

A simple blocks world description

A

BON(A,B,S0) ONTABLE(B,S0) CLEAR(A,S0)

Applying operator UNSTACK(A,B), our description of the world would be:

ONTABLE(B,S1) CLEAR(A,S1) CLEAR(B,S1) HOLDING (A,S1)

Goal Stack Planning

A

B

C D

C

DA

B

Start : ON(B,A) ONTABLE(A) ONTABLE(C) ONTABLE(D) ARMEMPTY

Goal: ON(C,A) ON (B,D) ONTABLE(A) ONTABLE(D)

Planning Solution

UNSTACK(B,A)STACK(B,D)PICKUP(C)

STACK(C,A)

C

DA

B

A

B

C D

Divide & Conquer

C

DA

B

ON(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

ON(B,D) ON(C,A) ON(C,A) ON(B,D) ONTAD

(1) (2)

Alternative 1

ON(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

STACK(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

CLEAR(A)

HOLDING(C)

ON(B,D) ON(C,A) ON(B,D) ONTADSUB-GOALS

A

B

C D

Goal Stack PlanningUNSTACK(B,A)

ON(B,A) CLEAR(B) ARMEMPTYHOLDING(C)CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

ONTABLE(A) ONTABLE(C) ONTABLE(D) HOLDING(B) CLEAR(A) database

CLEAR(A)HOLDING(C)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

Goal Stack Planning

PICKUP(C)

UNSTACK(C,x)

ON(B,A) CLEAR(B) ARMEMPTY

UNSTACK(B,A)

HOLDING(C)CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

Goal Stack Planning

PICKUP(C)ONTABLE(C) CLEAR(C) ARMEMPTY

CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

UNSTACK(C,x)ON (C,x) CLEAR(C) ARMEMPTY

CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

(1) (2)

Goal Stack Planning

ON (C,x)CLEAR(A) HOLDING(C)

STACK(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

CLEAR(x) HOLDING(C)STACK(C,x)

ON (C,x) CLEAR(C) ARMEMPTYUNSTACK(C,x)CLEAR(A) HOLDING(C)

STACK(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

Goal Stack Planning (back to alternative 1)

PICKUP(C)ONTABLE(C) CLEAR(C) ARMEMPTYONTABLE(C) (satisfied)CLEAR(C) (satisfied)ARMEMPTY (false since HOLDING(B) is true)

CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D)

ON(C,A) ON(B,D) ONTAD

C

DA

BUNSTACK(B,A) has been called at the beginning

A

B

C D

Goal Stack Planning (alternative 1)

CLEAR(D)HOLDING(B)CLEAR(D) HOLDING(B)STACK(B,D)

ONTABLE(C) CLEAR(C) ARMEMPTYPICKUP(C)CLEAR(A) HOLDING(C)

STACK(C,A)

ON(B,D) (done, using stack(B,D)

ON(C,A) ON(B,D) ONTAD

C

DA

BONTABLE(A) ONTABLE(C) ONTABLE(D) ON(B,D) ARMEMPTY

Now satisfied

Database updated

Goal Stack Planning (alternative 1)

UNSTACK(B,A)STACK(B,D)PICKUP(C)

STACK(C,A)

C

DA

B

ON(B,A)CLEAR(B)ARMEMPTYON(B,A) CLEAR(B) ARMEMPTYUNSTACK(B,A)CLEAR(D)HOLDING(B)CLEAR(D) HOLDING(B)STACK(B,D)ONTABLE(C)CLEAR(C)ARMEMPTYONTABLE(C) CLEAR(C) ARMEMPTYPICKUP(C)CLEAR(A) HOLDING(C)STACK(C,A) ON(B,D) ON(C,A) ON(B,D) ONTAD

A

B

C D

Another Problem

C

A

B

A B

C

Start :

ON(C,A) ONTABLE(A) ONTABLE(B) ARMEMPTY

Goal :

ON(A,B) ON(B,C)

Two (2) Solution

C

A

B

ON(A,B)

ON(B,C)

ON(A,B) ON(B,C)

ON(B,C)

ON(A,B)

ON(A,B) ON(B,C)

(1) (2)

A B

C

C

A

B

ON(C,A)CLEAR(C)ARMEMPTYUNSTACK(C,A)ARMEMPTYCLEAR(A) ARMEMPTYPICKUP(A)CLEAR(B) HOLDING(A)STACK(A,B) ON(B,C) ON(A,B) ON(B,C)

A B

C

C

A

B

Goal stack:ON(B,C) ON(A,B) ON(B,C)

Current state:ONTABLE(B) ON(A,B) ONTABLE(C) ARMEMPTY

ON(C,A)CLEAR(C)ARMEMPTYUNSTACK(C,A)ARMEMPTYCLEAR(A) ARMEMPTYPICKUP(A)CLEAR(B) HOLDING(A)STACK(A,B) ON(B,C) ON(A,B) ON(B,C)

C

A

B

UNSTACK(C,A)ARMEMPTY (PUTDOWN(C))PICKUP(A)STACK(A,B) ON(B,C) ON(A,B) ON(B,C)

C A

B

UNSTACK(C,A)PUTDOWN(C)PICKUP(A)STACK(A,B) UNSTACK(A,B)PUTDOWN(A)PICKUP(B)STACK(B,C)ON(A,B) ON(B,C)CHECK

C A

B UNSTACK(C,A)PUTDOWN(C)PICKUP(A)STACK(A,B) UNSTACK(A,B)PUTDOWN(A)PICKUP(B)STACK(B,C)PICKUP(A)STACK(A,B)

C

A

B

UNSTACK(C,A)PUTDOWN(C)PICKUP(B)STACK(B,C)PICKUP(A)STACK(A,B)

Blocks World

• PickUp(X)– X on table, hand empty, X

free

• PutDown(X)– X in hand

• Stack(X,Y)– X in hand, y free

• Unstack(X,Y)– X free, X on Y, hand free

A B

Initial State

AB

Goal State

Blocks World (cont)

Partial Ordered PlanningIntroduction

• A partially ordered plan is a general representation of

plans.

• Idea:– Working parallel on several sub-goals.

– Ordering of goals based on interactions

• Underlying assumption:

– Not many interactions.

• Partially ordered plan = directed graph (AND).

Partial Ordered PlanningAn Example

STRIPS (cont)

Figure 10.1. STRIPS representation for (1) opening a door (2) closing a door.

STRIPS Example

Figure 10.2. Example of STRIPS Planning (Operator Schema & Initial Model).

STRIPS Example (cont)

Figure 10.3. Example of STRIPS Planning (Goal wff and Plan).

1/15/2011 T0264 - Artificial Intelligence 44

» Goal stack planning dalam treeGoal stack planning dalam tree

ONTABLE(D)

CLEAR(C)

ARMEMPTYONTABLE(C)CLEAR(C)

ARMEMPTYON(C,A)

STACK(C,A)

CLEAR(D) HOLDING(B)

GOAL

ON(C,A)ON(B,D)

ONTABLE(A)

CLEAR(A)UNSTACK(B,A)

HOLDING(C)

PICKUP(C) UNSTACK(C,A)

ON(B,A)CLEAR(B)

ARMEMPTY

CLEAR(A) HOLDING(C)STACK(B,D) PUTDOWN(B)

STACK(C,A)

1/15/2011 T0264 - Artificial Intelligence 45

On(B,C)On(B,C)

Start State (KB) : Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B), Empty, Start State (KB) : Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B), Empty,

Empty

Unstack(C,A)

On(C,A) Clear(C)

Clear(C)

Holding (C)

GOALGOAL

Putdown(C)

Linear Planning (Goal Stack)Linear Planning (Goal Stack)

CC

AA BB

On(A,B)On(A,B)

Empty

EmptyEmpty

Ontable(C)Ontable(C)

Clear(A)

Clear(A)Clear(A)

CC

AA

BB

1/15/2011 T0264 - Artificial Intelligence 46

On(B,C)On(B,C)

Start State : Empty, Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B) Start State : Empty, Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B)

Stack(B,C)

Empty

Unstack(C,A)

On(C,A) Clear(C)

Clear(B)EmptyClear(C)

Holding(B)

Pickup(B)

Ontable(B)

Clear(B)

Empty

Holding (C)

GOALGOAL

Putdown(C)

CC

AA BB

On(A,B)On(A,B)

Empty

EmptyEmpty

Ontable(C)Ontable(C)

Clear(C)

Clear(A)

Clear(A)Clear(A)

1/15/2011 T0264 - Artificial Intelligence 47

On(B,C)On(B,C)

Start State : Empty, Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B) Start State : Empty, Ontable(A), On(C,A), Clear(C), Ontable(B), Clear(B)

Stack(B,C)

Empty

Unstack(C,A)

On(C,A) Clear(C)

Clear(B)EmptyClear(C)

Holding(B)

Pickup(B)

Ontable(B)

Clear(B)

Empty

Holding (C)

GOALGOAL

Putdown(C)

CC

AA BB

Stack(A,B)

On(A,B)On(A,B)Clear(A)Clear(A)

Clear(B)Holding(A)

Pickup(A)

EmptyOntable(A)

Clear(A)

Empty

EmptyEmpty

Ontable(C)Ontable(C)

Clear(C)

Clear(A)

Kasus 1

C

A

BA B

C

Start :

ON(C,A) ONTABLE(A) ONTABLE(B) ARMEMPTY

Goal :

ON(A,B) ON(B,C)

• A Very Simple Blocks World Problem

BB E A EA C D C D

Kasus 2

• A Very Simple Blocks World Problem

AC E B DB A D C E

Kasus 3

• Buatlah suatu urutan logika perencanaan• Jika saudara diminta membuat Planning

jadwal “take off” 5 buah pesawat (no. pes. 1, 2, 3, 4, dan 5) yang sedang parkir di hanggar setelah diperbaiki. Kondisi awal urutan parkir pesawat 3, 2, 4, 5, dan 1

• Target pesawat take off dengan urutan 1, 2, 3, 4, dan 5

• Jika perlu tambahkan suatu informasi/ kondisi 3 2 4 5 1 5 4 3 2 1

Initial State Goal State

AI Planning Is Different in PracticeThan it Was in Theory

Unstack(x,y) Pre: on(x,y), clear(x), handempty Del: on(x,y), clear(x), handempty Add: holding(x), clear(y)

• Theory:

– Symbolic computations (STRIPS operators)

– Single agent (the planner)

– Perfect information

• Practice:

– Complex numeric computations(geometry, images, probabilities)

– Multiple agents

– Imperfect information, external information sources

Sampai Jumpa di

Pertemuan 19

Selamat Belajar