2

enter image description hereplotted path

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]
Perseus784
  • 104
  • 2
  • 9
  • But they have to move simultaneously that's the constrain – Perseus784 Sep 24 '17 at 05:28
  • If time is no concern, let the robots go to their endpoints one after another. So: robot 1 moves to the endpoint. After that, robot 2, etc. Since at any time only one robot is moving, no deadlocks will occur. If the robots can't communicate with each other, assign timeslots. Maximum moves is 4+4=8. So robot 1 moves in round 1-8, robot 2 in round 9-16, etc. – agtoever Sep 24 '17 at 05:28
  • What exactly is wrong with stopping robots randomly? It looks like very general solution. – algrid Sep 24 '17 at 12:50
  • Say if one of them is already in the top row. then if R2 wanna cross that node, it cannot because R1 is blocking it. In this case, R1 should be moved first and then R2 should be moved. The probelm is how to decide which one of them to stop to avoid deadlockings. – Perseus784 Sep 24 '17 at 13:27

3 Answers3

1

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.

J_H
  • 17,926
  • 4
  • 24
  • 44
  • A little bit of elaboration, please. – Perseus784 Sep 23 '17 at 19:27
  • The robots cannot move independently since it's a line follower controlled by a Central system where all the planning happens and also the robots cannot move across except for the upper and lower rows. So, I doubt this method isn't suitable for this particular problem. – Perseus784 Sep 23 '17 at 19:37
  • What's the problem? *Any* method for resolving deadlock will satisfy the requirements you have stated. Give robot 1 priority, for example. – alexis Sep 23 '17 at 21:17
  • That's what I said, For this case giving the priority to a random robot is okay. but it'll not be effective for all the cases – Perseus784 Sep 24 '17 at 05:27
1

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

agtoever
  • 1,669
  • 16
  • 22
  • I have only 16 points, but I'm using 3 robots actually, so if each one takes all the points, there is a serious chance that many points would be taken and that is going to affect the other robot's path because of lack of points. and how do we know which one make wait and which one to let go. – Perseus784 Sep 23 '17 at 19:47
  • Robot don't take points. Just vertices. For the 4x4 fully connected matrix and 3 robots, there are some cases where there isn't a solution. I added a remark about robot priority. – agtoever Sep 24 '17 at 05:27
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.

roundabout

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

solution

agtoever
  • 1,669
  • 16
  • 22