Skripsi tentang pemrograman berbasis batasan

Ikhtisar

Sebagai mahasiswa sarjana ilmu komputer, riset saya berangkat dari pertanyaan yang praktis: ketika sebuah simulator menumpuk banyak kondisi yang mungkin terjadi, bagaimana caranya agar ia berhenti menimbang ulang kondisi yang sudah tidak mungkin terjadi? Saya mengembangkan dan mengevaluasi sebuah metode untuk HydLa yang memakai arah perubahan sebuah nilai untuk membuang kondisi usang dari pencarian. Pada model acuan, total waktu simulasi turun menjadi kira-kira setengahnya.

Karya ini adalah salah satu fondasi paling awal dari filosofi desain saya. Pemrograman berbasis batasan mengajarkan bahwa hasil yang rumit tidak selalu perlu ditetapkan secara langsung: ia bisa muncul dari ruang aturan, prioritas, dan batas yang didefinisikan dengan cermat. Cara berpikir itulah yang kini menopang pendekatan saya dalam merancang dari batasan di era AI — merancang kondisi tempat sebuah sistem generatif bebas bertindak.

Abstrak

HydLa adalah bahasa pemodelan untuk sistem hibrida: sistem tempat perubahan kontinu dan peristiwa diskret saling berinteraksi. Rancangannya yang berbasis batasan memungkinkan sistem semacam itu digambarkan secara ringkas dan disimulasikan dengan presisi tinggi. Ongkosnya, pada model yang besar simulator bisa terus memeriksa sangat banyak aturan bersyarat, bahkan setelah sebagian di antaranya tidak lagi relevan.

Riset ini mengusulkan pengurangan batasan berpenjaga tersebut secara dinamis. Dengan mengenali perilaku monoton — sebuah nilai yang terus bergerak ke satu arah — simulator dapat memastikan bahwa penjaga tertentu tidak akan pernah terpenuhi di masa depan, lalu berhenti memeriksanya dengan aman. Pendekatan ini terutama efektif pada model yang memuat banyak objek dengan penjaga serupa: waktu jalan yang terukur turun menjadi sekitar setengah dari semula.

1. Pendahuluan

Sistem hibrida memadukan perilaku kontinu dengan peristiwa diskret. Bola yang memantul adalah contoh sederhana: posisi dan kecepatannya berubah secara kontinu selama ia di udara, tetapi saat ia menyentuh permukaan tercipta peristiwa diskret yang mengubah arahnya. Termostat, kendaraan, dan robot memuat campuran yang sama dalam bentuk yang jauh lebih berkonsekuensi.

HydLa memungkinkan pemodel menggambarkan sistem seperti ini dengan batasan matematis dan logis, alih-alih menuliskan satu urutan prosedural. Simulatornya, HyLaGI, dapat melakukan perhitungan simbolik tanpa galat pembulatan dan mampu bekerja dengan parameter yang tak pasti. Namun, keleluasaan ini melahirkan masalah skala: ketika sebuah model memuat banyak aturan yang hanya aktif pada kondisi tertentu, simulator harus berulang kali bertanya apakah tiap kondisi itu yang akan terjadi berikutnya.

2. Batasan berpenjaga dalam simulasi

Batasan berpenjaga adalah aturan yang baru aktif ketika kondisi penjaganya terpenuhi. Pada model acuan di atas, tiap segmen permukaan punya aturannya sendiri: jika bola mencapai ketinggian nol sementara posisi mendatarnya berada di dalam segmen itu, aturan pantulan berlaku. Karena itu, membagi permukaan menjadi lebih banyak potongan berarti memberi simulator lebih banyak penjaga untuk diperiksa.

Percobaan memvariasikan jumlah segmen dari 10 sampai 200. Simulator asli menjadi lambat kira-kira sebanding dengan kuadrat angka tersebut. Hal ini penting di luar contoh mainan: model yang lebih besar bisa jadi mewakili banyak benda fisik, area kontak, atau peristiwa yang mungkin, persis dalam bentuk berpenjaga seperti ini.

3. Letak hambatannya

