約束程式設計學士論文
2019年6月
概要
模擬中可能發生的事件越多,就越需要反覆檢查大量條件。但如果隨著模擬進行,能確定某個條件不可能再次成立,是否就能安全地略過它?我為混合系統建模語言 HydLa 設計並實作了一種方法,利用變數的變化方向,移除不再需要檢查的條件。
在評估模型中,這個方法使執行時間縮短至原始演算法的約一半,且不改變模擬結果。效能改善來自運用問題本身的結構,減少需要考慮的可能性。
透過這項研究建立的約束程式設計觀點,至今仍是我處理作品集中各項專案的基礎:不逐一指定結果,而是定義規則、優先順序與界限,再推導出符合條件的解。
問題:可能性越多,執行時間越長
HydLa 以數學與邏輯約束描述混合系統,也就是結合連續變化與離散事件的系統。模型不必逐步指定執行程序,而是宣告必須成立的條件,再由模擬器找出符合條件的行為。
當模型包含許多條件式規則時,模擬器會反覆檢查大量候選條件。即使某些條件已不可能再次成立,仍會留在候選集合中。模型越大,這些不必要的檢查就帶來越多計算負擔。
模型:結合連續與離散變化
彈跳的球是混合系統的一個簡單例子。球在空中時,位置與速度持續變化;碰到地面則觸發離散的反彈事件。恆溫器、汽車與機器人,也在不同尺度上結合了這兩種變化。
評估使用的模型,是一顆水平移動的球,在分成多個區段的表面上彈跳。每個區段都有一項條件式規則,讓球到達該範圍時反彈。增加區段數量可讓模型表達更多物件,同時也增加模擬器必須檢查的條件。
瓶頸:條件越多,執行時間越長
只有在特定條件成立時才啟用的規則,稱為「帶有守衛條件的約束」(guarded constraint)。在評估模型中,只有當球到達地面,且水平位置落在某個區段內,該區段的反彈規則才會啟用。
區段數量從 10 增加到 200 時,原始模擬器的執行時間大致隨區段數量的平方成長。較大的模型包含更多物件、接觸區域與可能發生的事件,可能使這個問題更加嚴重。
調查:96% 的執行時間花在哪裡?
對 100 個區段的模型進行效能分析後發現,FindMinTime 占了總執行時間的 96%。這個程序反覆評估所有候選守衛條件,找出下一個最早可能發生的事件。
這項結果指出了明確的改善方向:安全地減少傳給 FindMinTime 的候選條件。目標是在維持模擬結果不變的前提下,只略過已不需要評估的可能性。
方法:移除不可能再次成立的條件
想像一顆球沿階梯向下彈跳。一旦越過某一階並繼續向前,那一階就不會再影響球。看圖的人會立刻忽略球後方的階梯,原始演算法卻仍逐一檢查。
困難之處是證明被移除的守衛條件之後不會再用到。若只因為條件目前不成立就移除它,一旦日後再次成立,模擬就可能在沒有警告的情況下產生錯誤結果。因此,提出的方法利用單調性,也就是判斷變數在某段時間內是否能保證持續增加或持續減少。
變化方向保持不變時
第一種方法適用於變數在整個模擬期間都朝同一方向變化的情況。在表面分段模型中,球的水平位置始終增加。一旦越過某個區段,該區段的守衛條件就不可能再次成立。模型檢查技術可以在模擬前驗證這項性質,因此執行時能安全地移除已不再相關的守衛條件。
變化方向反轉時
許多系統不會永遠朝單一方向變化:變數可能先增加,再反轉方向而減少。因此,論文提出第二種方法:先假設變化方向,再以斷言監測這個假設。方向改變時,重新啟動約束縮減程序,並恢復上一個單調區間中移除的守衛條件。這個方法在本專案中僅完成設計,尚未實作或評估。
結果:評估模型的執行時間約減半
我實作了一致單調性的方法,並以表面分段模型評估。兩種演算法的執行時間都隨區段數量增加,但所提方法始終較快。擬合曲線的最高次項係數由 1.1463 降至 0.6083;在這項基準測試中,整體模擬時間約減半。
這項結果僅適用於本次基準測試。當模型包含大量帶有守衛條件的物件、能證明變化方向,而且執行過程中有守衛條件永久不再相關時,這個方法才有用。這不代表所有 HydLa 模型都能以兩倍速度執行。
研究心得
這項研究運用系統行為的已知性質,縮小模擬器需要考慮的可能性集合。在維持結果不變的前提下縮小搜尋空間,是約束程式設計的優勢。
本次實作與評估涵蓋變數持續朝單一方向變化的情況。處理方向反轉的方法仍停留在設計階段,尚待評估。除了單調性,其他性質也可能有助於辨識不必要的約束。
這段經驗影響了我目前的設計方向:定義 AI 可以搜尋解答的條件與界限。面對複雜結果時,界定哪些因素可以安全地略過,與決定要計算什麼同樣重要。
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