Scaling Safe Multi-Agent Control for Signal Temporal Logic Specifications

Authors: joe  eappen
zikang  xiong
dipam  patel
aniket  bera
suresh  jagannathan
Venue: robot-learning_org_CoRL_2024_Conference
Published: 2024-06-07 07:21:28

Abstract: Existing methods for safe multi-agent control using logic specifications like Signal Temporal Logic (STL) often face scalability issues. This is because they rely either on single-agent perspectives or on Mixed Integer Linear Programming (MILP)-based planners, which are complex to optimize. These methods have proven to be computationally expensive and inefficient when dealing with a large number of agents. To address these limitations, we present a new scalable approach to multi-agent control in this setting. Our method treats the relationships between agents using a graph structure rather than in terms of a single-agent perspective. Moreover, it combines a multi-agent collision avoidance controller with a Graph Neural Network (GNN) based planner, models the system in a decentralized fashion, and trains on STL-based objectives to generate safe and efficient plans for multiple agents, thereby optimizing the satisfaction of complex temporal specifications while also facilitating multi-agent collision avoidance. Our experiments show that our approach significantly outperforms existing methods that use a state-of-the-art MILP-based planner in terms of scalability and performance.

Main paper: 
 introduction: 
 Learning-based methods have shown promise in multi-agent systems (MAS) for tasks such as collision avoidance, path planning, and task allocation [1, 2, 3, 4] . Extensions have also been developed to handle complex temporal tasks that may be described using formal languages such as Signal Temporal Logic (STL) [5, 6] and other temporal logics [7, 8, 9] ; unfortunately, these methods have well-known limitations in terms of scalability and performance.Signal Temporal Logic (STL) is a formal language for specifying complex temporal tasks that can be used to describe the behavior of agents in a multi-agent system. In many settings, including autonomous vehicles [10] , drones [11] , and robotic swarms [12] , it is essential to ensure that the agents satisfy complex temporal tasks such as sequentially visiting a series of locations while avoiding collisions with each other and the environment. Once the user has specified the task in STL, the task can be synthesized using formal methods [13, 14, 15] in certain environments; however, these methods often struggle to scale to complex specifications and environments. In response to these challenges, Mixed Integer Linear Programming (MILP)-based planners [16, 17] have been developed that can be used to plan over a range of STL specifications but still encounter difficulties with collision avoidance when a modest number such as 5 agents are considered (Table 1 ).Inspired by recent progress in learning-based planners [18, 19, 20] , we propose a novel approach to planning for multi-agent systems with STL specifications that can scale beyond these limitations demonstrated on up to 32 agents. More specifically, we introduce a Graph Neural Network (GNN) based planner using Neural Ordinary Difference Equations (ODEs) [18] g generates a sequence of goals for agent i given the initial state of the system G(0). The safety controller π i ensures that the agents do not collide while following the generated goals. A GNN encodes the graph representing the collective initial state of the system to yield an initial goal g i (0) (red) for each agent i. This goal g i (0) is fed into a Multi-Layer Perceptron (MLP) network to generate a new goal g i (1) (blue) which is fed back into the MLP network in a feedback loop. This is repeated for T -1 steps to generate a sequence of goals for the agent. The losses L STL and L ach are detailed in Sec. end-to-end on an STL objective to generate safe and robust plans for multiple agents that can be realized using a learnable MA collision avoidance controller ( [21] , Sec. 4.3). To scale up, we use the ODE-based component to plan general paths that satisfy the given task while using a GNN to model agent interactions in a scalable manner to achieve coordination between the agents as they determine which ODE-generated goal trajectory to follow. Our loss components (Sec. 4.1) allow the planner to find paths that satisfy the STL objective while also being achievable in the presence of collision avoidance maneuvers and agent-to-agent interactions.Our contributions are as follows: 1) We propose a novel scalable GNN-based planner (GNN-ODE) trained on an STL objective to generate safe and achievable plans for multiple agents. 2) We demonstrate the effectiveness of our approach on a range of STL specifications and show that our method can scale to a large number of agents and complex specifications beyond existing methods that use a state-of-the-art MILP-based planner with an average 65% improved success rate.Symbolic methods have been part of a recent resurgence as neuro-symbolic algorithms [22, 23] which aspire to combine the generalizability of neural methods with the ability of most symbolic systems to be interpretable and modifiable by human users. Notably, there have been efforts to integrate temporal logic constraints within learning-enabled controllers. In the field of Reinforcement Learning (RL), some examples of this are TLTL [24] , which defines a reward function from a logic specification and reward shaping mechanisms, [25, 26] which create automata modeling a similar specification and augment RL-based algorithms used for control. This has been extended to the Multi-agent domain, which had recent work [27, 9] showing possibilities of coordinating multiple agents with diverging objectives, as well as the benefits of distributing specifications among agents in terms of scalability.A key aspect of scaling control to higher-dimensional environments and robots involves efficiently incorporating a high-level planner. This involves decomposing complex logic planning from control tasks, allowing each component to focus on its specific role. The high-level planner focuses on logic-level planning, ensuring that the robot's actions adhere to complex specifications, such as those defined by STL. In contrast, the low-level controller acts as a tracker, executing the high-level plan accurately. Modern control methods have demonstrated this benefit as well from the burgeoning progress in Hierarchical RL [28, 29, 30, 31, 25] methods as well as the successful integration of classical planners with advanced control schemes, including RL controllers [32] .Symbolic techniques have appeared in robot motion planning as well with the use of Signal Temporal Logic (STL) to specify objectives for multi-robot systems, which can then be solved by MILP solvers [16] , graph-based algorithms [33] or sampling-based methods [34, 35] . Collision avoidance in these multi-robot systems is a challenging problem since one must also achieve the underlying objectives as well and a myriad of techniques [36, 37, 38, 21, 39] have attempted to handle this for general robot motion planning tasks. These existing methods, however, have not considered the generality of symbolic methods in specifying these objectives or quickly fail to scale as the specification dimension, robot complexity and number of agents increases. 
