## 3 Fast-Path-Plan Algorithm Considering the Fixed-Wing Aerial Vehicle's Turn Rate Limit
```
1:Form \(q\) viableMotionPoints on \(S_{n}\) using \(n\) and \(parent(n)\) (see (15));
2:for i=1:1:q do
3:if\(i\)-th viableMotionPoint satisfies the safety requirement for a motionPoint then
4: Store the viableMotionPoint as a motionPoint of \(n\);
5:endif
6:endfor
```
**Algorithm 1**\(GenerateOpenSimulationNode(n,parent(n))\)
```
1:Among all simulation nodes, \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:Among all motionPoints of \(n^{c}\), \(R\) finds a point which is the nearest to the destination \(\mathbf{D}\), and \(R\) sets it as \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
10:if\(n^{c}\) has no motionPoints then
11:\(n^{c}\) is closed;
12:endif
```
**Algorithm 2**\(R\_moveToOpenSimulationNode\)
```
1:Let \(n_{init}\) stand for the first simulation node spawned at the location of the real fixed-wing aerial vehicle;
2:Form a new simulated vehicle \(R\) at \(n_{init}\);
3:repeat
4:\(R\) spawns a new simulation node, say \(n\), at its 3D location, if there is no simulation node at its location;
5:\(GenerateOpenSimulationNode(n,parent(n))\) in Algorithm 1;
6:\(R\_moveToOpenSimulationNode\) in Algorithm 2;
7:if\(AlgorithmDone\) is TRUE then
8: Re-run Algorithm 3 (re-plan the path from \(n_{init}\) to \(D\));
9:endif
10:until\(R\) under the maximum turn rate limits ((6) and (7)) can track along the segments connecting \(Line(parent(n),n)\) and \(Line(n,g)\) without collision;
11:Set \(n\) as \(parent(g)\), the parent of the destination \(D\);
12:Form a path from \(n_{init}\) to \(D\) by backtracking the parent relationship starting from \(D\);
13:The real fixed-wing aerial vehicle at \(n_{init}\) tracks along the formed path;
14:if the real fixed-wing aerial vehicle abruptly senses a new obstacle which has not been sensed before then
15:Delete motionPoints that are inside the newly sensed obstacle;
16:Re-run Algorithm 3 (re-plan the path from \(n_{init}\) to \(D\));
17:endif
```
**Algorithm 3** Three-dimensional path planner considering the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:Among all motionPoints of \(n^{c}\), \(R\) finds a point which is the nearest to the destination \(\mathbf{D}\), and \(R\) sets it as \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
10:if\(n^{c}\) has no motionPoints then
11:\(n^{c}\) is closed;
12:endif
```
**Algorithm 4** Three-dimensional path planner considering the real fixed-wing aerial vehicle's turn rate limits
```
1:Let \(n_{init}\) stand for the first simulation node spawned at the location of the real fixed-wing aerial vehicle;
2:Form a new simulated vehicle \(R\) at \(n_{init}\);
3:repeat
4:\(R\) spawns a new simulation node, say \(n\), at its 3D location, if there is no simulation node at its location;
5:\(GenerateOpenSimulationNode(n,parent(n))\) in Algorithm 1;
6:\(R\_moveToOpenSimulationNode\) in Algorithm 2;
7:if\(AlgorithmDone\) is TRUE then
8: Re-run Algorithm 3 (re-plan the path from \(n_{init}\) to \(D\));
9:endif
10:until\(R\) under the maximum turn rate limits ((6) and (7)) can track along the segments connecting \(Line(parent(n),n)\) and \(Line(n,g)\) without collision;
11:Set \(n\) as \(parent(g)\), the parent of the destination \(D\);
12:Form a path from \(n_{init}\) to \(D\) by backtracking the parent relationship starting from \(D\);
13:The real fixed-wing aerial vehicle at \(n_{init}\) tracks along the formed path;
14:if the real fixed-wing aerial vehicle abruptly senses a new obstacle which has not been sensed before then
15:Delete motionPoints that are inside the newly sensed obstacle;
16:Re-run Algorithm 3 (re-plan the path from \(n_{init}\) to \(D\));
17:endif
```
**Algorithm 5** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:Among all motionPoints of \(n^{c}\), \(R\) finds a point which is the nearest to the destination \(\mathbf{D}\), and \(R\) sets it as \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
10:if\(n^{c}\) has no motionPoints then
11:\(n^{c}\) is closed;
12:endif
```
**Algorithm 6** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:Among all motionPoints of \(n^{c}\), \(R\) finds a point which is the nearest to the destination \(\mathbf{D}\), and \(R\) sets it as \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
10:if\(n^{c}\) has no motionPoints then
11:\(n^{c}\) is closed;
12:endif
```
**Algorithm 7** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:Among all motionPoints of \(n^{c}\), \(R\) finds a point which is the nearest to the destination \(\mathbf{D}\), and \(R\) sets it as \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
10:if\(n^{c}\) has no motionPoints then
11:\(n^{c}\) is closed;
12:endif
```
**Algorithm 8** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
2:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
13:\(R\) moves to \(f_{R}\);
14:\(R\) moves to \(f_{R}\);
15: Store \(n^{c}\) as the parent of \(f_{R}\);
16:\(R\) moves to \(f_{R}\);
17:\(R\) moves to \(f_{R}\);
18: Store \(n^{c}\) as the parent of \(f_{R}\);
19:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
20:if\(n^{c}\) has no motionPoints then
21:\(n^{c}\) is closed;
22:endif
```
**Algorithm 9** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is nearest to the destination \(\mathbf{D}\);
23:\(AlgorithmDone\)=FALSE;
3:if no openSimulationNode can be found among all simulation nodes then
4:\(AlgorithmDone\)=TRUE;
5:endif
6:\(R\) moves to \(f_{R}\);
7:\(R\) moves to \(f_{R}\);
8: Store \(n^{c}\) as the parent of \(f_{R}\);
9:\(f_{R}\) is deleted from a motionPoint of \(n^{c}\);
24:if no motionPoints then
25:\(n^{c}\) is closed;
26:endif
27:endif
28:endfor
```
**Algorithm 10** Three-dimensional path planner for the real fixed-wing aerial vehicle's turn rate limits
```
1:For \(n_{init}\), \(R\) searches for an openSimulationNode, say \(n^{c}\), which is Recall that Algorithms 1 and 2 are sub-algorithms of Algorithm 3.