AI Glossary / Graphs and symbolic AI / Advanced

Ignore delete lists

Definition

Ignore delete lists is a relaxation of a classical planning problem in which actions retain their positive effects but lose their effects that make facts false. With positive preconditions and goals, achieved facts then remain available. Planners use this simplified problem to derive heuristics that help guide search in the original problem.

What it means

An action can both establish and remove facts. Using a resource might produce an output while making the resource unavailable.
Deleting those negative effects makes the model optimistic. A resource may remain available after use, or several location facts may accumulate. Those states need not be physically possible.
The original action model must still govern executable plans. Ignoring effects during heuristic calculation does not authorize ignoring them when a real action is selected or validated.

How it works

In a basic STRIPS-style representation, an action has preconditions, an add list, and a delete list. Its ordinary successor state removes delete-list facts and inserts add-list facts. The relaxed successor inserts the add-list facts without removing anything.
Assuming positive preconditions and goals, every original plan remains a valid relaxed plan with the same action costs. The relaxed problem may admit additional plans. Consequently, its optimal cost cannot exceed the original optimal cost when comparing the same nonnegative action costs.
The exact optimal relaxed-plan estimate is commonly called h-plus. Computing an optimal relaxed plan can still be computationally difficult, so practical planners use approximations. Their guarantees differ. Do not assume every estimate derived from delete relaxation is admissible merely because the exact relaxed optimum is a lower bound.
In particular, Fast Downward distinguishes its max heuristic from its additive and FF heuristics and documents their admissibility properties. Supported language features and implementation conditions also matter when transferring a theoretical claim to a particular planner.

Three practical examples

• Logistics planning: A heuristic estimates progress toward deliveries while ignoring some facts removed by movements. The real search must still respect where vehicles and packages actually are before loading or unloading.
• Shared equipment: A planner estimates how many actions might complete several jobs while temporarily ignoring resource consumption. Executable plans must include any required reset, replenishment, or return actions.
• Workflow search: A system uses relaxed reachability to prioritize promising states in a complex process. It still checks the original prerequisites and effects before claiming that a sequence is feasible for execution.

Think of it this way

Imagine estimating a project's minimum effort while temporarily pretending that using a shared tool never makes it unavailable. The estimate can help organize the search for a real plan. It cannot establish that everyone may use the same tool whenever they wish.

Worked example

Define a small planning task with initial fact Ready and goals DoneA and DoneB. There are three actions, each costing 1. No other actions or facts are available.
DoA requires Ready, adds DoneA, and deletes Ready. DoB requires Ready, adds DoneB, and deletes Ready. Reset requires DoneA, adds Ready, and deletes nothing. DoneA and DoneB remain true once established.
In the original task, DoA produces {DoneA}. DoB cannot immediately follow because Ready is false. Reset restores Ready, after which DoB produces {DoneA, DoneB}. The sequence DoA, Reset, DoB costs 3 and reaches the goal.
This is optimal: both DoA and DoB are necessary because each uniquely establishes one goal. After the first consuming action, Ready must be restored before the other can occur. The only restoring action is Reset, so at least three actions are required. Starting with DoB instead leads to a dead end because Reset requires DoneA.
Now ignore the delete lists. After DoA, the relaxed state is {Ready, DoneA}. DoB is immediately applicable and yields {Ready, DoneA, DoneB}. The relaxed plan costs 2. It is optimal in the relaxation because two distinct actions are still needed to establish the two goals.
Thus h-plus at the initial state is 2, while the real optimal cost is 3. The heuristic's optimistic value is useful information, but the two-action sequence is not executable in the original task.
Finally, remove Reset from the action set entirely. The original task becomes unsolvable: whichever job is performed first consumes Ready permanently. The relaxed task still has a two-action solution. This variation shows why solvability of the relaxed problem does not prove solvability of the original one.

Illustrative case study

Fictional Maple Planning uses a relaxed estimate to prioritize candidate equipment schedules. A reporting layer mistakenly displays the relaxed action sequence as a confirmed operational plan, omitting reset operations that the real equipment needs.
The team separates heuristic explanations from executable plans. Every proposed operational sequence is replayed against the original action definitions, checking prerequisites and effects after each step.
Reviewers add the shared-resource example to their checks. The revised workflow can benefit from optimistic planning estimates while detecting the exact point where a relaxed sequence would fail in the real model.

Common misconceptions and mistakes

“Ignore delete lists means remove preconditions.” Preconditions remain; the relaxation removes negative effects.
“A relaxed plan can always be executed.” It may depend on facts that the original actions would remove.
“Every relaxed heuristic is admissible.” Practical approximations have distinct properties.
“The relaxation makes optimal planning trivial.” Finding an optimal relaxed plan can still be hard.
“A relaxed solution proves the original task is feasible.” The no-Reset example disproves that implication.

Business use

Use the technique as part of a planner whose search objective and heuristic guarantees are understood. If optimality is required, check the actual heuristic and search configuration rather than relying on a broad description of relaxation.
Validate returned plans against the unmodified domain model. Pay attention to consumption, exclusivity, locations, and facts that actions invalidate. These are exactly the interactions that the relaxation can hide.

People also ask

Does the method erase facts from the actual system?

No. It changes a planning model used for estimation.

Can an unsolvable relaxed task have a solvable original task?

Under the stated relaxation assumptions, no: every original plan would also be a relaxed plan.

Why retain an optimistic estimate?

It can provide useful search guidance even though it is not a complete execution plan.

Check your understanding

Why does DoB fail immediately after DoA in the original task?

Answer: DoA deletes Ready.

Why does Reset disappear from the optimal relaxed plan?

Answer: Ready never becomes false there.

What happens when Reset is removed from the original task?

Answer: Both goals can no longer be achieved together.

Related terms

• Precondition
• Add list
• Delete list
• Heuristic
• Delete relaxation
• STRIPS
• admissibility
• relaxed plan

Learn next

Trace the original and relaxed fact sets after every action. Add another shared resource and examine which conflicts the relaxation hides and which positive prerequisites it still preserves.

More in Graphs and symbolic AI

• Hybrid architecture - A hybrid architecture is an agent design that combines different approaches to control, typically reactive behavior and deliberative planning.
• Identification in the limit - Identification in the limit is a criterion for learning success in which a learner eventually settles on a correct hypothesis and never changes it afterward.
• Identity uncertainty - Identity uncertainty is uncertainty about whether different observations, names, or records refer to the same underlying entity.
• Ignore preconditions heuristic - The ignore preconditions heuristic estimates remaining planning effort using a relaxed problem in which actions no longer require their original preconditions.
• Imitation learning - Imitation learning is a family of methods that learn how to perform a task from demonstrations of another agent's behavior.
• Imperfect information - Imperfect information is a condition in a game where a player making a decision cannot distinguish all relevant situations that may have occurred.

Sources

AIMA glossary, ignore delete lists: https://github.com/aimacode/aima-glossary/blob/master/glossary.md Jorg Hoffmann, Where Ignoring Delete Lists Works, research abstract: https://arxiv.org/abs/1109.5713 Fast Downward, evaluator properties and heuristic documentation: https://www.fast-downward.org/HEAD/documentation/search/Evaluator/

Previous: Ignorability Next: Ignore preconditions heuristic