Unmanned Aerial Vehicles (UAVs) are increasingly permitted to operate within Visual Line of Sight (VLoS) under EU and US regulations. However, Beyond Visual Line of Sight (BVLoS) operations remain restricted, with waivers or certifications required. Extended Visual Line of Sight (EVLoS) offers a transitional solution, involving trained observers to assist pilots when visibility is obstructed. We propose enhancing EVLoS by integrating ground infrastructure, specifically city cameras and wireless communication networks already available on the ground, to replace human observers and enable BVLoS capabilities. Fixed and mobile cameras track drones to ensure regulatory compliance, while real-time data transmission via communication networks provides indirect oversight. The approach increases operational range, reliability, and redundancy through multi-hop connectivity. We introduce the Minimum Latency Problem (MLP), a UAV multi-trajectory optimization problem where UAVs are constantly tracked and monitored through ground antennas and city cameras, mimicking the human observers in EVLoS. Our goal is to minimize communication latency while ensuring that the number of antennas used for coverage is minimum. We prove MLP is$N P$-hard and propose an algorithm to solve it. Experiments on synthetic data demonstrate the effectiveness of our approach in matching coverage and latency requirements.

In this paper, we investigate the problem of deploying the minimum number of Unmanned Aerial Vehicles (UAVs) and determining their flying tours to collect data from all Internet of Things (IoT) sensors. We study this problem in a scenario with neighborhoods where a UAV can collect data from an IoT sensor if the distance between them is less than the wireless communication range of the IoT sensor. Since UAVs are powered by batteries with a limited amount of energy, we assume that the total energy consumed during the flying tour of each UAV is bounded by a given budget. We present the Minimum rooted drone Deployment Problem with Neighborhoods (MDPN), which is NP-hard, and propose two approximation algorithms for the single-depot case, where one of them is a bi-criteria approximation algorithm that returns a solution whose tour’s cost is violated by a factor of 1 + ε. Furthermore, we extend these two algorithms to the multi-depot scenario. Finally, we evaluate our algorithms in three different scenarios: the ideal one where the communication range is a circle and the data transfer rate is constant, and two more realistic scenarios where we introduce some degree of irregularity in the communication range and a non-constant rate in data transfer.

Unmanned aerial vehicles (UAVs) are crucial in various civilian applications, especially in Beyond Visual Line of Sight (BVLoS) operations. However, current regulations restrict BVLoS flights to specific corridors for safety reasons. This paper investigates the Drone Path Scheduling Problem (DPSP) whose goal is to assign time slots to each UAV by considering the corridors that UAVs need to traverse, and their starting time slot, in order to reach their destination such that the maximum slot for which all UAVs accomplished their mission is minimized. Time slots guarantee that each UAV accesses a corridor at a unique time, preventing multiple UAVs from using the same corridor simultaneously. We propose the Rec and the Heap-Based algorithms for unidirectional paths, demonstrating their optimality. For bidirectional paths, we offer sub-optimal solutions using Heap-Based and a 2-approximation algorithm called Bi-Alg. Furthermore, we present an Integer Linear Programming (ILP) formulation to optimally solve DPSP on unidirectional and bidirectional paths. Performance evaluations show the efficacy and scalability of our proposed algorithms compared to the ILP formulation.

Drones have become increasingly popular in a variety of fields, including agriculture, emergency response, and package delivery. However, most drone operations are currently limited to within Visual Line of Sight () due to safety concerns. Flying drones Beyond Visual Line of Sight () broadens to new challenges and opportunities, but also requires new technologies and regulatory frameworks to ensure that the drone is constantly under the control of a remote operator. In this work, we propose a novel graph-based multi-layer framework that closely resembles real-world scenarios and challenges in order to plan drone operations. Our framework includes layers of constraints such as ground risk, cellular network infrastructure, and obstacles, at different heights. From the multi-layer structure, a graph is constructed whose edges are weighted with a dependability score that takes into account the information of the layers, allowing efficient path planning of missions, using algorithms such as Dijkstra’s. Since the built graph can be really large, we also propose lighter graph-based corridors by considering only a limited portion of the original graph. Through extensive experimental evaluation on a real dataset, we demonstrate the effectiveness of our framework in solving the (), which can be efficiently solved by applying the Dijkstra’s algorithm.

