Robots on grid
Mindy met with the professor and talked about new ideas.
We consider robots on the grid, which means the motion is only
horizontal and vertaical. We use a maze applet from
http://foghorn.cadlab.lafayette.edu/MazeRouter.html
as a template.
The task of robot motion in the grid is different from what we have had before.
We designed two strategies: XY Strategy and
Push Strategy.
XY Strategy
Robots have their inital and final positions, each robot moves first
horizontally along x-axis on the grid, then vertically along y-axis to
reach the final position.
XY stratgy works perfectly when the arrangement of robots does not
have overlap at all both in x direction and y direction. An example
is a diagonal line.
To look at a movement using XY Strategy, please go to
Applet 1
It can even handle 19 robots!
19 robots
However, when there is an overlap in either direction, robot will not
be able to reach its final position because when two robots encounter
collision, both of them stay in their position without moving forward.
An example is 4 robots line up horrizontally and tries to perform
permutaion. From 1->2->3->4 to 4->3->2->1
The following link shows the problem we encountered:
Applet 2
Pust Strategy
Therefore, we made Push Strategy. Just like the name, when two robots
encounter collision, one robot moves down one step and moving toward
to its destination while the other robot keeps moving toward to
destination without changing its route.
This strategy works great with collision on the grid, not only it
doesn't encounter a problem, it's also efficiency. We slowed down
speed to see what exactly happend to the robots.
Applet 3
In the end, we want to see what happens when there are many robots,
say 10 robots. And the strategy still works great, we can see couple
robots were pushed down twice.
The patter we noticed is that the robots at the head of the line get
push down the most while the last robot in the line never got to push
down.
We believe this strategy will work great with diagonal line as well.
Applet 4