Planning : Shopping (POP) dan Brithday Dinner (Graph Plan)

Planning berbeda dengan Search-Based Problem Solving dalam hal representasi goals, states, dan actions, juga berbeda dalam representasi dan pembangunan urutan-urutan action. Planning berusaha untuk mengatasi kesulitan-kesulitan yang dialami dalam Search-Based Problem Solving.

Planning adalah suatu metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satudemi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadisebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.

Contoh permasalahan Planing yaitu :

 Cara Partially Ordered Plan (Shopping)

Pertama kita buat urutannya dari awal sampai akhir atau goalnya. Pada gambar diatas terdapat beberapa langkah, yaitu langkah “Buy(Drill)” untuk membeli bor, “Buy(Milk)” untuk membeli susu, “Buy (Bananas)” untuk membeli pisang.

Untuk “Buy (Drill)” langkah membeli bor berada pada “GO (HWDW)” atau pergi ke toko peralatan, sedangkan untuk “Buy(Milk)” dan “Buy (Bananas)” membeli susu dan pisang lankahnya yaitu “GO (SM) atau pergi ke supermarket.

Kita coba dengan menggunkan langkah (x1) yaitu langkah membeli bor yang berada toko peralatan, Kita memulai start dari (Home) rumah.

Lalu kita buat  langkah (x2) yaitu langkah membeli susu dan pisang yang berada di Supermarket, Kita memulai start dari (Home) rumah.

Kita perhatikan pada gambar ternyata langkah yagn kita tentukan sebelunnya memakan waktu banyak karena setelah langkah (x1) selasai kita harus kembali lagi kerumah (Home) untuk melanjutkan langkah (x2), itu akan mamakan waktu dan menjadi tidak efektif.

Oleh karena itu kita hapus lankah (x2) yang (Home) dari rumah, dan menggantinya dengan langkah (x2) baru yaitu setelah mambeli bor “Buy (Drill)” dari Toko peralatan “GO (HDW)” langsung menuju Supermarket “GO (SM)” untuk membeli Susu dan pisang. Maka tujuan kita terpenuhi. Mungkin masih banyak langkah yang lebih cepat dari contoh diatas tergantung penampatan langkah mana yang di ambil.

Untuk Contoh yang kedua yaitu :

Soal2

Cara Graph Plan (Birthday Dinner)

Langkah pertama kita buat GraphPlan, Kemudian kita letakkan initial state nya.

Kemudian kIta buat kotak aksi, dan menyesuaikannya dengan initial state nya.

Oke kita telah membuat dasar dalam GraphPlan. Selanjutnya kita akan membuat Mutex dari GraphPlan ini. Alasan pertama bahwa tindakan dapat mutex adalah karena efek yang tidak konsisten. Jadi, clean mutex dengan carry karena carry membuat clean menjadi salah. Begitu pula dengan garbage mutex dengan carry dan dolly karena carry dan dolly membuat garbage salah. Quite juga mendapatkan efek yang sama dengan dolly karena dolly membuat quite menjadi salah.

Alasan lain Mutex dapat terjadi karena adanya gangguan : suatu aksi meniadakan prekondisi dari aksi yang lain. Carry Mutex dengan cook karena hasil dari carry meniadakan prekondisi dari cook. Dolly mutex wrap karena hasil dari dolly meniadakan prekondisi dari wrap. Selanjtnya carry dan dolly mutex karena mereka saling meniadakan prekondisi mereka.

Kemudian, setiap preposisi mutex dengan negasi nya. Lalu, alasan lain kita mungkin memiliki mutex adalah karena dukungan tidak konsisten. Jadi, garbage mutex dengan not clean dan note quite karena untuk mendapatkan garbage kita harus membiarkan nya dan ini mutex dengan carry dan dolly. Dinner mutex dengan not celan karena cook dan carry mutex pada level sebelumnya. Present mutex dengan not quite karena warp dan dolly mutex pada level sebelumnya. Begitupula dengan not clean dan not quite karena carry dan dolly mutex pada level sebelumnya. Itulah mutex yang bisa kita dapatkan

 

Kita mulai untuk mendapatkan goals yang kita butuhkan. Pertama kita akan mendapatkan not garbage, kita menggunakan aksi carry, lalu kita mencoba mendapatkan dinner dengan aksi cook satu satunya aksi untuk mendapatkan dinner. Tetapi cook dan carry adalah mutex jadi kita tidak dapat menggunakan aksi tersebut.

Kita coba menggunakan cara lain. Kita akan mendapatkan not garbage dengan aksi dolly, lalu kita dapat mendapatkan dinner menggunakan cook, tetapi kita tidak dapat mendapatkan present dengan satu satu nya cara mendapatkan present yaitu warp, karena warp dengan dolly merupakan mutex.

