Solving mazes with memristors: A massively parallel approach

Solving mazes is not just a fun pastime: They are prototype models in several areas of science and technology. However, when maze complexity increases, their solution becomes cumbersome and very time consuming. Here, we show that a network of memristors—resistors with memory—can solve such a nontrivial problem quite easily. In particular, maze solving by the network of memristors occurs in a massively parallel fashion since all memristors in the network participate simultaneously in the calculation. The result of the calculation is then recorded into the memristors’ states and can be used and/or recovered at a later time. Furthermore, the network of memristors finds all possible solutions in multiple-solution mazes and sorts out the solution paths according to their length. Our results demonstrate not only the application of memristive networks to the field of massively parallel computing, but also an algorithm to solve mazes, which could find applications in different fields.

Figure 1

Maze mapping into a network of memristors (the memristive processor). (Right panel) The maze is covered by an array of vertical and horizontal lines having the periodicity of the maze. (Left panel) Architecture of the network of memristors in which each crossing between vertical and horizontal lines in the array (in the right panel) is represented by a grid point to which several basic units consisting of memristors and switches (field-effect transistors) are attached. The maze topology is encoded into the state of the switches such that, if the short line segment connecting neighboring crossing points in the array crosses the maze wall, then the state of the corresponding switch is not connected [shown with red (dark gray) symbols]. All other switches are in the connected state. The external voltage ($V$) is applied across the connection points corresponding to the entrance ($V$) and exit [ground (GND)] points of the maze.

Figure 2

(a) Initialization of the network of memristors can be performed by a simultaneous application of GND and appropriately selected $V_1$ voltages in a chessboardlike pattern to all grid points for a sufficiently long period of time to securely switch memristors to the OFF state. Note that, since the memristors’ polarities are alternated in the network, the corresponding voltage polarities are also alternated. During the initialization, all switches should be in the connected state or should already encode the maze (as shown on the plot). (b) In order to read a memristor’s state, such a memristor (shown in the center) can be disconnected from the rest of the circuit setting the corresponding switches to the not-connected state [shown with red (dark gray) symbols] and its own switch to the connected state and can be tested by the application of a short small-amplitude voltage pulse (or double bipolar voltage pulse to minimize the disturbance of the memristor’s state) of an amplitude $V_2$.

Figure 3

Solution of a single-path maze. (a) Network state at $t=0.075\mathrm{s}$. The chain of memristors in the low-memristance state [shown by red (dark gray) dots connected by a red (dark gray) line] clearly connects the entrance and exit points of the maze [note that memristors in the OFF state—when $R_{ij}^M(t=0)>90\Omega$—are not shown]. Here, every other memristor along the solution path is in the low-memristance state. (b) Network state at $t=0.12\mathrm{s}$. Note that, at $t=0.1\mathrm{s}$, the sign of the applied voltage has been changed. At $t=0.12\mathrm{s}$, each memristor along the solution path shows the maze solution. The resistance is in ohms, the voltage is in volts, and the current is in amperes.

Figure 4

Solution of a multiple-path maze. Network state at $t=0.047\mathrm{s}$. The maze solution contains two common segments [red (dark gray) dots connected by a red (dark gray) line], and two alternative segments of different lengths close to the left bottom corner. The memristance in the shorter segment [blue (very dark gray) dots connected by a red (dark gray) line] is smaller than that in the longer segment [green (light gray) dots connected by a red (dark gray) line] since the current through the shorter segment is larger and, consequently, the change in the memristors’ state along this segment is larger. The arrow at the bottom indicates where a modification of the maze from Fig. 3 has been made (position of the removed segment of the wall). The resistance is in ohms, the voltage is in volts, and the current is in amperes.