Valley Path Planning on 3D Terrains Using NSGA-II Algorithm

Abstract

Valley path planning on 3D terrains holds significant importance in navigating and understanding complex landscapes. This specialized form of path planning focuses on finding optimal routes that adhere to the natural contours of valleys within three-dimensional terrains. The significance of valley path planning lies in its ability to address specific challenges presented by valleys, such as varying depths, steep slopes, and potential obstacles. By following the natural flow of valleys, path planning can enhance the efficiency of navigation and minimize the risk of encountering difficult terrain or hazards. In recent years, an increasing number of researchers have focused on the study of valley path planning on 3D terrains. This study presents a valley path planning method utilizing the NSGA-II (Non-dominated Sorting Genetic Algorithm II) approach. To ensure that the paths generated by the algorithm closely follow the valley lines, the algorithm establishes an optimization function that includes three optimization criteria: mean altitude, flight route length, and mean offset. To test the performance of this algorithm, we conducted experiments based on workspaces based on three datasets full of 3D terrains and compared it with three baseline algorithms. The evaluation indicates that the suggested algorithm successfully designs routes that closely follow the valley contours.

Keywords

• valley path planning
• Non-dominated Sorting Genetic Algorithm II
• 3D terrains