Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Simulation

From OpenWetWare

< Biomod | 2011 | Caltech/DeoxyriboNucleicAwesome(Difference between revisions)
Jump to: navigation, search
(Added code)
Current revision (18:57, 31 October 2011) (view source)
m (Cargo Sorting Simulation)
 
(21 intermediate revisions not shown.)
Line 3: Line 3:
__TOC__
__TOC__
==Overview==
==Overview==
-
Our proposed sorting mechanism depends very heavily on a particular random-walking mechanism that has not been demonstrated in literature before. The verification of this mechanism is thus a vital step in our research. Verification of the random walk in one dimension is fairly straightforward: as discussed in <LINK TO THE EXPERIMENTAL DESIGN SECTION>, a one-dimensional track is easy to construct, and will behave like a [http://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk standard 1D random walk], showing an average translation on the order of <math>n^{\frac{1}{2}}</math> after n steps. Thus, we should expect the time it takes to get to some specific level of fluorescence to be proportional to the square of the number of steps we start the walker from the irreversible substrate. If we can, in an experiment, record the fluorescence over time when the walker is planted at different starting points and show that that fluorescence varies by this relationship, we'll have fairly certainly verified one-dimensional random walking.
+
Our proposed sorting mechanism depends very heavily on a particular random-walking mechanism that has not been demonstrated in literature before. The verification of this mechanism is thus a vital step in our research. Verification of the random walk in one dimension is fairly straightforward: as discussed in [[Biomod/2011/Caltech/DeoxyriboNucleicAwesome/SPEX Experiments|SPEX experiments]], a one-dimensional track is easy to construct, and will behave like a [http://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk standard 1D random walk], showing an average translation on the order of <math>n^{\frac{1}{2}}</math> after n steps. Thus, we should expect the time it takes to get to some specific level of fluorescence to be proportional to the square of the number of steps we start the walker from the irreversible substrate. If we can, in an experiment, record the fluorescence over time when the walker is planted at different starting points and show that that fluorescence varies by this relationship, we'll have fairly certainly verified one-dimensional random walking.
Our particular case of 2D random walking, however, is not as easily understood, especially considering the mobility restrictions (ability to move to only 4 of 6 surrounding locations at any particular time) of our particular walker. As a control for the verification of 2D random walking, though, we still need to get an idea how long the random walk should take, and how that time will change as we start the walker at different points on the origami. We opt to do this by simulating the system with a set of movement rules derived from our design. We also use the same basic simulation (with a few alterations and extra features) to simulate our entire sorting system in a one-cargo, one-goal scenario, to give us some rudimentary numbers on how long sorting should take, with one vs multiple walkers.
Our particular case of 2D random walking, however, is not as easily understood, especially considering the mobility restrictions (ability to move to only 4 of 6 surrounding locations at any particular time) of our particular walker. As a control for the verification of 2D random walking, though, we still need to get an idea how long the random walk should take, and how that time will change as we start the walker at different points on the origami. We opt to do this by simulating the system with a set of movement rules derived from our design. We also use the same basic simulation (with a few alterations and extra features) to simulate our entire sorting system in a one-cargo, one-goal scenario, to give us some rudimentary numbers on how long sorting should take, with one vs multiple walkers.
Basic parameters and assumptions:
Basic parameters and assumptions:
-
*The unit of time is the '''step''', which is the time it takes a walker to take a step given four good opposite track locations (good locations to step to) around it.
+
*The unit of time is the '''step''', which is the time it takes a walker to attempt to interact with one of the surrounding six locations.
-
*The walkable track are given coordinates like a grid (which shifts the even columns up by 0.5). The bottom-left is <1, 1>, the top-left <1, 8>, and the bottom-right <16, 1>.
+
*Every probe on the origami are given coordinates like a grid (which shifts the even columns up by 0.5). The bottom-left is <1, 1>, the top-left <1, n>, and the bottom-right <m, 1>, <m, n> being the number of probes on the origami (which can be anything).
 +
**These layouts are inputted as a matrix in MATLAB, with the top-left being <1,1> and bottom-right being <m, n>; different objects on origami to be mounted on each probe are coded by number:
 +
***0 = nothing
 +
***1 = track 1
 +
***10 = walker on track 1
 +
***2 = track 2
 +
***20 = walker on track 2
 +
***3 = cargo
 +
***4 = cargo goal
 +
***40 = filled cargo goal
 +
***5 = walker goal
 +
***50 = filled walker goal
 +
**To turn a hexagonal grid into the square one that the grid layout implies, even columns are shifted up by 0.5 in this representation. This leads to the restriction that the first column must be a "high" column, as described in the code's documentation (see below).
*Movement rules are based on column:
*Movement rules are based on column:
-
** In even columns, a walker can move in directions <0, 1>, <0, -1>, <1, 0>, <-1, -1>.
+
** In even columns, a walker can move in directions <0, 1>, <0, -1>, <1, 0>, <-1, -1>, <-1, 1>, <1, 0>.
-
** In odd columns, a walker can move in directions <0, 1>, <0, -1>, <-1, 0>, <1, 1>.
+
** In odd columns, a walker can move in directions <0, 1>, <0, -1>, <-1, 0>, <1, 1>, <1, -1>, <-1, 0>.
 +
*Every time step, each walker being simulated takes a step in a random direction, and attempts to interact with whatever it hits:
 +
**If it tries to step off of the origami or onto something that isn't a track, it doesn't move.
 +
**If it tries to step to a track of the same type or an occupied track of either type, it does nothing.
 +
**If it tries to step to a track of the opposite type that's not occupied, it moves there.
 +
**If it tries to step onto a cargo, it'll pick it up but not move.
 +
**If it's carrying a cargo and tries to step onto a goal of the same type as the cargo, it'll drop the cargo but not move.
-
[[Image:MotionRulesJustification1.png|thumb|center|800px|An illustration of the grid and motion rules used in the simulation. The bottom-left is the origin (<1,1> because MATLAB indexes by 1). The 2D platform that will be used for random walking, including track A (red), track B (blue), the marker (black), and the irreversible track (purple), is shown on the left. The grid on the right -- the grid corresponding to our numbering system -- is created by shifting even columns up by 0.5. This arrangement reveals through the vertical symmetry of the arrangement that movement rules are going to vary by column only. The valid moves in even and odd columns shown on the left are mapped onto the grid on the right to derive the moveset listed above.]]
+
[[Image:MotionRulesDerivation.png|thumb|center|800px|An illustration of the grid and motion rules (for walking; directions of motion that won't result in a step aren't shown) used in the simulation. The bottom-left is the origin (<1,1> because MATLAB indexes by 1). The 2D platform, including track A (red), track B (blue), the marker (tan), cargo (gold), and goal (green), is shown on the left. The grid on the right -- the grid corresponding to our numbering system and representing viable track for a random walk -- is created by shifting even columns up by 0.5. This arrangement (which is, in essence, a visualization tool) reveals through the vertical symmetry of the arrangement that movement rules are going to vary by column only. The valid moves in even and odd columns shown on the left are mapped onto the grid on the right to derive the moveset listed above.]]
==MATLAB Code==
==MATLAB Code==
-
At the core of the simulation is a function which runs runs one random walk on an origami of specified size. It can run in both a cargo-bearing (one-cargo one-goal) and a purely random-walk mode. The former has cargo positions corresponding to our particular origami pre-programmed and starting with multiple (specified by user) walkers at random locations on the origami, and terminates when all of the cargos have been "sorted" to the goal location (the x axis). The latter runs one walker starting at a specified location, and terminates when that walker reaches the specified irreversible track location. The function returns a log reporting when cargos were picked up and dropped off, and a count of the number of steps the simulation took. This function is utilized by separate cargo-bearing and random-walk data collection programs that call the function many times over a range of parameters.
+
At the core of the simulation is a function which runs runs one random walk on an origami of specified size. It can run in both a cargo-bearing (one-cargo one-goal) and a purely random-walk mode. The former has cargo positions corresponding to our particular origami pre-programmed and starting with multiple (specified by user) walkers at random locations on the origami, and terminates when all of the cargos have been "sorted" to the goal location (the x axis). The latter runs one walker starting at a specified location, and terminates when that walker reaches the specified irreversible track location. The function returns a log of all walkers positions over time, a log reporting when cargos were picked up and dropped off, a count of the number of steps the simulation took, and if desired, a move of the random walk. This function is utilized by separate cargo-bearing and random-walk data collection programs that call the function many times over a range of parameters.
-
The function code (saved as randomWalkFunction.m):
+
The function code (saved as randomWalkFunctionGeneric.m):
-
<code><pre>
+
<span class="_toggler-codeA">Toggle Code</span>
-
function [cargoLog, steps] = randomWalkFunction(x, y, length, numWalkers, ...
+
<div class="codeA" style="display:none;
-
     startPos, endPos, cargoBearing, restricted)
+
      border: 1px dashed rgb(0, 0, 0);
-
%x: Width        y: Height
+
      padding-top: 10px; 
-
%length: max # of steps to run simulation
+
      padding-right: 10px; 
-
%numWalkers = number of walkers to simulate in cargoBearing state
+
      padding-bottom: 10px; 
-
%startPos = starting position for walker in randomwalk state
+
      padding-left: 10px;
-
%endPos = irreversible track location in randomwalk state
+
      background-color: #FEF7EA;"><code><syntaxhighlight lang="matlab">
-
%cargoBearing = running cargoBearing (1) vs randomWalking (0)
+
function [log, cargoLog, steps, M] = randomWalkFunctionGeneric(...
-
%restricted = whether we're paying attention to borders
+
    length, layoutMode, startPos, numWalkers, cargoBearing, error,...
 +
     record, spaceWalkOnly, departThreshold, arriveThreshold)
-
%Random walking cargo pickup/dropoff simulation
+
%Random walking / cargo sorting  simulation for more general form
-
%for origami tile, x (horizontal) by y (vertical) dim.
+
%track layouts. More flexible in terms of layout but ultimately
-
%Locations index by 1. x+ = right, y+ = up
+
%probably a touch slower.
-
% Gregory Izatt & Caltech BIOMOD 2011
+
%Gregory Izatt & Caltech BIOMOD 2011
-
% 20110615: Initial revision
+
%20110713: Init revision
-
% 20110615: Continuing development
+
%20110714: Continuing init revision.
-
%          Added simulation for cargo pickup/dropoff
+
%20110715: Continuing debugging of init revision.
-
%          Adding support for multiple walkers
+
%20110718: Debugging issue where walkers n>=2 have occasional
-
% 20110616: Debugging motion rules, making display better
+
%          unexplained jaints to 0,0 in the log
-
% 20110616: Modified to be a random walk function, to be
+
%20110719: Adding full movie capture capability, mostly working on
-
%           called in a data accumulator program
+
%          rendering origami during movie production
 +
%20110816: Adding support for spacewalking and random
 +
%           walker appearance / departure
 +
%20110817: Adding support for ability to do /just/ a spacewalk
 +
%          for diagnostic / control purposes
 +
%Defines layouts:
 +
 
 +
%Layouts:
 +
%1 = Standard
 +
%2 = Mini-playground
 +
%3 = 1D random walk / cargo sort
 +
%4 = Wide & long random walk
 +
 
 +
%In layout specification:
 +
%0 = nothing
 +
%1 = track 1
 +
%10 = walker on track 1
 +
%2 = track 2
 +
%20 = walker on track 2
 +
%3 = cargo
 +
%4 = cargo goal
 +
%40 = filled cargo goal
 +
%5 = walker goal
 +
%50 = filled walker goal
 +
%Specification arrays are in origami coodinates as
 +
%defined on the BIOMOD wiki's simulation page.
 +
%Walking will assume that system, so make sure
 +
%they're right!
 +
%Also, make sure you start with an odd row (a high one)
 +
% or the movement will be messed up.
 +
 
 +
if layoutMode == 1
 +
    layout = ...
 +
    [[1, 1, 2, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 2, 2]
 +
    [2, 2, 1, 1, 2, 2, 3, 1, 2, 2, 3, 1, 2, 2, 1, 1]
 +
    [1, 1, 0, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 0, 2]
 +
    [2, 2, 3, 1, 2, 2, 1, 0, 3, 2, 1, 1, 2, 2, 3, 1]
 +
    [1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2]
 +
    [2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1]
 +
    [1, 4, 2, 4, 1, 4, 2, 2, 1, 4, 2, 4, 1, 4, 2, 4]
 +
    [2, 4, 1, 4, 2, 4, 1, 1, 2, 4, 1, 4, 2, 4, 1, 4]];
 +
elseif layoutMode == 2
 +
    layout = ...
 +
    [[0, 1, 0, 2, 1, 1, 0, 2]
 +
    [0, 2, 3, 1, 2, 2, 3, 1]
 +
    [0, 1, 2, 2, 1, 1, 2, 2]
 +
    [0, 2, 1, 0, 3, 2, 1, 1]
 +
    [0, 1, 2, 2, 1, 1, 2, 2]
 +
    [0, 2, 1, 1, 2, 2, 1, 1]
 +
    [0, 4, 2, 2, 1, 4, 2, 4]
 +
    [0, 4, 1, 1, 2, 4, 1, 4]];
 +
elseif layoutMode == 3
 +
    layout = ...
 +
    [[0, 2, 0]
 +
    [0, 1, 0]
 +
    [3, 2, 0]
 +
    [0, 1, 3]
 +
    [0, 2, 0]
 +
    [0, 1, 0]
 +
    [3, 2, 0]
 +
    [0, 1, 0]
 +
    [0, 2, 0]
 +
    [1, 4, 0]
 +
    [2, 4, 0]];
 +
elseif layoutMode == 4
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0]
 +
    [0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 410
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 416
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 422
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 457
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 434
 +
    layout = ...
 +
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 5]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 1]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 1, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 +
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]];
 +
