Generalizable Multi-Agent Planning from Signal Temporal Logic Specifications via Diffusion

AI summary

Overview

Research area: Multi-Agent Systems — specifically multi-robot motion planning under Signal Temporal Logic (STL) specifications, combining generative diffusion models with differentiable logic and graph-based safety control.

Technical level: Advanced. The paper assumes familiarity with temporal logic semantics, diffusion/score-based generative models, control barrier functions, and mixed-integer optimization baselines.

Scope: The paper proposes and evaluates Diff-MA, a diffusion-based planner that generates diverse, collision-free joint plans for many agents satisfying STL and team-level CaTL+ specifications at test time without retraining.

What This Paper Is About

Multi-agent systems such as drone swarms, autonomous cars, and warehouse robots must satisfy rich temporal tasks while avoiding collisions, and Signal Temporal Logic (STL) is an expressive way to encode those tasks. Existing methods face a hard trade-off: optimization-based STL planners handle arbitrary specifications but collapse computationally as the number of agents grows, while learning-based planners scale well but fail when deployment-time objectives differ from training objectives, and typically cannot assign different specifications to different agents or coordinate team-level objectives. The paper's goal is to build a planner that is simultaneously scalable, generalizable at test time, and diverse in the plans it produces.

Key Contributions

1. Diff-MA, a diffusion-based multi-agent planning framework that generates diverse, jointly-optimized trajectories sampled from a single-agent diffusion model, with multi-agent coupling injected at test time rather than learned in the prior.
2. Simultaneous satisfaction of MA-STL-A and team-level CaTL+ specifications while incorporating inter-agent collision avoidance, using a guidance function that combines an STL robustness term with an achievability loss derived from closed-loop GCBF+ rollouts.
3. Test-time generalization to new specifications whose predicates are sampled within the trained goal region, without requiring retraining.
4. A detailed evaluation study on the DubinsCar benchmark plus a demonstration on N=10 differential-drive robots via the Robotarium test-bed, establishing utility along three axes defined by the authors: C1 Scalability, C2 Generalizability, C3 Diversity.

Main Findings

• Success and speed against MILP baselines: Diff-MA on average exceeds STLPY-SA by 20%, with a notable relative success rate improvement of 36% for the crowded map (N=32), while being 55x faster with zero retraining.
• Planning time: Table I lists Diff-MA at roughly 1 s average planning time to generate a single end-to-end plan for novel agent placements, versus >10 s for PWL MA-STL, STLPY-SA, and Gradient, and <0.1 s for GNN-ODE.
• Capability coverage (Table I): Diff-MA is the only listed planner marked as supporting heterogeneous specifications, multi-agent awareness, complex specifications (N>5), scaling to large N (at least 32 agents), plan diversity, and generalization at once. GNN-ODE lacks heterogeneous specs and generalization; PWL MA-STL, STLPY-SA, and Gradient lack multi-agent awareness and scaling; Diff-SA lacks multi-agent awareness.
• Diversity improves with diffusion: In the homogeneous Dubins car setting at N=16, Diff-MA reaches 1.09 agents per cluster for Branch versus 3.81 for GNN-ODE and 2.35 for STLPY-SA, and 1.08 for Cover versus 6.40 (GNN-ODE) and 3.02 (STLPY-SA). Path Overlap is 0.00% for Diff-MA on Branch and Cover, versus 0.08% and 0.18% for GNN-ODE and 0.00% for STLPY-SA. For Loop at N=16, Diff-MA is 1.04 agents per cluster versus 4.40 (GNN-ODE) and 3.40 (STLPY-SA). (The provided table content is truncated after this row.)
• Increased diversity reduces safety violations: By using diffusion models, the method naturally enhances plan diversity, which the authors state significantly reduces safety-related violations such as collisions among agents.
• Generalization to unseen predicates: The diffusion model is trained only on single-agent trajectories over a fixed predicate set, yet at inference it handles arbitrary compositions of rectangular predicates whose centers are sampled anywhere in the 4.0 x 4.0 unit trained region with sizes drawn uniformly from [0.5, 1.0] units.
• Motivation for the approach: Pairwise collision-avoidance constraints introduce O(binomial(N,2)·K²) additional decision variables, and prior work reports timeouts even for simple STL tasks with N=5 single-integrator agents in 2-D space; GNN-ODE only demonstrated results up to N=32 agents in a nonlinear setting.

Methodology in Plain English

The approach has two stages. First, the authors fix a set of rectangular predicate regions placed evenly on a 4.0 x 4.0 unit grid (9 predicates in total), and collect a training dataset by sampling 10000 trajectories with the STLPY-SA planner on a sequence specification using 3 randomly sampled predicates. A single-agent diffusion model is then trained supervised on state-goal trajectories, using the EDM (Karras et al.) formulation, with no STL guidance during training.

