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

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

TL;DR

Neural Tree Expansion (NTE) brings the self-improving power of AlphaZero to the messy, continuous world of multi-robot robotics. By using neural networks to "propose" the most promising actions in a search tree, the system allows decentralized robots to perform complex, coordinated maneuvers in real-time—outperforming traditional methods with 20x fewer computational resources.

What Problem Does This Paper Address?

Planning for multiple robots in "non-cooperative" environments (like a game of drone tag or navigating through aggressive traffic) is incredibly difficult. You have to predict what others will do while maximizing your own reward.

While algorithms like AlphaZero have mastered discrete games like Chess and Go, they struggle with robotics for four main reasons:

  1. Continuous Spaces: Robots don't move in discrete "tiles"; their positions and accelerations are continuous.
  2. Decentralization: In the real world, robots can't always rely on a central "brain"; they must make decisions locally.
  3. Partial Information: Robots only see what their sensors allow, not the whole "board."
  4. Compute Limits: A drone can't carry a supercomputer to run massive searches mid-flight.

Methods

The authors introduce Neural Tree Expansion (NTE), which adapts Monte Carlo Tree Search (MCTS) for robotics through a "Global-to-Local" imitation learning framework.

  • The "Expert" vs. the "Learner": During training (offline), a centralized Expert MCTS with perfect information and high compute power generates high-quality demonstrations. A decentralized Learner MCTS (with limited info and compute) tries to mimic this expert.
  • Neural Expansion (The "Aha!" Moment): In standard AlphaZero, a neural network selects the best move from a list. In continuous robotics, there is no list. NTE uses a policy network to generate (expand) the most promising continuous actions directly into the search tree. This prevents the search from wasting time on useless "random" movements.
  • Self-Play Loop: The learner plays against itself to find "interesting" states. The expert then provides the "optimal" actions for those states, which are used to retrain the learner’s policy and value networks.
  • DeepSets Architecture: To handle a changing number of nearby robots, the authors use "DeepSets," a neural network structure that can process an arbitrary number of inputs without caring about their order.

Datasets

The paper doesn't use a static external dataset. Instead, it uses a self-generated dataset created through the iterative self-play loop.

  • Training Data: 80,000 state-action pairs generated per iteration.
  • Evaluation Scenarios: The primary benchmark is the Reach-Target-Avoid (RTA) game (a differential game where attackers try to reach a goal and defenders try to tag them). They tested this with both simple "double-integrator" physics and more complex "3D Dubin’s vehicle" dynamics (simulating fixed-wing aircraft).

Key Insights and Ideas

  • Expansion beats Selection: In high-dimensional games (e.g., 10 vs. 10 robots), the odds of randomly picking a good joint action are astronomical. By using the neural network to propose the action for the tree to explore, the search becomes focused and efficient.
  • Distilling Coordination: Even though the robots are decentralized at runtime, they act as if they are coordinated because they were trained by a centralized expert. This "implicit coordination" is vital for bandwidth-limited environments.
  • Computational Efficiency: The "Learner" MCTS only needs 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.

Key Results

  • Performance: The NTE-trained policies significantly outperformed the state-of-the-art control-theoretic baselines for the Reach-Target-Avoid game.
  • Emergent Strategy: Robots learned sophisticated behaviors, such as one defender guarding the goal while another aggressively pursued the attacker to reduce its maneuverability.
  • Hardware Validation: The system was tested on a swarm of CrazyFlie drones. The robots successfully ran the decentralized learner at 20 Hz, proving the algorithm is robust enough for the "sim-to-real" gap and real-time flight.
  • Scalability: Although trained on games with up to 5 robots per team, the neural networks generalized well to 10 vs. 10 scenarios without further training.

Limitations and Future Work

  • Deterministic Transitions: The current model assumes the world is deterministic (actions have predictable results). The authors note that while this can be relaxed, it wasn't the focus of this paper.
  • Homogeneous Teams: The experiments focused on teams of identical robots. Future work could explore how these networks handle heterogeneous teams (e.g., ground robots working with aerial drones).
  • Uncertainty: The authors plan to combine this with "planning under uncertainty" algorithms to better handle sensor noise and model inaccuracies in more 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 20 Hz 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},
}

Loading related content...

Figure