Search

We revisit the problem of motion planning in the Gaussian belief space. Motivated by the fact that most existing sampling-based planners suffer from high computational costs due to the high-dimensional nature of the problem, we propose an approach that leverages a deep learning model to predict optimal path candidates directly from the problem description. Our proposed approach consists of three steps. First, we prepare a training dataset comprising a large number of input-output pairs: the input image encodes the problem to be solved (e.g., start states, goal states, and obstacle locations), whereas the output image encodes the solution (i.e., the ground truth of the shortest path). Any existing planner can be used to generate this training dataset. Next, we leverage the U-Net architecture to learn the dependencies between the input and output data. Finally, a trained U-Net model is applied to a new problem encoded as an input image. From the U-Net's output image, which is interpreted as a distribution of paths,an optimal path candidate is reconstructed. The proposed method significantly reduces computation time compared to the sampling-based baseline algorithm.

We formulate a stochastic zero-sum game to analyze the competition between the attacker, who tries to covertly misguide the vehicle to an unsafe region, versus the detector, who tries to detect the attack signal based on the observed trajectory of the vehicle. Based on Girsanov's theorem and the generalized Neyman-Pearson lemma, we show that a constant bias injection attack as the attacker's strategy and a likelihood ratio test as the detector's strategy constitute the unique saddle point of the game. We also derive the first-order and the second-order exponents of the type II error as a function of the data length.

NanoTerasu, a new 3 GeV synchrotron light source in Japan, began user operation in April 2024. It provides high-brilliance soft to tender X-rays and covers a wide spectral range from ultraviolet to tender X-rays. Its compact storage ring with a circumference of 349 m is based on a four-bend achromat lattice to provide two straight sections in each cell for insertion devices with a natural horizontal emittance of 1.14 nm rad, which is small enough for soft X-rays users. The NanoTerasu accelerator incorporates several innovative technologies, including a full-energy injector C-band linear accelerator with a length of 110 m, an in-vacuum off-axis injection system, a four-bend achromat with B-Q combined bending magnets, and a TM020 mode accelerating cavity with built-in higher-order-mode dampers in the storage ring. This paper presents the accelerator machine commissioning over a half-year period and our model-consistent ring optics correction. The first user operation with a stored beam current of 160 mA is also reported. We summarize the storage ring parameters obtained from the commissioning. This is helpful for estimating the effective optical properties of synchrotron radiation at NanoTerasu., Comment: 30 pages, 24 figures, submitted to the journal

We study a pair of budget- and performance-constrained weak submodular maximization problems. For computational efficiency, we explore the use of stochastic greedy algorithms which limit the search space via random sampling instead of the standard greedy procedure which explores the entire feasible search space. We propose a pair of stochastic greedy algorithms, namely, Modified Randomized Greedy (MRG) and Dual Randomized Greedy (DRG) to approximately solve the budget- and performance-constrained problems, respectively. For both algorithms, we derive approximation guarantees that hold with high probability. We then examine the use of DRG in robust optimization problems wherein the objective is to maximize the worst-case of a number of weak submodular objectives and propose the Randomized Weak Submodular Saturation Algorithm (Random-WSSA). We further derive a high-probability guarantee for when Random-WSSA successfully constructs a robust solution. Finally, we showcase the effectiveness of these algorithms in a variety of relevant uses within the context of Earth-observing LEO constellations which estimate atmospheric weather conditions and provide Earth coverage., Comment: 36 pages, 5 figures. A preliminary version of this article was presented at the 2023 American Control Conference (ACC). This version was submitted to Automatica

Optimal and safety-critical control are fundamental problems for stochastic systems, and are widely considered in real-world scenarios such as robotic manipulation and autonomous driving. In this paper, we consider the problem of efficiently finding optimal and safe control for high-dimensional systems. Specifically, we propose to use dimensionality reduction techniques from a comparison theorem for stochastic differential equations together with a generalizable physics-informed neural network to estimate the optimal value function and the safety probability of the system. The proposed framework results in substantial sample efficiency improvement compared to existing methods. We further develop an autoencoder-like neural network to automatically identify the low-dimensional features of the system to enhance the ease of design for system integration. We also provide experiments and quantitative analysis to validate the efficacy of the proposed method. Source code is available at https://github.com/jacobwang925/path-integral-PINN., Comment: Accepted at the AAAI 24 conference

A simple method to reduce the numerical cost in free electron laser (FEL) simulations is presented, which is based on retrieving a spatially-coherent component of microbunching to suppress artifact effects that can potentially overestimate the FEL gain; this significantly reduces the number of macroparticles to reach the numerical convergence and enables the direct computation of amplified radiation without solving the wave equation. Examples of FEL simulations performed to demonstrate the proposed method show that the computation time to get a reliable result is reduced by 1-2 orders of magnitude depending on the simulation condition.

