# Aircraft Parking Trajectory Planning in Semistructured Environment Based on Kinodynamic Safety RRT∗

Authors: Xianglei Meng; Nengjian Wang; Qinhui Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

To improve the safety and effectiveness of autonomous towing aircraft aboard the carrier deck, this study proposes a velocity-restricted path planner algorithm named as kinodynamic safety optimal rapidly exploring random tree (KS-RRT∗) to plan a near time-optimal path. First, a speed map is introduced to assign different maximum allowable velocity for the sampling points in the workspace, and the traverse time is calculated along the kinodynamic connection of two sampling points. Then the near time-optimal path in the tree-structured search map can be obtained by the rewiring procedures, instead of a distance-optimal path in the original RRT∗ algorithm. In order to enhance the planner’s performance, goal biasing scheme and fast collision checking technique are adopted in the algorithm. Since the sampling-based methods are sensitive to their parameters, simulation experiments are first conducted to determine the optimal input settings for the specific problem. The effectiveness of the proposed algorithm is validated in several common aircraft parking scenarios. Comparing with standard RRT∗ and human heuristic driving, KS-RRT∗ demonstrates a higher success rate, as well as shorter computation and trajectory time. In conclusion, KS-RRT∗ algorithm is suitable to generate a near time-optimal safe path for autonomous high density parking in semistructured environment.


---

## Body

## 1. Introduction

Aircraft parking aboard the carrier deck is a carefully planned procedure in naval operations standardization [1], and its safety and effectiveness are essential in determining the sortie generation capacity of air wing [2]. Currently, the aircraft movement afloat mainly relied on manually operated towing tractor with extra personnel to ensure the safety of parking route. However, the aircraft parking operation is usually manpower intensive and time-consuming evolution with low reliability, which creates a more hazard situation for the already congested deck environment leading to mishaps [3]. Therefore, it is imperative to introduce an autonomous path planner that can speed up the aircraft parking operations with major improvements in safety and reduction in total manpower.Path planning is both a kinematic and geometric problem that specifies a set of configurations from one place to another and meanwhile avoids obstacles. And it is proved to be PSPACE-hard problem [4], especially difficult for vehicles under nonholonomic and dynamic constraints. Considerable efforts are devoted to solve this problem. The algorithms of graph searching methods [5–7] give a path solution by discretizing the state of workspace and visiting different states, while the state space is always so large that evaluating every potential solution is computational costly. The interpolating curve-based planners [8–12] are more suitable for local planning, but they consume too much time when managing obstacles in real time. The function-based optimization methods [13, 14] can easily account for different constraints, but the function optimization happens in each state of motion that usually consumes too much time. Therefore, these methods are not suitable for quickly generating optimal path in real-time application. In contrast, the sampling-based methods are incremental sampling and random searching approaches by covering the workspace of tree structure that yield good performance in practice, which could quickly generate feasible solution in high dimensional state space [15]. Rapidly random tree (RRT) [16] algorithm is a powerful sampling-based path planner, and it has been proved to be probabilistically complete to generate a feasible path but in no sense of being optimal. Subsequently, a variant of RRT, called RRT∗ [17], is proposed to achieve being asymptotically optimal by rewiring the random search tree structure for lower cost.Now that the RRT∗ algorithms have been widely used in the autonomous path planning [18–23], its effectiveness in specific problem still needs to be explored. Figure 1 shows a common aircraft parking operation in a cluttered environment. The traditional sampling-based algorithm prefers the dotted straight line between the start and goal spot across the obstacles (black polygons). However, with consideration for safety, following such distance-optimal path will require much too slow speed to be safe. In this example, the true optimal path is that the aircraft can be towed around the obstacles (solid line) at its maximum allowable speed, which results in a minimum parking time.Figure 1
An illustration of aircraft parking scenario. The dotted line is an optimal path without considering safety. The solid line is an approximate time-optimal solution with respect of safety.Therefore, this study presents a variant of RRT∗, called Kinodynamic Safety RRT∗ (KS-RRT∗), which adopts a speed map to assign different reference safety velocities in the searching space and introduces a time-based metric to determine an optimal path for aircraft parking operation. In addition, to quickly generate a near optimal trajectory as the time critical nature of deck operations requires, the primitives of the RRT∗ algorithm are also modified, including goal bias sampling and expansion-based fast collision checking strategies. The effectiveness of KS-RRT∗ is estimated in multiple common aircraft parking scenarios and compared with standard RRT∗ and a human driving heuristic.The remainder of this study is organized as follows. Section2 introduces occupancy cost map combined with a speed map, describes the development of the tractor-aircraft dynamics, and proposes the modified RRT∗ algorithm. Section 3 evaluates the algorithm through a set of scenarios and interprets the simulation results. Section 4 concludes the paper.


## 2. Methods

### 2.1. Speed Combined Cost Map

