Home > Reflections | ⏮️ ⏭️

2024-05-19

Pod Racing Continued

Yesterday I tried several iterations on my intuitive algorithm.
It seems that every added sophistication reduced overall performance.
This shouldn’t really be surprising.
Optimization is often unintuitive.
While I can intuit and implement a strategy, it’s hard to improve the overall performance without an explicit objective function.
Tractable optimization problems often take the form: minimize (or maximize) a single value under some constraints.
Having a single optimization variable is important.
Attempting to optimize multiple values simultaneously is much more difficult.
It may be fair to say that it’s often intractable or even impossible.
So when we’re tempted to optimize multiple values simultaneously, it can be fruitful to pick the objective we care most about and transform the others into constraints.
For example, if we want to simultaneously minimize the duration and cost of a project, we might instead minimize duration under the constraint that cost stays below some threshold.
In this case, I think our optimization problem is something like: minimize time to complete the race under the constraint that we pass through every way point in the correct order.
This sounds nice. It seems like the most direction expression of our ultimate goal. But how do we solve it?
A brute force approach could be to

1. generate all possible strategies to complete the race
2. delete every strategy that doesn’t pass through all the checkpoints in the correct order
3. pick the remaining strategy with the best time
   This problem seems computationally intractable.
   What even is a strategy to complete the race?
   Maybe a strategy is a path around the map.
   Not only are there a very large number of possible paths, but we’d need to add a constraint that our pod can actually follow the path given the game’s physics engine.

One step we could take toward tractability could be to reduce the vast search space with some simplifying assumptions.
Another approach could be to focus on solving a series of local optimization problems rather than a single global optimization problem.

The first intuitive algorithm I implemented is essentially a series of local optimization problems.
The implicit goals are to get to the next checkpoint as quickly as possible.
I say that’s the implied goal, rather than an explicit goal, because the explicit strategy is to

1. always aim at the next checkpoint
2. maintain 100% throttle reduced proportionally to the difference between our pod’s heading and the next checkpoint
   So it’s not even explicitly optimizing for time to each checkpoint.
   Expressed as an optimization problem, it would be more accurate to say we’re minimizing error in trajectory to the next checkpoint.
   Honestly, I don’t think it’s technically even an optimization problem.
   We really just have a heuristic: reduce throttle by an arbitrarily chosen factor that’s proportional to the error in trajectory to the next checkpoint.
   Despite the lack of rigor, this heuristic performed quite well for a while.
   So let’s see if we can improve the performance with the use of PID controller.

Let’s start by rewriting our sample Python code into TypeScript.

type PIDParams = {  
  kp: number  
  ki: number  
  kd: number  
  measurement: number  
  setpoint: number  
  time: number  
}  
type PIDState = {  
  control: number  
  error: number  
  integral: number  
  time: number  
}  
const pid = ({ kp, ki, kd, measurement, setpoint, time }: PIDParams, s: PIDState): PIDState => {  
  const error = setpoint - measurement  
  const de = error - s.error  
  const dt = time - s.time  
  const p = kp * error  
  const i = s.integral + ki * error * dt  
  const d = kd * de / dt  
  const control = p + i + d  
  return {  
    control,  
    error,  
    integral,  
    time  
  }  
}  

Now let’s apply this function in our pod racing game.
Our measurement will be the angle between our pod’s heading and the next checkpoint.
Our setpoint will be zero, implying that we want our pod pointed at the next checkpoint.
Our control variable will be the desired reduction in throttle.