We consider a continuous-time continuous-space stochastic optimal control problem, where the controller lacks exact knowledge of the underlying diffusion process, relying instead on a finite set of historical disturbance trajectories. In situations where data collection is limited, the controller synthesized from empirical data may exhibit poor performance. To address this issue, we introduce a novel approach named Distributionally Robust Path Integral (DRPI). The proposed method employs distributionally robust optimization (DRO) to robustify the resulting policy against the unknown diffusion process. Notably, the DRPI scheme shows similarities with risk-sensitive control, which enables us to utilize the path integral control (PIC) framework as an efficient solution scheme. We derive theoretical performance guarantees for the DRPI scheme, which closely aligns with selecting a risk parameter in risk-sensitive control. We validate the efficacy of our scheme and showcase its superiority when compared to risk-neutral PIC policies in the absence of the true diffusion process.

In this work, we study minimum data rate tracking of a dynamical system under a neuromorphic event-based sensing paradigm. We begin by bridging the gap between continuous-time (CT) system dynamics and information theory's causal rate distortion theory. We motivate the use of non-singular source codes to quantify bitrates in event-based sampling schemes. This permits an analysis of minimum bitrate event-based tracking using tools already established in the control and information theory literature. We derive novel, nontrivial lower bounds to event-based sensing, and compare the lower bound with the performance of well-known schemes in the established literature.

We consider a setting where a supervisor delegates an agent to perform a certain control task, while the agent is incentivized to deviate from the given policy to achieve its own goal. In this work, we synthesize the optimal deceptive policies for an agent who attempts to hide its deviations from the supervisor's policy. We study the deception problem in the continuous-state discrete-time stochastic dynamics setting and, using motivations from hypothesis testing theory, formulate a Kullback-Leibler control problem for the synthesis of deceptive policies. This problem can be solved using backward dynamic programming in principle, which suffers from the curse of dimensionality. However, under the assumption of deterministic state dynamics, we show that the optimal deceptive actions can be generated using path integral control. This allows the agent to numerically compute the deceptive actions via Monte Carlo simulations. Since Monte Carlo simulations can be efficiently parallelized, our approach allows the agent to generate deceptive control actions online. We show that the proposed simulation-driven control approach asymptotically converges to the optimal control distribution., Comment: 8 pages, 3 figures, CDC 2023

This paper addresses a continuous-time risk-minimizing two-player zero-sum stochastic differential game (SDG), in which each player aims to minimize its probability of failure. Failure occurs in the event when the state of the game enters into predefined undesirable domains, and one player's failure is the other's success. We derive a sufficient condition for this game to have a saddle-point equilibrium and show that it can be solved via a Hamilton-Jacobi-Isaacs (HJI) partial differential equation (PDE) with Dirichlet boundary condition. Under certain assumptions on the system dynamics and cost function, we establish the existence and uniqueness of the saddle-point of the game. We provide explicit expressions for the saddle-point policies which can be numerically evaluated using path integral control. This allows us to solve the game online via Monte Carlo sampling of system trajectories. We implement our control synthesis framework on two classes of risk-minimizing zero-sum SDGs: a disturbance attenuation problem and a pursuit-evasion game. Simulation studies are presented to validate the proposed control synthesis framework., Comment: 8 pages, 4 figures, CDC 2023

Safety control of dynamical systems using barrier functions relies on knowing the full state information. This paper introduces a novel approach for safety control in uncertain MIMO systems with partial state information. The proposed method combines the synthesis of a vector norm barrier function and a dynamic output feedback safety controller to ensure robust safety enforcement. The safety controller guarantees the invariance of the barrier function under uncertain dynamics and disturbances. To address the challenges associated with safety verification using partial state information, a barrier function estimator is developed. This estimator employs an identifier-based state estimator to obtain a state estimate that is affine in the uncertain model parameters of the system. By incorporating a priori knowledge of the limits of the uncertain model parameters and disturbances, the state estimate provides a robust upper bound for the barrier function. Comparative analysis with existing control barrier function based methods shows the advantage of the proposed approach in enforcing safety constraints under tight input constraints and the utilization of estimated state information.

In this paper, we consider the motion planning problem in Gaussian belief space for minimum sensing navigation. Despite the extensive use of sampling-based algorithms and their rigorous analysis in the deterministic setting, there has been little formal analysis of the quality of their solutions returned by sampling algorithms in Gaussian belief space. This paper aims to address this lack of research by examining the asymptotic behavior of the cost of solutions obtained from Gaussian belief space based sampling algorithms as the number of samples increases. To that end, we propose a sampling based motion planning algorithm termed Information Geometric PRM* (IG-PRM*) for generating feasible paths that minimize a weighted sum of the Euclidean and an information-theoretic cost and show that the cost of the solution that is returned is guaranteed to approach the global optimum in the limit of large number of samples. Finally, we consider an obstacle-free scenario and compute the optimal solution using the "move and sense" strategy in literature. We then verify that the cost returned by our proposed algorithm converges to this optimal solution as the number of samples increases., Comment: 19 pages, 10 figures

