Robotic Co-Design: Graph Grammar & MCTS in the Rostok Framework

Table of Links

Abstract and I. Introduction

II. Methods

III. Generation of Tendon Driven Grippers

IV. Results and Discussion

V. Conclusion and References

II. METHODS

In our approach the GD of dynamic systems can be decoupled into three sub-tasks: (1) generation of the mechanism morphology, (2) optimisation of its kinematic and dynamics parameters, and (3*) optimisation of control efforts*. Within this paper, the main focus is on the morphology of an underactuated tendon-driven griper, i.e. how many links and how they are jointed to form a mechanism, such that the gripper can grasp objects blindly without object-shape-based trajectory planning or behavior cloning. The only information regarding an object to be grasped is the position of its geometrical center expressed in gripper’s palm frame.

A. Graph grammar

Our approach requires a suitable way to represent different structures and to use search algorithms. For the “rostok” we chose to encode mechanisms in the form of graphs. The graph representation is frequently used for robot design [12], [18], [19]. In a graph, nodes typically symbolize components of mechanisms while the edges define their connections.

To effectively use the graph representation of designs, we must limit the search space to the graphs that represent mechanisms that can be manufactured, i.e., satisfy the conditions of existence. We apply the graph grammar for two reasons: limit the graph space and guide the search algorithm.

The graph grammar approach to graph synthesis requires two essential parts: set of nodes and vocabulary of production rules (Fig. 2). The set of nodes includes all possible node types that can appear in the graphs, however, several nodes of the same type can occur in a graph. Within the paper we limited a range of nodes to the minimal needed to generated planar open-chain linkages with revolute joints.

The production rules determine the possible transformations of a graph. Each rule mutates the current graph into a new one. As a result, in the grammar scheme, the graph space is limited to the set of graphs that can be built by applying a consequence of rules. User can design the rule vocabulary and set of nodes in such a way that all graphs represent either the mechanism that can be assembled or some intermediate state that can be mutated to the mechanism representation via rule application. The node alphabet and rules depend on the specific task of GD and the design space must be explored.

B. Reward function

We use the graph grammar to turn GD tasks into graph optimization problems. The optimization problem in graph space requires a mechanism of graph evaluation and comparison. This idea can be summarized into a reward function that can evaluate each proposed design. Through the reward function one tells the algorithm what is actually considered to be a good mechanism. The design of the reward function is the part of the GD permitting the vast space for variation and requires the most creativity.

In our paradigm of the GD, the algorithm has to generate graphs and calculate reward to evaluate the generated solution. Graph grammar approach is especially effective for building mechanism morphology, because it can restrict the graph space to only feasible mechanisms. In “rostok” we use graph grammar to search the morphology space. User can optimize robot parts by using global optimization algorithms or by incorporating it into the production rules. The same is true for control optimization tasks; they can be performed independently or added to the grammar rules, e.g. torques limits can be set directly to the graph of an actuated joints.

The “rostok” pipeline assumes the usage of the mechanism simulations as a main part of the reward calculation. Therefore, one needs to build an automatic way to convert the graph into the simulation models with the desired setup. In our experience, it is the hardest part of the process, since simulation models must satisfy verification and validation to

minimize reality gap. The framework utilizes the PyChrono multiphysical modeling engine, the Python version of the Project Chrono C++ modeling library [20] for multi-body simulation of the design mechanisms.

As the reward calculation is simulation-based, our evaluation is limited to the graphs that depict the final robot design. However, it’s important to note that the graph space encompasses the intermediate states as well. Any particular intermediate state can be used to isolate a graph subspace that can be approached from that state by applying the grammar rules. Therefore, one can use the finished mechanisms in the subspace for intermediate state evaluation.

C. Graph search algorithm

To explore the vast design space of possible solutions we need a heuristic search algorithm. Currently, the applied algorithms support only generation of open chain mechanisms. Therefore, we can restrict grammar rules so that they only add elements to design morphology. The search space can be represented as a tree with all possible states. We can use any search algorithm to find solutions on the tree.

We implemented the MCTS algorithm because it is simple to implement, it showed acceptable results, and it can be used to compare other more efficient search algorithms, such as GNNs [12], that we plan to integrate later.