Operators for the signs of and .
Memcomputing represents a novel form of neuro-oriented signal processing that uses the memristor as a key element. In this chapter, a memristive grid is developed in order to achieve the specific task of solving mazes. This is done by resorting to the dynamic behavior of the memristance in order to find the shortest path that determines trajectory from entrance to exit. The structure of the maze is mapped onto the memristive grid, which is formed by memristors that are defined by fully analytical charge-controlled functions. The dependance on the electric charge permits to analyze the variation of the branch memristance of the grid as a function of time. As a result of the dynamic behavior of the developed memristor model, the shortest path is formed by those memristive branches exhibiting the fastest memristance change. Special attention is given to achieve a realistic implementation of the fuses of the grid, which are formed by an anti-series connection of memristors and CMOS circuitry. HSPICE is used in combination with MATLAB to establish the simulation flow of the memristive grid. Besides, the memristor model is recast in VERILOG-A, a high-level hardware description language for analog circuits.
- memristive grids
- symbolic memristor modeling
- analog processors
For thousands of years, mazes have intrigued the human mind . The labyrinths have been used in research with laboratory animals, in order to study their ability to recognize their environment [2, 3, 4]. In the 1990s, artificial intelligence of robots was studied by examining their ability to traverse unfamiliar mazes [5, 6, 7]. Maze exploration algorithms are closely related to graph theory and have been used in both mathematics and computer science [8, 9].
There are several algorithms for maze solving in the literature, they can be classified in two very well-defined groups: the algorithms used by a traveler in the maze without knowledge of a general view of the maze, and the algorithms used for a program that can have a whole view the whole maze. Some examples of the first ones are the wall follower, random mouse, pledge algorithm , and Trémaux’s algorithm . In the second group, shortest path algorithms are most useful, because they can find the solution not only for a simple connected maze, but also for multiple-solution mazes.
In this chapter, we put a main idea into practice, namely that the topology of a maze can be mapped onto a memristive grid. By exploiting the analog computations performed by solving Kirchoft’s Current Laws (KCL) in a parallel manner, memristive grids have demonstrated their ability for computing shortest paths in a given maze, levering on the dynamic adjustment of their intrinsic memristance [12, 13].
The parallel solution of KCL introduces a resemblance of the memristive grid as an analog processor  in counterposition to a digital approach in which the processing can also be done in parallel way, but the overhead in additional conversion circuitry is too high.
Two important milestones appear in the history of the memristor. The first one in 1971 when professor Leon O. Chua introduced the memristor as the fourth basic circuit element in his seminal paper . It established that the memristor completes the number of possible relationships between the four fundamental circuit variables: current, voltage, magnetic flux, and electric charge—as depicted in Figure 1. Later, an extension to memristive systems was published in .
The second milestone occurred in 2008, when a team at Hewlett-Packard Laboratories fabricated a device whose behavior exhibited the memristance phenomenon . Since the advent of the memristor as an actual device, research and technological development in several areas related to memristive applications have been increased.
In the field of signal processing, the memristor has special preponderance in neuro-computing and artificial neural networks because it allows new architectures and processing paradigms with important features based on biological neuronal systems [18, 19, 20, 21, 22]. In summary, a novel form of neuro-computing is on scene, namely memcomputing .
Memristive grids represent a family of neuro-computing systems that are able of achieving in a very flexible way several tasks for analog applications. In the next paragraphs, we present a specially tailored memristive grid that is focused on solving mazes.
The rest of the manuscript is organized as follows: in Section 2, the developed models are recast in a set of fully analytical expressions for the memristance, which are given as charge-controlled functions that are further used in this application. The components of the memristive grid are introduced in Section 3. The maze-solving procedure is introduced in Section 4 by explaining the simulation flow of the memristive grid. Subsequently, several mazes are solved in order to illustrate the operation of the memristive grid in Section 6. Finally, a series of conclusions is drawn.
2. Development of a charge-controlled memristor model
In this section, a charge-controlled memristor model is introduced. The model has been developed by solving the ordinary differential equation (ODE) that describes the nonlinear drift mechanism, with a homotopy perturbation method that yields an analytical expression for the memristance [24, 25, 26, 27].
In order to obtain a charge-dependent memristance model, the nonlinear drift differential equation is expressed in terms of the electric charge:
where defines the direction of the drift and it can be . Besides, is the window function used to define the nonlinear and bounded behavior of the state variable , and it is given as :
Figure 2 shows the resulting window plots for various values of . In addition, is given as:
where , , and are the mobility, the ON-state resistance, and the dimension of the device.
The main goal is to obtain a solution to Eq. (1) in the form of an analytical expression x(q). Once, this is done, this solution is substituted into the coupled resistor equivalent of Figure 3 which is expressed as :
where is the total memristance. Besides, and are the on-state and the off-state resistances respectively.
In order to obtain an analytical solution to Eq. (1), we resort to the methodology reported in [24, 29], which is based on the homotopy perturbation method (HPM). HPM finds for a given order of the homotopy method as well as the integer value of exponent of the window function (). Furthermore, it should be also pointed out that the charge may be positive or negative.
As a result, the sign of the charge as well as the direction of the drift () allows us to introduce two operators that are used to simplify the final expressions for the solution. These operators are denoted as and . Table 1 shows how they are defined depending on the signs of the charge and .
As a matter of an example, the expression of for order-1 with is given as:
where the variable is given as:
For order-2 and , the solution to Eq. (1) is given as:
Again, after substituting the expression above in Eq. (4) and after some reductions, it is possible to obtain the memristance for order-2 and as:
In a similar way, an expression for the memristance for order-3 and can be obtained:
It can be noticed that HPM produces nested expressions of the memristance, that is to say, a given memristance of a given order is expressed as function of the memristance of lower orders.
For order-1 and , the memristance is given as follows:
In a similar way, the memristance for order-2 and is given:
3. Implementing the memristive grid
A memristive grid is a rectangular array of memristive branches, as shown in Figure 4. Herein, the memristive branches have been denoted as
The switch is used to define the structure of the labyrinth, if the switch is in the ON-state, then the way is free, while if the switch is in the OFF-state then a wall is encountered. Figure 5 shows the equivalent of the memristive fuse.
In order to illustrate the use of the memristive grid in describing a maze, the maze of Figure 6a is used. The entrance of the maze is marked by the green arrow and the output is marked by a red arrow, and the walls are shown in red. The maze is mapped onto the memristive grid as shown in Figure 6b by denoting the entrance of the maze as a voltage source, while the output of the maze is given by the ground node. For sake of clarity, both figures are merged into Figure 6c, where the blocked paths are represented by memristive fuses in red, on the contrary, the paths that can be followed are represented by memristive fuses in white. It clearly results that the walls should be given by memristive fuses with the switch in the OFF-state (high-resistance), while the open paths are constituted by memristive fuses with the switch in the ON-state (low-resistance).
On the top of this, the memristive grid can be straightforwardly adapted to other kinds of mazes. Mazes with multiple entrances are represented with multiple input voltages. Similarly, mazes with multiple outputs are given by setting multiple instances of the ground node.
3.1 An algorithmic view
A close look of the solution path in Figure 6a can lead us to a graph-theoretical explanation on how the memristive grid solves the maze, because the open ways in the maze can be regarded as an unweighted graph where the solution path is subgraph. The solution path can be found by using a
The application of BFS is illustrated by determining the shortest path between nodes 3 and 6 of the graph from Figure 7a. Here, node 3 can be regarded as the input () and node 6 as the output (). The algorithm starts by selecting the initial node (3). From this, a first level of coloring is achieved by selecting the neighboring nodes (2, 4, 5). This procedure is repeated until all nodes have been visited. For this graph, it suffices with 2 levels. The shortest path is defined by the sequence 356, which is shown in red in Figure 7b.
As a result, by representing the graph with the memristive grid, it allows us to define ways for the current to flow through the open paths by gradually changing the equivalent memristance of the fuse. Besides, what is more relevant, since the current is given as the time-derivative of the charge, then the solution of the maze is always given by the shortest path to ground which represents the path with the fastest changing memristance.
3.2 Technical specifications of the memristive fuse
The memristive fuse from Figure 5 contains a pair of memristors in anti-series connection. Such a memristor connection produces an -characteristic that is composed of the overlapping of the -curves of the memristor expressions for and . Figure 8a shows the -characteristics for the model of order-1, and Figure 8b shows the schematic curve with the values of and . Physical parameters of the memristor model are given by the nominal values of the HP memristor. A summary of the specs for the memristor model is given in Table 2.
It clearly results that the overall performance of the grid in solving mazes is based on the model of the memristors that form the fuses. Even though the models are recast in fully symbolic form—which represent a great advantage, numeric values should be assigned to the parameters of the model, as given in Table 2. Since variations of the model parameters may appear, it is important to notice that the anti-series connection alleviates the possible effects of those variations. Specific sensitivity analysis on the parameter variations of the charge-controlled models are given in .
3.2.1 Switch implementation
In the memristive fuse, an ideal switch can be used in the process of finding the solution, however, with the aim to have a more realistic switch, a transmission gate is used instead. The transmission gate is a switch in CMOS technology, it consists of an NMOS transistor and a PMOS transistor connected in parallel, as in Figure 9a. Both devices in combination can fully transmit any signal value between (the supply voltage of the transistors) and ground. In order to switch, each transistor requires a complementary control input. Therefore, it is necessary to add an inverter connected between the control input and the PMOS gate [30, 32].
If the control input is then the switch is closed, and as a result, the transmission gate can pass the input signal to output because it exhibits a low-resistance. On the contrary, if the control input is grounded, then the switch is opened and the transmission gate presents a high-resistance.
In order to simulate the transmission gate of the memristive fuse, a CMOS 180 nm technology is used. The parameters of the two complementary transistors are shown in Table 3. The equivalent resistance of the transmission gate both states as a function of the input voltage is shown in Figure 10.
The resistance values are extracted making a sweep of the input voltage and measure the equivalent average resistance of the transistors in the ON-state (switch closed, Figure 10a) and OFF-state (switch opened, Figure 10b). Table 4 shows the selected values for and .
In addition, it can be noticed that the initial value of the ON-state resistance is given as:
As a result of the specifications above, a couple of parameters are of special interest, namely, the initial resistance and the maximum resistance of the memristive fuses. At the start, the fuses present an initial resistance which is given as the sum of the initial resistance of the memristors in the anti-series connection plus initial resistance of the ON-state of the transmission gate:
which is 3.266 k.
Moreover, the maximum resistance of the fuse is given as:
It is worthy to notice that the maximum fuse resistance does not contain of both memristor, but of one memristor and of the other memristor due to the anti-series connection.
4. Simulation flow
Since the solution path for a given maze is obtained by determining the path where the fastest change in resistance occurs, the core of the solution process involves a transient analysis. We have chosen to achieve the electrical simulation of the memristive grid by using HSPICE. Both memristors of the fuse are defined as nonlinear resistors in the input netlist.
The simulation flow is shown in Figure 11 and is described as follows:
During the transient simulation, the equivalent resistance of the fuses is obtained at every instant . It clearly results that is obtained by calculating the difference between the measured resistance and the minimum resistance from Eq. (14):
Consequently, the fuses that first reach the highest define indeed the solution path of the maze. In mazes with multiple solutions, fuses that belong to the shortest path reach high values of more fastly. As time lapses, other solution paths are revealed reaching high values of . For a given time, all fuses within the solution paths reach the maximum , which is given by
5. Mazes under-test
In order to prove the behavior of the memristive grid in maze solving, this section presents several cases that have been ordered as follows:
Mazes with a single solution
Mazes with multiple solutions
Maze with two inputs and two outputs
An octogonal maze with three inputs and a single output
A 3D maze
5.1 Single-solution mazes
The first set to be solved consists of three mazes with a single-entrance and single-output and the solution is given by a unique path.
5.1.1 The maze
The first maze, from Figure 12a, is treated in full with the aim of highlighting the details of the solution procedure. The first stage of the procedure yields the memristive grid associated to the mapping of the maze, which is shown in Figure 12b. The resulting netlist of the memristive grid is then simulated in a transient analysis with HSPICE.
It can be noticed that there are 24 memristive fuses in the open paths of the maze. The electrical simulation is applied in order to measure the instantaneous resistance of the fuses. On the one hand, Figure 13a shows the transient behavior of the resistance of those fuses for the first s. It can be noticed that all fuses start with the same resistance at , namely . As a result, at , for all fuses and the maze is not walked yet and the output display shows the open paths in white color, as shown in Figure 13b.
As time lapses, at s, only the fuses belonging to the solution path exhibit significant changes in their resistance. Here, the blue lines correspond to fuses outside the solution path, while the red lines correspond to fuses that belong to solution path. These changes are represented in the output display of Figure 13c for the same time in yellow. The solution path can already be distinguished.
On the other hand, Figure 14a shows of the memristive fuses for s. The red lines show that the fuses belonging to the solution path reached a maximum, while the blue lines remain in low levels of resistance, i.e., they belong to paths that finish in dead-ends.
Within this time-window, two snapshots of the output display have been taken at s and s—as depicted in the plots of Figure 14b and c, respectively. In the first display, the solution path is already highlighted in red with fuses having a value of . At s, the fuses of the solution path show .
In summary, it can be concluded that the memristive grid achieves the solution of the maze in a parallel processing by calculating the resistance of the fuses simultaneously. The progress of the solution procedure can be regarded as tracking the dynamic behavior of , which directly points out the solution path of the maze. On top of this, the output display allows us to visualize this procedure with the help of a color scale.
5.2 Multiple solutions mazes
The second set to be solved consists of three mazes that have solutions with multiple paths.
5.2.1 The maze with multiple solutions
This maze is shown in Figure 17. It is a very simple example that is explained to some extent in order to illustrate the procedure for finding the paths that constitute the solutions.
After carrying out the transient simulation, the resistance of the memristive fuses is obtained. Figure 18a shows for s. Herein, the attention is focused only on the resistance of the fuses belonging to the solution paths. Furthermore, the red lines show a steepest behavior which is a result that the red lines are associated to the fuses belonging to the solution with the shortest path. Besides, the blue lines are associated to fuses for the second solution path.
It can be observed that all paths start from when , i.e., the maze has not yet been walked—as given in the display of Figure 18b. After 0.2204 s, both solutions paths are already distinguishable, but the shortest path exhibits higher , which denoted by the darkest yellow tones in Figure 18c. After a while, at , the solution given by the shortest path is perfectly differentiable from the other solution, which can be compared by using the color bar.
After a larger sweep of time, the resistances of the fuses for both solutions have coalesced into an asymptotic level, which is the maximum value of the resistance at s—as shown in Figure 19.
5.2.2 Other mazes with multiple solutions
In this paragraph, two case studies are presented. The first one is the maze shown in Figure 20a, which is a maze that has a single entrance and a single exit, but there are four possible solution paths.
A snapshot at 1.901 s has been taken—see Figure 20b. The four solution paths are visible in different colors. The shortest path is shown in red exhibiting the highest at the time of evaluation. On the opposite, the solution with the longest path is given in pale yellow. This example shows the usefulness of the color palette of the output display on its full extent, because all possible solution paths are visible and it gives more insight on the progress of the solution procedure. After a long time, all the solutions reach the same resistance value as shown in Figure 20c.
The second example of this paragraph is a maze with two entrances and two exits that is shown in Figure 21a. We show in Figure 21b a snapshot taken at 1.0276 s. At this point, the memristive grid has been able to find both shortest paths for the solutions between the entrances and the outputs. After a while, at s, the output display shows the connection between both paths—as given in Figure 21c.
5.3 Octogonal maze
A nonrectangular maze is given in Figure 22a, which is an octogonal concentric maze with three entrances and with the output goal in the center of the maze. The three entrances are denoted as
5.4 A 3D maze
In order to illustrate that the memristive grid is able to deal with a three-dimensional maze, a three-layer maze is solved. For sake of readiness, Figure 23 shows the maze in separated levels in a puzzle-fashion. The ball on the top-layer indicates the starting point of the maze, while the ball in the low-layer points out to the output of the maze. The layers communicate each other with holes that are depicted as circles on the floor and disks on the roof of them.
The memristive grid that describes this maze counts 16 nodes per layer which yields a total of 48 nodes. Every layer possesses 24 branches (the external walls do not count) plus four inter-layer branches, i.e., 78 memristive fuses to describe the maze.
Finally, the output display given in Figure 24 shows the progress of the solution procedure.
6. Code for the model
In the following, the code for the memristor model as used within HSPICE is given.
A specially tailored memristive grid has been used as an analog processor for solving mazes. The memristives branches of the grid (fuses) are formed by an anti-series connection of two memristors and a switch. On one side, we have introduced a family of symbolic models for the memristor that are defined by charge-controlled functions. The fact that the models are charge-controlled allows us to monitor the velocity of the variation of the equivalent memristance of the fuses by carrying out a transient analysis with HSPICE. It is worth to mention that the model has been recast in VERILOG-A. On the other side, with the aim of producing a more realistic scenario, the switches are implemented by a transmission gate in CMOS technology. In this form, the resulting grid is in fact a hybrid CMOS-Memristor circuit.
The simulation flow-work is formed by an input stage developed in MATLAB, the electric simulation in HSPICE and the output stage again in MATLAB. The input stage is responsible for mapping the structure of the maze onto the memristive grid. The outcome of this stage is an input file with the netlist of the grid. The intermediate stage executes the transient simulation. The output stage is used to display the variation of the resistance of the fuses and it literally draws the solution path of the maze. The solution is found by sensing the variations of the resistance of the fuses that belong to the path, which implies that the memristive grid achieves the shortest path algorithm.
Finally, the maze grid has proven its reliability in solving mazes with different levels of complexity. A series of examples has been analyzed: single-solution mazes, multiple-solution mazes, and a 3D maze.