STL-Constrained Multi-Robot Trajectory Planning via Constrained Bayesian Optimization and Local Cost Map Learning

Abstract

We address multi-robot motion planning under Signal Temporal Logic (STL) specifications with kinodynamic constraints. We propose a two-stage framework integrating sampling-based online learning with formal STL reasoning. At the single-robot level, our constrained Bayesian Optimization-based Tree search (cBOT) uses Gaussian-process surrogate models to learn local cost maps and feasibility constraints, generating shorter collision-free trajectories with fewer samples. At the multi-robot level, our STL-enhanced Kinodynamic Conflict-Based Search (STL-KCBS) incorporates STL monitoring into conflict detection and resolution, ensuring specification satisfaction while maintaining scalability and probabilistic completeness. Benchmarks show improved trajectory efficiency and safety over existing methods, and field experiments with autonomous surface vehicles validate robustness in uncertain environments. (Videos: stlbot.github.io)

Overview & Contributions

This section highlights the main contributions of our work, focusing on constrained Bayesian optimization, STL-constrained planning, and scalability guarantees.

Key Ideas

cBOT: Constrained BO-based tree search that learns a local cost map and feasibility (GP surrogates) to produce shorter, safer trajectories with fewer samples.
STL-KCBS: STL-enhanced kinodynamic CBS using robustness-based conflict detection and STL monitors for specification-compliant multi-robot coordination.
Scalability: Decoupled low-level planning paired with formal STL monitoring for robust satisfaction.

Kinodynamic Constraints Robust STL Monitoring Probabilistic Completeness

Benchmark Results

We evaluate across four environments (Env. 1: empty, Env. 2: cross-hall, Env. 3: forest, Env. 4: bugtrap) with teams up to 50 robots. STLcBOT achieves near-perfect success, tractable runtimes, and compact paths relative to RRT-based and convex-optimization baselines.

Benchmark comparison across four environments. — **Fig. 5.** Benchmark comparison of multi-robot motion planning algorithms across four representative environments (Env. 1: empty, Env. 2: cross-hall, Env. 3: forest, Env. 4: bugtrap). Columns report success rates, runtimes, and path lengths as team size increases. STLcBOT and other cBOT-based methods achieve near-perfect success and efficient paths with tractable runtimes, while RRT- and STGCS-based approaches degrade under clutter and density.

RRT under STL in forest. — **Fig. 2a.** RRT trajectories under STL constraints in *forest*.

cBOT under STL in forest. — **Fig. 2b.** cBOT trajectories under STL constraints in *forest* (shorter, smoother).

RRT under STL in cross-hall. — **Fig. 2c.** RRT trajectories under STL constraints in *cross-hall*.

cBOT under STL in cross-hall. — **Fig. 2d.** cBOT trajectories under STL constraints in *cross-hall* (shorter, smoother).

Outdoor Field Experiments with Two ASVs

Two-ASV planned trajectory (a). — **Fig. 3a.** Planned trajectory (two-ASV scenario).

Two-ASV planned trajectory (b). — **Fig. 3b.** Planned trajectory (two-ASV scenario).

Two-ASV planned trajectory (c). — **Fig. 3c.** Planned trajectory (two-ASV scenario).

Two-ASV execution (d). — **Fig. 3d.** ASVs executing missions in the operational area.

Two-ASV execution (e). — **Fig. 3e.** ASVs executing missions in the operational area.

Two-ASV execution (f). — **Fig. 3f.** ASVs executing missions in the operational area.

Outdoor Field Experiments with Three ASVs

Three-ASV trajectory execution (a). — **Fig. 4a.** Trajectory execution where ASVs reach goals while avoiding fountain obstacles.

Three-ASV trajectory execution (b). — **Fig. 4b.** Trajectory execution where ASVs reach goals while avoiding fountain obstacles.

Indoor UGV Experiments

UGV trajectories (a). — **Fig. 1a.** STLcBOT applied to three UGVs navigating a cluttered indoor environment.

UGV trajectories (b). — **Fig. 1b.** Kinodynamically-constrained trajectories enabling accurate tracking and collision avoidance.

STLcBOT Ground Robot Experiments

STLcBOT Outdoor Experiments with Two ASVs

STLcBOT Outdoor Experiments with Three ASVs

BibTeX

@inproceedings{stlcbot2025,
  title     = {STL-Constrained Multi-Robot Trajectory Planning via Constrained Bayesian Optimization and Local Cost Map Learning},
  author    = {<add authors>},
  booktitle = {<venue>},
  year      = {2025},
  url       = {https://stlbot.github.io/}
}