The global trend of energy deregulation has led to the market mechanism replacing some functionality of load frequency control (LFC). Accordingly, information exchange among participating generators and the market operator plays a crucial role in optimizing social utility. However, privacy has been an equally pressing concern in such settings. This conflict between individuals' privacy and social utility has been a long-standing challenge in market mechanism literature as well as in Cyber-Physical Systems (CPSs). In this paper, we propose a novel encrypted market architecture that leverages a hybrid encryption method and two-party computation protocols, enabling the secure synthesis and implementation of an optimal price-based market mechanism. This work spotlights the importance of secure and efficient outsourcing of controller synthesis, which is a critical element within the proposed framework. A two-area LFC model is used to conduct a case study., Comment: 7 pages, 3 figures, to be published in International Federation of Automatic Control (IFAC)

We propose an adaptive coding approach to achieve linear-quadratic-Gaussian (LQG) control with near-minimum bitrate prefix-free feedback. Our approach combines a recent analysis of a quantizer design for minimum rate LQG control with work on universal lossless source coding for sources on countable alphabets. In the aforementioned quantizer design, it was established that the quantizer outputs are an asymptotically stationary, ergodic process. To enable LQG control with provably near-minimum bitrate, the quantizer outputs must be encoded into binary codewords efficiently. This is possible given knowledge of the probability distributions of the quantizer outputs, or of their limiting distribution. Obtaining such knowledge is challenging; the distributions do not readily admit closed form descriptions. This motivates the application of universal source coding. Our main theoretical contribution in this work is a proof that (after an invertible transformation), the quantizer outputs are random variables that fall within an exponential or power-law envelope class (depending on the plant dimension). Using ideas from universal coding on envelope classes, we develop a practical, zero-delay version of these algorithms that operates with fixed precision arithmetic. We evaluate the performance of this algorithm numerically, and demonstrate competitive results with respect to fundamental tradeoffs between bitrate and LQG control performance., Comment: 8 pages 5 figures, under submission to the 2023 IEEE Conference on Decision and Control

This paper explores minimum sensing navigation of robots in environments cluttered with obstacles. The general objective is to find a path plan to a goal region that requires minimal sensing effort. In [1], the information-geometric RRT* (IG-RRT*) algorithm was proposed to efficiently find such a path. However, like any stochastic sampling-based planner, the computational complexity of IG-RRT* grows quickly, impeding its use with a large number of nodes. To remedy this limitation, we suggest running IG-RRT* with a moderate number of nodes, and then using a smoothing algorithm to adjust the path obtained. To develop a smoothing algorithm, we explicitly formulate the minimum sensing path planning problem as an optimization problem. For this formulation, we introduce a new safety constraint to impose a bound on the probability of collision with obstacles in continuous-time, in contrast to the common discrete-time approach. The problem is amenable to solution via the convex-concave procedure (CCP). We develop a CCP algorithm for the formulated optimization and use this algorithm for path smoothing. We demonstrate the efficacy of the proposed approach through numerical simulations.

This note addresses the problem of evaluating the impact of an attack on discrete-time nonlinear stochastic control systems. The problem is formulated as an optimal control problem with a joint chance constraint that forces the adversary to avoid detection throughout a given time period. Due to the joint constraint, the optimal control policy depends not only on the current state, but also on the entire history, leading to an explosion of the search space and making the problem generally intractable. However, we discover that the current state and whether an alarm has been triggered, or not, is sufficient for specifying the optimal decision at each time step. This information, which we refer to as the alarm flag, can be added to the state space to create an equivalent optimal control problem that can be solved with existing numerical approaches using a Markov policy. Additionally, we note that the formulation results in a policy that does not avoid detection once an alarm has been triggered. We extend the formulation to handle multi-alarm avoidance policies for more reasonable attack impact evaluations, and show that the idea of augmenting the state space with an alarm flag is valid in this extended formulation as well., Comment: 8 pages. arXiv admin note: substantial text overlap with arXiv:2203.16803

The barrier function method for safety control typically assumes the availability of full state information. Unfortunately, in many scenarios involving uncertain dynamical systems, full state information is often unavailable. In this paper, we aim to solve the safety control problem for an uncertain single-input single-output system with partial state information. First, we develop a synthesis method that simultaneously creates a barrier function and a dynamic output feedback safety controller. This safety controller guarantees that the unit sub-level set of the barrier function is an invariant set under the uncertain dynamics and disturbances of the system. Then, we build an identifier-based estimator that provides a state estimate affine to the uncertain model parameters of the system. To detect the potential risks of the system, a fault detector uses the state estimate to find an upper bound for the barrier function. The fault detector triggers the safety controller when the system's original action leads to a potential safety issue and resumes the original action when the potential safety issue is resolved by the safety controller.

In this work we consider discrete-time multiple-input multiple-output (MIMO) linear-quadratic-Gaussian (LQG) control where the feedback consists of variable length binary codewords. To simplify the decoder architecture, we enforce a strict prefix constraint on the codewords. We develop a data compression architecture that provably achieves a near minimum time-average expected bitrate for a fixed constraint on the LQG performance. The architecture conforms to the strict prefix constraint and does not require time-varying lossless source coding, in contrast to the prior art., Comment: 7 pages, 2 figures, accepted to the 2022 IEEE Mediterranean Conference on Communications and Networking (MeditCom 2022)

