Collections of heterogeneous air, ground, and/or water-based robotic vehicles must cooperatively plan their motion to accomplish remote sensing, searching, mapping, and similar missions in a 3D, real-world environment. Vehicles must avoid colliding with each other as well as with environmental obstacles while efficiently using available resources including time, computing, and communication bandwidth.

State-of-the-art techniques address some aspects of this problem but none provide a comprehensive solution. The best techniques are based on probabilistic sampling, including the probabilistic roadmap (PRM) and the open-loop rapidly exploring random tree (OL-RRT) algorithms. These “growing graph” strategies spread trajectory trees through cluttered environments based on open-loop models of a system. They quickly search high-dimensional spaces containing static or dynamic obstacles while considering velocity bounds and kinematic/dynamic constraints. They plan the motion of robots well in practice and are probabilistically complete and asymptotically optimal. However, implementations based on these techniques may be limited to single robots or homogeneous groups of robots, do not scale well, or are not robust against communication failures. Other implementations broadcast a single plan created by a centralized agent to all robots. Some are completely decentralized but require all agents to broadcast their plans and any state changes to all other agents before the next planning step can be taken. Further, errors in a robot’s state resulting from external disturbances propagate more rapidly with open-loop control than with closed-loop control. For this reason, CL-RRTs are more robust to uncertainties, often with finite and bounded errors. The authors provide a very readable summary of these techniques and their limitations.

The authors’ multi-agent rapidly exploring pseudorandom tree (MRPT) technique extends classical CL-RRTs to perform fully decentralized planning and coordination of the movements of a team of heterogeneous robots in real time as they perform a mission, subject to disturbances and measurement noise. A key innovation of their approach is instead of each robot planning randomly, all robots use the same pseudorandom sampling function that produces the same totally deterministic sequence of pseudorandom numbers. This means each robot can predict the behavior of all other robots since each follows the same plan.

The authors give complete pseudocode for both a planning algorithm (that expands trees and eliminates nodes leading to collisions) and a re-planning/real-time control algorithm (that finds an optimal path, re-planning if necessary.) They verify their algorithms using multiple air and ground robot experiments plus simulations with larger numbers of robots. They estimate computational complexity and barriers to scaling to large numbers of robots. This paper is well worth reading by anyone interested in planning and controlling the behavior of swarms of heterogeneous robots.