State Space

A state space is formally defined as a directed graph (S, A, T), where:

• S is the finite or countably infinite set of all possible states.
• A is the set of actions available to an agent.
• T: S × A → S is the deterministic transition function, mapping a state and action to a resulting successor state.

In non-deterministic or stochastic environments, T becomes a probability distribution over successor states: T: S × A → Δ(S). The initial state s0 ∈ S and the set of goal states G ⊆ S complete the planning problem specification.

The size and connectivity of a state space are primary drivers of planning complexity.

• Dimensionality: The number of independent variables defining a state. A robot's state might be defined by its (x, y, θ) pose, while a logistics problem's state could be defined by the locations of hundreds of packages. Dimensionality directly impacts the cardinality of S, which is often exponential in the number of variables.
• Branching Factor: The average number of distinct successor states reachable from a given state via a single action. A high branching factor (e.g., many possible moves in a game of Go) causes combinatorial explosion, making exhaustive search intractable and necessitating heuristic guidance.

A critical distinction exists between fully and partially observable environments.

• State (Fully Observable): In a Markov Decision Process (MDP), the agent has direct access to the true, complete state s_t. Planning and search operate directly on S.
• Belief State (Partially Observable): In a Partially Observable MDP (POMDP), the agent receives only observations. The true state is hidden. The agent must maintain a belief state b_t, which is a probability distribution over S representing its knowledge. The state space for planning thus becomes the belief space, which is continuous and infinitely larger, even for finite S.

The topology of the state graph determines solvability.

• Connectedness: A state space is connected if there exists a path between any two states. Many real-world problems have disconnected components, meaning some states are unreachable from the initial state, which can simplify search.
• Dead-End States: These are states from which no sequence of actions can lead to a goal state. Identifying dead ends early (e.g., using landmark analysis) is crucial for efficient planning, as it prevents wasteful exploration of futile paths.

To manage complexity, state spaces are abstracted.

• State Abstraction: Groups concrete states into abstract states based on shared relevant features. For example, all states where a package is in any truck might be grouped into a single abstract state "package in transit." This creates a smaller, more tractable abstract state space for high-level planning.
• Hierarchical Decomposition: Used in Hierarchical Task Network (HTN) Planning, where the high-level state space is defined by compound tasks, which are recursively decomposed into smaller sub-spaces of primitive actions. This constrains search to domain-sensible paths.

Intelligent search requires estimating distance to the goal.

• Heuristic Function h(s): A function that estimates the cost from state s to the nearest goal. Effective heuristics (like relaxed plan heuristics or landmark heuristics) exploit the structure of the state space to guide algorithms like A*.
• Landmarks: These are necessary facts that must be true at some point in any valid plan (e.g., "the robot must be at the charging station before its battery is full"). The order in which landmarks must be achieved imposes a structure on the state space, creating a skeleton that guides the search.

The action space is the complete set of primitive operations an agent can execute to transition between states within a state space. In formal planning, each action is defined by:

• Preconditions: Logical conditions that must be true in the current state for the action to be applicable.
• Effects: The changes the action makes, specified as add lists (propositions made true) and delete lists (propositions made false). The size and structure of the action space directly determine the branching factor of the state space graph, impacting the complexity of search.

A heuristic function, denoted h(n), provides an estimated cost from a given state to a goal state. It is crucial for efficiently navigating large state spaces by guiding search algorithms toward promising regions.

• Admissible Heuristics: Never overestimate the true cost to the goal. Used in optimal algorithms like A Search*.
• Domain-Specific vs. General: Heuristics can be hand-crafted using domain knowledge (e.g., Manhattan distance for grid navigation) or automatically derived (e.g., using a relaxed planning problem). Effective heuristics are the primary method for combating the combinatorial explosion inherent in state space search.

A Markov Decision Process is a mathematical framework for modeling sequential decision-making under uncertainty. It formalizes a state space with stochastic outcomes.

• Core Components: A set of states, an action space, transition probabilities P(s' | s, a), and a reward function R(s, a, s').
• Policy: A mapping from states to actions that defines the agent's behavior, optimized to maximize cumulative reward.
• Contrast with Classical Planning: Unlike deterministic planning, MDPs account for the probabilistic nature of action effects, requiring optimization over expected outcomes rather than finding a single path.

A Partially Observable Markov Decision Process extends the MDP framework to scenarios where the agent cannot directly perceive the true state. Instead, it receives observations that provide noisy clues.

• Belief State: The agent maintains a probability distribution over all possible states, which becomes the new 'state' for planning.
• Significantly Harder: Planning in POMDPs operates in the continuous space of belief states, making exact solutions intractable for most problems. Approximation techniques are essential. This model is critical for real-world robotics and dialogue systems where sensors are imperfect.

Forward search is the most intuitive planning paradigm. The search begins at the initial state, applies all applicable actions to generate successor states, and continues exploring forward through the state space graph until a goal state is reached.

• Algorithms: Includes breadth-first search, depth-first search, and informed variants like Greedy Best-First and A*.
• Challenge: The forward branching factor can lead to an exponentially growing frontier. Effective heuristics are required to prune the search tree. This approach is also known as progression planning.

Backward search, or regression planning, inverts the search direction. It starts from the goal state and applies the inverse of actions to find predecessor states, searching backward until the initial state is reached.

• Regression: For a goal G and an action A, the regressed state is the set of preconditions of A, plus any goals in G not achieved by A's effects.
• Advantage: Can be more efficient than forward search when the goal description is concise but the initial state is complex, as it only considers relevant actions. This approach systematically reduces the goal into subgoals.