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.

python
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"""
Show all 129 lines

Breadth-First Search Planning

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

python
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)])
Show all 83 lines

A* Search Planning

A* uses heuristics to guide the search more efficiently:

python
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)"""
Show all 78 lines

Hierarchical Task Networks (HTN)

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

python
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
Show all 217 lines

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