Bachelor's Thesis on Constraint Programming

Overview

As the number of possible events grows, a simulator repeatedly evaluates an expanding set of conditions. But once the system’s progress proves that a condition can never become true again, can the simulator safely stop checking it? Using the direction of value change as evidence, I designed and implemented a method for HydLa, a hybrid-systems modelling language, to remove unnecessary conditions from the active search.

In the evaluation model, the execution time was reduced to approximately half of the conventional time without changing the simulation results. The important point is not that all calculations were uniformly sped up. It is that, by using the structure of the problem, the very possibilities that needed to be considered were reduced.

The constraint-programming perspective developed through this research now underpins my design philosophy: rather than specifying every result directly, define the rules, priorities, and boundaries, then derive solutions that satisfy them.

Problem — The more possibilities there are, the slower the calculation becomes

HydLa is a language for describing "hybrid systems," which combine continuous changes and discrete events, as mathematical and logical constraints. Without writing out the order of procedures, you can simulate behavior that satisfies conditions by declaring what should hold.

On the other hand, in models with many rules that become effective depending on conditions, the simulator repeatedly checks a large number of candidates. Since candidates remain even for conditions that have already passed and will never be satisfied in the future, unnecessary calculations accumulated as the model grew larger.

Subject — Systems that combine continuous and discrete change

A bouncing ball is a clear example of a hybrid system. In the air, its position and velocity change continuously, and the moment it hits the floor, a discrete event of bouncing occurs. Thermostats, cars, and robots also have the same two types of changes internally, though on different scales.

For the evaluation, a model was used in which a ball moving horizontally bounces off a surface divided into multiple sections. Each section of the surface has a conditional rule that 'the ball will bounce back if it comes into this area.' Increasing the number of sections allows for more objects to be represented, but at the same time, the conditions that the simulator needs to check also increase.

Bottleneck — The number of conditions increases the computational complexity

A rule that becomes effective only when certain conditions are met is called a 'guarded constraint.' In the evaluation model, the rebound rule for a section becomes effective only when the ball reaches the floor and its horizontal position is within a specific section.

When the number of partitions was increased from 10 to 200, the conventional simulator became slower roughly in proportion to the square of the number of partitions. In large-scale models, the same problem becomes larger because the number of objects, contact areas, and possible events increases.

Investigation — Where was 96% of the processing time spent?

When measuring the processing time, in a model with 100 sections, 96% of the total time was spent on FindMinTime. This is the process of searching for 'the earliest next event' from among the candidates. As a result, all guard conditions were repeatedly evaluated.

This made the intervention point clear. Rather than redesigning the entire computation, the simulator only needed a safe way to reduce the candidates passed to FindMinTime. The goal was to remove possibilities that no longer needed evaluation without changing the simulation result.

Approach — Safely remove conditions that will never be met again

Imagine a ball bouncing down a staircase. Once it has passed a step and continues forwards, 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 does not change

The first measure applies when a variable moves in only one direction throughout the entire simulation. In a model with divided surfaces, the horizontal position of the ball always increases. Once it passes a certain section, the conditions of that section will never be satisfied again. Since this property can be verified before the simulation using model checking techniques, guards that become unnecessary as the execution progresses can be safely removed.

In cases where the direction of change reverses midway

Many real-world systems do not move in only one direction indefinitely. Variables can increase, change direction, and then decrease. The paper therefore presented a second approach. First, the direction is assumed, and this assumption is monitored with assertions, and when the direction changes, the reduction process is restarted from that point. Guards removed for a single monotonic interval are restored when the next interval begins.

Result — Evaluation model execution time reduced by about half

We implemented support for uniform monotonicity and evaluated it using a model with subdivided surfaces. Both the original algorithm and the proposed method take longer as the number of sections increases. However, the proposed method consistently required less work. Comparing the fitted curves, the highest-order coefficient decreased from 1.1463 to 0.6083, and in this benchmark, the total simulation time was roughly halved.

This is not a claim that every HydLa model will run twice as fast. What it shows is where this method is effective — in models with many guarded objects, where the directions of change can be proven, and where guards become permanently irrelevant during execution.

What this research changed in my design practice

What was done in this research was not to speed up individual computations little by little. It was to use what is known about the system's behavior to reduce the set of possibilities that need to be considered. The idea of narrowing the search space without changing the results is the strength of constraint programming.

What was implemented and evaluated is the case where a variable continues to move in one direction. If the direction of change reverses along the way, it was left at the design stage, and evaluation remains a future task. There is also room to use properties other than monotonicity to find further unnecessary constraints.

The reason I am now trying to design the conditions and boundaries that AI can explore, rather than directly designing AI's output, is also connected to this experience. When dealing with complex outcomes, it is as important to define what does not need to be considered as it is to define what to compute.