How to calculate shortest path between multiple pick and drop destinations

Question

I have a scenario where I have multiple robots, and they have to pick and drop some items at specified locations as shown in Figure.

There are 4 jobs to be done for this particular instance. How can I go about planning the shortest optimized path for carrying out these jobs.

I am a beginner in path planning and am finding it difficult to come up with a solution that can work in this case. I can use dikstra and A* etc to find all possible paths but in my case I have a constraint that the destination node cant be reached if the source node for that particular destination node hasnt been visited first.

Answer 1

Side note: If there are multiple objects at A and C, so the robots continue circulating to move the objects cyclically, then ABCD and CDAB are the same paths. In either case (single objects at A and C or multiple objects), just assign a weight to each segment that equals the distance travelled to go from source to destination. Add the segment lengths and choose the minimum. With this few number of nodes, an exhaustive search method like this would work.

As a thought exercise, and to confirm this method, assume the distance between A and B is very short, but that D is far away from A. I’ll choose 1 for segment AB and 10 for segment AD. In this case, let’s say that BD is 10.5 so the geometry makes sense. Let’s just compare those paths that begin with travelling along CA (but you’ll have to do this for all paths). Your choices are CABD and CADB.

For these two paths, CA is the same so we can disregard it for this exercise. So you are left with ABD vs ADB. ABD lengths are 1 + 10.5 = 11.5. ADB lengths are 10 + 10.5 = 20.5. So in this arrangement, CABD would be more optimal.

In addition to the distances between nodes, you may have to consider additional weights that stand for the distances between robots 1 and 2 and the various starting node options.

As the number of nodes increases, more advanced methods and heuristics would be needed rather than an exhaustive search.

Answer 2

One approach would be to use A* to plan a path to the pickup point and then again to plan a path to the dropout off point all the while ignoring that there are other moving agents. That should be pretty straightforward. From there you need to concern yourself with collision avoidance. For that you could look at Generalized Reciprocal Collision Avoidance (GRCA). If I recall correctly you should be able to use the A* solution to jump start the GRCA calculations by using it as a nominal trajectory.

Answer 3

On the first look, the question looks like an pathplanning problem in which the total amount of travel-distance has to be minimized. But a detailed look shows, that the problem is more complicated because many robots are in the game who have different tasks for start/destination points. The first step is to give such a challenge a name. I would call it a “blackboard scheduling problem”. A blackboard architecture isn't an algorithm but a datastructure for implementing a multi-agent system. Multi-agent doesn't mean, that many robots are available but many software-agents which are equal to planning submodules.

Let us go into the details. The output of the software is a plan which control the pick&place robots to drive around in the map. Before such a plan can be created many subplans are needed which are optimized for certain constraints, for example in respect to the local distance and if the pick&place action make sense in comparison to the job list in the table. Evaluating different kind of plans by separate planners can be realized on a blackboard. That means an example plan is stored in the datastructure and then the software agents are given feedback how well the plan looks to them. An overall control loop summarizes the comments of the agents and produces the resulting plan. This can be executed on the real robots.