Multi-Agent Collaboration for PrSTL Specifications with Temporal Collective Counting Operators
Yicheng Quan, Yan Yang, Zhijie Liu, Zhongjiao Shi
AI summary
Problem
Conventional Probabilistic Signal Temporal Logic lacks temporal operators to describe cumulative properties in multi-agent systems under uncertainty, while existing stochastic methods struggle with tractable variance propagation or lack formal guarantees for such tasks.
Approach
The authors introduce a Temporal Collective Counting Operator to formalize cumulative collaborative tasks within PrSTL, then leverage Polynomial Chaos Expansion to propagate uncertainty and transform probabilistic constraints into a Mixed-Integer Second-Order Cone Program, supplemented by a constraint relaxation mechanism to mitigate approximation conservatism.
Key results
- Introduction of the Temporal Collective Counting Operator for cumulative multi-agent specifications
- Formulation of the planning problem as a Mixed-Integer Second-Order Cone Program via Polynomial Chaos Expansion
- Derivation of a sufficient condition for TCCO satisfaction as a Boolean combination of atomic chance constraints
- Development of a constraint relaxation mechanism to balance formal guarantees with computational feasibility
Why it matters
Enables reliable, mathematically rigorous planning for complex collaborative robotic missions under uncertainty, bridging formal verification methods with practical multi-agent control.
Abstract
We address the collaborative path planning problem for multi-agent systems with heterogeneous capabilities, subject to uncertainty and operating under complex task specifications. Conventional Probabilistic Signal Temporal Logic (PrSTL) frame- works exhibit significant limitations in describing multi-agent col- laborative tasks with temporally cumulative properties. To address this challenge, we extend the PrSTL framework by introducing a Temporal Collective Counting Operator to characterize such spatio-temporal specifications. We then formulate the multi-agent collaborative planning problem under dynamics uncertainty as a Mixed-Integer Second-Order Cone Program. This formulation leverages PrSTL to specify tasks with cumulative temporal prop- erties, while employing Polynomial Chaos Expansion to propagate uncertainty. Finally, we propose a constraint relaxation mechanism toaddresstheconservatismintroducedbyformulatransformations and probabilistic constraints’ approximation.