Automated Planning: Teaching AI to Think in Action Sequences

In lesson 7, we treated the nurse-scheduling problem as a constraint satisfaction problem: the question was whether one complete assignment could satisfy every rule at once. In this lesson, the question changes again. Now we are not merely assigning values to variables. We are choosing an ordered sequence of actions that changes the world step by step until a goal becomes true.

That distinction matters in real hospital workflow. A patient cannot be admitted before a diagnosis is confirmed. A diagnosis cannot be confirmed before the right evidence exists. A lab cannot be ordered until the patient has been assessed enough to justify it. The quality of the final plan therefore depends not only on which actions appear, but on when they appear and what each action makes possible afterward.

This is the domain of automated planning. Planning asks how an AI system can move from the current state of the world to a desired future state by reasoning explicitly about preconditions, action effects, and goal satisfaction.

One planning term appears early in this lesson: goal regression means reasoning backward from the goal by asking which earlier subgoals would have to be true for the final goal-achieving action to become possible.

Core learnings about planning and STRIPS

• Planning represents intelligent behavior as action sequences that transform one world state into another.
• STRIPS models each action using preconditions, add effects, and delete effects, making state change explicit.
• Forward planning searches from the current world state toward the goal, while backward planning regresses the goal into required subgoals.
• Planning extends earlier search lessons by adding structured action semantics: not every successor state is arbitrary; it is produced by a specific action with requirements.

Planning as a state-transition problem

Earlier in the course, we studied search over paths, optimization over landscapes, and assignments under constraints. Planning keeps the search perspective, but it changes what is being searched. Instead of arbitrary nodes or candidate configurations, the planner reasons over world states and the actions that move between them.

A classical planning action is often written as:

$$a = (Pre(a), Add(a), Del(a))$$

This says that every action $a$ has three pieces:

• $Pre(a)$: the facts that must already be true before the action is allowed
• $Add(a)$: the facts made true by performing the action
• $Del(a)$: the facts made false by performing the action

In the triage workflow, take the action AdmitPatient. Its preconditions are things like diagnosis confirmed and bed available. Its add effect is patient admitted. Its delete effect might be bed available, because that bed is no longer free after the patient uses it.

The state update rule is then:

$$s' = (s \setminus Del(a)) \cup Add(a), \qquad \text{valid only if } Pre(a) \subseteq s$$

Here, $s$ is the current set of true facts and $s'$ is the next state after action $a$. In this lesson’s example, $s$ might contain patient present, vitals recorded, and symptom history. If we execute OrderLabs, then $Add(a)$ contributes lab-results-ready once the simplified action completes, and $Del(a)$ is empty. So the formula says: remove anything the action invalidates, add anything the action creates, and only do that if the preconditions are already in the current state. In the end, this tells us whether the action sequence is actually executable, not just intuitively plausible.

If set notation is unfamiliar, pause here and revisit Function notation for AI.

Why action order matters

The defining challenge in planning is not simply choosing useful actions. It is choosing them in a valid order. Many actions are individually reasonable but impossible in the wrong sequence.

In the triage domain, AdmitPatient is not a medical insight; it is an operational commitment. It only makes sense after evidence has been gathered, the diagnosis is supported, and hospital capacity exists. If the planner tries to admit before the diagnosis is confirmed, it violates the action’s preconditions. If it tries to confirm the diagnosis before labs are ready, that action also fails. Planning therefore turns informal workflow knowledge into executable logic about what must happen first.

This is why planning is more structured than the search problems in lessons 4 and 5. Search asked which path looked promising. Planning asks which action is legal now, what new facts it creates, and how that changes the space of possible next steps. The branching structure is not arbitrary; it is constrained by the semantics of the domain.

Forward planning, backward planning, and heuristics

There are two natural ways to plan. Forward planning begins with the current state and applies any action whose preconditions already hold. It behaves like the search algorithms from lessons 4 and 5: the planner expands successor states until one satisfies the goal. In hospital triage, this means starting from facts like patient present, vitals recorded, and symptom history, then asking which actions are executable now.

