Takafumi Horiuchi

Skripsi tentang pemrograman berbasis kendala

Gambaran umum

Semakin banyak kemungkinan kejadian dalam simulasi, semakin banyak kondisi yang harus dievaluasi berulang kali. Namun, jika perkembangan simulasi menunjukkan bahwa suatu kondisi tidak mungkin terpenuhi lagi, dapatkah kondisi itu dilewati dengan aman? Saya merancang dan mengimplementasikan metode untuk HydLa, bahasa pemodelan sistem hibrida, yang memanfaatkan arah perubahan variabel untuk mengeluarkan kondisi yang tidak perlu diperiksa lagi.

Pada model evaluasi, metode ini mengurangi waktu eksekusi menjadi sekitar setengah waktu algoritma semula tanpa mengubah hasil simulasi. Peningkatan ini diperoleh dengan memanfaatkan struktur masalah untuk mengurangi kemungkinan yang perlu dipertimbangkan.

Cara pandang pemrograman berbasis kendala yang saya kembangkan melalui penelitian ini kini mendasari pendekatan saya pada proyek-proyek dalam portofolio ini: alih-alih menentukan setiap hasil secara langsung, kita menetapkan aturan, prioritas, dan batas, lalu menurunkan solusi yang memenuhinya.


Masalah: Semakin banyak kemungkinan, semakin lama waktu eksekusi

HydLa mendeskripsikan sistem hibrida, yang menggabungkan perubahan kontinu dan kejadian diskret, melalui kendala matematis dan logis. Model menyatakan kondisi yang harus berlaku, bukan menentukan setiap langkah prosedural. Simulator kemudian mencari perilaku yang memenuhi kondisi tersebut.

Pada model dengan banyak aturan bersyarat, simulator berulang kali memeriksa sekumpulan besar kandidat. Kondisi yang tidak mungkin terpenuhi lagi pun tetap berada dalam kumpulan tersebut. Semakin besar model, semakin banyak beban komputasi yang ditimbulkan oleh pemeriksaan yang tidak perlu ini.

Model: Menggabungkan perubahan kontinu dan diskret

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.

Evaluasi menggunakan model bola yang bergerak horizontal sambil memantul di atas permukaan yang dibagi menjadi beberapa segmen. Setiap segmen memiliki aturan bersyarat yang membuat bola memantul saat mencapai area tersebut. Menambah segmen memungkinkan model merepresentasikan lebih banyak objek, tetapi juga menambah jumlah kondisi yang harus diperiksa simulator.

Kode sumber HydLa yang mendefinisikan bola yang bergerak horizontal dan memantul pada permukaan yang dibagi menjadi N segmen bersebelahan.
Model HydLa yang singkat mendeskripsikan sebuah bola dan permukaan yang dibagi menjadi N segmen, masing-masing dengan kendala bersyarat.

Sumber hambatan: Semakin banyak kondisi, semakin lama waktu eksekusi

Aturan yang hanya aktif ketika suatu kondisi terpenuhi disebut guarded constraint atau kendala bersyarat. Kondisi pemicunya disebut guard. Pada model evaluasi, aturan pantulan suatu segmen hanya aktif ketika bola mencapai lantai dan posisi horizontalnya berada di dalam segmen tersebut.

Ketika jumlah segmen meningkat dari 10 menjadi 200, waktu eksekusi simulator semula bertambah kira-kira sebanding dengan kuadrat jumlah segmen. Model yang lebih besar dapat memperparah masalah ini karena mencakup lebih banyak objek, wilayah kontak, dan kemungkinan kejadian.

Investigasi: Ke mana 96% waktu eksekusi digunakan?

Pengukuran kinerja model dengan 100 segmen menunjukkan bahwa FindMinTime menghabiskan 96% dari total waktu eksekusi. Rutin ini mencari waktu paling awal terjadinya kejadian berikutnya dengan mengevaluasi semua kandidat kondisi pemicu secara berulang.

Temuan ini menunjukkan sasaran perbaikan yang terarah: mengurangi secara aman kandidat yang diteruskan ke FindMinTime. Tujuannya adalah melewati hanya kemungkinan yang tidak perlu dievaluasi lagi, sambil tetap mempertahankan hasil simulasi.

Pendekatan: Menghapus kondisi yang tidak mungkin terpenuhi lagi

Bayangkan sebuah bola yang memantul menuruni 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.

Jejak merah menunjukkan bola yang turun sambil memantul di anak tangga hitam. Area yang diarsir menunjukkan anak tangga yang sudah dilewati dan tidak lagi relevan.
Saat bola bergerak ke kanan, kondisi pemicu yang terkait dengan anak tangga berarsir di belakangnya dapat dilewati.

