Smooth Coverage Path Planning for Unmanned Aerial Vehicles: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Paolo Tripicchio
,
Matteo Unetti
,
Salvatore D’Avella
,
Carlo Alberto Avizzano

Within the Industry 4.0 ecosystem, Inspection Robotics is one fundamental technology to speed up monitoring processes and obtain good accuracy and performance of the inspections while avoiding possible safety issues for human personnel. The robotics inspection of areas and surfaces employing Unmanned Aerial Vehicles (UAVs) has become an increasingly popular tool for agriculture. They offer a cost-effective and efficient way to monitor crops, assess crop health, and gather data for precision agriculture. Drones can cover large areas quickly and capture high-resolution images and other types of data that can be analyzed to identify issues and make informed decisions about crop management.

  • Unmanned Aerial Vehicles
  • Path Planning
  • Model Predictive Control Trajectory Tracking

1. Introduction

Mobile robots are frequently deployed to survey their surroundings to gather valuable information, such as creating a map or identifying the position of an object of interest. Additionally, they can perform a detailed analysis of the environment’s condition either through the direct reconstruction of surfaces or by assessing the quality of its components to determine its overall health or status. Many of the environments in which robots are deployed are complex environments, such as multi-story buildings with connecting staircases, uneven surfaces, etc. In addition, robots are subject to kinematic constraints and, in many applications, the environment in which they are located is an environment about which there is very little information or even unknown, and the combination of these aspects can make exploration a difficult task for a ground robot. For this reason and the recent decline in their price, there has been a great increase in the use of aerial robots (commonly known as drones), particularly mini-drones and micro-drones. Despite their rather limited autonomy, their versatility has made them very attractive in both the industrial and military markets as well as to the public. Common areas of application include the agricultural sector [1], search and rescue [2], cultural heritage [3], and industrial inspection [4].
In particular, they have become an increasingly popular tool for agriculture over the past few years. They offer a cost-effective and efficient way to monitor crops, assess crop health, and gather data for precision agriculture. Drones can cover large areas quickly and capture high-resolution images and other types of data that can be analyzed to identify issues and make informed decisions about crop management. One of the main benefits of using drones for agricultural monitoring is the ability to gather data more frequently and at a higher resolution than is possible with other methods, such as satellite imagery or ground-based sensors. This allows farmers and agronomists to identify problems early and take action to mitigate them, improving crop yields and reducing costs. There are many different types of sensors and data-gathering equipment that can be attached to drones, including cameras, multispectral sensors, and thermal cameras. These can be used to gather a wide range of data, such as plant health, soil moisture levels, and pest and disease outbreaks. The data collected by drones can be used to create detailed maps and reports that can help farmers optimize their operations and make informed decisions about things such as irrigation, fertilization, and pest control. Summarizing, drones offer a valuable tool for monitoring and managing agriculture. They allow for the collection of high-resolution data over large areas, enabling farmers and agronomists to identify problems early and take action to improve crop yields and reduce costs.
Apart from the agricultural sector, many other industrial applications could benefit from drone technologies following the Industry 4.0 paradigm. Drones can be efficiently used for activities such as monitoring and inspection in confined spaces where human personnel has limited access [5], or for inventory generation [6] where their speed and maneuverability can reduce overall timing and required resources.
Independently from the task to accomplish, efficient exploration of the environment is essential. To inspect an environment in an automated manner, it is necessary to have a plan of the path the robot will need to take within the environment. Strategies for planning trajectories are commonly known as the Path-Planning Problem (PPP). Given the starting and ending positions of the robot, the goal is to find a path that leads the robot from the initial position to the final position while minimizing some costs and avoiding collisions with possible obstacles present along the path. Depending on the specific application, the cost to be minimized can be the time, the number of direction changes, the number of braking, or the energy consumption. In PPP, there are no constraints regarding the number of passages that can be made over a certain area. In contrast, the purpose of many applications is to completely explore an environment while avoiding inspecting an area that has already been inspected to reduce energy consumption and at the same time to make the robot return to its initial position at the end of the exploration to make a safe landing (in the case of UAVs) or to allow easy recovery of the robot by an operator.
Coverage Path Planning (CPP) is the problem of finding a path (if any) from a given point to itself that passes through every part of the area of interest, avoiding collisions and minimizing passes over areas already examined. This definition leads back to the well-known Traveling Salesman Problem (TSP), in which the area to be inspected is modeled as a set of nodes in a graph (i.e., waypoints), and a path is a sequence of arcs that begins and ends at the same node. As is well known, finding the Hamiltonian cycle optimum in a graph is part of the NP-hard class of problems; consequently, the computational cost of solving large instances is often too high for the requirements imposed by the application.
Heuristic and meta-heuristic algorithms have polynomial complexity and are useful since they can provide “good” admissible solutions to the CPP problem at a low computational cost. In addition, to decompose the problem into simpler subproblems, most of the algorithms for CPP use geometric decomposition techniques: the area is partitioned into several sub-areas, called cells, which are easily explored with simple Back and Forth trajectories. Thanks to these geometric decomposition techniques, it is also natural to model situations in which there is a fleet of aerial robots that has to accomplish the mission since it is possible to assign a defined set of cells to each of them and finally merge the information collected at the end of the explorations.