background: 
 Multi Agent Systems with Partial Observability We can represent a multi-agent system with N agents {1, 2, . . . N }. Each agent has its own state s i (t) ∈ S i ⊂ R n , can take an action u i (t) ∈ U i ⊂ R m , and the collective behavior of the agents is governed by a dynamics function s i (t + 1) = f i (s i (t), u i (t)). For simplicity, we assume all agents have the same dynamics function f i = f , state space S i = S, and action space U i = U. A trajectory τ is a sequence of states τ = (s(0), s(1), . . . , s(T h )) where T h is the time horizon, s(t) = (s 1 (t), . . . s N (t)), ū(t) = (u 1 (t), . . . u N (t)) and a policy π i is a function that maps the state of agent i to an action u i = π i (s i ). The state of the system is partially observable, meaning that each agent can only observe its own state and the states of other agents within its sensing range.Signal Temporal Logic Signal Temporal Logic (STL) integrates both first-order logic and timedependent modifications of linear temporal logic operators. The essential logical operators include ∧ (and), ¬ (not), ∨ (or), and ⇒ (implies). Time-dependent operators are ♢ [a,b] (eventually between times a and b), □ [a,b] (globally between times a and b), and U [a,b] (until between times a and b). STL formulas are defined as:ϕ := P | ¬ϕ | ϕ ∧ ψ | ϕ ∨ ψ | ϕ ⇒ ψ | ♢ [a,b] ϕ | □ [a,b] ϕ | ϕ U [a,b] ψ,where P is a predicate function mapping states to real values. Quantitative semantics [13, 40] of STL evaluate a robustness value, ρ(ϕ, τ ), which measures how strongly a state trace τ satisfies or violates ϕ. This robustness metric is differentiable, allowing for direct optimization of STL formulas through differentiable planners like neural networks.With regards to multi-agent systems with N agents, the MA-STL specification Ψ is composed from N individual STL specifications N i=1 ϕ i where ϕ i associates an STL specification for a single agent with index i. The MA-STL specification Ψ is satisfied if all individual STL specifications are satisfied and the agents do not collide.Graphical Representation for Multi-Agent Systems Graph Neural Networks (GNNs) are adept at modeling multi-agent systems by representing agents and obstacles as vertices within a graph G = (V, E). Each vertex in V = V a ∪ V o corresponds to either an agent or a static obstacle. Edges E encapsulate direct interactions between vertices, with specific emphasis on agent-to-agent and agent-to-obstacle connections. We adopt a distance-based adjacency criterion where an edge (v i , v j ) ∈ E exists if the Euclidean distance between vertices v i and v j does not exceed a predefined threshold R, for capturing the local topology of agents within this range [38] . A GNN processes the graph to produce a global embedding representing the collective state of the system. This global state is further processed through specialized readout functions r i , tailored to extract and map the global embedding to a specific set of actions u i for each agent [39, 21, 38] .Barrier Certificates Barrier certificates [41] are a useful technique to avoid robot collisions in MA systems [42] by forcing the state of the entire system to stay within the safe region. For a state space S ⊂ R n , let S u ⊂ S be the unsafe set and S s = S\S u the safe set, which contains the set of initial conditions S 0 ⊂ S s . Also, define the space of control actions as U ⊂ R m . For a dynamic system ṡ(t) = f (s(t), u(t)), a control barrier function h : R n → R satisfies:EQUATIONFor a control policy ( π : S → U ) and CBF (h), if (s(0) ∈ s | h(s) ≥ 0) and the above conditions are satisfied with (u = π(x)), then (s(t) ∈ s | h(s) ≥ 0) for all t ∈ [0, ∞). This implies that the state never enters the unsafe set (S u ) under π (see [41] ).Learning-based approaches for barrier certificates [37, 39, 38, 21] have been shown to scale in the number of agents beyond existing methods for known systems. Notably, a graphical perspective of the agents and their interactions can be used to model the system in a scalable manner (Sec. 4.3). 
