Search

The bidirectional broadcast channel denotes a broadcast channel with two receivers where each receiver knows the message intended for the other. We consider streaming sources where messages of each user arrive as bit-stream to the encoder. Thus our main quantity of interest is the bit error probability. By extending Sahai's argument to bidirectional broadcast channel, we show that under maximum-likelihood decoding the bit error probability decays exponentially in delay with positive exponent for all the rate pairs inside the capacity region. We also show existence of deterministic codes which achieve exponentially decaying bit error probability with delay., QC 20111216

In this and a companion paper a dynamic programming (DP) approach to solve a smart home appliances scheduling problem is considered. The challenge with solving the scheduling problem is the coupling of decision variables due to some time precedence constraints. In general, the system of precedence constraints may contain redundant constraints that offer opportunities for simplification. This simplification is desirable for reducing the computation effort of the nonserial DP procedure presented in the companion paper (i.e., Part II). The current paper establishes the uniqueness of the maximum set of redundant constraints and its polynomial-time solvability with optimality guarantee, under the sufficient and necessary condition that the precedence graph (a graph representation of the precedence constraints system) does not contain any cycle with nonnegative weight. A numerical case study indicates the efficiency of the proposed simplification algorithm versus the brute-force enumerative search. Besides helping to reduce the computation effort in the DP procedure described in the companion paper, the algorithm in the current paper solves a generalization of a precedence graph simplification problem arising from application areas such as parallel computing., QC 20150408

In this paper, we investigate the reachability analysis and safety controller synthesis problem for linear discrete-time systems under additive bounded disturbances. We consider the following problem; design a state feedback controller such that any state trajectories starting from an initial set can be robustly controlled towards a target one in finite time, while at the same time avoiding any prohibited regions. One of the potential disadvantages of existing reachability algorithms when external disturbances are taken into account, may be that the solution to guarantee reachability becomes conservative. Motivated by this, this paper provides a new controller synthesis framework based on the notion of tube-based control strategy, in which a suitable sequence of polytopes is generated according to a convex feasibility problem. An illustrative simulation validates the effectiveness of our proposed method., QC 20180306

It is known that the problem of verifying the infinite-step opacity of nondeterministic finite transition systems (NFTSs)is PSPACE-hard. In this paper, we investigate whether it is possible to use classical bisimulation relation to come up with abstract NFTSs and verify the infinite-step opacity of original NFTSs over their abstractions. First, we show that generally bisimulation relation does not preserve infinitestep opacity. Second, by adding some additional conditions to bisimulation relation, we prove that a stronger version of bisimulation relation, called here opacity-preserving bisimulation relation, preserves infinite-step opacity. Therefore, if one can find an abstract NFTS for a large NFTS under an opacity-preserving bisimulation relation, then the infinite-step opacity of the original NFTS can be verified by investigating that over the abstract NFTS. Finally, we show that under some mild assumptions, the quotient relation between an NFTS and its quotient system becomes opacity-preserving bisimulation relation which provides a scheme for constructing opacity-preserving abstractions of large- scale NFTSs. We show the effectiveness of the results using several examples throughout the paper., QC 20180305

This paper investigates the online motion coordination problem for a group of mobile robots moving in a shared workspace. Based on the realistic assumptions that each robot is subject to both velocity and input constraints and can have only local view and local information, a fully distributed multi-robot motion coordination strategy is proposed. Building on top of a cell decomposition, a conflict detection algorithm is presented first. Then, a rule is proposed to assign dynamically a planning order to each pair of neighboring robots, which is deadlock-free. Finally, a two-step motion planning process that combines fixed-path planning and trajectory planning is designed. The effectiveness of the resulting solution is verified by a simulation example., QC 20210412

This paper studies the construction of symbolic abstractions for periodic event-triggered systems. To construct symbolic abstractions, the original event-triggered mechanism is over- and under-approximated, and thus the abstract event-triggered mechanisms are different from the original one, which leads to the asynchronous phenomenon between the original system and the constructed symbolic abstractions. To deal with this issue, an interface is proposed to guarantee the synchronization between the original and abstract event-triggering mechanisms and the equivalence relations between the original system and the constructed symbolic model. Furthermore, we study the controller refinement based on these two constructed symbolic models. Finally, the obtained results are illustrated via a numerical example., QC 20210414

