Thursday , March 30 2017
Home / Robotics / Robot Theory / Programming Shortest Path Line Follower Robot

Programming Shortest Path Line Follower Robot

This post is the programming section of my previous post Shortest Path Line Follower Robot Logic Revealed!  that dealt with the logic behind the following routines. To understand the complete nature of this post you should read that post first and then continue with this one.

No, this is not the entire code! even if the title reads Programming Shortest Path Line Follower Robot :-).

This by no means is the entire code for the shortest path detection robot. But listed below are some functions that constitute major parts of the code. I was developing the code to kill time and I have not yet tested it. But the logic by-far is correct and may contain a few bugs.

If you are making this robot and following the algorithm explained in my previous post, you will find these functions handy.

Sensor Arrangement:

The balckboy, has 8 sensors mounted on the base plate to provide it with the ability to follow any type of line with just some minor modifications in the programming section without having to touch the hardware. There are two other sensors for encoding the wheels of the robot, but for now our concern is only the line follower.

In the code I use C macros to address these sensors without any confusion. Here is what I have defined,

Here is an Image to show the physical location of these senors on the base plate of the robot. For understanding the code snippets to come, you will need this as a reference to see which sensor we are talking about.


Check for a bend or node:

In the theory section, I had give a clear definition of a bend and turn (node) do I will not rehash it here. This function is used to determine if a junction met my the robot is a node or a normal bend. If it is a node, it returns 1 and if it is a turn it returns 0. There is also another purpose this function solves. It also detects the end of track maker denoted by the return of 2 to the calling function.

Update Direction Array:

This function is used update the direction array with the new direction after the robot has made a turn in some direction. This function expects the calling function to send a mode selection value based on the last turn it made. Initially it is assumed that the robot is facing North and with respect to this North the other relative directions are derived.

If the robot made a normal single step turn to left or right then 1 is passed. If the robot makes a U turn (which is a 2 step turn) at a particular point then it has to send 2 to this function so that it is able to update the direction accordingly. The logic is such that, if it is a normal single step turn, then the next value of the dir_arr is one more than the previous value. On the other hand if it is a U-turn, then the next value of the dir_arr is two more than the previous value. In both the cases, the total sum should not exceed 4 so the answer is modulo 4-ed to get a circular buffer.

Identify the redundant tracks:

This function is used used to identify two consecutive the opposite directions in the dir_arr array and replace them with an arbitrary value (say 50) so that it can be removed as an useless path traversed by the robot.  I traverse the entire array searching for such opposite directions and increments a counter variable for monitoring if there has been atleast one replace of data. This counter is then used to terminate the call to the remove() function.

Remove the identified values:

The remove() function is used to remove the consecutive equal elements in the sorted array. The remove() function calls the sort function again. This process is recursive and has to be terminated by the the sort() function if there is no more sorting to be done. This is monitored by the loop counter ctr. If the counter is never incremented, then in the last pass there wasn’t anything to sort which means that all the passes are over and the array has the shortest path stored in it.

Reverse the direction form destination to source:

Since our objective is to make the robot come back to the source node from the destination node choosing the shortest path, we have to rearrange the dir_arr array such that the each of the directions are reversed. That is North becomes South and South becomes North and vice-verse.  Also the total arrya has to be flipped; as in, nth element become the 1st element and so on.

Wrapping Up, these are the functions that I have developed so far. Beyond this there is just the structuring of the program and testing the logic once the entire code is ready. There also has to be a hardware test (toughest of the lot) and of course the documentation section of the robot in action.

About Siddharth

Siddharth is a Firmware Engineer, techie, and a movie-buff. His interests include, Programming, Embedded Systems, Linux, Robotics, CV, Carpentry and a lot more. At times, you could see some of his sunday projects converge on release quality. You get to know him on the following social channels.

Check Also

shortest path

Shortest Path Line Follower Robot Logic Revealed!

Bored of the conventional line follower? People nearby are losing interest? Here is a post …

  • faizan

    I have some prblm in finding shortest path in line follower.My arena has loops I have to enter in it by a dry run and come back by shortest path

    • If your arena has “simple” loops (only one unit distance) then it’s very simple. From the top of my head I can think of one way. You should keep a local circular buffer which can hold 4 variables. Then every time you make a change in direction add it to the circular buffer. At every turn, check if all the elements are equal. If they are equal then you got into a loop.

      If the arena is made of complex loop structures, then it requires some more thinking (have to sit with a pen and paper 🙂 ) to get the robot out of it. I am sure you will be able to come up with something. Good luck.

  • sandy

    Sorry if i make a mess here, I’m unable to understand the program (shortest path). I guess default right or left algorithm can fetch a solution to destination. But how does the robot remembers the correct path and nodes in reverse direction. Can any one please explain me this ? I mean please explain me the code (I’m new to programming)
    thanking you

    • Hi sandy, there are two parts in your question. remembering the correct path and coming back in the reverse direction. The coming back in reverse direction was something that I added to make the robot look good. You could also make it so that you run it once and then carry it back to the start point and then it this time it takes the shortest path. About finding the shortest path, did you read my other article? (link in the top of the article) I have an elaborate account on that.

      • regalz

        hai..I need ur help..
        I have selected ur ckt for my project in my college..but now I am in trouble..itz not working well..coming friday (13/03/2015) is the final date for submission..pls help can I condact u have an accnt in fb ?

  • sujatha


  • sujatha

    Sir …. I have some problem while writing a program for fire bird robot for some task…
    Would you help me …

  • kapil patil

    Sir I want the robot to first scan the whole track and find the shortest path and then again from start it should follow shortest path and go to the destination.

  • murali mohan reddy kota

    Sir , can you send me the whole code in sigle file mail:

Keep in touch with the current trends!
Did you like this article? Sign up and get our latest posts delivered to your inbox!
  We hate spam and never share your details.