Overview

Imagine you're planning a cross-country road trip with multiple stops, budget constraints, and time limitations. You don't just jump in the car and drive randomly—you break down the big goal (reach your destination) into smaller, manageable tasks: plan the route, book accommodations, budget for gas, identify interesting stops along the way. You consider different path options, compare their trade-offs, and create a step-by-step plan.

This is exactly what AI agents do through planning algorithms. While ReAct patterns allow agents to think and act iteratively, many complex tasks require systematic decomposition and strategic planning before execution. Planning algorithms give agents the ability to look ahead, consider multiple options, and construct optimal sequences of actions to achieve their goals.

Learning Objectives

After completing this lesson, you will be able to:

• Understand different types of planning problems and when to use each approach
• Implement search-based planning algorithms (BFS, DFS, A*)
• Build hierarchical task networks for complex planning scenarios
• Choose appropriate planning algorithms based on problem characteristics
• Integrate planning algorithms with agent architectures

The Nature of Planning Problems

From Actions to Plans

Single Action: "Calculate 15% of $1,250" Simple Sequence: "Find a restaurant, make a reservation, get directions" Complex Plan: "Plan a week-long vacation within budget, considering weather, activities, and logistics"

Planning becomes essential when:

• Tasks have multiple steps with dependencies
• Actions have preconditions and effects
• Resources are limited and must be allocated efficiently
• Multiple paths exist to achieve the goal
• Mistakes are costly and should be avoided

Planning Complexity Visualization

Types of Planning Problems

<ComparisonTable defaultValue='{"title": "Planning Problem Types", "columns": ["Type", "Environment", "Information", "Agents", "Example"], "data": [ ["Classical", "Deterministic", "Complete", "Single", "Puzzle solving, file organization"], ["Temporal", "Time-dependent", "Complete", "Single", "Project scheduling, manufacturing"], ["Hierarchical", "Layered goals", "Partial", "Single", "Software development, research"], ["Multi-Agent", "Distributed", "Partial", "Multiple", "Team coordination, supply chain"], ["Probabilistic", "Uncertain", "Incomplete", "Single", "Robot navigation, medical diagnosis"] ], "highlightRows": [0, 2]}' />

Classical Planning: Deterministic world, complete information, single agent

• Example: Solving a puzzle, organizing files, scheduling meetings

Temporal Planning: Actions have durations, deadlines matter

• Example: Project management, manufacturing workflows

Hierarchical Planning: Complex tasks decomposed into subtasks

• Example: Software development, research projects, event planning

Multi-Agent Planning: Multiple agents must coordinate

• Example: Team projects, distributed systems, supply chain management

Search-Based Planning Algorithms

State Space Search Foundation

Planning can be viewed as searching through a space of possible states to find a path from the initial state to the goal state.

from typing import List, Dict, Any, Optional, Set, Tuple from dataclasses import dataclass from abc import ABC, abstractmethod import heapq from collections import deque

@dataclass class State: """Represents a state in the planning problem""" variables: Dict[str, Any] # State variables and their values

def __hash__(self):
    # Make state hashable for use in sets
    return hash(tuple(sorted(self.variables.items())))

def __eq__(self, other):
    return isinstance(other, State) and self.variables == other.variables

def copy(self) -> 'State':
    return State(self.variables.copy())
Copy

@dataclass class Action: """Represents an action in the planning domain""" name: str preconditions: Dict[str, Any] # What must be true to execute effects: Dict[str, Any] # What changes after execution cost: float = 1.0 # Cost of executing this action

Copy
def is_applicable(self, state: State) -> bool:
    """Check if action can be executed in given state"""
    for var, value in self.preconditions.items():
        if state.variables.get(var) != value:
            return False
    return True

def apply(self, state: State) -> State:
    """Apply action to state, returning new state"""
    if not self.is_applicable(state):
Show all 15 lines

@dataclass class PlanStep: """A step in a plan""" action: Action state_before: State state_after: State step_number: int

class PlanningProblem: """Defines a planning problem"""

