Co-optimal Coverage Path Planner (CCPP)

Original source code of the paper: Shang, Z., Bradley, J., & Shen, Z. (2020). A co-optimal coverage path planning method for aerial scanning of complex structures. Expert Systems with Applications, 158, 113535. https://doi.org/10.1016/j.eswa.2020.113535

Abstract: The utilization of unmanned aerial vehicles (UAVs) in survey and inspection of civil infrastructure has been growing rapidly. However, computationally efficient solvers that find optimal flight paths while ensuring high-quality data acquisition of the complete 3D structure remains a difficult problem. Existing solvers typically prioritize efficient flight paths, or coverage, or reducing computational complexity of the algorithm – but these objectives are not co-optimized holistically. In this work we introduce a co-optimal coverage path planning (CCPP) method that simultaneously co-optimizes the UAV path, the quality of the captured images, and reducing computational complexity of the solver all while adhering to safety and inspection requirements. The result is a highly parallelizable algorithm that produces more efficient paths where quality of the useful image data is improved. The path optimization algorithm utilizes a particle swarm optimization (PSO) framework which iteratively optimizes the coverage paths without needing to discretize the motion space or simplify the sensing models as is done in similar methods. The core of the method consists of a cost function that measures both the quality and efficiency of a coverage inspection path, and a greedy heuristic for the optimization enhancement by aggressively exploring the viewpoints search spaces. To assess the proposed method, a coverage path quality evaluation method is also presented in this research, which can be utilized as the benchmark for assessing other CPP methods for structural inspection purpose. The effectiveness of the proposed method is demonstrated by comparing the quality and efficiency of the proposed approach with the state-of-art through both synthetic and real-world scenes. The experiments show that our method enables significant performance improvement in coverage inspection quality while preserving the path efficiency on different test geometries.

Libraries

1. Numpy
2. LKH http://webhotel4.ruc.dk/~keld/research/LKH/
3. Deap https://deap.readthedocs.io/en/master/
4. VTK

Code was originally developed under Ubuntu 16.04 python 3.4, tested in Ubuntu 20.04 python 3.8.

Models

Four models can be found in /meshes folder, including three models used in SIP (https://github.com/ethz-asl/StructuralInspectionPlanner.git) and the paper

Parameters

Parameters are stored in param.py

How to run

1. View and select the models in /meshes folder
2. Use the default parameters or select your own in param.py
3. Run main.py

Examples

HoaHakanaia (pop=30, iter=30)

1. Best efficinecy (ε=1.0)

2. Quality-efficiency co-optimization (ε=0.5)

3. Best quality (ε=0.0)

To Do

This repository is still under development. The following fucntions are not included in the current update.

1. OBBTree
2. RRT*
3. Quality evaluation/visualization
4. etc.

Credits

This algorithm was developed by Zhexiong Shang under the supervison and support from Prof. Zhigang Shen and Prof. Justin Bradley at the University of Nebraska-Lincoln