Comprehensive Study Guide for University AI Planning and Formalisms

Fundamentals of Planning in Artificial Intelligence

• Definition of Planning: Planning is the task of coming up with a sequence of actions that will achieve a goal. It involves an agent taking advantage of the structure of a problem to construct complex plans of action.
• Core Objective: Transitioning from an initial state to a goal state using an expressive yet carefully constrained language for representing problems, environments, actions, and states.

Classical Planning Environments

• Environment Constraints: Classical planning focuses exclusively on environments that meet five criteria:     * Fully Observable: The agent has complete access to the state of the environment at all times.     * Deterministic: Every action has a single, certain outcome.     * Finite: There are a limited number of actions and states.     * Static: The environment does not change except when the agent performs an action.     * Discrete: Actions and states are distinct and well-defined.
• Non-Classical Planning: This field deals with partially observable or stochastic environments and requires different sets of algorithms and agent designs.

Limitations of Standard Problem-Solving Agents

• State-Space Search Difficulties: Standard search algorithms (like Depth-First Search or $A^*$) face specific hurdles in planning:     * Irrelevant Actions: Ordinary agents can be overwhelmed by actions that do not contribute to the goal.     * Heuristic Challenges: Finding a good heuristic function to guide the search is difficult for general problems.     * Efficiency: Standard solvers often fail to take advantage of problem decomposition (splitting a large problem into independent sub-problems).

The Language of Planning: STRIPS

• Balancing Expressivity and Efficiency: The goal is to find a language expressive enough for various problems but restrictive enough for efficient algorithmic processing.
• STRIPS (Stanford Research Institute Problem Solver): A basic representation used for classical planners.
• State Representation:     * Planners decompose the world into logical conditions.     * States are represented as a conjunction of positive literals.     * Propositional Literals: e.g., $\text{poor} \wedge \text{unknown}$.     * First-Order Literals: e.g., $\text{At}(\text{Plane1}, \text{Melbourne}) \wedge \text{At}(\text{Plane2}, \text{Sydney})$.     * Constraints: Literals in first-order state descriptions must be ground (no variables) and function-free (e.g., $\text{At}(\text{Father}(\text{Fred}), \text{Sydney})$ is prohibited).
• Closed-World Assumption: In STRIPS, any condition not explicitly mentioned in a state is assumed to be false.
• Goal Representation:     * A goal is a partially specified state, represented as a conjunction of positive ground literals (e.g., $\text{Rich} \wedge \text{Famous}$).     * A state $s$ satisfies a goal $g$ if $s$ contains all atoms in $g$. For example, $\text{Rich} \wedge \text{Famous} \wedge \text{Miserable}$ satisfies the goal $\text{Rich} \wedge \text{Miserable}$.

Action Schemas and Implementation

• Action Specification: Defined by two primary components:     1. Preconditions (PRECOND): Conditions that must hold for the action to be executable.     2. Effects (EFFECT): Results that occur after the action is executed.
• Example Action: Flying a plane     * Action: $\text{Fly}(p, \text{from}, \text{to})$     * PRECOND: $\text{At}(p, \text{from}) \wedge \text{Plane}(p) \wedge \text{Airport}(\text{from}) \wedge \text{Airport}(\text{to})$     * EFFECT: $\neg \text{At}(p, \text{from}) \wedge \text{At}(p, \text{to})$
• Action Schema: These general templates use variables ($p$, $\text{from}$, $\text{to}$) to represent classes of actions.
• State Transitions: Starting in state $s$, the resulting state $s'$ is identical to $s$ except:     * Any positive literal $P$ in the effect is added to $s'$.     * Any negative literal $\neg P$ in the effect is removed from $s'$.
• Add and Delete Lists: Systems often divide effects into an "add list" (positive literals) and a "delete list" (negative literals) to improve reliability.

The Frame Problem and Extensions

• The Frame Problem: The difficulty of formally specifying every non-effect of an action (everything that stays the same). Listing all unaffected aspects is computationally expensive and complicates reasoning.
• STRIPS Assumption: Solves the frame problem by assuming everything not explicitly affected by an action remains unchanged.
• Frame Axioms: Logical statements that explicitly declare what does not change.
• Ramification Problem: The complexity of secondary consequences (e.g., if a plane flies, the people and cargo inside also move).
• Qualification Problem: The difficulty of representing every circumstance that could cause an action to fail.

