World In Your Hand

Classical Planning

Kali ini, yang akan kita bahas adalah tentang Classical Planning.
Tujuan Planning adalah kita membuat sebuah computer berpikir apa yang harus ia lakukan dari awal (GOAL STATE), menuju tujuan akhir yang kita inginkan (GOAL STATE)

Ketika kita mendengar kata Planning di dunia AI, maka kita akan bermain dengan Block World.

Berikut adalah beberapa operator yang perlu kita ketahui dalam Block World:

• Unstack (A, B): Mengangkat balok A dari permukaan balok B, dimana posisi balok A berada diatas balok B, dan diatas permukaan balok A harus clear.
• Stack (A, B): Menaruh balok A ke atas permukaan balok B, dimana keadaan diatas permukaan balok B harus clear, dan balok A harus sudah berada di tangan robot.
• Pickup (A): Mengambil balok A dari tanah ke tangan robot, dimana balok A harus berada di atas tanah dan diatas permukaan balok A harus clear.
• Putdown (A): meletakkan balok A ke atas tanah, dimana posisi balok A sudah berada di tangan robot.

Berikut adalah beberapa predicates (kondisi) yang perlu kita pahami dalam Block World:

• ON (A, B): Balok A berada diatas balok B
• ONTABLE (A): Balok A berada diatas tanah
• CLEAR (A): Diatas permukaan balok A tidak ada balok lain
• HOLDING (A): Balok A berada di genggaman tangan robot
• ARMEMPTY: Tangan robot kosong (tidak memengang balok)

Di dalam Planning, terdapat dua jenis planning yaitu:

• Goal Stack Planning / Linear Planning

Pada metode Linear Planning, pertama-tama kita perlu mendefinisikan START STATE dan GOAL STATE nya itu ke dalam bentuk predicates (kondisi) yang valid. Kemudian, dilakukan dengan cara backward, dan dimulai dari paling kiri bawah. Setelah itu, selesaikan setiap langkah-langkah dari GOAL STATE dan akhirnya bisa berakhir di START STATE.

Contoh:

• Constraint Posting / Non Linear Planning

Sama seperti Linear Planing cara penyelesaiannya. Tetapi yang membedakan Goal Stack dengan Constraint Posting adalah GOAL STATE nya itu hanya perlu didefinisikan kedalam bentuk predicates ON(x,y), dimana GOAL STATE menjadi lebih sedikit kondisinya. Selain itu, didalam Constraint Posting juga perlu diperhatikan beberapa langkah yaitu:

1. Step Addition: membuat langkah-langkah baru untuk rencana.
2. Promotion: Menentukan satu diantara beberapa langkah yang mana harus dijalankan terlebih dahulu (priority proccess)
3. Declobbering: Menambahkan langkap baru diantara kedua proses yang sedang berjalan.
4. Simple Establishment: menempatkan nilai ke variabel, dalam rangka untuk memastikan prasyarat dari beberapa langkah.
5. Separation – mencegah penugasan nilai-nilai tertentu ke variabel.

Contoh:

[…]

-First Order Logic (FOL)

First-order logic digunakan untuk menarik sebuah kesimpulan dari beberapa fakta yang terkumpul, dan dapat kita buktikan dengan cara backward chaining dan resolution.

FOL dipakai untuk membuktikan apakah statement tersebut value nya true or false, tetapi sebelum dibuktikan kita perlu mengkonversi semua faktanya itu ke dalam bentuk FOL.

Di dalam FOL hanya mengasumsikan bahwa dunia ini hanya terdiri dari:

• Object
• Relation
• Function

Syntax dan Semantic dalam FOL:

• Atomic Sentences: predicate (term1,…,termn)

Misal: “Niko is a student.”

Student(Niko)

• Complex Sentences: gabungan dari atomic sentences yang tergabung dalam suatu relasi (konektivitas)

Misal: All students are human.

“x: Student(x) -> Human(x)

1. Proof by Backward Chaining

Setelah statement-statementnya sudah dikonversi ke dalam FOL, makan kita tinggal membuktikan kesimpulan yang kita tarik dari FOL yang kita dapatkan, dan kita hubungkan satu fakta dengan fakta-fakta lainnya, jika diakhiri dengan NULL, berarti kesimpulan yang ditarik benar.

2. Proof by Resolution

Bedanya resolution dengan backward chaining adalah pada FOL yang kita dapatkan dari statement-statement, membuat negasi FOL yang telah ada, menjadi FOL yang berimplikasi menjadi dan / atau (mengubah bentuknya ke dalam CNF/Clause Normal Form). Dan jika akhirnya menghasilkan NULL juga, maka kesimpulannya terbukti dari fakta-fakta yang terkumpul.

[…]

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 🙂