Graph Plan
Hello …
Yuk kita bahas kelanjutan dari
postingan sebelumnya untuk memenuhi Tugas 5 No 2 Pada Mata kuliah AI dengan pembahasan Graph plan.
Sebelumnya, Kalian sudah tau apa itu Graph Plan
???
Graphplan adalah algoritma untuk
perencanaan otomatis yang dikembangkan oleh Avrim Blum dan Merrick Furst pada
tahun 1995. Graphplan mengambilInput masalah perencanaan yang dinyatakan
dalam strip dan mengerjakan, jika salah satu memungkinkan, urutan operasi untuk
mencapai keadaan tujuan.
Didalam GraphPlan
terdapat constrain yang dinamakan Mutually Exclusive Action atau Mutex. Mutex
dapat dikatakan Jika dua tindakan tidak dapat dikerjakan secara
paralel kita dapat mengatakan bahwa mereka mutually exclusive atau
mutex. Hubungan mutex akan bervariasi dari lapisan ke lapisan, jadi kita akan
melihat pertanyaan mengenai kapan dua tindakan yang mutex di tingkat
i. Hal ini dapat menjadi kenyataan dalam tiga kondisi yang memungkinkan.
Selain itu terdapat juga mutex yang
lain seperti berikut
Berikut ini Contoh penggunaan Graph Plan
Yang akan saya Bahas : Birthday Dinner Example
Berikut adalah initial
state, goal state, dan aksi aksi yang dapat kita lakukan
Baiklah kita buat GraphPlan nya.
Pertama kita letakkan initial state nya.
Lalu kita masukkan aksi yang dapat
kita lakukan dan hubungkan denganinitial state.
Setelah itu kita masukkan hasil dari
setiap aksi yang bisa kita lakukan.
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:
1.
http://dantikpuspita.com/konsep-dan-pengertian-dasar-graph-graf/
2.
https://en.wikipedia.org/wiki/Graphplan
3.
http://whitenote03.blogspot.co.id/2016/10/penyelesaian-masalah-menggunakan.html
Tidak ada komentar:
Posting Komentar