Graph Plan

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)