In the field of automated planning, most problems are theoretically NP-hard or PSPACE-hard. Yet, in practice, many human-designed benchmarks and real-world tasks are solved almost instantly by simple search algorithms. This gap between theoretical gloom and practical success is explained by a structural property called planning width.
Research led by Blai Bonet and Hector Geffner has shown that the difficulty of a planning problem is not just a result of its "physics" (the rules of the environment), but a function of its representation. By identifying the right features, we can collapse the search space of a complex problem into a small, manageable "width" that can be navigated in polynomial time.
The Intuition: Novelty-Based Search
Standard search algorithms like Breadth-First Search (BFS) explore every possible state. In a world with $n$ variables, this leads to an exponential explosion. However, the Iterative Width (IW) algorithm uses a different pruning criterion: novelty.
A state is considered "novel" if it makes a small set of features take on a combination of values that has never been seen before in the current search. An algorithm like $IW(k)$ only expands states that are novel for a tuple of $k$ features.
- $IW(1)$ only cares if a single feature (e.g., "Is the door open?") changes to a new value.
- $IW(2)$ cares if a pair of features (e.g., "Am I in the kitchen?" AND "Is the light on?") reaches a new joint configuration.
As Wilmer Bandres, Blai Bonet, and Hector Geffner demonstrated in Planning With Pixels in (Almost) Real Time, this approach allows agents to play Atari games by looking at raw pixels. Instead of exploring the astronomical state space of a video game, the planner only explores states that provide "new" visual information, making real-time planning possible.
Width is Not Fixed
A crucial insight from General Policies, Representations, and Planning Width is that width is not an immutable property of a domain. If a problem has a high width, it might simply be because the features used to describe it are poor.
Imagine trying to solve a Rubik's Cube. If your only feature is "the entire configuration of the cube," the width is massive. But if you have features representing "the number of correctly placed corners" or "the orientation of the top cross," the problem's width collapses. By adding derived features that capture the logic of the task, we can reduce the width of a domain to a small constant, typically $k=1$ or $k=2$. This ensures the problem is solvable in polynomial time relative to the number of features.
The Link to General Policies
Why do so many benchmarks have low width? Bonet and Geffner argue in General Policies, Subgoal Structure, and Planning Width that low width is a formal consequence of the existence of general policies.
A general policy is a strategy that works across different instances of a domain (e.g., a single strategy to solve any Sokoban level). If a general policy can be described using only a few variables, then the planning width of that domain is bounded by that same small number. Essentially, if a problem is "easy" for a human to describe with a simple rule of thumb, it is "easy" for a width-based search to solve.
Policy Sketches: Guiding the Search
To exploit this structure, researchers introduced policy sketches. As detailed in Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches by Dominik Drexler, Jendrik Seipp, and Hector Geffner, sketches are a minimalist language used to define subgoals.
A sketch doesn't tell the agent exactly what to do; it identifies which features should change and in what order. This decomposes a high-width problem into a sequence of low-width subproblems. By following these "breadcrumbs," algorithms like $SIW_R$ can solve complex domains that previously required exhaustive search.
Learning the Representation
While classical planning relies on human-provided features, recent work has moved toward learning them. In Deep Policies for Width-Based Planning in Pixel Domains, Miquel Junyent and Anders Jonsson showed that neural networks can learn feature representations that specifically aim to reduce search width. By mapping high-dimensional states (like pixels) into a space where the goal is reachable via low-order novelty, the network simplifies the "topology" of the search, allowing simple planners to solve deep, multi-step tasks.
Summary
The theory of planning width shifts our focus from the size of the state space to the logical complexity of the strategy.
- Width measures how many features must be tracked simultaneously to guarantee progress.
- Representation determines width; better features make problems easier.
- General Policies and Sketches provide the theoretical and practical tools to decompose hard problems into low-width, polynomial-time fragments.
By understanding width, we move away from "blind" search and toward a structural understanding of what makes a problem computationally tractable.