Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control

Authors: Songyuan Zhang, Oswin So, Mitchell Black, Chuchu Fan
Primary area: reinforcement learning
Keywords: control barrier functions, multi-agent systems, black-box systems, partial observability, reinforcement learning

Abstract:
Control policies that can achieve high task performance and satisfy safety constraints are desirable for any system, including multi-agent systems (MAS). One promising technique for ensuring the safety of MAS is distributed control barrier functions (CBF). However, it is difficult to design distributed CBF-based policies for MAS that can tackle unknown discrete-time dynamics, partial observability, changing neighborhoods, and input constraints, especially when a distributed high-performance nominal policy that can achieve the task is unavailable. To tackle these challenges, we propose **DGPPO**, a new framework that *simultaneously* learns both a *discrete* graph CBF which handles neighborhood changes and input constraints, and a distributed high-performance safe policy for MAS with unknown discrete-time dynamics.
We empirically validate our claims on a suite of multi-agent tasks spanning three different simulation engines. The results suggest that, compared with existing methods, our DGPPO framework obtains policies that achieve high task performance (matching baselines that ignore the safety constraints), and high safety rates (matching the most conservative baselines), with a *constant* set of hyperparameters across all environments.

Decision: accept (poster)
Reviewer scores: 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1729687388176

thread_type:
official_review

<thread_object>
creator: reviewer_lzax

<content>
summary:
This paper proposes a safe multi-agent reinforcement learning method based on distributed control barrier functions (CBFs) for multi-agent systems with limited perception capabilities. Simulation results on several multi-agent safe coordination tasks demonstrate the effectiveness of the proposed method.

strengths:
(1) The multi-agent safe optimal control problem considered in this paper is both general and challenging, as neither the system model nor a nominal policy is available in advance.

(2) The learned policy is safe, which does not require additional safety filters in implementation.

(3) Extensive simulations are conducted, and state-of-the-art baselines are compared.

weaknesses:
There exist several theoretical issues in the paper. The motivation of employing the discrete graph CBF is unclear. Some implementation details should be incorporated. See Questions part for more details.

questions:
(1) The policy in this work only takes local observations as input, such that it is decentralized. Why do you refer to it as a distributed policy? 

(2) The modified constraint (11b) is too strict which cannot be satisfied by a lot of policy classes, such as the Gaussian policy.

(3) In (12), please provide the explicit gradient formula when the safety condition is violated. Note that the authors provide a gradient in (41). Nevertheless, this gradient is not associated to the policy loss function (under safety violation) in (12).

(4) Theorem 3 is very difficult to understand. The orthogonality assumption is impractical. The reviewers also find that the authors try to replace the stationary state distribution (which is a function associated to the policy parameter $\theta$) with a constant state distribution in this theorem to obtain their gradient $g$ in (13). What is the purpose of giving Theorem 3? What is the relationship between (13) and (14)? 

(5) The reason of using discrete graph CBFs should be explained clearly. Note that we can regard the multi-agent system as a large but single agent. Then, you can directly use the discrete CBF given in Theorem 2 to learn safe policies. In this case, the distributed control nature can still be preserved as the learned observation-based policy is end-to-end.

(6) Theorem 4 is hard to understand. What is the relationship between the discrete graph CBF and the discrete CBF? Similar to Theorem 1, it is important for the authors to show that the safe set is forward invariant based on the discrete graph CBF.

(7) In (11b), the safety constraint is calculated using a stochastic policy $\pi$. However, in Fig. 1, deterministic policies are used for estimating the discrete graph CBF.

(8) Why do the agents have different GAEs in your algorithm? Are you suggesting that the agents are heterogeneous and that their local policies differ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730572395648

thread_type:
official_review

<thread_object>
creator: reviewer_xeof

