Author Topic: superfast micromouse robot  (Read 11590 times)

0 Members and 1 Guest are viewing this topic.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots
superfast micromouse robot
« on: February 02, 2007, 08:24:08 AM »
wow, the control system on this thing is crazy . . . its as if the robot has zero mass . . .

26th All Japan Micromouse Contest

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: superfast micromouse robot
« Reply #1 on: February 02, 2007, 03:40:12 PM »
 :o

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

I wonder if he is taking apprentices....

Offline Somchaya

  • Robot Overlord
  • ****
  • Posts: 180
  • Helpful? 0
  • You know it's cute!
Re: superfast micromouse robot
« Reply #2 on: February 02, 2007, 09:40:56 PM »
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...
Somchaya - Back after a year of misc things
http://whisker.scribblewiki.com

Offline annoyin_kid

  • Full Member
  • ***
  • Posts: 91
  • Helpful? 0
Re: superfast micromouse robot
« Reply #3 on: February 03, 2007, 04:18:59 PM »
 :o :o :o :o :o
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.

Offline snow

  • Full Member
  • ***
  • Posts: 73
  • Helpful? 0
Re: superfast micromouse robot
« Reply #4 on: February 12, 2007, 03:55:36 AM »
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?


Offline ed1380

  • Supreme Robot
  • *****
  • Posts: 1,478
  • Helpful? 3
Re: superfast micromouse robot
« Reply #5 on: February 12, 2007, 03:21:26 PM »
Did that thing search its way through or was it programed turn by turn? That was crazy fast.
Problems making the $50 robot circuit board?
click here. http://www.societyofrobots.com/robotforum/index.php?topic=3292.msg25198#msg25198

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots
Re: superfast micromouse robot
« Reply #6 on: February 12, 2007, 03:40:26 PM »
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.

Offline trigger

  • Full Member
  • ***
  • Posts: 115
  • Helpful? 0
  • It's an op amp, not a gun part.
Re: superfast micromouse robot
« Reply #7 on: February 12, 2007, 03:59:43 PM »
Huge props for the first person who can name that algorithm.

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

What is it really?
There are 10 kinds of people in this world: those who can read binary, and those who can't.

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: superfast micromouse robot
« Reply #8 on: February 12, 2007, 07:31:42 PM »
Dijkstra's as A*

But for mobile robotics the better alogritm is D*  :P
It does less calculations than running A* over and over from the current position.
« Last Edit: February 12, 2007, 07:32:54 PM by JesseWelling »

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots
Re: superfast micromouse robot
« Reply #9 on: February 12, 2007, 08:08:09 PM »
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! :P

Offline snow

  • Full Member
  • ***
  • Posts: 73
  • Helpful? 0
Re: superfast micromouse robot
« Reply #10 on: February 13, 2007, 02:43:17 AM »
I did some searching on the web and i suppose he uses flooding algorithm.

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: superfast micromouse robot
« Reply #11 on: February 13, 2007, 02:00:55 PM »
what depth first search? ???
I don't know I know it.
And just for your refference....He could be using a Strong Arm Processor  :P

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots
Re: superfast micromouse robot
« Reply #12 on: February 13, 2007, 10:21:15 PM »
Quote
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/

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: superfast micromouse robot
« Reply #13 on: February 14, 2007, 12:15:51 AM »
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:
Quote
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.
« Last Edit: February 14, 2007, 12:17:35 AM by JesseWelling »

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots
Re: superfast micromouse robot
« Reply #14 on: February 14, 2007, 07:42:46 AM »
sounds similar to blob detection for computer vision . . .

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: superfast micromouse robot
« Reply #15 on: February 14, 2007, 02:50:56 PM »
I would guess so....All would be 'flood fill' or 'breadth first search' just with differing goals.

 


Get Your Ad Here

data_list