Can a delete list be empty?

Yes, if the modeled action makes no represented fact false.

What if a deleted fact is already absent?

Removing it makes no additional change to the set.

Why do some planning heuristics ignore delete lists?

Doing so creates a relaxed problem that can help guide search; a relaxed solution is not automatically executable in the original problem.

AI Glossary / Graphs and symbolic AI / Advanced

Delete list

Definition

A delete list is the set of facts that an action makes false in a STRIPS-style planning model. When the action is applied, those facts are removed from the current state. The delete list works alongside preconditions, which determine applicability, and an add list, which specifies facts made true.

What it means

Planning is not simply accumulating achievements. An action can establish one condition while undoing another. Moving a cart to a loading bay makes its new location true and its previous location false. A planner must represent both effects to avoid reasoning from an impossible situation.
The word “delete” concerns the current model of the world. It does not mean erasing historical records, destroying an object, or deleting a file from a computer. A system can retain an action history while removing an outdated fact from the state used to plan the next step.
This entry uses the classical planning sense of the term, rather than a general list of items marked for deletion.

How it works

In a simple propositional STRIPS model, a state is a set of true facts. Facts absent from that state are treated as false. An applicable action transforms state S into (S minus its delete list) union its add list. Facts unaffected by either list persist.
An action schema can contain variables; applying a concrete instance supplies specific objects. The resulting effects must refer to those objects consistently. Preconditions and delete effects serve different roles: a condition can be required without being removed, or removed without being an explicit precondition.
The action model must capture relevant changes. The update formula cannot repair a missing effect or an incorrect assumption about what the action does.

Three practical examples

Warehouse movement: Moving trolley T from storage to packing removes At(T, Storage) and adds At(T, Packing). Other trolleys remain where they were. Omitting the delete effect would leave the planner treating T as available at both places.
Equipment allocation: Assigning a portable scanner removes Available(Scanner) and adds Assigned(Scanner, TeamA). Returning it can reverse those conditions through a separate action. Correct effects help prevent a later plan from allocating the same modeled resource twice.
Document workflow: Submitting a draft can remove Editable(Draft) and add UnderReview(Draft), if that matches the actual workflow. A reviewer-return action can restore editability. These are modeled status changes, not instructions to erase the document or its revision history.

Think of it this way

Think of a board showing which room each meeting kit currently occupies. Moving a kit requires taking down its old location marker as well as placing the new marker. Keeping both markers would mislead the next person arranging a meeting. A separate movement log can preserve where the kit used to be.

Worked example

Consider an invented planning problem with one scanner and two teams. The initial state is S0 = {Available(S), Needs(A), Needs(B), Charged(S)}.
Define Assign(S, A) with preconditions Available(S) and Needs(A). Its delete list is {Available(S)} and its add list is {Assigned(S, A)}. Applying it produces S1 = {Needs(A), Needs(B), Charged(S), Assigned(S, A)}.
There are still four facts, but they are not the same four. Charged(S) persists because the modeled assignment does not change charge. Needs(A) also remains: assigning equipment does not mean the team's work is finished.
Assign(S, B) requires Available(S), which is absent from S1, so it is not applicable. If the first action's delete list were mistakenly empty, Available(S) would remain and the planner could assign the scanner to both teams.
Now define Return(S, A) to require Assigned(S, A), delete that fact, and add Available(S). It restores availability, after which assignment to B becomes possible. This small model deliberately omits travel, charging changes, and task completion; adding those realities requires additional conditions and effects.

Illustrative case study

Fictional Willow Facilities builds a planner for shared presentation kits. Its initial demonstration produces short schedules, but a reviewer notices that a kit is booked into two rooms without a transfer or return step.
The team traces the problem to an assignment action that adds a room booking while leaving the kit's availability fact unchanged. They correct the delete list, then inspect related actions for similar omissions. Tests include booking a kit twice, returning it before a second booking, and attempting a return from the wrong room.
The corrected model rules out that particular inconsistency. It does not establish that real staff will follow the schedule or that every operational constraint is modeled. Execution monitoring remains necessary. This is an illustrative case, not evidence of a measured productivity improvement.

Common misconceptions and mistakes

“Delete effects are preconditions.” Preconditions govern when an action can occur; delete effects describe changes afterward.
“Every precondition is consumed.” Many required conditions remain true.
“Deleting a fact destroys the object.” It changes the planning state, not necessarily the physical object or historical record.
“Unlisted effects happen automatically.” Relevant changes must be represented by the model.
“An omitted fact always means unknown.” In the simple closed-world state representation used here, it means false.

Business use

Review action models against realistic operational transitions. For each action, ask what becomes true, what ceases to be true, and what should remain unchanged. Pay particular attention to exclusive resources, locations, permissions, and workflow statuses.
Test short counterexamples as well as successful plans. A two-action sequence may reveal double allocation more clearly than a large demonstration. Keep model validation separate from execution verification: a valid symbolic plan can still fail if the actual environment differs from its assumptions.

Check your understanding

Why is assignment to B blocked after assignment to A?

Answer: The first action removes the required availability fact.

Why does Charged(S) remain true?

Answer: Neither effect list changes it.

Does returning the scanner complete either team's work?

Answer: Not in the defined model.

Related terms

Add list
Precondition
Action schema
Classical planning
Frame problem
STRIPS
state transition
delete relaxation

Learn next

Model a shared resource with assignment and return actions. Write every intermediate state and check whether an invalid double assignment is possible. Then add one operational constraint and revise the action effects accordingly.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Planning chapter: https://aima.cs.berkeley.edu/newchap11.pdf Carnegie Mellon University, AI Planning, Execution, and Learning, STRIPS representation and closed-world assumptions: https://www.cs.cmu.edu/~mmv/planning/schedule.html

Previous: Delaunay triangulation Next: Deletion Anomaly