The autonomous tractor is expected to steer the aircraft to an available parking spot. Figure2(a) shows the operating environment as a 2D occupancy grid, including available and occupied parking spots, deck markings, and obstacles such as other aircraft (black polygons). This paper assumes such map is fully known by a flight deck monitor system [24].Figure 2
A notional aircraft carrier flight deck layout (a) and its corresponding speed map (b). Blue colour represents the velocity in the obstacle area; green colour represents the safety velocity in the buffer contour around the obstacle area; warm toned colour (yellow to orange) represents the maximum velocity in the sparseness area.
(a)(b)For considering the safety velocity restrictions and maintaining safe clearance for the tractor-aircraft maneuvering in close-quarters, a speed map is generated for assigning different maximum allowable velocity in the environment (Figure2(b)). According to the naval operations standards [2], we confine different velocities in the obstacle areas (vobs), the safety velocity (vsafe) in the buffer contour d around the obstacle (making sure the towed aircraft can be slowed to an immediate stop), and the maximum velocity (vmax) in the sparseness areas that there are no obstacles in the vicinity.


### 2.2. Tractor-Aircraft Kinematics

Figure3 shows a non-rod tractor that directly attaches to the front wheel of an aircraft, creating a tractor-aircraft articulated system. The kinematics functions of such two-body system [25] can be written as follows:(1)x˙a=vcosθa,y˙a=vsinθa,θ˙a=vlatanφ,x˙b=vcosθbcosθa−θb,y˙b=vsinθbcosθa−θb,θ˙b=vlbsinθa−θb,where (xa, ya) is the tractor’s mass position that lies in the middle of its rear wheel axle and θa is the orientation of the tractor; v denotes the linear velocity of the tractor; x˙a and y˙a are the horizontal and vertical linear velocity, respectively; and θ˙a is the angular velocity of the tractor. Similarly, the aircraft’s state is presented as (xb, yb, θb). And la and lb are the wheelbases of the tractor and aircraft; f is the tractor’s steering angle, and it cannot exceed its maximum rotation angle |φmax|, which leads to a minimum turning radius rmin. Notice that the moving speed is limited by safety velocity vmax, and the inertial effect that brings the slipping of wheels can be ignored.Figure 3
Two-body tractor-aircraft towing system. The motion of the tractor-aircraft towing system is described by equation (1).


### 2.3. KS-RRT∗ Algorithm

In order to improve the safety and effectiveness, we propose a velocity-restricted KS-RRT∗ algorithm to plan a near time-optimal path in the semistructured cluttered environment.The primitives of KS-RRT∗ algorithm include goal bias sampling, kinodynamic local steering, expansion-based fast collision checking, and time-based rewiring procedures. Algorithm 1 outlines the KS-RRT∗ algorithm. At first, a single vertex is initialized in the tree graph as G (V, E). For each iteration of generating random sample nodes, a node xrand in free configuration space is sampled. Then, the xrand chooses the nearest vertex in the tree. Along the edge E (xnearest, xrand) by local steering curve with a step size, a potential new node xnew is generated. Now a collision check is performed to examine whether the xnew is obstructed. If not, the newly generated edge E (xnearest, xnew) is added to the tree. Next, the rewiring procedure works as an optimization process, by connecting from xnew to each potential parent nodes set Xnear within a radius r. Comparing different routes from start position qstart to xnew, the path with minimum time cost is selected as the newly added edge. Finally, the iteration stops when a new node has reached the goal region qgoal. The details and modifications of the algorithm are described below.Algorithm 1: Kinodynamic safety RRT∗.
Input: occupancy cost map, start and goal configurationOutput: time-optimal path connecting qstart and qgoal(1)
Vertex←{xinitial}; Edge←∅;(2)
fori = 1 to ndo(3)
xrand←Goalbias_Samplingi;(4)
xnearest←Nearest_Connect (G = (V, E), xrand);(5)
xnew←Kinodynamic_Steering (xnearest,xnew);(6)
if Collision_free (xnew,xnearest) then(7)
Tree.add_vertex (xnew)(8)
Tree.add_edge (xnew,xnearest)(9)
xnear←Nearest_Neighbors (Tree, xnew, ri)(10)
for all (xnear, Xnear) do(11)
Time-based_Rewiring (xnear,xnew)(12)
returnG = (V, E);


#### 2.3.1. Goal Bias Sampling

Sampling is the first step in exploring the workspace of the tree structure. The sampling-based algorithm originally adopts uniform sampling scheme that evenly extends towards outside. However, uniform sampling scheme may result in lower sampling chances in narrow regions of cluttered environment. Thus, we adopt a goal biasing scheme to explore the state space. A probabilistic thresholdPgoal∈ (0, 1) is set, and each time before sampling, a random number Prand∈ (0, 1) is generated. If Prand < Pgoal, the goal region is set to be the next sample point; else if Prand ≥ Pgoal, a random sampling is made in the free space. Such sampling scheme has been proved to have better performance than the dense distribution [26].


#### 2.3.2. Kinodynamic Local Steering

In the original algorithm, the subsequent way points are connected by straight lines, which may bring trouble for nonholonomic vehicles performing stationary turns due to the vehicle’s turning radius constraints. Since the tractor-aircraft system can move both forwards and backwards, Reeds-Shepp curves [8] is chosen as the local connection between two sampling poses, as it has been proven to be kinodynamically feasible withholding the small-time local controllability property to reach any place in the map. However, it would generate 46 types of curves for each connection, resulting in a high cost to test every possible connection at each iteration Step [5]. Thus, we put a limit on the curvature of steering (as shown in Figure 4), where the initial and final curvature of the steering is set as zero. Such method can eliminate many connection possibilities meanwhile guaranteeing the continuous smoothness of successive curve connection. This becomes beneficial especially considering real-time implementation, as the computational complexity is significantly reduced.Figure 4
An illustration of a zero-angled curve path for one of a Reeds-Shepp family curves. Here,qI is the initial pose and qG is the final pose.


