Search

An Optimal Transport (OT)-based decentralized collaborative multi-robot exploration strategy is proposed in this paper. This method is to achieve an efficient exploration with a predefined priority in the given domain. In this context, the efficiency indicates how a team of robots (agents) cover the domain reflecting the corresponding priority map (or degrees of importance) in the domain. The decentralized exploration implies that each agent carries out their exploration task independently in the absence of any supervisory agent/computer. When an agent encounters another agent within a communication range, each agent receives the information about which areas are already covered by other agents, yielding a collaborative exploration. The OT theory is employed to quantify the difference between the distribution formed by the robot trajectories and the given reference spatial distribution indicating the priority. A computationally feasible way is developed to measure the performance of the proposed exploration scheme. Further, the formal algorithm is provided for the efficient, decentralized, and collaborative exploration plan. Simulation results are presented to validate the proposed methods., Comment: arXiv admin note: substantial text overlap with arXiv:2009.00862

In this study, an ergodic environment exploration problem is introduced for a centralized multi-agent system. Given the reference distribution represented by the Mixture of Gaussian (MoG), the ergodicity is achieved when the time-averaged robot distribution is identical to the given reference distribution. The major challenge associated with this problem is to determine proper timing for a team of agents (robots) to visit each Gaussian component in the reference MoG for ergodicity. The ergodic function is defined as a measure of ergodicity and the condition for convergence is derived based on timing analysis. The proposed control strategy provides relatively reasonable performance to achieve the ergodicity. We provide the formal algorithm for centralized multi-agent control to achieve the ergodicity and simulation results are presented for the validation of the proposed algorithm.

This paper addresses an Optimal Transport (OT)-based efficient multi-robot exploration problem, considering the energy constraints of a multi-robot system. The efficiency in this problem implies how a team of robots (agents) covers a given domain, reflecting a priority of areas of interest represented by a density distribution, rather than simply following a preset of uniform patterns. To achieve an efficient multi-robot exploration, the optimal transport theory that quantifies a distance between two density distributions is employed as a tool, which also serves as a means of performance measure. The energy constraints for the multi-robot system is then incorporated into the OT-based multi-robot exploration scheme. The proposed scheme is decoupled from robot dynamics, broadening the applicability of the multi-robot exploration plan to heterogeneous robot platforms. Not only the centralized but also decentralized algorithms are provided to cope with more realistic scenarios such as communication range limits between agents. To measure the exploration efficiency, the upper bound of the performance is developed for both the centralized and decentralized cases based on the optimal transport theory, which is computationally tractable as well as efficient. The proposed multi-robot exploration scheme is also applicable to a time-varying distribution, where the spatio-temporal evolution of the given reference distribution is desired. To validate the proposed method, multiple simulation results are provided.

This paper investigates an expected average error for distributed averaging problems under asynchronous updates. The asynchronism in this context implies no existence of a global clock as well as random characteristics in communication uncertainty such as communication delays and packet drops. Although some previous works contributed to the design of average consensus protocols to guarantee the convergence to an exact average, these methods may increase computational burdens due to extra works. Sometimes it is thus beneficial to make each agent exchange information asynchronously without modifying the algorithm, which causes randomness in the average value as a trade-off. In this study, an expected average error is analyzed based on the switched system framework, to estimate an upper bound of the asynchronous average compared to the exact one in the expectation sense. Numerical examples are provided to validate the proposed results.

This paper addresses the autonomous robot ergodicity problem for efficient environment exploration. The spatial distribution as a reference is given by a mixture of Gaussian and the mass generation of the robot is assumed to be skinny Gaussian. The main problem to solve is then to find out proper timing for the robot to visit as well as leave each component-wise Gaussian for the purpose of achieving the ergodicity. The novelty of the proposed method is that no approximation is required for the developed method. Given the definition of the ergodic function, a convergence condition is derived based on the timing analysis. Also, a formal algorithm to achieve the ergodicity is provided. To support the validity of the proposed algorithm, simulation results are provided.

