Leveraging Hyperbolic Embeddings for Coarse-to-Fine Robot Design

Thanks for the valuable comments and helpful suggestions. Here we provide additional experimental results and detailed explanations for your questions.

Weakness 1 & Question 1: The generalizability of the proposed approach to other robot design representations is uncertain. Testing the approach on one common robot design representation would make it more convincing. The coarse-to-fine process seems specialized for the cellular robot representation in EvoGym. Is it generalizable to other robot design representations, such as articulate rigid robots (e.g. Wang et al. 2019 [1], Gupta 2021 [2])?

A: Though our paper mainly focuses on multi-cellular robot design problems, our method HERD can still be extended to other robot design representations, such as articulate rigid robots. Here we provide a solution to this setting.

To implement the idea of coarse-to-fine robot design in rigid robots, the major challenge is to define the refinement process for coarse-grained robot designs. Once the refinement definition is given, we can organize the design space as a hierarchy through recursive refinement, embed the hierarchy in hyperbolic space, and use CEM for optimization as we did in the paper. In the following, we discuss the refinement of rigid robots in detail.

Formally, a rigid robot design $D$ can be represented by a tree $D=(V,E,g,h)$, where each vertex $v\in V$ represents a joint in robot morphology and each edge $e=(v_i,v_j)\in E$ represents a limb connecting two joints $v_i,v_j$ and $|E|=|V|-1$. The function value $g(v)$ defines joint-specific attributes and function value $h(v_i,v_j)$ defines limb-specific attributes.

The intuition behind the solution is to regard the coarse-grained robot as a simplified tree, to which we enrich details such as adding new vertices and new edges during refinement, such that the fine-grained robot has a 'similar' shape to the coarse-grained robot. Given a design $D$, we denote the finer-grained design of $D$ by $D'=(V',E',g',h')$. $D'$ is a valid refinement of $D$ if and only there is a vertex map $\pi:V'\to V$ such that the following conditions are satisfied:

(i) (coarse-to-fine condition): $|V|<|V'|$;

(ii) (edge condition): the edge $e'=(v'_i,v'_j)\in E'$ if and only if there is an edge $e=(v_1,v_2)\in E$ such that $\pi(v'_i)=v_i$ and $\pi(v'_j)=v_j$;

(iii) (vertex attribute condition): for each $v'\in V'$, we have $g'(v')=g(\pi(v'))$;

(iv) (edge attribute condition): for each $e'=(v'_i,v'_j)\in E'$, we have $h'(v_i',v_j')=h(\pi(v_i'),\pi(v_j'))$;

The above conditions enable $D'$ to be one of the refinements of $D$ with a 'similar' shape. Given this refinement definition, we can then organize the design space of rigid robots as a hierarchy like multi-cellular robots and use the hyperbolic solution for coarse-to-fine optimization.

Due to the time limitation of rebuttal, we only provide a conceptual solution. We believe this could be a promising future work.

Weakness 2: The choice of Sarkar's construction for hyperbolic embedding needs more justification.

A: There are two reasons for this choice. Firstly, Sarkar's construction can embed the tree structure with arbitrarily low distortion [5], which matches our needs of embedding the tree of robot designs. Secondly, Sarkar's construction is a training-free method that will not bring extra computational cost and is also simple to implement.

Weakness 3: The experiments need improvements.

A: Thank you for your suggestions. We have improved our experiments by including the results of other tasks from EvoGym in Figure 25 of Appendix C in the revised reversion of our paper. Please refer to Question 8 for extra discussions.

Question 2: Since coarse-to-fine clustering is based on running K-Means with different random seeds, it seems to be possible that there are two robot designs located in different subtrees. Will such two designs be embedded in similar locations in the hyperbolic space?

A: There might be some misunderstandings. For each number of clusters, we only run K-Means once on robot cells per experiment. In this case, two similar robot designs will always be located in the same subtrees, then they will also be embedded in similar locations in the hyperbolic space.

Thank you for your detailed response. The additional results from the whole EvoGym tasks are helpful and thank you for the effort to put them together. After reading the response, I have two follow-up questions:

1. The answer to Question 2 confuses me further. Does running K-Means only once per experiment mean you only have one robot for each number of clusters? In other words, each robot design only has one child fine-grained design, is that the case? Otherwise, how do you get different child designs for one parent design with only one K-means run? More details about how this step works would be super helpful and is also relevant to my Question 3.

2. For the reply to my Question 7, I do think I understand correctly. The coarse-to-fine is mainly for constructing the design candidate pool instead of optimization. The optimization process shown in Algorithm 1 can be "automatic coarse-to-fine" but there is no theoretical guarantee. It basically finds the nearest design in the embedding space around the current CEM mean and it can be possible to get coarse-grained robots in the later stage of the algorithm. Feel free to point out if I misunderstood anything here or if there is any other missing special mechanism designed to enforce the coarse to fine optimization.

Thank you for your prompt response and further clarification on the robot construction process. Now I think it is clear to me how this process works. If I understand correctly, the short answer is that the cluster layout of all child robots under a parent robot are all the same while the only difference among them is their different choices of cell types. Also please update your manuscript about this detail, since I cannot find any explicit paragraph about this detail after I read the method section several times). Given this fact, I have one last question left.

Since you only run K-means once for each parent robot design to construct finer robot layouts, will it miss some large branches of robot structures and can it be a limitation of the proposed method? For example, assume we have 4x4 grid cells, if our first K-means cluster the cell into left and right clusters such as (A, B denote for different cell types) $AABB$ $AABB$ $AABB$ $AABB$ Is it still possible for the algorithm to get the robot in a top-down layout in its descendants as $AAAA$ $AAAA$ $BBBB$ $BBBB$ Since each round of the algorithm is only able to change the cell type of one cluster, it seems this structure branch will be missed and can limit the optimality of the algorithm.

Thank you for your prompt reply! Here we provide additional explanations to your questions.

Suggestion 1: If I understand correctly, the short answer is that the cluster layout of all child robots under a parent robot is all the same while the only difference among them is their different choices of cell types. Also please update your manuscript about this detail, since I cannot find any explicit paragraph about this detail after I read the method section several times).