Pemrofilan menunjukkan bahwa perlambatan itu tidak tersebar merata di seluruh simulator. Dengan 100 segmen permukaan, 96% waktu jalan yang terukur dihabiskan di FindMinTime, operasi yang mencari peristiwa berikutnya yang paling awal mungkin terjadi. Operasi itu berulang kali mengevaluasi penjaga dari setiap batasan yang menjadi kandidat.

Hasil tersebut membuat sasaran optimasi menjadi jelas: kurangi jumlah penjaga yang harus dipertimbangkan FindMinTime, sambil mempertahankan perilaku hasil simulasi persis sama.

4. Pengurangan batasan berpenjaga

Bayangkan sebuah bola memantul menuruni tangga. Begitu bola melewati satu anak tangga dan terus bergerak maju, anak tangga itu tidak lagi bisa memengaruhinya. Orang yang melihat diagramnya langsung mengabaikan anak tangga di belakang bola; algoritme aslinya tetap memeriksa semuanya, satu per satu.

Bagian yang sulit adalah membuktikan bahwa penjaga yang dibuang tidak akan diperlukan lagi nanti. Membuangnya hanya karena sekarang bernilai salah bisa diam-diam menghasilkan jawaban keliru bila ia kembali bernilai benar. Karena itu usulan ini bertumpu pada kemonotonan: apakah sebuah peubah dijamin terus naik, atau terus turun, sepanjang suatu selang waktu.

4.1 Pendekatan untuk kemonotonan seragam

Pendekatan pertama berlaku ketika sebuah peubah bergerak ke satu arah sepanjang seluruh simulasi. Pada model permukaan terbagi, posisi mendatar bola selalu naik. Begitu bola melewati sebuah segmen, kondisi segmen itu tidak akan pernah terpenuhi lagi. Teknik pemeriksaan model dapat menetapkan sifat ini sebelum simulasi dijalankan, sehingga penjaga yang usang bisa dibuang dengan aman seiring berjalannya eksekusi.

4.2 Pendekatan untuk kemonotonan bergantian

Banyak sistem nyata tidak bergerak ke satu arah selamanya. Sebuah peubah bisa naik, berbalik, lalu turun. Karena itu makalah tersebut menggariskan pendekatan kedua: mulai dengan arah yang diandaikan, awasi andaian itu dengan asersi, lalu jalankan ulang logika pengurangan dari titik tempat arahnya berubah. Penjaga yang dibuang untuk satu selang monoton dikembalikan ketika selang berikutnya dimulai.

5. Hasil percobaan

Saya menerapkan pendekatan kemonotonan seragam dan mengevaluasinya dengan model permukaan terbagi. Baik algoritme asli maupun yang diusulkan tetap makin lama seiring bertambahnya jumlah segmen, tetapi versi usulan secara konsisten mengerjakan lebih sedikit. Membandingkan kurva yang dicocokkan, koefisien pangkat tertingginya turun dari 1,1463 ke 0,6083; untuk kasus acuan ini total waktu simulasi kira-kira terpangkas separuh.

Hasil ini bukan klaim bahwa setiap model HydLa menjadi dua kali lebih cepat. Ia menunjukkan di mana metode ini menolong: pada model dengan banyak objek berpenjaga dan arah perubahan yang dapat dibuktikan, tempat penjaga menjadi tidak relevan secara permanen selama eksekusi.

6. Simpulan dan pekerjaan lanjutan

Riset ini memperlihatkan bahwa pengetahuan tentang sebuah model — bukan hanya perhitungan tingkat rendah yang lebih cepat — dapat membuat simulasi lebih efisien. Dengan memakai kemonotonan untuk mengenali kemungkinan mana yang sudah menjadi mustahil, HyLaGI dapat mengecilkan himpunan batasan aktifnya tanpa mengubah hasil.

Percobaan yang dikerjakan mencakup kemonotonan seragam. Makalah itu meninggalkan dua arah untuk kemudian: mengevaluasi metode berbasis asersi untuk perilaku bergantian, dan memakai invarian selain kemonotonan guna menemukan lebih banyak batasan yang dapat dibuang dengan aman.