Optimized Graph-Search-Based Path Planning for Intelligent UAVs in Complex Environments

The Unmanned Aerial Vehicles (UAVs) have experienced significant developments; therefore, they can be used in various sectors including agriculture, surveillance, disaster management and industrial monitoring. They have been able to work independently and this has contributed to a large extent to the minimization of human intervention which has made them efficient and cost effective in their operation. But, with the increasing use of UAVs, issues like Coverage Path Planning (CPP) have become more important. The CPP issue consists in creating optimal routes that will allow UAVs to fly over the given geographical areas, especially complicated concave geometries with fixed obstacles. To solve this problem, it is essential to develop novel and computationally efficient approaches that reduce traversal time and energy usage and provide omnipresence of the area. The proposed research is to create a new solution to CPP issue in concave geographic areas with immobile impediments. The offered methodology presents the Pair of point identification (PPI) technique and it is a systematic way of locating pairs of coverage points in each of the decomposed sub-areas. These points are important navigation milestones to the UAVs, which make optimization of path simple to follow in tricky terrain. The problem is also developed as a Travelling Sales Person (TSP) problem, so that it becomes feasible to apply Beam Search Algorithms that make use of the heuristic search based principles and come up with near-optimal solutions that consume lower computational costs. The originality of the proposed methodology is that it incorporates the initiative of conventional geometric decomposition approach with advanced searching programmes, which creates a scalable and powerful solution to intricate UAV path-planning challenges. This is a graph-search-based CPP work that builds upon the concept of geometric decomposition, waypoint pairing constrained, and a limited-width heuristic search. The proposed Beam Search algorithm shows a decrease in the maximum length of the tour by as much as 8 per cent compared to the Hill Climbing algorithm, and the optimal path length of A.0. asteroid search algorithm is also optimal, and it performs well due to its thin search width. The methodology reduces the execution time to up to 30% and the energy usage by about 15%. Also, coverage efficiency realized is 98-99.5%, so there was limited coverage lapses in the area under coverage. These findings indicate the strength and flexibility of the suggested solution especially when operating in large-scale and high-obstacle environments. In general, the methodology contributes to the development of the UAV path planning, providing the computationally efficient, scalable, and precise solution to the key issues in autonomous UAV navigation.