Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Simulation

From OpenWetWare

(Difference between revisions)
Jump to: navigation, search
(Finishing up random walk section with some results of simulation)
(Adding revised code)
Line 17: Line 17:
==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, 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.
The function code (saved as randomWalkFunction.m):
The function code (saved as randomWalkFunction.m):
<code><pre>
<code><pre>
-
function [cargoLog, steps] = randomWalkFunction(x, y, length, numWalkers, ...
+
function [log, cargoLog, steps] = randomWalkFunction(x, y, length, ...
-
     startPos, endPos, cargoBearing, restricted)
+
     numWalkers, startPos, endPos, cargoBearing, restricted, error)
 +
 
%x: Width        y: Height
%x: Width        y: Height
%length: max # of steps to run simulation
%length: max # of steps to run simulation
Line 30: Line 31:
%cargoBearing = running cargoBearing (1) vs randomWalking (0)
%cargoBearing = running cargoBearing (1) vs randomWalking (0)
%restricted = whether we're paying attention to borders
%restricted = whether we're paying attention to borders
 +
%error = the chance of the failure of any single track
%Random walking cargo pickup/dropoff simulation
%Random walking cargo pickup/dropoff simulation
Line 42: Line 44:
% 20110616: Modified to be a random walk function, to be
% 20110616: Modified to be a random walk function, to be
%          called in a data accumulator program
%          called in a data accumulator program
 +
% 20110628-30: Modified to take into account omitted positions
 +
%          , new probe layout, and automatic halting when
 +
%          starting on impossible positions.
 +
% 20110706: Fixed walker collision. It detects collisions properly
 +
%          now.
 +
% 20110707: Adding support for errors -- cycles through and
 +
%          omits each track position at an input error rate
 +
 +
%Initialize some things:
 +
%Cargo positions:
 +
cargoPos = [[3, 5]; [9, 5]; [15, 5]; [7, 7]; [11, 7]];
 +
filledGoals = [];
 +
omitPos = [[3, 6]; [7, 8]; [8, 5]; [11, 8]; [15, 6]];
 +
 +
steps = 0;
 +
hasCargo = zeros(numWalkers);
 +
sorted = 0;
 +
trackAPoss = [0, 1; 0, -1; 1, 0; -1, -1];  %Movement rules, even column
 +
trackBPoss = [0, 1; 0, -1; -1, 0; 1, 1]; %'', odd column
 +
log = zeros(length, 2*numWalkers + 1);
 +
cargoLog = [];
 +
collisionLog = [];
%Walkers:
%Walkers:
Line 49: Line 73:
     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(x, 1), randi(y, 1)];
 +
            done = checkPossible(numWalkers, currentPos, omitPos, ...
 +
                                    cargoPos);
 +
      end
     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 checkPossible(numWalkers, currentPos, omitPos, ...
 +
                                    cargoPos) ~= 1
 +
          'Invalid start position.';
 +
          cargoLog = [];
 +
          steps = -1;
 +
          return
 +
    end
end
end
 +
%Error: If there's a valid error rate, go omit some positions:
 +
if error > 0
 +
    for xPos=1:x
 +
        for yPos=1:y
 +
            %Only omit if it's not already blocked by something
 +
            if checkPossible(0, [xPos, yPos], omitPos, cargoPos)
 +
                if rand <= error
 +
                    omitPos = [omitPos; [xPos, yPos]];
 +
                end
 +
            end
 +
        end
 +
    end
 +
end
 +
%Convenience:
 +
numOmitPos = size(omitPos, 1);
 +
numCargoPos = size(cargoPos, 1);
-
%Initialize some things:
+
%Main loop:
-
steps = 0;
+
-
hasCargo = zeros(numWalkers);
+
-
sorted = 0;
+
-
cargoAPoss = [0, 1; 0, -1; 1, 0; -1, -1];  %Movement rules
+
-
cargoBPoss = [0, 1; 0, -1; -1, 0; 1, 1]; %''
+
-
log = zeros(length, 2*numWalkers + 1);
+
-
cargoLog = [];
+
-
collisionLog = [];
+
-
 
+
for i=1:length,
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, :);
Line 79: Line 121:
         %these are the only valid neighbors:
         %these are the only valid neighbors:
         %  (0, +1), (0, -1)
         %  (0, +1), (0, -1)
-
         % IF (x/2)%1 = 0:
+
         % IF x%2 = 0:
         %  (+1, 0), (-1, -1)
         %  (+1, 0), (-1, -1)
         % ELSE:
         % ELSE:
