# A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions

arXiv: https://arxiv.org/abs/2208.04220 · HTML: https://mlsanity.com/paper/2208.04220/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 8 Aug 2022.

## Builds on (most cited first, 6 of 6)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Anytime Stereo Image Depth Estimation on Mobile Devices](https://mlsanity.com/paper/1810.11408/) (2018)
- [The deterministic information bottleneck](https://mlsanity.com/paper/1604.00268/) (2016)
- [Information-Theoretic Abstractions for Planning in Agents with Computational Constraints](https://mlsanity.com/paper/2005.09611/) (2020)
- [Reduced Complexity Multi-Scale Path-Planning on Probabilistic Maps](https://mlsanity.com/paper/1602.04800/) (2016)
- [Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming](https://mlsanity.com/paper/2102.10015/) (2021)

## Built on by (most cited first, 1 of 1)

- [Communication-aware Hierarchical Map Compression of Time-Varying Environments for Mobile Robots](https://mlsanity.com/paper/2504.10751/) (2025)

## Abstract (arXiv)

In this chapter, an integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, environment abstractions for resource-constrained autonomous agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically, the information bottleneck (IB) method, to pose an abstraction problem as an optimal encoder search over the space of multi-resolution trees. The abstractions emerge in a task-relevant manner as a function of agent information-processing constraints. We detail our formulation, and show how hierarchical tree structures, signal encoders, and information-theoretic methods for signal compression can be unified under a common theme. A discussion delineating the benefits and drawbacks of our formulation is presented, as well as a detailed explanation how our approach can be interpreted within the context of generating abstractions for resource-constrained autonomous systems. It is shown that the resulting information-theoretic abstraction problem over the space of multi-resolution trees can be formulated as a integer linear programming (ILP) problem. We demonstrate the approach on a number of examples, and provide a discussion detailing the differences of the proposed framework compared to existing methods. Lastly, we consider a linear program relaxation of the ILP problem, thereby demonstrating that multi-resolution information-theoretic tree abstractions can be obtained by solving a convex program.