Perencanaan dan Penjadwalan Temporal

Perencanaan dan penjadwalan temporal memperluas perencanaan untuk menangani tindakan yang membutuhkan waktu, dapat berjalan secara bersamaan, dan mengonsumsi sumber daya terbatas, menghasilkan rencana yang tidak hanya menentukan apa yang harus dilakukan tetapi juga kapan harus melakukannya.

Definition

Perencanaan temporal menghasilkan rencana di mana tindakan memiliki durasi dan dapat tumpang tindih, tunduk pada kendala temporal dan sumber daya; penjadwalan menetapkan waktu mulai (dan sumber daya) untuk serangkaian aktivitas sehingga semua kendala, seperti urutan, tenggat waktu, dan kapasitas, terpenuhi.

Scope

Topik ini mencakup perencanaan dan penjadwalan dengan waktu dan sumber daya eksplisit: tindakan duratif, konkurensi dan kendala temporal, representasi dan solusi jaringan kendala temporal (seperti masalah temporal sederhana) dan aljabar interval Allen, serta integrasi perencanaan dengan penjadwalan aktivitas yang dibatasi sumber daya. Ini membahas bagaimana kelayakan waktu dan sumber daya dipertimbangkan bersama dengan pemilihan tindakan. Perencanaan klasik murni tanpa sumber daya dibahas dalam topik terkait.

Core questions

• Bagaimana tindakan duratif serta kondisi awal dan akhirnya direpresentasikan?
• Bagaimana kendala temporal antar peristiwa dimodelkan dan diperiksa konsistensinya?
• Bagaimana sumber daya terbatas dialokasikan di antara aktivitas yang bersamaan?
• Bagaimana perencanaan (memutuskan tindakan apa) dan penjadwalan (memutuskan kapan) digabungkan atau dipisahkan?

Key concepts

• tindakan duratif
• konkurensi dan tumpang tindih
• kendala temporal
• masalah temporal sederhana
• aljabar interval Allen
• kendala sumber daya
• penjadwalan
• tenggat waktu dan makespan

Key theories

Jaringan kendala temporal

Kendala temporal kuantitatif antara titik waktu dapat direpresentasikan sebagai jaringan yang konsistensi dan batas terketatnya dihitung secara efisien untuk masalah temporal sederhana, menyediakan tulang punggung penalaran temporal bagi banyak perencana dan penjadwal.

Aljabar interval untuk waktu kualitatif

Aljabar interval Allen menangkap kemungkinan hubungan kualitatif antara interval waktu (sebelum, selama, tumpang tindih, dan sebagainya) dan mendukung penalaran tentang pengetahuan temporal ketika waktu pasti tidak diketahui.

Mengintegrasikan perencanaan dengan penjadwalan

Masalah realistis memerlukan pemilihan tindakan dan penetapan waktu serta sumber dayanya secara bersamaan; teori perencanaan otomatis memperlakukan tindakan duratif, konkurensi, dan kendala sumber daya sebagai perluasan yang menggabungkan pemilihan tindakan dengan penjadwalan berbasis kendala.

Clinical relevance

Perencanaan dan penjadwalan temporal sangat penting dalam operasi pesawat ruang angkasa dan penjelajah, manufaktur dan penjadwalan proyek, transportasi dan penjadwalan kru, serta pengaturan apa pun di mana aktivitas yang berjangka waktu, bersamaan, dan terbatas sumber daya harus dikoordinasikan; sistem semacam itu telah merencanakan operasi untuk misi luar angkasa nyata.

History

Penalaran temporal kualitatif diformalkan oleh aljabar interval Allen (1983), dan jaringan kendala temporal kuantitatif oleh Dechter, Meiri, dan Pearl (1991). Fondasi-fondasi ini, bersama dengan model tindakan duratif yang ditambahkan ke PDDL pada awal tahun 2000-an, memungkinkan perencana temporal digunakan dalam aplikasi seperti kontrol pesawat ruang angkasa otonom.

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

Apa perbedaan antara perencanaan dan penjadwalan?

Perencanaan memutuskan tindakan apa yang harus diambil untuk mencapai tujuan, sementara penjadwalan memutuskan kapan tindakan tersebut terjadi dan sumber daya apa yang digunakannya, dengan mempertimbangkan kendala urutan dan kapasitas. Banyak masalah nyata memerlukan keduanya, dan perencanaan temporal mengintegrasikan pemilihan tindakan dengan penalaran waktu dan sumber daya.

Apa itu masalah temporal sederhana?

Masalah temporal sederhana adalah jaringan kendala temporal di mana setiap kendala membatasi perbedaan antara dua titik waktu dengan sebuah interval. Konsistensinya dan batas tersirat yang paling ketat dapat dihitung secara efisien, yang menjadikannya inti praktis untuk penalaran temporal dalam perencana dan penjadwal.