A: This is a correct understanding. Thanks for the suggestion, we have updated our paper about this detail in Section 4.1.

Question 1: Since you only run K-means once for each parent robot design to construct finer robot layouts, will it miss some large branches of robot structures and can it be a limitation of the proposed method? For example, assume we have 4x4 grid cells, if our first K-means cluster the cell into left and right clusters such as (A, B denote for different cell types)

$$\begin{matrix} AABB \\\ AABB \\\ AABB \\\ AABB \end{matrix}$$

Is it still possible for the algorithm to get the robot in a top-down layout in its descendants as

$$\begin{matrix} AAAA\\\ AAAA\\\ BBBB\\\ BBBB \end{matrix}$$

Since each round of the algorithm is only able to change the cell type of one cluster, it seems this structure branch will be missed and can limit the optimality of the algorithm.

A: We would like to thank the reviewer for pointing this out and here we provide some analysis into this issue. In short, part of this problem may occur, but it will not affect the optimization too much and can be easily solved.

During our implementation, we did observe this issue. However, it is caused by the small number of mutations (the number of clusters to change), which is a hyperparameter. Actually, if we increase the value of this hyperparameter, we will be able to cover the entire design space definitely. For the sake of maintaining the similarity between parent robots and child robots, we set the value to $1$. There is a trade-off between this similarity and the coverage of design space. In the empirical study, we found that the final performance was sufficiently good when the number of mutations was set to $1$.

Apart from that, even though this hyperparameter is set to $1$, the robot hierarchy might still include most of Robot-1's child robots shown as follows:

$$\text{(Robot-1):} \begin{matrix} AAAA\\\ AAAA\\\ BBBB\\\ BBBB \end{matrix}\quad \text{(Children):} \begin{matrix} BBAA\\\ BBAA\\\ BBBB\\\ BBBB \end{matrix}\quad \begin{matrix} AABB\\\ AABB\\\ BBBB\\\ BBBB \end{matrix}\quad \begin{matrix} AAAA\\\ AAAA\\\ AABB\\\ AABB \end{matrix}\quad \begin{matrix} AAAA\\\ AAAA\\\ BBAA\\\ BBAA \end{matrix}$$

These child robots can be generated by mutating $2\times 2$ cells of the following left-right robots that are included in the current robot hierarchy:

$$\begin{matrix} AABB\\\ AABB\\\ AABB\\\ AABB \end{matrix}\quad \begin{matrix} BBAA\\\ BBAA\\\ BBAA\\\ BBAA \end{matrix}$$

Thanks again for your efforts and insightful comments! We hope our clarification addresses your concerns and sincerely appreciate it if you could re-evaluate our work.

Thanks for your positive comments and constructive suggestions. Here we provide extra visualization results and detailed explanations for your questions.

Weakness 1: It's unclear to me how exactly any point on the manifold corresponds to a robot configuration. Some concrete examples may help to understand. If I randomly sample a point using a coordinate, what's the robot configuration it corresponds to? It seems that human has to handcraft such rules.

A: We would like to clarify that we do not have to handcraft such rules. Instead, we simply calculate the distance between the sampled point and other points that are embedded in the hyperbolic manifold. Then we choose the point and its corresponding robot design with minimum distance. Please refer to Figure 21 in Appendix B.2 in the revised version of our paper for a simplified visualization.

Question 1: It's unclear how general the hyperbolic space is for robotics design. The authors chose the Poincare ball as the hyperbolic embedding space for the design tree. I am wondering how general this is. In particular, the hyperbolic manifold seems very limiting. For example, let's say the robot can be comprised of material A and material B. From the center, I extend two different trees branching towards material A and material B separately. However, in each branch, fine-grained branches start to contain configurations that blend A & B which means the two branches should merge. In this case, you will have to have a finite cylinder manifold, correct?

A: Thanks for the idea. In our experiment, the "branch-merge problem" might happen with a low possibility but will not influence the optimization severely. This is because our method HERD optimizes the robot designs starting from the center of the Poincaré ball, and it can automatically identify the promising sub-space regardless of whether the branches are merged or not. The idea of the finite cylinder manifold might further improve final performance, but optimizing within a three-dimensional space may also introduce additional complexities to the problem, which requires in-depth empirical investigation.

Question 2: How exactly does the manifold correspond to designs or robot parameters? How many branches are there? I understand how you map between the Euclidean space and the hyperbolic space but this seems unclear. Giving more visualizations across the disk manifold will be helpful.

A: To correspond a point in the manifold to a design, as we discussed in Weakness 1, we simply choose the pre-embedded robot design in the manifold with the minimum distance to the point.

The number of branches may vary with the level of the hierarchy of robot designs. For example, the number of branches originating from the root node only has two branches. As for the other level of the hierarchy, we restrict the number of branches originating from the same non-leaf node to $20$. This restriction may limit the search space, but since the hierarchy grows exponentially, the search space is still large enough to contain the designs that solve given tasks, as long as the number of branches exceeds a threshold.

Thanks for the suggestion of visualization. We have visualized the 'corresponding process' in a simplified disk manifold, as there are too many points in the original manifold to be visualized clearly. Please refer to Figure 21 in Appendix B.2 in the revised version of our paper for details

Thank you for your clarifications and additional visualizations.

I acknowledge that I've read your responses carefully as well peer reviewers' comments. After reading through reviewer Wtet's comments carefully, I realized there were a few components that I didn't fully understand in my first pass. However, your responses are very helpful to give me a better under standing.

Overall I think the merits of the paper still outweight its problems. On the other hand due to the reason below I decide to lower my confidence to 3.

Thanks for your comments and valuable suggestions. Here provide additional quantitative analysis of the proposed method and explanations for your questions.

Weakness 1: As one of the concerns of the multi-cellar system, the design space is very large, so how a hyperbolic solution solves this problem is not well examined.

A: Our method HERD solves the large space problem of multi-cellular system by adopting a coarse-to-fine robot design mechanism, in which HERD starts by finding the optimal coarse-grained robot designs and subsequently refines them. For a simple and better optimization, we embed any-grained robots in hyperbolic space and use Cross-Entropy Method to optimize robot designs in hyperbolic space. The design space is substantially reduced in this way because (1) the design space of coarse-grained robots that HERD optimizes first is much smaller than the original design space; (2) by using the guidance of coarse-grained designs, HERD focuses on promising sub-space without the needs to explore the whole space, which further reduces the design space. This intuition is elaborated in Figure 1 and the Introduction Section of our paper.