This paper proposes a control algorithm for stable implementation of asynchronous parallel quadratic programming (PQP) through dual decomposition technique. In general, distributed and parallel optimization requires synchronization of data at each iteration step due to the interdependency of data. The synchronization latency may incur a large amount of waiting time caused by an idle process during computation. We aim to mitigate this synchronization penalty in PQP problems by implementing asynchronous updates of the dual variable. The price to pay for adopting asynchronous computing algorithms is the unpredictability of the solution, resulting in a tradeoff between speedup and accuracy. In the worst case, the state of interest may become unstable owing to the stochastic behavior of asynchrony. We investigate the stability condition of asynchronous PQP problems by employing the switched system framework. A formal algorithm is provided to ensure the asymptotic stability of dual variables. Further, it is shown that the implementation of the proposed algorithm guarantees the uniqueness of optimal solutions, irrespective of asynchronous behavior. To verify the validity of the proposed methods, simulation results are presented., Comment: arXiv admin note: substantial text overlap with arXiv:1506.05485

In this paper, we study a convergence condition for asynchronous consensus problems in multi-agent systems. The convergence in this context implies the asynchronous consensus value converges to the synchronous one and is unique. Although it is reported in the literature that the consensus value under asynchronous communications may not coincide with the synchronous consensus value, it has not received much attention. In some applications, the discrepancy between them may result in serious consequences. For such applications it is critical to determine under what conditions the asynchronous consensus value is the same as the synchronous consensus value. We illustrate these issues with a few examples and then provide a condition, which guarantees that the asynchronous consensus value converges to the synchronous one. The validity of the proposed result is verified with simulations.

In this note, we present the stability as well as performance analysis of asynchronous parallel computing algorithm implemented in 1D heat equation with CUDA. The primary objective of this note lies in dissemination of asynchronous parallel computing algorithm by providing CUDA code for fast and easy implementation. We show that the simulations carried out on nVIDIA GPU device with asynchronous scheme outperforms synchronous parallel computing algorithm. In addition, we also discuss some drawbacks of asynchronous parallel computing algorithms., Comment: arXiv admin note: text overlap with arXiv:1503.03952

In this paper, we analyze the convergence as well as the rate of convergence of asynchronous distributed quadratic programming (QP) with dual decomposition technique. In general, distributed optimization requires synchronization of data at each iteration step due to the interdependency of data. This synchronization latency may incur a large amount of waiting time caused by an idle process during computation. We aim to attack this synchronization penalty in distributed QP problems by implementing asynchronous update of dual variable. The price to pay for adopting asynchronous computing algorithms is unpredictability of the solution, resulting in a tradeoff between speedup and accuracy. Thus, the convergence to an optimal solution is not guaranteed owing to the stochastic behavior of asynchrony. In this paper, we employ the switched system framework as an analysis tool to investigate the convergence of asynchronous distributed QP. This switched system will facilitate analysis on asynchronous distributed QP with dual decomposition, providing necessary and sufficient conditions for the mean square convergence. Also, we provide an analytic expression for the rate of convergence through the switched system, which enables performance analysis of asynchronous algorithms as compared with synchronous case. To verify the validity of the proposed methods, numerical examples are presented with an implementation of asynchronous parallel QP using OpenMP.

In the near future, massively parallel computing systems will be necessary to solve computation intensive applications. The key bottleneck in massively parallel implementation of numerical algorithms is the synchronization of data across processing elements (PEs) after each iteration, which results in significant idle time. Thus, there is a trend towards relaxing the synchronization and adopting an asynchronous model of computation to reduce idle time. However, it is not clear what is the effect of this relaxation on the stability and accuracy of the numerical algorithm. In this paper we present a new framework to analyze such algorithms. We treat the computation in each PE as a dynamical system and model the asynchrony as stochastic switching. The overall system is then analyzed as a switched dynamical system. However, modeling of massively parallel numerical algorithms as switched dynamical systems results in a very large number of modes, which makes current analysis tools available for such systems computationally intractable. We develop new techniques that circumvent this scalability issue. The framework is presented on a one-dimensional heat equation as a case study and the proposed analysis framework is verified by solving the partial differential equation (PDE) in a $\mathtt{nVIDIA\: Tesla^{\scriptsize{TM}}}$ GPU machine, with asynchronous communication between cores., Comment: ACC 2015

