Bagian
penting dari AI adalah merancangkan rencana aksi untuk mencapai satu tujuan.
10.1 Definis Perencanaan Klasik
Setiap negara bagian diwakili sebagai sebuah gabungan dari fluents tanah, atom-atom yang berfungsi. Perencanaan klasik berkonsentrasi pada masalah-masalah yang mana kebanyakan tindakan meninggalkan hal-hal yang kebanyakan tidak berubah. Serangkaian tindakan (variabel-free) tanah dapat diwakili oleh skema tindakan. Skema adalah representasi mengangkat — itu mengangkat tingkat penalaran dari logika propositional untuk subset terbatas logika urutan pertama.
10.1.1 Contoh: Transportasi kargo udara
Gambar 10.1 menunjukkan masalah transportasi kargo udara melibatkan pemuatan dan pembongkaran kargo dan terbang dari satu tempat ke tempat. Masalah dapat didefinisikan dengan tiga tindakan: memuat, membongkar, dan terbang.
10.1.2 Contoh:
Masalah ban serep
Mempertimbangkan masalah mengganti ban yang kempes. Tujuannya adalah untuk memiliki ban cadangan yang baik benar dipasang pada as roda mobil, di mana keadaan awal memiliki ban kempes pada as roda dan ban cadangan yang baik di bagasi. Hanya ada empat tindakan: menghapus cadangan dari bagasi, menghapus ban dari as roda, menempatkan cadangan pada as roda, dan meninggalkan mobil tanpa pengawasan semalam.
10.1.3 Contoh: Blok dunia
Salah satu yang paling terkenal perencanaan domain dikenal sebagai dunia blok. Domain ini terdiri dari satu set blok berbentuk kubus duduk di tabel. Blok dapat ditumpuk, tetapi hanya satu blok bisa muat langsung di atas yang lain. Sebuah lengan robot dapat mengambil blok dan memindahkannya ke posisi lain, baik di atas meja atau di atas blok lain. lengan dapat mengambil hanya satu blok pada suatu waktu, sehingga tidak dapat mengambil blok yang memiliki satu sama lain di atasnya.
10.1.4 Kompleksitas klasik perencanaan
PlanSAT adalah pertanyaan apakah ada rencana yang memecahkan masalah perencanaan. PlanSAT dibatasi oleh NP-lengkap sementara PlanSAT p; dengan kata lain, perencanaan optimal biasanya sulit, tapi sub-optimal perencanaan kadang-kadang mudah.
10.2 Algoritma Untuk Perencanaan Sebagai Ruang Negara-Cari
Sekarang kita mengalihkan perhatian kita untuk perencanaan algoritma. Kami melihat bagaimana Deskripsi masalah perencanaan defines Cari masalah: kita dapat mencari dari keadaan awal melalui ruang Serikat, mencari tujuan. Salah satu keuntungan baik dari representasi deklaratif tindakan skema bisa begitu wecan juga mencari fromthegoal mundur, mencari keadaan awal.
10.2.1 Cari ruang negara-maju (kemajuan)
Pencarian pertama, maju rentan terhadap menjelajahi tindakan-tindakan yang tidak relevan. Kedua, perencanaan masalah yang sering memiliki ruang besar negara
10.2.2 Mundur (regresi) Cari relevan-negara
Dalam pencarian Regresi yang dimulai dari tujuan dan menerapkan tindakan mundur, sampai ditemukannya urutan langkah-langkah untuk pencapaian negara yang relevan. Secara umum, pencarian backward bekerja ketika kita tahu bagaimana untuk mundur dari suatu keadaan. PDDL dirancang untuk membuat mudah tindakan kemunduran, jika sebuah domain dapat dinyatakan dalam PDDL, maka kita dapat melakukan regresi.
10.2.3 Heuristik untuk perencanaan
Menurut definisi heuristik, tidak ada cara untuk menganalisis keadaan atom, dan dengan demikian memerlukan beberapa kecerdikan oleh seorang analis manusia untuk menentukan heuristik domain-spesifik baik untuk masalah pencarian dengan negara-negara atom. Perencanaan menggunakan representasi terfaktor untuk negara dan skema tindakan. Yang memungkinkan untuk menentukan heuristik domain-independent yang baik dan program-program untuk otomatis menerapkan heuristik domain-independen baik untuk masalah yang diberikan. Ide utama dalam mendefinisikan heuristik adalah dekomposisi, yaitu membagi masalah menjadi beberpa bagian-bagian yang lebih kecil (subgoal), lalu memecahkan setiap bagian (subgoal) secara independen, setelah setiap masalah pada bagian tadi sudah diselesaikan, maka kemudian menggabungkan bagian-bagian tadi menjadi satu kesatuan.
10.3 Analisis Pendekatan Perencanaan
Perencanaan menggabungkan dua bidang utama dari AI yaitu pencarian
dan logika. Sebuah perencanaan dapat dilihat baik sebagai sebuah program yang
mencari solusi atau sebagai salah satu yang membuktikan solusi. Perencanaan
adalah latihan dalam mengendalikan ledakan kombinatorial. Sebuah perencana yang
menggunakan trik bawah-ke-atas dapat memecahkan masalah dalam dunia blok tanpa
backtracking.
EmoticonEmoticon