# Transition Analysis and Its Application to Global Path Determination for a Biped Climbing Robot
## 4 Fast Determination of Feasible Global Paths
### Principle and Flowchart
GetNode\((iter(i)))\);
13:for\(j=1\)to\(T\). NumberOfParents\((iter(i))\)do
14:\({}^{W}_{U}\!\!\!\!R\Leftarrow T\). GetGripOrient\((iter(i),\ j)\); // Extract corresponding gripping orientation
15:if\(T\). IsLeaf\((iter(i))\)then // Reach the destination member
16:\({}^{W}_{V}\!\!\!\!R\Leftarrow{}^{W}_{B}\!\!\!R_{goal}\), \(K=[1]\);
17:elseif\(\zeta_{M2}=0\)then // Transition to a cylindrical member
18:\({}^{W}_{V}\!\!\!\!R\Leftarrow\textsc{SelectOrientation}(M2)\), \(K=[1]\);
19:else // Transition to a squared member
20:\({}^{W}_{V}\!\!\!\!R\Leftarrow T\). InitGripOrientation\((M2)\);
21:\(K=[1,\ 2,\ 3,\ 4]\);
22:endif
23:endif
24:for each\(k\) in \(K\)do // Check each potential gripping orientation
25:\((t_{1},\ t_{2})\Leftarrow\textsc{Algorithm}\) 4\((M1,\ M2,\ ^{W}_{U}\!\!\!\!\!R,\ ^{W}_{V}\!\!\!\!R)\);
26:if\(t_{1}\
eq\emptyset\)then // Trasisition is feasible
27:\(T^{ori}\). AddNode\((iter(i),\ ^{W}_{V}\!\!\!\!\!R,\ t_{1},\ t_{2})\);
28:endif
29:\({}^{W}_{V}\!\!\!\!R\Leftarrow{}^{W}_{R}(\pi/2)^{W}_{V}\!\!\!\!R\); // Prepare for another gripping orientation
30:endfor
31:\(i++\);
32:endwhile
```
**Algorithm 1** shows us the implementation of building up the \(N\times N\) symmetric adjacency matrix. Each element of the matrix stores a binary value, indicating whether a pair of members is translitable or not, i.e., the transition between \(Member\ i\) and \(Member\ j\) is possible if \(AM(i,j)=true\) and impossible if \(AM(i,j)=false\). The probabilities for transition between each pair of members are inspected successively, according to the preliminary requirements concerning about the reachability and safety, i.e., Equations (6) and (7). Binary values are then assigned to corresponding elements. Algorithm 2 implements the generation of the path tree according to the adjacency matrix from Algorithm 1, and the original and destination members. Algorithm 2 is actually a recursive function that calls itself iteratively, so that the path tree \"grows up\" from the root to leaves step by step. During each iteration, it extracts all transitable members from the current one, removes those visited, then adds the remaining members to the path tree. Such an iteration repeatedly goes on until the robot arrives at the destination member or has no new members to visit. The obtained path tree should be \"scanned\" and pruned if necessary, keeping only those branches with the destination member as leaves. Algorithm 3 traverses the obtained path tree in a breadth-first sequence, inspecting all transitions from a parent node to the present one with strict constraints. For squared members, all four gripping directions will be sent to Algorithm 4 for inspection. This is because a squared member has four potential gripping directions for a V-shaped palm gripper, which are around its center axis by an angular interval of \(\pi/2\). As a result, new branches may be grafted onto the path tree if more than one gripping directions result in operational regions for transition. Regarding the transit to an upright cylindrical member, the possible gripping directions are unlimited, as demonstrated in Equation (13). In this case, we can select an optimal gripping direction, for example to balance the difficulties of two consecutive transitions, i.e., from the parent node to the present one, and from the present node to the child one. ```
1:\( \begin{array}{l}\text{$W$}\text{$P$: reference point of Member 1;}\\ \text{$W$}\text{$P$: reference point of Member 2;}\\ \text{$W$}\text{$R$: gripping orientation on Member 1;}\\ \text{$W$}\text{$R$: gripping orientation on Member 2.}\\ \text{$W$}\text{$t_{1}$: operational region for transition on Member 1;}\\ \text{$t_{2}$: operational region for transition }\end{array}