We present an analytical method to estimate the continuous-time collision probability of motion plans for autonomous agents with linear controlled Ito dynamics. Motion plans generated by planning algorithms cannot be perfectly executed by autonomous agents in reality due to the inherent uncertainties in the real world. Estimating end-to-end risk is crucial to characterize the safety of trajectories and plan risk optimal trajectories. In this paper, we derive upper bounds for the continuous-time risk in stochastic robot navigation using the properties of Brownian motion as well as Boole and Hunter's inequalities from probability theory. Using a ground robot navigation example, we numerically demonstrate that our method is considerably faster than the naive Monte Carlo sampling method and the proposed bounds perform better than the discrete-time risk bounds.

This paper addresses a continuous-time continuous-space chance-constrained stochastic optimal control (SOC) problem via a Hamilton-Jacobi-Bellman (HJB) partial differential equation (PDE). Through Lagrangian relaxation, we convert the chance-constrained (risk-constrained) SOC problem to a risk-minimizing SOC problem, the cost function of which possesses the time-additive Bellman structure. We show that the risk-minimizing control synthesis is equivalent to solving an HJB PDE whose boundary condition can be tuned appropriately to achieve a desired level of safety. Furthermore, it is shown that the proposed risk-minimizing control problem can be viewed as a generalization of the problem of estimating the risk associated with a given control policy. Two numerical techniques are explored, namely the path integral and the finite difference method (FDM), to solve a class of risk-minimizing SOC problems whose associated HJB equation is linearizable via the Cole-Hopf transformation. Using a 2D robot navigation example, we validate the proposed control synthesis framework and compare the solutions obtained using path integral and FDM.

Motivated by control with communication constraints, in this work we develop a time-invariant data compression architecture for linear-quadratic-Gaussian (LQG) control with minimum bitrate prefix-free feedback. For any fixed control performance, the approach we propose nearly achieves known directed information (DI) lower bounds on the time-average expected codeword length. We refine the analysis of a classical achievability approach, which required quantized plant measurements to be encoded via a time-varying lossless source code. We prove that the sequence of random variables describing the quantizations has a limiting distribution and that the quantizations may be encoded with a fixed source code optimized for this distribution without added time-asymptotic redundancy. Our result follows from analyzing the long-term stochastic behavior of the system, and permits us to additionally guarantee that the time-average codeword length (as opposed to expected length) is almost surely within a few bits of the minimum DI. To our knowledge, this time-invariant achievability result is the first in the literature. The originally published version of the supplementary material included a proof that contained an error that turned out to be inconsequential. This updated preprint corrects this error, which originally appeared under Lemma A.7., Comment: Version as accepted to the IEEE Journal on Selected Areas in Information Theory (Special Issue on Modern Compression), modulo an additional correction to the proof of Lemma A.7. Official version: https://ieeexplore.ieee.org/document/10002900. 14 page main paper, 4 pages appendix, 3 figures

We address the attack impact evaluation problem for control system security. We formulate the problem as a Markov decision process with a temporally joint chance constraint that forces the adversary to avoid being detected throughout the considered time period. Owing to the joint constraint, the optimal control policy depends not only on the current state but also on the entire history, which leads to the explosion of the search space and makes the problem generally intractable. It is shown that whether an alarm has been triggered or not, in addition to the current state is sufficient for specifying the optimal decision at each time step. Augmentation of the information to the state space induces an equivalent convex optimization problem, which is tractable using standard solvers., Comment: 8 pages

In this letter, we consider a Linear Quadratic Gaussian (LQG) control system where feedback occurs over a noiseless binary channel and derive lower bounds on the minimum communication cost (quantified via the channel bitrate) required to attain a given control performance. We assume that at every time step an encoder can convey a packet containing a variable number of bits over the channel to a decoder at the controller. Our system model provides for the possibility that the encoder and decoder have shared randomness, as is the case in systems using dithered quantizers. We define two extremal prefix-free requirements that may be imposed on the message packets; such constraints are useful in that they allow the decoder, and potentially other agents to uniquely identify the end of a transmission in an online fashion. We then derive a lower bound on the rate of prefix-free coding in terms of directed information; in particular we show that a previously known bound still holds in the case with shared randomness. We generalize the bound for when prefix constraints are relaxed, and conclude with a rate-distortion formulation., Comment: To appear in the IEEE Control Systems Letters. Version as finally accepted. Copyright 2022 IEEE

