A Caltech Library Service

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

Rivière, Benjamin and Hoenig, Wolfgang and Anderson, Matthew and Chung, Soon-Jo (2021) Neural Tree Expansion for Multi-Robot Planning in Non-Cooperative Environments. IEEE Robotics and Automation Letters, 6 (4). pp. 6868-6875. ISSN 2377-3766. doi:10.1109/LRA.2021.3096758.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemVideo ItemCode
Rivière, Benjamin0000-0003-4189-4090
Hoenig, Wolfgang0000-0002-0773-028X
Anderson, Matthew0000-0001-8884-3448
Chung, Soon-Jo0000-0002-6657-3907
Additional Information:© 2021 IEEE. Manuscript received February 24, 2021; accepted June 24, 2021. Date of publication July 14, 2021; date of current version July 26, 2021. This work was supported by the Defense Advanced Research Projects Agency (DARPA). The views, opinions and/or findings expressed are those of the authors, and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Preliminary work was in part funded by Raytheon. Video: Code:
Group:GALCIT, Center for Autonomous Systems and Technologies (CAST)
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Raytheon CompanyUNSPECIFIED
Subject Keywords:Distributed robot systems, motion and path planning, reinforcement learning
Issue or Number:4
Record Number:CaltechAUTHORS:20210510-141334067
Persistent URL:
Official Citation:B. Rivière, W. Hönig, M. Anderson and S. -J. Chung, "Neural Tree Expansion for Multi-Robot Planning in Non-Cooperative Environments," in IEEE Robotics and Automation Letters, vol. 6, no. 4, pp. 6868-6875, Oct. 2021, doi: 10.1109/LRA.2021.3096758.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109046
Deposited By: George Porter
Deposited On:10 May 2021 21:34
Last Modified:05 Aug 2021 20:54

Repository Staff Only: item control page