#### 2.3.3. Expansion-Based Fast Collision Checking

Collision checking is usually considered as the bottleneck of sampling-based planners [27]. Here we use the expansion-based fast collision checking method [28]. In such context, the vehicle is usually approximated as a circumscribed circle, while the obstacles are expanded by a buffer, checking whether the circle lies on the expanded grid. However, such approximation leaves too much redundancy for path planning in cluttered environment; thus, an approximation algorithm [29] is implemented by covering the tractor-aircraft with multiple overlapping circles. Then the collision checking is simply performed by checking if these circles lie in the expanded grid. As shown in Figure 5, the shape of the aircraft towing system is approximate by 6 equal overlapping solid circles, and the obstacles (dark blue) are expanded (light blue) by a safety clearance δ.Figure 5
Collision checking model. The obstacle is shown in dark blue and the expanded contour is shown in light blue. The shape of the tractor-aircraft system is approximated as a circumscribed circle (dotted circle) and multiple overlapping circles (solid circles).


#### 2.3.4. Time-Based Rewiring

Before the rewiring procedure begins, the algorithm searchesXnear, which is a vertices set within a ball of radius from xrand, to find its potential time-optimal parent node. Once the path from xinitial to xrand with the least time cost is assured, xrand is added to the tree. If the steering from xrand has lower cost than current path, then its parent xnear is substituted by xrand. Algorithm 2 shows the pseudocode of rewiring procedure.Algorithm 2: Time-based rewiring procedure.
(1)
for each xnear ∈Xneardo(2)
xnew←Kinodynamic_Steering (xrand,xnear);(3)
ifTime_Cost (xrand) + Time_Cost (xnew) < Cost (xnear) then(4)
xparent←Parent (xnear);(5)
E←(E\{(xparent, xnear)}) ∪ {(xrand, xnear)};(6)
returnG = (V, E);The path traversing time in the tree is calculated as follows.Figure6 shows one of the path segments in the tree-structured map, where s is the arc length connecting the two nodes and v is the maximum allowable speed with respect of the speed map.Figure 6
An illustration of thekth segment connecting configuration qk and qk+1. s is the arc length and v is the velocity.Thekth arc length is sk, with initial and final velocity of vk and vk+1. Assuming the movement from configuration qk to configuration qk+1 is uniform acceleration (or deceleration) process, the traverse time along the path can be calculated based on the following equation:(2)sk=∫kk+1vdt⇒t=2skvk+vk+1,⇒t=2skvk+vk+1and the time-based cost function Ctime from initial node to the k node is calculated by(3)Ctime=∑0k−1tk.The benefit of the proposed algorithm is shown in the following example (Figure7). The proposed algorithm generates a σ′ path (solid line) while the standard RRT∗ generates a σpath (dashed line). Comparing the paths generated by the two planners, it can be noted that σ′ path (solid line) is longer but safer as the aircraft does not enter the expanded contour δ region. Following σ′ path with maximum allowable speed can reach the goal spot faster than that of σ path with much slower speed across the safety buffer contour.Figure 7
An illustration of the advantage of inducing velocity constraint in the algorithm. Our proposed algorithm generates aσ′ path (solid line), while standard RRT∗ generates a σpath (dashed line).


## 2.1. Speed Combined Cost Map

The autonomous tractor is expected to steer the aircraft to an available parking spot. Figure2(a) shows the operating environment as a 2D occupancy grid, including available and occupied parking spots, deck markings, and obstacles such as other aircraft (black polygons). This paper assumes such map is fully known by a flight deck monitor system [24].Figure 2
A notional aircraft carrier flight deck layout (a) and its corresponding speed map (b). Blue colour represents the velocity in the obstacle area; green colour represents the safety velocity in the buffer contour around the obstacle area; warm toned colour (yellow to orange) represents the maximum velocity in the sparseness area.
(a)(b)For considering the safety velocity restrictions and maintaining safe clearance for the tractor-aircraft maneuvering in close-quarters, a speed map is generated for assigning different maximum allowable velocity in the environment (Figure2(b)). According to the naval operations standards [2], we confine different velocities in the obstacle areas (vobs), the safety velocity (vsafe) in the buffer contour d around the obstacle (making sure the towed aircraft can be slowed to an immediate stop), and the maximum velocity (vmax) in the sparseness areas that there are no obstacles in the vicinity.


## 2.2. Tractor-Aircraft Kinematics

