Tesis kelulusan tentang pemrograman berbasis constraint

Gambaran umum

Simulator memeriksa banyak kondisi berulang kali seiring meningkatnya kemungkinan kejadian. Jadi, jika dari kemajuan dapat diputuskan bahwa 'kondisi ini tidak akan pernah terjadi lagi', apakah pemeriksaan tersebut dapat dihentikan dengan aman? Dengan memanfaatkan arah perubahan nilai sebagai petunjuk, metode untuk mengecualikan kondisi yang tidak diperlukan dari pencarian yang sedang dijalankan dirancang dan diimplementasikan untuk bahasa pemodelan sistem hibrida, HydLa.

Dalam model evaluasi, waktu eksekusi dikurangi hingga sekitar setengah dari sebelumnya tanpa mengubah hasil simulasi. Yang penting bukanlah membuat semua perhitungan menjadi cepat secara merata. Yang dilakukan adalah menggunakan struktur masalah untuk mengurangi kemungkinan yang perlu dipertimbangkan itu sendiri.

Pemikiran pemrograman berbasis kendala yang dipelajari dalam penelitian ini menjadi dasar dari Filosofi desain saya saat ini. Alih-alih menentukan hasil satu per satu secara langsung, pendekatannya adalah mendefinisikan aturan, prioritas, dan batas, dan kemudian menurunkan solusi yang berlaku dari dalam batas tersebut.

Tantangan — Semakin banyak kemungkinan, semakin lambat perhitungannya

HydLa adalah bahasa untuk mendeskripsikan "sistem hibrid" yang merupakan kombinasi dari perubahan kontinu dan peristiwa diskret sebagai kendala matematis dan logis. Tanpa menulis urutan prosedur secara lengkap, dengan hanya menyatakan apa yang harus berlaku, perilaku yang memenuhi kondisi dapat disimulasikan.

Di sisi lain, pada model yang memiliki banyak aturan yang berlaku tergantung pada kondisi, simulator memeriksa kembali banyak kandidat secara berulang. Karena kandidat tetap ada hingga kondisi yang sudah lewat dan yang tidak akan terpenuhi di masa depan, semakin besar model, semakin banyak perhitungan yang tidak perlu menumpuk.

Tema — Sistem di mana kontinu dan diskret bercampur

Bola yang memantul adalah contoh yang mudah dipahami dari sistem hibrida. Di udara, posisi dan kecepatan berubah secara terus-menerus, dan pada saat mengenai lantai, terjadi peristiwa diskret berupa pantulan. Termostat, mobil, dan robot juga memiliki dua jenis perubahan yang sama di dalamnya, meskipun skalanya berbeda.

Untuk evaluasi, digunakan model di mana bola yang bergerak secara horizontal memantul pada permukaan yang dibagi menjadi beberapa bagian. Pada setiap bagian permukaan terdapat aturan bersyarat 'bola akan memantul jika datang ke area ini'. Jika jumlah bagian ditambah, objek yang bisa diekspresikan juga bertambah, sementara kondisi yang harus diperiksa oleh simulator juga meningkat.

Titik leher botol — Jumlah kondisi meningkatkan kompleksitas perhitungan

Aturan yang hanya berlaku ketika kondisi terpenuhi disebut 'kontraint bersyarat'. Dalam model evaluasi, aturan pantulan dari suatu area hanya berlaku ketika bola mencapai lantai dan posisinya secara horizontal berada di dalam area tertentu.

Ketika jumlah petak ditingkatkan dari 10 menjadi 200, simulator konvensional menjadi lambat kira-kira sebanding dengan kuadrat jumlah petak. Pada model berskala besar, masalah yang sama menjadi lebih besar karena bertambahnya objek, area kontak, dan kemungkinan kejadian.

Investigasi — 96% dari waktu pemrosesan berada di mana

Ketika mengukur waktu pemrosesan, pada model dengan 100 blok, 96% dari keseluruhan digunakan untuk FindMinTime. Ini adalah proses untuk mencari "peristiwa terdekat berikutnya" dari kandidat yang ada. Oleh karena itu, semua kondisi pengaman dievaluasi berulang kali.

Tempat yang perlu diperbaiki sudah jelas. Alih-alih membangun kembali seluruh metode perhitungan, cukup kurangi kandidat yang diteruskan ke FindMinTime dengan aman. Tujuannya adalah untuk menghapus kemungkinan yang tidak perlu diperiksa tanpa mengubah hasil simulasi.

