Apa saja asumsi perencanaan klasik?

Perencanaan klasik mengasumsikan agen tunggal yang bertindak dalam lingkungan yang deterministik, dapat diamati sepenuhnya, dan statis, dengan tindakan yang membutuhkan waktu unit dan keadaan awal yang sepenuhnya diketahui. Melonggarkan salah satu asumsi ini, misalnya memungkinkan ketidakpastian atau konkurensi, mengarah pada masalah perencanaan yang lebih kaya di luar model klasik.

Apa arti daftar tambah dan daftar hapus STRIPS?

Ketika tindakan STRIPS diterapkan, proposisi dalam daftar tambahnya menjadi benar dan yang ada dalam daftar hapusnya menjadi salah; semua proposisi lainnya tidak berubah. Aturan pembaruan sederhana ini yang membuat STRIPS menjadi representasi yang ringkas dan nyaman secara komputasi tentang bagaimana tindakan mengubah dunia.

Perencanaan Klasik dan STRIPS

Perencanaan klasik membahas masalah menemukan urutan tindakan untuk mencapai tujuan dalam lingkungan yang deterministik, dapat diamati sepenuhnya, dan statis, menggunakan representasi tindakan gaya STRIPS yang terfaktorisasi berdasarkan prasyarat dan efek.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Perencanaan klasik mencari urutan tindakan deterministik yang mengubah keadaan awal yang sepenuhnya diketahui menjadi keadaan yang memenuhi tujuan, di mana setiap tindakan dijelaskan oleh kondisi yang harus berlaku agar dapat diterapkan dan perubahan yang ditimbulkannya.

Scope

Topik ini mencakup model perencanaan klasik dan asumsinya (tindakan deterministik, observabilitas penuh, agen tunggal, waktu atomik), representasi STRIPS dan ADL/PDDL dari keadaan dan tindakan, metode solusi dasar pencarian ruang keadaan maju (progresi) dan mundur (regresi) serta perencanaan urutan parsial, dan kompleksitas komputasi perencanaan proposisional. Panduan heuristik dan grafik perencanaan dibahas dalam topik terkait, dan varian nondeterministik atau probabilistik berada di luar cakupan.

Core questions

Asumsi apa yang mendefinisikan model perencanaan klasik, dan kapan asumsi tersebut tepat?
Bagaimana representasi STRIPS memfaktorkan suatu keadaan menjadi proposisi dan suatu tindakan menjadi prasyarat serta efek tambah/hapus?
Bagaimana pencarian progresi dan regresi berbeda sebagai strategi perencanaan?
Seberapa sulit secara komputasi perencanaan klasik secara umum?

Key concepts

model deterministik, dapat diamati sepenuhnya
prasyarat dan efek STRIPS
daftar tambah dan hapus
PDDL dan ADL
pencarian progresi (maju)
pencarian regresi (mundur)
perencanaan urutan parsial
kompleksitas keberadaan rencana

Key theories

Representasi STRIPS: STRIPS menggambarkan dunia sebagai sekumpulan proposisi benar dan setiap tindakan oleh daftar prasyarat ditambah daftar tambah dan hapus, sehingga menerapkan suatu tindakan hanya menambah dan menghapus proposisi; model terfaktorisasi ini adalah dasar dari hampir semua perencana klasik.
Pencarian progresi dan regresi: Rencana klasik dapat ditemukan dengan mencari maju dari keadaan awal menerapkan tindakan yang berlaku (progresi) atau mundur dari tujuan menghitung sub-tujuan yang diregresi (regresi), dengan perencanaan urutan parsial melonggarkan komitmen terhadap urutan tindakan total.
Kompleksitas perencanaan: Memutuskan apakah rencana STRIPS proposisional ada adalah PSPACE-lengkap secara umum, secara formal menjelaskan mengapa perencanaan sulit dan memotivasi metode heuristik dan struktural untuk membuatnya praktis.

Clinical relevance

Representasi perencanaan klasik adalah antarmuka umum untuk perencanaan tugas robot, perakitan dan logistik otomatis, dan aplikasi apa pun di mana tindakan deterministik harus diurutkan untuk mencapai tujuan; perencana klasik berbasis PDDL adalah tulang punggung bidang ini dan Kompetisi Perencanaan Internasional.

History

STRIPS dikembangkan di SRI sekitar tahun 1971 untuk mengendalikan robot Shakey, memperkenalkan model tindakan prasyarat/efek yang mendefinisikan perencanaan klasik. Perencanaan urutan parsial berkembang pada tahun 1970-an-80-an, Bylander menetapkan kelengkapan PSPACE dari perencanaan proposisional pada tahun 1994, dan standar PDDL kemudian menyatukan tolok ukur bidang ini.

Key figures

Richard E. Fikes
Nils J. Nilsson
Tom Bylander
Earl D. Sacerdoti

Seminal works

fikes1971
bylander1994

Frequently asked questions

Apa saja asumsi perencanaan klasik?: Perencanaan klasik mengasumsikan agen tunggal yang bertindak dalam lingkungan yang deterministik, dapat diamati sepenuhnya, dan statis, dengan tindakan yang membutuhkan waktu unit dan keadaan awal yang sepenuhnya diketahui. Melonggarkan salah satu asumsi ini, misalnya memungkinkan ketidakpastian atau konkurensi, mengarah pada masalah perencanaan yang lebih kaya di luar model klasik.
Apa arti daftar tambah dan daftar hapus STRIPS?: Ketika tindakan STRIPS diterapkan, proposisi dalam daftar tambahnya menjadi benar dan yang ada dalam daftar hapusnya menjadi salah; semua proposisi lainnya tidak berubah. Aturan pembaruan sederhana ini yang membuat STRIPS menjadi representasi yang ringkas dan nyaman secara komputasi tentang bagaimana tindakan mengubah dunia.