problem statement: 
 Consider a MA-STL specification Ψ on N agents N = {1, 2, . . . , N }, where each agent is at a position p i (t) ∈ P ⊂ R n with n being 2 or 3 for 2D or 3D environments respectively. Assume that each state s i (t) of agent i can be directly mapped to its position p i (t), say the first n elements of s i (t) by a function filter pi : S → P. Similar to Zhang et al. [21] , we include a LiDAR based observation of n rays > 0 for each agent measuring the distance to the nearest obstacle in the environment with a sensing radius R > 0. The j-th ray of agent i is denoted as y i,j (t), where y i,j (t) ∈ R + is the distance to the nearest obstacle in the direction of the j-th ray at time t.The MA-STL motion planning problem We now establish the problem of motion planning for MA-STL in multi-agent systems. Essentially, the objective is to identify a set of reference goals that when followed satisfy a given MA-STL specification, while ensuring that there are no collisions between the agents. Suppose there are N agents involved, and the time bound is denoted by T h . The planner π ϕi g generates a sequence of goals τ gi = (g i (0), g i (1), . . . , g i (T )) for agent i with a given plan length T < T h . Each agent has a size radius represented by r, where r > 0. This means that when an agent is at position p ∈ W, it is entirely contained within a ball of radius r centered at p, denoted as B r (p). With these considerations, we can define the planning problem as follows:Definition 1 (Motion Planning in MA-STL) For a given MA-STL specification Ψ = N i=1 ϕ i and a set of N agents N , the motion planning problem is finding a distributed control policy π i and a planner π ϕi g for each agent i such that the following conditions are satisfied for closed-loop trajectories of agents in N with length T h :• (Safety -Agents) For all t ∈ [0, T h ], and for all i, j ∈ N where i ̸ = j, ||p i (t)-p j (t)|| ≥ 2r.• (Safety -Obstacles) For all t ∈ [0, T h ], and for all i ∈ N , y i,j (t) ≥ 2r for all j ∈ [n rays ].• (STL Satisfaction) There exists t 0 , t 1 , . . . , t T such that t i ∈ {0, . . . , T h } and t 0 < t 1 < . . . < t T such that the closed-loop trajectories τ = (s(t 0 ), s(t 1 ), . . . , s(t T )) of the agents satisfy the MA-STL specification Ψ i.e. ρ(Ψ, τ ) ≥ 0.• (Achievability) For all i ∈ N , given the goal trajectory τ gi of length T from π ϕi g , the gap [16] , a PWL plan with K = 6 segments (1 seq ) / K = 10 segments (2 seq). The X seq spec. has X sequential waypoints.D τg i (τ i ) = T t ′ =0 filter pi (s i (t t ′ )) -filter pi (g i (t ′ )) 2 < ϵ for a small ϵ ∈ R + . N Spec.Given an MA-STL specification Ψ on a system of N -agents we would like to provide a decentralized algorithm to execute a policy satisfying the specification with high probability.While we might assume a plan-then-execute technique [16] that finds a Piece-Wise Linear (PWL) path for each agent with K segments, such an approach quickly fails to scale with specification complexity and number of agents when considering collisions between agents at planning time. We posit this is primarily due to its collision avoidance mechanism that introduces O(C N 2 * K 2 ) new variables, which quickly blows up (where C N 2 = N (N -1)/2). Consider two goal regions A and B and a sequential STL specification requiring agents to visit A (viz. 1 seq) or to visit A then B (viz. 2 seq) while avoiding collisions. Table 1 demonstrates this by timing out (over 50 minutes) for a simple STL specification with N = 5 agents in a 2-D environment with Single Integrator dynamics as well as all specifications and number of agents considered in this work (Sec. 5, App. B) .Accounting for collision-avoidance independent of the objective is not novel [37, 39] , but, as we argue in this paper, in order to satisfy an STL specification, one must account for the temporal nature of the specification simultaneously with performing any collision-avoidance maneuvers. An alternative, as we propose, is to plan for the objectives while adjusting for collision avoidance by means of an iterative training procedure involving the safety controller (such as GCBF+) and the planner. 
