Takafumi Horiuchi

Bachelor's Thesis on Constraint Programming

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.

HydLa source code defining a ball that moves horizontally and bounces on a surface divided into N adjacent segments.
A short HydLa model describes one ball and a surface divided into N segments, each with a guarded constraint.

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.

A red trajectory follows a ball bouncing down black steps. The hatched steps have already been passed and can no longer affect the ball.
As the ball moves to the right, the guard associated with a shaded step behind it can be skipped.

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.

A red line rises from α at time 0 to β at the end of the simulation, representing a variable that increases throughout the simulated interval.
Uniform monotonicity means that the direction of change is maintained throughout the interval being simulated.

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.

Five diagrams show an initially assumed increasing interval, an assertion failure, a new decreasing interval, a second failure, and the successive identification of monotonic intervals.
Assertion failures divide the behavior into intervals, each of which can be treated as monotonic.

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.

Simulation time plotted against N, the number of surface segments. From 10 to 200 segments, the proposed method is consistently faster. At N = 200, it takes about 250 seconds, compared with about 470 seconds for the original algorithm.
In the evaluated models, the proposed method (squares) takes roughly half as long as the original algorithm (circles).

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