Goal-oriented Compression with a Constrained Decoder

Consider an agent/decoder placed at a fixed vertex of a known directed weighted graph. The controller/encoder observes the location of a target placed at another random vertex of the graph, and its goal is to help the agent to reach this target with the minimal total cost, dictated by the weights of the edges traversed on the way. The encoder can transmit only a limited number of bits to the decoder at each step of the algorithm. Our goal is to identify the optimal trade-off between the available communication budget and the average total cost. We formulate this problem as a goal-oriented compression problem with decoder constraints, which generalizes classical lossless compression problems. We show that this problem is in general NP-complete, and construct several suboptimal algorithms for solving it in polynomial-time with bounds on their suboptimality gap. We also show a lower bound on the expected cost for any coding scheme, assuming unit cost for each transition.