Graph Plan adalah algoritma yang digunakan untuk perencanaan otomatis yang dikembangkan oleh Avrim Blum dan Merrick Furst pada tahun 1995. Graph Planmengambil input masalah perencanaan yang dinyatakan dalam strip, dan mengerjakan jika salah satu memungkinkan untuk urutan operasi guna mencapai keadaan goal state.
Didalam Graph Plan terdapat constrain yang disebut dengan Mutually Exclusive Action atau Mutex. Mutex dapat diartikan jika dua tindakan tidak dapat dikerjakansecara paralel. Hubungan mutex sangat bervariasi dari lapisan ke lapisan, jadi kita akan memiliki 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 gambar dibawah ini.
Contoh pengaplikasian Graph Plan : Birthday Dinner Example
Berikut adalah initial state, goal state, dan aksi-aksi yang dapat kita lakukan :
Diawali dengan meletakkan initial state nya.
Selanjutnya kita akan memasukkan aksi yang dapat dilakukan dan hubungkan dengan initial state.
Setelah itu kita masukkan hasil dari setiap aksi yang bisa kita lakukan.
Karena sekarang kita telah membuat dasar dalam Graph Plan. Selanjutnya yang harus dilakukan adalah membuat Mutex dari Graph Plan ini. Alasan pertama bahwa tindakan dapat mutex adalah karena efek yang tidak konsisten. Jadi, clean mutexdengan carry, karena carry membuat clean menjadi salah. Begitu pula dengan garbage mutex dengan carry dan dolly karena carry dan dolly membuat garbagesalah. Quite juga mendapatkan efek yang sama dengan dolly karena dolly membuatquite menjadi salah.
Alasan lain mutex dapat terjadi adalah karena adanya gangguan seperti suatu aksi yang 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. Selanjutnya carry dan dolly mutexkarena mereka saling meniadakan prekondisi mereka.
Selanjutnya, setiap preposisi mutex dengan negasi nya. Lalu, alasan lain yang mana kita mungkin memiliki mutex adalah karena dukungan yang tidak konsisten. Jadi, garbage mutex dengan not clean dan not quite karena untuk mendapatkan garbagekita harus membiarkan nya dan ini mutex dengan carry dan dolly. Dinner mutexdengan not clean 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.
Setelah itu kita mulai untuk mendapatkan goals yang kita butuhkan. Pertama-tama 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.
Lalu kita coba dengan menggunakan cara lain, yaitu 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.
Ternyata kita tidak bisa mendapatkan goal dengan cara ini. Untuk itu kita akan menggunakan depth two plan. Yaitu dengan menambahkan dua level lagi pada graph.
Nah pada aksi ini kita mendapatkan mutex sama seperti level sebelumnya.
Selanjutnya pada level ini kita juga akan mendapatkan mutex seperti pada levelsebelumnya. Akan tetapi ada sedikit perbedaan mencolok mutex disini dengan yang ada di level sebelumnya. Yaitu pada level ini dinner tidak mutex dengan carrykarena kita bisa mendapatkan dinner dengan membiarkan nya dan tetap bisa melakukan carry. Begitupun dengan present yang tidak mutex dengan dolly karena kita bisa mendapatkan present dengan membiarkan nya dan dapat tetap melakukandolly.
Setelah kita selesai dengan mutex, selanjutnya kita coba mencari lagi apa yang kita butuhkan dan akhirnya kita berhasil dengan melakukan dengan cara sebagai berikut.
Selesai sudah langkah-langkah dalam pengaplikasian Graph Plan. Sekian dan terimakasih, semoga dapat bermanfaat bagi kalian, saya pribadi, dan kita semua...
Sumber referensi :
