# Optimal Collision-Free Grip Planning for Biped Climbing Robots in Complex Truss Environment
## 1 Introduction
In [19; 20], the authors presented a novel footstep optimization method with mixed-integer convex constraints that could solve the problem to its global optimum. However, the generation of each reachable region deeply relied on the position of the previous step, increasing the time consumption. In addition, adjusting the parameters to approximate the reachable regions was always difficult and thus reduced the planning accuracy. [PERSON] et al. [21; 22] built global optimization models with non-linear constraints to find the maximum heights of the obstacles that can be overcome. The results were then used as a priori knowledge and a database for surmounting obstacles. However, they focused on how to stride across one obstacle only, but not generating the nearby footprint sequences. Please note that these footstep planning methods for humanoid robots are always applied in 2D or 2.5D environments, which differs from the grip planning for BiCRs in complex 3D truss environments. Figure 1: The 5-DoF Climbot and its kinematic diagram. To the best of our knowledge, the collision-free grip planning problem has rarely been studied in the literature. [PERSON] et al. [2; 23] treated the BiCRs' climbing path planning as a TSP-like problem. They modeled the environment as a graph with two categories of primitives. They then proposed a heuristic algorithm to solve the climbing path, along which the robot visited all beam faces without repetition. [PERSON] et al. [24] presented a path planning algorithm to optimize the locomotion sequences for the Shady3D robot. A set of potential gripping points was first dispersed in the truss environment up to a certain density. Then the shortest locomotion sequence represented with gripping points was computed with the Dijkstra's distance. Based on the framework of conventional genetic algorithm, [PERSON] et al. [25] adopted the concept of genetic modification to design a new genetic operator. They used this method to solve the climbing path with the minimum energy demand. However, these methods all suffer limitations from spending long planning time, ignoring specific transition movement, and not thinking about obstacle avoidance. [PERSON] et al. [7] discretized the tree surface into finite grasp points, then used a dynamic programming algorithm to identify the global path and adopted a motion planning algorithm to generate the single-step climbing motion. Therefore, this method was only applicable to BiCRs climbing on the object surface with non-enclosure grippers. It can only obtain a near-optimal solution. [PERSON] et al. [26] presented two optimal strategies to select a collision-free grip from its potential region based on three criteria step by step. However, this method lacks global guidance in searching, and hence, is inefficient most of the time. For BiCRs rapidly generating optimal collision-free grips, we have proposed a novel framework, which further subdivides the grip generation procedure into three steps:  
1. quick determination of all feasible climbing routes in global, outputting member sequence and corresponding grip orientation and operational regions for transition;
2. optimal arrangement of collision-free grips on the operational regions on each member along each feasible climbing route;
3. generation of the entire grip sequence with a gait interpreter. For Step (1), we have presented a high-efficiency global path planning method in [27]. Further to our previous work, we present an optimal collision-free grip planning method to minimize the number of climbing steps in this paper. The novelty of this paper is the first systematic presentation of an optimal collision-free grip planner for the biped climbing robots generating grip sequences in a complex truss environment. This grip planner not only handles well with the collision between the robot and the truss, but also guarantees the robot kinematics, the minimum number of climbing steps, the good manipulability of transition grips.