PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving mazes with memristors: a massively-parallel approach

Yuriy V. Pershin, Massimiliano Di Ventra

arXiv:1103.0021v2cond-mat.mes-hallcs.ETphysics.comp-ph

TL;DR

Maze-solving methods can become slow as maze complexity and local connectivity increase. This paper uses a memristor network to solve mazes through parallel state changes, with simulations showing that multiple paths can be identified and ordered by length. The authors conclude that the approach solves mazes in a massively parallel way, while noting that their demonstrated switching time is much longer than that of nanoscale devices.

  • Problem

    Existing maze-solving methods can become very slow as maze complexity and local connectivity increase, and biological or chemical approaches may not suit large, complex mazes.

    Source: §I · p. 1

  • Method

    The paper proposes a memristor network whose current-driven resistance-state changes encode maze solutions through massively parallel computation.

    Source: §I · p. 1, A. Model · p. 4

  • Results

    The simulations show that the network solves single-path mazes and identifies multiple solutions, with memristor states distinguishing paths by length.

    Source: B. Results · pp. 4–5

  • Takeaways & Limitations

    The authors conclude that memristive networks can solve mazes in a massively parallel way, with results stored in device states for later use.

    Source: §I · p. 1, §IV · p. 5

    The demonstration’s switching time is about 0.05 s, much longer than the roughly 5 ns switching times cited for nanoscale memristive devices.

    Source: B. Results · p. 5

Abstract

from arXiv · show

Solving mazes is not just a fun pastime. Mazes are prototype models in graph theory, topology, robotics, traffic optimization, psychology, and in many other 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 non-trivial 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 first application of memristive networks to the field of massively-parallel computing, but also a novel algorithm to solve mazes which could find applications in different research fields.

I. INTRODUCTION

Maze-solving methods can become slow as maze complexity and local connectivity increase, despite mazes’ relevance to fields including robotics and traffic optimization. The paper proposes a memristor network that computes in parallel, with simulations demonstrating maze solving in one step and multiple-path solutions sorted by length.

I. INTRODUCTION

  • Sequential search methods can slow dramatically as maze complexity and local connectivity increase, while biological or chemical approaches may also be unsuitable for large, complex mazes.Mazes also serve as prototype models across graph theory, topology, robotics, traffic optimization, and psychology.Source: §I · p. 1
  • The proposed memristor network performs maze solving through massively parallel computation, with resistance states recording the system’s dynamics.The paper describes memristors as resistors whose resistance depends on the system’s state history.Source: §I · p. 1
  • The simulations show that the processor finds a maze solution in one step, and in multiple-path mazes finds all solutions and sorts them by length.The authors distinguish the processor’s analog parallelism from parallelism in conventional computers.Source: §I · pp. 1–2
  • Memristors are selected over memcapacitors or meminductors because they are the most studied and can be readily realized experimentally.Source: §I · p. 1

II. MEMRISTIVE PROCESSOR

The processor maps a maze onto a reconfigurable grid of memristors and switches, then applies voltage between the entrance and exit. Current changes memristor states along connecting paths, encoding the solution; in multiple-path mazes, path resistance reflects relative length.

II. MEMRISTIVE PROCESSOR

  • Maze walls are encoded by setting the corresponding switches to “not connected,” allowing different maze topologies to be modeled on the same processor.Grid points represent crossings of periodic horizontal and vertical lines overlaid on the maze.Source: §II · p. 2
  • Applying voltage between entrance and exit drives current through connecting paths, changing their memristor states until the ON-state chain records the solution.The calculation is massively parallel because all memristors participate simultaneously; a proposed readout isolates a memristor and tests it with a short, small-amplitude pulse.Source: §II · pp. 2–3, Figure 2 · p. 3
  • In multiple-path mazes, shorter paths have lower resistance and greater current, so their memristors change state faster than those on longer paths.Different path states can therefore distinguish solutions and sort them by length.Source: §II · p. 3
  • Unlike a standard resistor network, the memristive network stores calculation results in its states for later use without external memory and local voltage-measurement hardware.Source: §II · p. 3
  • A memristive processor could be fabricated using CMOL architecture, and the authors note that small-scale implementations can use memristor emulators.The paper also cites experimental development of hybrid memristor-CMOS circuits and memristive memory chips.Source: §II · pp. 3–4

A. Model

The simulations model each memristor with a bounded internal state that determines its resistance and evolves in proportion to current. The authors use specified model parameters and a voltage reversal to simulate single- and two-path mazes.

