A Perception-Based Fuzzy Route Planing Algorithm for Autonomous Unmanned Ground Vehicles

Phillip J. Durst, Christopher T. Goodina, Cindy L. Bethelb, Derek T. Andersonb, Daniel W. Carruthb, and Hyeona Limb

Abstract: Path planning plays an integral role in mission planning for ground vehicle operations in urban areas. Determining the optimum path through an urban area is a well-understood problem for traditional ground vehicles; however, in the case of autonomous unmanned ground vehicles (UGVs), additional factors must be considered. For an autonomous UGV, perception algorithms rather than platform mobility will be the limiting factor in operational capabilities. For this study, perception was incorporated into the path planning process by associating sensor error costs with traveling through nodes within an urban road network. Three common perception sensors were used for this study: GPS, LIDAR, and IMU. Multiple set aggregation operators were used to blend the sensor error costs into a single cost, and the e ects of choice of aggregation operator on the chosen path were observed. To provide a robust path planning ability, a fuzzy route planning algorithm was developed using membership functions and fuzzy rules to allow for qualitative route planning in the case of generalized UGV performance. The fuzzy membership functions were then applied to several paths through the urban area to determine what sensors were optimized for in each path to provide a measure of the UGVs performance capabilities. The research presented in this paper shows the impacts sensing/perception has on ground vehicle route planning by demonstrating a fuzzy route planning algorithm constructed using a robust rule set that quanti es these impacts. Keywords: Unmanned Ground Vehicles; Path Planning; Perception; Performance Characterization.

1. Introduction

In general, path planning for ground vehicles through a known area of interest involves finding the shortest path between two points that contains no obstacles (Scoggins et al., 2007). Several methods have been developed to and the optimal path between two points, the most popular of which remains the A* algorithm first developed by Hart, Nilsson, and Rapheal in 1968 (Hart et al., 1968) and its multiple variants found in (Latombe, 2012). Obstacles can be defined in many ways depending on the capabilities of the ground vehicles in question, e.g., sharp turns, steep slopes, rough terrain, etc, and paths are planned around these obstacles. For manned ground vehicles, the problem of path planning is considered mostly solved; a good example detailing ground vehicle path planning is (Szczerba et al., 2000).

However, these path planning algorithms do not provide a complete solution for the case of autonomous unmanned ground vehicles (UGVs). Additional factors affect autonomous navigation beyond those that affect traditional ground vehicle mobility, and the best route for an autonomous UGV is not necessarily the shortest path. Rather than driver-based mobility concerns, the outputs of the UGV’s autonomy algorithms will determine a UGV’s mobility performance. The limiting factor for autonomous operations will most likely not be platform mobility but perception algorithm performance. The UGV’s ability to accurately sense its environment determines its ability to successfully navigate a path; therefore, an ideal path planning algorithm for UGVs should take into account the accuracy of the sensor outputs used to drive the UGV's autonomy algorithms.

Furthermore, what constitutes an obstacle for an autonomous ground vehicle is not clearly defined. Most autonomy systems have some built-in fault tolerance and performance limitations that cannot be fully captured using binary, crisp go-nogo obstacle definitions. For example, defining obstacles for a UGV that can handle “some” GPS drop-out: what constitutes “some” GPS drop out? Or an autonomous navigation system that can handle moderately sharp but not very sharp turns? A successful path planner for autonomous UGVs must take into account the fuzziness inherent in autonomy systems.

This study focuses on the use of set aggregation operators and fuzzy membership functions to derive a path planning algorithm for autonomous UGV operations in urban environments. The importance of using fuzzy logic in complex route planning with multiple optimization parameters is summarized well in (Yanyang et al., 2012). In the current study, sensor data accuracy were chosen as the optimization parameters for the reasons discussed above. Average sensor error values for the most common sensors used for autonomous navigation, a laser range finder, an inertial measurement unit, and a GPS receiver, were calculated for a road network within a typical urban environment using the Virtual Autonomous Navigation Environment (VANE), a high-fidelity tool for simulating UGVs and their sensor systems. The error values at each node along the urban road network were fused into a single node cost using various set aggregation operators. To handle qualitative inputs related to autonomy algorithm performance limitations, a set of fuzzy membership functions and fuzzy rules were developed to define a fuzzified obstacle set.

The structure of this paper is as follows. The Technical Approach section (Section 2) gives a detailed derivation of the fuzzy set aggregation operators and fuzzy membership functions. Details on the sensor errors, their calculation, and the simulation environment used can be found in Section 3. The resulting path planning algorithm is presented in Section 4. Section 4 also presents the application of this algorithm for UGV path planning. Finally, Section 5 pro vides conclusions and recommendations for future research.