Waypoint planning with Dubins Curves using Genetic Algorithms

Mission planning for aircraft is often done as waypoint planning. A sequence of waypoints describing the three-dimensional positions that the aircraft must visit. A common approach is to plan the sequence of the waypoints such that the Euclidean distance between them is minimized. When the high-level waypoint planning is finished, a finer grained planning is executed to obtain a trajectory that the aircraft must follow. When the waypoints in a plan are distributed far apart compared to the turning radius of the aircraft, the two- step planning approach works well, but when the waypoints are closer, the kinematics of the aircraft ruins the plan. This work describes an approach that uses a genetic algorithm to solve the waypoint planning problem while considering the kinematics of the aircraft in one single step. This approach entails the addition of a heading and target speed along with the position in the waypoint definition. The kinematics of the aircraft is modeled with Dubins curves, which are extended to allow variable turning radii.