superfast micromouse robot

[Admin]

wow, the control system on this thing is crazy . . . its as if the robot has zero mass . . .

26th All Japan Micromouse Contest
http://www.youtube.com/watch?v=N2fp6apH5Rw

[JesseWelling]

 

That man has the 1337 h4x0r skilz.........

I wonder if he is taking apprentices....

[Somchaya]

Wow!!! I did micromouse in high school and I've never seen such a fast, small AND amazing micromouse.. I'm absolutely amazed by its performance...

[annoyin_kid]

 
i never seen a micromouse contest but wow man that is fast!!!!!!!!!!! i thought the search run was quite fast but the speed run was amazing.

[snow]

What kind of motors can offer you such speed torque and accuracy (in search run fast 90 deg turns)?

Modified servo and some program tuning?

[ed1380]

Did that thing search its way through or was it programed turn by turn? That was crazy fast.

[Admin]

Ok I figured it out . . . took me long enough . . .

Actually, he is using the most elementary of pathplanning algorithms.

(hint: the maze size, number of cells, and start/goal locations are preprogrammed)

Huge props for the first person who can name that algorithm.

One day Ill write a tutorial on this . . .

What impressed me much more is the finely tweaked control. Im guessing he is using high quality RC racing DC motors with high resolution encoders.

[trigger]

Huge props for the first person who can name that algorithm.

Hmm...I'm guessing Dijkstra's algorithm?

What is it really?

[JesseWelling]

Dijkstra's as A*

But for mobile robotics the better alogritm is D* 
It does less calculations than running A* over and over from the current position.

[Admin]

another hint: factor in computational ability for a robot of that size

D* (pronounced D-star) can solve the problem, but there is another less computationally intensive solution . . . one that a robot of that size can handle . . .

Jesse, I know you know this!

[snow]

I did some searching on the web and i suppose he uses flooding algorithm.

[JesseWelling]

what depth first search?
I don't know I know it.
And just for your refference....He could be using a Strong Arm Processor 

[Admin]

I did some searching on the web and i suppose he uses flooding algorithm

yeap!

other correct answers would be 'brush fire' or 'wave front'

its all the same algorithm, but people for some odd reason have different names for it . . . i perfer to use 'wave front' . . .

if you notice carefully in the first run in the video, the robot often has these short pauses when it sees a wall. this is because the algorithm recalculates each time it adds a wall to its internal map. during the second run, it already knows the map, so doesnt need to stop to recalculate or find new paths.

At some point Ill write about it . . . here is a quickie explanation on wavefront with a single wall:
http://generalrobotics.org/labs/lab05/

[JesseWelling]

aha....yea that's pretty simple.
I actualy just had a coding interview with Amazon.com and I used it for the problem.

Here is was thier question:

An n by m grid has some cells filled in and others blank, in no particular pattern. Write a method to find the size of the largest block of filled cells in the grid.  A block is a group of contiguous cells that share an adjacent edge.  Cells in a block have north-south or east-west adjacency; diagonal adjacency does not count.

Here is my solution in Java:

Code: [Select]

import java.awt.Point;
import java.util.HashSet;
import java.util.SortedSet;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class BlockProblem {

private boolean [][] map; //true is full, false is empty
private PriorityQueue<Block> solidblocks;
private int n; //analgous to x
private int m; //analgous to y
private boolean blocksarefound;

public BlockProblem()
{
n = 50;
m = 50;
map = new boolean[n][m];
solidblocks = new PriorityQueue<Block>();
blocksarefound=false;
}

public BlockProblem(int newN, int newM)
{
n = newN;
m = newM;
map = new boolean [n][m];
solidblocks = new PriorityQueue<Block>();
blocksarefound=false;
}

public BlockProblem(boolean newmap[][], int newN, int newM)
{
n = newN;
m = newM;
map = newmap.clone();
solidblocks = new PriorityQueue<Block>();
findBlocks();
}

public void setCell(int x, int y, boolean value)
{
blocksarefound=false;
map[x][y]= value;
}

public void findBlocks()
{
HashSet<Point> visitedcells= new HashSet<Point>(n*m);
Point tempPoint = new Point(0,0);

for (int x=0; x<n; x++)//the x
{
for (int y=0; y<m; y++)//the y
{
tempPoint.setLocation(x, y);
if(!visitedcells.contains(tempPoint))
{
if (map[tempPoint.x][tempPoint.y])
solidblocks.add(new Block (map, n, m, visitedcells, tempPoint));
else
visitedcells.add(tempPoint);
}
}
}
blocksarefound=true;
}

public Block biggest()
{
if (!blocksarefound)
{
findBlocks();
}

return solidblocks.peek();
}

public String toString()
{
String outputString= "The Block Problem \n";

//the order in which we put out here is swaped
//so it coorisponds with a more traditional sense
//of x and y....cartesian like.
for (int y= m-1; y >=0; y--)//the y
{
for (int x=0; x<n; x++)//the x
{
if (map[x][y])
outputString += "X";
else
outputString += "O";
}
outputString += "\n";
}

outputString += "\nThe Blocks are\n";
for (Block b : solidblocks)
{
outputString += b;
outputString += "\n";
}
outputString += "The largest Block is \n";
outputString += solidblocks.peek();
return outputString;
}
}


