[4J3-GS-5] Agents:

[4J3-GS-5-02] Pre-Marking Direction for Efficient Search in Directed Controller Synthesis

〇Yoshito Ohata¹, Takuto Yamauchi², Takanori Hirano², Kenji Tei¹ (1. Institute of Science Tokyo, 2. Waseda University)

Keywords:Discrete Controller Synthesis, Heuristic, Path Finding

離散事象システムの制御において，Directed Controller Synthesisは要求を満たす制御器を自動合成する手法として知られている．従来のヒューリスティックでは，Markingアクションまでの推定距離のみを用いて探索の優先順序を決定するため，モデル間の同期に関する制約を十分に考慮できず，探索効率が悪化する問題があった．本論文では，モデル間の同期を考慮した探索優先度ヒューリスティックであるPre-Marking Directionを提案する．Pre-Marking Directionは，Markingアクションを発火させるために必須となる同期アクションを特定し，それを基準として優先度を決定する．ベンチマークによる評価では，本手法を適用可能な問題において，従来手法と比較して合成時間を最大99.8%，メモリ使用量を最大96.9%削減できることを確認した．