Expressiveness: ADL vs. STRIPS

• ADL (Action Description Language): A more expressive variant of STRIPS.
• Comparison of Features:     * States: STRIPS uses only positive literals; ADL allows positive and negative literals (e.g., $\neg \text{Rich} \wedge \neg \text{Famous}$).     * World Assumption: STRIPS uses Closed World (unmentioned = false); ADL uses Open World (unmentioned = unknown).     * Goal Representation: STRIPS requires ground literals; ADL allows quantified variables (e.g., $\exists x \, \text{At}(\text{P1}, x) \wedge \text{At}(\text{P2}, x)$).     * Goal Logic: STRIPS uses conjunctions; ADL allows conjunctions and disjunctions (e.g., $\neg \text{Poor} \wedge (\text{Famous} \vee \text{Smart})$).     * Effects: ADL supports conditional effects (e.g., "when $P : E$" means effect $E$ occurs only if $P$ is satisfied).     * Equality/Types: ADL has built-in equality predicates ($x=y$) and typed variables (e.g., $p: \text{Plane}$), which STRIPS lacks.
• PDDL (Planning Domain Definition Language): A standard syntax that systemizes various formalisms, allowing researchers to share benchmark problems for STRIPS and ADL.

Planning Examples: Air Cargo and Blocks World

• Air Cargo Domain:     * Initial State: $\text{At}(\text{C1, SFO}) \wedge \text{At}(\text{C2, JFK}) \wedge \text{At}(\text{P1, SFO}) \wedge \text{At}(\text{P2, JFK}) \wedge \dots$     * Goal: $\text{At}(\text{C1, JFK}) \wedge \text{At}(\text{C2, SFO})$     * Action Load: $\text{PRECOND: At}(c, a) \wedge \text{At}(p, a) \dots \text{EFFECT: } \neg \text{At}(c, a) \wedge \text{In}(c, p)$     * Action Unload: $\text{PRECOND: In}(c, p) \wedge \text{At}(p, a) \dots \text{EFFECT: At}(c, a) \wedge \neg \text{In}(c, p)$     * Action Fly: $\text{PRECOND: At}(p, \text{from}) \dots \text{EFFECT: } \neg \text{At}(p, \text{from}) \wedge \text{At}(p, \text{to})$     * Solution Plan: $\text{[Load(C1, P1, SFO), Fly(P1, SFO, JFK), Load(C2, P2, JFK), Fly(P2, JFK, SFO)]}$
• Blocks World Domain:     * Initial State: $\text{On(A, Table)} \wedge \text{On(B, Table)} \wedge \text{On(C, Table)} \wedge \text{Clear(A)} \wedge \text{Clear(B)} \wedge \text{Clear(C)}$.     * Goal: $\text{On(A, B)} \wedge \text{On(B, C)}$.     * Actions: $\text{Move}(b, x, y)$ and $\text{MoveToTable}(b, x)$.

State-Space Search Strategies

• Forward State-Space Search (Progressive Planning):     * Moves from the initial state toward the goal.     * Initial state is the planning problem's starting state.     * Goal test checks if a sequence reaches the goal state.     * Step cost is typically $1$ in STRIPS.     * Drawback: Often inefficient due to the irrelevant action problem; bogs down without high-quality heuristics.
• Backward State-Space Search (Regression Planning):     * Starts from the goal and works backward to the initial state.     * Advantage: Focuses only on relevant actions (actions that achieve a desired goal literal).     * Consistency: An action must achieve a desired literal and must not undo any other desired literal.

Heuristics for State-Space Search