We consider the problem of estimating a continuous-time Gauss-Markov source process observed through a vector Gaussian channel with an adjustable channel gain matrix. For a given (generally time-varying) channel gain matrix, we provide formulas to compute (i) the mean-square estimation error attainable by the classical Kalman-Bucy filter, and (ii) the mutual information between the source process and its Kalman-Bucy estimate. We then formulate a novel "optimal channel gain control problem" where the objective is to control the channel gain matrix strategically to minimize the weighted sum of these two performance metrics. To develop insights into the optimal solution, we first consider the problem of controlling a time-varying channel gain over a finite time interval. A necessary optimality condition is derived based on Pontryagin's minimum principle. For a scalar system, we show that the optimal channel gain is a piece-wise constant signal with at most two switches. We also consider the problem of designing the optimal time-invariant gain to minimize the average cost over an infinite time horizon. A novel semidefinite programming (SDP) heuristic is proposed and the exactness of the solution is discussed., Comment: 12 pages. arXiv admin note: substantial text overlap with arXiv:2109.13854

We present novel upper and lower bounds to estimate the collision probability of motion plans for autonomous agents with discrete-time linear Gaussian dynamics. Motion plans generated by planning algorithms cannot be perfectly executed by autonomous agents in reality due to the inherent uncertainties in the real world. Estimating collision probability is crucial to characterize the safety of trajectories and plan risk optimal trajectories. Our approach is an application of standard results in probability theory including the inequalities of Hunter, Kounias, Frechet, and Dawson. Using a ground robot navigation example, we numerically demonstrate that our method is considerably faster than the naive Monte Carlo sampling method and the proposed bounds are significantly less conservative than Boole's bound commonly used in the literature.

We propose a path planning methodology for a mobile robot navigating through an obstacle-filled environment to generate a reference path that is traceable with moderate sensing efforts. The desired reference path is characterized as the shortest path in an obstacle-filled Gaussian belief manifold equipped with a novel information-geometric distance function. The distance function we introduce is shown to be an asymmetric quasi-pseudometric and can be interpreted as the minimum information gain required to steer the Gaussian belief. An RRT*-based numerical solution algorithm is presented to solve the formulated shortest-path problem. To gain insight into the asymptotic optimality of the proposed algorithm, we show that the considered path length function is continuous with respect to the topology of total variation. Simulation results demonstrate that the proposed method is effective in various robot navigation scenarios to reduce sensing costs, such as the required frequency of sensor measurements and the number of sensors that must be operated simultaneously.

We consider the scenario in which a continuous-time Gauss-Markov process is estimated by the Kalman-Bucy filter over a Gaussian channel (sensor) with a variable sensor gain. The problem of scheduling the sensor gain over a finite time interval to minimize the weighted sum of the data rate (the mutual information between the sensor output and the underlying Gauss-Markov process) and the distortion (the mean-square estimation error) is formulated as an optimal control problem. A necessary optimality condition for a scheduled sensor gain is derived based on Pontryagin's minimum principle. For a scalar problem, we show that an optimal sensor gain control is of bang-bang type, except the possibility of taking an intermediate value when there exists a stationary point on the switching surface in the phase space of canonical dynamics. Furthermore, we show that the number of switches is at most two and the time instants at which the optimal gain must be switched can be computed from the analytical solutions to the canonical equations.

This paper considers the problem of task-dependent (top-down) attention allocation for vision-based autonomous navigation using known landmarks. Unlike the existing paradigm in which landmark selection is formulated as a combinatorial optimization problem, we model it as a resource allocation problem where the decision-maker (DM) is granted extra freedom to control the degree of attention to each landmark. The total resource available to DM is expressed in terms of the capacity limit of the in-take information flow, which is quantified by the directed information from the state of the environment to the DM's observation. We consider a receding horizon implementation of such a controlled sensing scheme in the Linear-Quadratic-Gaussian (LQG) regime. The convex-concave procedure is applied in each time step, whose time complexity is shown to be linear in the horizon length if the alternating direction method of multipliers (ADMM) is used. Numerical studies show that the proposed formulation is sparsity-promoting in the sense that it tends to allocate zero data rate to uninformative landmarks.

Although perception is an increasingly dominant portion of the overall computational cost for autonomous systems, only a fraction of the information perceived is likely to be relevant to the current task. To alleviate these perception costs, we develop a novel simultaneous perception-action design framework wherein an agent senses only the task-relevant information. This formulation differs from that of a partially observable Markov decision process, since the agent is free to synthesize not only its policy for action selection but also its belief-dependent observation function. The method enables the agent to balance its perception costs with those incurred by operating in its environment. To obtain a computationally tractable solution, we approximate the value function using a novel method of invariant finite belief sets, wherein the agent acts exclusively on a finite subset of the continuous belief space. We solve the approximate problem through value iteration in which a linear program is solved individually for each belief state in the set, in each iteration. Finally, we prove that the value functions, under an assumption on their structure, converge to their continuous state-space values as the sample density increases., Comment: 18 pages, 8 figures

