The Efficiency Optimality Tradeoff in Automated Planning

This direction is split into other directions: optimality-efficiency trade-off. Its last version stays readable and citable here.

Version 1 of 191 papers95 conceptsfrozen 2026-10-04

In the ideal world of computer science, an algorithm finds the shortest path, the lowest cost, or the most efficient sequence of actions. But in the real world—where a robot must navigate a crowded warehouse or a chemist must synthesize a complex molecule—the search for the "absolute best" solution often leads to a computational explosion.

Across decades of research, a consistent theme has emerged: to solve complex problems in reasonable time, we must often abandon the search for the optimal solution in favor of a satisficing one. This research direction explores how to intentionally trade solution quality for computational speed, and how to bridge the resulting "optimality gap."

The Computational Burden of Perfection

The fundamental challenge in automated planning is the size of the search space. As Richard Fikes and Nils J. Nilsson observed in their foundational work on STRIPS, finding a valid sequence of actions is hard enough; proving that no shorter sequence exists requires an exhaustive search that is often mathematically intractable.

When an algorithm like A searches for an optimal path, it must expand every node that could potentially* be part of a better route. In high-dimensional spaces, such as those encountered in robotics, Nathan R. Sturtevant and colleagues note in Heuristic Search Comes of Age that this overhead is frequently prohibitive. The system spends so much time trying to save a few centimeters of travel that it fails to move at all.

Satisficing via Heuristics and Greed

To bypass this bottleneck, researchers use satisficing search. The intuition is simple: instead of exploring all promising branches, the algorithm follows a "greedy" heuristic that prioritizes reaching the goal as quickly as possible.

For example, in Surrogate Search As a Way to Combat Harmful Effects of Ill-behaved Evaluation Functions, William Cushing and his co-authors suggest decoupling the process of finding a solution from the process of proving its optimality. By using "size-based" metrics (how many steps to the goal) rather than "cost-based" metrics (how expensive those steps are), planners can skip complex cost-traps and find a functional solution in a fraction of the time.

Similarly, in multi-robot coordination, Ryan Luna and Kostas E. Bekris developed the Push and Swap algorithm. It prioritizes resolving topological conflicts (like two robots blocking a hallway) over finding the shortest coordinate-level path, allowing it to solve problems orders of magnitude faster than exhaustive solvers.

Speeding Up Through Abstraction

Another powerful way to trade optimality for speed is through abstraction. By grouping states together or creating "macro-operators," a planner can treat a complex sequence of moves as a single step.

Richard E. Korf demonstrated this with A Program That Learns to Solve Rubik's Cube. By learning sequences of moves that achieve subgoals without disturbing previous progress, the system could solve the cube rapidly. However, because these macros are rigid, the resulting solution is almost always longer than the theoretical minimum (God's Number).

This same logic applies to modern road navigation. Bing Liu showed in Using Knowledge to Isolate Search in Route Finding that by forcing a search to stay on major highways (a hierarchy), we can find a route 9x faster. The route might be slightly longer, but it is "good enough" for a human driver and much easier to compute.

In motion planning, the tradeoff is often between feasibility and smoothness. Algorithms like the Rapidly-exploring Random Tree (RRT), adapted for symbolic planning by Manuela Veloso in Adapting a Rapidly-Exploring Random Tree for Automated Planning, work by randomly sampling the environment.

This randomness is a feature, not a bug: it allows the robot to find a path through high-dimensional obstacles very quickly. However, the resulting path is often "jagged" or redundant. As Zhaoliang Zheng notes in the BTO-RRT paper, these initial solutions require a secondary "optimization pipeline" to prune unnecessary movements and make the path dynamically feasible.

Closing the Optimality Gap

If the initial search produces a suboptimal "satisficing" plan, how do we improve it? This has led to the subfield of plan optimization.

As surveyed by Pascal Bercher and Patrik Haslum in A Survey on Plan Optimization, the modern approach is often a two-stage process:

  1. Find a plan quickly using greedy heuristics, sampling, or abstractions.
  2. Post-process the plan to remove redundant actions, shorten the duration, or "smooth" the trajectory.

This "anytime" approach—where the system gives you a bad answer immediately and a better answer the longer you let it think—is the practical resolution to the efficiency-optimality tradeoff. It acknowledges that in most real-world applications, the most "optimal" thing an agent can do is find a workable solution before the clock runs out.

Papers in this version

Showing 60 of 91 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_efficiency_optimality_tradeoff_in_au_574db041,
  title = {The Efficiency Optimality Tradeoff in Automated Planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-efficiency-optimality-tradeoff-in-automated-planning/rdr_574db0415d8040008d7bfb6680357ba6},
  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_the_efficiency_optimality_tradeoff_in_au_574db041_v1,
  title = {The Efficiency Optimality Tradeoff in Automated Planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-efficiency-optimality-tradeoff-in-automated-planning/rdr_574db0415d8040008d7bfb6680357ba6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}