Collision checking is considered to be the most expensive computational bottleneck in sampling-based motion planning algorithms. We introduce a simple procedure that theoretically eliminates this bottleneck and significantly reduces collision-checking time in practice in several test scenarios. Whenever a point is collision checked in the normal (expensive) way, we store a lower bound on that point’s distance to the nearest obstacle. The latter is called a “safety certificate” and defines a region of the search space that is guaranteed to be collision-free. New points may forgo collision checking whenever they are located within a safety certificate of an old point. Testing the latter condition is accomplished during the nearest-neighbor search that is already part of most sampling-based motion planning algorithms. As more and more points are sampled, safety certificates asymptotically cover the search space and the amortized complexity of (normal, expensive) collision checking becomes negligible with respect to the overall runtime of sampling-based motion planning algorithms. Indeed, the expected fraction of points requiring a normal collision check approaches zero, in the limit, as the total number of points approaches infinity. A number of extensions to the basic idea are presented. Experiments with a number of proof-of-concept implementations demonstrate that using safety certificates can improve the performance of sampling-based motion planning algorithms in practice.
3 January 2020 in IEEE Robotics and Automation Letters
In this letter, we address the problem of collision avoidance for a swarm of UAVs used for continuous surveillance of an urban environment. Our method, LSwarm, efficiently avoids collisions with static obstacles, dynamic obstacles and other agents in three-dimensional urban environments while considering coverage constraints. LSwarm calculates collision avoiding velocities that maximize the conformity of an agent to an optimal path given by a global coverage strategy and ensure sufficient resolution of the coverage data collected by each agent. Our algorithm is formulated based on optimal reciprocal collision avoidance and is scalable with respect to the size of the swarm. We evaluate the coverage performance of LSwarm in realistic simulations of a swarm of quadrotors in complex urban models. In practice, our approach can compute collision avoiding velocities for a swarm composed of tens to hundreds of agents in a few milliseconds on dense urban scenes consisting of tens of buildings.
Metareasoning refers to reasoning about one’s own decision making process. This paper considers metareasoning about the decision making process in multi-agent settings. We present a multi-agent metareasoning approach that enables a multi-agent team to select which task allocation algorithm to use as a function of changing communication quality level. Given a set of multi-agent task allocation algorithms, we synthesize a policy that prescribes the best algorithm to use among a predefined set of algorithms for a given communication level. Since each agent in the team runs the same policy, the team (or a part of the team) will collectively switch between task allocation algorithms as a function of the observed level of communication. We apply reactive synthesis to generate the policy from high-level specifications written in Linear Temporal Logic encoding the agents’ switching behavior with respect to the state of the environment. We perform experiments in simulation to identify the best performing algorithms under different communication levels. The communication environment is modeled using the Rayleigh fading model and communication estimation is done through the exchange of heartbeat messages among agents. We test our metareasoning policy in three types of scenarios: search & rescue, fire monitoring, and ship protection scenarios. For each scenario, we demonstrate that our policy achieved better performance with respect to either max distance traveled, max number of transmitted messages or both compared to running any single algorithm.
Bidirectional path and motion planning approaches decrease planning time, on average, compared to their unidirectional counterparts. In single-query feasible motion planning, using bidirectional search to find a continuous motion plan requires an edge connection between the forward search tree and the reverse search tree. Such a tree–tree connection requires solving a two-point boundary value problem (BVP). However, obtaining a closed-form two-point BVP solution can be difficult or impossible for many systems. While numerical methods can provide a reasonable solution in many cases, they are often computationally expensive, numerically unstable, or sensitive (to an initial guess) for the purposes of single-query sampling-based motion planning. To overcome this challenge, we present a novel bidirectional search strategy that does not require solving the two-point BVP. Instead of connecting the forward and reverse trees directly, the reverse tree's cost information is used as a guiding heuristic for forward search. This enables the forward search to quickly grow down the reverse tree—converging to a fully feasible solution without a direct tree–tree connection and without the solution to a two-point BVP. In this article, we propose two algorithms that use this strategy for single-query feasible motion planning for various dynamical systems, performing experiments in both simulation and hardware testbeds. We find that these algorithms perform better than or comparable to the existing state-of-the-art methods with respect to quickly finding an initial feasible solution.