approach: 
 Our approach integrates planning, control, and safety mechanisms in an end-to-end differentiable learning framework. We first introduce a differentiable STL framework using a neural network planner to maximize STL robustness (Sec. 4.1). For efficient multi-agent planning, we employ GNNs to model agent relationships and generate decentralized goal sequences (Sec. 4.2). To ensure collision avoidance, we define a safe set of states using GCBFs for robust control (Sec. 4.3). Finally, we discuss the training of our integrated system (Sec. 4.4).Signal Temporal Logic (STL) provides a robustness metric for a given trajectory that quantifies the level of satisfaction of a specification ϕ defined using the STL language (Sec. 2). Consider a NN planner π ϕi g that takes as input the current state of the system and outputs a sequence of goals τ gi = (g i (0), g i (1), . . . , g i (T )) for agent i with specification ϕ i . We can define a loss function that attempts to maximize the STL robustness score for the specification ϕ, given the waypoints from the planner. Prior work [19, 40] has used the differentiability of this score function to directly regularize a planner's waypoints for use by a given low-level controller π i (s i |g i ) which is goal-conditioned, i.e. targeted to reach the goal g i given the current state s i of agent i.For the planner architecture, similar to Xiong et al. [19] , we consider using π ϕi g to predict the deviation between subsequent waypoints ∆g i . Based on this, to maximize the probability of satisfying the STL specification given a controller π i , we define the loss function as:EQUATIONHere we consider two loss components, the first being the STL robustness score ρ(ϕ i , τ gi ) of the planned waypoints τ gi and the second being the tracking error D τg i (τ i ) of the controller π i with respect to the planned waypoints. The coefficients λ STL , λ ach > 0 are hyperparameters that control the relative importance of the two loss components (L STL and L ach ) in the overall loss function.The STL Loss L STL captures our objective, maximizing the STL robustness score of the planned waypoints τ gi with respect to the specification ϕ i . The achievable loss L ach on the other hand ensures that the controller π i can track the planned waypoints τ gi using a distance metric D τg i (τ i ) (Defn. 1) that extracts the positions from τ i using filter pi and minimizes a normed distance between the two, i.e.D τg i (τ i ) = T t=0 ∥filter pi (s i (kt)) -filter pi (g i (t))∥ 2 where k > 0, k ∈ Z + is afixed goal sampling rate during training such that kT = T h . In this paper, we consider the same specification ϕ i = ϕ and use the same planner for all agents. This enables easy generalization to different numbers of agents during testing and allows for a more scalable approach to planning. We leave the question of how to support different specifications among agents for future work. This leads to our overall loss function for the planner and controller asL π ϕ g ,π = N i=1 L π ϕ i g ,πi .Graphical models can be useful to scale collision avoidance in multi-agent systems [39, 21, 38 ] by modeling the system in a decentralized manner. Notably, by representing the agents as nodes and their interactions as edges, we can use Graph Neural Networks (GNNs) to process a graphical view of the system as described in Sec. 2 (Fig. 1 ).To handle the planning problem in multi-agent systems we describe the planner π ϕ g . We choose a GNN-based planner that takes as input the initial state of the system G(0) and outputs an initial goal g i (0) for agent i taking into account the relative positions of the agents. Next we feed this goal g i (0) into a 2-layer MLP to predict the deviation ∆g i . This process is repeated for T -1 steps to generate a sequence of goals for the agent given the initial state. By using this GNN-based structure, we can get this sequence of goals τ gi for each agent i in a single forward pass of the planner π ϕ g . As highlighted in Sec. 2, MA-STL can be thought of as independent single-agent STL specifications on the agents, albeit with an additional constraint on avoiding collisions between the agents. While collision avoidance during planning time is expensive (Sec. 3), we can attempt to plan for the objectives for a subset of the agents and use this plan with a safety scheme during run-time. Along these lines, during deployment, we use the GNN-ODE (Fig. 1 ) to generate a sequence of waypoints that we sequentially visit in a decentralized manner using the GCBF+ controller (Sec. 4.3). One should note this would not be straightforward if we had defined arbitrary STL specifications in the joint space of agents involving global coordination or synchronization of objectives [43, 9] . However, because this may detract from the overall objective due to collision avoidance maneuvers causing deadlocks, we update the planner iteratively by sampling the environment as detailed in Sec. 4.1 with the STL robustness score. In a sense, we "co-learn" the safety (GCBF+ controller, π i ) and objective (GNN-ODE, π ϕi g ) behavior which is a recurrent theme in recent work [19, 32] related to the safety of controllers in complex systems.Following [21] , we define the safe set S s ⊂ S N of an N -agent MAS as the set of MAS states s that satisfy the safety properties in Problem 1, i.e.,EQUATIONThen, the unsafe, set of the MAS S u = S N \ S s is defined as the complement of S s . We now define the notion of a GCBF [21] :Definition 2 (GCBF) A continuously differentiable function h : S M → R is termed as a Graph CBF (GCBF) if there exists an extended class-K ∞ function α and a control policy π i : S M → U for each agent i ∈ V a of the MAS such that, for all s ∈ S N with N ≥ M ,EQUATIONwhere for u j = π j (s Nj ) and set of neighbours N i of agent i in the MAS within sensing radius R, we haveEQUATIONFrom this definition, as a consequence of the results in Zhang et al. [21] , if we find a control policy π i and GCBF h such that Eq. ( 4) holds for all agents i and all states s ∈ S s , then the MAS will never enter the unsafe set S u under the control policy π i .By using the learning framework described in Sec. 4.2 and the safety mechanism in Sec. 4.3, we can train the planner and controller in an end-to-end differentiable manner using the loss function in Eq. (2) (Sec. 4.1). We use an iterative training loop to sample trajectories from the environment at different starting conditions and update the planner π ϕ g for a trained common GCBF+ controller π i = π using the loss L π ϕ g ,π . 
experiment setup: 
 Our experiments aim to validate the following two questions: Table 2 : Performance of the two planning schemes with the number of agents (N ) and specification complexity for the DubinsCar Environment. We note an average 65% improved success rate and highlight the best result in bold.• How scalable is a neural STL planner over competing methods in terms of the number of agents and specification complexity?• How do the distinct components of our planner (GNN and ODE) help with scalability?To demonstrate the robustness of our method to various specifications and agent models we execute our experiments on the following robot benchmarks: 2D single integrator dynamics (App. C.1), 2D non-linear Dubins Car model (Table 2 ), 2D Double Integrator dynamics (App. C.3) and a real-world 3D drone quadcopter setup moving in a fixed 2D plane (App. C.4).Our framework1 was built using JAX [44] based off GCBF+ [21] (Sec. 4.3) with all comparisons using this underlying collision avoidance controller. To demonstrate the effectiveness of our method, we compare it against a state-of-the-art MILP-based planner (STLPY [17] , Table 2 ) and an ablation of our planner without the GNN component (labeled ODE, Table 3 ).We evaluate the planner on a range of specifications: seq, cover, loop and branch. These STL specifications can be drawn to parallels in the real-world. A seq task is akin to a set of drones that need to visit a series of locations in a specific order at given time intervals for logging time-sensitive information. The cover task depicts a scenario where each drone measures a different sensor reading but must all cover the same locations within a time interval to consolidate information. The loop task captures a set of surveillance drones patrolling the same areas. Lastly, consider a scenario where drones are grouped into two separate rooms with two goals present in each. Here a branch task could represent a common specification applied to each agent that they must visit the goals of a particular room. For a more formal description of the specifications, refer to Appendix B.We sampled 30 random initial seeds for each experiment and report the mean planning time (in seconds), the percentage of runs in which the specification was satisfied (Finish Rate), the percentage of runs where the agent was safe (i.e. did not collide), the percentage of successful runs for each specification where the STL specification was satisfied and no collisions occurred, and time-to-reach (TtR) in number of steps (i.e. how long it took for the successful runs to complete the task). 
