Cooperative Sampling-Based Motion Planning under Signal Temporal Logic Specifications

We develop a cooperative sampling-based motion planning algorithm for two autonomous agents under coupled tasks expressed as signal temporal logic constraints. The algorithm builds incrementally two spatio-temporal trees, one for each agent, by sampling points in an extended space, which consists of a compact subset of the time domain and the physical space of the agents. The trees are built by checking if newly sampled points form edges in time and space that satisfy certain parts of the coupled task. Therefore, the constructed trees represent time-varying trajectories in the agents’ state space that satisfy the task. The algorithm is distributed in the sense that the agents build their trees individually by communicating with each other. The proposed algorithm inherits the properties of probabilistic completeness and computational efficiency of the original sampling-based procedures.