PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Joe Eappen, Zikang Xiong, Shreyash S. Iyengar, Suresh Jagannathan

arXiv:2608.29490v1cs.MAcs.AIcs.RO

TL;DR

Existing multi-agent STL planners trade scalability against generalizability, heterogeneity, and coordination. DIFF-MA uses STL-guided diffusion to generate diverse, safety-aware joint plans from single-agent training data. Experiments report stronger success, faster planning, reduced collision shares, and generalization to new specifications without retraining.

  • Problem

    Existing optimization-based planners scale poorly, while learning-based methods may lack heterogeneous and team-level specifications or require retraining for new deployment-time objectives.

  • Method

    DIFF-MA guides diffusion-based joint trajectory generation with differentiable STL objectives, achievability, and multi-agent safety constraints.

  • Results

    DIFF-MA achieves 20% higher average success than STLPY-SA while planning 3×–200× faster, and reaches a 36% relative success increase at N = 32.

  • Takeaways & Limitations

    The approach combines test-time specification generalization, heterogeneous and team-level planning, scalability, and diverse trajectories within one multi-agent planner.

Abstract

from arXiv · show

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 .

I. INTRODUCTION

Multi-agent STL planning must balance rich temporal specifications, collision avoidance, scalability, heterogeneous objectives, and plan diversity. DIFF-MA addresses these goals with diffusion-based, STL-guided planning that generalizes to new predicates at runtime.

  • Motivation: Optimization-based STL planners handle complex specifications but scale poorly as agent count and specification complexity increase.Pairwise collision constraints add decision variables, with prior work reporting timeouts for N = 5 agents.
  • Motivation: Learning-based planners can scale to many agents but may require homogeneous specifications and retraining for new deployment-time formulas.The cited GNN-ODE variant supports different agent counts and positions but not heterogeneous tasks or zero-shot specification changes.
  • Design goals: The paper identifies scalability, generalizability to different goals and new formulas, and diversity as three desired planner characteristics.Diversity is motivated by the need to reduce congestion from similar trajectories.
  • Proposed approach: DIFF-MA uses a diffusion-based framework to generate diverse, jointly optimized trajectories while satisfying per-agent, team-level, and collision-avoidance specifications.The framework supports MA-STL-A and CaTL+ specifications and generates plans from a trained single-agent diffusion model.
  • Proposed approach: DIFF-MA enables test-time generalization to new specifications whose predicates are sampled within the trained goal region without retraining.The training predicates are rectangular regions, and the proposed method is designed to handle new predicate placements within that region.

Related Work

Prior work combines symbolic planning, differentiable STL optimization, safety filtering, and generative trajectory models, but existing approaches retain important assumptions about tracking, specification guidance, or multi-agent coordination.

  • STL and safety planning: Optimization, automata, and differentiable planners synthesize or optimize STL trajectories, while controllers and safety filters handle execution-level safety.The related approaches include robustness-gradient optimization, hierarchical reinforcement learning, classical planners, and graph control barrier functions.
  • Generative planning: Diffusion and flow-matching models provide priors for robot policies and trajectory synthesis, but direct STL guidance has achieved only moderate single-agent success.The paper positions its method as adapting diffusion sampling for STL-guided multi-agent planning.
  • Multi-agent safety: Existing multi-robot path-planning work may assume perfect tracking for collision avoidance, an assumption that is difficult to satisfy in practice.The paper contrasts this assumption with its use of a safety-aware controller during planning and execution.

A. Multi Agent Systems with Partial Observability

The paper models partially observable multi-agent systems with shared dynamics, formalizes STL and multi-agent specifications, and uses graph-based control barrier functions to preserve inter-agent safety.

  • Multi-agent systems: Each agent observes its own state and nearby agents within sensing radius R, then maps neighborhood information to actions through a local policy.The system trajectory contains all agent states, while each policy uses the agent’s sensed neighborhood.
  • Signal Temporal Logic: STL combines Boolean and time-bounded temporal operators, with robustness ρ measuring how strongly a trace satisfies or violates a specification.Differentiable robustness enables gradient-based optimization of STL objectives.
  • Multi-agent specifications: MA-STL-A requires every agent’s individual STL specification to hold while also requiring collision avoidance among agents.The specification is formed by combining per-agent formulas across the N agents.
  • Team specifications: CaTL+ expresses team tasks by requiring at least m agents to satisfy an inner formula, with outer Boolean logic combining tasks.The framework covers independent per-agent tasks when m=1 and interdependent team tasks when m>1.
  • Graph-based safety: GCBF+ represents agents and local interactions as a graph and uses a graph neural network to parameterize local control policies.Edges connect agents within sensing radius R, and the controller handles agent-agent and agent-obstacle interactions.
  • Graph-based safety: Under the stated barrier conditions, the zero-superlevel set of h is forward invariant, preventing trajectories that start there from entering the unsafe set.The safe set is defined by inter-agent separation requirements, with the unsafe set as its complement.

