Escaping the maze: the Eikonal Equation unveiled
Have you ever been stuck in a maze, desperately searching for the quickest way out? Well, fear not, because the Eikonal Equation might just be your guiding light.
The Eikonal equation, a partial differential equation that models the evolution of wave fronts, finds a surprisingly practical application in the realm of path planning, particularly in the quest to escape mazes. Let’s dive into the mathematical intricacies and unveil its relevance to navigating the twists and turns of labyrinthine puzzles.
At its core, the Eikonal equation describes the propagation of wave fronts, such as shock waves or light rays and it is of interest in geometrical optics, computer vision, computational fluid dynamics, robotics etc. In the context of maze navigation, imagine each point in the maze as a potential source of a wave. The goal is to find the travel time from each point to the exit — the shorter the time, the better.
Let us consider the abstract problem of moving from a starting point and let us suppose that we want to reach a target point which can be any point in a target set Γ. We want to do that in the minimum possible time.
In the curve parameterization above, t is just the parameterization variable and does not actually represent the time. The time will be noted by T.
We suppose that each point where we can move in space is associated to a speed c. There can be points for which the speed is 0. They can be the walls of our maze. To minimize the time, we should choose the trajectory across which the motion speed keeps as low as possible.
To compute the overall time we take to complete the trajectory, consider the figure below illustrating an infinitesimal portion of curve.
The length of the infinitesimal curve is
so that the corresponding traveltime is
The overall traveltime associated to the whole trajectory is then
In the following, we will denote by
the traveltime of the minimum time trajectory from a certain starting point to any point in Γ. The function U in known as the eikonal function.
We now reformulate the problem of finding the minimum-time trajectory as the solution of a differential equation. To this end, let us consider the following figure.
Let us decompose the time needed to move from the starting point to the final one as the sum of two contributions, that is, the time needed to move from the starting point to an intermediate point and the time needed to move from the latter to the destination position. In other words:
Let us also suppose that the intermediate point is at an infinitesimal distance a from the starting point. In this way, the speed c can be considered approximately constant and equal to its value at the starting point for all the points inside a ball of radius a. This means that the time to move from the starting point to the intermediate one can be approximated as follows:
Accordingly,
If we now expand the time at the intermediate point around the starting point, we obtain:
If we now plug the above evaluation of the minimum time in the last approximate equation, we have
On considering that
then we can write
so that, finally,
which means
The above equation holds true for each starting point of the domain of interest and is the so called eikonal equation.
Solving the eikonal equation for each point of a domain of interest simplifies the determination of the minimum traveltime curve. Solving the eikonal equation first and then determining the minimum traveltime curve is an approach of the so called dynamic programming family which consists into dividing a complex problem into simpler sub-problems, recursively.
Once solved the eikonal equation, the minimum traveltime curve can be determined as
To convince ourselves that this is possible, let us assume that such a curve in fact exists and that it is such that
Along the curve, the minimum traveltime U should be decreasing since along it we approach the target set. Let us verify this proposition. We have:
which means that
Exploiting now the equation for the determination of the curve from the eikonal function U, then
proving that the eikonal function U is decreasing along the optimal curve.
Furthermore, the function U should equal the total traveltime along the curve. To check this point, let us notice that
From the above reported total derivative expression of the eikonal function, we have
On exploiting the above reported determination of the curve from the minimum time (eikonal) function U, then
But U must satisfy the eikonal equation. Accordingly,
Finally, on exploiting once again the above assumed link between curve and eikonal function, we achieve
