Very beginner. Need to compute route from A to B for a robot. i would like to know how to store area map and compute the route. I can compute shortest path etc using algorithms e.g. dijkstra. What format of maps are used for efficiency.

Edit: 0. Unable to find anything useful using search 1. could not find a relevant tag put geolocation and google-maps, though question is not limited to google maps)

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Nov 8 at 16:22
  • thanks gnat@ - I find nothing on google. Sorry I did not say that in question. Would you mind answering the question now if you know the answer. Also consider to remove ur downvote so that people can take this question (serious question). whole point is to help each other. – Adams Nov 8 at 16:24
  • 1
    I can't tell if this is a StackOverflow question or a SoftwareEngineering question. Are you asking how to solve your problem? Or are you hoping to compare the merits of various maps performance metrics? If the former, it's StackOverflow. If it's the latter, please name a few possible types and your current thoughts on them. Right now, it's too open-ended. Even the word "efficiency" is broad, because you aren't stating what efficiency to strive for ("RAM usage", "CPU cycles", etc) – bitsoflogic Nov 8 at 16:48
  • 1
    Maybe a place to start with committee.iso.org/home/tc211 - but you'll see, geospatial data can be complex – Christophe Nov 8 at 19:57
  • 2
    The reason we're spending so much time on the question is that if we don't, StackExchange becomes littered with bad questions and ends up a low-quality source of information. – Blrfl Nov 8 at 20:40

For moving robots or calculate routes to move from point A to point B, you need to use a graph data structure. A graph is a set of nodes and a set of edges that relate nodes. A path is a sequence of segments (i.e. two nodes and the edge used to go from the first to the second). A path finding algorithm then allows to compute an optimal route between 2 points.

If your robot moves on a flat and limited area (a floor, a building), a 2D map with X and Y coordinates for each node is sufficient. The nodes would represent key points for the possible routes (both ends of a corridor, center of doors, etc.. If needed a 3D structure could be used for representing the floor level.

If your robot moves on a larger scene, you then need to use GPS coordinates (latitude, longitude). From the graph algorithm point of view, it doesn't change much, it's just that the calculation of distance between points will get more complex.

In the latter case, you could be interested in using data formats in which you could easily get data, such as OpenStreetMap. It uses several data formats but one of it is OSM XML or its OSM JSON variant. But before reinventing the wheel, you may consider having a look at existing libraries/frameworks.

Finally, note that in real life the nodes are abstract points, and a road or corridor segment is larger than the theoretic line between two nodes. Here one possibility is to create a grid of tightly interrelated nodes. The other is to use the nodes to calculate the route, but let the robot deviate from the ideal theoretical trajectory, within some tolerances, based on the known topology and some sensors to avoid collisions.

But now we are entering in very complex aspects with a broad set of solutions.

Please define area map. Is this the set of dots the robot can potentially move between or are you thinking of something else?

I would say the dots are really all that matter. I imagine the "map" would be a set of dots with each dot having references to other dots that can be traveled to from that dot. This will typically be just two other dots (back and ahead). Junction dots would have more than two reference dots.

When calculating the best route from A to B you have a number of options. I can think of two from the top of my head:

  • Brute force: Just go a route with only right turns until you hit the target or cannot go any further (you have to turn and revisit a dot you already passed). If you cannot go any further, backtrack to the last junction and try the next exit. Continue to do this until you have had all possible routes. If you hit the target (B) you mark or save that route. When you are done you may have several paths from A to B from which you can pick the shortest and call it the best one. This is expensive of course. It is basically the generic maze escape algorithm

  • Smart: From the start, move to the dot that takes you closest to B and repeat. If you run into a dead end, discard the last move and retry with the next best step and continue until you reach B.

Once you implement this you will probably encounter cases that need special decision making. That is where the fun starts and probably what your teacher hopes will happen, that you will come up with some unique and clever approach.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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