Perencanaan Otomatis

Perencanaan otomatis adalah cabang kecerdasan buatan yang berkaitan dengan penghitungan urutan tindakan yang mengubah keadaan awal dunia menjadi keadaan tujuan yang diinginkan, dengan mempertimbangkan deskripsi formal dari tindakan yang tersedia.

Definition

Perencanaan otomatis adalah penghitungan suatu rencana—sekumpulan tindakan yang terurut (atau sebagian terurut)—yang secara terbukti mencapai tujuan dari keadaan awal, dengan mempertimbangkan model bagaimana setiap tindakan mengubah keadaan dunia.

Scope

Area ini mencakup representasi masalah perencanaan (keadaan, tindakan dengan prasyarat dan efek, tujuan) dan algoritma yang menyelesaikannya: perencanaan klasik dalam domain deterministik yang dapat diamati sepenuhnya, metode grafik perencanaan dan pencarian heuristik, perencanaan jaringan tugas hierarkis, serta perluasan ke waktu, sumber daya, dan penjadwalan. Ini membahas formalisme standar seperti STRIPS dan PDDL serta kompleksitas perencanaan. Perencanaan di bawah ketidakpastian probabilistik terhubung dengan penalaran di bawah ketidakpastian, dan pembelajaran model tindakan atau kebijakan dari data termasuk dalam subbidang pembelajaran mesin.

Sub-topics

• Classical Planning and STRIPS
• Hierarchical Task Network Planning
• Planning Graphs and Heuristics
• Temporal Planning and Scheduling

Core questions

• Bagaimana tindakan, keadaan, dan tujuan direpresentasikan secara cukup ringkas untuk menggambarkan domain yang besar?
• Bagaimana masalah perencanaan dicari secara efisien meskipun ruang keadaan sangat besar secara eksponensial?
• Bagaimana heuristik yang dapat diterima dan informatif diturunkan secara otomatis dari deskripsi domain?
• Bagaimana rencana dapat distrukturkan secara hierarkis, dan bagaimana kendala waktu serta sumber daya digabungkan?

Key concepts

• keadaan, tindakan, tujuan
• prasyarat dan efek
• STRIPS dan PDDL
• pencarian ruang keadaan maju dan mundur
• grafik perencanaan
• heuristik independen domain
• jaringan tugas hierarkis
• perencanaan dan penjadwalan temporal

Key theories

Representasi tindakan STRIPS

Formalisme STRIPS menggambarkan tindakan berdasarkan prasyarat dan efek tambah/hapus atas sekumpulan proposisi, menyediakan representasi terfaktor yang ringkas yang menjadikan perencanaan sebagai pencarian melalui keadaan simbolik daripada enumerasi keadaan dunia eksplisit.

Pencarian heuristik independen domain untuk perencanaan

Perencana modern menganggap perencanaan sebagai pencarian heuristik dan menurunkan heuristik secara otomatis dari deskripsi masalah, misalnya dengan mengabaikan efek penghapusan atau memanfaatkan struktur kausal, memungkinkan kinerja tujuan umum yang kuat.

Perencanaan sebagai hierarki kelas masalah

Perencanaan mencakup spektrum dari perencanaan deterministik klasik hingga varian hierarkis, temporal, dan terbatas sumber daya, masing-masing dengan representasi dan kompleksitas karakteristik, yang diatur dalam teori standar perencanaan otomatis.

Clinical relevance

Perencanaan otomatis diterapkan dalam robotika dan sistem otonom, operasi pesawat ruang angkasa dan misi, logistik dan rantai pasokan, manufaktur, serta pembuatan game dan narasi; perencana yang berasal dari teknik-teknik ini telah mengendalikan pesawat ruang angkasa otonom nyata dan mengoordinasikan alur kerja yang kompleks.

History

Perencanaan otomatis dimulai dengan STRIPS untuk robot Shakey di SRI sekitar tahun 1971, membingkai perencanaan sebagai pembuktian teorema atas deskripsi tindakan. Bidang ini berkembang melalui perencanaan urutan parsial, terobosan Graphplan (1995), dan munculnya perencana pencarian heuristik independen domain yang cepat serta standar PDDL dari akhir 1990-an dan seterusnya, yang dilacak melalui International Planning Competitions.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Malik Ghallab
• Dana Nau
• Paolo Traverso
• Malte Helmert

Seminal works

• fikes1971
• ghallab2004
• helmert2006

Frequently asked questions

Bagaimana perencanaan otomatis berbeda dari pencarian umum?

Perencanaan otomatis adalah bentuk pencarian, tetapi ia bekerja dari deskripsi tindakan yang deklaratif dan terfaktor (prasyarat dan efek) daripada fungsi penerus yang tidak jelas. Struktur ini memungkinkan perencana untuk secara otomatis menurunkan heuristik dan bernalar tentang tindakan mana yang relevan, yang tidak dapat dilakukan oleh pencarian generik.

Apa itu PDDL?

PDDL, Planning Domain Definition Language, adalah bahasa standar untuk menggambarkan domain dan masalah perencanaan—objek, predikat, tindakan, keadaan awal, dan tujuan. Ini memungkinkan perencana independen domain untuk dibandingkan pada tolok ukur umum, seperti dalam International Planning Competitions.