Penyelesaian Masalah menggunakan Partially Order Plan dan 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 satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.

Dalam Bahasan ini kita akan membahas penyelesaian suatu contoh kasus  permasalahan Planning dengan menggunakan Partial order planning dan Graph Plan.

Permasalahan pertama:

Shopping (menggunakan algoritma Partial order Planning)

Langkah penyelesaian:

Tahap awal yaitu membuat langkah dari awal sampai ke finish seperti pada gambar diatas.

Tahap selanjutnya menambahkan go(HDW) sebagai (X1) untuk mencapai untuk mencapai at(HDW) dan menambahkan go(SM) sebagai (X₂) untuk mencapai at(SM).

Langkah selanjutnya kita bisa menjalankan langkah actian go(X₁) dan precond Go(HDW), dengan menggunakan effect at(Home). Serta menjalankan langkah action go(X₂) dan precond Go(SM), dengan menggunkan effect at(Home) seperti gambar diatas.

Setelah selesai dengan langkah sebelumnya, kita harus memperhatikan masalah apa saja yang mungkin terjadi yang bisa kita lihat pada gambar diatas. Pada gambar diatas, masalah terjadi dapat kita lihat pada bulatan yang ditunjuk oleh tanda panah, kita dapat memperhatikan bahwa Go(SM) tidak bisa tersambung ke at(Home) sebagai akibat sudah dimiliki oleh at(X₁), dan juga berlaku sebaliknya untuk Go(HDW).

\

Solusi yang dapat kita ambil, mungkin kita bisa memerlukan Go(SM) terjadi setelah Go(HDW). Kita bisa memutuskan untuk memenuhi at(X₂) dengan hasil at(HDW) Go(HDW) dan at(HDW) Go(HDW), tetapi jika kita menuju at(HDW) Go(HDW) kita tidak bisa menuju at(HDW) Sells(HDW,D).

Solusi yang dapat kita ambil dengan menempatkan Go(SM) antara GO(HDW) dan at(HDW) yang ditunjukan oleh tanda panah pada gambar diatas. Tetapi jika seperti itu kita harus menuju dua kali ke Go(HDW) karena sehabis ke Go(HDW) kita menuju Go(SM) dan balik lagi ke Go(HDW) untuk Buy(Drill).

Solusi yang dapat diambil dengan meletakan Go(SM) terjadi setelah Buy(Drill). Dengan menandakan nya dengan garis putus putus berwarna merah untuk memastikan bahwa hal ini terjadi.

Setelah kita berada di GO(SM) kita bisa Buy(Milk) dan Buy(Bananas) dan terakhir menuju at(Home).

Permasalahan kedua:

Birthday Dinner(menggunakan algoritma Graph Plan)

Langkah Penyelesaian:

Langkah awal dengan meletakkan di kondisi awal.

Masukan action yang dapat dilakukan dan hubungkan dengan Initial State.

Setelah itu, kita masukan hasil dari action yang dapat kita lakukan.

Selanjutnya, kita akan membuat mutex dari Graph Plan ini, alasannya bahwa tindakan dapat mutex adalah karena efek yang tidak konsisten. Dapat dilihat Clean mutex dengan Carry membuat Clean menjadi salah. Begitu juga dengan Garbage mutex dengan Carry dan Dolly membuat Garbage menjadi salah. Begitu juga dengan Quiet mutex dengan Dolly membuat quiet menjadi salah.

Alasan lain dari mutex adalah karena adanya gangguan: suatu action meniadakan precondition dari action lain. Dapat dilihat Carry mutex dengan Cook dan Dolly dan meniadakan precondition hasilnya, begitu juga dengan Wrap mutex dengan Dolly dan meniadakan precondition hasilnya

Pertama-tama, setiap proposisi mutex dengan bentuk yang negatif. Kemudian Karena alasan lain dari mutex adalah karena dukungan tidak konsisten. Jadi, Garbage mutex dengan not Clean dan not Quiet (karena untuk mendapatkan Garbage kita harus mempertahankan itu, yang mutex dengan Carry dan Dolly). Dinner mutex dengan not Clean (karena Cook dan Carry mutex pada level sebelumnya). Present mutex dengan not Quiet (karena Warp dan Dolly mutex pada level sebelumnya). Begitu juga dengan not Clean dan not Quiet (karena Carry dan Dolly mutex pada level sebelumnya).