Bagian tersulit adalah membuktikan bahwa kondisi pemicu yang dihapus tidak akan diperlukan lagi. Menghapusnya hanya karena saat ini bernilai salah dapat menghasilkan kesalahan yang tidak terdeteksi jika kondisi itu kembali bernilai benar. Karena itu, metode yang diusulkan menggunakan sifat monoton: apakah suatu variabel dapat dijamin terus meningkat atau terus menurun selama interval tertentu.

Jika arah perubahan tidak berubah

Pendekatan pertama berlaku ketika variabel berubah ke satu arah sepanjang simulasi. Dalam model permukaan bersegmen, posisi horizontal bola selalu meningkat. Setelah bola melewati suatu segmen, kondisi pemicu segmen tersebut tidak mungkin terpenuhi lagi. Teknik pemeriksaan model dapat memverifikasi sifat ini sebelum simulasi, sehingga kondisi pemicu dapat dihapus dengan aman saat tidak lagi relevan selama eksekusi.

Garis merah yang meningkat dari α pada waktu 0 ke β pada waktu maksimum menunjukkan variabel yang terus meningkat sepanjang simulasi.
Sifat monoton seragam berarti arah perubahan dipertahankan sepanjang interval yang disimulasikan.

Jika arah perubahan berbalik

Banyak sistem tidak bergerak ke satu arah selamanya: variabel dapat meningkat, berbalik arah, lalu menurun. Karena itu, skripsi ini mengusulkan pendekatan kedua. Arah perubahan diasumsikan dan asumsi itu dipantau dengan asersi. Ketika arahnya berubah, proses pengurangan dimulai ulang dan kondisi pemicu yang dihapus selama interval monoton sebelumnya dikembalikan. Pendekatan ini telah dirancang, tetapi belum diimplementasikan atau dievaluasi dalam proyek ini.

Lima gambar menunjukkan bagaimana interval dengan asumsi peningkatan, kegagalan asersi, interval penurunan baru, kegagalan kedua, dan interval monoton ditetapkan satu per satu.
Asersi yang gagal membagi perilaku sistem menjadi sejumlah interval, yang masing-masing dapat diperlakukan sebagai interval monoton.

Hasil: Waktu eksekusi sekitar separuh pada model evaluasi

Saya mengimplementasikan pendekatan sifat monoton seragam dan mengevaluasinya dengan model permukaan bersegmen. Waktu eksekusi kedua algoritma meningkat seiring bertambahnya jumlah segmen, tetapi metode yang diusulkan secara konsisten memerlukan waktu lebih singkat. Pada kurva hasil pencocokan, koefisien pangkat tertinggi turun dari 1,1463 menjadi 0,6083. Total waktu simulasi dalam uji pembanding ini berkurang menjadi sekitar setengahnya.

Hasil tersebut khusus berlaku pada uji pembanding ini. Metode ini berguna ketika model memuat banyak objek dengan kondisi pemicu, arah perubahan dapat dibuktikan, dan kondisi pemicu menjadi tidak relevan secara permanen selama eksekusi. Hasil ini tidak berarti bahwa setiap model HydLa akan berjalan dua kali lebih cepat.

Grafik waktu simulasi terhadap N, yaitu jumlah segmen permukaan. Dari 10 hingga 200 segmen, metode yang diusulkan secara konsisten lebih cepat. Pada N = 200, waktu yang diperlukan sekitar 250 detik, dibandingkan sekitar 470 detik untuk algoritma semula.
Pada model yang dievaluasi, metode yang diusulkan (persegi) memakan waktu sekitar setengah dari algoritma asli (lingkaran).

Pelajaran yang saya peroleh

Penelitian ini menggunakan sifat perilaku sistem yang telah diketahui untuk memperkecil kumpulan kemungkinan yang harus dipertimbangkan simulator. Mempersempit ruang pencarian sambil mempertahankan hasil merupakan salah satu kekuatan pemrograman berbasis kendala.

Implementasi dan evaluasi mencakup variabel yang terus berubah ke satu arah. Penanganan pembalikan arah masih berada pada tahap desain dan perlu dievaluasi. Sifat selain monoton juga mungkin membantu mengidentifikasi kendala yang tidak diperlukan.

Pengalaman ini mendasari minat saya saat ini untuk merancang kondisi dan batas tempat AI dapat mencari solusi. Ketika menangani hasil yang kompleks, menentukan apa yang dapat diabaikan dengan aman sama pentingnya dengan menentukan apa yang perlu dihitung.

Takafumi Horiuchi, Kazunori Ueda, “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa,” 2019 Annual Conference of the Japanese Society for Artificial Intelligence (33rd), 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02