elseif layoutMode == 5
 +
    layout = ...
 +
    [[1, 1, 2, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 5, 2]
 +
    [2, 2, 1, 1, 2, 2, 0, 1, 2, 2, 0, 1, 2, 2, 1, 1]
 +
    [1, 1, 0, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 0, 2]
 +
    [2, 2, 0, 1, 2, 2, 1, 0, 0, 2, 1, 1, 2, 2, 0, 1]
 +
    [1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2]
 +
    [2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1]
 +
    [1, 0, 2, 0, 1, 0, 2, 2, 1, 0, 2, 0, 1, 0, 2, 0]
 +
    [2, 0, 1, 0, 2, 0, 1, 1, 2, 0, 1, 0, 2, 0, 1, 0]];
 +
end
 +
%Get the orientation right:
 +
layoutSize = size(layout);
 +
layout = flipud(layout);
 +
startPos(1) = layoutSize(1) - startPos(1) + 1;
 +
layout = transpose(layout);
 +
startPos = [startPos(2), startPos(1)];
 +
layoutSize = [layoutSize(2), layoutSize(1)];
 +
 
 +
 
 +
%Initialize some logging variables we'll need:
 +
steps = 0;
 +
log = zeros(length, 2*numWalkers + 1);
 +
cargoLog = [];
 +
 
 +