Line 86: Line 128:
         temp = randi(4, 1);
         temp = randi(4, 1);
         if (mod(currentPos(walker, 1),2) == 0)
         if (mod(currentPos(walker, 1),2) == 0)
-
             newPos = currentPos(walker, :) + cargoAPoss(temp, :);  
+
             newPos = currentPos(walker, :) + trackAPoss(temp, :);  
         else
         else
-
             newPos = currentPos(walker, :) + cargoBPoss(temp, :);  
+
             newPos = currentPos(walker, :) + trackBPoss(temp, :);  
         end
         end
-
         %If we just went out of bounds in the -y direction (toward
+
         %If we tried to move onto the bottom two spots (in terms of y)
-
         % a goal) and had cargos, we drop off
+
         %on an even column (i.e. a goal), we drop off cargo if we had it
-
         if cargoBearing && (hasCargo(walker) == 1 && (newPos(2) < 1))
+
        %and there wasn't one there already.
-
             %Drop cargo, increment cargo-dropped-count
+
        %% Specific: 8th column has no goals! It has track instead.
-
            hasCargo(walker) = 0;
+
         if newPos(2) <= 2 && mod(newPos(1),2) == 0 && newPos(1) ~= 8
-
            sorted = sorted + 1;
+
             if cargoBearing && hasCargo(walker) == 1
 +
                %Drop cargo, increment cargo-dropped-count, but
 +
                %only if there isn't already a cargo here
 +
                temp = size(filledGoals);
 +
                match = 0;
 +
                for k=1:temp(1)
 +
                    if filledGoals(k, :) == newPos
 +
                        match = 1;
 +
                        break
 +
                    end
 +
                end
 +
                if match ~= 1
 +
                    hasCargo(walker) = 0;
 +
                    cargoLog = [cargoLog; steps, walker];
 +
                    sorted = sorted + 1;
 +
                    filledGoals = [filledGoals; newPos];
 +
                end
 +
            end
             %Don't move
             %Don't move
             newPos = currentPos(walker, :);
             newPos = currentPos(walker, :);
-
            cargoLog = [cargoLog; steps, walker];
 
         end
         end
Line 110: Line 168:
         %Hitting cargos case:
         %Hitting cargos case:
-
         if cargoBearing
+
         for k=1:numCargoPos
-
            m = (find(cargoPos(:, 1) == newPos(1)));
+
             if cargoPos(k, :) == newPos
-
             for n=m
+
                %Remove the cargo from the list of cargos and "pick up"  
-
                if cargoPos(m, 2) == newPos(2)
+
                % if you don't already have a cargo
-
                    %Remove the cargo from the list of cargos and "pick up" if
+
                if hasCargo(walker) == 0 && cargoBearing
-
                    %you don't already have a cargo
+
                    cargoPos(k, :) = [-50, -50];
-
                    if hasCargo(walker) == 0
+
                    hasCargo(walker) = 1;
-
                        cargoPos(m, :) = [-50, -50];
+
                    cargoLog = [cargoLog; steps, walker];
-
                        hasCargo(walker) = 1;
+
-
                        cargoLog = [cargoLog; steps, walker];
+
-
                    %Anyway, don't move there
+
-
                    newPos = currentPos(walker, :);
+
-
                    end
+
                 end
                 end
 +
                %Anyway, don't move there
 +
                newPos = currentPos(walker, :);
             end
             end
         end
         end
-
       
+
 
         % Already on irrev. cargo case:
         % Already on irrev. cargo case:
         if (currentPos(walker, :) == endPos)
         if (currentPos(walker, :) == endPos)
Line 134: Line 189:
         %Hitting other walkers case:
         %Hitting other walkers case:
         if numWalkers > 1
         if numWalkers > 1
-
             m = (find(currentPos(:, 1) == newPos(1)));
+
             for k = 1:numWalkers
-
            for n=m
+
                 if all(newPos == currentPos(k, :)) && k ~= walker
-
                 if (currentPos(n, 2) == newPos(2))
+
-
                    %Derp, don't go there
+
                     newPos = currentPos(walker, :);
                     newPos = currentPos(walker, :);
-
                     collisionLog = [collisionLog; newPos, walker];
+
                     collisionLog = [collisionLog; newPos, walker, k];
                 end
                 end
             end
             end
 +
        end
 +
       
 +
        %Hitting the omitted positions case:
 +
        %If we have any position matches with "omitted" list
 +
        %, just don't go there.
 +
        match = 0;
 +
        for k=1:numOmitPos
 +
            if omitPos(k, :) == newPos
 +
                match = 1;
 +
            end
 +
        end
 +
        if match == 1
 +
            newPos = currentPos(walker, :);
         end
         end
          
          
