Bachelor's Thesis on Constraint Programming
June 2019
Overview
As a simulation includes more possible events, it must repeatedly evaluate more conditions. But if its progress establishes that a condition can never become true again, can that condition safely be skipped? I designed and implemented a method for HydLa, a hybrid-systems modeling language, that uses the direction of variable changes to remove conditions that no longer need to be checked.
In the evaluation model, the method reduced runtime to roughly half that of the original algorithm without changing the simulation results. The improvement came from using the problem’s structure to reduce the possibilities under consideration.
The constraint-programming perspective developed through this research now underpins my approach to the projects in my portfolio: rather than specifying every result directly, define the rules, priorities, and boundaries, then derive solutions that satisfy them.
Problem: More possibilities mean longer runtimes
HydLa describes hybrid systems, which combine continuous changes and discrete events, through mathematical and logical constraints. Instead of specifying every procedural step, the model declares the conditions that must hold, and the simulator finds behavior that satisfies them.
In models with many conditional rules, the simulator repeatedly checks a large set of candidates. Even conditions that can no longer become true remain in that set. As the model grows, these unnecessary checks add to the computational work.
Model: Combining continuous and discrete change
A bouncing ball is a simple example of a hybrid system. Its position and velocity change continuously while it is in the air, and hitting the floor triggers a discrete bounce event. Thermostats, cars, and robots also combine these two types of change, at different scales.
The evaluation used a model of a ball moving horizontally and bouncing across a surface divided into segments. Each segment has a conditional rule that causes the ball to bounce when it reaches that area. Adding segments allows the model to represent more objects, but also increases the number of conditions the simulator must check.
Bottleneck: More conditions increase runtime
A rule that becomes active only when a condition is satisfied is called a guarded constraint. In the evaluation model, a segment’s bounce rule becomes active only when the ball reaches the floor and its horizontal position lies within that segment.
As the number of segments increased from 10 to 200, the original simulator’s runtime grew approximately with the square of that number. Larger models can amplify this problem as they include more objects, contact regions, and possible events.
Investigation: Where did 96% of the runtime go?
Profiling the model with 100 segments showed that FindMinTime accounted for 96% of the total runtime. This routine finds the earliest possible next event by repeatedly evaluating all candidate guard conditions.
This identified a focused opportunity for improvement: safely reduce the candidates passed to FindMinTime. The goal was to skip only possibilities that no longer needed evaluation, while preserving the simulation results.
Approach: Remove conditions that cannot become true again
Imagine a ball bouncing down a staircase. Once it has passed a step and continues forward, that step can no longer affect it. A person looking at the diagram immediately ignores the steps behind the ball; the original algorithm continued to inspect every one.
The difficult part is proving that a removed guard will not be needed later. Removing it merely because it is false now could silently produce an incorrect result if it becomes true again. The proposed method therefore uses monotonicity: whether a variable can be guaranteed to keep increasing or decreasing over a given interval.
When the direction of change stays the same
The first approach applies when a variable moves in one direction throughout the simulation. In the segmented-surface model, the ball’s horizontal position always increases. Once it passes a segment, that segment’s guard can never become true again. Model-checking techniques can verify this property before simulation, allowing guards to be safely removed as they become irrelevant during execution.
When the direction of change reverses
Many systems do not move in one direction indefinitely: a variable may increase, reverse direction, and then decrease. The thesis therefore proposed a second approach. It assumes a direction of change and monitors that assumption with assertions. When the direction changes, the reduction process restarts, restoring guards that were removed during the previous monotonic interval. This approach was designed but not implemented or evaluated in this project.
Result: Roughly half the runtime in the evaluation model
I implemented the uniform-monotonicity approach and evaluated it with the segmented-surface model. Runtime increased with the number of segments for both algorithms, but the proposed method consistently took less time. In the fitted curves, the highest-order coefficient fell from 1.1463 to 0.6083. Overall simulation time in this benchmark was roughly halved.
The result is specific to this benchmark. The method is useful when a model contains many guarded objects, the direction of change can be proven, and guards become permanently irrelevant during execution. It does not imply that every HydLa model will run twice as fast.
What I learned
This research used known properties of a system’s behavior to reduce the set of possibilities the simulator needed to consider. Narrowing the search space while preserving the results is a strength of constraint programming.
The implementation and evaluation covered variables that continued changing in one direction. Handling reversals remained at the design stage and still needed evaluation. Properties other than monotonicity may also help identify unnecessary constraints.
This experience informs my current interest in designing the conditions and boundaries within which AI can search for solutions. When working with complex outcomes, defining what can safely be ignored matters as much as defining what to compute.
Takafumi Horiuchi and Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02