D. Diffusion Models as Trajectory Generators

The paper frames diffusion models as generators of state trajectories for multi-agent planning, with centralized goal-sequence planning and decentralized execution under safety, STL-satisfaction, and achievability requirements.

  • Diffusion Models as Trajectory Generators: Diffusion models learn to reverse a noise-adding process so they can generate high-dimensional data samples, including state trajectories for planning.The trajectories are intended to adhere to system dynamics and satisfy specified constraints or objectives.
  • Problem Formulation: The problem formulation considers either MA-STL-A or CaTL+ specifications over N agents with positions constrained to a workspace.MA-STL-A combines individual agent specifications, while CaTL+ can encode team-level coordination requirements.
  • Problem Formulation: The planner produces per-agent goal sequences of length T over a planning horizon, while execution is decentralized under local controllers.The centralized planner is denoted πψg and the local execution policies are (πi)i∈N.
  • Problem Formulation: A valid solution must maintain pairwise separation greater than 2r throughout the horizon, satisfy the joint STL specification, and keep tracking deviation below ϵ.For MA-STL-A, STL satisfaction reduces to satisfying each individual agent specification.

IV. APPROACH

DIFF-MA trains a diffusion prior on single-agent trajectories and injects multi-agent coupling at test time through STL and achievability guidance. This design supports new rectangular-predicate STL objectives within the trained goal region.

  • IV. APPROACH: DIFF-MA first trains a diffusion model on single-agent trajectories covering a set of STL predicates, then jointly generates multi-agent trajectories at test time.Multi-agent coupling is introduced during inference rather than learned in the diffusion prior.
  • IV. APPROACH: The test-time planner guides generated plans toward STL satisfaction while respecting multi-agent safety constraints.GCBF+ is embedded in guidance through closed-loop rollouts and is also used during execution.
  • IV. APPROACH: DIFF-MA enables safe test-time generalization to arbitrary compositions of rectangular predicates placed within the goal region covered during training.The new STL objective is supplied at test time rather than fixed during training.
  • IV. APPROACH: The training data comprise trajectories for a single agent achieving randomly sampled sequences of rectangular predicate goals over a time horizon Th.The predicate regions are fixed first, and trajectories are collected using the GCBF+ controller.
  • IV. APPROACH: Plan sampling starts from a random noise trajectory and iterates through denoising steps using specified noise, guidance, and diffusion parameters.Algorithm 1 lists the denoiser, guidance function, noise levels, and diffusion steps as inputs or parameters.
  • IV. APPROACH: The denoising procedure estimates a denoised trajectory and applies guidance gradients before Euler and second-order updates.The listed updates include MA-STL-A guidance and a second-order correction over N agents.
  • IV. APPROACH: The model is trained to generate state-goal trajectories τi = (τsi, τgi) for an agent i.The planner later uses these learned trajectory representations to generate multi-agent plans.

B. Guiding Diffusion Models with STL Objectives

STL-guided diffusion uses gradients of a differentiable STL objective together with an achievability loss to steer denoised trajectories toward satisfying specifications and remaining executable by the agents.

  • Guidance Mechanism: The denoised trajectory estimates the gradient of STL robustness, which guides each diffusion step toward satisfying the STL objectives.The current state is imposed by overwriting the first plan step after each denoising step.
  • Guidance Mechanism: The guidance function combines STL robustness with achievability so plans satisfy specifications while remaining achievable under the GCBF+ controller.The two terms are weighted by positive coefficients λSTL and λach.
  • STL Loss: For agent-decomposable specifications, the STL loss is the sum of negative robustness scores across agents.For CaTL+ specifications, which are not agent-decomposable, the loss instead uses the joint multi-agent robustness score.
  • Achievability Loss: The achievability loss measures tracking error between the denoised trajectory and a trajectory sampled using the GCBF+ controller.This makes the generated trajectory cognizant of system dynamics and controller capabilities in the presence of other agents.
  • Achievability Loss: Because trajectory-distance computation is expensive, achievability guidance is applied only during the final fraction of diffusion steps.The paper gives k_ach, such as 20%, as an example of this final fraction.

C. Applying Diffusion Planning to Multi-Agent Systems

The implementation accelerates joint diffusion sampling with JAX JIT vectorization and resamples individual plans until their STL robustness exceeds a positive threshold.

  • Implementation: JAX-based JIT-compiled vectorization is used to speed up the multi-agent implementation of the diffusion sampling algorithm.The paper notes that diffusion inference is inherently slow and joint sampling compounds this cost.
  • Implementation: Each agent’s plan is resampled up to Nsample times until its STL robustness exceeds ϵsample > 0.The resampling time is included in the reported planning time.

V. EXPERIMENT SETUP

