logical agents - share itsshare.its.ac.id/pluginfile.php/1369/mod_resource/content/1/8._pro... ·...

Logical Agents

Chastine Fatichah

Teknik Informatika

Institut Teknologi Sepuluh Nopember

November 2012

12/10/2012 1 / 62 Logical Agents @ Kecerdasan Buatan (KI092301)

Kecerdasan Buatan (KI092301)

Pokok Bahasan

• Knowledge-based agents

• Contoh: Wumpus world

• Logic

• Propositional logic

• Equivalence, validity, satisfiability

• Inference rules dan metode pembuktian

• forward chaining

• backward chaining

• resolution

12/10/2012 2/ 62 Logical Agents @ Kecerdasan Buatan (KI092301)

Outline



• Logic






• resolution

12/10/2012 3 / 62

Logical Agents @ Kecerdasan Buatan (KI092301)

Knowledge bases

• Knowledge base (pengetahuan) = sekumpulan kalimat pada sebuah bahasa formal

• Pendekatan deklaratif membangun agent : • Beritahu informasi yg relevan, simpan dalam KB (Tell)

•

• Agen dapat ditanya (bertanya pd diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB (Ask)

• Agen dapat ditunjukkan level pengetahuan Contoh: apa yg mereka ketahui, bagaimana implementasinya

Atau level implementasi • Contoh: struktur data pada KB dan algoritma-algoritma yang

memanipulasi

12/10/2012 4 Logical Agents @ Kecerdasan Buatan (KI092301)

Knowledge-based Agent

• Agen harus dapat: • Merepresentasikan state, action, dll.

• Menerima informasi baru

• Mengupdate representasi

• Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property)

• Menyimpulkan action apa yang perlu diambil


Outline



• Logic






• resolution


Wumpus World Performance measure

emas +1000, mati -1000

gerak -1 , panah -10

Environment

Squares adjacent to wumpus are smelly

Squares adjacent to pit are breezy

Glitter iff gold is in the same square

Shooting kills wumpus if you are facing it

Shooting uses up the only arrow

Grabbing picks up gold if in same square

Releasing drops the gold in same square

Sensors: Stench, Breeze, Glitter, Bump, Scream

Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot


Karakteristik Wumpus world

• Fully Observable No – hanya local persepsi

• Deterministic Yes – keluaran yg bisa

dispesifikasikan secara tepat

• Episodic No – sequential pada level aksi

• Static Yes – Wumpus dan Pits tidak bergerak

• Discrete Yes

• Single-agent? Yes – Wumpus mmepunyai fitur

alami


Exploring a wumpus world


Logic

• Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat

• Syntax mendefinisikan kalimat-kalimat pada bahasa

• Semantics mendefinisikan arti kalimat; misal, mendefinisikan kebenaran sebuah kalimat

• Contoh, bahasa aritmatika • x+2 ≥ y is a sentence; x2+y > is not a sentence

• x+2 ≥ y is true iff the number x+2 is no less than the number y

• x+2 ≥ y is true in a world where x = 7, y = 1

• x+2 ≥ y is false in a world where x = 0, y = 6

•


Entailment

• Entailment artinya bahwa sesuatu mengikuti dari yang lain

KB ╞

•

• Knowledge base KB entails kalimat α jika dan hanya jika α adalah true pada semua dunia dimana KB bernilai true

• Misal, KB “the Giants won” dan “the Reds won” entails “Either the Giants won or the Reds won”

• Misal, x+y = 4 entails 4 = x+y

• Entailment adalah sebuah hubungan antar kalimat ( syntax) yang didasarkan pada semantics


Models

• m adalah sebuah model pada sebuah kalimat α jika α bernilai true pada m

• M(α) adalah kumpulan semua model pada α

•

• KB ╞ α iff M(KB) M(α) • Misal:

• KB = Giants won and Reds won

• α = Giants won

•


Entailment pada wumpus world

Situasi setelah deteksi

nothing in [1,1], moving

right, breeze in [2,1]

Kemungkinan semua model

pada KB yang

mengasumsikan hanya

ada pits

3 Boolean terpilih 8

possible models


Wumpus models


Wumpus models

• KB = wumpus-world rules + observations

• 12/10/2012 22 Logical Agents @ Kecerdasan Buatan (KI092301)

Wumpus models


• α1 = "[1,2] is safe", KB ╞ α1, proved by model checking

•

•


Wumpus models



Wumpus models


• α2 = "[2,2] is safe", KB ╞ α2


Inference

• KB ├i α = kalimat α dapat diderivasi dari KB dengan prosedur I

• Soundness: i adalah sound jika KB ├i α, bernilai juga benar pada KB╞ α

• Completeness: i adalah complete jika KB╞ α, bernilai juga benar pada KB ├i α

•


Propositional logic: Syntax

• Propositional logic adalah logika paling sederhana – menggambarkan ide dasar

