I am interested in mission planning for multi-robot systems. Given multiple robots and multiple tasks and an environment, I need to specify missions and software should plan for the robot team to accomplish the mission.

To be more precise, tasks are just a bunch of waypoints with or without time-stamps or deadlines. More elaborately, a task in abstract sense is something like patrol location A using two robots which essentially can be coded up as two sets of way-points or trajectories for the robots. hence the assertion above that tasks can just be viewed as a bunch of waypoints.

So there are multiple tasks and what tasks have to be executed in which order has to be planned by user or software so as to fulfil a mission. I am looking for Github repositories where people have tackled such problems to take inspiration. I am open to any software framework.

As a prime example of the kind of work or software I am looking for, FLYAQ - An open source platform for mission planning of autonomous quadrotors is an example. Please share any code or PDF links, if possible.

  • $\begingroup$ What is the approximate robot size, mobility, and deployment area? $\endgroup$ – hauptmech Jun 12 '17 at 20:10
  • $\begingroup$ Right now this is a simulation problem only so no connection to real robots; considered robots follow dubins model and simple PID controllers in a 2d environment with main focus on testing abstract planning algorithms. $\endgroup$ – user_1_1_1 Jun 12 '17 at 20:27

First, it's important to note that depending on your problem specifications, we may not know of any good algorithms to solve it - this is especially true when you start to add in more problem constraints.

There are three levels of abstraction here - your question primarily deals with the highest level, but FLYAQ covers all three so I include them here as well.

High level: Task assignment and ordering

Given a list of tasks, constraints, and costs, we first find the best set of ordered sets of waypoints for each robot in your team respects the constraints. This is generally called the "vehicle routing problem", and has many variants. One open source software is OptaPlanner. The HeuristicLab also has an impressively mature software stack for these problems. You could also consider solving these problems using a linear program solver such as Gurobi or open source alternatives. If you have a more specific problem in mind, create another question and I'll post an answer (this is my area of research).

Mid-level: Trajectory planning

Once a robots has been assigned an ordered set of waypoints to visit, it still needs to decide how to connect the dots. Depending on your hardware this might already be abstracted away (e.g. with MotionPlanner and Ardu* planners). If you need to solve this problem, there are a few very good libraries for this, such as Open Motion Planning Library and Drake. The output of this layer is typically a polynomial or spline representation of a trajectory that is guaranteed to be collision free.

Low level: Rate control

At the lowest level the robot needs to translate a desired trajectory into rate commands for its actuators. This is entirely dependent on your hardware platform, and is often abstracted away. If you already have hardware, then see if a google search yields an example of how to go from a waypoint list or trajectory to rate commands.

Putting everything together

A typical software set-up will separate each level of abstraction into different applications, since they run at different rates (typically high level is ~0.1-1Hz, mid level is 1-10Hz, low level is 10-100Hz). One very popular middleware is the Robot Operating System, which has an active community and many tutorials.

This answer is vague by necessity - your question covers a range of topics which has thousands of published work on. If you have a more specific problem or abstraction layer in mind, there are definitely more specific answers available.

  • $\begingroup$ Thanks for so much information. I also wanted some idea on 1 planning layer above. Assume specification of how to compute way-points for different tasks are provided, we know how to plan trajectory, and control robot on it. But given an abstract mission like patrol 5 nuclear sites for 5 days, how to plan a flowchart of tasks? So i am assuming all 3 you pointed out are already solved and ready. Should I post another question on it? $\endgroup$ – user_1_1_1 Jun 12 '17 at 20:33
  • $\begingroup$ Definitely post another question, with details such as: Are the travel costs known? Is time continuous or discrete? How do you know that the paths are good (e.g. minimum cost, maximum information, ...)? Are all robots the same, or do they have different abilities? $\endgroup$ – combo Jun 13 '17 at 6:46

Your Answer