In this paper, we consider a secure distributed filtering problem for linear time-invariant systems with bounded noises and unstable dynamics under compromised observations. A malicious attacker is able to compromise a subset of the agents and manipulate the observations arbitrarily. We first propose a recursive distributed filter consisting of two parts at each time. The first part employs a saturation like scheme, which gives a small gain if the innovation is too large. The second part is a consensus operation of state estimates among neighboring agents. A sufficient condition is then established for the boundedness of estimation error, which is with respect to network topology, system structure, and the maximal compromised agent subset. We further provide an equivalent statement, which connects to 2s-sparse observability in the centralized framework in certain scenarios, such that the sufficient condition is feasible. Numerical simulations are finally provided to illustrate the developed results., QC 20201007

In this paper, we present a unified framework based on integral quadratic constraints for analyzing the convergence of distributed push-pull based optimization algorithms for directed graphs. Our framework provides numerical upper bounds on linear convergence rates of existing distributed push-pull based algorithms when local objective functions are strongly convex and smooth and directed graphs are strongly connected. Moreover, we propose a new distributed optimization algorithm for directed graphs and show that the proposed framework can also be applied to establish its linear convergence rate. The theoretical results are illustrated and validated via numerical examples., Part of proceedings: ISBN 978-1-7281-1164-3QC 20211014

This paper deals with the solution bounds for discrete-time Networked Control Systems (NCSs) via delay-dependent Lyapunov-Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. A time-delay approach was introduced recently for continuous-time NCS under a weighted Try-Once-Discard (TOD) protocol in [12], where actuator saturation was not taken into account. In the present paper, we develop the time-delay approach for linear (probably, uncertain) discrete-time NCS under the weighted TOD protocol in the presence of actuator saturation. A novel Lyapunov-based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time-delay approach is illustrated on the example of a cart-pendulum system., QC 20131216

In this paper a dynamic programming (DP) solution approach to a nonconvex resource allocation problem (RAP) is presented. The problem in this paper generalizes the smart home appliances scheduling problem introduced in the companion paper (i.e., Part I). The computation difficulty with solving the RAP depends on the decision variable coupling, which can be described by an interaction graph. This paper proposes a DP algorithm to solve the RAP in the special setting where the interaction graph is a tree. This extends the applicability result of DP to RAP beyond the standard serial case where the interaction graph is a line. The extension of the result is achieved by establishing that even in the tree case DP computation effort is polynomial in the number of decision variables. For RAP in its general form, this paper proposes a modification to the nonserial DP procedure originally introduced by Bertele and Brioschi. Contrary to that of the previous method, the computation effort of the proposed method can be characterized by a well-known minimum feedback vertex set problem. Case studies on known examples indicate that both nonserial DP methods are similarly efficient., QC 20150408

This paper deals with the solution bounds for discrete-time Networked Control Systems (NCSs) via delay-dependent Lyapunov-Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. A time-delay approach was introduced recently for continuous-time NCS under a weighted Try-Once-Discard (TOD) protocol in [12], where actuator saturation was not taken into account. In the present paper, we develop the time-delay approach for linear (probably, uncertain) discrete-time NCS under the weighted TOD protocol in the presence of actuator saturation. A novel Lyapunov-based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time-delay approach is illustrated on the example of a cart-pendulum system., QC 20131216

This paper deals with the solution bounds for discrete-time Networked Control Systems (NCSs) via delay-dependent Lyapunov-Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. A time-delay approach was introduced recently for continuous-time NCS under a weighted Try-Once-Discard (TOD) protocol in [12], where actuator saturation was not taken into account. In the present paper, we develop the time-delay approach for linear (probably, uncertain) discrete-time NCS under the weighted TOD protocol in the presence of actuator saturation. A novel Lyapunov-based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time-delay approach is illustrated on the example of a cart-pendulum system., QC 20131216

This paper deals with the solution bounds for discrete-time Networked Control Systems (NCSs) via delay-dependent Lyapunov-Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. A time-delay approach was introduced recently for continuous-time NCS under a weighted Try-Once-Discard (TOD) protocol in [12], where actuator saturation was not taken into account. In the present paper, we develop the time-delay approach for linear (probably, uncertain) discrete-time NCS under the weighted TOD protocol in the presence of actuator saturation. A novel Lyapunov-based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time-delay approach is illustrated on the example of a cart-pendulum system., QC 20131216