The experiments evaluate DIFF-MA on multi-agent navigation across scalability, generalizability, and diversity, using DubinsCar and comparisons with single-agent planning baselines. Performance is measured over 30 seeds with success rate, planning time, and time-to-reach, including tests up to 128 agents.

  • Experiments assess scalability, generalizability, and diversity as the evaluation criteria.
  • DIFF-MA is validated on the nonlinear DubinsCar benchmark with a shared collision-avoidance controller and additional robot demonstrations.
  • The study varies agent count and compares DIFF-MA with STLPY-SA, GRADIENT, and DIFF-SA single-agent planners executed independently.
  • 30-seed evaluations report mean planning time, success rate, and time-to-reach, where success requires STL satisfaction and collision avoidance.
  • Additional studies examine achievable-loss weighting, per-agent execution delay, and scalability on a map twice the grid size with up to N = 128 agents.

B. Generalizing to Different Goals (C2)

The goal-generalization experiments train on rectangular predicates arranged in a grid, then test arbitrary predicate locations within the trained region and team-level tasks with heterogeneous specifications. They also examine larger-scale performance on a map with up to 128 agents.

  • Training and goal generalization: The diffusion dataset uses 9 rectangular predicates on a 4.0 × 4.0-unit grid and 10,000 STLPY-SA trajectories from randomly sampled three-predicate sequences.
  • Training and goal generalization: At inference, predicate centers and sizes are sampled arbitrarily within the 4.0 × 4.0-unit training space to test generalization to unseen predicates.
  • Heterogeneous specifications: Heterogeneous evaluation covers sequence, coverage, loop, signal, branch, and mixed STL task structures with distinct specifications across agents.
  • Team-level specifications: CaTL+ experiments test Choice-Seq and Redundant team tasks with redundancy and inter-task avoidance, where independent planning cannot anticipate agents converging on shared regions.
  • Team-level specifications: DIFF-MA requires no task-to-agent allocation, while baselines include global MILP allocation and oracle-assigned single-agent planning.
  • High-agent-count evaluation: On the larger-map Mixed evaluation, success degrades at high agent counts and matches STLPY-SA at N = 128, while planning time increases modestly.

C. Diversity in Generated Plans (C3)

DIFF-MA improves safety and scalability by modeling multi-agent interactions during planning while generating more dispersed trajectories. The results also expose trade-offs in time-to-reach, execution delay, and performance at very high agent counts.

  • Performance and safety: DIFF-MA averages 20% higher success than STLPY-SA and plans 3×–200× faster, achieving at least 84% success with 32 agents.
  • Performance and safety: At N = 32, DIFF-MA's collision share is 10.9%, versus 34.4% for STLPY-SA and 27.5% for DIFF-SA, while plannerside STL failures remain minimal.
  • High-density limitations: At N = 128, DIFF-MA's safety rate falls to 42%, compared with 95% at N = 32, as dense scenarios expose limitations in collision avoidance and predicate-space coverage.
  • Achievable-loss ablation: Increasing λach lowers time-to-reach by 17.37% and raises success by 2.37% in dense 32-agent settings.
  • Execution delay: DIFF-MA incurs an average per-agent delay of 1.3–1.9× the isolated STLPY-SA single-agent time during runtime maneuvering.
  • Team specifications: On team specifications, DIFF-MA maintains near 90% average success and beats the best STLPY-SA baseline by over 30% at N = 32 without explicit allocation.
  • Plan diversity: DIFF-MA produces diverse trajectories with low path-overlap values, whereas GNN-ODE and STLPY-SA tend to cluster agents on similar paths.

VII. CONCLUSION

DIFF-MA uses STL-guided diffusion to generate safe multi-agent plans, with reported scalability matching learning-based methods and stronger performance and diversity. Its current scope is bounded by dynamics-model assumptions, obstacle-induced deadlocks, scalability beyond 32 agents, and limited specification expressivity.

  • Assumptions: The method assumes accurate system dynamics for GCBF+ safety control and differentiable plan-achievability evaluation.The authors note that model-free techniques could relax these assumptions.
  • Obstacle interaction: Scalability is demonstrated primarily in obstacle-free settings, while cluttered environments produce modest success-rate reductions.The paper attributes this limitation to interactions between rich temporal objectives and obstacle handling.
  • Obstacle interaction: Rich temporal objectives can cause decentralized deadlocks because barrier functions prioritize instantaneous safety over trajectory-level guarantees.The authors identify controllers reasoning about global or cumulative safety as a direction for improvement.
  • Scalability: Effective coordination beyond 32 agents on fixed maps and predicate sizes likely requires communication or distributed planning.Faster diffusion inference and conditional-flow models are proposed as ways to reduce planning-time growth while trading speed against plan diversity.
  • Task complexity: The method focuses on MA-STL-A and CaTL+ specifications with asynchronous timing rather than joint-state specifications or synchronized temporal relations.Explicitly modeling delays is also identified as a direction for broader applicability.
Loading 2608.29490v1…