Integer Logic Programming Basics
How to use discrete variables and linear constraints to solve complex logical decision-making problems. An introduction to ILP.
Have you ever tried to track something that is constantly moving, using sensors that are constantly lying to you?
If you've built a robot, worked on a GPS tracker, or tried to keep a drone stable in a gusty wind, you've run into this exact problem. Your GPS says you are at coordinates $(X, Y)$, but your accelerometer says you are accelerating left, and your wheels say you've traveled three feet forward. None of these sensors are 100% accurate. They are all noisy, drafty, and slightly broken.
How do you combine all these lying sensors to find the absolute truth?
Enter the Kalman Filter.
Despite its intimidating mathematical reputation, the core concept behind it is beautifully simple and incredibly elegant. Let's break down how it works without drowning in matrix calculus.
Imagine you are trying to guess the temperature outside.
What is the actual temperature?
You wouldn't just take the average (which would be $70^\circ$). Instead, you do a quick mental calculation. You trust the app a bit more than the cheap thermometer, so you guess something like 69°F.
You just ran a manual Kalman Filter in your head.
At its heart, a Kalman Filter is a process of Predicting the future state based on what we know about physics, and then Updating that prediction using incoming sensor measurements. The magic is in how much we weight the prediction versus the measurement.
A Kalman Filter runs in a continuous loop containing two main phases: Predict and Update.
+-------------------+
| Initialize |
+---------+---------+
|
v
+---------+---------+
| Predict | <------+
| (Where should we | |
| be now?) | |
+---------+---------+ | Loop
| |
v |
+---------+---------+ |
| Update | -------+
| (Incorporate new |
| sensor data) |
+-------------------+
Using the rules of physics, we project our current state forward in time.
Next, we get a new measurement from our sensor (e.g., GPS says $X = 13$ meters). Now we have a conflict:
The Kalman Filter calculates the Kalman Gain ($K$). The Kalman Gain is a number between $0$ and $1$ that represents how much we trust our sensor relative to our physics prediction:
Once we calculate $K$, we find our new estimate:
$\text{New Estimate} = \text{Predicted State} + K \times (\text{Measured State} - \text{Predicted State})$
We then update our uncertainty and feed this new estimate back into the loop as the starting point for the next prediction step.
You might think, "Okay, that's just a weighted average. What's the big deal?"
The power of the Kalman Filter lies in three things:
Here is what a 1D Kalman Filter looks like in Python code. It tracks a single scalar value (like temperature):
class KalmanFilter1D:
def __init__(self, initial_state, initial_uncertainty, process_noise, measurement_noise):
self.x = initial_state # Current estimate
self.p = initial_uncertainty # Current uncertainty
self.q = process_noise # How much noise the system adds over time
self.r = measurement_noise # How noisy the sensor is
def predict(self, control_input=0):
# Predict step: Project state and uncertainty forward
self.x = self.x + control_input
self.p = self.p + self.q
def update(self, measurement):
# Update step: Calculate Kalman Gain and correct estimate
kalman_gain = self.p / (self.p + self.r)
self.x = self.x + kalman_gain * (measurement - self.x)
self.p = (1 - kalman_gain) * self.p
return self.x
To use it:
# Initialize with a guess of 20 degrees, high initial uncertainty (10)
# process noise = 0.1, sensor noise = 2.0 (noisy sensor!)
kf = KalmanFilter1D(20.0, 10.0, 0.1, 2.0)
# Simulate receiving noisy measurements over time
measurements = [20.1, 19.8, 20.5, 21.0, 20.3]
for m in measurements:
kf.predict()
estimate = kf.update(m)
print(f"Measured: {m:.2f} -> Estimated: {estimate:.2f}")
The Kalman Filter isn't a complex black box; it's a logical, dynamic tug-of-war between what you expect to happen and what your sensors tell you is happening.
Next time you see a self-driving car merge lanes smoothly, a drone hover perfectly in place, or even your phone's GPS pin stop jumping around, you'll know there's a Kalman Filter quietly doing the math in the background, balancing trust and doubt to find the truth in a noisy world.
I'd love to hear your thoughts or questions. Connect with me on LinkedIn or send me an email!