Line 160: Line 226:
end
end
 +
return
 +
 +
 +
%%Checks if a position is a possible place for a walker to be:
 +
function [possible] = checkPossible(numWalkers, currentPos, ...
 +
                                    omitPos, cargoPos)
 +
    % If we're starting on an omitted position, or a goal, a cargo,
 +
    % or another walker, just give up immediately, and return a -1:
 +
    numOmitPos = size(omitPos, 1);
 +
    numCargoPos = size(cargoPos, 1);
 +
    possible = 1;
 +
    for walker = 1:numWalkers
 +
        thisWalkerPos = currentPos(walker, :);
 +
        % Only run this for this walker if it's placed somewhere
 +
        % valid (i.e. not waiting to be placed, x,y = 0,0)
 +
        if all(thisWalkerPos)
 +
            %Omitted positions:
 +
            for k=1:numOmitPos
 +
                if omitPos(k, :) == thisWalkerPos
 +
                    possible = 0;
 +
                    return
 +
                end
 +
            end
 +
            %Cargo positions:
 +
            for k=1:numCargoPos
 +
                if cargoPos(k, :) == thisWalkerPos
 +
                    possible = 0;
 +
                    return
 +
                end
 +
            end
 +
            %Other walkers:
 +
            for k=1:numWalkers
 +
                if (all(currentPos(k, :) == thisWalkerPos)) && ...
 +
                        (k ~= walker)
 +
                    possible = 0;
 +
                    return
 +
                end
 +
            end
 +
            %Goal positions:
 +
            if mod(thisWalkerPos(1), 2)==0 && thisWalkerPos(1) ~= 8 ...
 +
                    && thisWalkerPos(2) <= 2
 +
                possible = 0;
 +
                return
 +
            end
 +
        end
 +
    end
return
return
</pre></code>
</pre></code>
Line 172: Line 284:
% Gregory Izatt & Caltech BIOMOD 2011
% Gregory Izatt & Caltech BIOMOD 2011
% 20110616: Initial revision
% 20110616: Initial revision
-
% 20110623: Updating documentation a bit
+
% 20110624: Updating some documentation
 +
% 20110701: Updating to use new, updated randomWalkFunction
 +
% 20110707: Updated to use new error-allowing randomWalkFunction
%% Dependency: makes calls to randomWalkFunction.m
%% Dependency: makes calls to randomWalkFunction.m
Line 179: Line 293:
xMax = 16;  %Scale of platform for test
xMax = 16;  %Scale of platform for test
yMax = 8;  
yMax = 8;  
-
stopPos = [16, 8]; %Stop position
+
stopPos = [15, 7]; %Stop position
averages = zeros(xMax, yMax); %Init'ing this
averages = zeros(xMax, yMax); %Init'ing this
trash = []; %Trash storing variable
trash = []; %Trash storing variable
Line 189: Line 303:
         temp = zeros(iterations, 1);
         temp = zeros(iterations, 1);
         parfor i=1:iterations
         parfor i=1:iterations
-
             [trash, temp(i)] = randomWalkFunction(xMax, yMax, 1000000, ...
+
             [trash, trash2, temp(i)] = randomWalkFunction(xMax, yMax, ...
-
                 1, [x, y], stopPos, 0, 1);
+
                 10000, 1, [x, y], stopPos, 0, 1, 0.0);
         end
         end
         stdDev(x, y) = std(temp);
         stdDev(x, y) = std(temp);

Revision as of 17:44, 7 July 2011

Image:DeoxyriboNucleicAwesomeHeader.jpg

Friday, July 11, 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 <LINK TO THE EXPERIMENTAL DESIGN SECTION>, 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 take a step given four good opposite track locations (good locations to step to) around it.
  • 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>.
  • Movement rules are based on column:
    • In even 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>.
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.
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.

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, 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.

The function code (saved as randomWalkFunction.m):

function [log, cargoLog, steps] = randomWalkFunction(x, y, length, ...
    numWalkers, startPos, endPos, cargoBearing, restricted, error)

%x: Width         y: Height
%length: max # of steps to run simulation
%numWalkers = number of walkers to simulate in cargoBearing state
%startPos = starting position for walker in randomwalk state
%endPos = irreversible track location in randomwalk state
%cargoBearing = running cargoBearing (1) vs randomWalking (0)
%restricted = whether we're paying attention to borders
%error = the chance of the failure of any single track

