Solving the area coverage problem with UAVs: A vehicle routing with time windows variation

Download
2020-4
Semiz, Fatih
Polat, Faruk
In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. These difficulties are even greater if the area coverage must continue throughout a specific time window. We address this by considering a Vehicle Routing Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously without violating time windows. In this problem, our aim is to find a way to cover all areas with the necessary number of UAVs during the time windows, minimize the total distance traveled, and provide a fast solution by satisfying the additional constraint that each agent has limited fuel. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs. Then we solve transportation problems with the simplex algorithm to generate the solution. The performance of the proposed algorithm and other implemented algorithms to compare the solution quality is evaluated on example scenarios with practical problem sizes.
Robotics and Autonomous Systems

Suggestions

A Parallel Algorithm for UAV Flight Route Planning on GPU
Sanci, Seckin; İşler, Veysi (Springer Science and Business Media LLC, 2011-12-01)
Aerial surveillance missions require a geographical region known as the area of interest to be inspected. The route that the aerial reconnaissance vehicle will follow is known as the flight route. Flight route planning operation has to be done before the actual mission is executed. A flight route may consist of hundreds of pre-defined geographical positions called waypoints. The optimal flight route planning manages to find a tour passing through all of the waypoints by covering the minimum possible distanc...
Improvement of routing protocols for unmanned flying ad hoc networks (UFANETS) by using crosslayer metrics
Alkış, Oğuz; Ulusoy, İlkay; Department of Electrical and Electronics Engineering (2019)
Unmanned Air Vehicles (UAV) have been used to perform different type of missions. Many of these civilian and military missions require information exchange between UAVs, which is performed by using routing protocols for wireless ad hoc networks. An efficient routing protocol for unmanned flying ad hoc networks (UFANETs) plays a critical role for data transmission during various applications. In the literature, there are many studies for mobile ad hoc networks (MANET) routing protocols. Due to high mobility ...
An Interactive Algorithm for Multi-objective Route Planning
Tezcaner, Diclehan; Köksalan, Mustafa Murat (Springer Science and Business Media LLC, 2011-08-01)
We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as ...
Detection of mini/micro unmanned air vehicle (UAV) under clutter presence and environmental effects
Dere, İsmail Gökhan; Kuzuoğlu, Mustafa; Department of Electrical and Electronics Engineering (2019)
Detection, tracking and classification of Unmanned Air Vehicles (UAVs) is an emerging and crucial capability of radars in recent years. In the presence of clutter such as a crowded city or a foggy weather above sea surface, mini and micro UAVs become very difficult for radars to detect, track and classify. Classification information of UAV targets can be very useful for the critical infrastructures in order to provide security. Examined studies imply that kinematic and characteristic features such as Dopple...
A Trust-based Approach for Secure Data Dissemination in a Mobile Peer-to-Peer Network of AVs
Bhargava, Bharat K.; Angın, Pelin; Ranchal, Rohit; Sivakumar, Ranjitkumar; Linderman, Mark; Sinclair, Asher (2012-03-01)
Mobile peer-to-peer networks of aerial vehicles (AVs) have become significant in collaborative tasks including military missions and search and rescue operations. However, the nature of the communication between the nodes in these networks makes the disseminated data prone to interception by malicious parties, which could cause serious harm for the designated mission of the network. In this paper, we propose an approach for secure data dissemination in a mobile peer-to-peer network, where the data disclosed...
Citation Formats
F. Semiz and F. Polat, “Solving the area coverage problem with UAVs: A vehicle routing with time windows variation,” Robotics and Autonomous Systems, 2020, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35966.