How to solve any maze using the digits of π
Is there a universal, deterministic sequence of actions that can solve any maze, assuming that the actions are applied blindly with no sensor feedback? According to the recent paper Universal Plans: One Action Sequence to Solve Them All! by Kalle G. Timperi, Alexander J. LaValle, and Steven M. LaValle, the answer is “yes”. Even better, the universal sequence will work independently of the choice of maze, the choice of starting point, and the choice of target location.
The picture above shows a robot (shown in red) whose goal is to navigate a grid environment and reach the green circle. The robot is trying to execute the sequence of actions “right, right, right, right, down”. In the situation on the left, the robot is unable to execute the second, third, and fourth actions in the sequence because of an obstruction immediately to its right. As a result, it fails to reach the target. On the other hand, if the robot starts at the location shown in the situation on the right, executing this sequence of actions results in success.
The top picture shows a 30 by 30 maze, in which the robot’s goal is to reach the green point in the bottom right starting from the red point in the top left. A robot trying to solve the maze would eventually succeed if it tried to move in a random direction at each stage, but the goal is to solve the matrix deterministically, without modifying the algorithm in the light of sensor feedback. A reasonable substitute for a random string of numbers might be a fixed number whose digits look random, such as π. At each stage of the procedure, the robot has four potential choices: moving up, down, left, or right, so it is convenient to work in base 4.
The number π is 3.1415926535897932… in base 10, and 3.0210033312222020… in base 4. We can then interpret the base 4 digits of π as directions (up, down, left, or right) with the understanding that if the robot tries to move in an obstructed direction then it does nothing and moves on to the next instruction. The solution to the maze shown in the top picture was found in 213675 steps using the base 4 digits of π starting at the 1,200,000th place. But will this work for any maze, and for any starting and ending points?
The authors prove that a universal plan is possible if the number being used to generate the digits (π in this case) is a normal number. A normal number in base 10 is one whose decimal expansion has the property that all digits are equally likely to show up, all pairs of digits are equally likely to show up, and the same applies to triplets of digits, and so on. For example, an arbitrary 10-digit string like 4815162342 would show up, on average, every 1010 places in the decimal expansion of a normal number. A well-known example of a normal number is the Champernowne constant. In base 10, this is obtained by concatenating the base 10 representations of the integers after a decimal point (“zero point one two three four five six seven eight nine ten eleven…”). The Champernowne constant can also be defined for other number bases.
The base 4 version is useful in the maze context, because it provides a universal deterministic sequence to solve the maze problem and other similar problems in which a robot has four choices at every step. An example of one of these similar problems is shown above. In this case, a robot is placed in a 100 by 100 grid at the red dot inside the red circle. Its goal is to reach the green dot inside the green circle, and the black areas represent obstructions. A real life example of this might be a robot vacuum cleaner trying to reach its dock at the green point, and the obstructions might be items of furniture. The robot in the left hand version of the experiment is using the digits of π as its algorithm, and reaches the goal in 48291 steps after visiting 5220 of the 7128 possible points in the grid. The robot in the right hand version of the experiment is using the digits of the Champernowne constant in base 4. It takes far longer to reach the goal (almost 12 million steps!) and the picture shows its progress after 50000 steps.
It seems from this that using the digits of π form a much more useful navigational tool than those of the Champernowne constant. Unfortunately, it is not known whether the digits of π are normal in any base, let alone base 4. The same applies to other familiar rational numbers, like √2 and the natural logarithm of 2, although these are all conjectured to be normal numbers.
The paper investigates some variants of the maze problem, including one in which the robot can vary the length of the steps it takes, which allows greater navigational precision. The picture above shows the result of using the base 4 digits of π starting at the 1,200,000th position to solve a continuous planning problem in 970 steps. The robot starts at the red dot near the top left, and has the goal of reaching the green area in the bottom right.
Picture credits and relevant links
The four diagrams come from the paper by Kalle G. Timperi, Alexander J. LaValle, and Steven M. LaValle.
The two text graphics are my own work.
Wikipedia has articles on the six 9s in π and Champernowne’s constant.
Substack management by Buzz & Hum.
>> "We can then interpret the base 4 digits of p as directions (up, down, left, or right) with the understanding that if the robot tries to move in an obstructed direction then it does nothing and moves on to the next instruction."
I'm not clear on the latter part of that, what it means to move on to the next instruction. Just skip to the next digit, I assume? I wonder what would happen if you reset to the starting position and picked another starting point in the digit sequence. Though, if we're simulating an actual robot navigating, that doesn't fit.
I'm curious about the efficiency. It would be interesting to see how often points in the maze are revisited. Does the robot spend a lot of time wandering around a small area.
It is a cool way to approach mazes with loops preventing a right- (or left-) hand rule from working. I have a maze generator I wrote. Might be fun to try this.
I had some fun a while back using the digits of pi to drive a graphics turtle. Similar to a random walk but driven by the decimal digits of pi. Go a fixed length then turn in the direction given by 360 / (36 * digit). Made kind of an interesting animated video! Random walks using different bases to control the possible angles (3, 4, 5...) make interesting patterns, too.
Why isn’t this intuitively obvious?
For any maze there are only a finite number of states, so there is a sequence which works for that maze by assuming an initial state, exiting from there, if it doesn’t work crossing off from your list of possible initial states the one that was used up, assuming another initial state, applying the moves you made so far to derive your current state, exiting from there, it that doesn’t work crossing that second assumed initial state off your list, etc.
Any normal number will obviously have somewhere in its sequence of digits the sequence that works for the maze you’re in, so if you haven’t escaped by the time you reach that point you will escape with that sequence.