Figure3 shows a non-rod tractor that directly attaches to the front wheel of an aircraft, creating a tractor-aircraft articulated system. The kinematics functions of such two-body system [25] can be written as follows:(1)x˙a=vcosθa,y˙a=vsinθa,θ˙a=vlatanφ,x˙b=vcosθbcosθa−θb,y˙b=vsinθbcosθa−θb,θ˙b=vlbsinθa−θb,where (xa, ya) is the tractor’s mass position that lies in the middle of its rear wheel axle and θa is the orientation of the tractor; v denotes the linear velocity of the tractor; x˙a and y˙a are the horizontal and vertical linear velocity, respectively; and θ˙a is the angular velocity of the tractor. Similarly, the aircraft’s state is presented as (xb, yb, θb). And la and lb are the wheelbases of the tractor and aircraft; f is the tractor’s steering angle, and it cannot exceed its maximum rotation angle |φmax|, which leads to a minimum turning radius rmin. Notice that the moving speed is limited by safety velocity vmax, and the inertial effect that brings the slipping of wheels can be ignored.Figure 3
Two-body tractor-aircraft towing system. The motion of the tractor-aircraft towing system is described by equation (1).


## 2.3. KS-RRT∗ Algorithm

In order to improve the safety and effectiveness, we propose a velocity-restricted KS-RRT∗ algorithm to plan a near time-optimal path in the semistructured cluttered environment.The primitives of KS-RRT∗ algorithm include goal bias sampling, kinodynamic local steering, expansion-based fast collision checking, and time-based rewiring procedures. Algorithm 1 outlines the KS-RRT∗ algorithm. At first, a single vertex is initialized in the tree graph as G (V, E). For each iteration of generating random sample nodes, a node xrand in free configuration space is sampled. Then, the xrand chooses the nearest vertex in the tree. Along the edge E (xnearest, xrand) by local steering curve with a step size, a potential new node xnew is generated. Now a collision check is performed to examine whether the xnew is obstructed. If not, the newly generated edge E (xnearest, xnew) is added to the tree. Next, the rewiring procedure works as an optimization process, by connecting from xnew to each potential parent nodes set Xnear within a radius r. Comparing different routes from start position qstart to xnew, the path with minimum time cost is selected as the newly added edge. Finally, the iteration stops when a new node has reached the goal region qgoal. The details and modifications of the algorithm are described below.Algorithm 1: Kinodynamic safety RRT∗.
Input: occupancy cost map, start and goal configurationOutput: time-optimal path connecting qstart and qgoal(1)
Vertex←{xinitial}; Edge←∅;(2)
fori = 1 to ndo(3)
xrand←Goalbias_Samplingi;(4)
xnearest←Nearest_Connect (G = (V, E), xrand);(5)
xnew←Kinodynamic_Steering (xnearest,xnew);(6)
if Collision_free (xnew,xnearest) then(7)
Tree.add_vertex (xnew)(8)
Tree.add_edge (xnew,xnearest)(9)
xnear←Nearest_Neighbors (Tree, xnew, ri)(10)
for all (xnear, Xnear) do(11)
Time-based_Rewiring (xnear,xnew)(12)
returnG = (V, E);


### 2.3.1. Goal Bias Sampling

Sampling is the first step in exploring the workspace of the tree structure. The sampling-based algorithm originally adopts uniform sampling scheme that evenly extends towards outside. However, uniform sampling scheme may result in lower sampling chances in narrow regions of cluttered environment. Thus, we adopt a goal biasing scheme to explore the state space. A probabilistic thresholdPgoal∈ (0, 1) is set, and each time before sampling, a random number Prand∈ (0, 1) is generated. If Prand < Pgoal, the goal region is set to be the next sample point; else if Prand ≥ Pgoal, a random sampling is made in the free space. Such sampling scheme has been proved to have better performance than the dense distribution [26].


### 2.3.2. Kinodynamic Local Steering

In the original algorithm, the subsequent way points are connected by straight lines, which may bring trouble for nonholonomic vehicles performing stationary turns due to the vehicle’s turning radius constraints. Since the tractor-aircraft system can move both forwards and backwards, Reeds-Shepp curves [8] is chosen as the local connection between two sampling poses, as it has been proven to be kinodynamically feasible withholding the small-time local controllability property to reach any place in the map. However, it would generate 46 types of curves for each connection, resulting in a high cost to test every possible connection at each iteration Step [5]. Thus, we put a limit on the curvature of steering (as shown in Figure 4), where the initial and final curvature of the steering is set as zero. Such method can eliminate many connection possibilities meanwhile guaranteeing the continuous smoothness of successive curve connection. This becomes beneficial especially considering real-time implementation, as the computational complexity is significantly reduced.Figure 4
An illustration of a zero-angled curve path for one of a Reeds-Shepp family curves. Here,qI is the initial pose and qG is the final pose.


### 2.3.3. Expansion-Based Fast Collision Checking

Collision checking is usually considered as the bottleneck of sampling-based planners [27]. Here we use the expansion-based fast collision checking method [28]. In such context, the vehicle is usually approximated as a circumscribed circle, while the obstacles are expanded by a buffer, checking whether the circle lies on the expanded grid. However, such approximation leaves too much redundancy for path planning in cluttered environment; thus, an approximation algorithm [29] is implemented by covering the tractor-aircraft with multiple overlapping circles. Then the collision checking is simply performed by checking if these circles lie in the expanded grid. As shown in Figure 5, the shape of the aircraft towing system is approximate by 6 equal overlapping solid circles, and the obstacles (dark blue) are expanded (light blue) by a safety clearance δ.Figure 5
Collision checking model. The obstacle is shown in dark blue and the expanded contour is shown in light blue. The shape of the tractor-aircraft system is approximated as a circumscribed circle (dotted circle) and multiple overlapping circles (solid circles).


