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

Logika Proposisi (Propositional Logic) menawarkan logika dalam bentuk sederhana sehingga mudah dipahami. Meskipun begitu, Logika Proposisi sudah mampu membantu menarik kesimpulan. Namun, banyak kasus yang muncul akan menjadi terlihat panjang dan rumit saat diwujudkan dalam bentuk Logika Proposisi. Dan itu bisa lebih panjang dan rumit dibandingkan problem itu sendiri.

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu komputer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya kalkulus predikat bisa digunakan untuk memecahkan masalah dalam berbagai keadaan umum yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan.

Filsuf berkebangsaan Jerman yang bernama Gottlob Frege menebitkan The Begriffsschrift, dianggap sebagai asal muasal dari teori logika modern. Akan tetapi, dalam risalat milik Friege ini masih terdapat banyak kekurangan dalam beberapa bagian dan janggal dalam penotasiannnya. Walaupun demikian, penemuan Frege ini tetap diakui. Selain penemuan dari Frege, formulasi dari logika predikat yang sering digunakan sekarang adalah firstorder logic atau yang biasa dikenal dengan kalkulus predikat yang tercatat dalam Principle of Theorical Logic yang ditulis oleh David Hilbert dan Wilhelm Ackerman pada tahun 1928. First order logic dalam hal ini merupakan dasar pendiri logika matematika modern.

Beberapa poin penting yang membedakan kalkulus predikat dengan logika Aristotle diantaranya:

1. Di dalam kalkulus predikat didefinisikan bahwa subjek adalah hanya sebuah individu tidak pernah merupakan sekelompok individu. Karena subjek dalam kalkulus predikat ini hanyalah sebuah individu, maka subjek di sini lebih umum untuk disebutkan sebagai individual.
2. Kalkulus predikat memakai banyak simbol-simbol khusus untuk menotasikan sesuatu. Huruf kecil a, b, c, d, …, z digunakan untuk menyatakan individual. Huruf kapital M, N, P, Q, R, … digunakan untuk menyatakan predikat. Jika terdapat notasi seperti Ma, maka dikatakan bahwa a adalah argument untuk M.
3. Selain huruf kecil dan huruf kapital, kalkulus predikat juga menggunakan beberapa simbol khusus untuk menotasikan operator-operator logika. Beberapa simbol khusus itu adalah: ∧ ∨ ~ ⊃ ≡
4. Sebuah formula adalah ekpresi yang memiliki arti dan dibangun oleh atom-atomnya dan digabungkan dengan menggunakan operatoroperator logika.
5. Kalkulus predikat memiliki kapabilitas yang besar dalam mengekspresikan suatu hal. Banyak pernyataan dalam natural languageyang bisa direpresentasikan dengan baik oleh kalkulus predikat. Hal inilah yang kurang dimiliki oleh logika Aristoteles.

Dalam first-order logic yang paling utama adalah bahwa dunia berisi objek-objek yaitu identitas (ciri-ciri individu) dan sifat (properties) yang membedakan mereka dengan objek yang lain. Diantara objek tersebut, akan dibuat bermacam-macam relasi. Beberapa relasi adalah fungsi yaitu hubungan dimana hanya ada satu nilai untuk satu input. Jadi pada first-order logic mengasumsikan “world” memuat :

– Objek : hal-hal yang berhubungan dengan identitas individu, misalnya : manusia, rumah, teori-teori, warna, mobil, dan lain-lain.

– Sifat (properties): sifat benda yang membedakannya dari benda lain, misalnya: merah, bulat, tipis, dan lain-lain

– Relasi : hubungan antara benda yang satu dengan benda yang lainnya, misalnya: lebih besar dari, lebih kecil dari, memiliki, terjadi setelah, dan lain-lain.

– Fungsi (Functions): merupakan subset dari hubungan di mana hanya ada satu “nilai” untuk setiap “input” yang diberikan, misalnya: ayah dari, teman baik, dan lain-lain.

