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