GraphPlan
Graphplan adalah algoritma untuk perencanaan
otomatis yang dikembangkan oleh Avrim Blum dan Merrick Furst pada tahun 1995.
Graphplan mengambil Input 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
Contoh penggunaan GraphPlan : 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 dengan initial 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.
Source:
en.wikipedia.org/wiki/GraphPlan
Lecture 12 Final Part1 (GraphPlan)
