Robust Markov Decision Processes (MDPs) offer a promising framework for computing reliable policies under model uncertainty. While policy gradient methods have gained increasing popularity in robust discounted MDPs, their application to the average-reward criterion remains largely unexplored. This paper proposes a Robust Projected Policy Gradient (RP2G), the first generic policy gradient method for robust average-reward MDPs (RAMDPs) that is applicable beyond the typical rectangularity assumption on transition ambiguity. In contrast to existing robust policy gradient algorithms, RP2G incorporates an adaptive decreasing tolerance mechanism for efficient policy updates at each iteration. We also present a comprehensive convergence analysis of RP2G for solving ergodic tabular RAMDPs. Furthermore, we establish the first study of the inner worst-case transition evaluation problem in RAMDPs, proposing two gradient-based algorithms tailored for rectangular and general ambiguity sets, each with provable convergence guarantees. Numerical experiments confirm the global convergence of our new algorithm and demonstrate its superior performance.

Quadruped robots have demonstrated remarkable versatility in various applications, from search and rescue to exploration. Recent advancements have shifted focus from individual robots to swarms, recognizing the potential of collaborative behaviors to achieve complex tasks beyond the capabilities of a single robot. Inspired by the cooperative hunting behaviors observed in nature, this paper presents a reinforcement learning framework for a swarm of quadruped robots to learn decentralized end-to-end hunting locomotion. In particular, we integrate stable and dynamic locomotion with hunting objectives and utilize a guidance vector as privileged information for efficient training. The framework concerns the control dynamics of quadruped robots, ensuring both low-level stability and high-level hunting coordination in muti-robot environments. The trained policy is deployed onto a real robot system, and the experimental results demonstrate coordinative behavior in various scenarios. The implementation code is released to benefit the community.

Safe corridor-based Trajectory Optimization (TO) presents an appealing approach for collision-free path planning of autonomous robots, because its convex formulation can guarantee global optimality. The safe corridor is constructed based on the obstacle map, however, the non-ideal perception induces uncertainty, which is rarely considered in the context of trajectory generation. In this paper, we propose Distributionally Robust Safe Corridor Constraints (DRSCCs) to consider the uncertainty of the safe corridor. Then, we integrate DRSCCs into the trajectory optimization framework using Bernstein basis polynomials. Theoretically, we rigorously prove that the proposed trajectory optimization problem is equivalent to a convex quadratic program, which is computationally efficient to deploy onto real robots. The simulation results show that our method enhances navigation safety by significantly reducing the infeasible motions compared to the baseline. Moreover, the proposed approach is validated through two robotic applications, a micro Unmanned Aerial Vehicle (UAV) and a quadruped robot Unitree A1.

This paper presents a collaborative quadrotor-quadruped robot system for the manipulation of a cable-towed payload. In particular, we aim to solve the challenge from the unknown dynamics of the cable-towed payload. To this end, we first propose novel dynamic models for both the quadrotor and the quadruped robot, taking into account the nonlinear robot dynamics and the uncertainties associated with the cable-towed load. Moreover, we design observers for the hybrid interaction between the robots and the payload. Theoretically, the convergence of these observers is analyzed using Lyapunov functions under mild technical assumptions. Finally, we seamlessly integrate the dynamics models and the observers into a distributed Model Predictive Control (MPC) framework with kinematics limitations and collision avoidance constraints. The proposed system is validated through challenging field experiments in indoor and outdoor environments, involving push disturbances, varying and unknown payloads, uneven terrains, etc.

In this paper, we propose a reactive planning system for quadruped robots based on prescribed-time control. The navigation of the quadruped robot is fundamentally depicted as omnidirectional movements, while a feedback control law is formulated to address any deviations the robot may encounter. In particular, our proposed feedback control system is theoretically proven to achieve convergence within a predefined finite time that is specified by the user. To further compute the optimal convergent time and the local goal state, we present a high-level planning node encompassing terrain-aware kinodynamic search and spatiotemporal trajectory optimization, which can generate collision-free, smooth, and efficient trajectories. The effectiveness of our proposed framework is validated through both numerical simulation and real-robot experiments in indoor and outdoor environments, including scenarios with cluttered obstacles, slopes, and external disturbances.