%Movement rules:
 +
evenPoss = [0, 1 ; 0, -1; 1, 0; -1, 0; 1, -1; -1, -1]; %For even columns
 +
oddPoss = [0, 1 ; 0, -1; 1, 0; -1, 0; 1, 1; -1, 1]; %For odd columns
-
%Walkers:
+
%Walkers positioning:
% Set position randomly if we're doing cargo bearing simulation,
% Set position randomly if we're doing cargo bearing simulation,
% or set to supplied startPos if not.
% or set to supplied startPos if not.
Line 49: Line 225:
     currentPos = zeros(numWalkers, 2);
     currentPos = zeros(numWalkers, 2);
     for i=1:numWalkers
     for i=1:numWalkers
-
       currentPos(i, :) = [randi(x, 1), randi(y, 1)];
+
       done = 0;
 +
      while done ~= 1
 +
            currentPos(i, :) = [randi(layoutSize(1), 1), ...
 +
                                randi(layoutSize(2), 1)];
 +
            done = (layout(currentPos(i, 1), currentPos(i, 2)) == 1 || ...
 +
                    layout(currentPos(i, 1), currentPos(i, 2)) == 2);
 +
      end
 +
      layout(currentPos(i, 1), currentPos(i, 2)) = ...
 +
              layout(currentPos(i, 1), currentPos(i, 2)) * 10;
     end
     end
-
    % If doing a cargobearing walk, set these to cargo positions too:
 
-
    cargoPos = [[3, 5]; [9, 5]; [15, 5]; [7, 2]; [11, 2]];
 
else
else
-
    currentPos = startPos;
 
     numWalkers = 1; %Want to make sure this is one for this case
     numWalkers = 1; %Want to make sure this is one for this case
 +
    currentPos = startPos;
 +
    if currentPos(1) < 1 || currentPos(1) > layoutSize(1) || ...
 +
      currentPos(2) < 1 || currentPos(2) > layoutSize(2) || ...
 +
        (layout(currentPos(1), currentPos(2)) ~= 1 && ...
 +
        layout(currentPos(1), currentPos(2)) ~= 2)
 +
          'Invalid start position.';
 +
          layout
 +
          currentPos
 +
          cargoLog = [];
 +
          steps = -1;
 +
          M = [];
 +
          return
 +
    end
 +
    layout(currentPos(1), currentPos(2)) = ...
 +
        layout(currentPos(1), currentPos(2)) * 10;
end
end
 +
%Something to keep track of which walkers is carrying cargos:
 +