### 2.3.4. Time-Based Rewiring

Before the rewiring procedure begins, the algorithm searchesXnear, which is a vertices set within a ball of radius from xrand, to find its potential time-optimal parent node. Once the path from xinitial to xrand with the least time cost is assured, xrand is added to the tree. If the steering from xrand has lower cost than current path, then its parent xnear is substituted by xrand. Algorithm 2 shows the pseudocode of rewiring procedure.Algorithm 2: Time-based rewiring procedure.
(1)
for each xnear ∈Xneardo(2)
xnew←Kinodynamic_Steering (xrand,xnear);(3)
ifTime_Cost (xrand) + Time_Cost (xnew) < Cost (xnear) then(4)
xparent←Parent (xnear);(5)
E←(E\{(xparent, xnear)}) ∪ {(xrand, xnear)};(6)
returnG = (V, E);The path traversing time in the tree is calculated as follows.Figure6 shows one of the path segments in the tree-structured map, where s is the arc length connecting the two nodes and v is the maximum allowable speed with respect of the speed map.Figure 6
An illustration of thekth segment connecting configuration qk and qk+1. s is the arc length and v is the velocity.Thekth arc length is sk, with initial and final velocity of vk and vk+1. Assuming the movement from configuration qk to configuration qk+1 is uniform acceleration (or deceleration) process, the traverse time along the path can be calculated based on the following equation:(2)sk=∫kk+1vdt⇒t=2skvk+vk+1,⇒t=2skvk+vk+1and the time-based cost function Ctime from initial node to the k node is calculated by(3)Ctime=∑0k−1tk.The benefit of the proposed algorithm is shown in the following example (Figure7). The proposed algorithm generates a σ′ path (solid line) while the standard RRT∗ generates a σpath (dashed line). Comparing the paths generated by the two planners, it can be noted that σ′ path (solid line) is longer but safer as the aircraft does not enter the expanded contour δ region. Following σ′ path with maximum allowable speed can reach the goal spot faster than that of σ path with much slower speed across the safety buffer contour.Figure 7
An illustration of the advantage of inducing velocity constraint in the algorithm. Our proposed algorithm generates aσ′ path (solid line), while standard RRT∗ generates a σpath (dashed line).


## 2.3.1. Goal Bias Sampling

Sampling is the first step in exploring the workspace of the tree structure. The sampling-based algorithm originally adopts uniform sampling scheme that evenly extends towards outside. However, uniform sampling scheme may result in lower sampling chances in narrow regions of cluttered environment. Thus, we adopt a goal biasing scheme to explore the state space. A probabilistic thresholdPgoal∈ (0, 1) is set, and each time before sampling, a random number Prand∈ (0, 1) is generated. If Prand < Pgoal, the goal region is set to be the next sample point; else if Prand ≥ Pgoal, a random sampling is made in the free space. Such sampling scheme has been proved to have better performance than the dense distribution [26].


## 2.3.2. Kinodynamic Local Steering

In the original algorithm, the subsequent way points are connected by straight lines, which may bring trouble for nonholonomic vehicles performing stationary turns due to the vehicle’s turning radius constraints. Since the tractor-aircraft system can move both forwards and backwards, Reeds-Shepp curves [8] is chosen as the local connection between two sampling poses, as it has been proven to be kinodynamically feasible withholding the small-time local controllability property to reach any place in the map. However, it would generate 46 types of curves for each connection, resulting in a high cost to test every possible connection at each iteration Step [5]. Thus, we put a limit on the curvature of steering (as shown in Figure 4), where the initial and final curvature of the steering is set as zero. Such method can eliminate many connection possibilities meanwhile guaranteeing the continuous smoothness of successive curve connection. This becomes beneficial especially considering real-time implementation, as the computational complexity is significantly reduced.Figure 4
An illustration of a zero-angled curve path for one of a Reeds-Shepp family curves. Here,qI is the initial pose and qG is the final pose.


## 2.3.3. Expansion-Based Fast Collision Checking

Collision checking is usually considered as the bottleneck of sampling-based planners [27]. Here we use the expansion-based fast collision checking method [28]. In such context, the vehicle is usually approximated as a circumscribed circle, while the obstacles are expanded by a buffer, checking whether the circle lies on the expanded grid. However, such approximation leaves too much redundancy for path planning in cluttered environment; thus, an approximation algorithm [29] is implemented by covering the tractor-aircraft with multiple overlapping circles. Then the collision checking is simply performed by checking if these circles lie in the expanded grid. As shown in Figure 5, the shape of the aircraft towing system is approximate by 6 equal overlapping solid circles, and the obstacles (dark blue) are expanded (light blue) by a safety clearance δ.Figure 5
Collision checking model. The obstacle is shown in dark blue and the expanded contour is shown in light blue. The shape of the tractor-aircraft system is approximated as a circumscribed circle (dotted circle) and multiple overlapping circles (solid circles).


## 2.3.4. Time-Based Rewiring

