[1N1-GS-5] Agents: basic theory

[1N1-GS-5-02] Partial Problematization Algorithm for Time Reduction of Makespan Comparison in Discrete Controller Synthesis

〇Yuki Shimizu¹, Takuto Yamauchi¹, Kenji Tei¹ (1. Waseda University)

Keywords:Discrete Controller Synthesis, Reactive System, Labeled Transition System

System optimization needs to be achieved according to the evaluation indicators.The study of qualitative makespan comparisons provided an algorithm that not only guaranteed safety, but also automatically generated the optimal process in terms of time efficiency from qualitative execution time data.However, this algorithm of makespan comparison has challenges in computational cost and cannot be applied to large models.In this paper, we propose a partial problematization algorithm for the makespan comparison problem that improves the computational cost.The proposed method reduces the computational cost of the comparison problem by finding the state space to be compared in the model, and then performing the makespan comparison for each partial problem.We tested our method on multiple patterns of models, and has succeeded in reducing the comparison time by up to 91.7\% while maintaining the equivalence of the generative controller for models consisting of multiple subproblems with convergence to a single end state and branches with contingencies.