Planning Algorithms: Search and Basic Planning

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

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.

Copy
# Foundation: State Space Search for Planning
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())

@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
    
    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):
            raise ValueError(f"Action {self.name} not applicable in current state")
        
        new_state = state.copy()
        new_state.variables.update(self.effects)
        return new_state

@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"""
    
    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
        return True
    
    def get_applicable_actions(self, state: State) -> List[Action]:
        """Get all actions that can be executed in this state"""
        return [action for action in self.actions if action.is_applicable(state)]

class SearchNode:
    """Node in the search tree"""
    
    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"""
        path = []
        node = self
        step_num = 0
        
        while node.parent is not None:
            plan_step = PlanStep(
                action=node.action,
                state_before=node.parent.state,
                state_after=node.state,
                step_number=step_num
            )
            path.append(plan_step)
            node = node.parent
            step_num += 1
        
        return list(reversed(path))

class PlannerBase(ABC):
    """Base class for planning algorithms"""
    
    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
    
    def expand_node(self, node: SearchNode) -> List[SearchNode]:
        """Expand a node by applying all applicable actions"""
        self.nodes_expanded += 1
        self.max_depth = max(self.max_depth, node.depth)
        
        children = []
        for action in self.problem.get_applicable_actions(node.state):
            new_state = action.apply(node.state)
            new_cost = node.path_cost + action.cost
            child = SearchNode(new_state, node, action, new_cost)
            children.append(child)
        
        return children

Breadth-First Search Planning

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

Copy
# Breadth-First Search Planner
class BreadthFirstPlanner(PlannerBase):
    """Breadth-First Search planner - guarantees optimal solution"""
    
    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()
            explored.add(node.state)
            
            for child in self.expand_node(node):
                if child.state not in explored and child.state not in [n.state for n in frontier]:
                    if self.problem.is_goal_state(child.state):
                        return child.get_path()
                    frontier.append(child)
        
        return None  # No solution found

# Example: Simple Blocks World Problem
def create_simple_blocks_example():
    """Create a simple blocks world planning problem"""
    
    # 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
    goal_conditions = {
        'on(A)': 'B',
        'on(B)': 'Table'
    }
    
    # Define actions
    actions = [
        Action(
            name='pickup(B,A)',
            preconditions={'on(B)': 'A', 'clear(B)': True, 'arm_empty': True},
            effects={'on(B)': None, 'clear(A)': True, 'arm_empty': False, 'holding': 'B'}
        ),
        Action(
            name='putdown(B,Table)',
            preconditions={'holding': 'B'},
            effects={'on(B)': 'Table', 'arm_empty': True, 'holding': None}
        ),
        Action(
            name='pickup(A,Table)',
            preconditions={'on(A)': 'Table', 'clear(A)': True, 'arm_empty': True},
            effects={'on(A)': None, 'arm_empty': False, 'holding': 'A'}
        ),
        Action(
            name='putdown(A,B)',
            preconditions={'holding': 'A', 'clear(B)': True},
            effects={'on(A)': 'B', 'clear(B)': False, 'arm_empty': True, 'holding': None}
        )
    ]
    
    return PlanningProblem(initial_state, goal_conditions, actions)

# 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")

A* Search Planning

A* uses heuristics to guide the search more efficiently:

Copy
# A* Search Planner with Heuristics
class AStarPlanner(PlannerBase):
    """A* search planner - optimal with admissible heuristic"""
    
    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)
        node_counter = 0  # For tie-breaking in heap
        
        while frontier:
            _, _, node = heapq.heappop(frontier)
            
            if self.problem.is_goal_state(node.state):
                return node.get_path()
            
            explored.add(node.state)
            
            for child in self.expand_node(node):
                if child.state in explored:
                    continue
                
                g_cost = child.path_cost
                h_cost = self.heuristic(child.state, self.problem.goal_conditions)
                f_cost = g_cost + h_cost
                
                # Check if we have a better path to this state
                if child.state in frontier_states:
                    old_f, old_node = frontier_states[child.state]
                    if f_cost >= old_f:
                        continue
                
                frontier_states[child.state] = (f_cost, child)
                node_counter += 1
                heapq.heappush(frontier, (f_cost, node_counter, child))
        
        return None