2. Coverage Path Planning Methods 

Many researchers have studied the problem of planning trajectories to cover spaces. Comprehensive surveys on the most promising algorithms [7] and UAV applications [8] can be found in the recent literature. It emerges that most of the algorithms developed in recent years use some kind of geometric decomposition to make the problem more tractable. Ost [9] examined different types of trajectories and area decomposition and found that the Back and Forth trajectory without area decomposition had the best results for a single UAV performing offline path planning. Driscoll [10] developed an offline algorithm that accurately covers an agricultural field in O(n2). Valente [11] studied two meta-heuristic approaches: Harmony Search (HS) [12] and Ant Colony Optimization (ACO) [13] for CPP and found that ACO was the best approach for both online and offline systems in terms of path length and the number of changes of direction. An original approach to the solution of the TSP is given by Brocki in [14], where he employs a modified Self-Organizing Map (SOM) [15]. The purpose of the SOM technique is to represent the model of a map with a lower number of dimensions while maintaining the relations of similarity of the nodes contained in it. The presented approach substitutes the classical grid representation with a circular array of neurons where each node is only conscious of the neurons in front of and behind it. The convergence is assured by introducing a learning rate parameter with decay in a similar way to the Q-Learning approach.
To be able to make decisions about actions to be taken during exploration, it is often necessary to construct a map of the environment. Authors in [16] proposed an algorithm for covering space to obtain a series of partially overlapping images of the underlying terrain, using a fleet of fixed-wing drones. Each drone is equipped with a downward-facing camera, and the altitude is adjusted based on the minimum resolution required. Avellar et al. modeled the area (which must either be convex or the convex envelope of a nonconvex area) as a graph and transformed the original problem into a Vehicle Routing Problem (VRP). VRP is a generalization of TSP in which the goal is to find a set of disjoint paths, each of them traveled by a vehicle, that traverses all nodes exactly once. The goal of the algorithm is first, to find the number of drones that minimizes the time required to cover the area. Secondly, it is to calculate the path for each drone that covers its assigned waypoints in the minimum time. The work in [17] presents three experiments performed to evaluate and model the variations in the consumption of energy in different flight situations and proposes a cost function that, when minimized, provides the optimal speed at which the drone must travel to save energy, both in the case of constant and variable speed.
Ongoing research in coverage path planning for UAVs presents different approaches to improve the efficiency and effectiveness of UAV coverage operations, including multiobjective optimization techniques [18], deep reinforcement learning [19], and potential fields [20]. Most approaches consider the velocity of the UAV as fixed, thus reducing the complexity of the problem [21]. In [22], Tripicchio et al. presents a smoothing approach to tackle the NP-Hard problem of achieving full coverage of an environment while optimizing flight time using the full dynamics of UAVs.

 

This entry is adapted from the peer-reviewed paper 10.3390/electronics12102310

