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