I have to program an autonomous robot to traverse through a grid given in the following figure.
But the main problem is that the nodes to visit is not known beforehand, it will be received by the bot in real time.
E.g.- after reaching the node 19, the bot now has to go to node 6. The shortest path(19-17-7-6) can be calculated by Dijkstra algo but i don't know how to make the robot traverse that path.
Any idea ?

enter image description here

Edit: Sorry for not making the question clear enough.
I am facing the problem in determining the current position and the direction the robot is facing so i can't define the set of commands (turn left/right/forward) to traverse to the next desired node.
I am thinking about an extra array for previously visited nodes and the current node and an extra variable for facing direction.
But for that i will have to define command sets for each node from each and every node.
Any better idea ?

  • 2
    $\begingroup$ What difficulty are you having? You seem to already understand Dykstra's algorithm, and you're given the map in advance - what is it that you are not understanding? Navigation from one point to another? Locating? Line following? How is this actually set up - A line on the floor? A maze with walls? Please be specific. $\endgroup$ – Chuck Dec 28 '15 at 19:12
  • $\begingroup$ I'm voting to close this question because it's unclear what you're asking. $\endgroup$ – Chuck Dec 29 '15 at 12:43
  • $\begingroup$ It is unclear why this is a problem. "Go to 17 from 19" should be a reasonable activity for the robot. Please elaborate why it is difficult to make the robot do this. Some reasons that might pop up: Is the robot hard to manuver? Is the whole graph not known to the robot? Does the robot not know where it is on the graph? $\endgroup$ – Josh Vander Hook Dec 29 '15 at 17:19
  • $\begingroup$ Have updated my ques. Please take a look @Josh Vander Hook $\endgroup$ – Shivendra Singh Vishen Dec 30 '15 at 6:10
  • 1
    $\begingroup$ I'm afraid it is still unclear what you are asking. Rather than adding an "edit" section, please consider merging the info in that section into the main part of the question. $\endgroup$ – Mark Booth Jan 4 '16 at 11:54

You are absolutely correct that Dijkstra's Shortest Path Algorithm can tell you the correct path for the robot to follow. The problem seems to be that you cannot tell where the robot is, and what actions to make the robot take to get to the next node.

There's no "right" answer here, but I can offer some guidance about how I'd do it.

Where is the robot

  • If the robot can observe the configuration of the outgoing edges, then he can narrow down his location to a set of possible nodes. For example, if there are two outgoing edges, he can only be in 2,3,5,6,8,9, 11, or 12. Similarly for 3, and 4 outgoing is uniquely the center
  • Since you say you have to deal with the robot's orientation when moving, it is probably safe to assume the robot can measure its orientation or at least discover it relative to the current configuration of edges. If the robot has some way of knowing his orientation, then the number of edges and their cardinal direction would help even more. For example, with two edges facing north and south, then we know the robot is at 3,5,9, or 11.
  • Furthermore, if the robot knew the history of possible locations, then we can also incorporate that information. If we knew the robot had two outgoing edges facing east and west, then he moved to the westmost edge and now had two edges facing north and south, then we know the robot is now at 3 and came from 2. What's cool here, is the robot did not know from just the edges, it was the action of moving that caused it to figure out where it was.

I might do that as follows:

  • Keep a separate list of all nodes and their edges. Assume all nodes are "unmarked"
  • At the start
    • Observe the number of outgoing edges at the current node
    • Mark all nodes with a different number of edges
    • Observe the outgoing edge orientations, and mark all nodes which have different orientation (i.e., if we notice an edge going north, mark all nodes which don't have an edge going north).
    • At this point, we know the robot is only in an unmarked node
    • Travel along an arbitrary edge (but not back to start)
    • Check the new outgoing edges. Mark all nodes which have different outgoing edges.
    • Additionally, mark all nodes which have the same edges but are not connected to an unmarked node

Repeat this process until only one unmarked node remains. Without orientation, this will never happen though (for example, 4 and 10 are identical up to orientation)

If you have no orientation information, and no way to observe outgoing edges, then history is all you have. If you know what node you started at, then by all means, you must come up with a complete sequence of actions to get the robot to the desired node. Here's how we might do that.

Getting there

Let's assume the robot starts at 1 and has to get to 21. I'd program a small subroutine that did the following.

  • Call dijkstra to get the shortest path.
  • Until reached:
    • Turn the robot toward the next node
    • take the edge
    • Update the robot's current node
    • Update the next node from the list in Dijkstra's output

Using this, the robot always knows his current node and next node. We only assumed that we knew the starting orientation.


There are generally three parts to a simple roboitic system:

  • Guidance
    • How do I get to my goal?
      • extends to state-space, not just position of robot
  • Navigation
    • Where am I?
      • measurement of the robot's state
  • Control
    • How do I use the actuators to achieve my goal, given my current state.

Your path-planning application that uses Djekstra's algorithm to find a path covers only the Guidance part. You still need to be able to estimate where you are, then change your actuators (wheel direction, speed etc..) in order to achieve your goal position.

You can do all this in simulation with Gazebo + ROS, I think everything you need is already developed open-source in ROS.

A very good introductory resource is from Peter Corke "Robotics, Vision and Control".

  • $\begingroup$ This is a classic "RTFM" answer to an unclear question. It does not answer anything, and directs the reader to a textbook and waves some high-level knowledge like "use gazebo+ros" which does doesn't help a person new to robotics. Let's hold off until the question is clear. $\endgroup$ – Josh Vander Hook Dec 29 '15 at 17:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.