References

  1. Tripicchio, P.; Satler, M.; Dabisias, G.; Ruffaldi, E.; Avizzano, C.A. Towards smart farming and sustainable agriculture with drones. In Proceedings of the 2015 international conference on intelligent environments, Prague, Czech Republic, 15–17 July 2015; pp. 140–143.
  2. Mishra, B.; Garg, D.; Narang, P.; Mishra, V. Drone-surveillance for search and rescue in natural disaster. Comput. Commun. 2020, 156, 1–10.
  3. Luhmann, T.; Chizhova, M.; Gorkovchuk, D. Fusion of UAV and terrestrial photogrammetry with laser scanning for 3D reconstruction of historic churches in georgia. Drones 2020, 4, 53.
  4. Nikolic, J.; Burri, M.; Rehder, J.; Leutenegger, S.; Huerzeler, C.; Siegwart, R. A UAV system for inspection of industrial facilities. In Proceedings of the 2013 IEEE Aerospace Conference, Big Sky, MT, USA, 2–9 March 2013; pp. 1–8.
  5. Satler, M.; Unetti, M.; Giordani, N.; Avizzano, C.A.; Tripicchio, P. Towards an autonomous flying robot for inspections in open and constrained spaces. In Proceedings of the 2014 IEEE 11th International Multi-Conference on Systems, Signals & Devices (SSD14), Barcelona, Spain, 11–14 February 2014; pp. 1–6.
  6. Companik, E.; Gravier, M.J.; Farris II, M.T. Feasibility of warehouse drone adoption and implementation. J. Transp. Manag. 2018, 28, 5.
  7. Galceran, E.; Carreras, M. A survey on coverage path planning for robotics. Robot. Auton. Syst. 2013, 61, 1258–1276.
  8. Cabreira, T.M.; Brisolara, L.B.; Paulo R, F.J. Survey on coverage path planning with unmanned aerial vehicles. Drones 2019, 3, 4.
  9. Öst, G. Search Path Generation with UAV Applications Using Approximate Convex Decomposition. Master’s Thesis, Linköping University, Linköping, Sweden, 2012.
  10. Driscoll, T.M. Complete Coverage Path Planning in an Agricultural Environment. Ph.D. Thesis, Iowa State University, Ames, IA, USA, 2011.
  11. Valente, J. Aerial Coverage Path Planning Applied to Mapping. Ph.D. Thesis, ETSI Industriales (UPM), Madrid, Spain, 2014.
  12. Geem, Z.W.; Kim, J.H.; Loganathan, G.V. A new heuristic optimization algorithm: Harmony search. Simulation 2001, 76, 60–68.
  13. Dorigo, M.; Gambardella, L.M. Ant colonies for the travelling salesman problem. Biosystems 1997, 43, 73–81.
  14. Brocki, Ł.; Koržinek, D. Kohonen self-organizing map for the traveling salesperson problem. In Recent Advances in Mechatronics; Springer: Berlin/Heidelberg, Germany, 2007; pp. 116–119.
  15. Kohonen, T. The self-organizing map. Proc. IEEE 1990, 78, 1464–1480.
  16. Avellar, G.S.; Pereira, G.A.; Pimenta, L.C.; Iscold, P. Multi-UAV routing for area coverage and remote sensing with minimum time. Sensors 2015, 15, 27783–27803.
  17. Di Franco, C.; Buttazzo, G. Coverage path planning for UAVs photogrammetry with energy and resolution constraints. J. Intell. Robot. Syst. 2016, 83, 445–462.
  18. Majeed, A.; Hwang, S.O. A multi-objective coverage path planning algorithm for UAVs to cover spatially distributed regions in urban environments. Aerospace 2021, 8, 343.
  19. Theile, M.; Bayerlein, H.; Nai, R.; Gesbert, D.; Caccamo, M. UAV coverage path planning under varying power constraints using deep reinforcement learning. In Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA, 24 October 2020–24 January 2021; pp. 1444–1449.
  20. Chen, S.; Yang, Z.; Liu, Z.; Jin, H. An improved artificial potential field based path planning algorithm for unmanned aerial vehicle in dynamic environments. In Proceedings of the 2017 International Conference on Security, Pattern Analysis, and Cybernetics (SPAC), Shenzhen, China, 15–17 December 2017; pp. 591–596.
  21. Jones, M.; Djahel, S.; Welsh, K. Path-planning for unmanned aerial vehicles with environment complexity considerations: A survey. ACM Comput. Surv. 2023, 55, 1–39.
  22. Tripicchio P, Unetti M, D’Avella S, Avizzano CA. Smooth Coverage Path Planning for UAVs with Model Predictive Control Trajectory Tracking. Electronics. 2023; 12(10):2310.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
ScholarVision Creations
Feedback