# 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}")

Hierarchical Task Networks (HTN)

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

Copy
# Hierarchical Task Network (HTN) Planning
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 = {}

@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

class HTNPlanner:
    """Hierarchical Task Network planner"""
    
    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, [])
    
    def _plan_recursive(self, state: State, tasks: List[Task], plan: List[Action]) -> Optional[List[Action]]:
        """Recursive HTN planning"""
        if not tasks:
            return plan  # All tasks completed
        
        current_task = tasks[0]
        remaining_tasks = tasks[1:]
        
        if current_task.task_type == TaskType.PRIMITIVE:
            # Execute primitive action
            action = self.actions.get(current_task.name)
            if action and action.is_applicable(state):
                new_state = action.apply(state)
                new_plan = plan + [action]
                self.decomposition_trace.append(f"Execute: {current_task.name}")
                return self._plan_recursive(new_state, remaining_tasks, new_plan)
            else:
                return None  # Cannot execute action
        
        else:  # COMPOUND task
            # Try all applicable methods for decomposition
            for method in self.methods:
                if method.task == current_task.name and method.is_applicable(state):
                    # Decompose using this method
                    self.decomposition_trace.append(f"Decompose {current_task.name} using {method.name}")
                    new_tasks = method.subtasks + remaining_tasks
                    result = self._plan_recursive(state, new_tasks, plan)
                    if result is not None:
                        return result
            
            return None  # No applicable method found

# Example: Travel Planning with HTN
def create_travel_planning_example():
    """Create a hierarchical travel planning problem"""
    
    # 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',
            preconditions={'have_clothes': True},
            effects={'bags_packed': True},
            cost=1
        ),
        Action(
            name='book_hotel',
            preconditions={'have_money': True, 'have_destination': True},
            effects={'have_accommodation': True},
            cost=200
        ),
        Action(
            name='get_passport',
            preconditions={'have_id': True},
            effects={'have_passport': True},
            cost=10
        ),
        Action(
            name='research_destination',
            preconditions={'have_internet': True},
            effects={'have_destination': True, 'know_attractions': True},
            cost=2
        )
    ]
    
    # Methods for compound task decomposition
    methods = [
        Method(
            name='plan_vacation_international',
            task='plan_vacation',
            preconditions={'vacation_type': 'international'},
            subtasks=[
                Task('research_destination', TaskType.PRIMITIVE),
                Task('get_travel_documents', TaskType.COMPOUND),
                Task('make_reservations', TaskType.COMPOUND),
                Task('prepare_for_travel', TaskType.COMPOUND)
            ]
        ),
        Method(
            name='plan_vacation_domestic',
            task='plan_vacation',
            preconditions={'vacation_type': 'domestic'},
            subtasks=[
                Task('research_destination', TaskType.PRIMITIVE),
                Task('make_reservations', TaskType.COMPOUND),
                Task('prepare_for_travel', TaskType.COMPOUND)
            ]
        ),
        Method(
            name='get_travel_docs_international',
            task='get_travel_documents',
            preconditions={'vacation_type': 'international'},
            subtasks=[
                Task('get_passport', TaskType.PRIMITIVE)
            ]
        ),
        Method(
            name='make_reservations_method',
            task='make_reservations',
            preconditions={},
            subtasks=[
                Task('book_flight', TaskType.PRIMITIVE),
                Task('book_hotel', TaskType.PRIMITIVE)
            ]
        ),
        Method(
            name='prepare_for_travel_method',
            task='prepare_for_travel',
            preconditions={},
            subtasks=[
                Task('pack_bags', TaskType.PRIMITIVE)
            ]
        )
    ]
    
    return actions, methods

# 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}")
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)")

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

*For uniform cost
**In infinite spaces
***With admissible heuristic