Despite the recent successes in robotic locomotion control, the design of robot relies heavily on human engineering. Automatic robot design has been a long studied subject, but the recent progress has been slowed due to the large combinatorial search space and the difficulty in evaluating the found candidates. To address the two challenges, we formulate automatic robot design as a graph search problem and perform evolution search in graph space. We propose Neural Graph Evolution (NGE), which performs selection on current candidates and evolves new ones iteratively. Different from previous approaches, NGE uses graph neural networks to parameterize the control policies, which reduces evaluation cost on new candidates with the help of skill transfer from previously evaluated designs. In addition, NGE applies Graph Mutation with Uncertainty (GM-UC) by incorporating model uncertainty, which reduces the search space by balancing exploration and exploitation. We show that NGE significantly outperforms previous methods by an order of magnitude. As shown in experiments, NGE is the first algorithm that can automatically discover kinematically preferred robotic graph structures, such as a fish with two symmetrical flat side-fins and a tail, or a cheetah with athletic front and back legs. Instead of using thousands of cores for weeks, NGE efficiently solves searching problem within a day on a single 64 CPU-core Amazon EC2
 machine.
 The goal of robot design is to find an optimal body structure and its means of locomotion to best achieve a given objective in an environment. Robot design often relies on careful human-engineering and expert knowledge. The field of automatic robot design aims to search for these structures automatically. This has been a long-studied subject, however, with limited success. There are two major challenges: 1) the search space of all possible designs is large and combinatorial, and 2) the evaluation of each design requires learning or testing a separate optimal controller that is often expensive to obtain.In BID28 , the authors evolved creatures with 3D-blocks. Recently, soft robots have been studied in BID13 , which were evolved by adding small cells connected to the old ones. In BID3 , the 3D voxels were treated as the minimum element of the robot. Most evolutionary robots BID8 BID24 require heavy engineering of the initial structures, evolving rules and careful human-guidance. Due to the combinatorial nature of the problem, evolutionary, genetic or random structure search have been the de facto algorithms of automatic robot design in the pioneering works BID28 BID31 BID20 BID16 BID17 BID34 BID2 . In terms of the underlying algorithm, most of these works have a similar population-based optimization loop to the one used in BID28 . None of these algorithms are able to evolve kinematically reasonable structures, as a result of large search space and the inefficient evaluation of candidates.Similar in vein to automatic robot design, automatic neural architecture search also faces a large combinatorial search space and difficulty in evaluation. There have been several approaches to tackle these problems. Bayesian optimization approaches BID29 primarily focus on fine-tuning the number of hidden units and layers from a predefined set. Reinforcement learning BID38 and genetic algorithms BID19 are studied to evolve recurrent neural networks (RNNs) and convolutional neural networks (CNNs) from scratch in order to maximize the validation accuracy. These approaches are computationally expensive because a large number of candidate networks have to be trained from grounds up. BID25 and BID30 propose weight sharing among all possible candidates in the search space to effectively amortize the inner loop training time and thus speed up the architecture search. A typical neural architecture search on ImageNet BID15 ) takes 1.5 days using 200 GPUs BID19 .In this paper, we propose an efficient search method for automatic robot design, Neural Graph Evolution (NGE), that co-evolves both, the robot design and the control policy. Unlike the recent reinforcement learning work, where the control policies are learnt on specific robots carefully designed by human experts BID21 BID0 BID11 , NGE aims to adapt the robot design along with policy learning to maximize the agent's performance. NGE formulates automatic robot design as a graph search problem. It uses a graph as the main backbone of rich design representation and graph neural networks (GNN) as the controller. This is key in order to achieve efficiency of candidate structure evaluation during evolutionary graph search. Similar to previous algorithms like BID28 , NGE iteratively evolves new graphs and removes graphs based on the performance guided by the learnt GNN controller. The specific contributions of this paper are as follows:• We formulate the automatic robot design as a graph search problem.• We utilize graph neural networks (GNNs) to share the weights between the controllers, which greatly reduces the computation time needed to evaluate each new robot design.• To balance exploration and exploitation during the search, we developed a mutation scheme that incorporates model uncertainty of the graphs.We show that NGE automatically discovers robot designs that are comparable to the ones designed by human experts in MuJoCo , while random graph search or naive evolutionary structure search BID28 fail to discover meaningful results on these tasks. In this paper, we introduced NGE, an efficient graph search algorithm for automatic robot design that co-evolves the robot design graph and its controllers. NGE greatly reduces evaluation cost by transferring the learned GNN-based control policy from previous generations, and better explores the search space by incorporating model uncertainties. Our experiments show that the search over the robotic body structures is challenging, where both random graph search and evolutionary strategy fail to discover meaning robot designs. NGE significantly outperforms the naive approaches in both the final performance and computation time by an order of magnitude, and is the first algorithm that can discovers graphs similar to carefully hand-engineered design. We believe this work is an important step towards automated robot design, and may show itself useful to other graph search problems. A DETAILS OF NERVENET++ Similar to NerveNet, we parse the agent into a graph, where each node in the graph corresponds to the physical body part of the agents. For example, the fish in FIG0 can be parsed into a graph of five nodes, namely the torso (0), left-fin (1), right-fin (2), and tail-fin bodies (3, 4). By replacing MLP with NerveNet, the learnt policy has much better performance in terms of robustness and the transfer learning ability. We here propose minor but effective modifications to BID37 , and refer to this model as NerveNet++.In the original NerveNet, at every timestep, several propagation steps need to be performed such that every node is able to receive global information before producing the control signal. This is time and memory consuming, with the minimum number of propagation steps constrained by the depth of the graph.Since the episode of each game usually lasts for several hundred timesteps, it is computationally expensive and ineffective to build the full back-propagation graph. Inspired by BID22 , we employ the truncated graph back-propagation to optimize the policy. NerveNet++ is suitable for an evolutionary search or population-based optimization, as it brings speed-up in wall-clock time, and decreases the amount of memory usage.Therefore in NerveNet++, we propose a propagation model with the memory state, where each node updates its hidden state by absorbing the input feature and a message with time. The number of propagation steps is no longer constrained by the depth of the graph, and in back-propagation, we save memory and time consumption with truncated computation graph. The memory state h t+1,τ u depends on the previous actions, observations, and states. Therefore, the full back-propagation graph will be the same length as the episode length, which is very computationally intensive. The intuition from the authors in BID22 is that, for the RL agents, the dependency of the agents on timesteps that are far-away from the current timestep is limited. Thus, negligible accuracy of the gradient estimator will be lost if we truncate the back-propagation graph. We define a back-propagation length Γ, and optimize the following objective function instead: DISPLAYFORM0 DISPLAYFORM1 Essentially this optimization means that we only back-propagate up to Γ timesteps, namely at the places where κ = 0, we treat the hidden state as input to the network and stop the gradient. To optimize the objective function , we follow same optimization procedure as in BID37 , which is a variant of PPO Schulman et al. (2017) , where a surrogate loss J ppo (θ) is optimized. We refer the readers to these papers for algorithm details.
Automatic robotic design search with graph neural networks Proposes an approach for automatic robot design based on Neural graph evolution. The experiments demonstrate that optimizing both controller and hardware is better than optimizing just the controller. The authors propose a scheme based on a graph representation of the robot structure, and a graph-neural-network as controllers to optimize robot structures, combined with their controllers.  