Paths through a maze of rectangles

Abstract

Abstract Finding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.