Teknik Planning

            Menyelesaikan Masalah dengan Planning 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 satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah 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 timbul di 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: Rangkaian operator 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 implementasi dan biaya komputasi, GSP lebih unggul dibanding CP. Sedangkan, dari segi efisiensi Rencana 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 segi waktu yang tersedia.

Dua syarat untuk melakukan dekomposisi di atas adalah :

  • Menghindari penghitungan ulang dari seluruh state masalah ketika terjadi perubahan dari 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 hampir benar menjadi benar dilakukan jika teknik yang dipakai dalam pencarian solusi hanya menghasilkan rangkaian solusi yang hampir benar. Perencana kemudian akan mengaplikasikan suatu metode tertentu untuk membuat solusi yang hampir 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

 

 


Ref: Suyanto Book.