results: 
 Our results (Table 2 ) demonstrate how differentiable STL can be used to ensure agents achieve complex objectives while avoiding collisions in multi-agent systems.We first evaluate the scalability of our approach in the number of agents (N ) for the non-linear DubinsCar environment. From the results, we observe that the success rate decreases gradually as the number of agents increases, which is expected as the number of agents increases the complexity of the problem. The results show that the single agent view of STLPY proves unsuccessful especially in the N = 32 case where agent interactions are more prevalent. Notably our approach has a planning time that is 70-1000x faster than the MILP-based planner (STLPY) and does not blow up when considering a larger number of agents N . For certain specifications such as branch and loop, we observe that the MILP planner computation time is significant which can add up over different agent initializations. In contrast, our planner is able to generate a solution for all the specifications quickly and consistently for different agent initial positions, motivating our learning-based approach. We further note the effect in TtR when using our algorithm. We rationalize this trade-off because our method finds longer paths that allow goals to be reached by the GCBF+ controller, which is trained to avoid other agents. This inherently reduces the number of collisions which is often a greater priority. From our ablation study (Table 3 ) we note the impact of the GNN module especially in terms of a 28% impact in success rate for certain specifications such as seq which require increased coordination among agents. We can further reason that the impact in cover and loop of the GNN module is not as great since agents are not required to reach the goals within a strict order and thus require less coordination. With regards to the lower TtR of the successful runs, the lack of a GNN module may yield plans that can satisfy the specification efficiently but fail in terms of coordination between agents (affecting the overall success rate). 
limitations: 
 Model-based learning While a model-free approach to collision-avoidance [45, 32] would be more amenable to handle unknown environment dynamics, our approach is inherently model-based (as is GCBF [38, 21] , MACBF [37] and CAM [39] ). This is primarily due to the underlying controller and GCBF (akin to a barrier certificate), using the next state of the system while calculating the derivative for use in the loss function.Map Complexity, Homogeneity Additionally, since the approach is decentralized, complex maps requiring communication and coordination between agents may cause safety issues. As mentioned in [21] , it may be hard in dense regions to act in a decentralized manner thus necessitating the use of inter-agent communication. We have considered the homogeneous case in this work, where all agents have the same dynamics and STL specifications. However, in the heterogeneous case, agents may have different dynamics and STL specifications thus needing a more complex controller and a planner capable of generalizing to multiple goal positions or STL specifications. Our planner does not consider obstacles directly, although as demonstrated in the Appendix (Tables 5, 6 , 7), the GCBF+ controller to an extent provides inherent collision avoidance capabilities. Finally, the approach is limited by the complexity of the environment and the number of agents. While we have shown that the approach scales well with the number of agents, the complexity of the environment and the number of obstacles may cause the planner to fail to find a achievable plan. 
