# Advanced Line Following Robot of Maze Solving

I know how to make a line follower. But in this video what have they done exactly? They are giving the source and destination in the map but how the robot moves based on the instruction given in map?

What is the procedure to do it? They have mapped the path. Please do watch the video.

• Can you please clarify your question? I can't tell what exactly you need help with. – Chuck Oct 20 '15 at 11:40
• I know how to make a line follower. But in this video what have they done exactly? They are giving the source and destination in the map but how the robot moves based on the instruction given in map? – Karthik Oct 20 '15 at 11:43
• I believe I understand what he means as I've done this project before. I'll edit his question to make it clear when I'm home (in about 4 hours). Don't delete it yet. He means he wants to calculate which direction the robot has to go if only the route is calculated. – Paul Oct 20 '15 at 13:04
• Can't get you sir, Fine if you have done this project just explain me the procedures in answer sir please. – Karthik Oct 20 '15 at 13:12

See this similar question and my answer to it. The question I linked asks for how to handle an unknown starting position, but it seems similar in that you and the other OP are both asking "how do I go from Dijkstra's algorithm to implementation?"

Essentially, Dijkstra's algorithm only requires to you give a digraph with a set of distances or "costs" between the two points. Dijkstra's algorithm gives you the series of waypoints that will get you/your vehicle from any one arbitrary point to another arbitrary point at the lowest cost, based on the cost information you provided. If you don't give it correct cost information it won't give you the optimal route; this is akin (actually) a map routing program that might send you on a back road because it only looked at distance and not distance at a given speed limit, or through a downtown area in rush hour because it doesn't account for traffic.

So it is up to you to calculate the distances between points and to know the physical relationship between two points. (read:heading)

So, for example, if you store all of the coordinates for the points in addition to the digraph and distances, you could try:

currentWaypoint = [x0,y0];
nextWaypoint = [x1,y1];

nextHeadingAbsolute = atan2( (y1-y0) , (x1-x0) );

driveDistance = sqrt( (x1-x0)^2 + (y1-y0)^2 );

driveRobot(drivieDistance);


This snippet/example assumes that you measure heading as 0 radians as the +x-axis, with angle increasing in a counter-clockwise direction. You can make any other axis be the zero by adding an offset, and can convert to degrees if you desire.

Basically you just find the angle between the coordinates relative to the global x/y axes, then subtract your current heading from that. Drive distance would then be along the hypotenuse, which you can calculate using the Pythagorean Theorem.

• No sir, I don't want about Dijkstra. I know about that algorithm. What is that I need is have they mapped the path? If so how did they map? And how do they pass information for automation based on the map? – Karthik Oct 20 '15 at 14:58
• @Karthik - As I mentioned in my answer, the easiest way would be to have the coordinates for all of the points. You tell the Dijkstra algorithm where to start and end and the algorithm then tells every step along the way. Get the coordinates for the step you are on and the next step along the path and use the code snippet I wrote to get the angle to turn and the distance to drive. – Chuck Oct 20 '15 at 15:09
• Sir, I have updates my need in the previous. Need answer for that. These answers seems to get no value for the questions. – Karthik Oct 20 '15 at 15:14
• @Karthik - Please update your question then; I don't know what you need help with. I thought you wanted to know how to determine to turn and how far to drive. – Chuck Oct 20 '15 at 15:56
• Yes, here I have edited sir. Can you see the video sir? How they transfer the instruction with help of mapped image? – Karthik Oct 20 '15 at 16:00

It looks like there are 3 main components to the demonstration in this video.

### 1. Creating the map

Navigation requires a map of the robot's environment -- it looks like this was done manually. It doesn't matter whether you create the digital map based on the real-world map, or a real-world map based on a contrived digital map. But the maps must match.

### 2. Computing the path

As mentioned in Chuck's answer, Dijkstra's algorithm can compute a path through a map -- one of many methods of doing so, but probably the most appropriate for this problem. However, you need a bit more than Dijkstra here; the final path is not just the list of nodes you will travel through, but what direction you need to turn at each node (i.e. how many lines the line sensor will need to cross over) in order to be on the line leading to the next node in the path.

I would imagine that the instructions set to the robot are just a simple list of how many paths to rotate over at each intersection. Like [-1, -1, 1, 1, 0]. This assumes a known starting point and orientation.

### 3. Following the path

This seems like a straightforward application of a line-following robot. It looks like this robot is also able to detect the intersections.

In their video, they provide a huge piece of manual assistance: placing the robot at a known starting location. All that the robot does is follow the lines, and at each detected intersection executes a turn according to the list of turns it received as instructions.