堀内贵文

约束编程本科毕业论文

概要

仿真中的潜在事件越多,就越需要反复检查更多条件。但如果根据仿真的进展,可以确定某个条件不可能再次成立,是否就能安全地跳过它?针对混合系统建模语言 HydLa,我设计并实现了一种方法,利用变量的变化方向,移除不再需要检查的条件。

在评估模型中,这一方法在保持仿真结果不变的前提下,将运行时间缩短到了原算法的约一半。改进来自对问题结构的利用:减少仿真需要考虑的可能性。

这项研究形成的约束编程思路,如今也支撑着我在作品集中各项目的设计方法:先定义规则、优先级与边界,再推导出满足这些要求的解,而非直接指定每一个结果。


问题:可能性越多,运行时间越长

HydLa 通过数学和逻辑约束描述混合系统,即同时包含连续变化与离散事件的系统。模型无需逐一指定操作步骤,只需声明必须满足的条件,再由仿真器求出符合这些条件的行为。

在条件规则较多的模型中,仿真器需要反复检查大量候选项。即使某些条件已不可能再次成立,它们仍会留在候选集合中。随着模型扩大,这些不必要的检查会增加计算量。

模型:连续变化与离散事件的结合

弹跳的球是混合系统的一个易于理解的例子。在空中时,位置和速度连续变化,而在接触地面的一瞬间,会发生弹回这样的离散事件。温控器、汽车、机器人也是如此,虽然规模不同,但内部也存在相同的两种变化。

评估使用了一个球在水平方向移动、并在分段表面上弹跳的模型。每个区段都有一条条件规则:球到达该区域时便会反弹。增加区段可以让模型表达更多对象,同时也会增加仿真器需要检查的条件。

HydLa 源码:定义一个水平移动的球,以及它在由 N 个相邻区段构成的表面上的反弹行为。
一段简短的 HydLa 模型描述了一个球和由 N 个区段构成的表面,每个区段都带有守卫约束。

瓶颈:条件越多,运行时间越长

只有在条件满足时才生效的规则,称为守卫约束(guarded constraint)。在评估模型中,只有当球到达地面、且水平位置位于某一区段内时,该区段的反弹规则才会生效。

当区段数量从 10 增加到 200 时,原仿真器的运行时间大致按区段数量的平方增长。更大的模型包含更多物体、接触区域与潜在事件,可能会进一步放大这一问题。

调查——处理时间的96%集中在哪儿

对包含 100 个区段的模型进行性能分析后发现,FindMinTime 占总运行时间的 96%。这个例程通过反复计算所有候选守卫条件,寻找下一次可能最早发生的事件。

这明确了一个改进方向:安全地减少传递给 FindMinTime 的候选项。目标是在保持仿真结果不变的前提下,只跳过不再需要评估的可能性。

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

请想象一个沿着台阶跳下的球。如果球越过某一台阶并继续向前,那么这个台阶将不再影响球。看到图的人会立即忽略球身后的台阶。原来的算法则会继续检查每一个台阶。

红色的轨迹显示了球沿着黑色楼梯台阶跳下的路径。网格区域表示那些已经过去、与之无关的台阶。
当球向右移动时,可以跳过球后方阴影台阶所对应的守卫条件。

难点在于证明:移除的守卫条件以后也不会再被需要。如果仅因条件当前为假就将其移除,一旦它再次变为真,仿真便可能在不报错的情况下产生错误结果。因此,所提出的方法利用了单调性:是否能保证某个变量在给定区间内持续增加或持续减少。

变化的方向不改变的情况

第一种方法适用于变量在整个仿真过程中都沿同一方向变化的情况。在分段表面模型中,球的水平位置一直增加。一旦球越过某一区段,该区段的守卫条件就不可能再次成立。模型检验技术可以在仿真开始前验证这一性质,从而在运行过程中安全地移除不再相关的守卫条件。

从时刻0的α向最大时刻的β上升的红线,表示在整个仿真过程中持续增加的变量。
全程单调是指在整个仿真区间内,变量的变化方向保持不变。

当变化方向发生反转时

许多系统不会无限期地沿同一方向变化:变量可能先增加,再反向减少。因此,论文提出了第二种方法:先假设变化方向,再用断言监测这一假设。一旦方向改变,就重新启动约束削减过程,恢复上一单调区间中移除的守卫条件。本项目完成了这一方法的设计,但尚未实现或评估。

五个图展示了假定增加的区间、断言失败、新的减少区间、第二次失败,以及单调区间依次被确定的情况。
断言失败将变化过程划分为多个区间,每个区间内的变化都可以按单调过程处理。

结果——将评估模型的运行时间大约减半

我实现了适用于全程单调变量的方法,并在分段表面模型中进行评估。两种算法的运行时间都随区段数量增加而上升,但所提出的方法始终耗时更少。拟合曲线的最高次项系数从 1.1463 降至 0.6083。在这一基准测试中,仿真的总运行时间缩短了约一半。

这一结果仅适用于本次基准测试。这种方法适合以下模型:包含大量带守卫条件的对象,变量的变化方向可以被证明,而且某些守卫条件会在运行过程中永久失去相关性。这并不意味着所有 HydLa 模型都能快一倍。

仿真时间与表面区段数量 N 的关系。从 10 到 200 个区段,所提出的方法始终更快。在 N = 200 时,原算法约需 470 秒,所提出的方法约需 250 秒。
在评估的模型中,提出的方法(方形)大约只花原始算法(圆形)一半的时间。

从这项研究中获得的视角

这项研究利用系统行为的已知性质,减少仿真器需要考虑的可能性。在保持结果不变的同时缩小搜索空间,正是约束编程的优势之一。

实现与评估覆盖了持续沿同一方向变化的变量。处理方向反转的方法仍处于设计阶段,有待评估。除了单调性,还可能利用其他性质识别不必要的约束。

这段经历影响了我当前的研究兴趣:设计 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