• Simbol proposisi P1, P2 dll adalah sebuah kalimat

• If S is a sentence, S is a sentence (negation)

•

• If S1 and S2 are sentences, S1 S2 is a sentence (conjunction)

•

• If S1 and S2 are sentences, S1 S2 is a sentence (disjunction)

•

• If S1 and S2 are sentences, S1 S2 is a sentence (implication)

•

• If S1 and S2 are sentences, S1 S2 is a sentence (biconditional)


Logika Propositional: Semantics

Tiap model menspesifikasikan true/false untuk setiap simbol proposisi

Misal:P1,2 P2,2 P3,1

false true false

Dengan simbol ini, 8 possible models, dapat digenerate secara otomatis

Rule untuk mengevaluasi nilai kebenaran dengan model m:

S is true iff S is false

S1 S2 is true iff S1 is true and S2 is true

S1 S2 is true iff S1is true or S2 is true

S1 S2 is true iff S1 is false or S2 is true

i.e., is false iff S1 is true and S2 is false

S1 S2 is true iff S1S2 is true andS2S1 is true

Proses recursif sederhana mengevaluasi sebuah kalimat, misal

P1,2 (P2,2 P3,1) = true (true false) = true true = true


Tabel kebenaran untuk

konektifitas


Kalimat pada Wumpus world

Let Pi,j be true if there is a pit in [i, j].

Let Bi,j be true if there is a breeze in [i, j].

P1,1

B1,1

B2,1

• "Pits cause breezes in adjacent squares” B1,1 (P1,2 P2,1)

B2,1 (P1,1 P2,2 P3,1)


Tabel Kebenararan untuk

inference


Inference dengan enumeration

• Untuk n symbol, waktu kompleksitas adalah O(2n), space

kompleksitas adalah O(n)


Logical equivalence

• Dua kalimat adalah logically equivalent iff bernilai true

pada model yang sama: α ≡ ß iff α╞ β and β╞ α


Validity dan satisfiability

Sebuah kalimat adalah valid jika bernilai true pada semua model,

Misal, True, A A, A A, (A (A B)) B

Validity dihubungkan ke inference melalui Deduction Theorem:

KB ╞ α if and only if (KB α) is valid

Sebuah kalimat adalah satisfiable jika bernilai true pada beberapa model Misal: A B, C

Sebuah kalimat adalah unsatisfiable jika bernilai salah pada semua model Misal: AA

Satisfiability dihubungkan ke inference melalui : KB ╞ α if and only if (KB α) is unsatisfiable


Resolution Conjunctive Normal Form (CNF)

conjunction of disjunctions of literals

clauses

E.g., (A B) (B C D)

• Resolution inference rule (for CNF):

•

li … lk, m1 … mn

li … li-1 li+1 … lk m1 … mj-1 mj+1 ... mn

dimana li dan mj adalah complementary literals.

Misal: P1,3 P2,2, P2,2

P1,3


Resolution

Soundness of resolution inference rule:

(li … li-1 li+1 … lk) li

mj (m1 … mj-1 mj+1 ... mn)

(li … li-1 li+1 … lk) (m1 … mj-1 mj+1 ... mn)


Konversi ke CNF

B1,1 (P1,2 P2,1)β

1. Eliminate , replacing α β with (α β)(β α). (B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)

2. Eliminate , replacing α β with α β. (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

3. Move inwards using de Morgan's rules and double-negation: (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

4. Apply distributivity law ( over ) and flatten: (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)


Algortima Resolution


Resolution example

• KB = (B1,1 (P1,2 P2,1)) B1,1 α = P1,2

•


Forward and backward chaining

• Horn Form (restricted) KB = conjunction of Horn clauses

• Horn clause = • proposition symbol; or

• (conjunction of symbols) symbol

• E.g., C (B A) (C D B)

•

• Modus Ponens (for Horn Form): complete for Horn KBs

•

α1, … ,αn, α1 … αn β

β

• Can be used with forward chaining or backward chaining.

• These algorithms are very natural and run in linear time


Forward chaining

• Ide: sembarang rule yang memiliki premise yang satisfy

dalam KB,

• Tambahkan kesimpulan ke KB, sampai query ditemukan


Algortima Forward chaining


Contoh Forward chaining


Forward chaining example


Backward chaining

Ide: bekerja backwards dari query q:

membuktikan q dengan BC,

cek jika q sudah diketahui, atau

buktikan dengan BC semua premise pada beberapa rule concluding q

Avoid loops: chek jika subgoal baru sudah siap pada stack tujuan

Avoid repeated work: check if new subgoal

telah terbukti benar, atau

telah gagal


Contoh Backward chaining


12/10/2012 Logical Agents @ Kecerdasan Buatan (KI092301) 62

Sumber :

1.Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/

http://aima.cs.berkeley.edu/

logical agents - share itsshare.its.ac.id/pluginfile.php/1369/mod_resource/content/1/8._pro... ·...

Documents