HEURISTIC NEAR OPTIMAL UAS PATH PLANNING ALGORITHM FOR CONVOY OVERWATCH
The optimal path to fly a small unmanned aerial system (SUAS) for convoy overwatch was calculated, heuristically approximated onboard a SUAS autopilot, and demonstrated with hardware in the loop simulations and flight test. The optimal path minimized a cost functional consisting of the SUAS's control effort and deviation from a desired slant range. Due to several hardware and software limitations, the SUAS autopilot was incapable of implementing the optimal controller onboard. This paper introduces a novel heuristic based algorithm developed in three steps and implemented onboard the autopilot to approximate the optimal solution. The first step manipulated the autopilot loiter logic to allow target tracking. The second step identified three parameters in the loiter logic that were tuned using a Design of Experiments (DOE) methodology. Lastly, a finite state machine (FSM) was created based on the DOE results to further optimize the real world convoy overwatch algorithm. Each step was tested to evaluate how well it approximated the optimal path. The final algorithm using the FSM exhibited a 65% improvement in tracking performance and demonstrated an implementable, near optimal convoy overwatch algorithm. UNMANNED AERIAL SYSTEMS JOURNAL OF www.uasjournal.org 39 Volume 2, Issue 1 Heuristic Near Optimal UAS Path Planning Algorithm for Convoy Overwatch Nomenclature a Cost functional weight factor f, q, y Roll, Pitch, and Yaw angles, deg f Roll rate, deg/s y w Wind direction, deg f Update frequency, Hz g Gravitational acceleration, m/s2 h SUAS altitude (AGL) m J Cost function value Jth Cost function threshold SR Slant range, m SRD Slant range desired, m t0 Initial time, sec tf Final time, sec tlook Look ahead time, sec V SUAS airspeed, m/s VG SUAS ground speed, m/s Vw Wind speed, m/s XGV, YGV Ground vehicle components in inertial frame XSUAS, YSUAS SUAS components in the North, East, Down (NED) inertial frame Introduction Unmanned aerial systems (UASs) constitute a rapidly developing platform of American military air power. Since 2002, the number of operational UAS has increased over 40 fold and now UAS comprise an astounding 41% of the military's aircraft inventory (Gertler, 2012) Currently, both manned and unmanned platforms are used to provide real time, video surveillance of friendly vehicle convoys in wartime environments. The Air Force Research Lab's (AFRL) goal is to demonstrate autonomous convoy overwatch using small unmanned aerial systems (SUASs) that can stream continuous, full motion video to the convoy commander without any direct input from the ground station operator. Using autonomous SUAS platforms for convoy surveillance allows for improved allocation of personnel and resources, saving the Air Force time, money, and lives. In addition, the technology has applications to search and rescue operations, armored car overwatch, wildlife tracking and monitoring, and border patrol applications. Accomplishing the feat of autonomous target tracking with a SUAS is not without its challenges. The specific surveillance requirements for successfully performing convoy overwatch, coupled with the limited processing power of the onboard autopilot and power supply of the SUAS provide the greatest obstacles. To best achieve autonomous target tracking, first the optimal flight path for the SUAS must be determined. The subsequent challenge is to fly the optimal path onboard a real SUAS. If the optimal path cannot be determined and flown in real time, then a heuristicbased approximation of the optimal path should be demonstrated and compared. A variety of research has been done using optimal control to develop flight paths for unmanned tasks. Smith, Cobb, Pierce, and Raska (2013) used optimal control to generate paths for UAS collision avoidance. Kim, Oh, and Tsourdos (2013) used optimal control to develop a nonlinear model predictive coordinated standoff tracking of a moving target. Their optimal path formulation was compared with the Lyapunov vector field approach presented by Frew, Lawrence, and Morris (2008) The optimal solutions more accurately maintained the desired standoff distance from the target and kept the desired separation between the SUASs. Geiger et al. (2008) incorporated optimal control for a SUAS to track a moving ground vehicle. Their research used a fixed orientation camera and their cost functional maximize the SUAS time on target for simplified ground vehicle paths. Jodeh, Coon, Masternak, Cobb, and Agte (2014) used optimal control to plan a path for maximizing the ground coverage of unattended ground sensors. Prevost, Theiault, Desbiens, Poulini, and Gagnon (2009) developed an extended Kalman filter to predict the future path of a moving target and generated an optimal path based on that information. All of these optimal path UNMANNED AERIAL SYSTEMS JOURNAL OF www.uasjournal.org 40 Volume 2, Issue 1 formulations required a cost functional, optimizer, and future knowledge of some kind. The processing time required to determine the optimal solutions often exceeds the mission time, therefore disqualifying them from real time applications. There have been numerous research efforts accomplished that use unmanned platforms to track moving targets that are applicable in a real world environment. Rysdyk (2006) developed a path planning algorithm used for target observation in the presence of wind. His guidance law was developed using "good helmsman" techniques, which output a relative course heading as a function of cross track error. Yoon, Park, and Kim (2012) developed a guidance law that used multiple SUAS to perform coordinated standoff tracking. Similarly, work done by Frew et al. (2008) and Lawrence, Frew, and Pisano (2008) performed target tracking by creating globally stable, Lyapunov vector fields that allowed a SUAS to autonomously and efficiently track a moving target. Quigley, Goodrich, Griffiths, Eldridge, and Beard (2005) improved the Lyapunov vector field approach through introducing a Hopf bifurcation method. This specific type of limit cycle has a faster convergence rate to the circular orbit than the Lyapunov approach and was implementable real time onboard the SUAS. Each one of these methods represent a sub optimal, target tracking algorithm that were efficient enough to execute real time onboard the SUAS autopilot. The two objectives of this research were: develop an optimal path planning algorithm and demonstrate a real world execution of it for autonomous convoy overwatch. An optimal flight path algorithm is presented that calculates the necessary SUAS control inputs for any given ground vehicle path. More specifically, the algorithm determined the minimum control inputs required for a SUAS to maintain a desired slant range from the ground vehicle. This algorithm used future knowledge of the exact ground vehicle location to calculate the optimal path. The path planning capability was demonstrated through computer simulations using time stamped, GPS locations of a ground vehicle driving along a path. Secondly, the optimal path algorithm was approximated onboard the SUAS, demonstrating a real world, near optimal tracking capability. The finalized heuristic method did not rely on future knowledge of the ground vehicle information, instead it was able to adjust and track based on current ground vehicle information. The heuristic approximation was developed using a three step process built upon the preexisting loiter logic of the SUAS autopilot. Optimal Path Formulation The first objective was determining the optimal SUAS flight path to perform convoy overwatch for a given ground vehicle profile. In the optimal path formulation, the ground vehicle profile information was known prior to solving the optimization problem. Therefore, the resulting optimal path was used as a metric to compare the accuracy of the heuristic based approximations. This section presents the SUAS equations of motion, a multi objective cost functional to minimize the slant range error with the minimal amount of control input, and the optimal control algorithm used to determine the optimal path. Equations of Motion The SUAS was modeled as a modified 2D Dubins (Dubins, 1957) airplane and included a level turn assumption. It was also assumed that the SUAS automatically used the required pitch control to maintain a constant altitude, reducing the degrees of freedom in the optimal control problem. The aircraft's roll rate (f was the only control variable used in the optimization. Assuming the SUAS only executed level turns allowed the roll angle to dictate turn rate and effectively described the SUAS's lateral directional motion. For the optimization the SUAS and ground vehicles' ground velocity was an important parameter. While the SUAS's airspeed was fixed at the velocity corresponding to maximum endurance. However, the presence of wind (Vw) impacted the SUAS's groundspeed thus the SUAS groundspeed had to be calculated according to Equation 1: UNMANNED AERIAL SYSTEMS JOURNAL OF www.uasjournal.org 41 Volume 2, Issue 1 The equations of motion were discretized based on a fixed time step, rt. For a fixed rt, these equations were used as first order approximations to find the state information at the succeeding time step. The discrete form was consistent with the form sent to the optimization algorithm discussed later. The locations of the SUAS and the ground vehicle were required for calculating the slant range at each time step. Since the ground vehicle was friendly, as is the case for convoy overwatch, the exact location was known. For the optimal control algorithm, the location history of the ground vehicle was an exogenous input, passed directly into the optimizer. During flight test, the ground vehicle GPS coordinates were transmitted directly to the SUAS. The slant range at the current time step is defined as: Note that the SUAS altitude was held constant and the ground vehic