Metaheuristic Planning for Vehicle Fleets With Kinematic, Uncertain, And Battery Constraints

The planning of vehicle actions and movements is becoming increasingly important in daily life. With the growing list of potential and current applications of autonomous planning, the field is faced with an ever-growing list of complications. These complications make the task of producing efficient plans increasingly difficult. This research studies and develops solutions for a few of the most important vehicle planning applications in recent years. First, there is the planning of vehicle motion while considering the physical limitations of the vehicle. For many vehicles, for example, cars, airplanes, and boats, the biggest limitation is the inability to pan directly to the left or right. Although so many vehicles have this limitation, motion planning under this constraint is a difficult problem to solve efficiently. This research augments several state-of-the-art motion planning algorithms with the constraints imposed by these vehicles without sacrificing any performance penalty compared to the original algorithms. Next, this dissertation studies mission planning under vehicle constraints and when the location of the vehicle is not known exactly. This problem arises when an autonomous vehicle must pass through a region where global positioning system (GPS) is denied or unreliable, for example, urban environments where large buildings interfere with GPS. Not knowing exactly the position of the vehicle leads to complications when attempting to ensure that the vehicle will avoid hitting walls or triggering other undesirable outcomes. This research further augments the mission planning algorithms from before to solve this problem. The resulting algorithms far exceed previous work in terms of reliability and mission optimality. The final development given in this dissertation is the design of routes for fleets of battery electric vehicles with the goal of monitoring a given region. Examples of when this application arises are monitoring a protected building with autonomous robots and law enforcement patrolling while driving electric vehicles. This research derives a formulation of the electric vehicle constraints that considers more aspects of the problem than previous works on the topic. Several algorithms are derived to solve the problem and show the benefits of the proposed constraint formulation.