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.
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.