Possibility of implementing Shortest path algorithm with waypoints on webots

Question

I'm currently doing a project using Webots to create a 3d simulation world - a container terminal yard whereby multiple robots(AGVs) reach their designated destination to load/unload containers.

Here's a glimpse of what I've been doing for the past few weeks.

http://www.youtube.com/watch?v=Rt6NlGP9wpA

The round bubbles you see act as a wireless range to send directions to the AGVs.

Seeing some similar threads on shortest path algorithm like Dijkstra or A* Algorithms, I'm pretty sure it can be done but i was hoping if anyone could perhaps provide some insights whether it's possible? and which algorithm is preferred to use?

Thanks and Regards

Answer 1

Given your clarifications, you need to choose your game here. The most straightforward solution is indeed running a Dijkstra algorithm and building the shortest paths from any waypoint to any other waypoint (this means a single algorithm run for each possible source point). Note however that this is only done once (at least until some waypoint is moved or removed). By the way A* isn't related here, it's intended to run on decision/game trees and find min/max optimal path (max benefit for you, min for the opponent), that's a different story. Another alternative is to run Floyd–Warshall which find all paths in a single run.

Anyway, once you ran that, you can keep for each waypoint a table, saying what is the next node in the shortest path for each destination waypoint. You don't need to entire path, just the next vertice. Once the robot gets there, it's told where to go next. This is basically the same thing done in most network routing algorithms.

Now, if you want to showcase how the robots are working, you could make them run this algorithm online and calculate the paths for themselves, but then the communication with the waypoints is rather pointless.

Either way, looks like you're having some fun coming your way, enjoy :-)

Answer 2

Well if there was a certain path you had that we could use as example, explaining how the algorithm would work would be simpler.

But i'll try to explain anyways:

Considering you have a Starting point A and a destination Z, which i will represent in this Pyramid:

. . . . 3 . . . .  
. . . 7 4 . . .  
. . 2 4 6 . .  
. 8 5 9 3 .  

In this pyramid we will try and find the minimum path sum, starting from the first line and reaching the last line, by picking any of the two numbers benieth the one we picked previously.

On a small tree, it would be simpler to measure all possible solutions and pick the smallest. This is not effective on bigger trees.

The way to solve it would be to start from the bottom and go up, take 8 and 5, and add the smallest to the number above them (2 here) then 5 and 9, then 9 and 3. You repeat the process on the line above, until you reach the top line, and the Minimum path sum.

I hope this clears up a bit on the nodes and minimum path. Though this might be hard to code for AGV paths with several paths and nodes intercrossing.

A simple way i would use, if you have the coordinates of each AGV node (stopping point that connects different paths) would be to draw a line between the destination and the start, and add node by node the closest ones to that line that are connected to the previous node.

Good luck :)