Multi-Agent Temporal Logic Planning via Penalty Functions and Block-Coordinate Optimization
It provides a scalable optimization-based approach for multi-agent STL planning, which is a known bottleneck in robotics and autonomous systems.
The paper addresses the computational challenges of multi-agent planning under Signal Temporal Logic (STL) by formulating it as an optimization problem solved via Block-Coordinate Gradient Descent (BCGD), achieving scalable synthesis with convergence guarantees. The method is validated on complex multi-robot scenarios.
Multi-agent planning under Signal Temporal Logic (STL) is often hindered by collaborative tasks that lead to computational challenges due to the inherent high dimensionality of the problem, preventing scalable synthesis with satisfaction guarantees. To address this, we formulate STL planning as an optimization program under multi-agent STL constraints and introduce a penalty-based unconstrained relaxation that can be efficiently solved via a Block-Coordinate Gradient Descent (BCGD) method, where each block corresponds to a single agent's decision variables, thereby mitigating complexity. By utilizing a quadratic penalty function defined via smooth STL semantics, we show that BCGD iterations converge to a stationary point of the penalized problem under standard regularity assumptions. To enforce feasibility, the BCGD solver is embedded within a two-layer optimization scheme: inner BCGD updates are performed for a fixed penalty parameter, which is then increased in an outer loop to progressively improve multi-agent STL robustness. The proposed framework enables scalable computations and is validated through various complex multi-robot planning scenarios.