go_away

Author Topic: a line maze  (Read 2605 times)

0 Members and 1 Guest are viewing this topic.

Offline karthikvenkatTopic starter

  • Beginner
  • *
  • Posts: 2
  • Helpful? 0
a line maze
« on: March 10, 2008, 09:41:35 AM »
Hi...can any1 help me out with the algorithm for a line following maze(black line on white bg) ? reaching the center isnt a problem , but the robot has to come back to start from the center without encountering any dead ends.

Offline cooldog

  • Supreme Robot
  • *****
  • Posts: 751
  • Helpful? 4
  • be nice to nerds, one day they will be your boss
Re: a line maze
« Reply #1 on: March 10, 2008, 10:28:38 AM »
you could use some form of SLAM. have a line follower with encoders to map the way to the center then have it follow the map back to the start. tricky part is to make it eliminatethe dead ends in the maze.

read this
http://www.societyofrobots.com/robot_iRobot_Create_mod.shtml

and this might be a good chasi for you
http://www.societyofrobots.com/robot_mobot_2007.shtml
robot will rule the world and i will be building them
-admin

favorite web sites
http://www.societyofrobots.com/
http://www.instructables.com/

Offline karthikvenkatTopic starter

  • Beginner
  • *
  • Posts: 2
  • Helpful? 0
Re: a line maze
« Reply #2 on: March 10, 2008, 11:10:47 AM »
well , actually we are doing this with 4 IR sensors (l,r,f and b) and using right/left hand rule to reach the center...our prob is recording the correct path to be taken when coming back...can this be done in a simple manner using an array  ??

Offline cooldog

  • Supreme Robot
  • *****
  • Posts: 751
  • Helpful? 4
  • be nice to nerds, one day they will be your boss
Re: a line maze
« Reply #3 on: March 10, 2008, 11:15:06 AM »
like i said priviosly use a wavefront algorithum to map the area
robot will rule the world and i will be building them
-admin

favorite web sites
http://www.societyofrobots.com/
http://www.instructables.com/

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,658
  • Helpful? 169
    • Society of Robots
Re: a line maze
« Reply #4 on: March 15, 2008, 04:07:31 PM »
I agree with cooldog (gasp!) hehe . . .

The wavefront would be the best method.

Basically start with an empty grid, and use high precision encoders while follow the line. Record where the line is in the grid, while all other grid squares are treated as obstacles. Its a bit tricky so requires some thought . . .

Offline Ro-Bot-X

  • Contest Winner
  • Supreme Robot
  • ****
  • Posts: 1,431
  • Helpful? 25
  • Store: RoBotXDesigns.ca
Re: a line maze
« Reply #5 on: March 16, 2008, 06:41:07 AM »
well , actually we are doing this with 4 IR sensors (l,r,f and b) and using right/left hand rule to reach the center...our prob is recording the correct path to be taken when coming back...can this be done in a simple manner using an array  ??

Yes, it can be done simply by using an array of "n" nodes (having the value 0 at start), each node being a change in direction. Each time you need to change direction, you write the node with a value like 1 for left, 2 for forward, 3 for right. If you follow a left hand rule, at an intersection you will allways turn left. So, if the left turn takes you to a dead end, you turn back to the node and add an other left turn value to the one that it is allready there. For example, if you the intersection is a +, you first turn left (write 1 in the node), reach a dead end, turn back to the node, turn left again (add a 1 to the existing value, making that a 2). If say the intersection looks like a T and when you come back from the dead end you can't turn left just go forward, you add a 2 to the value in that node (that makes a 3). Now lets say that you explore all directions from a node and get dead ends and you are headed to the previous node. In this case you will get a value of 4 for the curent node, which is illegal, so you make it 0. Then you continue exploring the directions left unexplored from the previous node.

After you found the center of the maze, you turn around to the last node and substract the value from 4 and turn that direction. For example, at the last node you turned right (the value was 3), when you go back you substract 3 from 4 and get the result a 1, so you turn left instead of right and so on untill you reach the first node, then you know you are about to exit the maze without even looking for other dead ends...

Using this method it is verry important to accurately detect the type of intersection. Mounting the sensors in a "+" pattern simplyfies the process of detecting that. Also being able to accurately turn 90 degrees and correct the errors while driving the straight segments is of a great importance.
Check out the uBotino robot controller!

 


Get Your Ad Here