1,720,980 research outputs found
On the Maximum Connectivity Improvement Problem
No full textIn this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph a weight function (formula presented), a profit function (formula presented), and an integer B, find a set S of at most B edges not in E that maximises (formula presented), where p(R(v, S)) is the sum of the profits of the nodes reachable from node v when the edges in S are added to G. We first show that we can focus on Directed Acyclic Graphs (DAG) without loss of generality. We prove that the MCI problem on DAG is NP-Hard to approximate to within a factor greater than 1-1/e even if we restrict to graphs with a single source or a single sink, and MCI remains NP -Complete if we further restrict to unitary weights. We devise a polynomial time algorithm based on dynamic programming to solve the MCI problem on trees with a single source. We propose a polynomial time greedy algorithm that guarantees (1-1/e) -approximation ratio on DAGs with a single source or a single sink
Automated picking system employing a drone
No full textWe study the possibility of using drones to implement an automated picking system in a warehouse. We imagine a warehouse divided into two contiguous areas: in one area, the drone moves according to the Euclidean distance, while in the other area, the drone moves according to the Manhattan distance. For each customer-order (CO), the automated picking system is in charge of gathering the items requested in the CO to a predefined location where the cart of the drone is positioned. For each item of the order, the drone flies to the location where the item is stored, grasps it, and brings it back to its cart. Our goal is to find the position of the drone's cart that minimizes the sum of the distances traversed by the drone to pick-up all the items of the CO. We propose algorithms to find such a location when the items to be collected are in Euclidean and Manhattan areas. We can prove a √2-approximation factor for our solutions. Moreover, we compare the efficiency of the automated picking system employing a drone with that of a traditional picking system employing a worker that pushes a cart, and we find under which conditions the drone can be more efficient
Border effects on connectivity for randomly oriented directional antenna networks
No full textWe study the possibility of creating a fully con-nected ad-hoc network with bidirectional links between nodes equipped with randomly oriented directional antennas de-ployed in a circular planar region. The major contribution of our paper is to show that in the directional antenna setting there are always isolated nodes, no matter how high the transmission power of the antennas. We observe, however, that the isolated nodes are confined to a narrow annulus near the boundary of the region. We propose two solutions to achieve full connectivity in the directional setting: T-core that reorients isolated antennas towards the centre of the circular region, and Greedy that simply flips the antenna orientation. We show that the former heuristic, which needs information of the location of the centre of the region, achieves full connectivity with high probability and that, even the latter, which requires no extra information, is able to eliminate most of the isolation
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Intrusion Detection Framework for Invasive FPV Drones Using Video Streaming Characteristics
No full textCheap commercial off-the-shelf (COTS) First-Person View (FPV) drones have become widely available for consumers in recent years. Unfortunately, they also provide low-cost attack opportunities to malicious users. Thus, effective methods to detect the presence of unknown and non-cooperating drones within a restricted area are highly demanded. Approaches based on detection of drones based on emitted video stream have been proposed, but were not yet shown to work against other similar benign traffic, such as that generated by wireless security cameras. Most importantly, these approaches were not studied in the context of detecting new unprofiled drone types. In this work, we propose a novel drone detection framework, which leverages specific patterns in video traffic transmitted by drones. The patterns consist of repetitive synchronization packets (we call pivots), which we use as features for a machine learning classifier. We show that our framework can achieve up to 99% in detection accuracy over an encrypted WiFi channel using only 170 packets originated from the drone within 820ms time period. Our framework is able to identify drone transmissions even among very similar WiFi transmissions (such as video streams originated from security cameras) as well as in noisy scenarios with background traffic. Furthermore, the design of our pivot features enables the classifier to detect unprofiled drones in which the classifier has never trained on and is refined using a novel feature selection strategy that selects the features that have the discriminative power of detecting new unprofiled drones
Speeding-up Routing Schedules on Aisle-Graphs
No full textIn this paper, we study the Orienteering Aisle-graphs Single-column Problem (OASP), which is a variant of the route planning problem for an entity/robot moving along a specific aisle-graph consisting of a set of rows connected via just one column at one endpoint of the rows. Such constrained aisle-graph may model, for instance, a vineyard or warehouse, where each vertex is assigned with a reward that a robot gains when visiting it for accomplishing a task. As the robot is energy limited, it must visit a subset of vertices before going back to the depot for recharging, while maximizing the total reward gained. It is known that the OASP for constrained aisle-graphs composed by m rows of length n is polynomially solvable in Om2n2) time, which can be prohibitive for graphs of large dimensions. With the goal of designing more time efficient solutions, we propose four algorithms that iteratively build the solution in a greedy manner. These solutions take at most O(mn(m + n)) time, thus improving the optimal solution by a factor of n. Experimentally, we show that these algorithms collect more than 80% of the optimum reward. For two of them, we also guarantee an approximation ratio of 12(1-1e) on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm
On the Scheduling of Conflictual Deliveries in a last-mile delivery scenario with truck-carried drones
No full textIn this paper, we investigate the symbiosis between a truck and multiple drones in a last-mile package delivery scenario, introducing the Scheduling Conflictual Deliveries Problem (SCDP). From the main depot, a truck takes care of transporting a fleet of drones that will be used to deliver packages to customers. The route of the truck is predefined. Each delivery is associated with the energy cost of a drone, a reward that characterizes the priority of the delivery, and an interval between two points of the truck's route: the point from which the drone departs (launch point) and the point at which the drone returns to the truck (rendezvous point). The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward subject to the drone's battery capacity while ensuring that the same drone performs deliveries whose delivery intervals do not intersect. After showing that SCDP is an NP-hard problem, we devise an Integer Linear Programming (ILP) formulation for it. Furthermore, we devise a pseudo-polynomial time optimal algorithm for the single drone case and additional approximation algorithms for both the single and multiple drones case. Finally, we thoroughly compare the performances of our presented algorithms on different synthetic datasets
How the Wind Can Be Leveraged for Saving Energy in a Truck-Drone Delivery System
Full text linkIn this work, we investigate the impact of the wind in a drone-based delivery system. For the first time, to the best of our knowledge, we adapt the trajectory of the drone to the wind. We consider a truck-drone tandem delivery system. The drone actively reacts to the wind adopting the 'most tailwind' trajectory available between the truck's path and the delivery. The truck moves on a predefined route and carries the drone close to the delivery point. We propose the Minimum-energy Drone-trajectory Problem (MDP) which aims, when the wind affects the delivery area, at planning minimum-energy trajectories for the drone to serve the customers starting from and returning to the truck. We then propose two algorithms that optimally solve MDP under two different routes of the truck. We also analytically study the feasibility of sending drones with limited battery to deliver packages. Finally, we first numerically compare our algorithms on randomly generated synthetic and real data, and then we evaluate our model simulating the drone's flight in the BlueSky simulator
- …