Kita tidak bisa mendapatkan goal dengan cara ini. Untuk itu kita menggunakan depth two plan. Yaitu dengan menambahkan dua level lagi pada graph.

Pada aksi ini kita mendapatkan mutex sama seperti level sebelumnya.

Pada level selanjutnya kita juga mendapatkan mutex seperti pada level sebelumnya. Tetapi ada sedikit perbedaan mutex disini dengan di level sebelumnya. Pada level ini dinner tidak mutex dengan carry karena kita bisa mendapatkan dinner dengan membiarkan nya dan tetap bisa melakukan carry. Begitupun dengan present tidak mutex dengan dolly karena kita bisa mendapatkan present dengan membiarkan nya dan dapat tetap melakukan dolly.

Setelah kita selesai dengan mutex kita coba mencari lagi apa yang kita butuhkan dan akhirnya kita berhasil dengan melakukan cara nya sebagai berikut

Referensi :

https://adubiyung.wordpress.com/

Lecture 11 FinalPart1 (Partially Order Plan)

Lecture 12 Final Part1 (GraphPlan)

Read More

Constraint Satisfaction Problems (CSP) Game Sudoku

Constraint Satisfaction Problems merupakan pengertian problem matematika yang dijadikan sebagai sekumpulan objek yang harus memenuhi beberapa batasan. CSP juga mewakili mewakili entitas dalam masalah sebagai sekumpulan kendala terbatas yang homogen terhadap variabel, yang diselesaikan oleh metode constraint satisfaction. CSP merupakan subjek dari riset intensif dalam artificial intelligence dan operations research, sejak sejak regularitas dalam formula mereka melengkapi basis dari analisis dan menyelesaikan masalah dari banyak unrelated family. CSP sering menunjukan kompleksitas yang tinggi, membutuhkan kombinasi dari metode heuristics dan combinatorial search untuk diselesaikan dalam waktu yang wajar. Boolean satisfiability problem (SAT), Satisfiability Modulo Theories (SMT) dan Answer set Programming (ASP) secara kasar dapat dianggap sebagai beberapa bentuk dari Constraint Satisfaction Problem.

Contoh masalah simpel yang dapat dibentuk menjadi Constraint Satisfaction Problem,

- Eight queens puzzle ,

- Map coloring problem ,

- Crosswords, Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato dan masih banyak yang lainnya.

Game Sudoku juga termaksuk contoh dari CSP, Sudoku dikenal sebagai Number Place atau Nanpure, adalah sejenis teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

Untuk memecahkan teka-teki Sudoku, dapat digunakan Algoritma Backtracking

(runut-balik). Algoritma ini merupakan perbaikan dari Algoritma Brute Force, dimana solusi dapat ditemukan dengan penelusuran yang lebih sedikit dan dapat mencari solusi permasalahan secara lebih efektif karena tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang perlu dipertimbangkan.

Komponen Constraint Satisfaction Problem pada Game Sudoku :

> Variabel : Angka 1-9.

> Domain : Terdapat 9x9 kotak.

> Constraint : Mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

Definisi masalah pada game Sudoku tersebut yaitu:

A.)  Initial state ( keadaan awal).

Sudoku terdiri dari 3x3 kotak, masing-masing terbagi lagi menjadi 9x9 kotak lebih kecil yang terdapat beberapa angka 1-9 secara acak.

B.) Successor function.

Mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

C.) Goal test.

Akhir pada game Sudoku semua kotak terisi penuh dengan angka tanpa ada angka yang sama.

D.) Path cost.

Pada game Sudoku terdapat 9 proses untuk menyelesaikan game.

1.) Pencarian sel yang kosong.

Sel pertama yang kosong adalah pada baris ke-1 kolom ke-2.

2.) Angka yang akan diisikan adalah 1,2,3,4,5,6,7,8,9.

3.) Pencarian kandidat angka yang akan diisikan.

Kandidat angka yang mungkin adalah sebagai berikut:

Baris ke-1, kolom ke-2 (S1,2)

a. Kandidat yang mungkin pada baris ke-1, B={3,6,9}

b. Kandidat yang mungkin pada kolom ke-2, K={3,4,7,8,9}

c. Kandidat yang mungkin pada blok ke-1, G={1,5,7,9}

4.) Pengecekan.

Pengecekan dapat direpresentasikan dengan himpunan seperti pada gambar

berikut:

Himpunan A = {3,6,9}

Himpunan B = {3,4,7,8,9}

