Hi,
I want to make a line follower that follows the grid as shown in the image below-
I'll be feeding an array in the code eg. [12,19,06,28,03] which will contain the node numbers. The line follower must reach the specific node and glow the LED for 500ms and then move to the next node in the array following the shortest path..
I have written the code for following the line. I am not able to understand how do i guide my bot through the nodes.
For Shortest path finding, I found about Dijkstra’s Algorithm that might be useful. But how do i enter my grid as array.
Any help will be appreciated.
Thank you
Hi,
Tell us a lot more about how the robot works.
What line-following sensors does it have?
Can it sense multi-connection intersections?
Does it have any spatial information about the grid?
Can it identify the node it is at in some way?
Does it have compass heading information available?
How accurate is the drive system for straight ahead and various heading changes?
This is very challenging when going from one known node like 16 to node 17 which has multiple paths.
Is this your own research or some competition? A school assignment?
Here's one line follower sensor. A video of a robot that I was told uses that sensor is HERE.
DISCALIMER: SHowed a product from my own shop...
How about a 29 row, 5 entry per row of nearest neighbor?
1: 2,16,17,0,0
2: 1,3,0,0,0
3: 2,4,17,19,0
4:3,5,0,0,0
5:4,6,18,19,20
6:5,7,0,0,0
7:6,8,19,21,0
8:7,9,0,0,0
9: 8,10,20,21,22
10: 9,11,0,0,0
etc.
with
29: an exception with 8 neighbors.
Or do 10 rows,
1-16
3-19-7-21-11-23-15-17
5,20,9,22,13,24,1,18
25,26,27,28
Then the other interconnects:
1,17,5,19,9,21,13,23
29,17,19,21,23
17,25,19
19,26,21
21,27,23
23,28,17
with any path being able to be traversed in either direction.
Make a rule that you can only turn 90 degrees or less, or 180.
Figure out where are, say 16, and you want to get to 27.
One path might be 16,15,23,11,21,27
Another might be 16,15,14,13,12,11,10,9,21,27
2nd is longer, but maybe faster with one 90 degree turn. Are you going for fewest waypoints, or fastest speed?
I am using 3 infrared sensors to detect the black line. I also have an encoder on the 2 wheels. I am making it for college. The line will be followed by the central infra sensor while the nodes and turns will be detected by the other two sensors on its side.
I don't understand how to make the bot move from one point to another autonomously in the shortest path.
I can make the bot go from 1 to any node, say 16, by feeding the directions and turns, but how do I make it go ahead from 16.
Is there any way to convert this map path into some format that can be stored in the arduino?
CrossRoads:
Figure out where are, say 16, and you want to get to 27.
One path might be 16,15,23,11,21,27
Another might be 16,15,14,13,12,11,10,9,21,27
2nd is longer, but maybe faster with one 90 degree turn. Are you going for fewest waypoints, or fastest speed?
How do I figure which node the bot is on, after its left the 1st node? I will be looking for the fewest waypoint. Speed is constant, so the shortest path is important.
Get the basics working first - just sensing a line and being able to follow it, ignoring any turn offs.
I wonder how your robot can distinguish lines from nodes, and find out which line goes from a node to which neighbour node?
If you want to apply methods of graph theory, I fear that the Ardunio memory is too small for handling your sample graph, in detail if you want to build the graph dynamically from some input.
In general a node struct or class is required for every node (vertex), containing at least the node number and a list of adjacent node numbers and distances. In your case the list also must indicate, somehow, how the robot can identify the specific lines going to its neighbour nodes. More attached lists will be required for the path analysis.
The graph can be implemented as an array of node structures. The lists can be implemented as fixed-size arrays, with sufficient entries for the node with the most follower nodes, plus a dummy element indicating the end of the list. Sets can be implemented like lists, or as bitfields, where e.g. a uint32_t can hold up to 32 elements (bits).
In your sample graph it's not clear how the nodes 25-28 can be reached. Did you misplace these nodes, or will intermediate nodes be required between e.g. 17 and 29, from which also node 25 and 28 can be reached?
CrossRoads:
Get the basics working first - just sensing a line and being able to follow it, ignoring any turn offs.
Line following is working now. Need to figure out path finding now!
DrDiettrich:
I wonder how your robot can distinguish lines from nodes, and find out which line goes from a node to which neighbour node?
The robot will identify a node when all the 3 sensors are on black surface. Which line goes to which node, figuring that out is the main problem here
DrDiettrich:
In your sample graph it's not clear how the nodes 25-28 can be reached. Did you misplace these nodes, or will intermediate nodes be required between e.g. 17 and 29, from which also node 25 and 28 can be reached?
My bad. The nodes are on the vertices of the central square
Ok Here's what I am able to do till now.
My line follower is ready. It detects the lines and nodes and turns.
Using Djiktra's algorithm I am able to find out the shortest path, say Source= node 1 and destination= node 22. So on running the algorithm, I get the path 1-17-29-21-9-22.
How do I make my bot keep track of the node that it currently is on?
You can enter the starting point manually, or fix it in code and make sure, somehow, that the robot initially is on that node. A reed switch or hall sensor can be used, to detect the presence of a magnet at that starting point.
Also every node could have its own identifier, e.g. an RFID tag, what would allow the robot to figure out the graph/maze layout himself!
Cannot use any other sensors. Only line following sensor and a sharp sensor in front of the bot is allowed. Also I have an optical encoder.
terryking228:
Hi,Tell us a lot more about how the robot works.
What line-following sensors does it have?
Can it sense multi-connection intersections?
Does it have any spatial information about the grid?
Can it identify the node it is at in some way?
Does it have compass heading information available?
How accurate is the drive system for straight ahead and various heading changes?This is very challenging when going from one known node like 16 to node 17 which has multiple paths.
Is this your own research or some competition? A school assignment?
Here's one line follower sensor. A video of a robot that I was told uses that sensor is HERE.
DISCALIMER: SHowed a product from my own shop...
Dear Sir
i'm interesting to do the bot like your link can you help me?