<content>
summary:
The paper introduces a novel framework, Discrete Graph Control Barrier Functions Proximal Policy Optimization (DGPPO), for ensuring safe control in multi-agent systems (MAS) operating under unknown discrete-time dynamics and input constraints. Unlike prior approaches that rely on continuous-time models and known nominal policies, DGPPO incorporates discrete CBFs (DCBFs) and reinforcement learning to dynamically learn both a high-performance safe policy and a discrete graph CBF (DGCBF). Through extensive empirical validation across various simulated MAS environments, DGPPO claims to achieve both high task performance and safety without the need for hyperparameter adjustments specific to each environment.

strengths:
The authors present an innovative combination of reinforcement learning and discrete-time CBFs to address the challenges of safety and task performance in MAS with unknown dynamics. The extension to the DCBF framework in discrete-time and the introduction of DGCBFs allow for neighborhood adaptability, overcoming limitations associated with continuous-time CBFs. The approach is well-motivated, tackling safety in unknown environments without requiring a predefined nominal policy—a substantial improvement for multi-agent reinforcement learning (MARL). I particularly appreciate the rigorous theoretical presentation to support the proposed approach.

weaknesses:
While DGPPO introduces a novel safety mechanism for MAS, nonetheless I believe there are few critical concerns that could limit the effectiveness and general applicability of the approach.

**Lack of clear performance metrics**: 

while DGPPO is shown to achieve high safety, the empirical results focus primarily on safety metrics and the minimization of constraints. It remains unclear if the agents are successfully accomplishing global objectives. Without metrics like mean global success rate or reward, it is difficult to assess if the agents are merely achieving safety (e.g., by staying stationary) rather than making meaningful progress toward the task goals while satisfying the safety constraints. This is especially relevant as the DGPPO framework does not incorporate a nominal policy, meaning that without these metrics, the experiments risks overlooking cases where the agents avoid unsafe states at the expense of task completion. Does the proposed framework present mechanisms to ensure that safety constraints do not excessively dominate the objective?

**Limited scalability experiments**: 

the authors state that DGPPO scale well w.r.t to the baseline approach tested, however testing 5 agents instead of 3 as in the original experiment, I believe it is too limited to claim scalability of the proposed approach. Crucially, as stated from the authors themselves the proposed approach requires both stochastic and deterministic rollouts to enforce DGCBFs. While this approach ensures safety in discrete-time settings, it also introduces significant sample inefficiency, which may limit the framework’s scalability to larger or more complex MAS. Hence, an extensive test with for instance 10 or 15 agents would strength the results of the paper.
Moreover while the authors employ GNNs with attention mechanisms to handle changing agent neighborhoods, the computational complexity of GNNs in larger MAS could become important. In high-density environments with frequent neighborhood changes, maintaining an updated and accurate DGCBF through GNNs could pose significant computational challenges, possibly impacting real-time applicability. A detailed discussion on the scalability of GNN-based policies for larger agent systems would add valuable context to the method’s limitations.

**Dependence on hyperparameter $\nu$ for constraint enforcement**: 

the authors claim on the fact that DGPPO is less sensitive to hyperparameters does not seem to be properly backed up. From the plot in Fig. 6b the value of $\nu$—responsible for controlling the weight on constraint minimization steps—significantly impacts performance. Misalignment in $\nu$ could lead to either overly conservative or unsafe policies, showing that DGPPO still requires careful tuning, contrary to its stated hyperparameter robustness.

questions:
Q1: How does DGPPO ensure that agents achieve the global objective, rather than just meeting safety constraints?  

Q2: Could DGPPO’s rollout requirements be reduced to improve sample efficiency without compromising safety?  

Q3: What are the practical scalability limits of DGPPO when applied to larger MAS, particularly with the use of GNNs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730665701093

thread_type:
official_review

<thread_object>
creator: reviewer_ub5m

