Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Simulation

From OpenWetWare

(Difference between revisions)
Jump to: navigation, search
(Discussing MATLAB code)
(Added 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.
+
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.
-
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 to test traits including expected random-walk duration and cargo collection rate:
+
The function code (saved as randomWalkFunction.m):
-
<code>
+
<code><pre>
-
</code>
+
function [cargoLog, steps] = randomWalkFunction(x, y, length, numWalkers, ...
 +
    startPos, endPos, cargoBearing, restricted)
 +
%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
 +
 
 +
%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
 +
 
 +
%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
 +
      currentPos(i, :) = [randi(x, 1), randi(y, 1)];
 +
    end
 +
    % If doing a cargobearing walk, set these to cargo positions too:
 +
    cargoPos = [[3, 5]; [9, 5]; [15, 5]; [7, 2]; [11, 2]];
 +
else
 +
    currentPos = startPos;
 +
    numWalkers = 1; %Want to make sure this is one for this case
 +
end
 +
 
 +
 
 +
 
 +
%Initialize some things:
 +
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 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)%1 = 0:
 +
        %  (+1, 0), (-1, -1)
 +
        % ELSE:
 +
        %  (-1, 0), (+1, +1)
 +
 
 +
        temp = randi(4, 1);
 +
        if (mod(currentPos(walker, 1),2) == 0)
 +
            newPos = currentPos(walker, :) + cargoAPoss(temp, :);
 +
        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, :);
 +
            cargoLog = [cargoLog; steps, 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:
 +
        if cargoBearing
 +
            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
 +
        end
 +
       
 +
        % Already on irrev. cargo case:
 +
        if (currentPos(walker, :) == endPos)
 +
            return
 +
        end
 +
       
 +
        %Hitting other walkers case:
 +
        if numWalkers > 1
 +
            m = (find(currentPos(:, 1) == newPos(1)));
 +
            for n=m
 +
                if (currentPos(n, 2) == newPos(2))
 +
                    %Derp, don't go there
 +
                    newPos = currentPos(walker, :);
 +
                    collisionLog = [collisionLog; newPos, walker];
 +
                end
 +
            end
 +
        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
 +
</pre></code>
==Random-Walk Simulation==
==Random-Walk Simulation==

Revision as of 21:04, 22 June 2011

Image:DeoxyriboNucleicAwesomeHeader.jpg

Wednesday, April 16, 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 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 [cargoLog, steps] = randomWalkFunction(x, y, length, numWalkers, ...
    startPos, endPos, cargoBearing, restricted)
%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

%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

%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
       currentPos(i, :) = [randi(x, 1), randi(y, 1)];
    end
     % If doing a cargobearing walk, set these to cargo positions too:
    cargoPos = [[3, 5]; [9, 5]; [15, 5]; [7, 2]; [11, 2]];
else
    currentPos = startPos;
    numWalkers = 1; %Want to make sure this is one for this case
end



%Initialize some things:
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 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)%1 = 0:
        %   (+1, 0), (-1, -1)
        % ELSE:
        %   (-1, 0), (+1, +1)

        temp = randi(4, 1);
        if (mod(currentPos(walker, 1),2) == 0)
            newPos = currentPos(walker, :) + cargoAPoss(temp, :); 
        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, :);
            cargoLog = [cargoLog; steps, 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:
        if cargoBearing
            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
        end
        
        % Already on irrev. cargo case:
        if (currentPos(walker, :) == endPos)
            return
        end
        
        %Hitting other walkers case:
        if numWalkers > 1
            m = (find(currentPos(:, 1) == newPos(1)));
            for n=m
                if (currentPos(n, 2) == newPos(2))
                    %Derp, don't go there
                    newPos = currentPos(walker, :);
                    collisionLog = [collisionLog; newPos, walker];
                end
            end
        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

Random-Walk Simulation

Personal tools