In this paper, we consider the stability analysis of large-scale distributed networked control systems with random communication delays between linearly interconnected subsystems. The stability analysis is performed in the Markov jump linear system framework. There have been considerable researches on stability analysis of Markov jump systems, however, these methods are not applicable to large-scale systems because large numbers of subsystems result in an extremely large number of the switching modes. To avoid this scalability issue, we propose a new reduced mode model for stability analysis, which is computationally efficient. We also consider the case in which the transition probabilities for the Markov jump process contain uncertainties. We provide a new method that estimates bounds for uncertain Markov transition probability matrix to guarantee the system stability. The efficiency and the usefulness of the proposed methods are verified through examples.

This paper provides a method to design an optimal switching sequence for jump linear systems with given Gaussian initial state uncertainty. In the practical perspective, the initial state contains some uncertainties that come from measurement errors or sensor inaccuracies and we assume that the type of this uncertainty has the form of Gaussian distribution. In order to cope with Gaussian initial state uncertainty and to measure the system performance, Wasserstein metric that defines the distance between probability density functions is used. Combining with the receding horizon framework, an optimal switching sequence for jump linear systems can be obtained by minimizing the objective function that is expressed in terms of Wasserstein distance. The proposed optimal switching synthesis also guarantees the mean square stability for jump linear systems. The validations of the proposed methods are verified by examples., Comment: ASME Dynamic Systems and Control Conference (DSCC), 2014

In this note, we provide a unified framework for the mean square stability of stochastic jump linear systems via optimal transport. The Wasserstein metric known as an optimal transport, that assesses the distance between probability density functions enables the stability analysis. Without any assumption on the underlying jump process, this Wasserstein distance guarantees the mean square stability for general stochastic jump linear systems, not necessarily for Markovian jump. The validity of the proposed methods are proved by recovering already-known stability conditions under this framework., Comment: 6 pages, no figures, IEEE TAC

In this paper, we propose a new method to measure the probabilistic robustness of stochastic jump linear system with respect to both the initial state uncertainties and the randomness in switching. Wasserstein distance which defines a metric on the manifold of probability density functions is used as tool for the performance and the stability measures. Starting with Gaussian distribution to represent the initial state uncertainties, the probability density function of the system state evolves into mixture of Gaussian, where the number of Gaussian components grows exponentially. To cope with computational complexity caused by mixture of Gaussian, we prove that there exists an alternative probability density function that preserves exact information in the Wasserstein level. The usefulness and the efficiency of the proposed methods are demonstrated by example., Comment: 2014 ACC(American Control Conference) paper

This paper focuses on the performance and the robustness analysis of stochastic jump linear systems. The state trajectory under stochastic jump process becomes random variables, which brings forth the probability distributions in the system state. Therefore, we need to adopt a proper metric to measure the system performance with respect to stochastic switching. In this perspective, Wasserstein metric that assesses the distance between probability density functions is applied to provide the performance and the robustness analysis. Both the transient and steady-state performance of the systems with given initial state uncertainties can be measured in this framework. Also, we prove that the convergence of this metric implies the mean square stability. Overall, this study provides a unifying framework for the performance and the robustness analysis of general stochastic jump linear systems, but not necessarily Markovian jump process that is commonly used for stochastic switching. The practical usefulness and efficiency of the proposed method are verified through numerical examples.

This paper presents a new framework for controller robustness verification with respect to F-16 aircraft's closed-loop performance in longitudinal flight. We compare the state regulation performance of a linear quadratic regulator (LQR) and a gain-scheduled linear quadratic regulator (gsLQR), applied to nonlinear open-loop dynamics of F-16, in presence of stochastic initial condition and parametric uncertainties, as well as actuator disturbance. We show that, in presence of initial condition uncertainties alone, both LQR and gsLQR have comparable immediate and asymptotic performances, but the gsLQR exhibits better transient performance at intermediate times. This remains true in the presence of additional actuator disturbance. Also, gsLQR is shown to be more robust than LQR, against parametric uncertainties. The probabilistic framework proposed here, leverages transfer operator based density computation in exact arithmetic and introduces optimal transport theoretic performance validation and verification (V&V) for nonlinear dynamical systems. Numerical results from our proposed method, are in unison with Monte Carlo simulations., Comment: 27 pages, 17 figures