Graf Perencanaan dan Heuristik

Graf perencanaan dan heuristik independen domain adalah teknik yang membuat perencanaan klasik menjadi cepat, dengan menganalisis ketercapaian secara ringkas dan secara otomatis memperkirakan jarak dari suatu keadaan ke tujuan.

Definition

Graf perencanaan adalah struktur berlapis yang menyisipkan tingkat proposisi dan tindakan dengan batasan mutex untuk memperkirakan ketercapaian; heuristik perencanaan adalah fungsi, seringkali dihitung dari struktur tersebut atau dari masalah yang direlaksasi penghapusannya, yang memperkirakan biaya untuk mencapai tujuan dari suatu keadaan.

Scope

Topik ini mencakup struktur data graf perencanaan yang diperkenalkan oleh Graphplan, termasuk tingkat proposisi dan tindakan serta hubungan pengecualian bersama (mutex) yang menangkap fakta dan tindakan mana yang tidak dapat terjadi bersamaan, dan keluarga heuristik independen domain yang berasal dari masalah yang direlaksasi (terutama mengabaikan efek penghapusan) yang mendorong perencana pencarian heuristik modern. Ini membahas bagaimana informasi ketercapaian dihitung dan digunakan untuk memandu pencarian. Model perencanaan klasik yang mendasarinya dibahas dalam topik terkait.

Core questions

• Bagaimana graf perencanaan merepresentasikan proposisi dan tindakan yang dapat dicapai tingkat demi tingkat?
• Apa itu hubungan mutex, dan bagaimana mereka menangkap ketidakcocokan antara fakta dan tindakan?
• Bagaimana relaksasi penghapusan digunakan untuk menurunkan heuristik perencanaan yang dapat diterima atau informatif?
• Bagaimana heuristik ini mengubah perencanaan menjadi pencarian heuristik yang efisien?

Key concepts

• graf perencanaan
• tingkat proposisi dan tindakan
• pengecualian bersama (mutex)
• Graphplan
• relaksasi penghapusan
• heuristik h-max dan h-add
• heuristik FF dan rencana yang direlaksasi
• pencarian maju heuristik

Key theories

Graf perencanaan dan Graphplan

Graphplan membangun graf perencanaan yang secara ringkas mengkodekan proposisi dan tindakan mana yang dapat dicapai pada setiap tingkat dan pasangan mana yang saling eksklusif, kemudian mengekstrak rencana dengan mencari mundur melalui struktur ini, secara dramatis mempercepat perencanaan.

Heuristik relaksasi penghapusan

Mengabaikan efek penghapusan tindakan menghasilkan masalah perencanaan yang direlaksasi yang jauh lebih mudah dipecahkan; biaya pemecahan relaksasi ini memberikan heuristik yang informatif, seringkali dapat diterima (seperti h-max dan h-add serta heuristik FF) yang memandu pencarian maju.

Perencanaan pencarian heuristik

Perencana klasik canggih menggabungkan heuristik yang diturunkan secara otomatis dengan pencarian terbaik pertama atau serakah dan peningkatan seperti operator pilihan, mencapai kinerja tujuan umum yang kuat di berbagai domain.

Clinical relevance

Graf perencanaan dan heuristik relaksasi penghapusan adalah teknologi inti dari perencana pemenang kompetisi yang digunakan dalam robotika, logistik, dan kontrol otonom, di mana mereka memungkinkan perencana independen domain untuk memecahkan masalah besar dengan cepat tanpa panduan pencarian yang dibuat secara manual.

History

Graphplan Blum dan Furst (1995, versi jurnal 1997) memperkenalkan graf perencanaan dan merevolusi kecepatan perencanaan. Akhir 1990-an dan 2000-an menyaksikan munculnya heuristik relaksasi penghapusan, dengan perencana FF (Hoffmann dan Nebel, 2001) dan kemudian Fast Downward (Helmert, 2006) menetapkan pencarian maju heuristik sebagai pendekatan yang dominan.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Apa itu mutex dalam graf perencanaan?

Hubungan mutex (mutual exclusion) menandai dua proposisi atau dua tindakan yang tidak dapat keduanya berlaku atau diterapkan pada tingkat yang sama, misalnya karena satu tindakan menghapus prasyarat tindakan lainnya. Mutex membuat graf perencanaan menjadi perkiraan yang lebih ketat dari ketercapaian yang sebenarnya.

Mengapa mengabaikan efek penghapusan memberikan heuristik yang berguna?

Tanpa efek penghapusan, mencapai satu tujuan tidak pernah membatalkan tujuan lain, sehingga masalah yang direlaksasi jauh lebih mudah dipecahkan dan tidak pernah lebih sulit daripada yang asli. Oleh karena itu, biaya rencana yang direlaksasi adalah batas bawah atau perkiraan yang terinformasi dari biaya sebenarnya, menjadikannya heuristik yang efektif untuk memandu pencarian.