hasCargo = zeros(numWalkers);
 +
%Error: If there's a valid error rate, go omit some positions:
 +
if error > 0
 +
    for y=1:layoutSize(2)
 +
        for x=1:layoutSize(1)
 +
            %Only omit if it's not already blocked by something
 +
            if rand <= error
 +
                layout(x, y) = 0;
 +
            end
 +
        end
 +
    end
 +
end
-
%Initialize some things:
+
%Convenience:
-
steps = 0;  
+
if cargoBearing == 1
-
hasCargo = zeros(numWalkers);
+
    numCargoPos = 0;
-
sorted = 0;
+
    for y=1:layoutSize(2)
-
cargoAPoss = [0, 1; 0, -1; 1, 0; -1, -1]; %Movement rules
+
        for x=1:layoutSize(1)
-
cargoBPoss = [0, 1; 0, -1; -1, 0; 1, 1]; %''
+
            if layout(x, y) == 3
-
log = zeros(length, 2*numWalkers + 1);
+
                numCargoPos = numCargoPos + 1;
-
cargoLog = [];
+
            end
-
collisionLog = [];
+
        end
 +
    end
 +
end
 +
 
 +
if record == 0
 +
    M = [];
 +
else
 +
    aviobj = avifile('RR2.avi');
 +
end
 +
 
 +
%Indicator for premature completion
 +
done = 0;
-
for i=1:length,
+
%Main loop:
 +
for i=1:length
     for walker=1:numWalkers
     for walker=1:numWalkers
-
         %Add current pos to log
+
         %Add current pos to log:
         log(steps + 1, 2*walker-1:2*walker) = currentPos(walker, :);
         log(steps + 1, 2*walker-1:2*walker) = currentPos(walker, :);
          
          
-
         %Update pos to randomly
+
         %Update pos to randomly chosen neighbor, based on motion rules
-
        %chosen neighbor -- remember,
+
         temp = randi(6, 1);
-
        %these are the only valid neighbors:
+
         if ~spaceWalkOnly
-
        %  (0, +1), (0, -1)
+
            if (mod(currentPos(walker, 1), 2) == 0)
-
        % IF (x/2)%1 = 0:
+
                newPos = currentPos(walker, :) + evenPoss(temp, :);
-
        %  (+1, 0), (-1, -1)
+
             else
-
        % ELSE:
+
                newPos = currentPos(walker, :) + oddPoss(temp, :);  
-
        %  (-1, 0), (+1, +1)
+
            end
-
 
+
-
         temp = randi(4, 1);
+
-
         if (mod(currentPos(walker, 1),2) == 0)
+
-
             newPos = currentPos(walker, :) + cargoAPoss(temp, :);  
+
         else
         else
-
            newPos = currentPos(walker, :) + cargoBPoss(temp, :);
 
-
        end
 
-
 
-
        %If we just went out of bounds in the -y direction (toward
 
-
        % a goal) and had cargos, we drop off
 
-
        if cargoBearing && (hasCargo(walker) == 1 && (newPos(2) < 1))
 
-
            %Drop cargo, increment cargo-dropped-count
 
-
            hasCargo(walker) = 0;
 
-
            sorted = sorted + 1;
 
-
            %Don't move
 
             newPos = currentPos(walker, :);
             newPos = currentPos(walker, :);
-
            cargoLog = [cargoLog; steps, walker];
 
         end
         end
 +
       
 +
        %If this is out of defined boundaries, don't do anything:
 +
        if ~(newPos(1) > layoutSize(1) || newPos(1) < 1 || ...
 +
            newPos(2) > layoutSize(2) || newPos(2) < 1)       
 +
            %Now react based on what kind of spot the new position is:
 +
            oldPosIdent = layout(currentPos(walker, 1), ...
 +
                                currentPos(walker, 2)) / 10;
 +
            newPosIdent = layout(newPos(1), newPos(2));
-
        %General out-of-bounds case without cargo drop:
+
            %Can't move from one track to the same kind of track:
-
        if restricted && ((newPos(1) > x || newPos(1) < 1 || ...
+
            if newPosIdent == oldPosIdent
-
                 newPos(2) > y || newPos(2) < 1))
+
                 %'Cant step to same kind of track'
-
            %Don't go anywhere
+
             %Hitting cargos: pick up cargo if possible.
-
             newPos = currentPos(walker, :);
+
             elseif newPosIdent == 3 && cargoBearing
-
        end
+
                 if hasCargo(walker) == 0
-
 
+
                     hasCargo(walker) = 1;
-
        %Hitting cargos case:
+
                    layout(newPos(1), newPos(2)) = 0;
-
        if cargoBearing
+
                    cargoLog = [cargoLog; walker, newPos, steps];
-
             m = (find(cargoPos(:, 1) == newPos(1)));
+
-
            for n=m
+
-
                 if cargoPos(m, 2) == newPos(2)
+
-
                     %Remove the cargo from the list of cargos and "pick up" if
+
-
                    %you don't already have a cargo
+
-
                    if hasCargo(walker) == 0
+
-
                        cargoPos(m, :) = [-50, -50];
+
-
                        hasCargo(walker) = 1;
+
-
                        cargoLog = [cargoLog; steps, walker];
+
-
                    %Anyway, don't move there
+
-
                    newPos = currentPos(walker, :);
+
-
                    end
