Compass-free Navigation of Mazes
Phil Scott, Jacques Fleuriot · EPiC series in computing · 2018
If you find yourself in a corridor of a standard maze, a sure and easy way to escape is to simply pick the left (or right) wall, and then follow it along its twists and turns and around the dead-ends till you eventually arrive at the exit. But what happens when you cannot tell left from right? What if you cannot tell North from South? What if you cannot judge distances, and have no idea what it means to follow a wall in a given direction? The possibility of escape in these circumstances is suggested in the statement of an unproven theorem given in David Hilbert's celebrated /Foundations of Geometry/, in which he effectively claimed that a standard maze could be fully navigated using axioms and concepts based /solely/ on the relations of points lying on lines in a specified order. We discuss our algorithm for this surprisingly challenging version of the maze navigation problem, and our HOL Light verification of its correctness from Hilbert's axioms.