We have also examined the above solution empirically in our paper. We first show that HERD can successfully solve plenty of tasks in Figures 3 & 22, then we check the functionality of coarse-to-fine and hyperbolic embedding components in Figure 4, finally, we visualize the optimization process of HERD in Figure 5 for an in-depth understanding of how it works.

Weakness 2: The quantitative analysis of the proposed model is somewhat absent, some tables will help the understanding of the evaluation of different methods.

A: Thanks for the suggestion. We have revised our paper and updated several tables of the performance comparisons with baselines and ablation studies in Appendix D. Specifically, we compare our method HERD with various baselines in Table 2 and HERD outperforms other robot design methods in most tasks, which showcases the effectiveness of our method. We also display the numeric results of ablation studies in Table 3 in Appendix D, which demonstrates the validity of the main components of our method: coarse-to-fine robot design and hyperbolic embedding. Please refer to the updated version of our paper for detailed quantitative results.

Thanks for the comments and helpful suggestions. Here we provide detailed clarifications to your questions.

Weakness 1: The issue of local optimal (not very good performance compared to other baselines). HERD is not significantly better than baselines.

A: We respectfully disagree with this claim. Our method HERD is significantly better than baselines as shown in Figure 3 and Figure 22 of the paper, which includes 15 tasks. In summary, (1) HERD outperforms all the other robot design baselines (CuCo, Vanilla RL, BO, GA, CPPN-NEAT) in 12 tasks out of 15 tasks; (2) HERD is much better than HandCrafted Robot in 7 tasks and has a comparable performance in 5 tasks.

HERD utilizes a variant of the Cross-Entropy Method (CEM) for optimizing the coarse-to-fine robot design process. CEM is a popular stochastic optimization method due to its simplicity and effectiveness. Because of its population-based search and stochastic nature, it has less tendency to local optimality convergence than many other heuristic methods. Its global optimality can be further enhanced by using a mixture of Gaussian models [1], which can be an interesting direction for future work.

Weakness 2: The proposal method, HERD, appears to have no mechanism for exploration in the global design space.

A: There might be some misunderstandings. HERD has an exploration mechanism, which is built inherently in the Cross-Entropy Method (CEM) -- a stochastic optimization method we use. Concretely, HERD maintains a distribution of robot designs and optimizes the distribution with CEM. When sampling from this distribution, HERD explores the robot design space such that robots of lower performance will still be sampled, though with a relatively lower possibility.

Weakness 3: The issue of high variance in Figure 3.

A: We appreciate the reviewer pointing this out. High variance is a common challenge in the field of robot design. For example, GA in task Carrier-v1 and CuCo in task GapJumper-v0 also show high variance. One major cause of this problem is that the optimal control policies are possibly difficult to learn as the robot designs are changing over time. Similar robots might have totally different performances due to the learning issue of control policies. For a fair comparison, our method HERD together with baselines CuCo, Vanilla RL, and HandCrafted Robot adopt the same control policy architecture (transformers) and optimization algorithm (PPO). It is an open and important direction for future work to investigate more effective control policy learning methods in the field of robot design.

Weakness 4 & Question 4: Does the parent node of an optimal robot design node consistently outperform the parent node of a non-optimal robot design node? If not, coarse-to-fine seems greedy and vulnerable to local optimal. How can we guarantee that sequential refinements on a coarse design are better than sequential refinements on another coarse design, given that the former coarse design outperforms the latter coarse design?

A: We do not need to guarantee that "the parent node of an optimal robot design node consistently outperforms the parent node of a non-optimal robot design node", because our method HERD is not a greedy deterministic algorithm. As we discussed in Weakness 2, HERD uses a stochastic optimization method to optimize the distribution of robot design instead of one or several robot samples. Hence, HERD can still explore child nodes from another subtree if the current child nodes are less efficient.

Question 1: What are the policy architecture and learning methods adopted for the baselines? Are they the same as those of HERD?

A: The baselines CuCo, Vanilla RL, and HandCrafted Robot adopt the same control policy architecture (transformers) and learning method (PPO) as our method HERD. For the other baselines GA, BO, and CPPN-NEAT, we use their official implementations from CuCo and EvoGym.