堀內貴文

約束程式設計學士論文

概要

模擬中可能發生的事件越多,就越需要反覆檢查大量條件。但如果隨著模擬進行,能確定某個條件不可能再次成立,是否就能安全地略過它?我為混合系統建模語言 HydLa 設計並實作了一種方法,利用變數的變化方向,移除不再需要檢查的條件。

在評估模型中,這個方法使執行時間縮短至原始演算法的約一半,且不改變模擬結果。效能改善來自運用問題本身的結構,減少需要考慮的可能性。

透過這項研究建立的約束程式設計觀點,至今仍是我處理作品集中各項專案的基礎:不逐一指定結果,而是定義規則、優先順序與界限,再推導出符合條件的解。


問題:可能性越多,執行時間越長

HydLa 以數學與邏輯約束描述混合系統,也就是結合連續變化與離散事件的系統。模型不必逐步指定執行程序,而是宣告必須成立的條件,再由模擬器找出符合條件的行為。

當模型包含許多條件式規則時,模擬器會反覆檢查大量候選條件。即使某些條件已不可能再次成立,仍會留在候選集合中。模型越大,這些不必要的檢查就帶來越多計算負擔。

模型:結合連續與離散變化

彈跳的球是混合系統的一個簡單例子。球在空中時,位置與速度持續變化;碰到地面則觸發離散的反彈事件。恆溫器、汽車與機器人,也在不同尺度上結合了這兩種變化。

評估使用的模型,是一顆水平移動的球,在分成多個區段的表面上彈跳。每個區段都有一項條件式規則,讓球到達該範圍時反彈。增加區段數量可讓模型表達更多物件,同時也增加模擬器必須檢查的條件。

HydLa 原始碼,定義一顆水平移動的球,在由 N 個相鄰區段構成的表面上反彈。
簡短的 HydLa 模型描述一顆球,以及由 N 個區段組成的表面;每個區段各有一項帶有守衛條件的約束。

瓶頸:條件越多,執行時間越長

只有在特定條件成立時才啟用的規則,稱為「帶有守衛條件的約束」(guarded constraint)。在評估模型中,只有當球到達地面,且水平位置落在某個區段內,該區段的反彈規則才會啟用。

區段數量從 10 增加到 200 時,原始模擬器的執行時間大致隨區段數量的平方成長。較大的模型包含更多物件、接觸區域與可能發生的事件,可能使這個問題更加嚴重。

調查:96% 的執行時間花在哪裡?

對 100 個區段的模型進行效能分析後發現,FindMinTime 占了總執行時間的 96%。這個程序反覆評估所有候選守衛條件,找出下一個最早可能發生的事件。

這項結果指出了明確的改善方向:安全地減少傳給 FindMinTime 的候選條件。目標是在維持模擬結果不變的前提下,只略過已不需要評估的可能性。

方法:移除不可能再次成立的條件

想像一顆球沿階梯向下彈跳。一旦越過某一階並繼續向前,那一階就不會再影響球。看圖的人會立刻忽略球後方的階梯,原始演算法卻仍逐一檢查。

紅色軌跡表示球沿黑色階梯向下彈跳。斜線標示的階梯已被越過,不會再影響球。
隨著球向右移動,便能略過後方陰影階梯所對應的守衛條件。

困難之處是證明被移除的守衛條件之後不會再用到。若只因為條件目前不成立就移除它,一旦日後再次成立,模擬就可能在沒有警告的情況下產生錯誤結果。因此,提出的方法利用單調性,也就是判斷變數在某段時間內是否能保證持續增加或持續減少。

變化方向保持不變時

第一種方法適用於變數在整個模擬期間都朝同一方向變化的情況。在表面分段模型中,球的水平位置始終增加。一旦越過某個區段,該區段的守衛條件就不可能再次成立。模型檢查技術可以在模擬前驗證這項性質,因此執行時能安全地移除已不再相關的守衛條件。

紅線從時間 0 的 α 上升至模擬結束時的 β,代表在整個模擬區間內持續增加的變數。
一致單調性表示變化方向在整個模擬區間內保持不變。

變化方向反轉時

許多系統不會永遠朝單一方向變化:變數可能先增加,再反轉方向而減少。因此,論文提出第二種方法:先假設變化方向,再以斷言監測這個假設。方向改變時,重新啟動約束縮減程序,並恢復上一個單調區間中移除的守衛條件。這個方法在本專案中僅完成設計,尚未實作或評估。

五張圖依序呈現最初假設的遞增區間、斷言失敗、新的遞減區間、第二次斷言失敗,以及逐步辨識單調區間的過程。
斷言失敗將變數的行為分成數個區間,每個區間都可視為單調。

結果:評估模型的執行時間約減半

我實作了一致單調性的方法,並以表面分段模型評估。兩種演算法的執行時間都隨區段數量增加,但所提方法始終較快。擬合曲線的最高次項係數由 1.1463 降至 0.6083;在這項基準測試中,整體模擬時間約減半。

這項結果僅適用於本次基準測試。當模型包含大量帶有守衛條件的物件、能證明變化方向,而且執行過程中有守衛條件永久不再相關時,這個方法才有用。這不代表所有 HydLa 模型都能以兩倍速度執行。

模擬時間與表面區段數量 N 的關係圖。N 從 10 到 200 時,所提方法始終較快。N = 200 時,所提方法約需 250 秒,原始演算法則約需 470 秒。
在評估模型中,所提方法(方形)的執行時間約為原始演算法(圓形)的一半。

研究心得

這項研究運用系統行為的已知性質,縮小模擬器需要考慮的可能性集合。在維持結果不變的前提下縮小搜尋空間,是約束程式設計的優勢。

本次實作與評估涵蓋變數持續朝單一方向變化的情況。處理方向反轉的方法仍停留在設計階段,尚待評估。除了單調性,其他性質也可能有助於辨識不必要的約束。

這段經驗影響了我目前的設計方向:定義 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