Copy
def __init__(self, initial_state: State, goal_conditions: Dict[str, Any], actions: List[Action]):
    self.initial_state = initial_state
    self.goal_conditions = goal_conditions
    self.actions = actions

def is_goal_state(self, state: State) -> bool:
    """Check if state satisfies goal conditions"""
    for var, value in self.goal_conditions.items():
        if state.variables.get(var) != value:
            return False
Show all 15 lines

class SearchNode: """Node in the search tree"""

Copy
def __init__(self, state: State, parent: Optional['SearchNode'] = None, 
             action: Optional[Action] = None, path_cost: float = 0.0):
    self.state = state
    self.parent = parent
    self.action = action  # Action that led to this state
    self.path_cost = path_cost
    self.depth = 0 if parent is None else parent.depth + 1

def get_path(self) -> List[PlanStep]:
    """Reconstruct path from root to this node"""
Show all 26 lines

class PlannerBase(ABC): """Base class for planning algorithms"""

Copy
def __init__(self, problem: PlanningProblem):
    self.problem = problem
    self.nodes_expanded = 0
    self.max_depth = 0

@abstractmethod
def search(self) -> Optional[List[PlanStep]]:
    """Search for a plan"""
    pass
Show all 23 lines

`} language="python" />

Breadth-First Search Planning

BFS guarantees finding the shortest plan (optimal in terms of number of steps):

class BreadthFirstPlanner(PlannerBase): """Breadth-First Search planner - guarantees optimal solution"""

Copy
def search(self) -> Optional[List[PlanStep]]:
    """BFS search for shortest plan"""
    if self.problem.is_goal_state(self.problem.initial_state):
        return []  # Already at goal
    
    frontier = deque([SearchNode(self.problem.initial_state)])
    explored = set()
    
    while frontier:
        node = frontier.popleft()
Show all 19 lines

Example: Simple Blocks World Problem

def create_simple_blocks_example(): """Create a simple blocks world planning problem"""

Copy
# Initial state: A on Table, B on A
initial_state = State({
    'on(A)': 'Table',
    'on(B)': 'A',
    'clear(A)': False,
    'clear(B)': True,
    'arm_empty': True
})

# Goal: B on Table, A on B
Show all 40 lines

Test BFS planning

problem = create_simple_blocks_example() bfs_planner = BreadthFirstPlanner(problem) bfs_plan = bfs_planner.search()

print("BFS Planning Result:") print("=" * 30) if bfs_plan: print(f"Found plan with {len(bfs_plan)} steps:") for i, step in enumerate(bfs_plan): print(f"{i+1}. {step.action.name}") print(f"Nodes expanded: {bfs_planner.nodes_expanded}") else: print("No plan found") `} language="python" />

A* Search Planning

A* uses heuristics to guide the search more efficiently:

class AStarPlanner(PlannerBase): """A* search planner - optimal with admissible heuristic"""

Copy
def __init__(self, problem: PlanningProblem, heuristic_func):
    super().__init__(problem)
    self.heuristic = heuristic_func

def search(self) -> Optional[List[PlanStep]]:
    """A* search using f(n) = g(n) + h(n)"""
    frontier = []
    heapq.heappush(frontier, (0, 0, SearchNode(self.problem.initial_state)))
    explored = set()
    frontier_states = {}  # state -> (f_cost, node)
Show all 39 lines

Heuristic functions

def blocks_world_heuristic(state: State, goal: Dict[str, Any]) -> float: """Count number of blocks not in correct position""" misplaced = 0 for var, target_value in goal.items(): if state.variables.get(var) != target_value: misplaced += 1 return misplaced

def manhattan_heuristic(state: State, goal: Dict[str, Any]) -> float: """Manhattan distance heuristic for grid-based problems""" if 'robot_x' in state.variables and 'robot_y' in state.variables: current_x = state.variables.get('robot_x', 0) current_y = state.variables.get('robot_y', 0) goal_x = goal.get('robot_x', current_x) goal_y = goal.get('robot_y', current_y) return abs(goal_x - current_x) + abs(goal_y - current_y) return 0