Second, at test time, the trained single-agent model is used to jointly denoise plans for all agents in the system. Each denoising step produces a denoised trajectory estimate, from which the authors compute a guidance gradient that pushes the plan toward satisfying the specification and toward being trackable. The guidance function is a weighted combination of an STL loss (the negative robustness score, summed per agent for MA-STL-A, or evaluated jointly for CaTL+ since CaTL+ robustness is not agent-decomposable) and an achievability loss measuring the tracking error between the denoised trajectory and a trajectory sampled using the GCBF+ controller. Because computing the achievability term is expensive, it is applied only in the last fraction of diffusion steps (for example 20%), avoiding wasted computation on initial near-Gaussian samples. The agent's current state is imposed each denoising step by inpainting the first plan step.

To handle the fact that diffusion samples can still violate STL constraints — related work reports only 50-80% success, worsening in multi-agent settings — the sampler resamples each agent's plan before execution up to N_sample times until robustness exceeds a threshold. Each resampling iteration draws B = 8 candidate joint plans in one reverse pass and keeps the one with highest exact robustness, never mixing agents across candidates. Accepted plans are frozen and excluded from further updates, so the accepted set is monotonically non-decreasing. The authors implement the sampler with a JAX-based, JIT-compiled vectorization for fast inference, and embed GCBF+ both in guidance and in execution for safety.

Why This Matters

Impact on research. The work attacks a documented trade-off between scalability and generalizability in multi-agent STL planning, showing that test-time guidance of a single-agent generative prior can substitute for retraining. It extends generative planners to heterogeneous per-agent specifications and to team-level CaTL+ tasks with redundancy (m>1) and inter-task avoidance, and it argues that plan diversity is itself a safety mechanism because dispersed plans reduce congestion-induced deadlocks and collisions. The authors are explicit about limits: acceptance of a plan certifies STL satisfaction at the plan level only, while the achievability condition is promoted through soft guidance rather than formally guaranteed, and is assessed empirically through reported success rates.

Real-world applications (as named in the paper):

• Drone swarms
• Autonomous cars
• Warehouse robots
• Multi-robot tasks such as coverage, patrolling, and surveillance, plus a demonstrated differential-drive robot task on the Robotarium test-bed

Industry relevance. Practitioners deploying fleets need planners that generate a plan in roughly a second, scale to at least 32 agents (evaluated up to N=128 on a larger map), accept new task specifications at runtime without hours of retraining, and assign different goals to different robots. Warehousing, logistics, inspection, and autonomous mobility are all directly implicated, and the released code and videos lower the barrier to reproduction.

Future Directions

• Formal enforcement of achievability: The achievability condition in Definition 1 is currently promoted through soft guidance rather than formally guaranteed. Closing this gap with hard guarantees would strengthen deployment claims.
• Obstacles and richer environments: GCBF+ supports agent-agent and agent-obstacle interactions, but the authors focus on agent-agent interaction due to a known deadlock limitation when obstacles are present. Extending to cluttered environments is an open problem.
• Generalization beyond the trained goal region: Test-time generalization is demonstrated only for predicates sampled within the 4.0 x 4.0 unit region covered during training. Handling predicates outside that region, or entirely new predicate shapes, is not addressed.
• Scaling and inference cost: Diffusion inference is inherently slow, and multi-agent joint sampling compounds this cost; the paper reports scalability up to N=128 on a larger map for the Mixed specification, leaving higher agent counts and further inference acceleration as open questions.

Target Audience

Robotics and multi-agent systems researchers, graduate students and practitioners working on temporal-logic planning, neuro-symbolic methods, and diffusion-based trajectory generation, and engineers building fleet-control or multi-robot deployment stacks who need scalable planning with runtime specification changes. Readers without a background in STL semantics, diffusion samplers, or control barrier functions will find the method and evaluation demanding.

Authors’ abstract

Multi-agent systems in the real-world (e.g., drone swarms, autonomous cars, warehouse robots) must satisfy rich, temporal tasks while avoiding collisions. Signal Temporal Logic (STL) elegantly encodes such objectives, but current STL planning methods face critical limitations. State-of-the-art optimization-based approaches can handle arbitrary STL specifications but struggle with scalability, becoming computationally impractical as the number of agents grows. Learning-based methods efficiently handle a large number of agents with rapid planning times but fare poorly when deployment-time objectives differ from those used during training, and do not support planning tasks that require different specifications to be ascribed to different agents (i.e., heterogeneity) or team-level specifications requiring coordination of multiple agents. This fundamental trade-off between generalizability and scalability presents a challenge for realizing multi-agent STL planning algorithms in practice. To overcome this challenge, we introduce a new diffusion method for multi-agent planning with STL specifications. Using a differentiable approximation of STL, we integrate the STL gradient in the denoising process, making our approach generalizable to novel formulas whose predicates are placed anywhere within the goal region covered during training, while achieving the same scalability as existing learning-based methods. Our method supports heterogeneous specifications, and by using diffusion models, naturally enhances plan diversity, thereby significantly reducing safety-related violations (e.g., collisions) among agents. A detailed evaluation study justifies the utility of STL-guided diffusion-based multi-agent planners for constructing generalizable, scalable, and diverse plans. Videos and code are available at https://www.jeappen.com/diff-ma-stl/ and https://github.com/jeappen/diff-ma-stl .