Tracking and Control of Gauss–Markov Processes over Packet-Drop Channels with Acknowledgments

Anatoly Khina, Victoria Kostina, Ashish Khisti, Babak Hassibi

Abstract

This paper investigates the problem of tracking the state of Gauss-Markov processes over rate-limited, erasure-prone communication links. We demonstrate that in the limit of many independent processes, a "greedy" quantization strategy—optimizing for the lowest possible error at the current moment—is globally optimal, eliminating the tension between current and future Mean Square Error (MSE). We further address the challenge of delayed acknowledgments by framing it as a problem of compression with side information, showing that a one-unit delay in feedback results in only a marginal loss in tracking performance. Finally, we demonstrate the practical application of these results to single-process tracking using variable-length coding and to Linear Quadratic Gaussian (LQG) control frameworks.

Introduction

In networked control and sensing systems, tracking the state of dynamic processes over digital communication links is a fundamental challenge. These links are typically characterized by limited bandwidth and are susceptible to packet drops. A core question in this field is whether an observer should prioritize immediate accuracy or preserve resources for future tracking. This paper explores these trade-offs for Gauss-Markov processes, which are standard mathematical models for systems where the next state depends on the current state plus random noise.

System Model

System model for tracking multiple Gauss–Markov processes over a rate-limited channel. Source, p. 3

System model for tracking multiple Gauss–Markov processes over a rate-limited channel.

The system architecture consists of an observer/encoder that monitors $N$ independent Gauss-Markov processes. These states are mapped into finite-rate packets of $N R_t$ bits and transmitted over an erasure-prone link to a state estimator/decoder. The estimator's goal is to track the processes with zero delay and minimum mean square error (MMSE). The observer receives acknowledgments (ACKs) upon successful packet arrival, which may be instantaneous or delayed.

Optimality of Greedy Quantization

A significant finding of this research is the "optimality of greed" in the large-frame limit (tracking many processes simultaneously). The authors prove that there is no trade-off between current and future performance; a strategy that minimizes current distortion is optimal for all future time steps. This leads to a fundamental recursive formula for the minimum achievable distortion ($D^*_t$):

$$D^*_t = (\alpha^2_t D^*_{t-1} + W_t) 2^{-2R_t}$$

This result simplifies encoder design, as it removes the need for complex temporal optimization strategies.

Handling Delayed Acknowledgments

When acknowledgments are delayed, the observer faces uncertainty regarding the estimator's current state. The authors resolve this by mapping the problem to Kaspi-based compression with side information. In this framework, the most recent (potentially lost) packets serve as side information known to the observer but only occasionally known to the estimator. This approach allows the observer to encode packets robustly, and numerical results indicate that the performance gap between instantaneous and one-unit delayed ACKs is surprisingly small.

Single-Process Tracking and LQG Control

For scenarios involving only a single process, the paper shows that variable-length coding techniques, specifically Entropy-Coded Dithered Quantization (ECDQ), can achieve performance within a small gap of the multi-process theoretical bounds. These tracking insights are directly applicable to discrete-time scalar LQG control. The authors derive new bounds for optimal control costs, demonstrating that their proposed coding schemes significantly outperform naive strategies that do not account for the specific structure of the erasure channel.

Conclusion and Future Work

This work establishes that greedy quantization is a globally optimal strategy for tracking multiple Gauss-Markov processes over unreliable links. While the results for one-unit ACK delays are promising, extending this to longer delays remains an open problem due to the complexities of multi-option side information in information theory. Future research will also look toward extending these scalar results to high-dimensional vector plants and exploring performance under non-Gaussian noise distributions.

Summary updated

Abstract

We consider the problem of tracking the state of Gauss-Markov processes over rate-limited erasure-prone links. We concentrate first on the scenario in which several independent processes are seen by a single observer. The observer maps the processes into finite-rate packets that are sent over the erasure-prone links to a state estimator, and are acknowledged upon packet arrivals. The aim of the state estimator is to track the processes with zero delay and with minimum mean square error (MMSE). We show that, in the limit of many processes, greedy quantization with respect to the squared error distortion is optimal. That is, there is no tension between optimizing the MMSE of the process in the current time instant and that of future times. For the case of packet erasures with delayed acknowledgments, we connect the problem to that of compression with side information that is known at the observer and may be known at the state estimator-where the most recent packets serve as side information that may have been erased, and demonstrate that the loss due to a delay by one time unit is rather small. For the scenario where only one process is tracked by the observer-state estimator system, we further show that variable-length coding techniques are within a small gap of the many-process outer bound. We demonstrate the usefulness of the proposed approach for the simple setting of discrete-time scalar linear quadratic Gaussian control with a limited data-rate feedback that is susceptible to packet erasures.
BibTeX
@article{khina2019tracking,
  author = {Anatoly Khina and Victoria Kostina and Ashish Khisti and Babak Hassibi},
  title = {{Tracking and Control of Gauss–Markov Processes over Packet-Drop Channels with Acknowledgments}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2019},
  doi = {10.1109/tcns.2018.2850225},
}
Figure