# Transition Analysis and Its Application to Global Path Determination for a Biped Climbing Robot
## 4 Fast Determination of Feasible Global Paths
### Principle and Flowchart  
The basic idea is to find out all the feasible routes from the current state based on our transition analysis in Section 3, and then reserve only those terminated at the expected destination. Tree data structure is a good choice to organize the route exploration and record all the feasible routes. Each node of a tree stores the information of a member and associated operational regions for transiting to from its parent node (the former member). Let the member the robot initially grips on be the root node and ensure the leaf nodes represent the destination member. In this way, each route from the root to the leaf forms a global path from the original point to the destination, containing the necessary information for transition, i.e., members and operational regions. Figure 7 shows us the flowchart. First of all, the original and destination members are extracted by checking which members the points \(\Psi\mathbf{P}_{init}\) and \(\Psi\mathbf{P}_{goal}\) are located on. Secondly, all the members are checked in pairs with preliminary requirements in Equations (6) and (7). The results are stored in an adjacency matrix, as shown in Algorithm 1. Elements of this matrix refer to the preliminary possibility of transition between two members indicated by the row and the column indexes. Thirdly, a tree data structure (path tree for short) rooted at the original member is then built up according to the adjacency matrix and the following rules, as in Algorithm 2. * Never go backwards. * Stop going forwards only when either the destination member is reached or there is no member that it has never been to. Those branches not terminated at the destination member are pruned off promptly in order to keep the tree data structure on a small scale, which is helpful for improving the solving efficiency. Fourthly, the above path tree will be traversed and inspected by analyzing strict constraints for transition presented in Section 3.2 and shown in Algorithm 3. This process starts from the root and spreads to the leaves. In other words, each route from the root to any of leaves will be inspected. Figure 7: The flowchart of global path planning. Branches will be grafted onto the tree if more than one possible gripping orientations result in operational regions for transition. Conversely, a branch will be pruned off once its corresponding transition is verified to be impossible. It should be noted that the pruning operation must ensure that the tree leaves can only be the destination member at this moment. After traversing the entire tree, the remaining routes if any, are feasible global paths. Finally, feasible global paths are obtained by tracing back from the leaves to the root. Each route consists of a sequence of members with specific gripping orientations and the corresponding operational regions for transition. ```
1:\({}^{W}S\): the truss;
2:\(l_{i}\): lengths of robot linkages. 3:\(AM\): the adjacency matrix. 4:\(N\Leftarrow\textsc{NumberOfmembers}({}^{W}S)\)
5:for\(i=1\)to\(N-1\)do
6:for\(j=i+1\)to\(N\)do
7:\(M_{i}\Leftarrow\textsc{GetMember}({}^{W}S,\ i)\);
8:\(M_{j}\Leftarrow\textsc{GetMember}({}^{W}S,\ j)\)
9:\(D\Leftarrow\textsc{Distance}(M_{i},\ M_{j})\);
10:\(R\Leftarrow\textsc{Relationship}(M_{i},\ M_{j},\ {}^{W}G)\);
11:if\(D\) and \(R\) satisfy Equations (6) and (7) then // Transition may be possible
12:\(AM(i,\ j)\Leftarrow\textbf{true},\ AM(j,\ i)\Leftarrow\textbf{true}\);
13:else // Transition is definitely impossible
14:\(AM(i,\ j)\Leftarrow\textbf{false},\ AM(j,\ i)\Leftarrow\textbf{false}\);
15:endif
16:endfor
17:\(AM(i,\ i)\Leftarrow\textbf{false}\);
18:endfor
```  
**Algorithm 1**Building up the adjacency matrix  
```
1:\(AM\): the adjacency matrix;
2:\(\chi(i)\): the member the robot moving on in current iteration;
3:\(\chi(m)\): the destination member;
4:\(T\): the path tree from last iteration. 5:\(T\): the path tree updated in each iteration.