Despite being a fundamental building block for reinforcement learning, Markov decision processes (MDPs) often suffer from ambiguity in model parameters. Robust MDPs are proposed to overcome this challenge by optimizing the worst-case performance under ambiguity. While robust MDPs can provide reliable policies with limited data, their worst-case performances are often overly conservative, and so they do not offer practical insights into the actual performance of these reliable policies. This paper proposes robust satisficing MDPs (RSMDPs), where the expected returns of feasible policies are softly-constrained to achieve a user-specified target under ambiguity. We derive a tractable reformulation for RSMDPs and develop a first-order method for solving large instances. Experimental results demonstrate that RSMDPs can prescribe policies to achieve their targets, which are much higher than the optimal worst-case returns computed by robust MDPs. Moreover, the average and percentile performances of our model are competitive among other models. We also demonstrate the scalability of the proposed algorithm compared with a state-of-the-art commercial solver.

Robust Markov decision processes (RMDPs) provide a promising framework for computing reliable policies in the face of model errors. Many successful reinforcement learning algorithms build on variations of policy-gradient methods, but adapting these methods to RMDPs has been challenging. As a result, the applicability of RMDPs to large, practical domains remains limited. This paper proposes a new Double-Loop Robust Policy Gradient (DRPG), the first generic policy gradient method for RMDPs. In contrast with prior robust policy gradient algorithms, DRPG monotonically reduces approximation errors to guarantee convergence to a globally optimal policy in tabular RMDPs. We introduce a novel parametric transition kernel and solve the inner loop robust policy via a gradient-based method. Finally, our numerical results demonstrate the utility of our new algorithm and confirm its global convergence properties.

In this paper, we present a fully distributed framework for multiple quadruped robots in environments with obstacles. Our approach utilizes Model Predictive Control (MPC) and multi-robot consensus protocol to obtain the distributed control law. It ensures that all the robots are able to avoid obstacles, navigate to the desired positions, and meanwhile synchronize the gaits. In particular, via MPC and consensus, the robots compute the optimal trajectory and the contact profile of the legs. Then an MPC-based locomotion controller is implemented to achieve the gait, stabilize the locomotion and track the desired trajectory. We present experiments in simulation and with three real quadruped robots in an environment with a static obstacle.

The knowledge gradient (KG) algorithm is a popular policy for the best arm identification (BAI) problem. It is built on the simple idea of always choosing the measurement that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. In this research, we show that this policy has limitations, causing the algorithm not asymptotically optimal. We next provide a remedy for it, by following the manner of one-step look ahead of KG, but instead choosing the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. The new policy is called improved knowledge gradient (iKG). iKG can be shown to be asymptotically optimal. In addition, we show that compared to KG, it is easier to extend iKG to variant problems of BAI, with the $\epsilon$-good arm identification and feasible arm identification as two examples. The superior performances of iKG on these problems are further demonstrated using numerical examples.

Markov decision processes (MDPs) often suffer from the sensitivity issue under model ambiguity. In recent years, robust MDPs have emerged as an effective framework to overcome this challenge. Distributionally robust MDPs extend the robust MDP framework by incorporating distributional information of the uncertain model parameters to alleviate the conservative nature of robust MDPs. This paper proposes a computationally efficient solution framework for solving distributionally robust MDPs with Wasserstein ambiguity sets. By exploiting the specific problem structure, the proposed framework decomposes the optimization problems associated with distributionally robust Bellman updates into smaller subproblems, which can be solved efficiently. The overall complexity of the proposed algorithm is quasi-linear in both the numbers of states and actions when the distance metric of the Wasserstein distance is chosen to be $L_1$, $L_2$, or $L_{\infty}$ norm, and so the computational cost of distributional robustness is substantially reduced. Our numerical experiments demonstrate that the proposed algorithms outperform other state-of-the-art solution methods.

Methods that employ the EM algorithm for parameter estimation typically face a notorious yet unsolved problem that the initialization input significantly impacts the algorithm output. We here develop a Reinforced Expectation Maximization (REM) algorithm for cluster analysis using Gaussian mixture models. The competence of REM is achieved by introducing two innovative strategies into the EM framework: (1) a mode-finding strategy for initialization that detects non-trivial modes in the data, and (2) a mode-pruning strategy for detecting true modes/mixture components of the population. The pruning strategy is well-justified in the context of mixture modelling, and we present theoretical guarantees on the quality of the initialization. Extensive experimental studies on both synthetic and real datasets show that our approach achieves better performance compared to state-of-the-art methods.