Himpunan C = {1,5,7,9}

A ∩ B ∩ C = {9}

Jadi, solusinya adalah 9.

5.) Solusi diisikan pada sel tersebut.

6.) Selanjutnya melakukan pencarian sel yang kosong berikutnya yaitu sel pada

baris ke-1 kolom ke-6. Proses dilakukan berulang-ulang sampai didapatkan

solusi untuk sel yang kosong pada baris ke-1:

S1,6 = {6}, S1,9 = {3}

7.) Pencarian solusi pada baris ke-2 akan dihadapkan pada kasus yang berbeda yaitu terdapat himpunan solusi yang lebih dari satu. Dalam hal ini akan dilakukan

backtrack ke kandidat angka yang lain. Hasil pengecekan berupa himpunan

solusi akan disimpan yang kemudian dapat digunakan untuk proses

backtracking.

Pencarian kandidat angka untuk baris ke-2:

S2,2 = {7}, S2,3 = {1,5}, S2,5 = {6,8,9}, S2,6 = {2,6,8,9},

S2,7 = {6,9}, S2,8 = {5,6}, S2,9 = {5}

8.) Selanjutnya dilakukan backtrack berdasarkan himpunan solusi yang telah ada

untuk masing-masing sel. Sehingga didapatkan solusi:

S2,2 = {7}, S2,3 = {1}, S2,5 = {8}, S2,6 = {2}, S2,7 = {9}

S2,8 = {6}, S2,9 = {5}

9.) Proses pencarian solusi dilakukan berulang-ulang sesuai jumlah sel yang masih

kosong sampai seluruh sel terisi oleh angka menurut fungsi pembatas yang ada.

Referensi :

-http://www.sudoku.com/

-https://id.wikipedia.org/

-http://ideatech.stts.edu/proceeding2011/20-000047-01p-INF%20Rina%20P164-177.pdf

-http://sudokuindonesia.blogspot.co.id/

Read More

Soal Bonus : Knapsack Problem

Knapsack problem adalah suatu permasalahan bagaimana memilih objek dari sekian banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek (1,2,3,…) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai probabilitas dari setiap objek (Xi).

Contoh Soal :

KNAPSACK PROBLEM DALAM METODE GREEDY
Diketahui bahwa kapasitas M = 30 kg ,
Dengan jumlah barang n=3

Berat Wi masing-masing barang

(W₁, W₂, W₃) = (28, 25, 20)         
Nilai Pi masing-masing barang
(P₁, P₂, P₃) = (38, 34, 25)
Pilih barang dengan Nilai Profit Maksimal
P1 = …  –> X1 = …
P2 = …  –> X2 =  …
P3 = … –> X3 = …
Pilih barang dengan Berat Minimal
W1 = …  –> X1 = …
W2 = …  –> X2 = …
W3 = …  –>X3 = …
Pilih barang dengan menghitung perbandingan yang terbesar dari Profit dibagi Berat (Pi/Wi) yang diurut secara tidak naik, yaitu :
P1/W1 = … = … –> X1 = …
P2/W2 = … = …  –> X2 = …
P3/W3 = … = …  –> X3 = …

Fungsi Pembatas dicari dengan rumus:  

Tabel berdasarkan elemen dari ke-3 kriteria metode Greedy yaitu:

Nilai profit maksimal = ….

Penyelesaian  :
Pilih barang dengan Nilai Profit Maksimal
P1 = 38 à X1 = 1, dimisalkan sebagai batas atas nilai
P2 = 34 à X2 = 2/15, dihitung dengan Fungsi Pembatas
P3 = 25 à X3 = 0, dimisalkan sebagai batas bawah nilai

Menyelesaikan fungsi pembatas : 

Pilih barang dengan Berat Minimal
W1 = 28 à X1 = 0, sebagai batas bawah
W2 = 25 à X2 = 2/5,dihitung dgn Fungsi Pembatas
W3 = 20 à X3 = 1, sebagai batas atas

Menyelesaikan fungsi pembatas :

Pilih barang dgn menghitung perbandingan yg terbesar dari Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik, yaitu :
P1/W1 = 38/28 à = 1,35 karena terkecil maka X1 = 5/28 
P2/W2 = 34/25 à = 1,36 karena terbesar maka X2 =  1
P3/W3 = 25/20 à = 1,25 dengan Fungsi pembatas X3 = 0

Menyelesaikan fungsi pembatas :

Tabel berdasarkan elemen dari
ke-3 kriteria metode Greedy yaitu :

Nilai profit maksimal adalah 40.8  à diambil dari nilai terbesar.
Dengan cara :