This paper presents a new method to solve a dynamic sensor fusion problem. We consider a large number of remote sensors which measure a common Gauss-Markov process and encoders that transmit the measurements to a data fusion center through the resource restricted communication network. The proposed approach heuristically minimizes a weighted sum of communication costs subject to a constraint on the state estimation error at the fusion center. The communication costs are quantified as the expected bitrates from the sensors to the fusion center. We show that the problem as formulated is a difference-of-convex program and apply the convex-concave procedure (CCP) to obtain a heuristic solution. We consider a 1D heat transfer model and 2D target tracking by a drone swarm model for numerical studies. Through these simulations, we observe that our proposed approach has a tendency to assign zero data rate to unnecessary sensors indicating that our approach is sparsity promoting, and an effective sensor selection heuristic.

We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of an agent's trajectories to an outside observer while guaranteeing the completion of a task expressed by a reward function. We first prove that an agent with partial observations can achieve an entropy at most as well as an agent with perfect observations. Then, focusing on finite-state controllers (FSCs) with deterministic memory transitions, we show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of the parametric Markov chain (pMC) induced by such FSCs. This relationship allows us to recast the entropy maximization problem as a so-called parameter synthesis problem for the induced pMC. We then present an algorithm to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In numerical examples, we illustrate the relationship between the maximum entropy, the number of memory states in the FSC, and the expected reward., Comment: 14 pages, 10 figures. arXiv admin note: text overlap with arXiv:1903.07665

We consider an architecture of confidential cloud-based control synthesis based on Homomorphic Encryption (HE). Our study is motivated by the recent surge of data-driven control such as deep reinforcement learning, whose heavy computational requirements often necessitate an outsourcing to the third party server. To achieve more flexibility than Partially Homomorphic Encryption (PHE) and less computational overhead than Fully Homomorphic Encryption (FHE), we consider a Reinforcement Learning (RL) architecture over Leveled Homomorphic Encryption (LHE). We first show that the impact of the encryption noise under the Cheon-Kim-Kim-Song (CKKS) encryption scheme on the convergence of the model-based tabular Value Iteration (VI) can be analytically bounded. We also consider secure implementations of TD(0), SARSA(0) and Z-learning algorithms over the CKKS scheme, where we numerically demonstrate that the effects of the encryption noise on these algorithms are also minimal., Comment: 8 pages, 7 figures, American Control Conference

In this work, we study an LQG control system where one of two feedback channels is discrete and incurs a communication cost. We assume that a decoder (co-located with the controller) can make noiseless measurements of a subset of the state vector (referred to as side information) meanwhile a remote encoder (co-located with a sensor) can make arbitrary measurements of the entire state vector, but must convey its measurements to the decoder over a noiseless binary channel. Use of the channel incurs a communication cost, quantified as the time-averaged expected length of prefix-free binary codeword. We study the tradeoff between the communication cost and control performance. The formulation motivates a constrained directed information minimization problem, which can be solved via convex optimization. Using the optimization, we propose a quantizer design and a subsequent achievability result., Comment: Accepted for publication at CISS 2021

The problem of synthesizing an optimal sensor selection policy is pertinent to a variety of engineering applications ranging from event detection to autonomous navigation. We consider such a synthesis problem over an infinite time horizon with a discounted cost criterion. We formulate this problem in terms of a value iteration over the continuous space of covariance matrices. To obtain a computationally tractable solution, we subsequently formulate an approximate sensor selection problem, which is solvable through a point-based value iteration over a finite "mesh" of covariance matrices with a user-defined bounded trace. We provide theoretical guarantees bounding the suboptimality of the sensor selection policies synthesized through this method and provide numerical examples comparing them to known results., Comment: 9 pages, 2 figures

On-farm experiments can provide farmers with information on more efficient crop management in their own fields. Developments in precision agricultural technologies, such as yield monitoring and variable-rate application technology, allow farmers to implement on-farm experiments. Research frameworks including the experimental design and the statistical analysis method strongly influences the precision of the experiment. Conventional statistical approaches (e.g., ordinary least squares regression) may not be appropriate for on-farm experiments because they are not capable of accurately accounting for the underlying spatial variation in a particular response variable (e.g., yield data). The effects of experimental designs and statistical approaches on type I error rates and estimation accuracy were explored through a simulation study hypothetically conducted on experiments in three wheat fields in Japan. Isotropic and anisotropic spatial linear mixed models were established for comparison with ordinary least squares regression models. The repeated designs were not sufficient to reduce both the risk of a type I error and the estimation bias on their own. A combination of a repeated design and an anisotropic model is sometimes required to improve the precision of the experiments. Model selection should be performed to determine whether the anisotropic model is required for analysis of any specific field. The anisotropic model had larger standard errors than the other models, especially when the estimates had large biases. This finding highlights an advantage of anisotropic models since they enable experimenters to cautiously consider the reliability of the estimates when they have a large bias., Comment: 12 pages, 4 figures, Accepted by Precision Agriculture