First Order Logic sangat penting dalam ilmu matematika, filsafat, kecerdasan buatan, karena ruang lingkupnya, sebab keberadaan manusia sehari-hari selalu berhubungan dengan obyek dan hubungan antar manusia sendiri. Sehingga kita tidak dapat menyangkal bahwa dunia ini terdiri dari obyek dan hubungan (relasi).

 

Saya ambil contoh berikut ini. Di sebuah kelas II SD, terdapat 35 siswa. Setiap hari Senin sampai dengan Kamis, mereka mengenakan seragam merah-putih. Sedangkan hari lain, mereka mengenakan seragam pramuka. Anak tetanggaku yang bernama Amin, ada salah satu siswa kelas II SD tersebut. Hari Rabu pagi kami bertemu saat dia berangkat sekolah. Seragam apa yang dia kenakan?

Bagaimana menyelesaikan contoh tersebut dengan menggunakan Logika Proposisi?
Solusi:

Misalkan:

p : amin adalah siswa kelas II SD
q : amin mengenakan seragam merah putih
r : hari rabu

Kalimat yang bisa kita nyatakan dari cerita tersebut adalah

1 : p Λ r → q
2 : p
3 : r

Dengan ekpresi seperti itu, kita sudah bisa menarik kesimpulan tentang Amin. Tetapi banyak informasi yang tidak dinyatakan dan terlewatkan. Akibatnya, ekspresi tersebut tidak bisa digunakan untuk membuat kesimpulan tentang seragam yang dipakai Ali pada hari Rabu jika diketahui bahwa Ali juga seorang siswa kelas SD tersebut. Agar bisa membuat kesimpulan tentang Ali, kita bisa mengubahnya menjadi seperti di bawah ini:

1 : p1 Λ r → q
2 : p1
3 : r
4 : p2 Λ r → q
5 : p2

dengan p1 berarti “amin adalah anak kelas II SD” dan p2 berarti “ali adalah anak kelas II SD”. Bagaimana jika untuk semua siswa? Kita harus menambahkan lagi kalimat nomor 1 dan 2 dengan sebelumnya mengubah p1 menjadi p3. Demikian seterusnya sampai p35. Maka akan diperoleh 71 kalimat. Padahal, solusi ini hanya untuk hari Rabu saja, belum hari-hari yang lain.

 

Predicate: Simbol dengan Parameter

First order Logic menawarkan penggunaan simbol dengan parameter. Simbol ini dikenal sebagai predikat. Sebuah predikat didefinisikan sebagai atribut(sifat) sebuah obyek atau relasi antar obyek. Obyek-obyek tersebutlah yang dijadikan sebagai parameter predikat tersebut.

Sebagai contoh, kita kembali ke contoh sebelumnya. Untuk menyelesaikan contoh tersebut, kita menggunakan simbol p untuk menyatakan atribut seorang siswa kelas II SD, r untuk menyatakan atribut nama hari, dan q untuk menyatakan relasi mengenakan seragam. Definisi lengkap setiap simbol, termasuk parameternya, adalah sebagai berikut:

p(x) : x adalah seorang siswa kelas II SD
r(x) : x adalah nama hari
q(x,y) : x mengenakan seragam y.

Dengan definisi tersebut, jika kita ingin mengungkapkan kalimat amin adalah seorang siswa kelas II SD, hari rabu, dan amin mengenakan seragam pramuka maka dapat dinyatakan sebagai berikut:

p(amin)
r(rabu)
q(amin,pramuka)

Quantifier

Selain penggunaan predikat, First Order Logic juga menawarkan quantifier untuk membuat kalimat logika yang lebih sederhana. Ada 2 jenis quantifier, yaituuniversal dan existential. Quatifier ini berlaku terhadap parameter yang muncul di sebuah kalimat masih dalam bentuk variabel. Universal quantifier terhadap sebuah variabel x (disimbolkan dengan ∀x) berarti bahwa kalimat tersebut berlaku untuk setiap obyek x, sedangkan existential quantifier (disimbolkan dengan ∃x) berarti berlaku untuk sebagian obyek saja.