Code: [Select]

import java.util.LinkedList;
import java.util.Queue;
import java.awt.Point;
import java.util.HashSet;

public class Block implements Comparable
{
private LinkedList<Point> members;
private int size;

public Block()
{
members = new LinkedList<Point>();
size = 0;
}

public Block(boolean [][]map, int n, int m, HashSet<Point> visited, Point start)
{
members = new LinkedList<Point>();
size = floodFillIterative(map, n, m, visited, start);
}

public int floodFillIterative(boolean [][]map, int n, int m, HashSet<Point> visited, Point start)
{
System.out.println("starting on "+start);
int count=0;
Queue<Point> toCheck;
toCheck = new LinkedList<Point>();
Point current = new Point(start);

//push the current Point onto the queue
toCheck.offer(current);

while (toCheck.size()!= 0)
{

current = toCheck.poll();
System.out.println("\tpopped "+ current);
//have we been here? (base case for the recursion)
if (visited.contains(current))
{
//yes so this doesn't count
System.out.println("\tHas already been visited");
continue;
}
else
{
//we have not been here so we add it to the visited hash set
visited.add(current);


//add it to the list of memebers in this block
count++;
members.add(current);

//add cell to the north to the queue if possible
if ((current.y+1) < m)
{
if (map[current.x][current.y+1])
{
toCheck.offer(new Point(current.x, current.y+1));
System.out.println("\tpushed "+current.x+" "+(current.y+1));
}
}

//add cell to the south to the queue if possible
if ((current.y-1) >= 0)
{
if (map[current.x][current.y-1])
{
toCheck.offer(new Point(current.x, current.y-1));
System.out.println("\tpushed "+current.x+" "+(current.y-1));
}
}

//add cell to the east to the queue if possible
if ((current.x+1) < n)
{
if (map[current.x+1][current.y])
{
toCheck.offer(new Point(current.x+1, current.y));
System.out.println("\tpushed "+(current.x+1)+" "+current.y);
}
}

//add cell to the west to the queue if possible
if ((current.x-1) >= 0)
{
if (map[current.x-1][current.y])
{
toCheck.offer(new Point(current.x-1, current.y));
System.out.println("\tpushed "+(current.x-1)+" "+current.y);
}
}
}
System.out.println();
}
System.out.println();
return count;
}

public int getSize()
{
return size;
}

public LinkedList<Point> getMembers()
{
return members;
}

public int compareTo(Object other)
{
Block otherBlock = (Block) other;
if(this.size<otherBlock.size)return 1;
        if(this.size==otherBlock.size)return 0;
return -1;
}

public String toString()
{
String outputString="Size of Block is";
outputString += " "+size;
outputString += "\nmembers:\n";

for (Point p: members)
{
outputString += p;
outputString += "\n";
}

return outputString;
}
}

If any one is realy interested in it I can give you the driver class and some test files.
So breadth first search is the Idea for wave front. You could also do this recursively
if you wanted to waste stack space.

[Admin]

sounds similar to blob detection for computer vision . . .

[JesseWelling]

I would guess so....All would be 'flood fill' or 'breadth first search' just with differing goals.