We consider a discrete-time linear-quadratic Gaussian control problem in which we minimize a weighted sum of the directed information from the state of the system to the control input and the control cost. The optimal control and sensing policies can be synthesized jointly by solving a semidefinite programming problem. However, the existing solutions typically scale cubic with the horizon length. We leverage the structure in the problem to develop a distributed algorithm that decomposes the synthesis problem into a set of smaller problems, one for each time step. We prove that the algorithm runs in time linear in the horizon length. As an application of the algorithm, we consider a path-planning problem in a state space with obstacles under the presence of stochastic disturbances. The algorithm computes a locally optimal solution that jointly minimizes the perception and control cost while ensuring the safety of the path. The numerical examples show that the algorithm can scale to thousands of horizon length and compute locally optimal solutions., Comment: Submitted to 2020 CDC

This paper considers the problem of closed-loop identification of linear scalar systems with Gaussian process noise, where the system input is determined by a deterministic state feedback policy. The regularized least-square estimate (LSE) algorithm is adopted, seeking to find the best estimate of unknown model parameters based on noiseless measurements of the state. We are interested in the fundamental limitation of the rate at which unknown parameters can be learned, in the sense of the D-optimality scalarization criterion subject to a quadratic control cost. We first establish a novel connection between a closed-loop identification problem of interest and a channel coding problem involving an additive white Gaussian noise (AWGN) channel with feedback and a certain structural constraint. Based on this connection, we show that the learning rate is fundamentally upper bounded by the capacity of the corresponding AWGN channel. Although the optimal design of the feedback policy remains challenging, we derive conditions under which the upper bound is achieved. Finally, we show that the obtained upper bound implies that super-linear convergence is unattainable for any choice of the policy.

We consider a path-planning scenario for a mobile robot traveling in a configuration space with obstacles under the presence of stochastic disturbances. A novel path length metric is proposed on the uncertain configuration space and then integrated with the existing RRT* algorithm. The metric is a weighted sum of two terms which capture both the Euclidean distance traveled by the robot and the perception cost, i.e., the amount of information the robot must perceive about the environment to follow the path safely. The continuity of the path length function with respect to the topology of the total variation metric is shown and the optimality of the Rationally Inattentive RRT* algorithm is discussed. Three numerical studies are presented which display the utility of the new algorithm., Comment: 10 pages, 5 figures

We consider a cloud-based control architecture in which the local plants outsource the control synthesis task to the cloud. In particular, we consider a cloud-based reinforcement learning (RL), where updating the value function is outsourced to the cloud. To achieve confidentiality, we implement computations over Fully Homomorphic Encryption (FHE). We use a CKKS encryption scheme and a modified SARSA(0) reinforcement learning to incorporate the encryption-induced delays. We then give a convergence result for the delayed updated rule of SARSA(0) with a blocking mechanism. We finally present a numerical demonstration via implementing on a classical pole-balancing problem., Comment: 7 pages, 2 figures, submitted to SICE ISCS 2021; replaced with supplementary paragraphs added and format change for the correct publishing medium

We study the traffic routing game among a large number of selfish drivers over a traffic network. We consider a specific scenario where the strategic drivers can be classified into teams, where drivers in the same team have identical payoff functions. An incentive mechanism is considered to mitigate congestion, where each driver is subject to dynamic tax penalties. We explore a special case in which the tax is affine in the logarithm of the number of drivers selecting the same route from each team. It is shown via a mean-field approximation that a Nash equilibrium in the limit of a large population can be found by linearly solvable algorithms.

In two-player zero-sum stochastic games, where two competing players make decisions under uncertainty, a pair of optimal strategies is traditionally described by Nash equilibrium and computed under the assumption that the players have perfect information about the stochastic transition model of the environment. However, implementing such strategies may make the players vulnerable to unforeseen changes in the environment. In this paper, we introduce entropy-regularized stochastic games where each player aims to maximize the causal entropy of its strategy in addition to its expected payoff. The regularization term balances each player's rationality with its belief about the level of misinformation about the transition model. We consider both entropy-regularized $N$-stage and entropy-regularized discounted stochastic games, and establish the existence of a value in both games. Moreover, we prove the sufficiency of Markovian and stationary mixed strategies to attain the value, respectively, in $N$-stage and discounted games. Finally, we present algorithms, which are based on convex optimization problems, to compute the optimal strategies. In a numerical example, we demonstrate the proposed method on a motion planning scenario and illustrate the effect of the regularization term on the expected payoff., Comment: Corrected typos

In this paper, we revisit the sequential source coding framework to analyze fundamental performance limitations of discrete-time stochastic control systems subject to feedback data-rate constraints in finite-time horizon. The basis of our results is a new characterization of the lower bound on the minimum total-rate achieved by sequential codes subject to a total (across time) distortion constraint and a computational algorithm that allocates optimally the rate-distortion for any fixed finite-time horizon. This characterization facilitates the derivation of analytical, non-asymptotic, and finite-dimensional lower and upper bounds in two control-related scenarios. (a) A parallel time-varying Gauss-Markov process with identically distributed spatial components that is quantized and transmitted through a noiseless channel to a minimum mean-squared error (MMSE) decoder. (b) A time-varying quantized LQG closed-loop control system, with identically distributed spatial components and with a random data-rate allocation. Our non-asymptotic lower bound on the quantized LQG control problem, reveals the absolute minimum data-rates for (mean square) stability of our time-varying plant for any fixed finite time horizon. We supplement our framework with illustrative simulation experiments., Comment: 40 pages, 6 figures