Before the rewiring procedure begins, the algorithm searchesXnear, which is a vertices set within a ball of radius from xrand, to find its potential time-optimal parent node. Once the path from xinitial to xrand with the least time cost is assured, xrand is added to the tree. If the steering from xrand has lower cost than current path, then its parent xnear is substituted by xrand. Algorithm 2 shows the pseudocode of rewiring procedure.Algorithm 2: Time-based rewiring procedure.
(1)
for each xnear ∈Xneardo(2)
xnew←Kinodynamic_Steering (xrand,xnear);(3)
ifTime_Cost (xrand) + Time_Cost (xnew) < Cost (xnear) then(4)
xparent←Parent (xnear);(5)
E←(E\{(xparent, xnear)}) ∪ {(xrand, xnear)};(6)
returnG = (V, E);The path traversing time in the tree is calculated as follows.Figure6 shows one of the path segments in the tree-structured map, where s is the arc length connecting the two nodes and v is the maximum allowable speed with respect of the speed map.Figure 6
An illustration of thekth segment connecting configuration qk and qk+1. s is the arc length and v is the velocity.Thekth arc length is sk, with initial and final velocity of vk and vk+1. Assuming the movement from configuration qk to configuration qk+1 is uniform acceleration (or deceleration) process, the traverse time along the path can be calculated based on the following equation:(2)sk=∫kk+1vdt⇒t=2skvk+vk+1,⇒t=2skvk+vk+1and the time-based cost function Ctime from initial node to the k node is calculated by(3)Ctime=∑0k−1tk.The benefit of the proposed algorithm is shown in the following example (Figure7). The proposed algorithm generates a σ′ path (solid line) while the standard RRT∗ generates a σpath (dashed line). Comparing the paths generated by the two planners, it can be noted that σ′ path (solid line) is longer but safer as the aircraft does not enter the expanded contour δ region. Following σ′ path with maximum allowable speed can reach the goal spot faster than that of σ path with much slower speed across the safety buffer contour.Figure 7
An illustration of the advantage of inducing velocity constraint in the algorithm. Our proposed algorithm generates aσ′ path (solid line), while standard RRT∗ generates a σpath (dashed line).


## 3. Simulation and Results

In order to assess the effectiveness of KS-RRT∗, the simulation experiments are analyzed through several scenarios representing common parking patterns aboard (as shown in Figure 8).Figure 8
Path planning in three autonomous parking scenarios, where each scenario highlights a challenging parking situation within the cyclic flight operations afloat in congested environment. (a) Postflight parking. (b) Hangar deck parking. (c) Preflight parking.
(a)(b)(c)The tractor-aircraft parameters are listed in Table1, which are defined referencing to the naval operations standardization [1].Table 1
Tractor-aircraft parameters.
ParameterValueMinimum turning radius (r)12 mLength (l)15.3 mWheel base (L)8 mWidth (w)6 mMaximum velocity (v)1.5 m/sMaximum acceleration (a)2 m/s2Maximum steering angle (φmax)π/4A 300 m × 80 m occupancy grid with a resolution of 0.5 m is used to represent the flight deck environment. Table2 lists the parameters of the cost map and the reference speed map, referenced to the naval operations standardization [1].Table 2
The map parameters.
ParameterValueMap size300 m × 80 mCell resolution0.5 mGoal tolerance0.5 mHard obstacle margin0.2 mSafety bufferδ1.5 mvfree/vsafe/vobs1.5/0.2/0 m/sSince the efficiency of sampling-based algorithm is heavily influenced by its resolution parameters, different parameter settings are first tested to find the suitable values that result in less computation time and better trajectory qualities. Then several parking scenarios are analyzed by comparing with standard RRT∗ and human driving heuristic. The simulation platform is a virtual carrier deck operations simulator we previously developed [30], as shown in Figure 9, whose input device is Logitech driving suite that can control tractor towing aircraft in the virtual environment. All the simulations are performed on a ThinkPad T450 computer (2.60 GHz Intel i7-5600 U core CPU, 4 GB RAM, Microsoft Windows 10 64 bit operating system).Figure 9
The carrier deck operation simulator environment. (a) The Logitech driving input device. (b) The simulated 3D tractor towing aircraft. (c) The tractor-aircraft movement and path generated (green line).
(a)(b)(c)


### 3.1. KS-RRT∗ Parameters

Since sampling-based planners are sensitive to their embedded parameters, many parameters in the algorithm can be customized to improve their performances. Figure10 shows the distribution results. We give 30 independent runs for each testing to eliminate the randomized causes of sampling-based technique.Figure 10
Simulation results of parameter comparison in different scenarios. (a) Convergence test. (b) Step size test. (c) Goal bias test. The solid lines represent the cost of trajectory time (left vertical axis) and the dashed lines represent the computation time (right vertical axis).
(a)(b)(c)KS-RRT∗ is an asymptotically optimal algorithm; thus; the convergence property of the algorithm is first investigated. For each scenario, the planner was run from 1000 to 20,000 iterations, and the results were averaged for analysis. Figure 10(a) shows as expected that in all three scenarios, the trajectory time will converge to optimal value as the iteration increases, but with increased computation time. By pairwise comparison of iterations 5000 and 20000, the computation time expenses increase more than five times with less than 1% improvements in trajectory cost. Hence a run for the planner of 5000 iterations is compromised to result in a near optimal solution with least computation cost.Then we test different step size values that influence the quality of generated trajectory (Figure10(b)). The planner starts with a step size of 1 m. The average computation time reduces as the step size enlarges. This is because larger steps are capable of covering more free configuration space. However, the path quality will be lowered as the step size increases. A step size of 5 meters is suitable as it compensates the solution quality with exploration speed.Goal biasing ratio takes the similar analysis. It can be seen from Figure10(c), for scenario 1 and 3, increasing the goal biasing ratio accelerates reaching the goal, but for scenario 2 it takes much more computation time. This is because scenario 2 creates a high density of narrow passage; thus, the larger goal biasing ratio will behave like greedy algorithm that falls into circumnavigate obstacles. Increasing biasing ratio from 10% to 90% provides hardly no improvements in trajectory time. Hence, bias ratio of 10% is considered as a better biasing scheme.