Modeling and shaping how information spreads through a network is a major research topic in network analysis. While initially the focus has been mostly on efficiency, recently fairness criteria have been taken into account in this setting. Most work has focused on the maximin criteria however, and thus still different groups can receive very different shares of information. In this work we propose to consider fairness as a notion to be guaranteed by an algorithm rather than as a criterion to be maximized. To this end, we propose three optimization problems that aim at maximizing the overall spread while enforcing strict levels of demographic parity fairness via constraints (either ex-post or ex-ante). The level of fairness hence becomes a user choice rather than a property to be observed upon output. We study this setting from various perspectives. First, we prove that the cost of introducing demographic parity can be high in terms of both overall spread and computational complexity, i.e., the price of fairness may be unbounded for all three problems and optimal solutions are hard to compute, in some case even approximately or when fairness constraints may be violated. For one of our problems, we still design an algorithm with both constant approximation factor and fairness violation. We also give two heuristics that allow the user to choose the tolerated fairness violation. By means of an extensive experimental study, we show that our algorithms perform well in practice, that is, they achieve the best demographic parity fairness values. For certain instances we additionally even obtain an overall spread comparable to the most efficient algorithms that come without any fairness guarantee, indicating that the empirical price of fairness may actually be small when using our algorithms.

Fairness in influence maximization has been a very active research topic recently. Most works in this context study the question of how to find seeding strategies (deterministic or probabilistic) such that nodes or communities in the network get their fair share of coverage. Different fairness criteria have been used in this context. All these works assume that the entity that is spreading the information has an inherent interest in spreading the information fairly, otherwise why would they want to use the developed fair algorithms? This assumption may however be flawed in reality -- the spreading entity may be purely efficiency-oriented. In this paper we propose to study two optimization problems with the goal to modify the network structure by adding links in such a way that efficiency-oriented information spreading becomes automatically fair. We study the proposed optimization problems both from a theoretical and experimental perspective, that is, we give several hardness and hardness of approximation results, provide efficient algorithms for some special cases, and more importantly provide heuristics for solving one of the problems in practice. In our experimental study we then first compare the proposed heuristics against each other and establish the most successful one. In a second experiment, we then show that our approach can be very successful in practice. That is, we show that already after adding a few edges to the networks the greedy algorithm that purely maximizes spread surpasses all fairness-tailored algorithms in terms of ex-post fairness. Maybe surprisingly, we even show that our approach achieves ex-post fairness values that are comparable or even better than the ex-ante fairness values of the currently most efficient algorithms that optimize ex-ante fairness.

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in this area. Similar to previous works like Fish et al. (WWW ’19) and Tsang et al. (IJCAI ’19), we study the maximin criterion for (group) fairness. In contrast to their work however, we model the problem in such a way that, when choosing the seed sets, probabilistic strategies are possible rather than only deterministic ones. We introduce two different variants of this probabilistic problem, one that entails probabilistic strategies over nodes (node-based problem) and a second one that entails probabilistic strategies over sets of nodes (set-based problem). After analyzing the relation between the two probabilistic problems, we show that, while the original deterministic maximin problem was inapproximable, both probabilistic variants permit approximation algorithms that achieve a constant multiplicative factor of 1 − 1/e minus an additive arbitrarily small error that is due to the simulation of the information spread. For the node-based problem, the approximation is achieved by observing that a polynomial-sized linear program approximates the problem well. For the set-based problem, we show that a multiplicative-weight routine can yield the approximation result. For an experimental study, we provide implementations of multiplicative-weight routines for both the set-based and the node-based problems and compare the achieved fairness values to existing methods. Maybe non-surprisingly, we show that the ex-ante values, i.e., minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This indicates that studying fairness via randomization is a worthwhile path to follow. Interestingly and maybe more surprisingly, we observe that even the ex-post fairness values, i.e., fairness values of sets sampled according to the probabilistic strategies computed by our routines, dominate over the fairness achieved by previous methods on many of the instances tested.

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in the area of information spread in networks. Similar to previous works like Fish et al. (WWW '19) and Tsang et al. (IJCAI '19), we study the maximin criterion for (group) fairness. By allowing randomized solutions, we introduce two different variants of this problem. While the original deterministic maximin problem has been shown to be inapproximable, interestingly, we show that both probabilistic variants permit approximation algorithms with a constant multiplicative factor of 1-1/e plus an additive arbitrarily small error that is due to the simulation of the information spread. For an experimental study, we provide implementations of our methods and compare the achieved fairness values to existing methods. Non-surprisingly, the ex-ante values, i.e., minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This confirms that studying fairness via randomization is a worthwhile direction. More surprisingly, we observe that even the ex-post fairness values, i.e., fairness values of sets sampled according to the probabilistic strategies, computed by our routines dominate over the fairness achieved by previous methods on most of the instances tested.