Source-linked AI summary
Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection
Manh Duong Phung, Cong Hoang Quach, Tran Hiep Dinh, Quang Ha
TL;DR
Inspection path planning requires generating an optimal path under available conditions while avoiding obstacles. The paper applies DPSO to the inspection path planning problem and reports validity and effectiveness in time and travelling cost, with parallel computation improving time performance.
Problem
Inspection path planning should generate an optimal path under available conditions while accounting for obstacle avoidance.
Method
The paper applies a discrete particle swarm optimization algorithm to solve the inspection path planning problem, incorporating viewpoint selection and velocity operations.
Results
The proposed approach is reported as valid and effective in both time and travelling cost, while parallel computation significantly improves DPSO time performance.
Takeaways & Limitations
The approach supports efficient inspection path planning by combining DPSO with parallel computation for improved time performance.
Takeaways & Limitations
The generated path may not be optimal, and future work will extend the algorithm to non-planar surfaces.
Abstract
from arXiv · showhide
In built infrastructure monitoring, an efficient path planning algorithm is essential for robotic inspection of large surfaces using computer vision. In this work, we first formulate the inspection path planning problem as an extended travelling salesman problem (TSP) in which both the coverage and obstacle avoidance were taken into account. An enhanced discrete particle swarm optimization (DPSO) algorithm is then proposed to solve the TSP, with performance improvement by using deterministic initialization, random mutation, and edge exchange. Finally, we take advantage of parallel computing to implement the DPSO in a GPU-based framework so that the computation time can be significantly reduced while keeping the hardware requirement unchanged. To show the effectiveness of the proposed algorithm, experimental results are included for datasets obtained from UAV inspection of an office building and a bridge.
1. Introduction
Vision-based inspection of large or inaccessible infrastructure requires efficient paths that cover surfaces, avoid obstacles, remain near-optimal, and support timely planning. The paper formulates inspection path planning as an extended TSP and solves it with an enhanced DPSO accelerated on GPUs.
- Problem: Inspection paths must provide viewpoints covering every region of interest while avoiding obstacles and generating an optimal path within available processing time.These criteria address coverage, robot safety, path quality, and online replanning or large-area computation.
- Related approaches: Cell-decomposition methods can achieve coverage and obstacle avoidance, but their generated paths may not be optimal.The paper motivates seeking a more feasible alternative to these methods.
- Related approaches: Existing approaches may require constrained robot dynamic models or produce near-optimal solutions, while inspection still requires shorter paths.The introduction frames path length and modeling constraints as unresolved concerns.
- Proposed approach: The proposed method formulates inspection path planning as an extended TSP that simultaneously accounts for coverage and obstacle avoidance.This formulation separates kinematic and dynamic constraints from the DPSO solution, supporting application across a broad range of robots.
- Proposed approach: Deterministic initialization, random mutation, and edge exchange are introduced to improve DPSO accuracy.The paper also implements parallel GPU computation to significantly improve DPSO time performance without adding hardware requirements, allowing operation on popular laptops.
2. Problem formulation
The inspection path planning problem is formulated for UAVs photographing planar building or bridge surfaces, combining viewpoint coverage with obstacle-free navigation. The formulation generates feasible camera viewpoints, computes connecting paths, and models the resulting inspection route as an extended TSP.
- 2. Problem formulation: The inspection setup assumes a CCD camera on a controllable gimbal and a known 3D model of the structure and environment before planning.
- 2. Problem formulation: The objective is to find the shortest UAV path while taking photographs that can later support defect or damage detection.
- 2.1. Viewpoint selection: Viewpoint selection seeks the minimum number of camera configurations needed to cover all surface primitives while satisfying imaging requirements.
- 2.1. Viewpoint selection: Camera configurations are constrained by perpendicular viewing, sufficient resolution for the smallest feature, and specified image overlap.
- 2.1. Viewpoint selection: Viewpoints are generated by gridding each surface, projecting cell centers onto a parallel working surface, and assigning surface-normal orientations.
- 2.2. Point-to-point pathfinding: Point-to-point paths are found with A* on a voxel grid whose occupied clearance region accounts for the UAV’s largest dimension.
- 2.3. Modelling the IPP as a TSP: The resulting inspection graph represents viewpoints as nodes and paths between them as edges weighted by travel cost, assigning very large costs to obstacle-blocked connections.
- 2.3. Modelling the IPP as a TSP: The extended TSP seeks a minimum-cost closed tour that visits every viewpoint exactly once, with degree constraints and subtour elimination enforcing the tour structure.
3. Enhanced Discrete Particle Swarm Optimization for Inspection Path Planning
The paper adapts particle swarm optimization to discrete inspection tours and enhances DPSO with initialization, mutation, edge exchange, and GPU parallelization. These additions target faster convergence, reduced swarm collapse, shorter tours, and lower computation time.
- 3. Enhanced Discrete Particle Swarm Optimization for Inspection Path Planning: The proposed DPSO combines deterministic initialization, random mutation, edge exchange, and GPU execution to improve optimization performance and reduce computation time.The implementation exploits the SIMD-based nature of the optimization and can use GPU-capable, low-power onboard computers.
- 3.1. DPSO approach to the IPP: DPSO represents each particle as a closed sequence of distinct inspection nodes and evolves tours through discrete velocity and position operators.Positions contain N + 1 nodes, with the final node equal to the first; velocities are lists of node transpositions.
- 3.2.1. Deterministic initialization: The enhanced algorithm uses viewpoint-based deterministic seeding alongside random initialization to increase the probability of reaching the global optimum.Viewpoints are generated from a grid decomposition, and back-and-forth tours provide useful seeding particles.
- 3.2.2. Random mutation: Random mutation maintains exploration by disturbing particles after swarm convergence risks producing nearly identical solutions.The method addresses swarm collapse by mutating particles across different randomly chosen dimensions.
- 3.2.3. Edge exchange: Edge exchange evaluates valid edge swaps and selects the exchange producing the greatest tour improvement.Because this augmentation is computationally demanding, it is used only when random mutation produces no improvement.
- 3.2.4. Parallel implementation on GPU: The GPU implementation parallelizes particle velocity, position, fitness, mutation, and edge-exchange computations while keeping initialization on the CPU.Each particle is processed in a different thread, and updated parameters are saved to global memory between computation rounds.
4. Experimental results
Experiments on laser-scanned office-building and concrete-bridge datasets show that enhanced DPSO generates obstacle-avoiding inspection paths and improves both travel cost and computational efficiency. The method also outperforms conventional DPSO and ACS in the reported bridge comparison.
- 4. Experimental results: The experiments use two real laser-scanned datasets: an office-building floor and a concrete-bridge section.The building dataset measures 25 m × 12 m × 8 m, while the bridge dataset includes piers and surfaces measuring 22 m × 10 m × 4.5 m.
- 4. Experimental results: The preprocessing detects planar surfaces, boundaries, and obstacle objects from unordered point clouds using RANSAC, IMU data, convex hulls, and nearest-neighbour clustering.Users then select the surfaces to inspect before path generation.
- 4.1. Path Generation and DPSO Convergence: The generated paths are dominated by back-and-forth coverage patterns, with changes required around obstacles and when switching between surfaces.Front and side views show paths avoiding obstacles for both datasets.
- 4.1. Path Generation and DPSO Convergence: 22.2% lower travelling cost and convergence within 60 generations are reported for the office-building dataset.For the bridge dataset, the corresponding reported values are 37.9% and 80 generations.
- 4.2. Performance comparison: Against ACS on the bridge dataset, enhanced DPSO improves travelling cost by 15% and computation time by 87 times on average.The comparison uses 15 trials and reports average values and standard deviations for processing time and travelling cost.
- 4.2. Performance comparison: The reported processing-time improvement supports applying enhanced DPSO to real-time automated inspection.The paper identifies parallel processing through the DPSO's SIMD feature as the source of the strongest computation-time impact.
5. Conclusion
The paper presents an enhanced DPSO for the IPP problem, formulated as an extended TSP that jointly considers coverage and obstacle avoidance. Deterministic initialization, random mutation, edge exchange, and GPU parallelization improve time and travelling cost, with validation on UAV inspection datasets.
- The enhanced DPSO incorporates deterministic initialization, random mutation, and edge exchange to solve the extended TSP.
- The IPP problem is formulated as an extended TSP that simultaneously considers surface coverage and obstacle avoidance.
- GPU-based parallel implementation significantly reduces computation time while improving travelling cost performance without changing hardware requirements.
- The technique was validated through successful experiments using UAV inspection datasets from an office building and a concrete bridge.
- Future work will extend the algorithm to non-planar surfaces and online re-planning for irregular built infrastructure.