A. Model

  • Numerical modeling provides a practical maze-solving algorithm but requires multiple computational steps, unlike the real memristive processor’s single-step computation.Source: A. Model · p. 4
  • RON and ROFF denote the minimal and maximal memristance values, respectively; xij is a dimensionless internal state variable bounded by 0 ≤ xij ≤ 1.The numerical results use RON = 10 Ohms, ROFF = 100 Ohms, RM_ij(t = 0) = 91 Ohms, x(t = 0) = 0.1, and α = 104/(s·A) for all memristors.Source: A. Model · p. 4
  • The internal state changes in proportion to memristor current, while grid-point potentials are computed from Kirchhoff’s current law at each time step.The network uses a sparse-matrix technique to solve for potentials, then computes state changes using Eq. (2).Source: A. Model · p. 4
  • In the illustrated two-path maze, the shorter alternative branch has lower memristance than the longer branch because its higher current produces greater state change.Source: Figure 4 · p. 4
  • The passage specifies an initial 0.1 s interval, then -50V at t > 0.1s, and compares single-path and multiple- (two-) path mazes.The sign of the applied voltage was changed to better represent the maze solution.Source: A. Model · p. 4

B. Results

The simulations found correct solutions for the tested mazes, including a two-path case where resistance changes distinguished shorter from longer paths. The paper also contrasts the numerical solver’s theoretical complexity with the single-step hardware approach and notes that its simulation parameters were selected for demonstration.

B. Results

  • The simulations found correct solutions for the tested mazes, and the modeled system evolved toward a unique stable solution with a reported 100% success rate.The examples used a 30 × 30 grid-point processor; the authors describe 100% success for simulations using their specified memristor model.Source: B. Results · pp. 4–5
  • About 0.06s switched every other memristor along a single solution path to the low-resistance ON state, recording the path in the resulting sequence.Reversing the applied voltage makes ON-path resistance rise and OFF-state resistance fall; at equal resistance, the intermediate states make the path more visible.Source: B. Results · pp. 4–5
  • In a two-path maze, current split according to path resistance, and memristors on shorter paths changed resistance faster, ranking solutions by length.The two-path case was created by removing one wall segment from the single-path maze.Source: B. Results · p. 5
  • The memristor type and simulation parameters were chosen to demonstrate the idea; the simulated switching time was about 0.05s, versus cited nanoscale-device times as short as 5ns.The authors argue that suitable voltage/current magnitudes could bring maze-solving time to a few nanoseconds or less; this is a projection, not the reported simulation time.Source: B. Results · p. 5
  • O(n2.376) is the best theoretical estimate for the numerical solver, while breadth-first search is O(V + E) ∼O(n2), described as only slightly better.The authors distinguish these numerical complexities from the hardware processor’s single computational step.Source: B. Results · p. 5

IV. CONCLUSION

The conclusion presents a memristive processor as a massively parallel way to solve mazes, with possible experimental or computer implementation. It anticipates applications to other computational problems and use either as a complete device or alongside traditional hardware.

IV. CONCLUSION

  • A network of memristors can solve mazes in a massively parallel way, and the approach can be implemented experimentally or on a computer.The conclusion describes the hardware implementation as superior to existing maze-solving methods, particularly as local graph connectivity increases.Source: §IV · p. 5
  • Networks of memcapacitors or meminductors could also perform massively parallel calculations, alongside the memristor-based approach.The conclusion notes that known experimental systems exhibit memcapacitive and meminductive properties, and that such circuits can be emulated using memristors.Source: §IV · p. 5
  • The authors anticipate that memristive processors could facilitate or solve other computational problems, including the traveling salesman problem and graph-theory problems.They envision use as either a complete computational device or a supplemental tool for traditional hardware.Source: §IV · p. 5

Supplementary materials to the manuscript Solving mazes with memristors: a massively-parallel approach by Y. V. Pershin and M. Di Ventra

The supplementary materials describe movies of the processor’s dynamics for single-path and multiple-path mazes, including electrical variables and a voltage-polarity change.

Supplementary materials

  • The single-path movie reports time, resistance, voltage, and current, and uses a red line for connected grid points with memristors below 80 Ohms.The applied-voltage polarity changes at t = 0.1s.Source: Supplementary materials to the… · p. 7
  • The multiple-path movie shows dynamics for a maze obtained by removing one wall segment from the single-path maze.It reports time, resistance, voltage, and current; its red line marks connected grid points with memristors below 80 Ohms, and voltage polarity changes at t = 0.1s.Source: Supplementary materials to the… · p. 7
  • The supplementary text lists a website where the movies can be found.The listed address is http://www.physics.sc.edu/ pershin/memdevices.htm.Source: Supplementary materials to the… · p. 7
Loading 1103.0021v2…