More Like this

1. 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
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. 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
4. Automated 3D Reconstruction Using Optimized View-Planning Algorithms for Iterative Development of Structure-from-Motion Models

   https://doi.org/10.3390/rs12132169  

   Arce, Samuel; Vernon, Cory A.; Hammond, Joshua; Newell, Valerie; Janson, Joseph; Franke, Kevin W.; Hedengren, John D. (July 2020, Remote Sensing)

   Unsupervised machine learning algorithms (clustering, genetic, and principal component analysis) automate Unmanned Aerial Vehicle (UAV) missions as well as the creation and refinement of iterative 3D photogrammetric models with a next best view (NBV) approach. The novel approach uses Structure-from-Motion (SfM) to achieve convergence to a specified orthomosaic resolution by identifying edges in the point cloud and planning cameras that “view” the holes identified by edges without requiring an initial model. This iterative UAV photogrammetric method successfully runs in various Microsoft AirSim environments. Simulated ground sampling distance (GSD) of models reaches as low as 3.4 cm per pixel, and generally, successive iterations improve resolution. Besides analogous application in simulated environments, a field study of a retired municipal water tank illustrates the practical application and advantages of automated UAV iterative inspection of infrastructure using 63 % fewer photographs than a comparable manual flight with analogous density point clouds obtaining a GSD of less than 3 cm per pixel. Each iteration qualitatively increases resolution according to a logarithmic regression, reduces holes in models, and adds details to model edges. 

   more » « less
5. Throughput Maximization in Multi-Band Optical Networks with Column Generation

   https://doi.org/10.1109/ICC51166.2024.10622664  

   Chen, Cao; Xiao, Shilin; Zhou, Fen; Tornatore, Massimo (June 2024, IEEE)

   Multi-band transmission is a promising technical direction for spectrum and capacity expansion of existing optical networks. Due to the increase in the number of usable wavelengths in multi-band optical networks, the complexity of resource allocation problems becomes a major concern. Moreover, the transmission performance, spectrum width, and cost constraint across optical bands may be heterogeneous. Assuming a worst-case transmission margin in U, L, and C-bands, this paper investigates the problem of throughput maximization in multi-band optical networks, including the optimization of route, wavelength, and band assignment. We propose a low-complexity decomposition approach based on Column Generation (CG) to address the scalability issue faced by traditional methodologies. We numerically compare the results obtained by our CG-based approach to an integer linear programming model, confirming the near-optimal network throughput. Our results also demonstrate the scalability of the CG-based approach when the number of wavelengths increases, with the computation time in the magnitude order of 10 s for cases varying from 75 to 1200 wavelength channels per link in a 14-node network. Code of this publication is available at github.com/cchen000/CG-Multi-Band. 

   more » « less