You Remind Me of the Babe

Recently, I was reminded of a toy my grandparents had when I was growing up, a marble maze like this one:

Amazon

Turning the knobs tilts the board, causing the marble to roll. I was curious if I could find the fastest possible path through the maze. The key is that the tilt of the board limits how much acceleration you can apply, which in turn limits the speed with which the ball can navigate turns.

Since hitting walls would introduce sharp changes in velocity, which makes things difficult to optimize, I decided to simplify the problem by leaving out the holes, and penalizing any path that passes through a wall – With a high enough penalty, the optimum solution should not allow any Kool-Aid balls.

The first problem to solve is representing the maze, and a path through it. I found a Python package that handles both of these, pyamaze. This package can generate a maze on a grid of squares, and give the series of points leading from the start to the finish. To go from these points to a continuous path, I decided to use spline curves. These are a technique for generating a function that passes smoothly through a given set of control points. By moving each control point around inside its square, we can try to find the fastest way to navigate the maze. Here's an example, using the initial centered points:

The spline curves are parameterized by a variable, which we'll call λ. This is defined such that each integer corresponds to one of the control points. This variable may not obey our acceleration limits, when going around a sharp turn for example. We can imagine a function λ(t), then use the chain rule to write a relationship between our spline curves, and the acceleration of the ball:

This is for the horizontal motion of the ball, and we can write a similar equation for the vertical motion. I struggled for a while with how best to derive the λ equation from these, and settled on the simpler solution of setting d^2λ/dt^2 = 0. This means λ increases linearly with time, at a constant rate given by

where a_max is the maximum acceleration applied by gravity.

Now we have a method to get the time associated with a given path – It remains to find a path with the shortest time. Each control point is an input, which means this problem has a high number of dimensions. We also need to keep each point inside its square, meaning this is a constrained problem. Both of these qualities make it difficult to optimize. I decided to use Scipy's dual annealing method, which gave good results. I may talk about annealing in a future post, since it's an interesting topic (which you may have more experience with than you expect).

In the animation below, I show the steps of the optimization. At each step, the algorithm adjusts the positions of the control points to minimize the total time, shown at the top.

Notice that as the optimization progresses, the path gets more straight lines, which allow the ball to accelerate without the speed limits imposed by tight curves. You can see this effect if we animate the ball's path in time:

We can check we're obeying the acceleration limits by plotting the value of the equation given above:

There appears to be some numeric error I couldn't get rid of that makes us cross the limits I set a little bit, but overall it looks like the best strategy involves whipping the knobs from one extreme to the other, suggesting this is another game where spastic movements are key!