Compare BFS vs A*

print("Algorithm Comparison:") print("=" * 40)

Test A*

astar_planner = AStarPlanner(problem, blocks_world_heuristic) astar_plan = astar_planner.search()

print(f"BFS: {len(bfs_plan) if bfs_plan else 0} steps, {bfs_planner.nodes_expanded} nodes expanded") print(f"A*: {len(astar_plan) if astar_plan else 0} steps, {astar_planner.nodes_expanded} nodes expanded")

if astar_plan: print(f"\nA* Plan:") for i, step in enumerate(astar_plan): print(f"{i+1}. {step.action.name}") `} language="python" />

Hierarchical Task Networks (HTN)

When problems become very complex, flat planning becomes inefficient. Hierarchical Task Networks break down abstract tasks into more concrete subtasks.

from typing import Union, List, Dict, Any from dataclasses import dataclass from enum import Enum

class TaskType(Enum): PRIMITIVE = "primitive" # Directly executable action COMPOUND = "compound" # Needs decomposition

@dataclass class Task: """Represents a task in HTN planning""" name: str task_type: TaskType parameters: Dict[str, Any] = None

def __post_init__(self):
    if self.parameters is None:
        self.parameters = {}
Copy

@dataclass class Method: """Method for decomposing compound tasks""" name: str task: str # Which compound task this method decomposes preconditions: Dict[str, Any] subtasks: List[Task] # Ordered list of subtasks

def is_applicable(self, state: State) -> bool:
    """Check if method can be applied in current state"""
    for var, value in self.preconditions.items():
        if state.variables.get(var) != value:
            return False
    return True
Copy

class HTNPlanner: """Hierarchical Task Network planner"""

Copy
def __init__(self, actions: List[Action], methods: List[Method]):
    self.actions = {action.name: action for action in actions}
    self.methods = methods
    self.decomposition_trace = []

def plan(self, initial_state: State, tasks: List[Task]) -> Optional[List[Action]]:
    """Plan using HTN decomposition"""
    self.decomposition_trace = []
    return self._plan_recursive(initial_state, tasks, [])
Show all 41 lines

Example: Travel Planning with HTN

def create_travel_planning_example(): """Create a hierarchical travel planning problem"""

Copy
# Primitive actions
actions = [
    Action(
        name='book_flight',
        preconditions={'have_money': True, 'have_destination': True},
        effects={'have_flight': True, 'have_money': False},
        cost=500
    ),
    Action(
        name='pack_bags',
Show all 85 lines

Test HTN planning

actions, methods = create_travel_planning_example() htn_planner = HTNPlanner(actions, methods)

Test international vacation

initial_state = State({ 'have_money': True, 'have_clothes': True, 'have_id': True, 'have_internet': True, 'vacation_type': 'international' })

tasks = [Task('plan_vacation', TaskType.COMPOUND)]

print("HTN Travel Planning:") print("=" * 30)

plan = htn_planner.plan(initial_state, tasks)

if plan: print(f"Found plan with {len(plan)} actions:") total_cost = 0 for i, action in enumerate(plan): print(f"{i+1}. {action.name} (cost: {action.cost})") total_cost += action.cost print(f"Total cost: {total_cost}")

print(f"\nDecomposition trace:")
for step in htn_planner.decomposition_trace:
    print(f"  {step}")
Copy

else: print("No plan found")

Test domestic vacation

print(f"\nDomestic vacation planning:") domestic_state = State({ 'have_money': True, 'have_clothes': True, 'have_id': True, 'have_internet': True, 'vacation_type': 'domestic' })

domestic_plan = htn_planner.plan(domestic_state, tasks) if domestic_plan: print(f"Domestic plan has {len(domestic_plan)} actions (vs {len(plan)} for international)") `} language="python" />

Planning Algorithm Selection

Choosing the Right Algorithm

Different planning problems require different approaches:

Algorithm Characteristics:

With appropriate conditions (admissible heuristic for A, finite depth for DFS)

Connections to Previous Concepts

Building on Agent Architectures and Tool Integration

Planning algorithms enhance the agent patterns we've learned:

From Agent Architectures:

• ReAct vs Planning: ReAct is reactive planning, while these algorithms do lookahead planning
• Hybrid Agents: Planning provides the deliberative layer in hybrid architectures
• Plan-and-Execute: These algorithms power the "Plan" phase

From Tool Integration:

• Action Representation: Planning actions map directly to tool calls
• Preconditions: Tool requirements become action preconditions
• Effects: Tool outputs become action effects
• Workflows: Planning generates tool execution sequences

Real-World Planning Applications

Modern AI agents use these planning algorithms for:

• Code Generation: Planning sequences of code edits
• Research: Planning information gathering strategies
• Business Process: Planning workflow automation
• Content Creation: Planning article structure and research steps

Practice Exercises

Exercise 1: Algorithm Implementation

Implement and compare different search algorithms:

1. Add Depth-First Search with iterative deepening
2. Implement bidirectional search
3. Create a hybrid planner that switches algorithms based on problem size
4. Measure performance across different problem types

Exercise 2: Heuristic Design

Design effective heuristics for different domains:

1. Grid navigation with obstacles
2. Resource allocation problems
3. Scheduling with constraints
4. Evaluate heuristic admissibility and effectiveness

Exercise 3: HTN Domain Modeling

Model a complex domain using HTN planning:

1. Software development project planning
2. Event organization with multiple tracks
3. Multi-step cooking recipes with ingredient dependencies
4. Compare HTN vs flat planning approaches

Exercise 4: Performance Analysis

Analyze planning algorithm performance:

1. Vary problem complexity and measure scaling
2. Compare memory usage across algorithms
3. Identify breakeven points for different approaches
4. Create decision trees for algorithm selection

Looking Ahead

In our next lesson, we'll explore Advanced Planning: Goal Decomposition and Uncertainty. We'll learn how to:

• Use means-ends analysis for complex goal decomposition
• Handle planning under uncertainty with probabilistic outcomes
• Create contingency plans for robust execution
• Implement dynamic replanning when conditions change

The search foundations and hierarchical planning we've built will enable sophisticated planning systems that can handle real-world complexity and uncertainty.

Additional Resources

• Planning Algorithms Book by Steven LaValle
• Artificial Intelligence: A Modern Approach - Planning Chapters
• HTN Planning Overview
• Search Algorithms Comparison
• PDDL Planning Domain Definition Language

Search Algorithm Visualization

Interactive Search Algorithm Comparison

Try different search problems:

• Pathfinding: Navigate through a grid with obstacles
• Puzzle Solving: Solve sliding puzzle or blocks world
• Resource Allocation: Optimize resource distribution
• Task Scheduling: Find optimal task ordering

Algorithm Performance Comparison

<ComparisonTable defaultValue='{"title": "Search Algorithm Performance", "columns": ["Algorithm", "Completeness", "Optimality", "Time Complexity", "Space Complexity", "Best For"], "data": [ ["Breadth-First Search", "Yes", "Yes*", "O(b^d)", "O(b^d)", "Shortest path, small spaces"], ["Depth-First Search", "No**", "No", "O(b^m)", "O(bm)", "Memory limited, very deep"], ["Iterative Deepening", "Yes", "Yes*", "O(b^d)", "O(bd)", "Combines BFS + DFS benefits"], ["A* Search", "Yes***", "Yes***", "Varies", "O(b^d)", "Informed search with heuristics"], ["Greedy Best-First", "No", "No", "O(b^m)", "O(b^m)", "Fast approximate solutions"], ["Bidirectional Search", "Yes", "Yes*", "O(b^(d/2))", "O(b^(d/2))", "Long paths, known goal"] ], "highlightRows": [0, 3], "footnotes": ["*For uniform cost", "**In infinite spaces", "***With admissible heuristic"]}' />