We study adjustable distributionally robust optimization problems, where their ambiguity sets can potentially encompass an infinite number of expectation constraints. Although such ambiguity sets have great modeling flexibility in characterizing uncertain probability distributions, the corresponding adjustable problems remain computationally intractable and challenging. To overcome this issue, we propose a greedy improvement procedure that consists of solving, via the (extended) linear decision rule approximation, a sequence of tractable subproblems—each of which considers a relaxed and finitely constrained ambiguity set that can be iteratively tightened to the infinitely constrained one. Through three numerical studies of adjustable distributionally robust optimization models, we show that our approach can yield improved solutions in a systematic way for both two-stage and multistage problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Financial support by the Early Career Scheme from the Hong Kong Research Grants Council [Project No. CityU 21502820], the CityU Start-Up Grant [Project No. 9610481], the CityU Strategic Research Grant [Project No. 7005688], the National Natural Science Foundation of China [Project No. 72032005], and Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited [Project No. 9229076] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0181 ), as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0181 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This article considers quadruped locomotion control in the presence of uncertainties. Two types of structured uncertainties are considered, namely, uncertain friction constraints and uncertain model dynamics. Then, a min-max optimization model is formulated based on robust optimization, and a robust min-max model predictive controller is proposed by recurrently solving the optimization model. We prove that the min-max optimization model is equivalent to a convex quadratic constrained quadratic program by exploiting the structure of uncertainties. Moreover, a two-stage optimization algorithm is proposed to solve the optimization problem efficiently, allowing for the deployment of the controller onto the real robot. The results show that the proposed optimization algorithm can improve solving frequency by$\sim$11× compared with Gurobi. The proposed controller is able to stabilize quadruped locomotion in challenging scenarios where the uncertainties are caused by significant disturbances and unknown environments.

Four-legged animals are able to change their gaits adaptively for lower energy consumption. However, designing a robust controller for their robot counterparts with multi-modal locomotion remains challenging. In this paper, we present a hierarchical control framework that decomposes this challenge into two kinds of problems: high-level decision-making for gait selection and robust low-level control in complex application environments. For gait transitions, we use reinforcement learning (RL) to design a gait policy that selects the optimal gaits in different environments. After the gait is decided, model predictive control (MPC) is applied to implement the desired gait. To improve the robustness of the locomotion, a model adaptation policy is developed to optimize the input parameters of our MPC controller adaptively. The control framework is first trained and tested in simulation, and then it is applied directly to a quadruped robot in real without any fine-tuning. We show that our control framework is more energy efficient by choosing different gaits and is more robust by adjusting model parameters compared to baseline controllers.

In recent years, robust Markov decision processes (MDPs) have emerged as a prominent modeling framework for dynamic decision problems affected by uncertainty. In contrast to classical MDPs, which only account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, robust MDPs additionally account for ambiguity by optimizing in view of the most adverse transition kernel from a prescribed ambiguity set. In this paper, we develop a novel solution framework for robust MDPs with $s$-rectangular ambiguity sets that decomposes the problem into a sequence of robust Bellman updates and simplex projections. Exploiting the rich structure present in the simplex projections corresponding to $\phi$-divergence ambiguity sets, we show that the associated $s$-rectangular robust MDPs can be solved substantially faster than with state-of-the-art commercial solvers as well as a recent first-order solution scheme, thus rendering them attractive alternatives to classical MDPs in practical applications.

We address the problem of computing reliable policies in reinforcement learning problems with limited data. In particular, we compute policies that achieve good returns with high confidence when deployed. This objective, known as the percentile criterion, can be optimized using Robust MDPs (RMDPs). RMDPs generalize MDPs to allow for uncertain transition probabilities chosen adversarially from given ambiguity sets. We show that the RMDP solution’s sub-optimality depends on the spans of the ambiguity sets along the value function. We then propose new algorithms that minimize the span of ambiguity sets defined by weighted L1 and L-infinity norms. Our primary focus is on Bayesian guarantees, but we also describe how our methods apply to frequentist guarantees and derive new concentration inequalities for weighted L1 and L-infinity norms. Experimental results indicate that our optimized ambiguity sets improve significantly on prior construction methods.

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_\infty$-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.