+
                 end
                 end
 +
                %'Hit cargo planter'
 +
            %Hitting goals: drop a cargo if possible.
 +
            elseif newPosIdent == 4 && cargoBearing
 +
                if hasCargo(walker) == 1
 +
                    hasCargo(walker) = 0;
 +
                    layout(newPos(1), newPos(2)) = 40;
 +
                    cargoLog = [cargoLog; walker, newPos, steps];
 +
                    done = done + 1/numCargoPos;
 +
                end
 +
                %'Hit goal'
 +
            %Hitting walker goal: go there and trigger completion.
 +
            elseif newPosIdent == 5 
 +
                %'Hit walker goal'
 +
                currentPos(walker, :) = newPos;
 +
                layout(newPos(1), newPos(2)) = 50;
 +
                done = 1;
 +
            %Valid move, and we haven't been shot down yet?
 +
            % Then actually move, and update layout to reflect that.
 +
            elseif newPosIdent == 1 || newPosIdent == 2
 +
                %'Moving'
 +
                layout(currentPos(walker, 1), currentPos(walker, 2)) =  ...
 +
                layout(currentPos(walker, 1), currentPos(walker, 2)) / 10;
 +
                currentPos(walker, :) = newPos;
 +
                layout(currentPos(walker, 1), currentPos(walker, 2)) =  ...
 +
                layout(currentPos(walker, 1), currentPos(walker, 2)) * 10;
 +
            end 
 +
      end 
 +
    end
 +
   
 +
    %Finish up bookkeeping log and step count for this step
 +
    log(steps + 1, 2*numWalkers + 1) = steps;
 +
    steps = steps + 1;
 +
   
 +
    if record
 +
        hold on;
 +
        xlim([0, layoutSize(1) + 1]);
 +
        ylim([0, layoutSize(2) + 1]);
 +
        %Plot walkers:
 +
        for walker=1:numWalkers
 +
            tempPos = currentPos(walker, :);
 +
            if mod(tempPos(1), 2) == 0
 +
                tempPos(2) = tempPos(2) - 0.5;
             end
             end
 +
            if hasCargo(walker)
 +
                plot(tempPos(1), tempPos(2), ...
 +
                        'o', 'color', [0, 0.5, 0], 'MarkerSize', 15);
 +
            end
 +
            plot(tempPos(1), tempPos(2), 'o', ...
 +
                        'color', [0, 0, 0], 'MarkerSize', 25);
         end
         end
          
          
-
         % Already on irrev. cargo case:
+
         %Plot origami:
-
         if (currentPos(walker, :) == endPos)
+
         for x=1:layoutSize(1)
-
            return
+
            for y=1:layoutSize(2)
-
        end
+
                %Plot with coloration specific to probe identity
-
       
+
                if layout(x, y) == 0  || ...
-
        %Hitting other walkers case:
+
                  layout(x, y) == 10 || ...
-
        if numWalkers > 1
+
                  layout(x, y) == 20
-
            m = (find(currentPos(:, 1) == newPos(1)));
+
                    color = [1 1 1];
-
            for n=m
+
                elseif layout(x, y) == 1
-
                 if (currentPos(n, 2) == newPos(2))
+
                    color = [1 0 0];
-
                     %Derp, don't go there
+
                elseif layout(x, y) == 2
-
                     newPos = currentPos(walker, :);
+
                    color = [0 0 1];
-
                     collisionLog = [collisionLog; newPos, walker];
+
                elseif layout(x, y) == 3
 +
                    color = [0 .5 0];
 +
                 elseif layout(x, y) == 4
 +
                    color = [0 1 1];
 +
                elseif layout(x, y) == 5
 +
                     color = [1 1 0];
 +
                elseif layout(x, y) == 40
 +
                     color = [0 .5 0];
 +
                elseif layout(x, y) == 50
 +
                     color = [.5 .5 .5];
 +
                end
 +
                tempY = y;
 +
                if mod(x, 2) == 0
 +
                    tempY = tempY - 0.5;
                 end
                 end
 +
                plot(x, tempY, 's', 'Color', color, 'MarkerSize', 10);
             end
             end
         end
         end
-
          
+
         M(i) = getframe;
-
         %Finally actually update the position
+
         aviobj = addframe(aviobj, M(i));
-
        currentPos(walker, :) = newPos;
+
         hold off;
-
          
+
        clf;
     end
     end
      
      
-
     % Step forward, update log
+
     %If finished, done with everything
-
     steps = steps + 1;
+
     if done >= 1
-
    log(steps, 2*numWalkers + 1) = steps - 1;
+
        if record
 +
            aviobj = close(aviobj);
 +
        end
 +
        log((steps + 1):length, :) = [];
 +
        return
 +
    end 
      
      
-
     if (sorted == 5)
+
     %If we're thinking about astronaut / orphaned walkers, do it here:
-
         log(steps+1:end, :) = [];