• Goal Representation: Planning languages allow derivation of heuristics directly from problem specifications.
• Approaches to Deriving Heuristics:     1. Relaxed Problems: Solve a simplified version of the problem to get an admissible heuristic (one that never overestimates).     2. Subgoal Independence Assumption: Assume the cost of solving a conjunction of subgoals is the sum of costs for each subgoal independently.
• Specific Relaxations:     * Ignore Preconditions: Every action is applicable in every state. Any single goal fluent can be achieved in $1$ step. This relates to the set-cover problem.     * Ignore Delete Lists: Removing negative literals from effects makes reaching a goal easier. However, the state-space size remains massive (e.g., $10^{100}$ states).
• State Abstraction: Mapping many ground states to a single abstract state (e.g., ignoring specific fluents).     * Example: In a cargo problem with $50$ planes and $200$ packages across $10$ airports, there are $\approx 10^{155}$ states. Reducing package locations to $5$ airports reduces the space to $\approx 10^{17}$ states.
• Decomposition:     * Dividing a set of fluents $G$ into disjoint subsets $G_1, …, G_n$.     * Max Heuristic: $\max_i \text{Cost}(P_i)$ is always admissible but often too low.     * Sum Heuristic: $\sum_i \text{Cost}(P_i)$ is more accurate but not always admissible. It is valid if subgoals are truly independent (effects of plan $P_i$ do not change preconditions/goals of $P_j$).

Partial-Order Planning (POP)

• Philosophy: Unlike total order planning (linear sequences), POP allows flexibility in action ordering.
• Least Commitment Strategy: Delaying choices about action ordering during the search to avoid making fixed decisions too early.
• Decomposition Advantage: POP can work on several subgoals independently and then combine the subplans.
• Components of a Partial-Order Plan:     1. Set of Actions: The steps making up the plan.     2. Ordering Constraints: Noted as $A < B$, meaning action $A$ must occur sometime before action $B$. Cycles (e.g., $A < B$ and $B < A$) are contradictions.     3. Causal Links: Noted as $A \xrightarrow{p} B$, read as "$A$ achieves $p$ for $B$."     4. Open Preconditions: Preconditions not yet achieved by an action in the plan.
• POP Algorithm Consistency: A plan is a solution if it is consistent (no cycles, no causal link conflicts) and has no open preconditions.

Planning Graphs and GraphPlan

• Definition: A planning graph is an approximation of a complete tree of all possible actions and results, used to reduce search or as a source of heuristics.
• Structure: Organized into alternating levels:     * Level $S_i$: Nodes representing fluents (atomic facts) that could hold at time $i$.     * Level $A_i$: Nodes representing ground actions whose preconditions could be satisfied at time $i$.
• Persistence Actions (No-ops): Represent a fluent's truth being preserved from $S_i$ to $S_{i+1}$.
• Mutex (Mutual Exclusion): Constraints indicating that elements cannot exist or occur together (depicted by red semicircles).
• Mutex Conditions for Actions:     1. Inconsistent Effects: One action negates an effect of another (e.g., $\text{Eat(Cake)}$ negates $\text{Have(Cake)}$).     2. Interference: An effect of one action negates a precondition of another.     3. Competing Needs: The preconditions of two actions are mutually exclusive.
• Mutex Conditions for Fluents: Inconsistent support (all ways of achieving two fluents at a level are mutually exclusive).
• The GRAPHPLAN Algorithm:     1. Create an initial planning graph.     2. Check if all goals are present and non-mutex in the latest level.     3. If yes, try to extract a solution.     4. If extraction fails or goals aren't met, expand the graph to the next level.     5. Continue until a solution is found or it is determined that no solution is possible.

Detailed Example: Cake Problem and Spare Tire Problem

• Cake Problem:     * Init: $\text{Have(Cake)}$     * Goal: $\text{Have(Cake)} \wedge \text{Eaten(Cake)}$     * Actions: $\text{Eat(Cake)}$ (Effect: $\neg \text{Have(Cake)} \wedge \text{Eaten(Cake)}$), $\text{Bake(Cake)}$ (Precond: $\neg \text{Have(Cake)}$, Effect: $\text{Have(Cake)}$).
• Spare Tire Problem (ADL Representation):     * Init: $\text{At(Flat, Axle)} \wedge \text{At(Spare, Trunk)}$     * Goal: $\text{At(Spare, Axle)}$     * Action $\text{Remove(Spare, Trunk)}$: Precond $\text{At(Spare, Trunk)}$; Effect $\neg \text{At(Spare, Trunk)} \wedge \text{At(Spare, Ground)}$.     * Action $\text{PutOn(Spare, Axle)}$: Precond $\text{At(Spare, Ground)} \wedge \neg \text{At(Flat, Axle)}$; Effect $\text{At(Spare, Axle)} \wedge \neg \text{At(Spare, Ground)}$.     * Action $\text{LeaveOvernight}$: Effectively negates all locations for cargo and planes.