Robust Markov decision processes (MDPs) compute reliable solutions for dynamic decision problems with partially-known transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which limits their scalability. This paper describes new, efficient algorithms for solving the common class of robust MDPs with s- and sa-rectangular ambiguity sets defined by weighted L1 norms. We propose partial policy iteration, a new, efficient, flexible, and general policy iteration scheme for robust MDPs. We also propose fast methods for computing the robust Bellman operator in quasi-linear time, nearly matching the ordinary Bellman operator's linear complexity. Our experimental results indicate that the proposed methods are many orders of magnitude faster than the state-of-the-art approach, which uses linear programming solvers combined with a robust value iteration.

We describe two efficient, and exact, algorithms for computing Bellman updates in robust Markov decision processes (MDPs). The first algorithm uses a homotopy continuation method to compute updates for L1-constrained s,a-rectangular ambiguity sets. It runs in quasi-linear time for plain L1-norms and also generalizes to weighted L1-norms. The second algorithm uses bisection to compute updates for robust MDPs with s-rectangular ambiguity sets. This algorithm, when combined with the homotopy method, also has a quasi-linear runtime. Unlike previous methods, our algorithms compute the primal solution in addition to the optimal objective value, which makes them useful in policy iteration methods. Our experimental results indicate that the proposed methods are over 1,000 times faster than Gurobi, a state-of-the-art commercial optimization package, for small instances, and the performance gap grows considerably with problem size.

Myocardial contrast echocardiography (MCE) is an imaging technique that assesses left ventricle function and myocardial perfusion for the detection of coronary artery diseases. Automatic MCE perfusion quantification is challenging and requires accurate segmentation of the myocardium from noisy and time-varying images. Random forests (RF) have been successfully applied to many medical image segmentation tasks. However, the pixel-wise RF classifier ignores contextual relationships between label outputs of individual pixels. RF which only utilizes local appearance features is also susceptible to data suffering from large intensity variations. In this paper, we demonstrate how to overcome the above limitations of classic RF by presenting a fully automatic segmentation pipeline for myocardial segmentation in full-cycle 2-D MCE data. Specifically, a statistical shape model is used to provide shape prior information that guide the RF segmentation in two ways. First, a novel shape model (SM) feature is incorporated into the RF framework to generate a more accurate RF probability map. Second, the shape model is fitted to the RF probability map to refine and constrain the final segmentation to plausible myocardial shapes. We further improve the performance by introducing a bounding box detection algorithm as a preprocessing step in the segmentation pipeline. Our approach on 2-D image is further extended to 2-D+t sequences which ensures temporal consistency in the final sequence segmentations. When evaluated on clinical MCE data sets, our proposed method achieves notable improvement in segmentation accuracy and outperforms other state-of-the-art methods, including the classic RF and its variants, active shape model and image registration.

Myocardial Contrast Echocardiography (MCE) with micro-bubble contrast agent enables myocardial perfusion quantification which is invaluable for the early detection of coronary artery diseases. In this paper, we proposed a new segmentation method called Shape Model guided Random Forests (SMRF) for the analysis of MCE data. The proposed method utilizes a statistical shape model of the myocardium to guide the Random Forest (RF) segmentation in two ways. First, we introduce a novel Shape Model (SM) feature which captures the global structure and shape of the myocardium to produce a more accurate RF probability map. Second, the shape model is fitted to the RF probability map to further refine and constrain the final segmentation to plausible myocardial shapes. Evaluated on clinical MCE images from 15 patients, our method obtained promising results (Dice = 0.81, Jaccard = 0.70, MAD = 1.68 mm, HD = 6.53 mm) and showed a notable improvement in segmentation accuracy over the classic RF and its variants. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

As the computing industry enters the Cloud era, multicore architectures and virtualisation technologies are replacing traditional IT infrastructures. However, the complex relationship between applications and system resources in multicore virtualised environments is not well understood. Workloads such as web services and on-line financial applications have the requirement of high performance but benchmark analysis suggests that these applications do not optimally benefit from a higher number of cores.