# Sampling-Based Motion Planning for Free-Floating Space Robot without Inverse Kinematics
## 3 Motion Planning Algorithm for FFSRs  
In this paper, an RRT-based planning algorithm is designed for FFSRs from an initial configuration to a goal EE pose. In this method, it is not necessary to solve the inverse kinematics to obtain a goal configuration corresponding to the target EE pose. RRTs have a tree data structure, and this data structure includes vertexes and edges. Vertexes are configurations of FFSRs, and edges are local trajectories. In the basic version of RRTs, the tree takes root in the initial configuration and grows in an iterative manner. In each iteration, local planning is performed from one node of the existing tree to generate a new edge and a new node. The algorithm is not terminated until EE reaches the goal or the number of iterations reaches the upper limit. In the process of local planning, guide points are used to guide the growth of the tree. Guide points can be a random configuration or the goal EE pose, respectively called random configuration guiding growth (RC-GG) and goal EE pose guiding growth (GEE-GG). GEE-GG ensures the rapid convergence of the algorithm. RC-GG guarantees that the algorithm does not fall into a local minimum caused by goal bias. For the RRT algorithm, when using the goal EE pose to guide the growth of the tree, the tree will be directly extended toward the area closer to the goal EE pose, and this will speed up the convergence of the algorithm. However, if the tree only extends directly toward the goal EE pose, sometimes it will be stuck by obstacles or configuration limits, which means that the algorithm falls into a local minimum. When using a random configuration to guide the growth of the tree, the tree will be extended toward the unexplored area, and this will guarantee that the algorithm does not fall into the local minimum caused by GEE-GG. RRTs introduce GEE-GG to a certain probability; otherwise, it will perform random guided growth. That is, in each iteration of RRTs for FFSRs, Line 3 of Algorithm 1 generates a random number within 0-1. If this generated random number is smaller than the constant _p_g_, the goal EE pose will be selected as the guiding point. Otherwise, a random configuration will be selected as the guiding point. _p_g_ is a constant between 0 and 1. After selecting the guiding point, according to certain criteria, the node closest to the guide point in the existing tree is selected as the node to be extended. We define this node as _q_Extended_. Then, the algorithm performs local planning, which can extend the tree toward the guiding point. Collision detection is performed when necessary during local planning. The result of local planning includes a new node and a local trajectory, and they can be added to the tree if they meet some requirements. The pseudo-code of the basic RRT algorithm is shown in Algorithm 1. RC-GG and GEE-GG are subalgorithms of Algorithm 1. RC-GG is used in Line 6 of Algorithm 1 and GEE-GG is used in Line 4 of Algorithm 1. Variables and functions used in Algorithm 1 are defined in Table 1.  
```
1 Tree.V.init(q_I)
2 fori = 1 to Kdo
3 Ifi  rand() < p_g
4[q_new, Local_Traj, is_Reaching_Goal, Is_Extend] = Extend_Toward_Goal()
5 Else
6[q_new, Local_Traj, Is_Extend] = Extend_Randomly()
7 Endif1
8 If2 Is_Extend = true
9 Tree.Add(q_new, Local_Traj)
10 Endif2
11 If3 is_Reaching_Goal = true
12 Break;
13 Endif3
14 Endfor
15 Return tree

### Overview of the Algorithm

For RRTs, the key steps include random sampling, selection of \(q_{Extended}\), local planning, and collision detection. FFSRs are nonholonomic, and their attitude disturbance during the motion cannot exceed a certain range. Therefore, the following problems must be considered and solved when using RRTs for motion planning of FFSRs:

1. **Random sampling**: The configuration space of the FFSR includes the joint space and the space of the base attitude. In order to meet the constraint on base attitude disturbance, it is necessary to limit the sampling space of the base attitude. 2.