### 3.2. Numerical Experiments

For comparing the performance of the KS-RRT∗ with both standard RRT∗ and human driving heuristic, the algorithm is implemented in the virtual deck operations simulator [30] as noted above. A human expert steers the tractor in the simulation to reach goal spot quickly meanwhile maintain the same safety protocols as human driving heuristic. Once successfully parked the aircraft to the designate spot, the total driving time from start will be recorded as the trajectory time. Driving the same scenario for 30 times will get the average trajectory time.First, the planner is executed for 5000 iterations with a step size of 5 meters and 10% goal biasing ratio, which is the optimal parameters of previous section. Every setting runs for 30 times. The results are compared with the standard RRT∗ and human driving heuristic in all three scenarios.Scene 1 is considered as easy case of sparseness environment. Aircraft starts at the bow area and is towed aft to the fantail. The average trajectory time is 156 seconds. Figure11 shows one of the 30 running results. As shown in Table 3, all the three algorithms get similar results, this is because the aircraft can be towed at its maximum speed towards goal spot without obstacles.Figure 11
One sample result of aircraft-tractor foot print with respect to the planned route in Scenario 1. Start and goal spots are shown as blue and yellow colour, respectively.Table 3
Simulation statistical results of Scenario 1.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1002.6156RRT∗1004.2165Human driving100—160Since narrow passages can cause difficulty for sampling-based path planners, Scenario 2 aims to test the algorithm in a much more congested environment of hangar deck spotting. As shown in Figure12, the start position is at the left top and the goal position is in the right bottom. One resulting path is given in Figure 12. The aircraft first moves slowly through the narrow passage, until it nears the final spot, and it gets back into an interim spot and then finally moves forward into the goal spot. As shown in Table 4, the human driving takes longer time due to maneuvering in close-quarters with less sensing accuracy.Figure 12
One sample result of Scenario 2. Start and goal spots are shown as blue and yellow colour, respectively.Table 4
Simulation statistical results of Scenario 2.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1002.3213RRT∗847231Human driving95-255Scene 3 represents the prelaunch status with many aircraft waiting to take off on the flight deck, where an aircraft tries to get to a launch spot of catapult 1 through congested street area. Figure13 shows the result of two different homotopy types of trajectories. The KS-RRT∗ finds the safety time-optimal trajectory that bypasses the six-pack congested area (Figure 13(a)). In contrast, the standard RRT∗ prefers the shortest distance passing through the six-pack area (Figure 13(b)), without considering safety speed limits. Statistical results (Table 5) show that such a path generated by the standard RRT∗ would require unacceptably slow speeds to be safe, consuming more time than that generated by the KS-RRT∗.Figure 13
One simulation result of Scenario 3. (a) A near time-optimal trajectory generated by the KS-RRT. (b) A solution found by the standard RRT. Start and goal spots are shown as blue and yellow colour, respectively.
(a)(b)Table 5
Simulation statistical results of Scenario 3.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1001.5122RRT∗972.2166.7Human driving100-145Throughout the experiments, the KS-RRT∗ shows its ability of generating a robust safety time-optimal trajectory, despite the complexity of the environment. Compared to the standard RRT∗, the KS-RRT∗ has faster computation and trajectory time and a higher success rate in a congested environment without the need for further speed profile generation. Besides, it also outperforms the human driving heuristic in terms of safety trajectory time with a dramatic reduction in total manpower. Hence, the KS-RRT∗ is more suitable for automated aircraft towing in the carrier deck environment.


## 3.1. KS-RRT∗ Parameters

Since sampling-based planners are sensitive to their embedded parameters, many parameters in the algorithm can be customized to improve their performances. Figure10 shows the distribution results. We give 30 independent runs for each testing to eliminate the randomized causes of sampling-based technique.Figure 10
Simulation results of parameter comparison in different scenarios. (a) Convergence test. (b) Step size test. (c) Goal bias test. The solid lines represent the cost of trajectory time (left vertical axis) and the dashed lines represent the computation time (right vertical axis).
(a)(b)(c)KS-RRT∗ is an asymptotically optimal algorithm; thus; the convergence property of the algorithm is first investigated. For each scenario, the planner was run from 1000 to 20,000 iterations, and the results were averaged for analysis. Figure 10(a) shows as expected that in all three scenarios, the trajectory time will converge to optimal value as the iteration increases, but with increased computation time. By pairwise comparison of iterations 5000 and 20000, the computation time expenses increase more than five times with less than 1% improvements in trajectory cost. Hence a run for the planner of 5000 iterations is compromised to result in a near optimal solution with least computation cost.Then we test different step size values that influence the quality of generated trajectory (Figure10(b)). The planner starts with a step size of 1 m. The average computation time reduces as the step size enlarges. This is because larger steps are capable of covering more free configuration space. However, the path quality will be lowered as the step size increases. A step size of 5 meters is suitable as it compensates the solution quality with exploration speed.Goal biasing ratio takes the similar analysis. It can be seen from Figure10(c), for scenario 1 and 3, increasing the goal biasing ratio accelerates reaching the goal, but for scenario 2 it takes much more computation time. This is because scenario 2 creates a high density of narrow passage; thus, the larger goal biasing ratio will behave like greedy algorithm that falls into circumnavigate obstacles. Increasing biasing ratio from 10% to 90% provides hardly no improvements in trajectory time. Hence, bias ratio of 10% is considered as a better biasing scheme.


