论文标题
随机游戏的有界价值迭代中最宽的路径和全球传播
Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
论文作者
论文摘要
以可及性目标解决随机游戏是一个基本问题，尤其是在定量验证和综合方面。为此，有界价值迭代（BVI）作为一种有效的迭代方法引起人们的注意。但是，BVI的性能通常会受到确保收敛所需的昂贵的最终组件（EC）计算的阻碍。我们的贡献是一种新型的BVI算法，除了通过Bellman更新的局部传播外，BVI的典型繁殖，这是BVI的典型代表，这是对ECS不受阻碍的上限的全球繁殖。为了以计算方式进行全局传播，我们构建了加权图并解决其中最广泛的路径问题。我们的实验表明，算法比依赖于EC计算的BVI算法的性能优势。
Solving stochastic games with the reachability objective is a fundamental problem, especially in quantitative verification and synthesis. For this purpose, bounded value iteration (BVI) attracts attention as an efficient iterative method. However, BVI's performance is often impeded by costly end component (EC) computation that is needed to ensure convergence. Our contribution is a novel BVI algorithm that conducts, in addition to local propagation by the Bellman update that is typical of BVI, global propagation of upper bounds that is not hindered by ECs. To conduct global propagation in a computationally tractable manner, we construct a weighted graph and solve the widest path problem in it. Our experiments show the algorithm's performance advantage over the previous BVI algorithms that rely on EC computation.
