AI · Knowledge, reasoning, and planning

11 · Automated Planning

Planning searches for a sequence of actions that transforms an initial state into a goal state. Watch a simple shortest-path planner use actions with preconditions and effects.

Plans as action sequences

11.1 Definition of Classical Planning

A classical problem specifies an initial state, a goal, and actions whose preconditions and effects define state transitions; actions are usually deterministic and fully observable.

11.2 Algorithms for Classical Planning

Search can proceed forward through reachable states or backward from the goal. Planning representations such as STRIPS make action preconditions and add/delete effects explicit.

11.3 Heuristics for Planning

Relaxed problems—often ignoring negative effects—yield estimates of remaining work that guide search toward promising states.

11.4 Hierarchical Planning

High-level tasks can be decomposed into smaller subtasks until executable primitive actions remain.

11.5 Planning and Acting in Nondeterministic Domains

When actions have multiple possible outcomes, a plan may need branches that condition later actions on observations.

11.6 Time, Schedules, and Resources

Temporal planners account for action durations, deadlines, concurrency, and limited resources—not only ordering.

11.7 Analysis of Planning Approaches

Planning methods trade off expressiveness and computational cost; domain structure and uncertainty determine which approach is suitable.

Key terms and BFS trace

A planning state is a configuration; the goal test says when it is solved. An action model specifies preconditions and effects. BFS uses a FIFO frontier and expands by increasing number of actions, so the first discovered route is shortest when every move has equal cost. A heuristic estimates remaining cost; this demo does not use one.

Trace: start at the upper-left cell; expand open neighbors and mark each cell seen when it enters the queue, recording its parent once. Expanding one distance layer before the next prevents longer routes from being accepted first. On reaching the goal, follow parent links backward to the start and reverse that chain to obtain the action sequence.

This is deterministic, fully observable, unit-cost grid planning with static walls. Real-time schedules, uncertain outcomes, resource limits, or hierarchical task decomposition need richer state/action models and different algorithms.

Interactive planner

Navigate to a goal

Each move has a precondition (the destination is open) and effect (the agent changes cell). Breadth-first search finds a shortest route around walls.

Goal

Start at the green cell; walls are impassable.

Planner complexity

Let V be the number of open grid cells and E the legal neighbor links; BFS visits each cell at most once and checks each link a constant number of times. The queue uses a head index (not repeated front-removal), and each cell has at most four neighbors. Let N be all displayed cells, including walls.

Search time: O(V + E); on this fixed-degree grid E = O(V), so O(V). Auxiliary space: O(V) for queue, seen set, and parent map. The returned plan is output storage O(L), where L ≤ V is its move count. Playback redraws all N cells per action, so its UI work is O(L·N) overall (and the grid DOM is O(N)); the search itself remains O(V + E). Here the board is 5×5 and walls are fixed. Bounds assume unit-cost moves and expected O(1) Set/Map operations.