Optimization
Holistic Construction Automation with Modular Robots: From High-Level Task Specification to Execution
Külz, Jonathan, Terzer, Michael, Magri, Marco, Giusti, Andrea, Althoff, Matthias
In situ robotic automation in construction is challenging due to constantly changing environments, a shortage of robotic experts, and a lack of standardized frameworks bridging robotics and construction practices. This work proposes a holistic framework for construction task specification, optimization of robot morphology, and mission execution using a mobile modular reconfigurable robot. Users can specify and monitor the desired robot behavior through a graphical interface. Our framework identifies an optimized robot morphology and enables automatic real-world execution by integrating Building Information Modelling (BIM). By leveraging modular robot components, we ensure seamless and fast adaption to the specific demands of the construction task. Experimental validation demonstrates that our approach robustly enables the autonomous execution of robotic drilling.
Accelerating Energy-Efficient Federated Learning in Cell-Free Networks with Adaptive Quantization
Mahmoudi, Afsaneh, Xiao, Ming, Björnson, Emil
Federated Learning (FL) enables clients to share learning parameters instead of local data, reducing communication overhead. Traditional wireless networks face latency challenges with FL. In contrast, Cell-Free Massive MIMO (CFmMIMO) can serve multiple clients on shared resources, boosting spectral efficiency and reducing latency for large-scale FL. However, clients' communication resource limitations can hinder the completion of the FL training. To address this challenge, we propose an energy-efficient, low-latency FL framework featuring optimized uplink power allocation for seamless client-server collaboration. Our framework employs an adaptive quantization scheme, dynamically adjusting bit allocation for local gradient updates to reduce communication costs. We formulate a joint optimization problem covering FL model updates, local iterations, and power allocation, solved using sequential quadratic programming (SQP) to balance energy and latency. Additionally, clients use the AdaDelta method for local FL model updates, enhancing local model convergence compared to standard SGD, and we provide a comprehensive analysis of FL convergence with AdaDelta local updates. Numerical results show that, within the same energy and latency budgets, our power allocation scheme outperforms the Dinkelbach and max-sum rate methods by increasing the test accuracy up to $7$\% and $19$\%, respectively. Moreover, for the three power allocation methods, our proposed quantization scheme outperforms AQUILA and LAQ by increasing test accuracy by up to $36$\% and $35$\%, respectively.
BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning
Pan, Jianming, Ye, Zeqi, Yang, Xiao, Yang, Xu, Liu, Weiqing, Wang, Lewen, Bian, Jiang
Data-driven decision-making processes increasingly utilize end-to-end learnable deep neural networks to render final decisions. Sometimes, the output of the forward functions in certain layers is determined by the solutions to mathematical optimization problems, leading to the emergence of differentiable optimization layers that permit gradient back-propagation. However, real-world scenarios often involve large-scale datasets and numerous constraints, presenting significant challenges. Current methods for differentiating optimization problems typically rely on implicit differentiation, which necessitates costly computations on the Jacobian matrices, resulting in low efficiency. In this paper, we introduce BPQP, a differentiable convex optimization framework designed for efficient end-to-end learning. To enhance efficiency, we reformulate the backward pass as a simplified and decoupled quadratic programming problem by leveraging the structural properties of the KKT matrix. This reformulation enables the use of first-order optimization algorithms in calculating the backward pass gradients, allowing our framework to potentially utilize any state-of-the-art solver. As solver technologies evolve, BPQP can continuously adapt and improve its efficiency. Extensive experiments on both simulated and real-world datasets demonstrate that BPQP achieves a significant improvement in efficiency--typically an order of magnitude faster in overall execution time compared to other differentiable optimization layers. Our results not only highlight the efficiency gains of BPQP but also underscore its superiority over differentiable optimization layer baselines.
Differentiable Convex Optimization Layers in Neural Architectures: Foundations and Perspectives
The integration of optimization problems within neural network architectures represents a fundamental shift from traditional approaches to handling constraints in deep learning. While it is long known that neural networks can incorporate soft constraints with techniques such as regularization, strict adherence to hard constraints is generally more difficult. A recent advance in this field, however, has addressed this problem by enabling the direct embedding of optimization layers as differentiable components within deep networks. This paper surveys the evolution and current state of this approach, from early implementations limited to quadratic programming, to more recent frameworks supporting general convex optimization problems. We provide a comprehensive review of the background, theoretical foundations, and emerging applications of this technology. Our analysis includes detailed mathematical proofs and an examination of various use cases that demonstrate the potential of this hybrid approach. This work synthesizes developments at the intersection of optimization theory and deep learning, offering insights into both current capabilities and future research directions in this rapidly evolving field.
AI-Powered Urban Transportation Digital Twin: Methods and Applications
Di, Xuan, Fu, Yongjie, Turkcan, Mehmet K., Ghasemi, Mahshid, Mo, Zhaobin, Zang, Chengbo, Adhikari, Abhishek, Kostic, Zoran, Zussman, Gil
We present a survey paper on methods and applications of digital twins (DT) for urban traffic management. While the majority of studies on the DT focus on its "eyes," which is the emerging sensing and perception like object detection and tracking, what really distinguishes the DT from a traditional simulator lies in its ``brain," the prediction and decision making capabilities of extracting patterns and making informed decisions from what has been seen and perceived. In order to add values to urban transportation management, DTs need to be powered by artificial intelligence and complement with low-latency high-bandwidth sensing and networking technologies. We will first review the DT pipeline leveraging cyberphysical systems and propose our DT architecture deployed on a real-world testbed in New York City. This survey paper can be a pointer to help researchers and practitioners identify challenges and opportunities for the development of DTs; a bridge to initiate conversations across disciplines; and a road map to exploiting potentials of DTs for diverse urban transportation applications.
Learning Optimal Control and Dynamical Structure of Global Trajectory Search Problems with Diffusion Models
Graebner, Jannik, Li, Anjian, Sinha, Amlan, Beeson, Ryne
Spacecraft trajectory design is a global search problem, where previous work has revealed specific solution structures that can be captured with data-driven methods. This paper explores two global search problems in the circular restricted three-body problem: hybrid cost function of minimum fuel/time-of-flight and transfers to energy-dependent invariant manifolds. These problems display a fundamental structure either in the optimal control profile or the use of dynamical structures. We build on our prior generative machine learning framework to apply diffusion models to learn the conditional probability distribution of the search problem and analyze the model's capability to capture these structures.
Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces
We consider a minimax problem motivated by distributionally robust optimization (DRO) when the worst-case distribution is continuous, leading to significant computational challenges due to the infinite-dimensional nature of the optimization problem. Recent research has explored learning the worst-case distribution using neural network-based generative models to address these computational challenges but lacks algorithmic convergence guarantees. This paper bridges this theoretical gap by presenting an iterative algorithm to solve such a minimax problem, achieving global convergence under mild assumptions and leveraging technical tools from vector space minimax optimization and convex analysis in the space of continuous probability densities. In particular, leveraging Brenier's theorem, we represent the worst-case distribution as a transport map applied to a continuous reference measure and reformulate the regularized discrepancy-based DRO as a minimax problem in the Wasserstein space. Furthermore, we demonstrate that the worst-case distribution can be efficiently computed using a modified Jordan-Kinderlehrer-Otto (JKO) scheme with sufficiently large regularization parameters for commonly used discrepancy functions, linked to the radius of the ambiguity set. Additionally, we derive the global convergence rate and quantify the total number of subgradient and inexact modified JKO iterations required to obtain approximate stationary points. These results are potentially applicable to nonconvex and nonsmooth scenarios, with broad relevance to modern machine learning applications.
Scalable Bayesian Optimization via Focalized Sparse Gaussian Processes
Wei, Yunyue, Zhuang, Vincent, Soedarmadji, Saraswati, Sui, Yanan
Bayesian optimization is an effective technique for black-box optimization, but its applicability is typically limited to low-dimensional and small-budget problems due to the cubic complexity of computing the Gaussian process (GP) surrogate. While various approximate GP models have been employed to scale Bayesian optimization to larger sample sizes, most suffer from overly-smooth estimation and focus primarily on problems that allow for large online samples. In this work, we argue that Bayesian optimization algorithms with sparse GPs can more efficiently allocate their representational power to relevant regions of the search space. To achieve this, we propose focalized GP, which leverages a novel variational loss function to achieve stronger local prediction, as well as FocalBO, which hierarchically optimizes the focalized GP acquisition function over progressively smaller search spaces. Experimental results demonstrate that FocalBO can efficiently leverage large amounts of offline and online data to achieve state-of-the-art performance on robot morphology design and to control a 585-dimensional musculoskeletal system.
A survey on pioneering metaheuristic algorithms between 2019 and 2024
Dokeroglu, Tansel, Canturk, Deniz, Kucukyilmaz, Tayfun
With innovation accelerating, selecting the most effective algorithms has become increasingly demanding for researchers and practitioners alike. Recognizing this, we conducted an in-depth review of metaheuristics introduced in the past six years, focusing on their influence and effectiveness. We evaluated these algorithms across essential criteria: citation frequency, diversity in tackled problem types, code availability, ease of parameter tuning, introduction of novel mechanisms, and resilience to issues like stagnation and early convergence. Out of 158 algorithms, we identified 23 that set themselves apart, each contributing unique solutions to long-standing optimization challenges. These algorithms stand out for their versatility and innovation, positioning them as valuable assets for advancing research and addressing complex real-world problems. Our review offers a detailed analysis of these algorithms, comparing their strengths, limitations, similarities, and applications, while highlighting promising trends and future pathways in metaheuristic research.
Global SLAM in Visual-Inertial Systems with 5G Time-of-Arrival Integration
This paper presents a novel approach to improve global localization and mapping in indoor drone navigation by integrating 5G Time of Arrival (ToA) measurements into ORB-SLAM3, a Simultaneous Localization and Mapping (SLAM) system. By incorporating ToA data from 5G base stations, we align the SLAM's local reference frame with a global coordinate system, enabling accurate and consistent global localization. We extend ORB-SLAM3's optimization pipeline to integrate ToA measurements alongside bias estimation, transforming the inherently local estimation into a globally consistent one. This integration effectively resolves scale ambiguity in monocular SLAM systems and enhances robustness, particularly in challenging scenarios where standard SLAM may fail. Our method is evaluated using five real-world indoor datasets collected with RGB-D cameras and inertial measurement units (IMUs), augmented with simulated 5G ToA measurements at 28 GHz and 78 GHz frequencies using MATLAB and QuaDRiGa. We tested four SLAM configurations: RGB-D, RGB-D-Inertial, Monocular, and Monocular-Inertial. The results demonstrate that while local estimation accuracy remains comparable due to the high precision of RGB-D-based ORB-SLAM3 compared to ToA measurements, the inclusion of ToA measurements facilitates robust global positioning. In scenarios where standard mono-inertial ORB-SLAM3 loses tracking, our approach maintains accurate localization throughout the trajectory.