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 satudemi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadisebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.

Pengujian keberfungsian suatu metode perencanaan dapat dilakukan pada suatu domain yang dinamakan Dunia Balok (Blocks-World). Dunia Balok dinilai cukup layak sebagai lahan pengujian karena tingkat kompleksitas permasalahan yang mungkin timbuldi dalamnya. Di dalam Dunia Balok dikenal istilah initial-state dan goal-state yang  masing-masing direpresentasikan oleh suatu komposisi dari sejumlah balok. Kemudian,ada satu set operator yang dapat diaplikasikan oleh sebuah tangan robot untuk memanipulasi balok. Permasalahan yang ada di dalam Dunia Balok adalah: Rangkaianoperator seperti apa yang dapat mengubah initial-state menjadi goal-state? Rangkaian operator tersebut biasa disebut sebagai Rencana Penyelesaian

Dua metode perencanaan yang cukup populer dan sudah pernah diuji pada Dunia Balok adalah Goal-Stack-Planning (GSP) dan Constraint-Posting (CP). GSP dan CP memiliki kelemahan dan keunggulan masing-masing. Dari segi kemudahan implementasidan biaya komputasi, GSP lebih unggul dibanding CP. Sedangkan, dari segi efisiensiRencana Penyelesaian yang dihasilkan, CP pada umumnya lebih unggul dibanding GSP.

Tetapi, dari seluruh kemungkinan permasalahan yang timbul pada Dunia Balok,meskipun GSP dan CP mampu menghasilkan rencana-rencana penyelesaian, namun rencana-rencana penyelesaian yang dihasilkan pada umumnya tidak efisien[RIC91]. Padahal, rencana penyelesaian yang efisien adalah salah satu hal yang penting, terutama pada sistem-sistem raksasa. Pada domain tertentu, pemecahan masalah menggunakan komputer perlu dilakukan dengan cara bekerja pada bagian-bagian kecil dari masalah secara terpisah kemudian menggabungkan solusi-solusi per bagian kecil tersebut menjadi sebuah solusi lengkap dari masalah. Karena, jika hal-hal tersebut tidak dilakukan, jumlah kombinasi state dari komponen masalah menjadi terlalu besar untuk dapat ditangani dipandang dari segiwaktu yang tersedia.

Dua syarat untuk melakukan dekomposisi di atas adalah :

• Menghindari penghitungan ulang dari seluruh state masalah ketika terjadi perubahandari suatu state ke state lainnya.
• Membagi masalah ke dalam beberapa sub masalah yang relatif lebih mudah untuk diselesaikan.

Penggunaan metode-metode yang terfokus pada cara mendekomposisi masalah ke dalam sub-sub masalah yang sesuai dan cara untuk mengingat dan menangani interaksi antar sub masalah ketika terjadi proses penyelesaian masalah tersebut diistilahkan dengan Perencanaan.

Pemecahan masalah dengan menggunakan perencanaan pada umumnya:

• Modus Goal-Directed, yaitu pencarian solusi dilakukan dari kondisi goal-state sampai ke kondisi initial-state yang dapat dicapai.
• Runut-Balik-Terpandu-Kebergantungan (Dependency-Directed-Backtracking) ketika menemukan jalan buntu.

Untuk berpindah dari satu state ke state lainnya, perencana diperkenankan untuk mengaplikasikan sejumlah operator. Sebuah sistem perencanaan pada umumnya perlu untuk mampu:

• Memilih operator
• Mengaplikasikan operator
• Mendeteksi ketika solusi telah tercapai
• Mendeteksi jalan-jalan buntu
• Mendeteksi ketika solusi yang hampir benar telah dicapai dan melakukan teknik khusus untuk membuat solusi tersebut menjadi benar

Pemilihan operator pada umumnya dilakukan dengan:

• Pertama, mengumpulkan kondisi pembeda goal-state dan current –state (current – state adalah suatu state yang menunjukkan kondisi saat ini).
• Kedua, mengidentifikasi operator yang dapat mengurangi perbedaan tersebut.

Pendeteksian bahwa solusi telah ditemukan dilakukan dengan cara menguji rangkaian operator yang telah dihasilkan. Jika rangkaian operator tersebut dapat mengubah kondisi initial-state menjadi goal-state, maka solusi telah ditemukan.

Pendeteksian jalan-jalan buntu dilakukan dengan: jika suatu rangkaian operator menghasilkan state yang diyakini bukan state antara goal-state dan initial-state atau jika kemajuan yang dicapai dianggap terlalu kecil atau menimbulkan permasalahan yang lebih sulit, maka rangkaian operator tersebut dianggap telah menemukan atau akan menuju jalan buntu.

Membuat solusi yang hamper benar menjadi benar dilakukan jika teknik yang dipakai dalam pencarian solusi hanya menghasilkan rangkaian solusi yang hamper benar. Perencana kemudian akan mengaplikasikan suatu metode tertentu untuk membuat solusi yang hamper benar tersebut menjadi benar.

Untuk menghindari pencatatan kondisi keseluruhan di setiap titik persimpangan (node) dalam pencarian solusi, pengaplikasian operator memerlukan tiga daftar predikat untuk mendeskripsikan perubahan kondisi, yaitu:

• PRECONDITION : predikat – predikat yang harus bernilai benar sebelum pengaplikasian operator
• ADD: predikat-predikat yang bernilai benar setelah pengaplikasian suatu operator.
• DELETE : predikat-predikat yang bernilai salah setelah pengaplikasian suatu operator

Ketiga daftar predikat tersebut selanjutnya disebut dengan daftar-PAD

Dunia Balok 

Dunia Balok adalah sebuah domain dengan karakteristik:

• Memiliki sebuah permukaan datar tempat menyimpan balok, umumnya disebut dengan meja.
• Memiliki sejumlah balok kotak yang berukuran sama.
• Memiliki sebuah tangan robot yang dapat memanipulasi balok.Untuk memudahkan pendefinisian kondisi balok pada suatu state dalam.

Dunia Balok digunakan predikat-predikat berikut :

• ON (A, B) – Balok A menempel di atas balok B.
• ONTABLE (A) – Balok A berada di permukaan meja.
• CLEAR (A) – Tidak ada balok yang sedang menempel di atas balok A.

Sedangkan, untuk tangan robot digunakan :

• HOLDING (A) – Tangan robot sedang memegang balok A.
• ARMEMPTY – Tangan robot tidak sedang memegang balok.

Permasalahan yang akan dicari rencana penyelesaiannya adalah permasalahan yang memenuhi spesifikasi berikut:

• Jumlah balok sama.
• Balok yang berada pada initial-state juga berada pada goal-state.
• Kondisi terdefinisi dengan benar.
• Tangan robot tidak sedang memegang balok.

Dalam menyelesaikan sebuah masalah, GSP menggunakan sebuah stack untuk menampung kondisi-kondisi (kondisi goal dan kondisi-kondisi yang mungkin terjadi ketika pencarian solusi) dan operator-operator yang telah diajukan untuk memenuhi kondisi-kondisi tersebut. Juga, tergantung pada sebuah basis data yang menggambarkan current –state dan satu set operator yang dideskripsikan sebagai daftar predikat PRECONDITION, ADD dan DELETE  atau daftar-PAD.

Langkah – langkah menyelesaikan masalah

• Langkah pertama GSP dalam menyelesaikan sebuah masalah adalah menempatkan kondisi-kondisi goal-state pada stack. Kondisi-kondisi tersebut akan disimpan di dalam sebuah slot stack.
• Langkah kedua, mengacu pada current -state, kondisi-kondisi goal-state yang belum tercapai dimasukkan ke dalam stack, masing-masing menempati sebuah slot. GSP tidak memiliki aturan khusus yang mengatur urutan pemasukan ke dalam stack dari kondisi-kondisi yang belum tercapai tersebut
• Langkah ketiga, slot terisi yang berada paling atas pada stack akan diperiksa. Hal-hal yang akan dilakukan bergantung pada kondisi slot tersebut. Kondisi yang mungkin terjadi pada slot tersebut adalah sebagai berikut:

Kondisi 1

Jika slot berisi kondisi yang sudah memenuhi current -state, tetapi slot tidak terletak di dasar stack dan juga tidak terletak di atas slot yang berisi operator, maka isi slotakan di-pop dari stack dan pemeriksaan dilanjutkan pada slot berikutnya.

Kondisi 2

Jika slot berisi kondisi yang belum memenuhi current –state maka isi slot akan di-pop dari stack. Kemudian, sebuah operator yang sesuai untuk mencapai kondisi tersebut akan dimasukkan ke dalam stack. Setelah itu, serangkaian kondisi yang dibutuhkanagar operator itu bisa diaplikasikan akan dimasukkan ke dalam sebuah slot stack. Selanjutnya, setiap kondisi dari rangkaian kondisi yang dibutuhkan operator agar dapat diaplikasikan tersebut akan dimasukkan ke dalam sebuah slot secara terurut, dimana kondisi yang harus dicapai paling akhir dimasukkan pertama kali.

Kondisi 3

Jika slot berisi kondisi atau rangkaian kondisi dan slot tersebut berada di atas slot yang berisi operator, maka isi slot teratas dari stack tersebut akan di-pop. Kemudian, operator pada slot berikutnya akan di-pop dan dimasukkan ke dalam antrian operator dalam rencana penyelesaian dan current –state di-update dengan mengaplikasikan operator tersebut pada current –state berdasarkan daftar-PAD.

Kondisi 4

Jika slot yang diperiksa adalah slot terdasar maka akan diuji kesamaan antara current – state dan  goal-state. Jika sama (berarti goal-state telah tercapai) maka isi slot akan di- pop dan pencarian rencana penyelesaian dihentikan. Jika berbeda (goal-state belum tercapai) maka langkah ke dua diulangi. Jika kondisi yang terjadi bukan kondisi 4,setelah rangkaian tindakan yang bersesuaian dilakukan, langkah ketiga diulangi

GSP mungkin menemui jalan buntu yang disadari (meningkatkan biaya komputasi) atau pun yang tidak disadari (membuat rencana penyelesaian tidak efisien). Jalan buntu yang tidak disadari disebabkan karena GSP tidak memiliki aturan untuk mengurutkan pemasukan kondisi goal-state yang belum tercapai ke alam stack (langkah ke-2).

 

Binus