Path planning for multiple robots simultaneously

Question

Image1 represents the problem perfectly and shows the freedom of motion the robot is capable of.

Square-> Origin, Circle-> Destination.

These are two robots that will be working simultaneously. How to guide these robots without deadlocking each other and if anyone of them should move first, then how to choose which one.

(the above case is just an example, I know in this case we can stop anyone of them randomly and get away with it, but I'm looking for a generalized solution. Nearest Neighbour approach is forbidden.) NOTE: the robot cannot move across except for the upper and lower rows.

I have a dict of all the X marked points and also the routes for it in both ids and coordinates below,

# X generated points  
{1: [0, 0], 2: [0, 30], 3: [0, 60], 4: [0, 90], 5: [30, 0], 6: [30, 30], 7: [30, 60], 8: [30, 90], 9: [60, 0], 10: [60, 30], 11: [60, 60], 12: [60, 90], 13: [90, 0], 14: [90, 30], 15: [90, 60], 16: [90, 90]}

# Routes:
red=[11,12,8,4]
blue=[7,8,12,6]

Answer 1

Let all robots turn in the outer circle until the destination is one step away and the destination is empty. In that case, move to the destination point.

So the algorithm becomes:

• if in the inner circle and the outer circle is free, move there; else wait for one cycle (or if that is not allowed, make a step in the inner circle)
• if in the outer circle, check if the destination is 1 step away. If that's the case, go there. Otherwise, move one step on the outer circle.

No collisions. No weird cases. Works 100% of the time.

Applied to your example: robot A will get home in 3 steps. Robot B will take 11 steps.

Answer 2

Do gradient descent in a potential field.

Think of your board as 3 dimensional (OK, 2.5 dimensional), with "mountains" where barriers like walls are, and a "valley" where the goal is. Each robot maintains its own potential field, which can be same or higher resolution than the grid you drew. Fields can change as a function of time t.

So now you have a function, z(x, y, t), that you can probe in the robot's immediate neighborhood, on which you can compute deltas (gradients) showing you the way "down-hill", the way toward the goal state. While traversing a hallway, for example, your robot would prefer going down the center because potential fields would extend outward from the walls, essentially repelling the robot. The grid you drew is surrounded by 4 impassable walls.

Now let's move from fixed obstacles to mobile peer robots. It sounds like you have some means for a robot to broadcast its intentions to its peers. A robot has an A* planner, which predicts that it will be visiting certain locations at certain future times. Of course, that might not work out due to sensor noise and event uncertainties, but it's a plan. So broadcast that to peers. They will add the anticipated path to the potential field they're using, so other robots exert a repulsive field just like walls and fixed objects do. This encourages a peer to plan a trajectory which steers around an obstacle (a robot) that is anticipated to be at a location in future. One can still encounter local maxima and deadlocks, so some amount of random backoff will still be needed. For example, two robots meeting head-on in a hall would, with some random noise, hopefully pick one side or the other, but it is non-deterministic whether it would be London or Manhattan driving rules, left or right side.

A technique like flood-fill can propagate gradient incentives outward from the goal to encourage a robot to move "away" from goal in order to move around maze barriers.

This approach works for autonomous robots with sporadic sensing / communication, and also for centrally controlled robots. The central controller would maintain one plan per robot, and also one potential field per robot, corresponding to obstacles plus peers. Trajectories from start to finish could be assembled by a Planner component before the first motion command was even sent to a physical robot. If the planner loops through robots 1..N, the lower numbered robots will tend to obtain shorter paths as they announce plans first and enjoy greater freedom of movement. For example, if Purple moves first at t0, then its potential field essentially blends into that of the wall for t1 and subsequent, so Pink will naturally make plans that avoid the wall and hence the two stay deconflicted. You can think of this as Purple having priority over Pink.

Answer 3

If your maze/grid has many options to get from source to target, the following "greedy" algorithm will work:

• Use a shorthest path algorithm to plot a path for the first robot.
• Remove all vertices of the found path from the maze
• Repeat for the next robot(s)

This resolves the routes one robot at a time. By removing the path(s) of the previous robot(s) from the maze, you prevent the other robot(s) to use the same path.

There is the posiibility that two robots try to occupy the same node, but this will not deadlock them because their entry and exit paths are unique. One of the two robots will just have to wait one turn until the other is gone. Just let robot[i] get priority over robot[j] for i