%Random walking cargo pickup/dropoff simulation
%for origami tile, x (horizontal) by y (vertical) dim.
%Locations index by 1. x+ = right, y+ = up
% Gregory Izatt & Caltech BIOMOD 2011
% 20110615: Initial revision
% 20110615: Continuing development
%           Added simulation for cargo pickup/dropoff
%           Adding support for multiple walkers
% 20110616: Debugging motion rules, making display better
% 20110616: Modified to be a random walk function, to be
%           called in a data accumulator program
% 20110628-30: Modified to take into account omitted positions
%           , new probe layout, and automatic halting when
%           starting on impossible positions.
% 20110706: Fixed walker collision. It detects collisions properly
%           now.
% 20110707: Adding support for errors -- cycles through and 
%           omits each track position at an input error rate

%Initialize some things:
%Cargo positions:
cargoPos = [[3, 5]; [9, 5]; [15, 5]; [7, 7]; [11, 7]];
filledGoals = [];
omitPos = [[3, 6]; [7, 8]; [8, 5]; [11, 8]; [15, 6]];

steps = 0; 
hasCargo = zeros(numWalkers);
sorted = 0;
trackAPoss = [0, 1; 0, -1; 1, 0; -1, -1];  %Movement rules, even column
trackBPoss = [0, 1; 0, -1; -1, 0; 1, 1]; %'', odd column
log = zeros(length, 2*numWalkers + 1);
cargoLog = [];
collisionLog = [];

%Walkers:
% Set position randomly if we're doing cargo bearing simulation,
% or set to supplied startPos if not.
if cargoBearing
    currentPos = zeros(numWalkers, 2);
    for i=1:numWalkers
       done = 0;
       while done ~= 1
            currentPos(i, :) = [randi(x, 1), randi(y, 1)];
            done = checkPossible(numWalkers, currentPos, omitPos, ...
                                    cargoPos);
       end
    end
else
    numWalkers = 1; %Want to make sure this is one for this case
    currentPos = startPos;
    if checkPossible(numWalkers, currentPos, omitPos, ...
                                    cargoPos) ~= 1
          'Invalid start position.';
          cargoLog = [];
          steps = -1;
          return
    end
end

%Error: If there's a valid error rate, go omit some positions:
if error > 0
    for xPos=1:x
        for yPos=1:y
            %Only omit if it's not already blocked by something
            if checkPossible(0, [xPos, yPos], omitPos, cargoPos)
                if rand <= error
                    omitPos = [omitPos; [xPos, yPos]];
                end
            end
        end
    end
end

%Convenience:
numOmitPos = size(omitPos, 1);
numCargoPos = size(cargoPos, 1);

%Main loop:
for i=1:length,
    for walker=1:numWalkers
        
        %Add current pos to log
        log(steps + 1, 2*walker-1:2*walker) = currentPos(walker, :);
        
        %Update pos to randomly
        %chosen neighbor -- remember,
        %these are the only valid neighbors:
        %   (0, +1), (0, -1)
        % IF x%2 = 0:
        %   (+1, 0), (-1, -1)
        % ELSE:
        %   (-1, 0), (+1, +1)

        temp = randi(4, 1);
        if (mod(currentPos(walker, 1),2) == 0)
            newPos = currentPos(walker, :) + trackAPoss(temp, :); 
        else
            newPos = currentPos(walker, :) + trackBPoss(temp, :); 
        end

        %If we tried to move onto the bottom two spots (in terms of y)
        %on an even column (i.e. a goal), we drop off cargo if we had it
        %and there wasn't one there already.
        %% Specific: 8th column has no goals! It has track instead.
        if newPos(2) <= 2 && mod(newPos(1),2) == 0 && newPos(1) ~= 8
            if cargoBearing && hasCargo(walker) == 1
                %Drop cargo, increment cargo-dropped-count, but
                %only if there isn't already a cargo here
                temp = size(filledGoals);
                match = 0;
                for k=1:temp(1)
                    if filledGoals(k, :) == newPos
                        match = 1;
                        break
                    end
                end
                if match ~= 1
                    hasCargo(walker) = 0;
                    cargoLog = [cargoLog; steps, walker];
                    sorted = sorted + 1;
                    filledGoals = [filledGoals; newPos];
                end
            end
            %Don't move
            newPos = currentPos(walker, :);
        end

        %General out-of-bounds case without cargo drop:
        if restricted && ((newPos(1) > x || newPos(1) < 1 || ...
                newPos(2) > y || newPos(2) < 1))
            %Don't go anywhere
            newPos = currentPos(walker, :);
        end

        %Hitting cargos case:
        for k=1:numCargoPos
            if cargoPos(k, :) == newPos
                %Remove the cargo from the list of cargos and "pick up" 
                % if you don't already have a cargo
                if hasCargo(walker) == 0 && cargoBearing
                    cargoPos(k, :) = [-50, -50];
                    hasCargo(walker) = 1;
                    cargoLog = [cargoLog; steps, walker];
                end
                %Anyway, don't move there
                newPos = currentPos(walker, :);
            end
        end

        % Already on irrev. cargo case:
        if (currentPos(walker, :) == endPos)
            return
        end
        
        %Hitting other walkers case:
        if numWalkers > 1
            for k = 1:numWalkers
                if all(newPos == currentPos(k, :)) && k ~= walker
                    newPos = currentPos(walker, :);
                    collisionLog = [collisionLog; newPos, walker, k];
                end
            end
        end
        
        %Hitting the omitted positions case:
        %If we have any position matches with "omitted" list
        %, just don't go there.
        match = 0;
        for k=1:numOmitPos
            if omitPos(k, :) == newPos
                match = 1;
            end
        end
        if match == 1
            newPos = currentPos(walker, :);
        end
        
        %Finally actually update the position
        currentPos(walker, :) = newPos;
        
    end
    
    % Step forward, update log
    steps = steps + 1;
    log(steps, 2*numWalkers + 1) = steps - 1;
    
    if (sorted == 5)
        log(steps+1:end, :) = [];
        break
    end
    
