Cristina M. Pinotti

Francesco Betti Sorbelli, Mauro Conti, Cristina M. Pinotti et al.

Recently, Unmanned Aerial Vehicles (UAVs) are employed for a plethora of civilian applications. Such flying vehicles can accomplish tasks under the pilot's eyesight within the range of a remote controller, or autonomously according to a certain pre-loaded path configuration. Different path deviation attacks can be performed by malicious users against UAVs. We classify such attacks and the relative defenses based on the UAV's flight mode, i.e., (i) First Person View (FPV), (ii) civilian Global Navigation Satellite System based (GNSS), and (iii) GNSS "plus" auxiliary technologies (GNSS+), and on the multiplicity, i.e., (i) Single UAV, and (ii) Multiple UAVs. We found that very little has been done to secure the FPV flight mode against path deviation. In GNSS mode, spoofing is the most worrisome attack. The best defense against spoofing seems to be redundancy, such as adding vision chips to single UAV or using multiple arranged UAVs. No specific attacks and defenses have been found in literature for GNSS+ or for UAVs moving in group without a pre-ordered arrangement. These aspects require further investigation.

Francesco Betti Sorbelli, Stefano Carpin, Federico Coro et al.

In this paper, we study the Orienteering Aisle-graphs Single-access Problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle-graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle-graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when visits the vertex itself. As the robot's energy is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves OASP in O(m^2 n^2) time for aisle-graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy sub-optimal algorithms that run in at most O(mn (m+n)) time. For two of them, we guarantee an approximation ratio of 1/2(1-1/e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

Francesco Betti Sorbelli, Federico Corò, Sajal K. Das et al.

In this paper, we study the feasibility of sending drones to deliver goods from a depot to a customer by solving what we call the Mission-Feasibility Problem (MFP). Due to payload constraints, the drone can serve only one customer at a time. To this end, we propose a novel framework based on time-dependent cost graphs to properly model the MFP and tackle the delivery dynamics. When the drone moves in the delivery area, the global wind may change thereby affecting the drone's energy consumption, which in turn can increase or decrease. This issue is addressed by designing three algorithms, namely: (i) compute the route of minimum energy once, at the beginning of the mission, (ii) dynamically reconsider the most convenient trip towards the destination, and (iii) dynamically select only the best local choice. We evaluate the performance of our algorithms on both synthetic and real-world data. The changes in the drone's energy consumption are reflected by changes in the cost of the edges of the graphs. The algorithms receive the new costs every time the drone flies over a new vertex, and they have no full knowledge in advance of the weights. We compare them in terms of the percentage of missions that are completed with success (the drone delivers the goods and comes back to the depot), with delivered (the drone delivers the goods but cannot come back to the depot), and with failure (the drone neither delivers the goods nor comes back to the depot).

Francesco Betti Sorbelli, Stefano Carpin, Federico Corò et al.

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be NP-hard. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive even for COP in both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.