Contoh: Menggunakan definisi untuk p(x), r(x), dan q(x,y), berikut adalah kalimat-kalimat logika dengan menggunakan quantifier dan artinya:

∀x(p(x) Λ r(rabu) → q(x,merah-putih)) : untuk setiap x, jika x adalah seorang siswa kelas II SD dan pada hari Rabu maka x akan mengenakan seragam merah-putih.

∃x(p(x) → ¬q(x,merah-putih)) : ada x, jika x adalah seorang siswa kelas II SD maka x tidak mengenakan seragam merah putih.

Contoh First Order Logic dan Penarikan Kesimpulan

Lihat kembali contoh seragam Amin di atas. Solusi untuk problem di atas adalah sebagai berikut.

Solusi:

Misalkan:

p(x) : x adalah seorang siswa kelas II SD
r(x) : x adalah nama hari
q(x,y) : x mengenakan seragam y.

Kalimat yang bisa kita nyatakan dari cerita tersebut adalah

1 : ∀x(p(x) Λ r(senin) → q(x,merah-putih))
2 : ∀x(p(x) Λ r(selasa) → q(x,merah-putih))
3 : ∀x(p(x) Λ r(rabu) → q(x,merah-putih))
4 : ∀x(p(x) Λ r(kamis) → q(x,merah-putih))
5 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))
6 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))

Jika diketahui bahwa Amin adalah seorang siswa kelas II SD dan hari rabu, maka ditambahkan kalimat berikut:

7 : p(amin) Λ r(rabu)

Proses penarikan kesimpulan untuk menjawab pertanyaan apa seragam yang dipakai oleh Amin pada hari Rabu adalah sebagai berikut:

8 : p(amin) Λ r(rabu) → q(amin,merah-putih) {Instansiasi x dengan Amin pada kalimat 3}
9 : q(amin,merah-putih) {Modus Ponens antara 7 dan 8}

Arti kalimat 9 adalah Amin mengenakan seragam merah-putih.

—————- []

 

Instansiasi: membuang quantifier dan mengganti kemunculan setiap variabel yang terkait dengan quantifier tersebut dengan sebuah obyek.

Contoh yang lain: Menggunakan contoh seragam siswa kelas II SD di atas, tetapi yang ditanyakan adalah apakah Taufiq seorang siswa kelas II SD jika diketahui dia tidak mengenakan seragam pramuka pada hari Jumat.

Solusi:

Menggunakan definisi sebelumnya, kita tetap memperoleh kalimat logika sebagai berikut:

1 : ∀x(p(x) Λ r(senin) → q(x,merah-putih))
2 : ∀x(p(x) Λ r(selasa) → q(x,merah-putih))
3 : ∀x(p(x) Λ r(rabu) → q(x,merah-putih))
4 : ∀x(p(x) Λ r(kamis) → q(x,merah-putih))
5 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))
6 : ∀x(p(x) Λ r(jumat) → q(x,pramuka))

Diketahui bahwa taufiq tidak mengenakan seragam pramuka pada hari Jumat. Ditambahkan kalimat-kalimat berikut:

7 : ¬q(taufiq,pramuka)
8 : r(jumat)

Proses penarikan kesimpulan untuk menjawab pertanyaan apa Taufiq seorang siswa kelas II SD adalah sebagai berikut:

9 : p(taufiq) Λ r(jumat) → q(taufiq,pramuka) {Instansiasi x dengan taufiq pada kalimat 5}
10 : ¬(p(taufiq) Λ r(jumat)) {Modus Tollens antara 7 dan 9}
11 : ¬p(taufiq) V ¬r(jumat) {Hukum de Morgan untuk 10}
12 : p(taufiq) → ¬r(jumat) {Ekuivalensi implikasi dengan 11}
13 : ¬p(taufiq) {Modus Tollens antara 8 dan 12}

 

Binus

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