Generating Qualitatively Diverse Plans

34 concepts26 papers1 proposal

Standard automated planning typically focuses on a single goal: finding the most optimal sequence of actions to achieve a target state. Whether minimizing time, fuel, or computational cost, classical planners excel at finding a single, highly efficient path.

However, when deployed in the real world, this single-minded focus on optimality becomes a liability. Real-world environments are riddled with unmodeled constraints, shifting human preferences, and unexpected physical obstacles. If a planner provides only one "perfect" solution, and that solution is blocked by an unforeseen real-world hurdle, the system fails entirely.

To build resilient, collaborative systems, researchers have shifted their focus toward qualitative plan diversity. The goal is not just to find a solution, but to generate a portfolio of high-quality, structurally distinct alternatives that allow humans, robots, and machine learning models to pivot when conditions change.

The Illusion of Choice in Top-k Planning

A naive approach to generating multiple options is top-k planning, which finds the $k$ cheapest or fastest plans for a given task. While computationally rigorous, top-k planning frequently suffers from structural redundancy.

Imagine planning a driving route from New York to Boston. The optimal plan takes the highway. The second-best plan might take the exact same highway but involve a single lane change two miles earlier. The third-best might swap the order of turning on the radio and fastening the seatbelt. As David Speck 0001 et al. demonstrate, top-k algorithms often produce sets of plans that differ only by the permutation of independent actions. If the highway is completely closed due to an accident, all $k$ plans fail simultaneously because they lack true strategic variety.

For human decision-makers, this lack of variety makes automated assistants frustratingly rigid. Early work by Andrew Gelman et al. in financial resource management highlighted that planners must present diverse strategic paths to help managers navigate judgmental, non-quantifiable constraints. David E. Smith 0001 formalizes this by framing planning as an iterative, interactive process. In complex missions like planetary exploration, providing a set of qualitatively diverse plans allows human operators to explore the trade space between competing goals and resource constraints, capturing nuances that cannot easily be encoded into a mathematical cost function.

The Mechanics of Qualitative Diversity

To generate plans that are both useful and distinct, a planner must balance two competing forces: quality (keeping costs low) and distance (maximizing structural or semantic differences between plans).

   Low Distance (Redundant)             High Distance, High Quality (Diverse)
        [ Start ]                             [ Start ]
       /         \                           /         \
  (Action A)   (Action B)               (Highway)     (Train Route)
       \         /                           \         /
        [ Goal ]                              [ Goal ]

To achieve this, algorithms must explicitly optimize for distance metrics rather than just path costs. Michael Katz et al. developed a framework using top-quality planners and Mixed Integer Linear Programming (MILP) to find sets of plans that are mathematically guaranteed to be both high-quality and significantly different from one another.

Another powerful mechanism is post-generation filtering. Instead of forcing the planner to find diversity natively, a system can generate a large volume of candidate paths using an efficient top-k planner and then group them using hierarchical clustering. As shown by Shirin Sohrabi et al. in enterprise risk management, this strategy filters out redundant permutations and distills hundreds of raw plans into a limited set of distinct, representative "what-if" scenarios for decision-makers.

Robustness Against the Unmodeled World

In robotics and reinforcement learning (RL), qualitative diversity is not just a convenience for humans—it is a core mechanism for physical survival and efficient exploration.

When a robot operates in a physical space, its high-level task planner relies on low-level skill models (such as trajectories for pouring or grasping). If these skill models only provide a single optimal parameter set, the robot will get stuck if an environmental obstacle blocks that specific path. Zi Wang et al. address this by integrating diversity-aware sampling directly into Task and Motion Planning (TAMP). By generating a wide variety of valid candidate parameters for a skill, the robot can seamlessly navigate around physical obstructions that block the primary execution path.

Similarly, sample-based planners operating in continuous or massive discrete action spaces struggle if they evaluate actions based on average expected value alone. Zaheen Farraz Ahmad et al. introduced a "marginal utility" objective for training action generators. Instead of optimizing for the single best action, this objective explicitly rewards the added value of each new candidate action in a shortlist. This forces the generator to propose a diverse set of candidates spanning different regions of the action space, preventing the planner from getting trapped in local optima.

In exploratory RL, executing a single optimal path based on an incomplete environment model can lead to repetitive failures. Sarath Sreedharan et al. demonstrate that generating a set of distinct candidate plans based on a learned symbolic model allows an agent to explore sparse-reward environments far more effectively. When the agent tries multiple, structurally diverse plans, it is highly likely to encounter informative failures. These failures provide the exact data needed to prune incorrect assumptions from the agent's internal model.

Powering LLM Planners and Diagnostics

The necessity of qualitative diversity extends directly into modern Large Language Model (LLM) planning frameworks and diagnostic systems.

When LLMs are used to generate multi-step task plans, prompting them for a single sequential output makes them fragile to execution errors. To fix this, Yao Mu et al. introduced Tree-Planner, which samples multiple potential plans upfront and organizes them into an "action tree" for closed-loop execution. The authors note that the performance of such selection-based frameworks is fundamentally bounded by the diversity of the initial samples; if the generated plans lack sufficient variety, the system cannot recover when an obstacle invalidates the primary branch.

A parallel approach by Zikang Tian et al. generates a diverse pool of candidate "planning programs" (Python code) rather than raw text strings, using a reinforcement-learning-tuned selector to choose the best execution path on the fly.

                  [ LLM / Generator ]
                     /      |      \
             [Plan A]    [Plan B]   [Plan C]  <- Must be qualitatively diverse!
                     \      |      /
                 [ Selection Mechanism ]
                            |
                     [ Executed Path ]

Finally, qualitative diversity is critical for diagnostic tasks like plan recognition and hypothesis exploration. When a system tries to infer an actor's hidden goals from noisy or missing sensor data, multiple distinct explanations may be equally plausible. Shirin Sohrabi et al. demonstrate that combining top-k and diverse planning algorithms to sample the solution space ensures broad coverage of the search space.

As Shirin Sohrabi argues, providing a multi-hypothesis portfolio rather than a single guess transforms automated planning from a rigid execution engine into an explainable, robust tool for complex real-world reasoning.

Key Foundational Work

Generating Qualitatively Different Plans through Metatheoretic Biases (1999) — contributed 3 concept elements to this direction.
FRM: An Intelligent Assistant for Financial Resource Management (1988) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_diverse_plan_generation_f5b9bd1f,
  title = {diverse plan generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-plan-generation/rdr_f5b9bd1f3a52443582251dfb00e322e9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_diverse_plan_generation_f5b9bd1f_v1,
  title = {diverse plan generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-plan-generation/rdr_f5b9bd1f3a52443582251dfb00e322e9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake