Solving Mazes: A New Approach Based on Spectral Graph Theory

Abstract

The use of graph theory for solving labyrinths and mazes is well known, understanding the possible paths as the connections between the nodes that represent the corners or bifurcations. This work presents a new idea: minimizing the length of the optimal path formulated as a topology optimization problem. The maze is mapped with finite elements, and then, through the eigenvalues of the Laplacian matrix of the graph, a constraint is imposed over the connectivity between the input and the output. Several 2D examples are provided to support this approach, allowing for unequivocally finding the shortest path in mazes with multiple connections between entrance and exit, resulting in an nonheuristic algorithm.

1. Introduction

A maze is a network of paths, typically designed as a puzzle or game, where the solution consists of reaching the destination point from the starting point, following the shortest route [1]. Techniques for solving mazes has been developed in scientific literature due to their versatile applications across diverse domains in real-world problems, such as autonomous navigation [2,3] or search and rescue using drones [4]. Efficient maze-solving skills have wide-ranging implications for problem solving, not only in physical environments but also in virtual ones. This can be analogized to the task of finding routes with weighted constraints, for instance, in logistics, optimization of road networks, or energetic issues [2,5].

In recent decades, advancements in graph theory and discrete mathematics have enabled the solution of labyrinths and mazes of different complexities and structures. A graph is basically a set of nodes, some (or possibly all) of which are connected by edges, also called links or lines. The way to proceed is to map the maze with nodes which have assigned a numerical value. Pathways are numerically represented as 1, whereas walls are denoted by 0. This leads to the maze being understood as a black and white design. The shortest path is understood as the one that uses fewer black squares. The concept involves converting the matrix of zeros and ones into an undirected simple graph [6], where an edge of weight 1 will connect nodes i and j if the value at position $(i,j)$ of the matrix is 1.

Spectral theory of graphs studies its properties in relation to the eigenvalues or eigenvectors of matrices associated with them [6]. For instance, a graph is connected if there is a path linking any two of its vertices. In graph theory, there is a well-known result linking connectivity to an invariant within one of the matrices associated with a graph: the Laplacian matrix. M. Fiedler [7,8] showed that the multiplicity of zero eigenvalue of the Laplacian matrix is equal to the number of connected components in the graph. Then, a graph will be connected if and only if the second smallest Laplacian eigenvalue is positive. Based on this theory, the work of Steinenberger [9] proposes an algorithm for discovering one of the shortest paths in a simple, connected graph.

Previous works have already demonstrated the capabilities to solve shortest path problems through topology optimization. Works [10,11] employ a quite similar approach to find the optimal trajectory of the movement of a robot in the presence of different obstacles. Both works take advantage of the analogy between this trajectory problem and a heat transfer one, whereby manipulating the conductivity of materials—using insulators for obstacles and thermal conductors for free paths—the route with minimal thermal compliance between a heat source and a sink is found. Both articles also use mazes as benchmark examples for the developed methodologies. Other physics branches also offer solutions to shortest path problems, with many scholarly works focusing on fluid dynamics [12,13].

Some authors have showed interest in maximizing the weighted algebraic connectivity in different communications networks [14,15,16]. Several studies have focused on the constraints of algebraic connectivity in relation to other graph properties [17]. The Laplacian matrix and its associated eigenvalue (or Fiedler eigenvalue) have generated interest among several authors for it many applications, particularly in the partitioning of meshes for parallel computing [18,19].

The aim of this work is to propose a new method to find the shortest path inside a maze. This builds on prior research which integrates spectral graph theory and topological optimization [20,21], demonstrating the potential to manipulate physical connectivity in structural components.

The optimization problem is formulated in terms of a topology optimization problem. The maze is mapped with finite elements and a constraint is imposed over the connectivity between the input and the output through the eigenvalues of the Laplacian matrix of the graph. The minimum number of elements needed is determined when the shortest route that connects both ends of the maze is found.

The manuscript is organized as follows: in Section 2, concepts about algebraic connectivity of graphs are discussed. Section 3 relates graphs to mazes, detailing and solving the topological optimization problem. Numerical verification with different sizes of the maze and numbers of cells are shown in Section 4. Finally, the conclusions are summarized in Section 5.

2. Algebraic Connectivity of Graphs

Graph theory is a branch of mathematics concerned with networks of points connected by lines, also called nodes and edges, respectively [6]. The classical definition of a graph is a mathematical structure used to model pairwise relations between components. Graph theory provides a framework for analyzing and solving problems related with different applications: computer science, social systems, biological systems, etc.

There are many types of graphs, which allow for the creation of really complex structures able to model the applications commented in the previous paragraphs. This work is focused in graphs without loops and multiple lines, and undirected. The latter means that the connection between two nodes have no orientation. An example of an undirected graph is shown in Figure 1 (left). A numerical value, called weight, can be assigned to each link. This parameter may represent the distance between both nodes, the cost, the capacity of the line, or any variable depending of the edge. An example of a weighted graph is depicted in Figure 1 (right).

From a graph, several matrices can be obtained that provide useful information about its structure and properties. From now on, bold will be used to represent vectors and matrices. The most intuitive matrix is the adjacency matrix $\mathcal{A}$, which stores the weighted (or not) connection between nodes. For the graph presented in Figure 1 (right), a number is assigned to each node (1 for a, 2 for b, …) to relate the rows and the columns. The adjacency matrix $\mathcal{A}$ is defined as:

$$\mathcal{A}=\left(\begin{array}{ccccc}0& w_{ab}& 0& w_{ad}& 0\\ w_{ab}& 0& w_{bc}& 0& w_{be}\\ 0& w_{bc}& 0& 0& 0\\ w_{ad}& 0& 0& 0& 0\\ 0& w_{be}& 0& 0& 0\end{array}\right).$$

The next one is the degree matrix $\mathcal{D}$. It stores in the diagonal the connections of each edge. $\mathcal{D}$ for the graph presented before is defined as follows:

$$\mathcal{D}=\left(\begin{array}{ccccc}{w}_{ab}+w_{ad}& 0& 0& 0& 0\\ 0& w_{ab}+w_{bc}+w_{be}& 0& 0& 0\\ 0& 0& w_{bc}& 0& 0\\ 0& 0& 0& w_{ad}& 0\\ 0& 0& 0& 0& w_{be}\end{array}\right).$$

The last matrix used in this work is the Laplacian matrix $\mathcal{L}$. This matrix is specially important in spectral graph theory. The eigenvalues of this matrix provide information about the global connectivity of the graph. $\mathcal{L}$ is computed as the difference between $\mathcal{D}$ and $\mathcal{A}$:

$$\mathcal{L}=\mathcal{D}-\mathcal{A}=\left(\begin{array}{ccccc}{w}_{ab}+w_{ad}& -w_{ab}& 0& -w_{ad}& 0\\ -w_{ab}& w_{ab}+w_{bc}+w_{be}& -w_{bc}& 0& -w_{be}\\ 0& -w_{bc}& w_{bc}& 0& 0\\ -w_{ad}& 0& 0& w_{ad}& 0\\ 0& -w_{be}& 0& 0& w_{be}\end{array}\right)·$$

(1)

A graph is considered to be connected when a path can be found between any two of its nodes. There exists a classical result of spectral graph theory [6] that relates an invariant of the Laplacian matrix with its own connectivity. This result is presented in [7,8] for nonweighted and weighted graphs, respectively. The number of zero eigenvalues of $\mathcal{L}$ indicates how many disconnected parts exist in the graph. This means that for a connected graph, the second smallest eigenvalue of $\mathcal{L}$ (the Fiedler’s eigenvalue) is positive and this is called the algebraic connectivity of the graph. The introduction of this invariant as a constraint in an optimization problem is the main point of this work.

3. Discretization of the Maze and Problem Formulation

The idea of finding the shortest path using graph theory has been studied widely in the literature [1,2,22,23,24]. Most of the proposed methods have an heuristic nature. The novelty of this paper is the use of the spectral properties of the Laplacian matrix $\mathcal{L}$ of the graph associated to the maze to achieve the goal of finding the optimal route.

The idea has been implemented with good results within a mechanical [20] and electrode design [21] context.

The first step is the discretization of the maze, since the graph can be considered a discrete structure. The walls and the pathways are divided into square elements, as shown in Figure 2.

A maze is solved when there exists a path between the entrance (cyan color) and the exit (magenta color). For this simple case, the solution is shown in Figure 3 (left). The different squares that form this route can be considered as a connected graph as represented in Figure 3 (right).

The Laplacian matrix of this graph ($\mathcal{L}\in {\mathcal{M}}^{10\times 10}$) is computed with Equation (1). The squares are ordered alphabetically: the first row and column are related with the square A, the second pair with B, and so on, for all the nodes:

$$\mathcal{L}=\left(\begin{array}{ccccc}\hfill 1& \hfill -1& \hfill 0& \hfill \dots & \hfill 0\\ \hfill -1& \hfill 2& \hfill -1& \hfill \dots & \hfill 0\\ \hfill 0& \hfill -1& \hfill 2& \hfill \dots & \hfill 0\\ \hfill ⋮& \hfill ⋮& \hfill ⋮& \hfill \ddots & \hfill 0\\ \hfill 0& \hfill 0& \hfill 0& \hfill \dots & \hfill 1\end{array}\right).$$

The two first eigenvalues of $\mathcal{L}$ are ${\lambda }_1=0$ and ${\lambda }_2=0.1$, meaning that the graph is made up of a single joined element. All the weights $w_{ij}$ are set to 1. The example shown in Figure 2 and Figure 3 highlights that if the maze is understood as a graph, Fiedler’s eigenvalue of the solution is positive.

Once the solution is found, it can be interpreted as a connected graph whose Laplacian matrix has the second eigenvalue positive. The point here is how to obtain the path from all the possibilities when the maze is not solved. A new example is presented in Figure 4 discretized with a mesh of $11\times 11$ elements. The entrance and exit are cyan and magenta, respectively, and the adjacent squares to both of them are orange.

A new variable $\mathit{\phi }\in \{\mathbf{0},\mathbf{1}\}$ is assigned to each square, representing whether this node belongs to the path (${\phi }_i=1$) or not (${\phi }_i=0$). The nodes are numbered by columns (including the walls), from left to right, and then ${\phi }_2=1$ and ${\phi }_{120}=1$. Wall squares cannot be included in the solution path. Naming S the set of nodes fixed as walls, it implies ${\phi |}_S=0$.

In order to determine if two adjacent nodes belong to the path, the weight of the link between both of them can be defined as

$$w_{ij}={\phi }_i{\phi }_j,$$

an expression that measures connectivity between squares. The idea of the method is to determine the set of squares P that connects the entrance with the exit of the maze.

A trivial solution can be found by fixing the variable to ${\phi }_i=1$ in all the elements. The way to find the optimal path is through an optimization problem, where the amount of squares with ${\phi }_i=1$ is minimized (the shortest path), while ${\lambda }_2$ is positive (a unique connected path). The problem can be formulated as follows [20,21]:

$$\begin{array}{ccc}\hfill {\displaystyle \underset{\mathit{\phi }\in \{\mathbf{0},\mathbf{1}\}}{min}:}& {\mathbf{1}}^T\mathit{\phi }& \\ \hfill \mathrm{s}.t.:& \left\{\begin{array}{c}\begin{array}{cccc}\hfill (\mathcal{L}\left(\mathit{\phi }\right)-{\lambda }_k\mathbf{M}\left(\mathit{\phi }\right)){\mathbf{\Phi }}_k& =& \mathbf{0},k=1,\dots ,m\hfill & \left(\mathrm{auxiliary}\mathrm{eigenproblem}\right)\hfill \\ \hfill {\mathbf{\Phi }}_k^T\mathbf{M}\left(\mathit{\phi }\right){\mathbf{\Phi }}_k& =& 1\hfill & (\mathbf{M}-\mathrm{orthonormalization})\hfill \\ \hfill {\lambda }_2& >& 0\hfill & \left(\mathrm{connectivity}\mathrm{constraint}\right),\hfill \end{array}\hfill \end{array}\right.\end{array}$$

(2)

where ${\mathbf{1}}^T$ is a vector of ones and $\mathcal{L}$ and $\mathbf{M}$ stand, respectively, for the Laplacian matrix and global (lumped) mass matrix that stores in its diagonal the value of the design variable $\mathit{\phi }$. ${\lambda }_k$ and ${\mathbf{\Phi }}_k$ are the eigenvalues and the associated eigenvectors, respectively, of the eigenproblem proposed: $(\mathcal{L}\left(\mathit{\phi }\right)-{\lambda }_k\mathbf{M}\left(\mathit{\phi }\right)){\mathbf{\Phi }}_k=\mathbf{0}$. The number of eigenvalues computed, m, needs to be large enough due to the algebraic multiplicity of the second eigenvalue. It is important to remark that for this example, the $\mathcal{L}$ and $\mathbf{M}\in {\mathcal{M}}^{121\times 121}$. This is because both matrices include all the elements in which the maze has been discretized, including the walls, unlike the previous case.

The initial optimization problem is formulated in terms of the integer variable $\mathit{\phi }$. With the aim of writing Equation (2) within the framework of the topology optimization method [25], $\mathit{\phi }\in \{\mathbf{0},\mathbf{1}\}$ is relaxed into the density variable $\mathit{\rho }\in [\mathbf{0},\mathbf{1}]$. The conic filter [26,27,28] with the Heaviside projection [29,30] is used to avoid the appearance of gray areas, resulting in the next formulation of the problem:

$$\begin{array}{ccc}\hfill {\displaystyle \underset{\mathit{\rho }\in [\mathbf{0},\mathbf{1}]}{min}:}& {\mathbf{1}}^T\overline{\mathit{\rho }}& \\ \hfill \mathrm{s}.t.:& \left\{\begin{array}{c}\begin{array}{cccc}\hfill (\mathcal{L}\left(\overline{\mathit{\rho }}\right)-{\lambda }_k\mathbf{M}\left(\overline{\mathit{\rho }}\right)){\mathbf{\Phi }}_k& =& \mathbf{0},k=1,\dots ,m\hfill & \left(\mathrm{auxiliary}\mathrm{eigenproblem}\right)\hfill \\ \hfill {\mathbf{\Phi }}_k^T\mathbf{M}\left(\overline{\mathit{\rho }}\right){\mathbf{\Phi }}_k& =& 1\hfill & (\mathbf{M}-\mathrm{orthonormalization})\hfill \\ \hfill {\lambda }_2& >& 0\hfill & \left(\mathrm{connectivity}\mathrm{constraint}\right),\hfill \end{array}\hfill \end{array}\right.\end{array}$$

(3)

where the projected density $\overline{\mathit{\rho }}$ is computed as follows:

$${\overline{\rho }}_e={\displaystyle \frac{tanh\left(\beta \eta \right)+tanh\left(\beta ({\tilde{\rho }}_e-\eta )\right)}{tanh\left(\beta \eta \right)+tanh\left(\beta \right(1-\eta )}},$$

where the parameters $\beta$ and $\eta$ define the sharpness and the threshold of the projection. The filtered density $\tilde{\mathit{\rho }}$ is obtained from the initial variable $\mathit{\rho }$:

$${\tilde{\rho }}_e={\displaystyle \frac{{\displaystyle \sum _i^{n_e}{d}_e\left({\mathbf{x}}_i\right){\rho }_i}}{{\displaystyle \sum _i^{n_e}{d}_e\left({\mathbf{x}}_i\right)}}}.$$

The weighting function d is given by the cone-shape function:

$$d_e\left({\mathbf{x}}_i\right)=max\{R_f-\parallel {\mathbf{x}}_i-{\mathbf{x}}_e\parallel ,0\},$$

where $R_f$ is the filter radius and ${\mathbf{x}}_i$ is the centroid of each finite element. The filtered density $\tilde{\mathit{\rho }}$ takes the value of the weighted average of $\mathit{\rho }$ in the neighborhood defined by the filter radius. The Figure 5 shows a representation of the density filter, in such a way that only the elements whose centroid are within the circle of radius $R_f$ are considered.

The filtering technique together with the projection approach ensure mesh independence [25] and 0-1 designs [29]. During the optimization process, intermediate densities may appear. The next interpolation scheme is used for computing the weights of the Laplacian matrix:

$$w_{ij}={\left({\rho }_i{\rho }_j\right)}^p+w_{min},$$

where p is the penalization exponent and $w_{min}$ is the minimum value of the weight, imposed to avoid singularities. Note that the difference with Equation (3) is the use of the power law. When the variable only takes two values, the weight clearly indicates if both nodes are linked or not. This connection is not clear for intermediate densities, and then, with a value of $p=6$, only squares with $\mathit{\rho }$ close to 1 are considered to be connected.

The optimization problem is solved by using the method of moving asymptotes (MMA) [31]. This algorithm needs the objective function values and the constraints, and the derivatives of both of them. The differentiation of the problem is straightforward, and it has not been included here for the sake of brevity. The interested reader is referred to [32,33].

A summary of the process is shown in

Table 1. Algorithm and computational implementation.

.

4. Examples of Mazes

This section is devoted to the resolution of several mazes with different meshes and configurations.

4.1. Coarse Mesh with Single Solution

For the first example, a maze with only one solution is generated with [34]. The maze is discretized with a regular mesh of $21\times 21$ square elements as shown in Figure 6. The cyan and magenta lines represent the entrance and the exit, respectively, whose squares are painted in orange. They are introduced in the problem as passive areas with ${\rho }_i=1$.

The parameters of the filter and the projection are set to $R_f=1.1$ elements, $\eta =0.5$ and $\beta =2$ at the beginning of the iterative process (it doubles its value each 50 iterations up to ${\beta }_{max}=16$). The maximum number of iterations is 1000. The minimum weight of the connections of the graph is $w_{min}={10}^{-5}$. The walls are introduced in the optimization problem as passive areas with ${\rho }_i=0$. This means that a path cannot go through the wall, because the squares cannot be connected. For this first maze, the solution is presented in Figure 7.

This maze has only one path that connects, in an efficient way, the entrance and the exit, and this is the solution obtained. The second eigenvalue of the problem is close to 0, but positive: ${\lambda }_2=0.05$. The value of the objective function is not interesting in this problem, but it can be computed as the number of orange squares.

The evolution of the objective function is shown in Figure 8.

4.2. Fine Mesh with Single Solution

The same maze is proposed for the second example. In this case, the domain is discretized with a mesh of 105 × 105 square elements. The main difference with the previous example is that the width of every path and wall is more than one element, as shown in Figure 9.

Only the filter radius changes for this example, which is set to $R_f=5.6$ elements, the rest of the parameters remain constants. The solution for this case study is depicted in Figure 10, where the color orange symbolizes the optimal path.

It is interesting to remark that, in this case, the path is narrower than the corridors. Every time the solution turns a corner, it takes the inside part of the turn, since the length of the path is being minimized. This parameter, the width of the optimal route, can be partially controlled with the conic filter and the projection. For a total control of the minimum length scale, the robust approach presented in [30] can be implemented.

4.3. Fine Mesh with Various Solutions

The previous examples show the solution of a maze when only one path can connect the entrance with the exit. For the following example, a maze with more than one solution is proposed. In Figure 11 (left) is presented the new example, and two possible solutions are painted with the orange line in Figure 11 (right). It is important to remark that when moving in a straight line, both paths have the same length. It is easy to find more solutions with a longer connection.

Keeping all parameters constant, including the mesh, the optimal solution is plotted with orange in Figure 12.

Even when both paths seem to have the same length, the one that has more corners is shorter. The optimal path obtained has 14 corners, while the other shown in Figure 11 (right) has only 10. This is due to the objective function, that minimizes the number of orange squares that link the entrance with the exit. Just as happened in the other examples, the second eigenvalue of the problem is positive.

4.4. Forcing the Path

In this case study, the same maze is solved again, but forcing the solution through a new point. The new conditions for the maze are shown in Figure 13 (left), where the optimal path is forced to pass through a point that was not included in the shortest path. The solution is represented in Figure 13 (right).

4.5. Three-Dimensional Maze with Single Solution

For this example, we have created a 3D maze by using a hypermatrix. The maze is discretized with a regular mesh of $14\times 14\times 14$ elements, as shown in Figure 14 (left). The cyan and magenta squares denote the entrance and the exit, respectively. This maze has a single path that efficiently connects the entrance and exit, and this is the obtained solution. The optimal solution is plotted in orange in Figure 14 (right).

5. Conclusions

In this work, the resolution of a maze is proposed from a mathematical point of view that involves the use of spectral graph theory. The strategy used consists of studying the connectivity between the entrance and the exit. The second eigenvalue of the Laplacian matrix of the graph is imposed to be positive, while the length of the path is minimized. Several examples with different meshes thoroughly corroborates the results. Furthermore, this method also allows for an optimal solution (the shortest way) to be found, even when multiple paths linking the entrance with the exit are present. An extension of the approach is also presented, where the optimal path is forced to pass through one point.

The results are shown qualitatively since the value of the objective function is not representative of the optimal path. Regarding the constraint, it is enough that the second eigenvalue is positive. This work can be extended to labyrinths, a particular case of a maze, without loss of generality.

The objective function has been defined as the sum of the design variables, but it can be adapted to problems of different nature. The increase in computing time is justified by the flexibility of the algorithm. With this approach, the connectivity of the graph and the objective function are completely independent, allowing to model problems of different nature. In addition, this approach may include as design parameter the width of the path, which can be useful to design trajectories. The approach is focused in the two-dimensional and three-dimensional cases.