<content>
summary:
The proposed DGPPO framework addresses challenges in multi-agent systems (MAS) by learning both a discrete graph control barrier function (DGCBF) and a high-performance safe policy under unknown discrete-time dynamics, changing neighborhoods, and input constraints. DGPPO combines reinforcement learning and DGCBF, achieving high task performance and safety across varied environments without needing a pre-existing nominal policy or multiple hyperparameter sets, consistently outperforming other methods in both metrics of safety rate vs cost for various simulations.

strengths:
- The proposed method (DGPPO) is an elegant way to solve the discrete-time distributed MASOCP (multi-agent safe optimal control problem) with unknown environment dynamics. This assumption was not present in previous work which had to differentiate through the given transition functions.
- The theorems introduced provide a solid foundation for the applicability of DGPPO in the discrete-time setting.

weaknesses:
- Scalability appears limited (only up to 7 agents) compared to the continuous time setting of GCBF+ [1] (most likely due to the present of unknown environment dynamics and the noise introduced through the sample score function gradient).
- The stability of DGPPO compared to the baselines does not seem appropriately explained. Is it a purely empirical observation or is there some theoretical justification available?
- In the given setting, why is the assumption of unknown dynamics interesting? To me, the environments considered are purely the settings of [1] without using the environment dynamics directly (even though they are available). Would it not be a better idea to consider an environment where the dynamics are not as simple as the ones in [1] or some complex unknown function (for e.g., common Mujoco robots)?

References:

[1] GCBF+: A Neural Graph Control Barrier Function Framework for Distributed Safe Multi-Agent Control, Zhang et al, T-RO, 2024

questions:
1. Why is the dependency of the algorithm on a nominal policy a bad idea in the given settings? Since it appears easy enough to construct one (say a PID controller like in [1]) for the environments given, is this the right direction?
2. What is the difference between the training and inference situations in terms of the number of agents? Does the algorithm need to be retrained for every new number of agents unlike in [1] where the algorithm was trained on 8 agents and deployed on up to 1024 agents (albeit being purely concerned with single goal reaching while avoiding collisions)?
3. With regards to the sample efficiency and computation requirements, how is DGPPO w.r.t. the baselines (I noticed the training time was listed as 12 hours on the reference specifications)? On a related note, how is the benefit of a constant set of hyperparameters demonstrated? Can we confidently say the hyperparameter search for the baselines takes significantly longer (in wall clock time on a comparable machine)?
4.What are the restrictions on the definition of the avoid set $\mathcal{A}_i$ and the assumptions on the function $h_i^{(m)}$? Do the avoid sets primarily represent distance to $y^k$ greater than some safe radius?
5. The LiDAR part of the observation appears less clear. From the appendix (Sec B.2.1) is it right to say that only the LiDAR environments use the 32 equally spaced ray capturing relative positions? How are the obstacles in the VMAS environments represented to the agent?
6. The experiments with scalability to multiple agents (Fig. 5) appear quite close to the baselines. Is there a better comparison available?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732339558749

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Reply to all

