Operators for the signs of
Abstract
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.
Keywords
- memristive grids
- symbolic memristor modeling
- maze-solving
- analog processors
1. Introduction
For thousands of years, mazes have intrigued the human mind [1]. 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 [10], and Trémaux’s algorithm [11]. 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 [14] 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 [15]. 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 [16].
The second milestone occurred in 2008, when a team at Hewlett-Packard Laboratories fabricated a device whose behavior exhibited the memristance phenomenon [17]. 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 [23].
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
Figure 2 shows the resulting window plots for various values of
where
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 [17]:
where
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
As a result, the sign of the charge as well as the direction of the drift (
As a matter of an example, the expression of
After substituting Eq. (5) in Eq. (4), it results in the memristance expression:
where the variable
For order-2 and
Again, after substituting the expression above in Eq. (4) and after some reductions, it is possible to obtain the memristance for order-2 and
In a similar way, an expression for the memristance for order-3 and
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
In a similar way, the memristance for order-2 and
Eqs. (6), (9)–(12) are indeed the analytical expressions that constitute memristor models. References [29, 30] contain a proper characterization of the resulting models.
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 (
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
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 [30].
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
If the control input is
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.
Order | ||||||
5 | 1 |
CMOS TG | ||
PMOS | 1.44 | 0.18 |
NMOS | 0.48 | 0.18 |
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
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
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
Consequently, the fuses that first reach the highest
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 5 × 5 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
As time lapses, at
On the other hand, Figure 14a shows
Within this time-window, two snapshots of the output display have been taken at
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
5.1.2 The 10 × 10 and 15 × 15 mazes
The memristive grid has also been applied to single-solution mazes that have larger sizes. The first maze is of
The second case is a
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 5 × 5 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
It can be observed that all paths start from
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
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
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
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
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.
7. Conclusions
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.
References
- 1.
Kern H, Saward J, Schons M, Clay AH, Thomson SB, Velder KA. Through the Labyrinth: Designs and Meanings Over 5,000 Years. Art and Design Series. New York: Prestel Publishing; 2000 - 2.
Barnes CA. Memory deficits associated with senescence: A neurophysiological and behavioral study in the rat. Journal of Comparative and Physiological Psychology. 1979; 93 (1):74 - 3.
Olton DS, Samuelson RJ. Remembrance of places passed: Spatial memory in rats. Journal of Experimental Psychology: Animal Behavior Processes. 1976; 2 (2):97 - 4.
Morris R. Developments of a water-maze procedure for studying spatial learning in the rat. Journal of Neuroscience Methods. 1984; 11 (1):47-60 - 5.
Dracopoulos DC. Robot path planning for maze navigation. In: The 1998 IEEE International Joint Conference on Neural Networks Proceedings, IEEE World Congress on Computational Intelligence; Vol. 3. IEEE; 1998. pp. 2081-2085 - 6.
Lumelsky VJ. A comparative study on the path length performance of maze-searching and robot motion planning algorithms. IEEE Transactions on Robotics and Automation. 1991; 7 (1):57-66 - 7.
Werbos PJ, Pang X. Generalized maze navigation: SRN critics solve what feedforward or Hebbian nets cannot. In: IEEE International Conference on Systems, Man, and Cybernetics; Vol. 3. IEEE; 1996. pp. 1764-1769 - 8.
Milková E, Slaby A. Graph algorithms in mutual contexts. In: 7th WSEAS International Conference Proceedings on Mathematics and Computers in Science and Engineering; Vol. 1. World Scientific and Engineering Academy and Society; 2008. pp. 721-726 - 9.
Bondy JA, Murty USR. Graph Theory with Applications. Vol. 290. London: Macmillan; 1976 - 10.
Abelson H, DiSessa AA. Turtle Geometry: The Computer as a Medium for Exploring Mathematics. Cambridge, Massachusetts: MIT Press; 1986 - 11.
Müller H. A one-symbol printing automaton escaping from every labyrinth. Computing. 1977; 19 (2):95-110 - 12.
Vourkas I, Stathis D, Sirakoulis G. Massively parallel analog computing: Ariadnes thread was made of memristors. IEEE Transactions on Emerging Topics in Computing. 2015; 6 (1):145-155 - 13.
Ye Z,Wu SHM, Prodromakis T. Computing shortest paths in 2D and 3D memristive networks. In: Adamatzky A, Chua LO. Memristor Networks. Basel, Switzerland: Springer; 2014. pp. 537-552 - 14.
Pershin YV, Di Ventra M. Solving mazes with memristors: A massively parallel approach. Physical Review E. 2011; 84 (4):046703 - 15.
Chua L. Memristor—The missing circuit element. IEEE Transactions on Circuit Theory. 1971; 18 (5):507-519 - 16.
Chua LO, Kang S-M. Memristive devices and systems. Proceedings of the IEEE. 1976; 64 (2):209-223 - 17.
Strukov DB, Snider GS, Stewart DR, Williams RS. The missing memristor found. Nature. 2008; 453 (7191):80-83 - 18.
Indiveri G, Linares-Barranco B, Legenstein R, Deligeorgis G, Prodromakis T. Integration of nanoscale memristor synapses in neuromorphic computing architectures. Nanotechnology. 2013; 24 (38):384010 - 19.
Vittoz EA. Future of analog in the VLSI environment. In: IEEE International Symposium on Circuits and Systems. IEEE; 1990. pp. 1372-1375 - 20.
Chua L. Memristor, Hodgkin-Huxley, and edge of chaos. In: Adamatzky A, Chua LO. Memristor Networks. Basel, Switzerland: Springer; 2014. pp. 67-94 - 21.
Jo SH, Chang T, Ebong I, Bhadviya BB, Mazumder P, Lu W. Nanoscale memristor device as synapse in neuromorphic systems. Nano Letters. 2010; 10 (4):1297-1301 - 22.
Naous R, Al-Shedivat M, Salama KN. Stochasticity modeling in memristors. IEEE Transactions on Nanotechnology. 2016; 15 (1):15-28 - 23.
Pershin YV, Di Ventra M. Memcomputing: A computing paradigm to store and process information on the same physical platform. In: 2014 International Workshop on Computational Electronics (IWCE). IEEE; 2014. pp. 1-2 - 24.
Sarmiento-Reyes A, Hernández-Martínez L, Vázquez-Leal H, Hernández-Mejía C, Diaz Arango GU. A fully symbolic homotopy-based memristor model for applications to circuit simulation. Analog Integrated Circuits and Signal Processing. 2015; 85 (1):65-80 - 25.
He J-H. Homotopy perturbation technique. Computer Methods in Applied Mechanics and Engineering. 1999; 178 (3):257-262 - 26.
Vazquez-Leal H. Generalized homotopy method for solving nonlinear differential equations. Computational and Applied Mathematics. 2014; 33 (1):275-288 - 27.
He J-H. Comparison of homotopy perturbation method and homotopy analysis method. Applied Mathematics and Computation. 2004; 156 (2):527-539 - 28.
Joglekar YN, Wolf SJ. The elusive memristor: Properties of basic electrical circuits. European Journal of Physics. 2009; 30 (4):661 - 29.
Sarmiento-Reyes A, Velásquez YR. Chapter 5: Charge-controlled memristor grid for edge detection. In: Ciufudean C, editor. Advances in Memristor Neural Networks. London, United Kingdom: InTechOpen; 2018. pp. 91-113 - 30.
Velásquez YAR. Development of an analytical model for a charge-controlled memristor and its applications [Master’s thesis]. Puebla, Mexico: National Institute for Astrophysics, Optics and Electronics (INAOE); 2017 - 31.
Recski A. Matroid Theory and Its Applications. Berlin, Germany: Spring-Verlag; 1989 - 32.
Hodges DA, Jackson HG. Analysis and Design of Digital Integrated Circuits. Boston, USA: McGraw-Hill; 1988