The Markov decision process, the standard framework for sequential decision making under uncertainty, assumes a perfectly rational agent: one with unlimited time and computation, able to process all the information available to it and compute the optimal policy unhindered. Real agents are not like this, and neither are biological ones, which are very good at finding solutions that are not globally optimal but are good enough given the constraints they operate under. This project replaces the perfectly rational agent with a bounded-rational one by charging the decision process for the information it must process. Concretely, we constrain the Kullback-Leibler divergence between the agent’s posterior policy and a given prior policy: the further the posterior has to move from the prior, the more expensive it is to compute, while the prior itself can encode what the agent already knows about the task or the environment. A single trade-off parameter sets how resource-limited the agent is, and as that parameter grows without bound one recovers the deterministic solution of the original, unconstrained problem. Cast this way, the problem is the rate-distortion problem of information theory in another guise, which is what makes it tractable.
A grid world makes the effect concrete. The environment below admits two representations, a coarse one and a fine one, and the agent carries a suite of sensors that lets it toggle between them. It must therefore decide not only how to move from the start state to the goal, but which description of the world to use, the coarser one being cheaper. An agent with a small resource parameter navigates on the abstraction; one with a large parameter pays for the finest-resolution sensor and goes after the globally optimal path.
Two-level representation of a stochastic grid world. The start state is shaded gray, obstacle states red and the goal state green.
The same principle settles where the abstraction should come from in the first place. Earlier work generally assumed the abstractions were given, or were built in some manner fixed beforehand, and took no account of what the agent could actually afford to process. We instead pose abstraction generation itself as an optimization problem: given an occupancy grid, compress it into a multi-resolution quadtree that preserves as much information about cell occupancy as possible, with the degree of compression set by the same non-negative trade-off parameter. Two algorithms solve the resulting problem, with guarantees. The abstractions that emerge refine the regions carrying the most relevant information first, leave uniform regions coarse, and approach the original grid as the parameter grows; the parameter therefore acts as a rationality knob, with less capable agents settling on simpler, lower-cardinality descriptions of the world. Introducing a non-uniform distribution over the state space, which costs the framework and the algorithms nothing, makes the abstraction region-specific, so that only the neighborhood the agent cares about is refined and the rest of the map stays compressed. This line of work is described here.
We then used these abstractions to reduce the cost of path planning itself, so that the agent’s time and computational limits enter the planning problem directly rather than being imposed on it after the fact. Each quadtree carries an associated graph on which a path can be planned. Because occupancy grids encode obstacles probabilistically, feasibility is defined through a threshold , with smaller values yielding a more conservative agent, and path feasibility is folded into the cost function so that an agent can decide whether a path is feasible from knowledge of its cost alone. Planning on a sequence of trees of increasing resolution then produces a sequence of paths whose cost decreases monotonically toward the cost of a path planned in the unabstracted environment, which places the scheme alongside anytime algorithms: a coarse answer is available immediately and improves as the agent spends more. The figures below show this on a 6464 occupancy grid. At the coarsest setting the path cuts through vertices flagged as -obstacles and is not -feasible; as the trade-off parameter grows the graph refines, the path becomes feasible, and its cost falls toward that of the finest-resolution solution. The details are in our RA-L paper.
Tree, graph and path for at , , and (left to right, top to bottom). Orange vertices are -obstacles; the path in the first panel traverses one and is therefore not -feasible.
The same accounting carries over to settings with more than one decision-maker. In a pursuit-evasion game the two players rarely hold a common description of the world, although the classical equilibrium notions assume they do; we therefore studied Nash and correlated equilibria for pursuit-evasion games played under a lack of common knowledge, where each player reasons with its own abstraction of the state. Charging each player for the information its policy consumes gives bounded-rational versions of these games, in which each player’s resource parameter sets how sharply it plays and the perfectly rational game is recovered in the limit. The entropy regularization that makes the single-agent problem tractable also makes the game easier to learn: approximating entropy-regularized policies yields a practical method for learning Nash equilibria in zero-sum stochastic games, and, for very large populations of agents, the same regularization lets a designer shape the collective behavior of the population through mean-field games.
When several agents plan at once, each with its own multi-resolution view of the environment, the abstractions themselves become the thing to coordinate. The MAMS-A* algorithm searches over the multi-scale representations held by a team of agents, so that each agent can plan on its own coarse description of the world while drawing on the finer information held by the others, and the team recovers a solution of the quality that the best available description supports without any single agent having to carry the full-resolution map.
Planning across levels of a multi-resolution representation. The region outlined in magenta is held at a finer resolution, and the grey lines mark the correspondence between vertices at the two levels.
Finally, the same reasoning applies below the planning layer. In a linear quadratic-Gaussian problem whose measurements must pass through a quantizer before reaching the controller, the controller and the quantizer can be synthesized together and the quantizer switched over time, so that a limited channel between sensing and control is spent where it does the control cost the most good.
Sponsors
This work has been sponsored by ONR, NSF, and ARL.