Pendekatan — dengan aman menghapus kondisi yang tidak akan pernah terpenuhi lagi

Bayangkan sebuah bola yang turun sambil melompat di tangga. Jika bola melewati satu anak tangga dan terus bergerak ke depan, anak tangga itu tidak akan berpengaruh pada bola lagi. Orang yang melihat gambar akan segera mengabaikan anak tangga yang ada di belakang bola. Algoritma asli terus memeriksa masing-masing anak tangga itu satu per satu.

Yang sulit adalah pihak yang menunjukkan bahwa penjaga yang dihapus tidak akan diperlukan di kemudian hari. Jika dihapus hanya karena saat ini palsu, ketika menjadi benar lagi, itu bisa secara diam-diam mengembalikan hasil yang salah. Oleh karena itu, metode yang diusulkan menggunakan monotoni — yaitu apakah dapat dijamin bahwa suatu variabel terus meningkat atau terus menurun sepanjang interval waktu tertentu.

Jika arah perubahan tidak berubah

Tindakan pertama berlaku ketika variabel bergerak ke satu arah sepanjang keseluruhan simulasi. Dalam model yang membagi permukaan, posisi horizontal bola selalu meningkat. Setelah melewati suatu area, kondisi di area itu tidak akan pernah terpenuhi lagi. Sifat ini dapat diperiksa sebelum simulasi dengan teknik pemeriksaan model, sehingga guard yang tidak dibutuhkan bisa dengan aman dihapus seiring berjalannya eksekusi.

Jika arah perubahan berubah di tengah jalan

Banyak sistem dalam kenyataan tidak bergerak satu arah selamanya. Variabel bisa bertambah, berubah arah, dan kemudian berkurang. Oleh karena itu, makalah ini menunjukkan pendekatan kedua. Pertama, arah diasumsikan, asumsi tersebut dipantau dengan assertion, dan ketika arah berubah, proses pengurangan diulang dari titik tersebut. Guard yang dihapus untuk satu interval monoton dikembalikan ketika interval berikutnya dimulai.

Hasil — Waktu eksekusi model penilaian sekitar setengahnya

Kami mengimplementasikan penanganan untuk monotoni yang seragam dan mengevaluasinya pada model yang dibagi menjadi beberapa bidang. Baik algoritme asli maupun metode yang diusulkan, waktu yang dibutuhkan meningkat seiring bertambahnya jumlah bidang. Namun demikian, metode yang diusulkan konsisten membutuhkan lebih sedikit pekerjaan. Jika dibandingkan kurva yang dipasang, koefisien tertinggi turun dari 1,1463 menjadi 0,6083, dan pada tolok ukur ini, waktu total simulasi menjadi kira-kira setengahnya.

Ini bukan klaim bahwa semua model HydLa akan menjadi dua kali lebih cepat. Yang ditunjukkan adalah tempat di mana metode ini efektif — yaitu model dengan banyak objek yang memiliki guard, arah perubahan dapat dibuktikan, dan selama eksekusi guard menjadi tidak relevan secara permanen.

Perspektif yang diperoleh dari penelitian ini

Yang dilakukan dalam penelitian ini bukanlah mempercepat perhitungan individu sedikit demi sedikit. Yang dilakukan adalah menggunakan hal-hal yang diketahui tentang perilaku sistem untuk mengecilkan himpunan kemungkinan yang perlu dipertimbangkan. Konsep mempersempit ruang pencarian tanpa mengubah hasil adalah kekuatan dari pemrograman berbasis kendala.

Yang diimplementasikan dan dievaluasi adalah kasus di mana variabel terus bergerak ke satu arah. Jika arah perubahan berubah di tengah jalan, hal itu hanya sampai pada tahap perancangan, dan evaluasinya tetap menjadi tugas untuk masa depan. Ada juga ruang untuk menemukan batasan yang tidak diperlukan dengan menggunakan sifat selain monoton.

Pengalaman ini juga terkait dengan kenyataan bahwa saat ini saya mencoba merancang kondisi dan batasan yang bisa dijelajahi oleh AI, bukan langsung merancang output AI. Saat menangani hasil yang kompleks, sama pentingnya untuk mendefinisikan apa yang perlu dihitung dan apa yang tidak perlu dipikirkan.