+
    %(astronaut walking isn't yet considered for cargobearing walks,
-
         break
+
    %(but should be implemented in the future if it becomes an issue)
 +
    if rand() > departThreshold && cargoBearing == 0
 +
         numWalkers = numWalkers + 1;
 +
        log = [log(:, 1:end-1) zeros(length, 2) log(:, end)];
 +
        currentPos = [currentPos; [1, 1]];
 +
         landingDone = 0;
 +
        while landingDone ~= 1
 +
            currentPos(end, :) = [randi(layoutSize(1), 1), ...
 +
                                randi(layoutSize(2), 1)];
 +
            if layout(currentPos(end, 1), currentPos(end, 2)) == 4
 +
                done = 1;
 +
            end
 +
            landingDone = (layout(currentPos(end, 1), ...
 +
                                  currentPos(end, 2)) == 1 || ...
 +
                          layout(currentPos(end, 1), ...
 +
                                  currentPos(end, 2)) == 2);
 +
        end
 +
    end
 +
    if rand() > arriveThreshold && numWalkers > 0 && cargoBearing == 0
 +
        walkerToRemove = randi(numWalkers);
 +
        numWalkers = numWalkers - 1;
 +
        log(:, walkerToRemove*2-1:walkerToRemove*2) = [];
 +
        currentPos(walkerToRemove, :) = [];
     end
     end
      
      
end
end
-
 
+
if record
 +
    aviobj = close(aviobj);
 +
end
return
return
-
</pre></code>
+
</syntaxhighlight></code></div>
 +
===Examining Errors in Origami===
 +
This code can be used to generate diagrams like those below, visualizing the mobility of the walker. One immediate question is the vulnerability of this layout to errors in the laying of track. We investigate this by, when generating the track layout in the beginning of randomWalkFunction, introducing a small (specified by input) percent chance that any single probe will be omitted. Error rates at around 10% are bearable; error rates greater than that, however, are catastrophic, causing walkers to become permanently trapped in small sections of the track field.
 +
[[Image:FullGridErrors.png | center | 800 px | thumb | Node graphs showing walker mobility of origami. Each junction represents a track, and each edge represents a step a walker can take. The left diagram shows no error, whereas the other two show increasing error rates. We observe that 10% error rates decrease walker mobility, but tend not to trap the walker in any particular location; 20% error rates or greater, over several tests, tend to cause catastrophic loss of mobility, making the sorting task impossible.]]
==Random-Walk Simulation==
==Random-Walk Simulation==
 +
The data we need from this simulator is a rough projection of the fluorescence response from our test of 2D random walking, which should change based on the starting location of the walker. [[Image:Caltech5000iter0ErrorRRWideLinearTrack.jpg | thumb | 300 px | right | A plot of the number of steps (on an average over 5000 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at one end. This test was done assuming a 0% error rate, on the 3-track-wide linear random walking playground that we are using to investigate random walking (in a pseudolinear environment).]]Because this fluorescence is changed by a fluorophore-quencher interaction upon a walker reaching its irreversible track, in the case where we plant all of the walkers on the same starting track, the time it takes <math>(fluorescence_{initial} - fluorescence_{current})</math> in the sample to reach some standard value should be proportional to the average time it takes the walkers to reach the irreversible substrate. As this 'total steps elapsed' value is one of the outputs of our simulation function, we can generate a map of these average walk durations by running a large number of simulations at each point on the origami and averaging the results: <span class="_toggler-codeB">Toggle Code</span>
 +
<div class="codeB" style="display:none;
 +
      border: 1px dashed rgb(0, 0, 0);
 +
      padding-top: 10px; 
 +
      padding-right: 10px; 
 +
      padding-bottom: 10px; 
 +
      padding-left: 10px;
 +
      background-color: #FEF7EA;"><code><syntaxhighlight lang="matlab">
 +
%%% Random walk bulk simulation that
 +
%% runs a battery of tests and plots the results
 +
%% to see how long random walks take on average to complete
 +
%% based on distance from goal / platform size
 +
% Gregory Izatt & Caltech BIOMOD 2011
 +
% 20110616: Initial revision
 +
% 20110624: Updating some documentation
 +
% 20110701: Updating to use new, updated randomWalkFunction
 +
% 20110707: Updated to use new error-allowing randomWalkFunction
 +
% 20110719: Updating to use new and hopefully much faster
 +
%              randomWalkFunctionGeneric
 +
%% Dependency: makes calls to randomWalkFunctionGeneric.m
 +
%Layout modes:
 +
layoutMode = 4;
 +
if layoutMode == 4
 +
    yMax = 15;
 +
    xMax = 9;
 +
elseif layoutMode == 5
 +
    yMax = 16;
 +
    xMax = 8;
 +
else
 +
    'Layout not yet implemented.'
 +
    return
 +
end
 +
 +
iterations = 500; %Test each case of random walk this # times
 +
averages = zeros(xMax, yMax); %Init'ing this
 +
trash = []; %Trash storing variable
 +
 +
%Cycle over whole area, starting the walker at each position
 +
%and seeing how long it takes it to get to the stop position
 +
matlabpool(3)
 +
for x=1:xMax
 +
    for y=1:yMax
 +
        temp = zeros(iterations, 1);
 +
        parfor i=1:iterations
 +
            [trash, trash2, temp(i), trash3]=randomWalkFunctionGeneric(...
 +
                10000, layoutMode, [x, y], 1, 0, 0.1, 0, 0, 1, 1);
 +
        end
 +
        stdDev(x, y) = std(temp);
 +
        averages(x, y) = mean(temp)
 +
    end
 +
end
 +
matlabpool close
 +
</syntaxhighlight></code></div>
 +
===Results===
 +
Results of the bulk data collection at right show that the average random-walk duration, and thus the time for <math>(fluorescence_{initial} - fluorescence_{current})</math> to reach some standard level, increases with distance, though it changes less significantly the farther out one gets. We can also use a similar simulation (run instead with tracks that don't continue past the start location of the walker, an arrangement which we have found to behave more like a linear track) data to generate approximate half-completion times, which we can compare with the SPEX results of the same random walk to both estimate the amount of time it takes the walker to perform a single branch migration on our origami, and to see if whatever our walker is doing on origami is looking like a random walk, as compared to a repeated jumping across or between origami platforms (whose half-completion times for this test would presumably not depend on the track length at all). That data is detailed on the SPEX results page.
 +
 +
==Cargo Sorting Simulation==
 +
This simulation investigates both the overall tractability of our sorting problem, and the degree to which it can be parallelized via the addition of multiple walkers onto a single origami. [[Image:250iters0ErrorCargoSort.jpg | thumb | 300px | right | A plot of the number of steps (on an average over 250 iterations) it takes n walkers to sort all five cargos to respective goals on a perfectly formed 16x8 track, as detailed above. The jaggedness in the curve is a result of the large spread of results for any given test.]] It runs by making repeated calls to randomWalkFunction in its cargo-bearing mode, testing the number of steps it takes to sort all five cargos to respective goals over a range of number of cooperating walkers: <span class="_toggler-codeC">Toggle Code</span>
 +
<div class="codeC" style="display:none;
 +
      border: 1px dashed rgb(0, 0, 0);
 +
      padding-top: 10px; 
 +
      padding-right: 10px; 
 +
      padding-bottom: 10px; 
 +
      padding-left: 10px;
 +
      background-color: #FEF7EA;"><code><syntaxhighlight lang="matlab">
 +
%%% Cargo pickup/dropoff bulk simulation that
 +
%% runs a battery of tests and plots the results
 +
%% to see how long cargo sorts take on average
 +
% Gregory Izatt & Caltech BIOMOD 2011
 +
% 20110616: Initial revision
 +
% 20110616: Fixing to fit cargoSort.m revision
 +
% 20110623: Fixing documentation
 +
% 20110701: Updating to work with new and improved randomWalkFunction
 +
% 20110707: Updated to include error rate addition in randomWalkFunction
 +
%% Dependency: Makes calls to randomWalkFunction.m
 +
 +
iterations = 50; %Test each #walker scenario this many times
 +
maxNumWalkers = 30; %Test scenarios with up to this many walkers
 +
averages = zeros(maxNumWalkers, 1);
 +
medians = zeros(maxNumWalkers, 1);
 +
 +
'Initialized...'
 +
 +
matlabpool(3)  %Built-in parallel processing for speedup.
 +
              %Change "4" to your # of cores.
 +
             
 +
for numWalkers=1:maxNumWalkers  %Iterate over possible #'s of walkers
 +
    tempStorage = zeros(iterations, 1);
 +
    parfor i=1:iterations %Iterate a bunch of times
 +
        [trash, trash2, temp] = randomWalkFunction(16, 8, 10000, ...
 +
            numWalkers, [1, 1], [-100, -100], 1, 1, 0.0);
 +
        tempStorage(i) = temp;
 +
    end
 +
    averages(numWalkers) = mean(tempStorage);  %Store the average
 +
    medians(numWalkers) = median(tempStorage);
 +
    numWalkers, averages
 +
end
 +
matlabpool close
 +
averages
 +
plot(averages)
 +
</syntaxhighlight></code></div>
 +
(Note: this code is now obsolete (as it relies on an obsolete version of the randomWalkFunction script), and may be rewritten in the future. This should not, however, impact the validity of this code's results.
 +
===Results===
 +
While a single walker takes over a thousand steps to complete the sorting challenge, the addition of even a single walker vastly decreases the completion time, and additional walkers decrease it further, until a critical point is reached where the walkers are more getting in the way than helping with the sorting process. This is visible in the positive slope visible in the diagram at right that starts at around the 20 walker point.
{{Template:DeoxyriboNucleicAwesomeFooter}}
{{Template:DeoxyriboNucleicAwesomeFooter}}

Current revision

Image:DeoxyriboNucleicAwesomeHeader.jpg

Friday, August 1, 2014

Home

Members

Project

Protocols

Progress

Discussion

References


Simulations

Contents

Overview

Our proposed sorting mechanism depends very heavily on a particular random-walking mechanism that has not been demonstrated in literature before. The verification of this mechanism is thus a vital step in our research. Verification of the random walk in one dimension is fairly straightforward: as discussed in SPEX experiments, a one-dimensional track is easy to construct, and will behave like a standard 1D random walk, showing an average translation on the order of n^{\frac{1}{2}} after n steps. Thus, we should expect the time it takes to get to some specific level of fluorescence to be proportional to the square of the number of steps we start the walker from the irreversible substrate. If we can, in an experiment, record the fluorescence over time when the walker is planted at different starting points and show that that fluorescence varies by this relationship, we'll have fairly certainly verified one-dimensional random walking.

Our particular case of 2D random walking, however, is not as easily understood, especially considering the mobility restrictions (ability to move to only 4 of 6 surrounding locations at any particular time) of our particular walker. As a control for the verification of 2D random walking, though, we still need to get an idea how long the random walk should take, and how that time will change as we start the walker at different points on the origami. We opt to do this by simulating the system with a set of movement rules derived from our design. We also use the same basic simulation (with a few alterations and extra features) to simulate our entire sorting system in a one-cargo, one-goal scenario, to give us some rudimentary numbers on how long sorting should take, with one vs multiple walkers.

Basic parameters and assumptions:

  • The unit of time is the step, which is the time it takes a walker to attempt to interact with one of the surrounding six locations.
  • Every probe on the origami are given coordinates like a grid (which shifts the even columns up by 0.5). The bottom-left is <1, 1>, the top-left <1, n>, and the bottom-right <m, 1>, <m, n> being the number of probes on the origami (which can be anything).
    • These layouts are inputted as a matrix in MATLAB, with the top-left being <1,1> and bottom-right being <m, n>; different objects on origami to be mounted on each probe are coded by number:
      • 0 = nothing
      • 1 = track 1
      • 10 = walker on track 1
      • 2 = track 2
      • 20 = walker on track 2
      • 3 = cargo
      • 4 = cargo goal
      • 40 = filled cargo goal
      • 5 = walker goal
      • 50 = filled walker goal
    • To turn a hexagonal grid into the square one that the grid layout implies, even columns are shifted up by 0.5 in this representation. This leads to the restriction that the first column must be a "high" column, as described in the code's documentation (see below).
  • Movement rules are based on column:
    • In even columns, a walker can move in directions <0, 1>, <0, -1>, <1, 0>, <-1, -1>, <-1, 1>, <1, 0>.
    • In odd columns, a walker can move in directions <0, 1>, <0, -1>, <-1, 0>, <1, 1>, <1, -1>, <-1, 0>.
  • Every time step, each walker being simulated takes a step in a random direction, and attempts to interact with whatever it hits:
    • If it tries to step off of the origami or onto something that isn't a track, it doesn't move.
    • If it tries to step to a track of the same type or an occupied track of either type, it does nothing.
    • If it tries to step to a track of the opposite type that's not occupied, it moves there.
    • If it tries to step onto a cargo, it'll pick it up but not move.
    • If it's carrying a cargo and tries to step onto a goal of the same type as the cargo, it'll drop the cargo but not move.
An illustration of the grid and motion rules (for walking; directions of motion that won't result in a step aren't shown) used in the simulation. The bottom-left is the origin (<1,1> because MATLAB indexes by 1). The 2D platform, including track A (red), track B (blue), the marker (tan), cargo (gold), and goal (green), is shown on the left. The grid on the right -- the grid corresponding to our numbering system and representing viable track for a random walk -- is created by shifting even columns up by 0.5. This arrangement (which is, in essence, a visualization tool) reveals through the vertical symmetry of the arrangement that movement rules are going to vary by column only. The valid moves in even and odd columns shown on the left are mapped onto the grid on the right to derive the moveset listed above.
An illustration of the grid and motion rules (for walking; directions of motion that won't result in a step aren't shown) used in the simulation. The bottom-left is the origin (<1,1> because MATLAB indexes by 1). The 2D platform, including track A (red), track B (blue), the marker (tan), cargo (gold), and goal (green), is shown on the left. The grid on the right -- the grid corresponding to our numbering system and representing viable track for a random walk -- is created by shifting even columns up by 0.5. This arrangement (which is, in essence, a visualization tool) reveals through the vertical symmetry of the arrangement that movement rules are going to vary by column only. The valid moves in even and odd columns shown on the left are mapped onto the grid on the right to derive the moveset listed above.

MATLAB Code

At the core of the simulation is a function which runs runs one random walk on an origami of specified size. It can run in both a cargo-bearing (one-cargo one-goal) and a purely random-walk mode. The former has cargo positions corresponding to our particular origami pre-programmed and starting with multiple (specified by user) walkers at random locations on the origami, and terminates when all of the cargos have been "sorted" to the goal location (the x axis). The latter runs one walker starting at a specified location, and terminates when that walker reaches the specified irreversible track location. The function returns a log of all walkers positions over time, a log reporting when cargos were picked up and dropped off, a count of the number of steps the simulation took, and if desired, a move of the random walk. This function is utilized by separate cargo-bearing and random-walk data collection programs that call the function many times over a range of parameters.

The function code (saved as randomWalkFunctionGeneric.m): Toggle Code

Examining Errors in Origami

This code can be used to generate diagrams like those below, visualizing the mobility of the walker. One immediate question is the vulnerability of this layout to errors in the laying of track. We investigate this by, when generating the track layout in the beginning of randomWalkFunction, introducing a small (specified by input) percent chance that any single probe will be omitted. Error rates at around 10% are bearable; error rates greater than that, however, are catastrophic, causing walkers to become permanently trapped in small sections of the track field.

Node graphs showing walker mobility of origami. Each junction represents a track, and each edge represents a step a walker can take. The left diagram shows no error, whereas the other two show increasing error rates. We observe that 10% error rates decrease walker mobility, but tend not to trap the walker in any particular location; 20% error rates or greater, over several tests, tend to cause catastrophic loss of mobility, making the sorting task impossible.
Node graphs showing walker mobility of origami. Each junction represents a track, and each edge represents a step a walker can take. The left diagram shows no error, whereas the other two show increasing error rates. We observe that 10% error rates decrease walker mobility, but tend not to trap the walker in any particular location; 20% error rates or greater, over several tests, tend to cause catastrophic loss of mobility, making the sorting task impossible.

Random-Walk Simulation

The data we need from this simulator is a rough projection of the fluorescence response from our test of 2D random walking, which should change based on the starting location of the walker.
A plot of the number of steps (on an average over 5000 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at one end. This test was done assuming a 0% error rate, on the 3-track-wide linear random walking playground that we are using to investigate random walking (in a pseudolinear environment).
A plot of the number of steps (on an average over 5000 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at one end. This test was done assuming a 0% error rate, on the 3-track-wide linear random walking playground that we are using to investigate random walking (in a pseudolinear environment).
Because this fluorescence is changed by a fluorophore-quencher interaction upon a walker reaching its irreversible track, in the case where we plant all of the walkers on the same starting track, the time it takes (fluorescenceinitialfluorescencecurrent) in the sample to reach some standard value should be proportional to the average time it takes the walkers to reach the irreversible substrate. As this 'total steps elapsed' value is one of the outputs of our simulation function, we can generate a map of these average walk durations by running a large number of simulations at each point on the origami and averaging the results: Toggle Code

Results

Results of the bulk data collection at right show that the average random-walk duration, and thus the time for (fluorescenceinitialfluorescencecurrent) to reach some standard level, increases with distance, though it changes less significantly the farther out one gets. We can also use a similar simulation (run instead with tracks that don't continue past the start location of the walker, an arrangement which we have found to behave more like a linear track) data to generate approximate half-completion times, which we can compare with the SPEX results of the same random walk to both estimate the amount of time it takes the walker to perform a single branch migration on our origami, and to see if whatever our walker is doing on origami is looking like a random walk, as compared to a repeated jumping across or between origami platforms (whose half-completion times for this test would presumably not depend on the track length at all). That data is detailed on the SPEX results page.

Cargo Sorting Simulation

This simulation investigates both the overall tractability of our sorting problem, and the degree to which it can be parallelized via the addition of multiple walkers onto a single origami.
A plot of the number of steps (on an average over 250 iterations) it takes n walkers to sort all five cargos to respective goals on a perfectly formed 16x8 track, as detailed above. The jaggedness in the curve is a result of the large spread of results for any given test.
A plot of the number of steps (on an average over 250 iterations) it takes n walkers to sort all five cargos to respective goals on a perfectly formed 16x8 track, as detailed above. The jaggedness in the curve is a result of the large spread of results for any given test.
It runs by making repeated calls to randomWalkFunction in its cargo-bearing mode, testing the number of steps it takes to sort all five cargos to respective goals over a range of number of cooperating walkers: Toggle Code

(Note: this code is now obsolete (as it relies on an obsolete version of the randomWalkFunction script), and may be rewritten in the future. This should not, however, impact the validity of this code's results.

Results

While a single walker takes over a thousand steps to complete the sorting challenge, the addition of even a single walker vastly decreases the completion time, and additional walkers decrease it further, until a critical point is reached where the walkers are more getting in the way than helping with the sorting process. This is visible in the positive slope visible in the diagram at right that starts at around the 20 walker point.


Personal tools