Multi-Agent Temporal Logic Planning via Penalty Functions and Block-Coordinate Optimization

Technical Summary: Multi-Agent Temporal Logic Planning via Penalty Functions and Block-Coordinate Optimization

Problem Statement
The paper addresses the challenge of synthesizing control policies for Multi-Agent Systems (MAS) subject to collaborative tasks encoded in Signal Temporal Logic (STL). While STL offers a powerful framework for specifying complex spatio-temporal and logical constraints with quantitative robustness semantics, planning for multiple agents remains computationally formidable. Existing approaches, such as distributed Model Predictive Control (MPC) or sequential planning, often suffer from scalability issues, rely on restricted STL fragments, or require the prior existence of feasible solutions. The core difficulty lies in the high dimensionality of the joint decision space and the non-smooth, coupled nature of multi-agent STL constraints, which hinder scalable synthesis with satisfaction guarantees.

Methodology
The authors propose a scalable, optimization-based framework that integrates smooth STL semantics, penalty functions, and Block-Coordinate Gradient Descent (BCGD). The methodology proceeds through the following stages:

1. Smooth Approximation: The non-smooth STL robustness function, which involves $\min$ and $\max$ operators, is approximated using smooth functions parameterized by a scalar $\Gamma$. This under-approximation allows the use of gradient-based methods. A key theoretical insight (Proposition 1) establishes that for formulas involving at least two cliques, satisfying the smooth robustness constraint ($\ge 0$) implies satisfying the original non-smooth STL constraint ($> 0$).
2. Penalty Relaxation: The constrained optimization problem (minimizing a separable cost subject to STL constraints) is transformed into an unconstrained problem using a quadratic penalty function. The penalty term penalizes violations of the smooth robustness condition.
3. Block-Coordinate Optimization (BCGD): The unconstrained problem is solved using a BCGD method. This approach exploits the separability of the cost function across agents. In each iteration, the algorithm updates a subset of agents (blocks) while holding others fixed. This decomposition mitigates complexity by allowing agent-level computations. The method includes a specific step-size selection rule (Armijo-type) and a block selection strategy.
4. Two-Layer Penalty Scheme: To ensure feasibility for the original problem, the BCGD solver is embedded within a two-layer optimization scheme. An inner loop optimizes the penalized objective for a fixed penalty parameter $\lambda$, while an outer loop iteratively increases $\lambda$ to progressively enforce the STL constraints.

Key Contributions

• Scalable Framework: The paper introduces the first framework to systematically integrate smooth STL semantics, block-coordinate optimization, and penalty functions for multi-agent STL synthesis under arbitrary collaborative tasks.
• Convergence Guarantees: Under standard regularity assumptions (convexity of agent costs, feasibility of the problem), the authors prove that the BCGD iterations converge to a stationary point of the penalized problem.
• Feasibility Conditions: Theorem 1 provides a conditional guarantee that the proposed penalty method yields a feasible solution for the original non-smooth STL problem, provided the limit point of the algorithm has zero penalty and the number of cliques is at least two.
• Modular Architecture: The approach decouples the complexity of the multi-agent specification from the solver, enabling efficient computations at the agent level.

Experimental Results
The framework was validated through numerical experiments involving ten robots with both linear and unicycle dynamics. Three scenarios were tested:

1. R2AM: Robots perform individual tasks (obstacle avoidance, reach goals) and collaborative meeting tasks.
2. R2AMCA: R2AM augmented with global inter-agent collision avoidance.
3. RURAMCA: A complex scenario connecting reach specifications with an "until" operator alongside collision avoidance and collaborative meetings.

The proposed BCGD-Penalty Method (BCGD-PM) was benchmarked against an LBFGS-based implementation within the same penalty framework.

• Feasibility: BCGD consistently found feasible solutions across all 100 randomized initial condition permutations for all scenarios and dynamics types. In contrast, LBFGS failed to find feasible solutions in a significant portion of runs (e.g., 32% failure rate for R2AMCA with linear dynamics).
• Runtime: While LBFGS was faster on average for the problems it could solve, BCGD demonstrated a significantly lower 95%-quantile solve time, indicating more reliable performance.
• Scalability: The method showed favorable scalability with respect to the time horizon and the number of agents. Runtime scaled gracefully with the horizon and exhibited subquadratic-to-moderate growth when doubling the number of agents and cliques.
• Comparison to Prior Work: The proposed algorithm significantly outperformed the authors' earlier methods in runtime for the R2AM scenario and succeeded in finding solutions for R2AMCA and RURAMCA where previous methods failed within a 10,000-second timeout.

Significance and Claims
The paper claims that this framework addresses a critical open problem in multi-agent planning: developing scalable methods that handle complex collaborative tasks while maintaining computational tractability under a broad class of STL formulas. By leveraging the structure of the problem through block-coordinate updates, the method enables agent-level computations that remain tractable despite the complexity of the global specification. The authors position this work as a foundational step toward reactive STL planning for time-varying MAS structures and tasks, noting that the method is implemented in Python using JAX and is open-source. The work does not claim global optimality guarantees due to the non-convex nature of the problem but emphasizes the practical effectiveness and robustness of the approach in generating feasible, high-quality trajectories.