Friday, April 29, 2016
Home
Members
Project
Protocols
Progress
Discussion
References



Simulations
Overview
Our proposed sorting mechanism depends very heavily on a particular randomwalking 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 onedimensional track is easy to construct, and will behave like a standard 1D random walk, showing an average translation on the order of 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 onedimensional 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 onecargo, onegoal 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 bottomleft is <1, 1>, the topleft <1, n>, and the bottomright <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 topleft being <1,1> and bottomright 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 bottomleft 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 cargobearing (onecargo onegoal) and a purely randomwalk mode. The former has cargo positions corresponding to our particular origami preprogrammed 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 cargobearing and randomwalk data collection programs that call the function many times over a range of parameters.
The function code (saved as randomWalkFunction.m):
Toggle Code
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
% 2011062830: 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*walker1: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 cargodroppedcount, 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 outofbounds 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
Examining Errors in Origami
This code can be used to generate diagrams like those below, visualizing the mobility of the walker. One immediate question thus far unanswered 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 track 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.
RandomWalk 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 fluorophorequencher 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 (fluorescence_{initial} − fluorescence_{current}) 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
%%% 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 errorallowing 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 2000 iterations) it takes a walker to random walk from any point on the origami to the irreversible track at <15, 7>. The holes are due to omitted, cargo, or goal strands blocking the walker's starting location.
Results
Results of the bulk data collection at right show that the average randomwalk duration, and thus the time for (fluorescence_{initial} − fluorescence_{current}) 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 straightline movement  it requires a backandforth 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.
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. It runs by making repeated calls to randomWalkFunction in its cargobearing 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
%%% 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) %Builtin 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)
Results
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.
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.