We consider a cloud-based control architecture for a linear plant with Gaussian process noise, where the state of the plant contains a client's sensitive information. We assume that the cloud tries to estimate the state while executing a designated control algorithm. The mutual information between the client's actual state and the cloud's estimate is adopted as a measure of privacy loss. We discuss the necessity of uplink and downlink privacy masks. After observing that privacy is not necessarily a monotone function of the noise levels of privacy masks, we discuss the joint design procedure for uplink and downlink privacy masks. Finally, the trade-off between privacy and control performance is explored.

We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of a decision-maker's trajectories while guaranteeing the completion of a task expressed by a reward function. First, we prove that a decision-maker with perfect observations can randomize its paths at least as well as a decision-maker with partial observations. Then, focusing on finite-state controllers, we recast the entropy maximization problem as a so-called parameter synthesis problem for a parametric Markov chain (pMC). We show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of this pMC. Finally, we present an algorithm, based on a nonlinear optimization problem, to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In numerical examples, we demonstrate the proposed algorithm on motion planning scenarios., Comment: 10 pages, 6 figures

We consider a dynamic traffic routing game over an urban road network involving a large number of drivers in which each driver selecting a particular route is subject to a penalty that is affine in the logarithm of the number of drivers selecting the same route. We show that the mean-field approximation of such a game leads to the so-called linearly solvable Markov decision process, implying that its mean-field equilibrium (MFE) can be found simply by solving a finite-dimensional linear system backward in time. Based on this backward-only characterization, it is further shown that the obtained MFE has the notable property of strong time-consistency. A connection between the obtained MFE and a particular class of fictitious play is also discussed., Comment: arXiv admin note: text overlap with arXiv:1808.05305

Emerging applications in autonomy require control techniques that take into account uncertain environments, communication and sensing constraints, while satisfying highlevel mission specifications. Motivated by this need, we consider a class of Markov decision processes (MDPs), along with a transfer entropy cost function. In this context, we study highlevel mission specifications as co-safe linear temporal logic (LTL) formulae. We provide a method to synthesize a policy that minimizes the weighted sum of the transfer entropy and the probability of failure to satisfy the specification. We derive a set of coupled non-linear equations that an optimal policy must satisfy. We then use a modified Arimoto-Blahut algorithm to solve the non-linear equations. Finally, we demonstrated the proposed method on a navigation and path planning scenario of a Mars rover., Comment: 8 pages, 6 figures, Preprint accepted at the 57th IEEE Conference on Decision and Control, Miami Beach, FL, USA, December 17-19, 2018

We analyze the behavior of a large number of strategic drivers traveling over an urban traffic network using the mean-field game framework. We assume an incentive mechanism for congestion mitigation under which each driver selecting a particular route is charged a tax penalty that is affine in the logarithm of the number of agents selecting the same route. We show that the mean-field approximation of such a large-population dynamic game leads to the so-called linearly solvable Markov decision process, implying that an open-loop $\epsilon$-Nash equilibrium of the original game can be found simply by solving a finite-dimensional linear system.

We propose a convex distributed optimization algorithm for synthesizing robust controllers for large-scale continuous time systems subject to exogenous disturbances. Given a large scale system, instead of solving the larger centralized synthesis task, we decompose the problem into a set of smaller synthesis problems for the local subsystems with a given interconnection topology. Hence, the synthesis problem is constrained to the sparsity pattern dictated by the interconnection topology. To this end, for each subsystem, we solve a local dissipation inequality and then check a small-gain like condition for the overall system. To minimize the effect of disturbances, we consider the $\mathrm{H}_\infty$ synthesis problems. We instantiate the distributed synthesis method using accelerated alternating direction method of multipliers (ADMM) with convergence rate $O(\frac{1}{k^2})$ with $k$ being the number of iterations., Comment: To appear in ACC 2018

We revisit the sequential rate-distortion (SRD) trade-off problem for vector-valued Gauss-Markov sources with mean-squared error distortion constraints. We show via a counterexample that the dynamic reverse water-filling algorithm suggested by [1, eq. (15)] is not applicable to this problem, and consequently the closed form expression of the asymptotic SRD function derived in [1, eq. (17)] is not correct in general. Nevertheless, we show that the multidimensional Gaussian SRD function is semidefinite representable and thus it is readily computable., Comment: 7 pages, 2 figures

We consider the situation in which a continuous-time vector Gauss-Markov process is observed through a vector Gaussian channel (sensor) and estimated by the Kalman-Bucy filter. Unlike in standard filtering problems where a sensor model is given a priori, we are concerned with the optimal sensor design by which (i) the mutual information between the source random process and the reproduction (estimation) process is minimized, and (ii) the minimum mean-square estimation error meets a given distortion constraint. We show that such a sensor design problem is tractable by semidefinite programming. The connection to zero-delay source-coding is also discussed.