This paper deals with the solution bounds for discrete-time Networked Control Systems (NCSs) via delay-dependent Lyapunov-Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. A time-delay approach was introduced recently for continuous-time NCS under a weighted Try-Once-Discard (TOD) protocol in [12], where actuator saturation was not taken into account. In the present paper, we develop the time-delay approach for linear (probably, uncertain) discrete-time NCS under the weighted TOD protocol in the presence of actuator saturation. A novel Lyapunov-based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time-delay approach is illustrated on the example of a cart-pendulum system., QC 20131216

Queue overflow of a dynamic queue system gives rise to the information loss (or packet loss) in the communication buffer or the decrease of throughput in the transportation network. This paper investigates a stochastic optimal control problem for dynamic queue systems when imposing probability constraints on queue overflows. We reformulate this problem as a Markov decision process (MDP) with safety constraints. We prove that both finite-horizon and infinite-horizon stochastic optimal control for MDP with such constraints can be transformed as a linear program (LP), respectively. Feasibility conditions are provided for the finite-horizon constrained control problem. Two implementation algorithms are designed under the assumption that only the state (not the state distribution) can be observed at each time instant. Simulation results compare optimal cost and state distribution among different scenarios, and show the probability constraint satisfaction by the proposed algorithms., QC 20190319

This paper presents the formulation and analysis of a fully distributed dynamic event-triggered communication based robust dynamic average consensus algorithm. Dynamic average consensus problem involves a networked set of agents estimating the time-varying average of dynamic reference signals locally available to individual agents. We propose an asymptotically stable solution to the dynamic average consensus problem that is robust to network disruptions. Since this robust algorithm requires continuous communication among agents, we introduce a novel dynamic event-triggered communication scheme to reduce the overall inter-agent communications. It is shown that the event-triggered algorithm is asymptotically stable and free of Zeno behavior. Numerical simulations are provided to illustrate the effectiveness of the proposed algorithm., QC 20190305

In this paper, we consider the distributed optimization problem, whose objective is to minimize the global objective function, which is the sum of local convex objective functions, by using local information exchange. To avoid continuous communication among the agents, we propose a distributed algorithm with a dynamic event-triggered communication mechanism. We show that the distributed algorithm with the dynamic event-triggered communication scheme converges to the global minimizer exponentially, if the underlying communication graph is undirected and connected. Moreover, we show that the event-triggered algorithm is free of Zeno behavior. For a particular case, we also explicitly characterize the lower bound for inter-event times. The theoretical results are illustrated by numerical simulations., QC 20190305

The indirect approach to continuous-time system identification consists in estimating continuous-time models by first determining an appropriate discrete-time model. For a zero-order hold sampling mechanism, this approach usually leads to a transfer function estimate with relative degree 1, independent of the relative degree of the strictly proper real system. In this paper, a refinement of these methods is developed. Inspired by the indirect prediction error method, we propose an estimator that enforces a fixed relative degree in the continuous-time transfer function estimate, and show that the estimator is consistent and asymptotically efficient. Extensive numerical simulations are put forward to show the performance of this estimator when contrasted with other indirect and direct methods for continuous-time system identification., QC 20190305

We consider a lossless multi-terminal source coding problem with one transmitter, two receivers and side information. The achievable rate region of the problem is not well understood. In this paper, we characterise the rate region when the side information at one receiver is conditionally less noisy than the side information at the other, given this other receiver's desired source. The conditionally less noisy definition includes degraded side information and a common message as special cases, and it is motivated by the concept of less noisy broadcast channels. The key contribution of the paper is a new converse theorem employing a telescoping identity and the Csiszár sum identity., QC 20130219

This paper considers the precoder designs for successive zero-forcing dirty paper coding (SZF-DPC), a suboptimal transmission technique for MIMO broadcast channels (MIMO BCs). Existing precoder designs for SZF-DPC often consider a sum power constraint. In this paper, we address the precoder design for SZF-DPC with per-antenna power constraints (PAPCs), which has not been well studied. First, we formulate the precoder design as a rank-constrained optimization problem, which is generally difficult to handle. To solve this problem, we follow a relaxation approach, and prove that the optimal solution of the relaxed problem is also optimal for the original problem. Considering the relaxed problem, we propose a numerically efficient algorithm to find the optimal solution, which exhibits a fast convergence rate. Suboptimal precoder designs, with lower computational complexity, are also presented, and compared with the optimal ones in terms of achievable sum rate and computational complexity., QC 20130118