Automated Planning

A state is a complete snapshot of the world at a specific moment in time. In classical planning, it is typically represented as a set of logical propositions that are true.

• Initial State (S₀): The complete description of the world before any actions are taken. This is the planner's starting point.
• Goal State (S_g): A (usually partial) description of the desired world conditions. The planner's objective is to find actions that make this description true.
• The state space is the set of all possible states reachable from the initial state via actions.

An action is a discrete, instantaneous operator that transforms one state into another. Each action is formally defined by:

• Preconditions: A set of logical conditions that must be true in the current state for the action to be executable.
• Effects: The changes the action makes. These are typically split into:
  • Add List: Propositions that become true.
  • Delete List: Propositions that become false (in STRIPS-style planning).
• The set of all available actions defines the action space, which determines the branching factor of the search.

A plan is the output of the planning process: a sequence of actions ⟨a₁, a₂, ..., aₙ⟩ that, when executed in order from the initial state, is expected to produce a state satisfying the goal conditions.

• Valid Plan: A plan where the preconditions of each action aᵢ are satisfied in the state resulting from the execution of all preceding actions.
• Optimal Plan: A valid plan that minimizes a specified cost function (often the sum of individual action costs or the plan length).
• In contingent or probabilistic planning, a plan may be a policy (a mapping from states to actions) rather than a simple sequence.

The formal specification is cleanly separated into two parts:

• Planning Domain: The reusable 'physics' of the world. It defines the action schemas (with variables), predicates (properties of objects), and types for objects. It is independent of any specific scenario.
• Planning Problem: The specific instance to solve. It provides:
  1. The object declarations (the concrete entities in this instance).
  2. The initial state (the propositions true for these objects at the start).
  3. The goal specification (the desired conditions for these objects).

This separation, central to languages like PDDL, allows domain knowledge to be authored once and reused across countless problems.

The transition function (or dynamics model) is the formal mechanism that defines how the world evolves. Given a state s and an applicable action a, the function T(s, a) = s' deterministically yields the resulting successor state s'.

• In classical planning, this function is implicitly defined by the add/delete effects of actions.
• The frame problem is the challenge of efficiently specifying that all propositions not mentioned in an action's effects remain unchanged.
• In probabilistic planning (MDPs/POMDPs), the transition function is defined by a probability distribution P(s' | s, a) over possible successor states.

A cost function assigns a non-negative numerical cost c(s, a, s') to executing action a in state s, leading to s'. The cost of a plan is the sum of the costs of its constituent actions.

• The planner's objective is often to find a least-cost plan.
• A common simplification is unit cost, where each action costs 1, making plan length the metric to minimize.
• The Bellman equation provides the foundational recursive relationship for calculating optimal costs (values) in sequential decision-making under this function.

In games like chess, Go, and real-time strategy (RTS) games, AI agents plan sequences of moves to defeat an opponent. Monte Carlo Tree Search (MCTS) was famously used by AlphaGo to evaluate millions of potential future board states. In video games, non-player character (NPC) behavior is often driven by planners that decide between combat, retreat, or resource-gathering actions based on the game state. This requires efficient search in vast, adversarial state spaces.

Automated planning algorithms schedule and route resources at a massive scale. This includes:

• Vehicle Routing Problems (VRP): Planning delivery routes for fleets to minimize fuel and time.
• Job Shop Scheduling: Sequencing tasks on factory machines to maximize throughput.
• Air Traffic Control: Planning safe, efficient flight paths and landing sequences. These are often modeled as Constraint Satisfaction Problems (CSPs) or Temporal Planning problems, where actions have durations and resources are limited.

Autonomous software agents use planning to execute complex, multi-step business workflows. For example, an agent might plan the sequence of API calls needed to: 1. Query a database, 2. Process the data, 3. Generate a report, 4. Email it to stakeholders, 5. Log the action. HTN planning is particularly relevant here, as business processes are naturally hierarchical. This moves automation beyond simple scripts to systems that can dynamically adapt their plan if an API is unavailable or data is missing.

In clinical settings, planning can assist in creating personalized treatment regimens. This involves sequencing diagnostic tests, drug administrations, and therapies while respecting patient-specific constraints and medical guidelines. Contingent planning is critical, as the plan must branch based on test results (e.g., if biomarker X is present, administer drug Y; else, proceed to scan Z). Research systems also use planning for robotic-assisted surgery, where motion trajectories must be meticulously pre-computed and executed.

STRIPS (Stanford Research Institute Problem Solver) is the foundational formalism for representing classical planning problems. It defines:

• States as sets of logical propositions (facts).
• Actions with preconditions (facts that must be true to execute), add effects (facts made true), and delete effects (facts made false). This representation elegantly handles the frame problem by explicitly stating what changes, implicitly assuming all else remains unchanged. Most modern planning languages, like PDDL, are descendants of the STRIPS formalism.

PDDL (Planning Domain Definition Language) is the standardized, first-order logic-based language used to formally define planning problems for competition and research. It separates:

• Domain File: Declares types, predicates, and actions (with parameters, preconditions, and effects).
• Problem File: Defines specific objects, the initial state, and the goal state. By providing a common syntax, PDDL allows planners and domain models to be developed independently, fostering algorithmic advancement and benchmarking. It supports extensions for temporal planning, numeric fluents, and derived predicates.

A Markov Decision Process is a mathematical framework for modeling sequential decision-making under uncertainty. It is defined by:

• A set of states and actions.
• Transition probabilities: P(s' | s, a), the probability of moving to state s' after taking action a in state s.
• A reward function: R(s, a, s'), providing immediate feedback.
• A discount factor for future rewards. The solution to an MDP is an optimal policy (π: S → A) that maximizes expected cumulative reward. MDPs form the theoretical basis for reinforcement learning and probabilistic planning.

HTN Planning is a problem-solving method that uses domain-specific knowledge to decompose high-level tasks into networks of subtasks. Key components are:

• Compound Tasks: High-level, non-primitive activities (e.g., 'Travel to City').
• Primitive Tasks: Executable actions (e.g., 'Buy Ticket', 'Board Train').
• Methods: Recipes that decompose a compound task into a partially ordered set of subtasks. The planner recursively decomposes tasks until the plan consists solely of primitive actions. This approach is highly efficient for complex, structured domains like manufacturing, logistics, and military operations, as it heavily constrains the search space.

A heuristic function, h(n), estimates the cost from a given state to the goal. It is the intelligence that guides search algorithms like A*. Critical properties include:

• Admissibility: h(n) never overestimates the true cost to the goal. An admissible heuristic guarantees A* will find an optimal path.
• Consistency (Monotonicity): h(n) ≤ c(n, n') + h(n') for every successor n'. A consistent heuristic is also admissible. Common heuristics in planning are derived from solving a relaxed version of the problem (e.g., ignoring delete effects in the ignore-deletes heuristic) or identifying critical landmarks (facts that must be true in any solution).

Plan execution is the phase where a generated sequence of actions is dispatched to actuators. In dynamic environments, execution often fails due to unexpected events, necessitating plan repair (replanning).

• Monitoring: Continuously comparing expected vs. observed state.
• Replanning: Generating a new plan from the current, unexpected state. This can be a full re-invocation of the planner or a more efficient partial-plan repair.
• Contingent Planning: A proactive alternative that generates conditional plans (policy trees) specifying different actions for different possible observations during execution, making the agent robust to uncertainty.