More Like this

1. A-VRPD: Automating Drone-Based Last-Mile Delivery Using Self-Driving Cars

   https://doi.org/10.1109/TITS.2023.3266460  

   Imran, Navid Mohammad ; Mishra, Sabyasachee ; Won, Myounggyu ( September 2023 , IEEE Transactions on Intelligent Transportation Systems)

   Drone-based last-mile delivery is an emerging technology that uses drones loaded onto a truck to deliver parcels to customers. In this paper, we introduce a fully automated system for drone-based last-mile delivery through incorporation of autonomous vehicles (AVs). A novel problem called the autonomous vehicle routing problem with drones (A-VRPD) is defined. A-VRPD is to select AVs from a pool of available AVs based on crowd sourcing, assign selected AVs to customer groups, and schedule routes for selected AVs to optimize the total operational cost. We formulate A-VRPD as a Mixed Integer Linear Program (MILP) and propose an optimization framework to solve the problem. A greedy algorithm is also developed to significantly improve the running time for large-scale delivery scenarios. Extensive simulations were conducted taking into account real-world operational costs for different types of AVs, traveled distances calculated considering the real-time traffic conditions using Google Map API, and varying load capacities of AVs. We evaluated the performance in comparison with two different state-of-the-art solutions: an algorithm designed to address the traditional vehicle routing problem with drones (VRP-D), which involves human-operated trucks working in tandem with drones to deliver parcels, and an algorithm for the two echelon vehicle routing problem (2E-VRP), wherein parcels are first transported to satellite locations and subsequently delivered from those satellites to the customers. The results indicate a substantial increase in profits for both the delivery company and vehicle owners compared with the state-of-the-art algorithms. 

   more » « less
2. Performance Comparison of Fault-Tolerant Virtual Machine Placement Algorithms in Cloud Data Centers

   Gonzalez, Christopher ; Tang, Bin ( March 2021 , the First Computer Science Conference for CSU Undergraduates (CSCSU 2021))

   null (Ed.)

   Fault-tolerant virtual machine (VM) placement refers to the process of placing multiple copies of the same VM cloud application inside cloud data centers. The challenge is how to place required number of VM replicas while minimizing the number of physical machines (PMs) that store them, in order to save energy consumption of cloud data centers. We refer to it as fault-tolerant VM placement problem. In our previous work, we have proposed a greedy algorithm to solve this problem. In this paper, we compare it with an existing research that is based on well-known Welsh Powell Graph-Coloring Algorithm to place items into bins while considering the conflicts between items and items and items and bins. Via extensive simulations, we show that our greedy algorithm can turn off 40-50% more PMs than existing work and can place upto four times as many VM replicas as existing work, achieving much stronger fault-tolerance with less energy consumption. We also compare both algorithms with the optimal integer lin- ear programming (ILP)-based algorithm, which serves as the benchmark of the comparison. 

   more » « less
3. Fast Algorithms for L∞-Constrained S-Rectangular Robust MDPs

   Bahram Behzadian, Marek Petrik ( January 2021 , Advances in neural information processing systems)

   Robust Markov decision processes (RMDPs) are a useful building block of robust reinforcement learning algorithms but can be hard to solve. This paper proposes a fast, exact algorithm for computing the Bellman operator for S-rectangular robust Markov decision processes with L∞-constrained rectangular ambiguity sets. The algorithm combines a novel homotopy continuation method with a bisection method to solve S-rectangular ambiguity in quasi-linear time in the number of states and actions. The algorithm improves on the cubic time required by leading general linear programming methods. Our experimental results confirm the practical viability of our method and show that it outperforms a leading commercial optimization package by several orders of magnitude. 

   more » « less
4. Achieving Tiered Model Quality in 3D Structure from Motion Models Using a Multi-Scale View-Planning Algorithm for Automated Targeted Inspection

   https://doi.org/10.3390/s19122703  

   Okeson, Trent J. ; Barrett, Benjamin J. ; Arce, Samuel ; Vernon, Cory A. ; Franke, Kevin W. ; Hedengren, John D. ( June 2019 , Sensors)

   This study presents a novel multi-scale view-planning algorithm for automated targeted inspection using unmanned aircraft systems (UAS). In industrial inspection, it is important to collect the most relevant data to keep processing demands, both human and computational, to a minimum. This study investigates the viability of automated targeted multi-scale image acquisition for Structure from Motion (SfM)-based infrastructure modeling. A traditional view-planning approach for SfM is extended to a multi-scale approach, planning for targeted regions of high, medium, and low priority. The unmanned aerial vehicle (UAV) can traverse the entire aerial space and facilitates collection of an optimized set of views, both close to and far away from areas of interest. The test case for field validation is the Tibble Fork Dam in Utah. Using the targeted multi-scale flight planning, a UAV automatically flies a tiered inspection using less than 25% of the number of photos needed to model the entire dam at high-priority level. This results in approximately 75% reduced flight time and model processing load, while still maintaining high model accuracy where needed. Models display stepped improvement in visual clarity and SfM reconstruction integrity by priority level, with the higher priority regions more accurately modeling smaller and finer features. A resolution map of the final tiered model is included. While this study focuses on multi-scale view planning for optical sensors, the methods potentially extend to other remote sensors, such as aerial LiDAR. 

   more » « less
5. Heuristic Algorithms for Co-scheduling of Edge Analytics and Routes for UAV Fleet Missions

   A. Khochare, Y. Simmhan ( May 2021 , IEEE International Conference on Computer Communications (INFOCOM))

   null (Ed.)

   Unmanned Aerial Vehicles (UAVs) or drones are increasingly used for urban applications like traffic monitoring and construction surveys. Autonomous navigation allows drones to visit waypoints and accomplish activities as part of their mission. A common activity is to hover and observe a location using on-board cameras. Advances in Deep Neural Networks (DNNs) allow such videos to be analyzed for automated decision making. UAVs also host edge computing capability for on-board inferencing by such DNNs. To this end, for a fleet of drones, we propose a novel Mission Scheduling Problem (MSP) that co-schedules the flight routes to visit and record video at waypoints, and their subsequent on-board edge analytics. The proposed schedule maximizes the utility from the activities while meeting activity deadlines as well as energy and computing constraints. We first prove that MSP is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design two efficient heuristic algorithms, JSC and VRC, that provide fast sub-optimal solutions. Evaluation of these three schedulers using real drone traces demonstrate utility–runtime trade-offs under diverse workloads. 

   more » « less