Kita coba dengan cara lain, kita akan mendapatkan not Garbage dengan action Carry, dan Dinner dengan action Cook, tetapi Carrry dan Cook mutex jadi gagal.

Kita coba dengan cara lain, kita akan mendapatkan not Garbage dengan action Dolly, dan Dinner dengan action Cook, serta Present dengan action Wrap, tetapi Doly dan Wrap mutex.

Dikarenakan tidak ada cara lain untuk mendapatkan goal kita akan menggunakan depth two plan, yaitu menambahkan dua level lagi pada Graph.

Pada tahap ini kita mendapatkan mutex sama seperti di level sebelumnya

Pada level ini kita juga mendapatkan mutex yang sama dengan level sebelumnya, tetapi terdapat perbedaan yaitu pada level ini Dinner tidak mutex dengan Carry,karena kita bisa mendapatkan Dinner dengan membiarkannya dan tetap bisa melakukan Carry. Begitu juga dengan Present tidak mutex dengan Dolly karena kita bisa mendapatkan Present dengan membiarkannya dan dapat tetap melakukan Dolly.

Setelah kita selesai dengan mutex kita mencari lagi dengan cara seperti gambar diatas dan akhirnya dapat berhasil dengan cara seperti yang ditunjukan oleh gambar diatas.

Referensi :

Lecture11FinalPart1.pdf

Lecture12FinalPart1.pdf

Ihzhadamy.blogspot.com

Read More

Persoalan Cryptarithmetic menggunakan Algoritma Backtracking

Cryptarithmetic merupakan pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan huruf-huruf alfabet atau symbol lain. Cryptarithmetic termasuk salah satu persoalan CSP (Constraint Satisfaction Problem) yang bisa diselesaikan menggunakan algoritma backtracking.

Backtracking adalah algoritma berbasis DFS (Depth First Search) untuk mencari solusi persoalan secara lebih tepat. Pada algoritma backtracking tidak perlu memeriksa semua kemungkinan solusi yang ada, hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Dengan proses seperti ini maka perfomansi akan lebih baik karena akan menghemat waktu pencarian.

Cryptarithmetic merupakan contoh yang sangat cocok untuk CSP, karena selain menyediakan deskripsi, masalah cryptarithmetic dapat dijelaskan lebih baik dengan constraint-constraint.

Constraint-constraint yang mendefinisikan sebuah cryptarithmetic problem antara lain :

<>  Masing-masing huruf atau symbol merepresentasikan digit yang hanya satu dan unik dalam persoalan tersebut.

<>  Ketika digit-digit menggantikan huruf atau simbol, maka hasil dari operasi aritmatika harus benar.

Batasan-batasan di atas memunculkan beberapa batasan baru dalam persoalan, yaitu apabila basis dari angka adalah 10, maka pasti akan ada paling banyak 10 simbol atau huruf yang unik dalam persoalan. Jika tidak, maka tidak akan mungkin untuk memberikan digit yang unik ke setiap huruf atau simbol yang unik juga dalam persoalan. Dan supaya memiliki makna yang berarti secara semantik, angka tidak boleh dimulai dengan 0, jadi huruf-huruf yang muncul untuk setiap variabel pertama sekali seharusnya tidak boleh mengandung 0.

Contoh Persoalan Cryptarithmetic :

Solusi persoalan Cryptarithmetic dengan CSP dengan menggunakan algoritma Backtracking

Variabel      : {M, O, S, E, N, R, D, Y, X₁, X₂, X₃}

Domain       : D_i = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Constraint  : D + E         = Y + 10 * X₁

                         X₁ + N + R = E + 10 * X₂

                         X₂ + E + O = N + 10 * X₃

                         X₃ + S + M = O + 10 * M

Initial State, Setiap variabel masih berbentuk huruf atau symbol.

Successor, Pemberian digit atau nilai kepada setiap variabel, tetapi setiap digit atau nilai harus berbeda untuk setiap variabel.

Path Cost, Jumlah pencarian solusi permasalahan agar mencapai goal state.

Goal State,  Setiap variabel sudah memiliki nilai yang memenuhi semua constraint yang telah ditetapkan untuk persoalan.