## 3.2. Numerical Experiments

For comparing the performance of the KS-RRT∗ with both standard RRT∗ and human driving heuristic, the algorithm is implemented in the virtual deck operations simulator [30] as noted above. A human expert steers the tractor in the simulation to reach goal spot quickly meanwhile maintain the same safety protocols as human driving heuristic. Once successfully parked the aircraft to the designate spot, the total driving time from start will be recorded as the trajectory time. Driving the same scenario for 30 times will get the average trajectory time.First, the planner is executed for 5000 iterations with a step size of 5 meters and 10% goal biasing ratio, which is the optimal parameters of previous section. Every setting runs for 30 times. The results are compared with the standard RRT∗ and human driving heuristic in all three scenarios.Scene 1 is considered as easy case of sparseness environment. Aircraft starts at the bow area and is towed aft to the fantail. The average trajectory time is 156 seconds. Figure11 shows one of the 30 running results. As shown in Table 3, all the three algorithms get similar results, this is because the aircraft can be towed at its maximum speed towards goal spot without obstacles.Figure 11
One sample result of aircraft-tractor foot print with respect to the planned route in Scenario 1. Start and goal spots are shown as blue and yellow colour, respectively.Table 3
Simulation statistical results of Scenario 1.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1002.6156RRT∗1004.2165Human driving100—160Since narrow passages can cause difficulty for sampling-based path planners, Scenario 2 aims to test the algorithm in a much more congested environment of hangar deck spotting. As shown in Figure12, the start position is at the left top and the goal position is in the right bottom. One resulting path is given in Figure 12. The aircraft first moves slowly through the narrow passage, until it nears the final spot, and it gets back into an interim spot and then finally moves forward into the goal spot. As shown in Table 4, the human driving takes longer time due to maneuvering in close-quarters with less sensing accuracy.Figure 12
One sample result of Scenario 2. Start and goal spots are shown as blue and yellow colour, respectively.Table 4
Simulation statistical results of Scenario 2.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1002.3213RRT∗847231Human driving95-255Scene 3 represents the prelaunch status with many aircraft waiting to take off on the flight deck, where an aircraft tries to get to a launch spot of catapult 1 through congested street area. Figure13 shows the result of two different homotopy types of trajectories. The KS-RRT∗ finds the safety time-optimal trajectory that bypasses the six-pack congested area (Figure 13(a)). In contrast, the standard RRT∗ prefers the shortest distance passing through the six-pack area (Figure 13(b)), without considering safety speed limits. Statistical results (Table 5) show that such a path generated by the standard RRT∗ would require unacceptably slow speeds to be safe, consuming more time than that generated by the KS-RRT∗.Figure 13
One simulation result of Scenario 3. (a) A near time-optimal trajectory generated by the KS-RRT. (b) A solution found by the standard RRT. Start and goal spots are shown as blue and yellow colour, respectively.
(a)(b)Table 5
Simulation statistical results of Scenario 3.
SimulationSuccess rate (%)Average computation time (s)Average trajectory time (s)KS-RRT∗1001.5122RRT∗972.2166.7Human driving100-145Throughout the experiments, the KS-RRT∗ shows its ability of generating a robust safety time-optimal trajectory, despite the complexity of the environment. Compared to the standard RRT∗, the KS-RRT∗ has faster computation and trajectory time and a higher success rate in a congested environment without the need for further speed profile generation. Besides, it also outperforms the human driving heuristic in terms of safety trajectory time with a dramatic reduction in total manpower. Hence, the KS-RRT∗ is more suitable for automated aircraft towing in the carrier deck environment.


## 4. Conclusions

In this paper, a modified version of RRT∗ algorithm was proposed to quickly generate a near time-optimal safe path for tractor-aircraft parking in cluttered onboard environments. The proposed method integrates a safety speed map in the configuration space, which allows for rewiring the tree structure in the algorithm by calculating minimum travelling time cost. The proposed KS-RRT∗ path planner is validated through numerical experiments. The experimental results also show that the KS-RRT∗ algorithm performs better than the standard RRT∗ and human driving heuristic. However, the spotting operations aboard might be operated concurrently in the real-world situations, which will be multirobot motion planning problem that leads to new problems such as interference of different moving body, towing sequence, arising more serious safety issues. In the near future, our planner can be fit from single query to more complicated scenarios, such as the multirobot collaboration problem that makes them cooperate to optimize the overall traffic.



---

*Source: 3872248-2021-09-23.xml*