Backward planning, also called goal regression, begins at the goal and reasons in reverse. If the goal is Admit Patient, the planner asks which action could make that true. That action introduces new subgoals such as Diagnosis Confirmed and Bed Available. Each of those subgoals can be regressed again until the planner reaches facts that are already true. This is the planning analogue of the backward reasoning we saw in lessons 2 and 3, but now each subgoal stands for an action requirement rather than a static rule condition.

Large planning problems still need guidance. One common heuristic idea is to solve a relaxed problem where delete effects are ignored. In that easier world, facts accumulate and never disappear, so the planner can estimate how many actions remain to achieve the goal. That estimate is not the final answer, but it is often informative enough to guide search efficiently.

Exploring goal regression in the triage planner

The visualization below shows the planning problem as a goal-regression tree. Instead of drawing every possible state transition, it shows the subgoals that must be satisfied for admission to become possible.

The key idea is to connect the planning formula directly to what you see. Each leaf in the tree is a fact that belongs to the current state $s$. Each internal node is a larger subgoal that depends on those facts. When a fact is present in the selected scenario, you can think of it as satisfying part of $Pre(a)$ for some action later in the plan. When enough leaves are present to prove the higher node, the planner has established the preconditions needed for the next action. So the visualization tells us not only which facts matter, but also which action becomes executable once those facts are in place.

Walkthrough: Regressing the admission goal

Use the visualization once with the Waiting on labs scenario:

1. Keep the mode on Backward and click Run. The planner starts from Admit Patient and asks which subgoals must be true first.
2. Watch the tree expand into Diagnosis Confirmed and Bed Available. These are the practical components of the action preconditions for the final admission step.
3. Notice that Bed Available can still be proven because the triage facts are present, but Diagnosis Confirmed fails when the planner reaches Lab Results Ready.
4. Compare this with the Ready for admission scenario. There, all needed leaf facts are already true, so the full goal can be proven.
5. Finally, try No bed available. Diagnosis succeeds, but the plan still fails because the operational precondition for admission is missing.

What this means in practice: planning does not fail because the goal is conceptually wrong. It fails because at least one necessary precondition for the final action sequence is still missing. That is exactly what the STRIPS formulas above are designed to make explicit.

Relation to earlier lessons

1. Lesson 4 introduced search over states. Planning keeps that search perspective, but the successor states now come from legal actions with explicit preconditions and effects.
2. Lesson 5 added heuristic guidance. Planning still benefits from heuristics, but the heuristic now estimates remaining goal requirements rather than geometric or path cost distance.
3. Lesson 7 focused on satisfying a final assignment all at once. Planning instead spreads the problem across time, because later states depend on earlier actions.

Concrete bridge: in lesson 7 we asked, “Is there a consistent final assignment?” In this lesson we ask, “Which ordered actions make that final state true?”

Notation quick reference

Symbol	Meaning	Detailed Explanation
$a$	one action schema	Planning as a state-transition problem
$Pre(a)$	facts required before action $a$	Planning as a state-transition problem
$Add(a)$	facts made true by action $a$	Planning as a state-transition problem
$Del(a)$	facts made false by action $a$	Planning as a state-transition problem
$s$	current world state	Planning as a state-transition problem
$s'$	next world state after an action	Planning as a state-transition problem
$\subseteq$	is a subset of / is fully contained in	Planning as a state-transition problem
$\cup$	set union, meaning “add these facts”	Planning as a state-transition problem
$\setminus$	set difference, meaning “remove these facts”	Planning as a state-transition problem

Concept deep dives

• Function notation for AI
• Big-O growth intuition for search

What comes next

In lesson 9, we pivot from hand-crafted action models to machine learning. Instead of writing preconditions and effects ourselves, we begin studying systems that infer useful mappings directly from data.

Next: Post 9, Introduction to Machine Learning

---

References and Further Reading

• Fikes, R.E. and Nilsson, N.J. “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence 2(3-4), 1971.
• Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020. Chapter 11.
• Ghallab, M., Nau, D., and Traverso, P. Automated Planning and Acting. Cambridge University Press, 2016.
• Blum, A. and Furst, M. “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence 90(1-2), 1997.

---

This is Lesson 8 of 18 in the AI Starter Course.