Solusi :

=>  S + M = O nilai S dan M harus berkisar diantara [0-9], karena hanya 1 digit. Maka nilai M adalah 1 (M = 1) karena S + M + X₃ tidak bisa lebih besar dari 19.

=>  Karena M = 1, maka (S + 1 + X₃ = 1(M)O) nilai S adalah 8(+1) atau 9 agar didapat 2 digit nilai (10 atau 11). 8(+1) maksudnya 8 ditambah nilai X₃.

=>  Nilai O adalah 0 karena S + (M = 1) + X₃ harus bernilai 10 supaya didapat 2 digit. Nilai 11 bisa didpat kalau menggunakan S = 9 dan X₃ = 1, tapi nilai 1 sudah buat M, karena itu nilai O tidak boleh 1.

=>  Kemungkinan pertama : S = 8, X₃ = 1, O = 0

<> E + O = N, nilai E + O harus bernilai 10 agar bisa didapat nilai X₃ = 1

<>  X₂ + E + O = N, (1+) + (E = 9) + (O = 0) = (1)N, maka 10 = (1)N, maka    N = 0, hal ini menciptakan kesalahan karena nilai N = O, jadi kemungkinan ini salah.

=>  Kemungkinan kedua : S = 9, X₃ = 0, O = 0

<> E + O = N, X₂ + E + O = N, maka nilai X₂ harus 1 karena nilai E tidak boleh sama dengan N.

<> Didapat persamaan 1 + E + 0 = N, maka N = E + 1.

=>  Karena nilai pasti tidak dapat, maka kita menjalan kemungkinan pertama.

=>  N + R = E (hasil disini harus bernilai belasan agar X₂ = 1) D + E = Y.

=>  kemungkinan pertama sudah dijalankan, tapi tidak ketemu nilai variabel, karena itu kita jalankan kemungkinan kedua.

=>  Kita mulai dengan tebakan Kalo E = 2, maka N = 3. Pemilihan nilai E, karena  variabel E paling banyak muncul dan paling banyak berinteraksi dengan huruf lain. X₁ + N + R = (1)E, X₁ + 3 +R = (1)2, berapa nilai           X₁ + R + 3 agar di dapat nilai 12?

<> Jawabannya X₁ = 1, R = 8. Lalu kita masukan ke persamaan lanjutan, D + E = Y (hasil disini harus belasan agar di dpat X₁ = 1), D + 2 = Y, dari sini didapatkan kesimpulan bahwa kemungkinan ini tidak mungkin, karena sebesar apapun nilai D + 2 tidak akan mencapai nlai belasan.

=>  Kita lanjutkan tebakan jika E = 3, maka N = 4, (X₁ + N + R), X₁ + 4 + R = (1)3, berapa X₁ + R + 4  agar didapat 12? R = 8 dam X₁ =1.

<> Kita masukan ke D + E = (1)Y, kemungkinan ini tidak mungkin karena D + 3 hanya bernilai paling besar 10(D = 7), dan menyebabkan Y = 0 dan menjadi sama dengan nilai O.

=>  Sekarang jika E = 4, maka N = 5, (X₁ + N + R), X₁ + 5 +R = (1)4, berapa  X₁ + 5 + R agar didapat 14? R = 8 dan X₁ = 1.

<>  Kita masukan  ke D + E  = (1)Y kemungkinan ini tidak mungkin karena D(7) + 4 hanya bernilai paling besar 11, dan menyebabkan
Y = 1 dan menjadi sama dengan nilai M.

=>  Sekarang jika E = 5, maka N = 6, (X₁ + N + R), X₁ + 6 + R = (1)5, berapa X₁ + 6 + R agar didapat 15? R = 8 dan X₁ = 1.

<> Kita masukan ke D + E = (1)Y kemungkinan ini mungkin karena  D(7) + 5 bernilai paling besar 12, dan menyebabkan Y = 2. Didapatkan jawaban.

Hasil yang didapat adalah :

M = 1        N = 6       X₁ = 1

O = 0        R = 8       X₂ = 1

S = 9         D = 7      X₃ = 0

E = 5         Y = 2

   

Referensi :

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf.

http://slideplayer.info/slide/5075075/

Read More