conclusion: 
 In this work, we have presented a novel approach to planning for multi-agent systems with Signal Temporal Logic specifications. Primarily we have shown that by using a differentiable STL robustness metric, we can optimize for the satisfaction of complex temporal specifications given a controller with MA collision avoidance capabilities. We demonstrate that by training a GNN-ODE planner with a carefully constructed loss function we can overcome the limitations of the plan-thenexecute approach and scale to complex specifications and large numbers of agents.  
 
 Appendix: Node features and edge features Following Zhang et al. [21] , the node features v i ∈ R ρv encode information specific to each node in our graph observation. Here, we set ρ v = 3 and use the node features v i to one-hot encode the type of the node as either an agent node, goal node or LiDAR ray hitting point node. The edge features e ij ∈ R ρe , where ρ e > 0 is the edge dimension, are defined as the information shared from node j to the agent at node i, which depends on the states of the nodes i and j. Since the safety objective depends on the relative positions, one component of the edge features is p ij = p j -p i . The remaining edge features can be set depending on system dynamics, such as, relative velocities for double integrator dynamics.All training procedures were ran on an AWS g4dn.xlarge instance or equivalent with 4 Intel Xeon-based CPU Cores and 16 GB of RAM with an Nvidia T4 GPU.Evaluation Details Since we consider objectives that require agents to navigate close to one another at/near termination subsequently blocking the goal locations (A,B,C,D in Table 4 ), safety rates were reported until the point an agent had completed their plan. This can be thought of as an alternative to the agents navigating to a 'safe' position upon completing their specification/plan. In a drone setting, we captured this behavior by landing the drones at an agent-specific location upon completing their specification.Planner Details For all plans, at any time step t, planning step t ′ , each agent i proceeded to the next waypoint g i (t ′ + 1) only when they reached goal g i (t ′ ) within some threshold distancer goal = 0.3 at a time t ≥ k(t ′ + 1)where k is the goal sampling interval (Sec. 4.1) . This allowed all agents to reach the waypoints in the plan without a strict time restriction on the plan duration. The asynchronous nature of our plans (among agents) fits our problem description (Defn. 1), specifically the STL Satisfaction criteria. We leave the setting where agents follow a synchronized plan to future work. For a given plan of length T with goal sample interval k (values in Table 4 ), the maximum trajectory length horizon during evaluation T h was 5kT .Here, we provide the details of each experiment environment as taken from Zhang et al. [21] . We used a common simulation time step δt = 0.03 across all three environments.SingleIntegrator We use single integrator dynamics as the base environment to verify the correctness of the implementation and to show the performance of the methods when there are no control input limits. The dynamics is given as ẋi = v i , where x i = [p x i , p y i ] ⊤ ∈ R 2 is the position of the i-th agent and v i = [v x i , v y i ] ⊤ its velocity. In this environment, we use e ij = x j -x i as the edge information.DoubleIntegrator We use double integrator dynamics for this environment. The state of agent i is given byx i = [p x i , p y i , v x i , v y i ] ⊤ , where [p x i , p y i ]⊤ is the position of the agent, and [v x i , v y i ] ⊤ is the velocity. The action of agent i is given by u i = [a x i , a y i ] ⊤ , i.e., the acceleration. The dynamics function is given by:EQUATIONIn this environment, we use e ij = x j -x i as the edge information.DubinsCar We use the standard Dubin's car model in this environment. The state of agent i is given byx i = [p x i , p y i , θ i , v i ] ⊤ , where [p x i , p y i ]⊤ is the position of the agent, θ i is the heading, and v i is the speed. The action of agent i is given by u i = [ω i , a i ] ⊤ containing angular velocity and acceleration magnitude. The dynamics function is given by:ẋi = [v i cos(θ i ), v i sin(θ i ), ω i , a i ] ⊤ (7)We use e ij = e j (x j ) -e i (x i ) as the edge information, wheree i (x i ) = [p x i , p y i , v i cos(θ i ), v i sin(θ i )] ⊤ .We formally define the Signal Temporal Logic (STL) specifications used in the experiments in Table 4 . The specifications include a sequential waypoint task (seq), a coverage task (cover), a loop task (loop), and a branching task (branch). The specifications are defined over a time horizon T and are satisfied if the agents satisfy the corresponding STL formula. We use four markers A, B, C, and D to represent rectangular predicates centered around x-y coordinates [0, 0], [2, 2] , [2, 0] , and [0, 2], respectively. The predicates are defined as p i = dist(s i , p i ) ≤ 1.0 where dist(s i , p i ) is the L1-norm (| • | 1 ) distance between the agent i's state s i and the predicate p i .Spec. Description Formula T k seq Sequence of goalsEQUATIONTable 4 : STL specifications used in the experiments. T and k are the specification lengths and goal sample intervals respectively.In Tables 5, 6 and 7 we show results for the various environments and obstacle scenarios. While our GNN-ODE has an initial GNN module which can observe these obstacles, and is also trained to generate initial goals that are 'achievable', the GNN-ODE is inherently limited to only consider obstacles within the sensing radius R of the agents at planning time (i.e. t = 0). As in Zhang et al. [21] , the GCBF+ controller is trained to avoid obstacles. Thus, with a robust plan, we can achieve reasonably high success rates in this setting as well due to the run-time collision avoidance maneuvers. Planning times are nearly similar to the results in Sec. 6 (Table 2 ) likely because our learning-based planners do not use environment dynamics at inference time and should have a similar computation cost after training is complete. For this reason, to avoid clutter, we omit this column in the following tables. We include results from the ODE ablation of our method as shown in Table 3 under the column 'ODE'. Additional simulation videos are hosted online2 .In Table 5 we contain the results for various combinations of specifications, 8 sampled obstacle positions (marked 'Y' if present, 'N' otherwise), and number of agents in the SingleIntegrator Environment. We observe that the GNN-ODE planner outperforms the other planners in terms of planning time and success rate across all the specifications and obstacles. We note the average improvement in success rate of 10% for our GNN-ODE planner over the MILP planner which is not as large as the improvement in the non-linear DubinsCar environment (Table 2, 6 ). This is due to the SingleIntegrator environment being less constrained and the MILP planner being able to find a feasible solution more easily.In Table 6 we contain the results for various combinations of specifications, 8 sampled obstacle positions (marked 'Y' if present, 'N' otherwise), and number of agents in the DubinsCar Environment.On average, with obstacles present as well we get a 69% improvement in success rate for our GNN-ODE planner over the MILP planner, primarly due to the non-linear dynamics of the DubinsCar environment being challenging for the collision avoidance controller. In Table 7 we contain the results for various combinations of specifications, 8 sampled obstacle (Obs) positions (marked 'Y' if present, 'N' otherwise), and number of agents (N) in the DoubleIntegrator Environment. The average improvement in success rate of 11% for our GNN-ODE planner over the MILP planner is similar to the SingleIntegrator environment (Table 5 ) due to GCBF+controller being more effective at collision avoidance with the linear dynamics of the DoubleIntegrator environment.The experimental validation of this methodology involved deploying a fleet of WiFi mode to enable swarm behavior which was facilitated through the open-source DJITelloPy3 library.Each Tello drone is equipped with an Inertial Measurement Unit (IMU), a forward-facing camera, and a downward-facing camera. The latter is useful for precise hovering and position estimation using the Vision Positioning System (VPS). However, this system is inaccurate and unreliable as the drones do not possess other sensors like lidar or depth cameras. To mitigate drift and correct the position estimate errors, ArUco tags were utilized to make the trajectory following robust for each drone. This ensured the swarm of drones could accurately follow the designated trajectory as evidenced in the simulation results.We focus on the most complex non-linear environment as presented in the main paper (DubinsCar) and have presented the results over 30 initial seeds in Table 8 and 9 and included bar charts with error bars for the main experiments in Figures 2 and 3 . We chose this format as including all values in the tables created excessive clutter.Since the tasks are homogenous, one might attempt to follow a common plan among agents with a formation. To compare this, we include results on a common shared plan generated by the STLPY solver [17] (marked STLPY (S)) for the specifications considered in Table 8 and 9 . The initial starting state of this plan was near the first predicate in each specification (viz. goal A).An obvious benefit of a single plan generated by the STLPY solver is a reduced planning time.Using a single common plan also enforced a rudimentary level of coordination among agents as evident in the branch task reducing the number of crossing paths (present in the earlier individually generated STLPY plans). However, in long horizon specifications such as loop and signal this effect is detrimental causing increased safety violations (leading to a low overall success rate) due to a lack of a more informed coordination among agents. We posit the fixed predicate sizes further play a role in preventing this coordination scheme to succeed. We found that the challenges in scalable collision avoidance modeling with the PWL MA-STL planner [16] (discussed in Section 3) were also present in other centralized STL planning strategies [46] . Namely, directly adding predicates for collision avoidance into the STL specification proved intractable for optimization over the long planning horizons considered due to an O(C N 2 * K 2 ) variable blowup for N agents and planning horizon K. To address this following our proposed method, we attempt planning for the joint multi-agent task without considering collisions during planning, while introducing run-time collision avoidance schemes like GCBF+. As a result, in the simulation step of [46] (Alg. 1, line 4), the GCBF+policy would be incorporated into the rollout. However, in our experiments, we found that the gradient vanishes too quickly (within 50 time steps) to meaningfully differentiate through the trajectory, which spans over 200 time steps for all our tasks (Table 4 , Appendix B). Consequently, the algorithm in [46] cannot directly handle the longer-range STL tasks considered in our work. Additionally, we noted that the proposed approach was not robust to many initial starting positions, often leading to unfruitful plans.To build a centralized planner with [46] , we opted to run the proposed method without incorporating collision avoidance during planning time simulations. This choice allowed us to achieve longer optimization horizons within a limited initial starting position range. The resulting plans were executed using the trained GCBF+ controller. The results, as shown marked CE in 8 and 9 for the DubinsCar Environment, indicate that the proposed approach performed demonstrably worse than ours and the other compared methods (note Success Rate). The planning time of this centralized approach scaled linearly with the number of agents since agent-agent interactions were not considered. These results further point to the importance of an achievability loss (L ach , Sec. 4.1) when planning in the presence of run-time collision avoidance. This outcome reinforces the notion that current methods for centralized planning in multi-agent STL requires further advancements to effectively handle scalable collision avoidance.In Table 8 we include a signal specification demonstrating the Until operator. This is a variant of our loop specification ( 8 and Table 9 . 8 and Table 9 .Code: https://github.com/jeappen/mastl-gcbfSite: https://jeappen.github.io/mastl-gcbf-website/https://github.com/damiafuentes/DJITelloPy 


Decision: This paper received 3 confident reviews. It proposes a hierarchical architecture for multi-agent control with STL constraints, wherein a GNN and recurrent MLP predict a set of high-level waypoints that are tracked using a neural graph control barrier function controller. This combination is trained end-to-end on different environments and achieves better empirical scalability than MILP-based solution methods.

To address in rebuttal (in addition to reviewer comments):
- Discuss limitations on homogeneity, noted by several reviewers (dynamics, as well as STL specs)
- Address technical queries highlighted by reviewers
- Add training details
- Discuss insights obtained on real robot experiments

Post-rebuttal:
The reviewers provided key clarifications. The experimental analyses should ideally be extended in support of claims.

Reviews: review: title: title: Multi-agent STL planner
paper_summary: paper_summary: The paper proposes a multi-agent planning framework using Signal Temporal Logic. The proposed method relies on a graph neural network to generate plans in a decentralized manner. A comparison against mixed-integer linear programming-based planning is made.
main_review: main_review: The paper is well-motivated, as mixed-integer-based planners often suffer from the curse of dimensionality, especially in multi-agent settings. Moreover, signal temporal logic (STL) can capture much richer mission specifications compared to traditional planning methods. However, the paper assumes that all agents receive the same type of temporal logic formula throughout the entire mission. In my opinion, this is quite a limitation, as we often want agents to perform different tasks. If all agents have the same STL formula, one could plan for a single agent and then use low-level abstraction controls to steer the group of agents (while maintaining formation) to achieve the same objective. The experimental results show promising speed improvements across all scenarios, with the maximum number of agents tested being 32. The paper is well written, but some questions need to be addressed for further clarity and improvement. The hardware experiment is appreciated but the sequence is not that exciting, a more convincing scenario is needed for the drone demonstration.
questions: questions: (1) Why is safety treated separately from STL satisfaction? One can directly specify safety and liveness through an STL formula, which can be encoded as part of robustness, i.e., a measurement of how safe the agents are.

(2) The "co-learning" of the safety (GCBF+) and objective controllers (GNN-ODE) is not clear to me. Are there cases where the GNN-ODE controller and GCBF+ controller cause the planner to be unable to find a solution? If yes, how do you address this?

(3) In Table 2, the STLPY's safety rate is decreasing dramatically. Can you explain this in more detail? If your method is using GCBF+ and GNN-ODE, is the baseline algorithm also using some sort of CBF-based safety checking mechanism?

(4) The STL formula used for scenarios (seq, cover, loop, branch) does not contain the "Until" operator. Can you show an example that includes it?
limitations: limitations: 2
review_summary: review_summary: The motivation of the paper is good and I appreciate the hardware experiments. Some technical details need to be addressed as it directly impacts the claim from the authors.
title: title: Clear writing but limited applicability of the proposed method.
paper_summary: paper_summary: This paper concerns a problem of multi-agent planning where each agent shares the same dynamics and the STL specifications of their objectives. The problem is decoupled into two learning problems, one that learns the neural network planner that learns to achieve the STL objective, and the other that learns the Graph CBF to ensure that each agent does not collide to each other and the obstacles.
main_review: main_review: Overall, I think the writing is clear, and within the scope of the problem that the authors specified, the method seems to work well. However, since the method requires a rather strong assumption that the agents share common dynamics and STL objectives, I think the applicability of the work is quite limited. Other than this, I only have minor comments listed below:
- In definition 1, Achievability - the tracking performance requirement is written in sum-over-time form. Is there a particular reason for this or could this be written in other forms? (for instance, tracking error not exceeding the threshold for all time instances)
- In Section 4.2, since the sequence of goals is produced by a forward pass of the MLP neural network, it seems like the error will compound through these integration steps.
- Results in Table 2: in line 271, it is said that 5 random initial seeds are sampled for this statistic. Is it reliable enough?
- The planner and the GCBF controller are learned together. Is there any specification of the update rates between the two entities? For instance, are they updated in the same frequency and same learning rates?
questions: questions: The author claims that by decoupling the problem of STL specification and safety, the proposed method does not suffer the poor scalability that other methods that solve STL suffer. However, in order to achieve this, the method operates under a strong assumption of homogeneous dynamics and objectives. Under this strong assumption, wouldn’t other methods’ scalability also improve?
limitations: limitations: 3
review_summary: review_summary: The method only works under strong assumptions, however, under this setting, I think the presentation of the paper and its originality are both very clear.
title: title: Review
paper_summary: paper_summary: This paper proposes a hierarchical architecture for multi-agent control with STL constraints, wherein a GNN and recurrent MLP predict a set of high-level waypoints that are tracked using a neural graph control barrier function controller. This combination is trained end-to-end on different environments and achieves better empirical scalability than MILP-based solution methods.
main_review: main_review: The paper reads well overall, but there are some opportunities for confusion since the proposed framework has multiple parts that are discussed individually before being brought together in Section 4.4. Consider adding more high-level introduction to your framework earlier on to avoid the risk of losing your reader.

This paper does a good job of combining different building blocks, some known (GCBF, differentiable STL) and some new (GNN+ODE planner), into a useful system.

Overall, I think this paper would be well-received at CoRL, but there are a number of minor things the authors should be sure to address. These include:

Section 1.1: there is an additional class of STL planners that attempt to improve scalability over MILP planners by using nonlinear optimization (sacrificing completeness but improving efficiency). See e.g. [C. Dawson, C. Fan/ "Robust Counterexample-guided Optimization for Planning from Differentiable Temporal Logic." IROS 2022](https://arxiv.org/pdf/2203.02038) . You also cite [19] and [40] later in the paper; perhaps those should be mentioned in Section 1.1 as well?

The problem setting assumes that the STL requirements for each agent are independent; is this a restrictive assumption? This would seem to preclude potentially useful specifications like "Agent 1 remains in area A until agent 2 gets there".

Fig. 1 is a bit dense; it's a lot of information before the reader really catches up on what you're doing. Have you considered splitting it up so that each subfigure is close to the relevant section of the paper?

Can you provide error bars for Table 2?

Can you report the total training time in addition to the planning time?

You claim that your approach is decentralized, but doesn't evaluating the GNN require communication between nodes (message passing)?

I can see an additional limitation in this approach not mentioned in the limitations section: relative to single-shot planners (e.g. using differentiable MA-STL to directly optimize the goals), your approach will require additional samples and time to train the GNN. This will be earned back if you have to plan multiple times in the same environment and with the same specification, but is lost if the specification changes.

I notice that your approach has a high optimality gap (in time to reach) relative to MILP planner. Is that because the MILP sacrifices STL satisfaction for time to reach, or is it a limitation of your method?

A number of details about the training process seem to be missing (at least, I couldn't find them). Such as number of randomly sampled initial conditions per epoch, number of epochs, hyperparameters, .... These should be included in the supplementary material so that others can reproduce your work.

You also conduct hardware experiments, but hide them in the supplementary materials. The CoRL audience generally values hardware demonstrations, so make sure to highlight them!
questions: questions: Please respond to my questions in the review above.
limitations: limitations: 2
review_summary: review_summary: I think this paper would be well-received at CoRL, but there are a number of minor things the authors should be sure to address.