Neural Tree Expansion for Multi-Robot Planning in Non-Cooperative Environments

Benjamin Rivière, Wolfgang Hönig, Matthew Anderson, Soon-Jo Chung

Abstract

We present a self-improving, Neural Tree Expansion (NTE) method for multi-robot online planning in non-cooperative environments, where each robot attempts to maximize its cumulative reward while interacting with other self-interested robots. Our algorithm adapts the centralized, perfect information, discrete-action space method from AlphaZero to a decentralized, partial information, continuous action space setting. Our method has three interacting components: (i) a centralized, perfect-information "expert" Monte Carlo Tree Search (MCTS) that provides expert demonstrations, (ii) a decentralized, partial-information "learner" MCTS that runs in real-time and provides self-play examples, and (iii) policy & value neural networks that bias both the expert and the learner tree growth. Our numerical experiments demonstrate NTE's computational advantage, finding better solutions than a MCTS with 20 times more resources. Hardware experiments on an aerial swarm demonstrate online planning at 20Hz with effective policies in complex scenarios.

Introduction

Planning for multiple robots in non-cooperative environments—such as navigating aggressive traffic or competitive drone games—presents significant challenges. Robots must predict the actions of self-interested agents while maximizing their own rewards. While algorithms like AlphaZero have mastered discrete games like Chess and Go, they face four major hurdles in robotics: continuous action spaces, the need for decentralized execution, partial observability, and severe onboard computational constraints. Neural Tree Expansion (NTE) bridges this gap by enabling efficient, real-time search in continuous spaces.

Methodology

NTE adapts Monte Carlo Tree Search (MCTS) for robotics through a "Global-to-Local" imitation learning framework.

Overview of the Neural Tree Expansion (NTE) framework, illustrating the offline training loop and online decentralized deployment.

The Expert-Learner Framework

The system operates in two phases. During offline training, a centralized Expert MCTS with perfect information and high computational resources generates high-quality demonstrations. Simultaneously, a decentralized Learner MCTS with limited information and compute runs in real-time to provide self-play examples. The learner plays against itself to find "interesting" states, and the expert provides optimal actions for those states to retrain the neural networks.

Neural Expansion and DeepSets

In continuous robotics, there is no discrete list of moves to select from. NTE uses a policy network to directly generate (expand) the most promising continuous actions into the search tree. This prevents the search from wasting time on suboptimal random movements. To handle a dynamic number of agents, the architecture utilizes DeepSets, a neural network structure that can process an arbitrary number of inputs without being sensitive to their order.

Key Results and Hardware Validation

The NTE-trained policies significantly outperformed state-of-the-art control-theoretic baselines in the Reach-Target-Avoid (RTA) game, a differential game where attackers try to reach a goal and defenders try to tag them.

  • Computational Efficiency: The Learner MCTS requires only 500 nodes to outperform an unbiased MCTS using 10,000 nodes. This 20x reduction in search depth is what makes 20Hz real-time planning possible on standard hardware.
  • Emergent Strategy: Robots learned sophisticated, coordinated behaviors. For example, defenders learned to split roles, with one guarding the goal while another aggressively pursued the attacker to reduce its maneuverability.
  • Hardware Robustness: The system was successfully validated on a swarm of CrazyFlie drones. The robots successfully ran the decentralized learner at 20 Hz, proving the algorithm's robustness to the sim-to-real gap and real-time flight constraints.
Hardware implementation on a swarm of CrazyFlie drones, demonstrating real-time 20Hz planning.

Conclusion

Neural Tree Expansion successfully brings the self-improving power of search-based reinforcement learning to continuous, decentralized multi-robot systems. While current work assumes deterministic transitions and homogeneous teams, future research will explore heterogeneous robot configurations and planning under sensor uncertainty to better handle model inaccuracies in chaotic environments.

Summary updated

Abstract

We present a self-improving, Neural Tree Expansion (NTE) method for multi-robot online planning in non-cooperative environments, where each robot attempts to maximize its cumulative reward while interacting with other self-interested robots. Our algorithm adapts the centralized, perfect information, discrete-action space method from AlphaZero to a decentralized, partial information, continuous action space setting for multi-robot applications. Our method has three interacting components: (i) a centralized, perfect-information "expert" Monte Carlo Tree Search (MCTS) with large computation resources that provides expert demonstrations, (ii) a decentralized, partial-information "learner" MCTS with small computation resources that runs in real-time and provides self-play examples, and (iii) policy & value neural networks that are trained with the expert demonstrations and bias both the expert and the learner tree growth. Our numerical experiments demonstrate Neural Tree Expansion's computational advantage by finding better solutions than a MCTS with 20 times more resources. The resulting policies are dynamically sophisticated, demonstrate coordination between robots, and play the Reach-Target-Avoid differential game significantly better than the state-of-the-art control-theoretic baseline for multi-robot, double-integrator systems. Our hardware experiments on an aerial swarm demonstrate the computational advantage of Neural Tree Expansion, enabling online planning at 20Hz with effective policies in complex scenarios.
BibTeX
@article{riviere2021neural,
  author = {Benjamin Rivière and Wolfgang Hönig and Matthew Anderson and Soon-Jo Chung},
  title = {{Neural Tree Expansion for Multi-Robot Planning in Non-Cooperative Environments}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2021},
  url = {https://openreview.net/forum?id=fovXUsZ1T3},
}
Figure