comment:
We thank the reviewers for their valuable comments.
We are excited that the reviewers have identified the importance of the problem ($\color{#648FFF}{\textsf{uB5M}}$, $\color{#DC267F}{\textsf{LZax}}$),
the novelty of our technical contributions (**all** reviewers),
appreciated our extensive empirical validation ($\color{#E69F00}{\textsf{XeoF}}$, $\color{#DC267F}{\textsf{LZax}}$),
and found the paper well-motivated with good presentation ($\color{#648FFF}{\textsf{uB5M}}$, $\color{#E69F00}{\textsf{XeoF}}$).
We believe that DGPPO takes a significant step towards greatly improving the safety of multi-agent systems with **unknown, discrete-time dynamics _without_ an available performant reference controller** by applying distributed graph CBFs and multi-agent reinforcement learning.

---

As _all_ reviewers have recognized our technical novelty, the primary concerns stem from the scalability and generalizability (all reviewers), 
hyperparameter sensitivity ($\color{#E69F00}{\textsf{XeoF}}$),
and clarity of theoretical results ($\color{#DC267F}{\textsf{LZax}}$).

In our updated revision, we provide major improvements by clarifying _all_ raised questions.
We provide a brief summary of notable changes below. All references to sections refer to the **revised** version.

## 1. Generalizability of DGPPO

We have **added an additional theorem** in Appendix A.7 which theoretically proves that the discrete graph control barrier function (DGCBF) can be generalized to more agents than initially trained for.

Next, we **perform an additional experiment where we train DGPPO with 8 agents and deploy the learned policy on up to 512 agents** (Appendix C.8). The results, shown below, demonstrate that DGPPO can maintain a high safety rate and low costs even with larger numbers of agents.

|Number of agents|Safety rate|Normalized cost|
|---|---|---|
|8|$1.000\pm0.000$|$1.673\pm0.430$|
|16|$0.992\pm0.088$|$1.784\pm0.316$|
|32|$0.987\pm0.112$|$1.748\pm0.235$|
|64|$0.986\pm0.118$|$1.799\pm0.418$|
|128|$0.982\pm0.133$|$1.839\pm0.323$|
|256|$0.985\pm0.122$|$1.823\pm0.366$|
|512|$0.985\pm0.123$|$1.821\pm0.390$|

## 2. Hyperparameter Sensitivity

Figure 6(b) shows that using larger values of $\nu$ results in a slower reduction of the cumulative cost.
We have **performed additional experiments that confirm that only the rate and _not_ the final converged policy is affected by $\nu$** (Appendix C.6.4).
This is a _significant improvement_ compared to the baseline methods, where both the rate **and** the performance of the converged policy are greatly affected by the choice of hyperparameter.

## 3. More Clarification on Theoretical Analysis

We have significantly clarified our theoretical analysis. In short, we have:

1. Included a more detailed derivation of our proposed policy loss (Appendix B.1)
1. Clarified the difference between **policy gradients** and **score function gradients** during the policy updates w.r.t. the DCBF condition and performed additional experiments that demonstrate the difference (Appendix B.2)
2. Provided proofs for the **safety** (Appendix A.6) and **generalizability** (Appendix A.7) guarantee of DGCBF.

---

We hope the new presentation better presents the contributions of our method in improving the safety and task-performance of multi-agent systems by generalizing distributed CBFs to more general settings.

We have tried our best to resolve all the questions raised in the individual responses below.
If the reviewers have any additional questions/comments/concerns, please let us know.
We appreciate the reviewer's precious time in providing their valuable feedback.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control


Summary:  This paper proposes DGPPO, which integrates discrete graph control barrier functions (DGCBFs) with reinforcement learning to address the safety and performance challenges in multi-agent systems under unknown discrete-time dynamics and limited sensing conditions. The paper introduces discrete-time extensions of control barrier functions and leverages a policy optimization technique to jointly learn safe and performant policies without requiring a predefined nominal policy. DGPPO is evaluated across multiople simulation environments, demonstrating superior safety and cost performance compared to baselines while being robust to hyperparameter changes. 

Comments: We received 3 expert reviews, with the scores 6, 6, 8, and the average score is 6.67. The reviewers are generally positive about the algorithmic and technical contributions of this paper. The discrete graph formulation and their integration with reinforcement learning overcomes many limitations of continuous-time CBFs. The technical analysis is rigorous, with results that ensure forward invariance of safety constraints and address the challenges of unknown dynamics in MAS.  Simulations demonstrate near-perfect safety rates as a validation of the proposed approach.  The paper is also well-written. 

The reviewers have also provided multiple comments to strengthen the paper. One main comment was to include additional experiments that demonstrate the scalability. Another comment is to further validate the claim that the proposed method is robust to hyperparameters changes. I am glad to see that the authors have already addressed these comments during the rebuttal and the reviewers have acknowledged their efforts.  I recommend the authors update the paper by accommodating these suggestions.