This Algorithm is simple and straight forward. These LEFT, RIGHT, STRAIGHT, and BACK are the directions that the robot follows. In "LSRB" L stands for 'LEFT', S for 'STRAIGHT', R for RIGHT, and B for 'BACK' or BACKWARD. 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.This is the algorithm by which the robot solves the maze. In their video, they provide a huge piece of manual assistance: placing the robot at a known starting location. It looks like this robot is also able to detect the intersections. This seems like a straightforward application of a line-following robot. This assumes a known starting point and orientation. 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. 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. 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. Computing the pathĪs 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. 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. Navigation requires a map of the robot's environment - it looks like this was done manually. It looks like there are 3 main components to the demonstration in this video. Drive distance would then be along the hypotenuse, which you can calculate using the Pythagorean Theorem. You can make any other axis be the zero by adding an offset, and can convert to degrees if you desire.īasically you just find the angle between the coordinates relative to the global x/y axes, then subtract your current heading from that. This snippet/example assumes that you measure heading as 0 radians as the +x-axis, with angle increasing in a counter-clockwise direction. NextHeadingRelative = nextHeadingAbsolute - currentHeading ĭriveDistance = sqrt( (x1-x0)^2 + (y1-y0)^2 ) NextHeadingAbsolute = atan2( (y1-y0), (x1-x0) ) So, for example, if you store all of the coordinates for the points in addition to the digraph and distances, you could try: currentWaypoint = So it is up to you to calculate the distances between points and to know the physical relationship between two points. 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. 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. 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?"Įssentially, Dijkstra's algorithm only requires to you give a digraph with a set of distances or "costs" between the two points. See this similar question and my answer to it.
0 Comments
Leave a Reply. |