Refernsi:
http://slideplayer.info/slide/3716032/
https://hendryprihandono.wordpress.com/
https://en.wikipedia.org/

Read More

Pembahasan Game 8 Puzzle

8 puzzle merupakan salah satu game yang diimplementasi dari Artificial Intelegence /Kecerdasan Buatan. Dalam proses penyelesaian game ini banyak terdapat algoritma- algoritma pencarian yang dapat diterapkan. Permasalahan pada game 8 puzzle adalah bagaimana cara agar dapat menyusun petak- petak puzzle sesuai dengan urutann yang sudah di acak letaknya.

Untuk menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic Search.

Ada 2 cara untuk menentukan permasalahan pada game 8 puzzle yaitu:

1.)  Jumlah dari petak- petak yang salah tempat.

2.)  Total jarak Manhattan (jumlah petak- petak dari lokasi yang seharusnya untuk setiap tile).

Mari kita coba cara yang pertama dulu.

1.)  Jumlah dari petak- petak yang salah tempat.

Pada gamabar tersebut, banyak petak yang salah tempat ada 6 buah.

Kita mulai menyelesaikan puzzle ini dengan patokan pada petak- petak kosong, jika kita lihat ada 3 pilihan yang dapat kita lakukan.

a.)  Jika UP petak 7 jika kita hitung jumlah petak yang salah tempat = 7 buah.

b.)  Jika DOWN petak 1 jumlah petak yang salah tempat = 7 buah.

c.)  Jika LEFT petak 4 jumlah petak yang salah tempat = 5 buah. 

Pilihanan yang kita ambil yaitu langkah yang kesalahannya kecil yang di ambil.

Langkah selanjutnya ada 3 kemungkinan yang dapat kita ambil.

a.)  Jika DOWN petak 8 ,maka jumlah petak yang salah tempat = 5 buah.

b.)  Jika UP petak 6 ,maka jumlah petak yang salah tempat = 5 buah.

c.)  Jika LEFT petak 3 ,maka jumlah petak yang salah tempat = 5 buah.

Karena semuanya memiliki jumlah salah yang sama ,maka kita bebas memilih mana saja ,disini kita pilih petak yang a kita pindahkan. Sehingga posisi menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.)  Jika RIGHT petak 1 ,maka jumlah petak yang salah tempat = 6 buah.

b.)  Jika LEFT petak 2 ,maka jumlah petak yang salah tempat = 4 buah.

Kita pilih yang paling kecil yaitu pilihan b. Sehingga puzzle menjadi.

Kemudian Kita pindahkan petak 3 keatas maka = 3 kesalahannya.

Kembali muncul pilihan.

a.)  Jika RIGHT petak 8 ,maka jumlah petak yang salah tempat = 3 buah.

b.)  Jika UP petak 5 ,maka jumlah petak yang salah tempat = 3 buah.

Karena semuanya memiliki jumlah salah yang sama ,maka kita bebas memilih mana saja ,disini kita pilih petak yang a kita pindahkan. Sehingga menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.)  Jika LEFT petak 4 ,maka jumlah petak yang salah tempat = 4 buah.

b.)  Jika UP petak 6 ,maka jumlah petak yang salah tempat = 3 buah.

Kita ambil pilihan yang b ,Sehingga menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.)  Jika LEFT petak 5 ,maka jumlah petak yang salah tempat = 3 buah.

b.)  Jika RIGHT petak 7 ,maka jumlah petak yang salah tempat = 4 buah.

 Maka kita ambil yang a ,Sehingga menjadi.

Tidak ada pilihan lagi jadi kita DOWN petak 8 , maka menjadi.

Lalu terdapat 2 pilihan yaitu :

a.)  Jika DOWN petak 3 ,maka jumlah petak yang salah tempat = 2 buah.

b.)  Jika RIGHT petak 6 ,maka jumlah petak yang salah tempat = 4 buah.

Kita pilih yang a ,Sehingga menjadi.

Kemudian Kita pindahkan petak 5 keatas maka = 1 kesalahannya.

Dan yang terakhir LEFT petak 8 ,sehingga semua petak- petak tidak memiliki kesalahan.

Mari kIta coba cara yang ke 2 yaitu dengan menentukan total jarak Manhattan (jumlah petak- petak dari lokasi yang seharusnya untuk setiap tile). Hampir sama dengan cara yang ke 2 tetapi ini dengan menentukan petak ke lokasi yang benar. Lihat gambar dibwah ini.

Refernsi:

http://kuliahkusayang.blogspot.co.id/

http://andiktaufiq.wordpress.com/

*Note Post ini untuk tugas AI 5B

Read More