end

return


%%Checks if a position is a possible place for a walker to be:
function [possible] = checkPossible(numWalkers, currentPos, ...
                                    omitPos, cargoPos)
    % If we're starting on an omitted position, or a goal, a cargo,
    % or another walker, just give up immediately, and return a -1:
    numOmitPos = size(omitPos, 1);
    numCargoPos = size(cargoPos, 1);
    possible = 1;
    for walker = 1:numWalkers
        thisWalkerPos = currentPos(walker, :);
        % Only run this for this walker if it's placed somewhere
        % valid (i.e. not waiting to be placed, x,y = 0,0)
        if all(thisWalkerPos)
            %Omitted positions:
            for k=1:numOmitPos
                if omitPos(k, :) == thisWalkerPos
                    possible = 0;
                    return
                end
            end
            %Cargo positions:
            for k=1:numCargoPos
                if cargoPos(k, :) == thisWalkerPos
                    possible = 0;
                    return
                end
            end
            %Other walkers:
            for k=1:numWalkers
                if (all(currentPos(k, :) == thisWalkerPos)) && ...
                        (k ~= walker)
                    possible = 0;
                    return
                end
            end
            %Goal positions:
            if mod(thisWalkerPos(1), 2)==0 && thisWalkerPos(1) ~= 8 ...
                    && thisWalkerPos(2) <= 2
                possible = 0;
                return
            end
        end
    end
return

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. 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:

%%% 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

%% Dependency: makes calls to randomWalkFunction.m

iterations = 2500; %Test each case of random walk this # times
xMax = 16;  %Scale of platform for test
yMax = 8; 
stopPos = [15, 7]; %Stop position
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(4)
for x=1:xMax
    for y=1:yMax
        temp = zeros(iterations, 1);
        parfor i=1:iterations
            [trash, trash2, temp(i)] = randomWalkFunction(xMax, yMax, ...
                10000, 1, [x, y], stopPos, 0, 1, 0.0);
        end
        stdDev(x, y) = std(temp);
        averages(x, y) = mean(temp)
    end
end
matlabpool close
A plot of the number of steps (on an average over 2500 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at <16, 8>.
A plot of the number of steps (on an average over 2500 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at <16, 8>.

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. Also important to note is that the "effective distance" (in terms of steps) along the short axis of our platform is a significantly less than the same physical distance along the long axis. This difference is due to our arrangement of track A and B: as can be seen in the left half of the diagram at the end of the #Overview section, alternating tracks A and B create a straight vertical highway for the walker to follow. Horizontal movement, in contrast, cannot be accomplished by purely straight-line movement -- it requires a back-and-forth weave that makes motion in that direction slower. The disparity in "effective distances" between the vertical and horizontal dimensions is something, in particular, that we should test for; however, a simple series of tests running random walks at a variety of points across the surface, and the comparison of the resulting fluorescence data to the control provided by this simulation should be sufficient to prove that our walker can, indeed, perform a 2D random walk.

Personal tools