Lecture 5: Search Algorithms

Author

Your Name

Published

February 10, 2025

Introduction

Course Logistics and Questionnaire

Welcome to the fifth lecture on Artificial Intelligence. Today’s topic will be search algorithms. Please note that this lecture will conclude slightly earlier than usual, and we will forgo the break due to a scheduling conflict with a research committee meeting. Kindly ensure the door is closed to minimize external disturbances.

Before we proceed, I would like to remind everyone to complete the course questionnaire. We observed a significant increase in submissions following the last reminder; however, some students present in the classroom have yet to participate. Your feedback is valuable, so if you have not already done so, please take a moment to complete the questionnaire at your earliest convenience.

Review of Previous Lectures

To set the stage for today’s topic, let’s briefly recap what we have covered in the initial lectures. We began with introductory discussions on the fundamental question: What is Artificial Intelligence? We explored its origins, historical evolution, and the various approaches that have shaped the field.

Definition of AI and Agents

A significant portion of our early discussions was dedicated to establishing a comprehensive definition of Artificial Intelligence. We aimed to move beyond superficial understandings and delve into the core principles that define intelligent systems. Furthermore, we introduced and elaborated on the concept of an agent, particularly intelligent agents. This notion is central to the study of AI, as it provides a framework for understanding how intelligent systems interact with their environment and pursue goals. The concept of agents and intelligent agents is foundational, and much of the subsequent material in this course, as reflected in the textbook, will build upon these ideas.

Introduction to Search

In our previous lecture, we initiated our exploration of search as a core topic in AI. We started to examine how agents can exhibit what we term, in a somewhat loose sense, "intelligent" behavior by employing search techniques. Specifically, we discussed how agents could find solutions or achieve goals by systematically exploring a state space. This lecture will directly continue from where we left off, delving deeper into search algorithms and strategies within state spaces.

Defining Search Problems

In the realm of Artificial Intelligence, problem-solving often involves searching for a sequence of actions that lead to a desired goal. To formalize this process, we define a search problem through several key components. These components provide a structured way to represent and solve problems using search algorithms.

Components of a Search Problem

Definition 1 (Components of a Search Problem). A search problem is formally defined by the following six elements, which collectively specify everything needed to formulate a problem for algorithmic solution:

State Space ($S$): This is the set of all possible configurations or situations that the agent can be in. Each element in $S$ is a state. The state space can be discrete or continuous, finite or infinite.
Initial State: This is the state in which the agent starts. It is the starting point of the search. There may be multiple possible initial states, but typically we consider a single, well-defined initial state for simplicity.
Goal State(s): This defines the desired state or condition that the agent is trying to achieve. There can be one or more goal states. Often, for simplicity, we refer to a single goal state, but in general, it can be a set of states. The goal is what defines success in problem-solving.
Actions ($ADS$): For each state $s \in S$, there is a set of applicable actions, given by the function $ADS(s)$. These are the actions that can be executed by the agent when it is in state $s$. The actions define how the agent can move or change its state within the state space.
Transition Model: This describes the result of performing an action in a given state. In the simplest form, which we consider initially, the transition model is deterministic. This means that for each state $s$ and action $a \in ADS(s)$, the outcome is a single, uniquely determined next state. More complex scenarios might involve non-deterministic transition models, where an action could lead to multiple possible outcomes, each with a certain probability.
Cost Function: Each action has an associated cost, representing the ‘expense’ of performing that action. This cost can be measured in terms of time, resources, distance, or any other relevant metric. The path cost is the sum of the costs of the actions taken to reach a state. The objective in many search problems is to find a solution with the minimum total path cost, known as an optimal solution.

Examples of Search Problems

To better understand these components, let’s consider a couple of illustrative examples.

Romania Travel Problem

Example 1 (Romania Travel Problem). The Romania travel problem* is a classic example used to illustrate search algorithms. In this problem, the state space is defined by cities in Romania. The goal is to travel from a starting city, say Arad, to a destination city, Bucharest, by following a sequence of roads.*

States: Cities in Romania (e.g., Arad, Bucharest, Sibiu, etc.).
Initial State: Arad.
Goal State: Bucharest.
Actions: Driving from one city to an adjacent city. For example, from Arad, possible actions are to drive to Sibiu, Timisoara, or Zerind.
Transition Model: Driving from city A to city B results in being in city B. This is deterministic.
Cost Function: The cost of each action (driving from one city to another) is the distance between the cities, typically measured in kilometers or miles. The objective is to find a sequence of cities to visit (path) that minimizes the total distance traveled from Arad to Bucharest.

This example is particularly useful because it is intuitive and allows us to visualize the search process on a map. It is important to note that while this example involves geographical locations, the concept of state space search is far more general and not limited to physical spaces or trajectory planning.

Vacuum Cleaner Robot

Example 2 (Vacuum Cleaner Robot). Consider a simplified environment with two cells, where a vacuum cleaner robot needs to clean up dirt. This example illustrates that states can represent more than just physical locations; they can include properties of the environment.

States: A state is defined by the robot’s location (cell 1 or cell 2) and the dirt status of each cell (dirty or clean). For instance, a state could be represented as (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty). There are $2 \times 2 \times 2 = 8$ possible states.
Initial State: Could be any state, for example, (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty).
Goal State: Any state where both cells are clean, regardless of the robot’s location. For example, (Location=Cell 1, Cell 1=Clean, Cell 2=Clean) or (Location=Cell 2, Cell 1=Clean, Cell 2=Clean).
Actions:
- **Move Right: Move from cell 1 to cell 2 (if in cell 1).
- **Move Left: Move from cell 2 to cell 1 (if in cell 2).
- **Suck: Clean dirt in the current cell.
- **NoOp: Do nothing.
Transition Model: For example, in state (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty), performing Suck* leads to (Location=Cell 1, Cell 1=Clean, Cell 2=Dirty).*
Cost Function: Each action can have a cost, e.g., 1 for Move Right* and Move Left, and 1 for Suck, and 0 for NoOp. The goal is to find a sequence of actions to reach a goal state with minimum cost.*

In this example, a state is not merely a position in physical space but an abstraction representing the robot’s configuration and the environment’s condition. This highlights the versatility of state space representation in search problems.

State Space Graphs

To visualize and analyze search problems, we use state space graphs. These graphs provide a graphical representation of the state space and the transitions between states.

Nodes and States

Definition 2 (Nodes and States in State Space Graphs). In a state space graph, each node represents a state from the state space $S$. There is a direct, one-to-one correspondence between states and nodes. While it is formally correct to distinguish between a node in the graph and the state it represents, in practice, and for ease of discussion, we often use the terms interchangeably. Thus, we might say "node Arad" when we technically mean "the node in the state space graph that corresponds to the state of being in Arad."

Arcs and Actions

Definition 3 (Arcs and Actions in State Space Graphs). The arcs (or edges) in a state space graph represent the actions that allow transitions between states. A directed arc from node $A$ to node $B$ indicates that there is an action that can be performed in state $A$ to transition to state $B$. In a weighted state space graph, each arc is associated with a cost, representing the cost of the corresponding action.

Solutions and Optimal Solutions

Definition 4 (Solution in State Space Graphs). A solution to a search problem, within the context of a state space graph, is a path from the node representing the initial state to a node representing a goal state. This path is a sequence of connected arcs in the graph.

Definition 5 (Optimal Solution in State Space Graphs). An optimal solution is a path from the initial state to a goal state that has the minimum total cost. The cost of a path is typically the sum of the costs of all arcs along the path. If all actions have a uniform cost (e.g., cost of 1 for each action), then the optimal solution is the path with the fewest arcs, i.e., the shortest path in terms of path length. However, when actions have varying costs, the optimal solution is the path with the minimum sum of these costs, not necessarily the one with the fewest steps. For the Romania travel problem, the state space graph is weighted, with the weights on the arcs representing the distances between connected cities. These distances, often given in miles in textbooks, serve as the cost for moving between cities.

Search Trees

While state space graphs represent the problem structure, search trees are used by search algorithms to explore potential solutions. A search tree is derived from the state space graph and represents the exploration process.

Construction from State Space Graphs

Definition 6 (Search Tree Construction). A search tree is built starting from the initial state, which becomes the root of the tree. The process of building the tree involves expanding nodes. To expand a node means to consider the actions applicable in the state corresponding to that node and to generate the successor states. Each successor state becomes a child node in the search tree, connected to the parent node by an edge representing the action taken. This process is repeated level by level, exploring paths from the initial state towards potential goal states. The search tree essentially unfolds paths in the state space graph starting from the initial state.

Node Repetition

Remark. Remark 1 (Node Repetition in Search Trees). A key difference between a state space graph and a search tree is that a single state (and thus, a single node in the state space graph) can appear multiple times in a search tree. This happens because there can be multiple paths leading to the same state. Consider a state space where state E can be reached from state S directly, and also through an intermediate state D. In the search tree, state E will appear as a child of S and potentially again as a descendant of D, even though in the state space graph, there is only one node for state E. Each occurrence of a node in the search tree represents a unique path from the initial state to the corresponding state in the state space graph.

Representing Paths as Nodes

Remark. Remark 2 (Paths as Nodes in Search Trees). Each node in the search tree can be thought of as representing not just a state, but an entire path from the initial state to the current state in the state space graph. This is why a state can be repeated in the search tree – each repetition corresponds to a different path to reach that state.

Potential for Infinite Trees

Remark. Remark 3 (Infinite Search Trees). If the state space graph contains cycles, the search tree derived from it can be infinite. For example, if we have states S, A, and B, and transitions S $\rightarrow$ A, A $\rightarrow$ B, and B $\rightarrow$ A, starting from S, we can generate an infinite search tree with paths like S-A-B-A-B-A-... and S-B-A-B-A-B-... This is a crucial consideration for search algorithms, as naively exploring such a tree can lead to infinite loops and prevent finding a solution, even if one exists.

Illustration of a State Space Graph and a corresponding partial Search Tree, showing node repetition. In the search tree, node ’A’ and ’B’ are repeated, representing different paths from the initial state ’S’.

To manage potentially infinite search trees and avoid redundant exploration, it is crucial to keep track of the paths already explored and the states already visited. As the adage goes, "Those who do not know history are destined to repeat it." In the context of search algorithms, this translates to: if we do not remember the paths we have already taken, we risk revisiting states and exploring redundant paths, leading to inefficiency or infinite loops. Effective search algorithms must therefore incorporate mechanisms to remember and utilize the history of the search process.

Systematic Search and the Frontier

In the quest to build intelligent agents, it is crucial that these agents can find solutions to problems in a reliable and efficient manner. This necessitates the use of systematic search methods. Unlike random exploration, systematic search ensures that no part of the search space is overlooked, guaranteeing that a solution will be found if one exists within the explored space.

The Need for Systematic Search

Imagine an agent navigating a maze or searching for a specific file on a vast computer system. If the agent explores randomly, it might stumble upon the solution by chance, but there’s no guarantee of success, especially in complex or infinite environments. Systematic search is essential because it provides a structured approach to explore the state space. By methodically examining states and transitions, we ensure that if a path to a goal exists, the search algorithm will eventually discover it.

Consider a simple grid world example. If a goal is located at a finite distance from the starting point, a systematic search, such as exploring layer by layer, will eventually reach the goal. In contrast, a random walk might miss the goal entirely or take a highly inefficient path. Systematicity is particularly important in scenarios where solutions are not immediately obvious or where the search space is vast or even infinite. For instance, in automated planning or complex problem-solving tasks, a haphazard approach is unlikely to yield satisfactory results. Therefore, for an agent to be truly intelligent and effective, its search for solutions must be systematic and well-organized.

The Frontier: Separating Explored and Unexplored States

To implement systematic search, we introduce the concept of a frontier. The frontier is a crucial abstraction that helps us manage the search process by clearly delineating the boundary between the parts of the state space we have explored and those we have yet to examine. At any point during the search, we can categorize all nodes in the state space into three disjoint sets:

Expanded Nodes (Explored Set)

Definition 7 (Expanded Nodes (Explored Set)). Expanded nodes, also referred to as the explored set, are the states that the search algorithm has already processed and explored. When we "expand" a node, we generate its successors and evaluate them. In the lecture’s visual examples, these nodes are depicted in violet. Essentially, these are the states for which we have already determined the next possible steps and added them to our list of states to consider further.

Frontier Nodes (Pending Exploration)

Definition 8 (Frontier Nodes (Pending Exploration)). Frontier nodes represent the current boundary of our exploration. These are the states that we have discovered and know about, but have not yet explored in detail. They are "on the edge" of the explored region, waiting to be selected for expansion. In the visual analogy, these are shown in green. The frontier is the set of nodes that are candidates for the next step of expansion. It acts as a buffer between the explored and unexplored regions of the state space.

Unexplored Nodes (Unseen States)

Definition 9 (Unexplored Nodes (Unseen States)). Unexplored nodes are all the states in the state space that the search algorithm has not yet encountered or considered. These are the vast, unknown parts of the state space that lie beyond the frontier. In our visual representation, these are in grey. These states have not yet been generated or added to the frontier.

The process of expanding a node from the frontier is the core operation in systematic search. When we expand a node:

We move it from the frontier set to the expanded set, signifying that we have now fully processed this state.
We examine the state to determine the possible actions and resulting next states (successors).
For each successor state, if it is a new state (i.e., not already in the expanded set or the frontier), we add it to the frontier set.

This expansion process ensures that the frontier always represents the interface between the explored and unexplored parts of the state space. By systematically selecting and expanding nodes from the frontier, search algorithms can methodically explore the state space and find solutions.

A General Tree Search Algorithm

To formalize the concept of systematic search using the frontier, we can define a general tree search algorithm. Algorithm [alg:tree_search] presents a pseudo-code outline for such an algorithm.

Objective: Find a solution path from an initial state to a goal state in a search problem. Input:

problem: Definition of the search problem, including the initial state, goal state(s), actions, transition model, and cost function.
strategy: A strategy that dictates how to choose the next node to expand from the frontier. Different strategies lead to different search algorithms (e.g., Depth-First, Breadth-First, Uniform Cost).

Output: A solution path (sequence of actions) if a goal state is reachable, or failure if no solution is found.

Initialize the frontier using the initial state of the problem. This often involves creating a node representing the initial state and adding it to the frontier. failure node $\leftarrow$ if node is a goal state then Expand node, generating its successors. Add successors to the frontier if they are not already in the frontier or expanded set. Add node to the expanded set.

This Tree-Search algorithm provides a high-level framework for various search algorithms. It takes a problem definition and a search strategy as input. The algorithm begins by initializing the frontier with the initial state. Then, it enters a loop that continues until a solution is found or the frontier becomes empty. Inside the loop:

Check for Empty Frontier: It first checks if the frontier is empty. If it is, it means there are no more states to explore, and the algorithm returns failure, indicating that no solution was found in the explored search space.
Node Selection: If the frontier is not empty, the algorithm selects a node from the frontier using a strategy. This strategy is a crucial parameter that differentiates various search algorithms. For example, different strategies will dictate whether to explore deeper paths first or broader paths first, or paths with lower costs.
Goal Test: The selected node is then checked to see if it represents a goal state. If it is a goal state, the algorithm has found a solution and returns the solution path, which is typically reconstructed by tracing back from the goal node to the initial node, keeping track of the parent pointers or actions taken to reach each state.
Node Expansion: If the selected node is not a goal state, it is expanded. This involves generating all possible successor states reachable from the current state through applicable actions, as defined by the problem’s transition model.
Frontier Update: The newly generated successor nodes are added to the frontier, provided they meet certain conditions (e.g., not already explored or in the frontier, depending on whether we are doing tree search or graph search). The expanded node is then moved to the expanded set to keep track of visited states and prevent redundant exploration in some search variants.

The efficiency and characteristics of different search algorithms derived from this framework depend heavily on the strategy used to select nodes from the frontier. In the following sections, we will explore several uninformed search strategies, which vary in how they implement this node selection process, and analyze their properties.

Complexity Analysis: The time and space complexity of this general tree search algorithm are highly dependent on the specific search strategy and the properties of the state space. In the worst case, for tree search without cycle detection, the algorithm might explore paths of exponential length relative to the depth of the search space. For graph search (which avoids repeated states), the complexity is often related to the size of the state space itself and the branching factor. Specific complexity analyses will be provided when we discuss concrete search strategies like Breadth-First Search, Depth-First Search, and Uniform Cost Search.

Uninformed Search Strategies

Informed search strategies are essential for navigating state spaces when we lack specific information about the location of the goal. These methods, also known as blind search strategies, explore the state space based solely on the problem definition, without any heuristic guidance about which paths are more promising. We will now delve into several fundamental uninformed search algorithms: Depth-First Search (DFS), Breadth-First Search (BFS), Iterative Deepening Depth-First Search (ID-DFS), and Uniform Cost Search (UCS).

Depth-First Search (DFS)

Depth-First Search (DFS) is a strategy that explores the state space by always expanding the deepest node in the current frontier. It proceeds as far as possible along each branch before backtracking. Imagine exploring a maze; DFS is like choosing a path and following it to the end, and if you reach a dead end, you backtrack to the last decision point and try another path.

LIFO Queue (Stack) Implementation

Definition 10 (DFS Implementation using LIFO Queue). DFS is typically implemented using a Last-In-First-Out (LIFO) queue, commonly known as a stack, to manage the frontier. When a node is expanded, its successors are added to the top of the stack. The algorithm then picks the node from the top of the stack to expand next. This LIFO structure ensures that the search explores deeper into the tree whenever possible.

Properties of DFS: Completeness, Optimality, Complexity

To evaluate search algorithms, we consider several key properties: completeness, optimality, time complexity, and space complexity. For DFS:

Completeness:

Remark. Remark 4 (Completeness of DFS). DFS is not complete in infinite state spaces or in state spaces with cycles. In such scenarios, DFS can follow an infinite path and never return to explore other parts of the state space, potentially missing goal states. If the state space is finite and we implement cycle detection (i.e., avoid revisiting states), DFS is complete. However, without cycle detection in a cyclic graph, it can fail to find a solution even if one exists.
Optimality:

Remark. Remark 5 (Optimality of DFS). DFS is not optimal. It explores paths deeply and may find a goal state that is far from the initial state in terms of path cost, even if shorter paths to goal states exist. DFS prioritizes depth over cost, so the first solution it finds is not guaranteed to be the optimal one.
Time Complexity:

Remark. Remark 6 (Time Complexity of DFS). In the worst case, DFS can explore the entire search tree. For a state space with a maximum depth $m$ and branching factor $b$, the time complexity of DFS is $O(b^m)$. In the worst case, it might explore all paths up to depth $m$. However, if DFS happens to stumble upon a solution early in a deep path, it can be much faster.
Space Complexity:

Remark. Remark 7 (Space Complexity of DFS). DFS has a space complexity of $O(b \cdot m)$, where $m$ is the maximum depth of the search tree. This is because DFS only needs to store the current path from the root to the deepest node in the frontier, along with the unexpanded siblings for each node on the path. This makes DFS space-efficient compared to BFS, especially for large search spaces with deep solutions.

Breadth-First Search (BFS)

Breadth-First Search (BFS) systematically explores the state space layer by layer. It expands all nodes at the current depth before moving on to nodes at the next depth level. BFS is like exploring a maze by examining all possible paths of length 1, then all possible paths of length 2, and so on, until a solution is found.

FIFO Queue Implementation

Definition 11 (BFS Implementation using FIFO Queue). BFS is implemented using a First-In-First-Out (FIFO) queue to manage the frontier. When a node is expanded, its successors are added to the back of the queue. The algorithm always selects the node from the front of the queue to expand next. This FIFO structure ensures that nodes are explored in the order of their depth from the starting node.

Properties of BFS: Completeness, Optimality, Complexity

For BFS, the properties are as follows:

Completeness:

Remark. Remark 8 (Completeness of BFS). BFS is complete for finite state spaces. If a solution exists, BFS is guaranteed to find it. For infinite state spaces, BFS is complete if there is a solution at a finite depth (i.e., a finite number of steps from the initial state). If a solution exists at some finite depth $d$, BFS will find it.
Optimality:

Theorem 1 (Optimality of BFS for Uniform Costs). BFS is optimal if all step costs are uniform (i.e., each action has the same cost, typically considered as 1). In this case, BFS finds the solution with the shortest path in terms of the number of steps (path length). However, if step costs are not uniform, BFS is not guaranteed to find the least-cost solution. It will still find a solution with the minimum number of steps, but not necessarily the minimum total cost.
Time Complexity:

Remark. Remark 9 (Time Complexity of BFS). In the worst case, BFS explores all nodes at depth up to the depth of the shallowest goal state. If the shallowest goal is at depth $d$, and the branching factor is $b$, BFS may explore $1 + b + b^2 + \dots + b^d = O(b^d)$ nodes. Thus, the time complexity is $O(b^d)$.
Space Complexity:

Remark. Remark 10 (Space Complexity of BFS). BFS must keep all nodes at the current depth in memory to explore their children in the next step. In the worst case, if the shallowest goal is at depth $d$, BFS stores all nodes at depth $d-1$ in the frontier, leading to a space complexity of $O(b^d)$. Space is often the limiting factor for BFS, as the number of nodes at each level grows exponentially.

Comparison of BFS and DFS

Remark. Remark 11 (Comparison of BFS and DFS). The choice between BFS and DFS depends on the problem characteristics and priorities:

When to use BFS: BFS is preferred when the solution is expected to be at a shallow depth in the search tree, or when finding the shortest path (in terms of steps) is crucial and step costs are uniform. BFS is also favored when completeness is a must,and we need to guarantee finding a solution if one exists in a finite state space.
When to use DFS: DFS can be more efficient in terms of space and time if solutions are known to be deep in the search tree, or if only one solution is needed and optimality is not a concern. DFS might also be suitable when the search space is very large, but there’s a good chance of finding a solution by exploring a deep path early on. However, DFS risks getting lost in infinite paths and is not guaranteed to find the shortest path.

Iterative Deepening Depth-First Search (ID-DFS)

Iterative Deepening Depth-First Search (ID-DFS) aims to combine the space efficiency of DFS with the completeness and optimality (for uniform costs) of BFS. ID-DFS performs a sequence of DFS searches, each with a progressively increasing depth limit.

Combining DFS and BFS for Efficiency

Remark. Remark 12 (Iterative Deepening Process of ID-DFS). ID-DFS works as follows:

Perform DFS to depth limit 0 (only root node).
If no solution is found, perform DFS to depth limit 1.
If no solution is found, perform DFS to depth limit 2.
Continue increasing the depth limit by one at each iteration until a goal is found.

In each iteration, ID-DFS starts from the initial state and explores in a depth-first manner, but it cuts off the search at the current depth limit. This iterative process ensures that the algorithm explores the search space in layers, similar to BFS, but using DFS for each layer.

Completeness and Optimality of Iterative Deepening

ID-DFS inherits the desirable properties of both BFS and DFS to some extent:

Completeness:

Remark. Remark 13 (Completeness of ID-DFS). ID-DFS is complete in finite state spaces and for state spaces with solutions at finite depth. Because it explores layer by layer, it will eventually reach any reachable goal state, similar to BFS.
Optimality:

Theorem 2 (Optimality of ID-DFS for Uniform Costs). ID-DFS is optimal when step costs are uniform, just like BFS. It finds the shallowest goal state, which corresponds to the least number of steps in uniform cost scenarios.
Time Complexity:

Remark. Remark 14 (Time Complexity of ID-DFS). Although ID-DFS repeats searches at shallower depths, the total time complexity remains comparable to BFS. For a branching factor $b$ and solution depth $d$, the number of nodes expanded in ID-DFS is approximately $O(b^d)$. The re-exploration of shallower nodes is not as computationally expensive as it might first appear because the number of nodes at each depth level grows exponentially. Most of the nodes are at the deepest level explored.
Space Complexity:

Remark. Remark 15 (Space Complexity of ID-DFS). ID-DFS has the space complexity of DFS, which is $O(b \cdot d)$, where $d$ is the depth of the solution. In each iteration, it performs a DFS, and the space required is only for the current path being explored. This is a significant advantage over BFS, especially for problems with large search spaces and deeper solutions.

Remark. Remark 16 (Use Cases for ID-DFS). ID-DFS is often preferred in scenarios where space is a constraint and optimality (for uniform costs) is desired. It effectively balances the benefits of BFS and DFS.

Uniform Cost Search (UCS)

Uniform Cost Search (UCS), also known as Dijkstra’s algorithm, is an uninformed search algorithm that expands nodes based on the cost of the path from the start node to the current node. UCS is designed to find the least-cost path to a goal, making it optimal for problems with varying step costs.

Dijkstra’s Algorithm in AI

Remark. Remark 17 (UCS and Dijkstra’s Algorithm). In the field of computer science, particularly in algorithms and graph theory, UCS is recognized as Dijkstra’s algorithm. In the context of Artificial Intelligence search, it is often referred to as Uniform Cost Search, emphasizing its strategy of expanding nodes in order of their path cost uniformity.

Cost Function G(n): Path Cost

Definition 12 (Path Cost Function G(n) in UCS). UCS uses a cost function, denoted as $G(n)$, which represents the accumulated cost of the path from the initial state to reach node $n$. For the initial state, $G(\text{initial state}) = 0$. For any successor $n'$ of node $n$ reached by action $a$ with cost $c(n, a, n')$, the path cost is updated as $G(n') = G(n) + c(n, a, n')$.

Priority Queue Implementation

Definition 13 (UCS Implementation using Priority Queue). UCS employs a priority queue to manage the frontier. The priority queue orders nodes based on their $G(n)$ values. At each step, UCS selects the node from the frontier that has the lowest $G(n)$ value for expansion. This ensures that paths with lower costs are explored first.

Properties of UCS: Completeness, Optimality, Complexity

The properties of UCS are crucial for understanding its applicability and performance:

Completeness:

Theorem 3 (Completeness of UCS). UCS is complete under the condition that the cost of every step is greater than some small positive constant $\epsilon > 0$. This condition ensures that the path costs increase monotonically and prevents infinite paths with zero or near-zero costs from being explored indefinitely. If there is a solution, UCS is guaranteed to find it.
Optimality:

Theorem 4 (Optimality of UCS). UCS is optimal. It always finds the least-cost path to a goal state. Because it expands nodes in order of increasing path cost, the first time UCS reaches a goal state, it is guaranteed to have done so via the cheapest path.
Time Complexity:

Remark. Remark 18 (Time Complexity of UCS). The time complexity of UCS is related to the cost of the optimal solution, let’s say $C^*$, and the minimum step cost, $\epsilon$. In the worst case, UCS might explore all nodes with path cost less than or equal to $C^*$. If we consider the ‘effective depth’ in terms of cost as $C^*/\epsilon$ and branching factor $b$, the time complexity can be roughly approximated as $O(b^{C^*/\epsilon})$. In practice, it is often described in terms of the number of nodes whose path cost is less than the cost of the optimal solution.
Space Complexity:

Remark. Remark 19 (Space Complexity of UCS). Similar to time complexity, the space complexity is also related to the number of nodes explored, which can be in the order of $O(b^{C^*/\epsilon})$ in the worst case, as UCS needs to store all nodes in the frontier.

Water Maze Example: BFS vs. UCS

Example 3 (Water Maze Example: BFS vs. UCS). Consider a water maze where different regions have varying depths, representing different costs for movement. In a shallow region, moving one step might cost 1 unit, while in a deep region, it might cost 2 units.

BFS in Water Maze: BFS would explore the maze uniformly in all directions, expanding layer by layer based on the number of steps. It would find a path with the fewest steps, regardless of the cost associated with each step. In the water maze example, BFS might lead the robot through deeper, more costly regions if that path happens to have fewer steps.
UCS in Water Maze: UCS, on the other hand, would prioritize paths through shallower, less costly regions. It expands nodes based on the accumulated cost, so it would prefer to move through shallow water even if it means taking a slightly longer path in terms of steps. UCS is guaranteed to find a path that minimizes the total ‘effort’ or cost, which is more relevant when actions have different costs.

In scenarios with varying action costs, UCS is generally more appropriate than BFS if the goal is to minimize the total cost, not just the number of steps. BFS is only optimal when all step costs are uniform.

Best-First Search: A General Framework

Best-First Search is not a specific algorithm but rather a conceptual framework that encompasses several search algorithms, including BFS, DFS, and UCS, as special cases. The core idea of Best-First Search is to expand nodes based on an evaluation function that estimates the "desirability" of each node.

Using a Cost Function F(n)

Definition 14 (Evaluation Function F(n) in Best-First Search). Best-First Search uses a generic evaluation function, $F(n)$, to determine the order in which nodes in the frontier are expanded. At each step, the algorithm selects the node $n$ from the frontier for which $F(n)$ is minimum (or maximum, depending on the definition of ‘best’). The function $F(n)$ is designed to estimate how promising each node is, guiding the search towards potentially better paths.

BFS, DFS, and UCS as Best-First Search Instances

Remark. Remark 20 (BFS, DFS, and UCS as Best-First Search Instances). Different choices for the evaluation function $F(n)$ in Best-First Search lead to different search algorithms:

BFS as Best-First Search: In BFS, we prioritize nodes based on their depth. We can define $F(n) = \text{Depth}(n)$. By minimizing $F(n)$, we are effectively choosing to expand the shallowest nodes first, which is exactly what BFS does.
DFS as Best-First Search: In DFS, we prioritize deeper exploration. We can define $F(n) = -\text{Depth}(n)$. By minimizing $F(n)$ (which is equivalent to maximizing $-\text{Depth}(n)$ or maximizing $\text{Depth}(n)$ in terms of absolute value), we prioritize expanding the deepest nodes, thus mimicking DFS behavior.
UCS as Best-First Search: In UCS, we prioritize nodes based on their path cost from the start node, $G(n)$. We can set $F(n) = G(n)$. By minimizing $F(n)$, we are selecting nodes with the lowest path cost to expand, which is the core strategy of UCS.

Thus, BFS, DFS, and UCS can all be viewed as instances of Best-First Search, each employing a different evaluation function to guide the search process. This perspective highlights the underlying common structure of these algorithms and how their behavior is determined by the node selection strategy defined through the evaluation function. The textbook may indeed introduce Best-First Search as a general algorithm first, and then present BFS, DFS, and UCS as specific implementations derived by choosing particular evaluation functions.

Optimizing Search

To enhance the efficiency of search algorithms, various optimization techniques have been developed. One notable approach is Bidirectional Search, which aims to reduce the search effort by simultaneously exploring from both the start and goal states.

Bidirectional Search

Bidirectional Search is an optimization technique designed to speed up the search process by running two simultaneous searches: one forward from the initial state and one backward from the goal state. The idea is to meet in the middle, hoping to find the solution faster than searching in a single direction.

Forward and Backward Search

Definition 15 (Forward and Backward Search in Bidirectional Search). Traditional search algorithms, like those discussed so far, operate by searching forward from the initial state towards the goal state. Bidirectional search enhances this by concurrently initiating a second search process that operates backward from the goal state towards the initial state.

Forward Search: This search starts at the initial state and explores the state space in the usual direction, moving from predecessors to successors.
Backward Search: This search starts at the goal state and explores in reverse, moving from successors to predecessors. To perform a backward search, we need to be able to determine the predecessors of each state, which requires reversible actions. In some problems, reversing actions might be straightforward, while in others, it may require more complex inverse operations or might not be possible at all.

The process continues until the two search frontiers meet. When a state is reached that has been explored by both the forward and backward searches, a path from the initial state to the goal state has been found.

Mechanism of Bidirectional Search

Remark. Remark 21 (Mechanism of Bidirectional Search). To implement bidirectional search, we need to manage two frontiers:

Forward Frontier ($F_f$): This frontier is used by the forward search, starting from the initial state. It contains nodes to be expanded in the forward direction.
Backward Frontier ($F_b$): This frontier is used by the backward search, starting from the goal state(s). It contains nodes to be expanded in the backward direction.

The algorithm proceeds in steps, typically alternating between expanding a node from the forward frontier and a node from the backward frontier. In each step, we:

Select a node from either $F_f$ or $F_b$ (the selection strategy can vary, e.g., alternating turns, or based on the size of the frontiers).
Expand the selected node, generating successors (for forward search) or predecessors (for backward search).
Check if any of the newly generated nodes are present in the other* frontier. If a node is found in both $F_f$ and $F_b$, it means the two searches have met, and a path has been found.*
If no intersection is found, add the newly generated nodes to the respective frontier ($F_f$ for forward search, $F_b$ for backward search).

When an intersection occurs, and a common state $S_{meet}$ is found in both frontiers, a complete path from the initial state to the goal state can be constructed by concatenating the path from the initial state to $S_{meet}$ (found by the forward search) and the reversed path from the goal state to $S_{meet}$ (found by the backward search).

Reduced Complexity

Remark. Remark 22 (Reduced Complexity of Bidirectional Search). The primary advantage of bidirectional search is the potential for reduced time and space complexity. In a standard unidirectional search, if the solution is at depth $M$ and the branching factor is $b$, the search might explore up to $O(b^M)$ nodes in the worst case.

In contrast, bidirectional search aims to meet in the middle. Ideally, each of the forward and backward searches only needs to explore up to approximately half the depth, say $M/2$. If both searches explore roughly $O(b^{M/2})$ nodes, the total number of explored nodes becomes approximately $2 \times O(b^{M/2}) = O(b^{M/2})$, which is significantly less than $O(b^M)$ for larger values of $M$ and $b$.

Unidirectional Search (Worst Case): Complexity $\approx O(b^M)$ Bidirectional Search (Ideal Case): Complexity $\approx O(2 \cdot b^{M/2}) = O(b^{M/2})$ Where:

$b$ is the branching factor.
$M$ is the depth of the solution.

Note: The actual reduction in complexity depends on various factors, including the branching factor, the depth of the solution, and the efficiency of checking for intersection between the two frontiers. The $O(b^{M/2})$ complexity is an ideal case scenario.

To realize these complexity benefits, bidirectional search requires:

Reversible Actions: It must be possible to efficiently compute predecessors, meaning actions should be reversible to allow searching backward from the goal.
Efficient Intersection Check: A mechanism to efficiently check if a node generated by one search is also present in the frontier of the other search is needed. Hash tables or similar data structures can be used for quick lookups.
Strategy for Frontier Selection: A strategy to decide whether to expand from the forward or backward frontier at each step. Simple alternation or strategies based on frontier sizes can be used.

While bidirectional search offers a promising approach to reduce search complexity, its effectiveness is contingent on the problem structure and the feasibility of implementing backward search and efficient frontier intersection checks.

Introduction to Informed Search

While uninformed search strategies systematically explore the state space, they can be inefficient for large or complex problems because they do not leverage any knowledge about the location of the goal. Informed search strategies, also known as heuristic search, address this limitation by using additional information to guide the search process, making it more efficient and focused.

The Need for Heuristics

Heuristics are the cornerstone of informed search. In the context of search algorithms, a heuristic is a function that estimates the cost from the current state to the nearest goal state. This estimation allows the search algorithm to prioritize paths that seem more promising, i.e., those that are estimated to be closer to a goal.

In the context of informed search, a heuristic function $H(n)$ is:

An estimate of the cost of the cheapest path from the current state (node $n$) to a goal state.
Problem-specific: Heuristics are tailored to the particular search problem. A good heuristic leverages domain knowledge to make informed estimates.
Used to guide the search: By evaluating heuristics for different paths, the search algorithm can decide which paths are more promising and should be explored first.

A well-designed heuristic can significantly reduce the search space that needs to be explored, leading to faster and more efficient problem-solving.

Unlike uninformed search methods that explore blindly, informed search methods use heuristics to make more intelligent decisions about which paths to explore. This guidance is crucial for efficiently solving complex problems where the search space is vast. By using heuristic estimates, informed search algorithms aim to find solutions more directly, avoiding the exploration of less promising branches of the search space.

A* Search: Informed Search (Preview)

A* Search is a widely used and prototypical example of an informed search algorithm. It is an extension of Uniform Cost Search (UCS) that incorporates a heuristic function to improve efficiency. A* search is particularly effective in finding optimal solutions while significantly reducing the search space compared to uninformed methods.

Heuristic Function H(n): Estimating Distance to Goal

Definition 16 (Heuristic Function H(n) in A* Search). A* search enhances the node evaluation process by using a heuristic function, denoted as $H(n)$. For each node $n$, $H(n)$ calculates an estimated cost of the cheapest path from node $n$ to a goal state. It is important to note that $H(n)$ is an approximation and not the actual cost, as the true cost to the goal is generally unknown during the search.

For A* search to be both efficient and optimal, the heuristic function $H(n)$ should ideally be admissible.

Definition 17 (Admissible Heuristic). An admissible heuristic $H(n)$ is one that:

Never overestimates the actual cost to reach the goal. That is, $H(n) \leq h^*(n)$ for all nodes $n$, where $h^*(n)$ is the true cost of the optimal path from node $n$ to the nearest goal state.
Ensures that A* search, when using it, will find an optimal solution if one exists, provided that the heuristic is also consistent (a condition often, but not always, implied by admissibility, and to be discussed further).

Admissibility is a crucial property for heuristics used in A* search to guarantee optimality.

Airline Distance Heuristic for Romania Problem

Example 4 (Airline Distance Heuristic for Romania Problem). To illustrate the concept of a heuristic and admissibility, let’s revisit the Romania travel problem. For this problem, a useful heuristic is the airline distance (straight-line distance) from each city to Bucharest, the destination. Let $H(n)$ be the airline distance from city $n$ to Bucharest.

Why Airline Distance is a Heuristic: The airline distance provides an estimate of the remaining distance to Bucharest. It is based on geographical knowledge and is easy to calculate (or pre-calculate).
Admissibility of Airline Distance: The airline distance is an admissible heuristic because the straight-line distance between two points is always less than or equal to any actual road path distance between those points. In reality, roads are rarely straight and often involve detours, curves, and changes in elevation, making the road distance longer than the straight-line distance. Therefore, the airline distance never overestimates the actual shortest path distance by road.

*Airline Distances to Bucharest from Various Romanian Cities (Example Heuristic Values)*
*City*	*Airline distance to Bucharest*
Arad	366
Bucharest	0
Craiova	160
Fagaras	176
Lugoj	244
Mehadia	241
Neamt	234
Oradea	380
Pitesti	100
Rimnicu Vilcea	193
Sibiu	253
Timisoara	329
Urziceni	80
Vaslui	199
Zerind	374

Table 1 provides example airline distances from several Romanian cities to Bucharest. For instance, the airline distance from Arad to Bucharest is 366 km. Using this heuristic in A* search, when deciding which city to visit next from Arad, the algorithm would consider not only the cost to reach the current city (as in UCS) but also this heuristic estimate of the remaining distance to Bucharest. By incorporating the heuristic, A* search is guided to explore paths that are not only cheap in terms of accumulated cost but also appear to be closer to the goal, thus significantly improving search efficiency.

Conclusion

In this lecture, we have explored fundamental search algorithms essential for intelligent agents to solve problems by navigating through state spaces. We began by defining the components of a search problem, including state space, initial state, goal state, actions, transition model, and cost function. We then differentiated between state space graphs and search trees, highlighting the concept of node repetition in search trees and the potential for infinite search spaces.

We introduced the concept of systematic search and the frontier, which separates explored from unexplored states, providing a structured approach to search. We discussed the general tree search algorithm framework and then delved into several key uninformed search strategies:

Depth-First Search (DFS): Explores deeply along each path. Implemented using a LIFO queue (stack). Known for space efficiency but is incomplete and not optimal in general cases.
Breadth-First Search (BFS): Explores layer by layer. Implemented using a FIFO queue. Guaranteed to find the shortest path in terms of steps for uniform cost scenarios and is complete, but can be space-intensive.
Iterative Deepening Depth-First Search (ID-DFS): Combines DFS’s space efficiency with BFS’s completeness and optimality (for uniform costs) by iteratively deepening the search depth.
Uniform Cost Search (UCS): Expands nodes based on path cost, using a priority queue. Guarantees finding the least-cost path and is complete under certain conditions on step costs.
Best-First Search: A general framework unifying BFS, DFS, and UCS, where node expansion is guided by an evaluation function.

We also briefly touched upon Bidirectional Search as an optimization technique to reduce search complexity by simultaneously searching from the initial and goal states.

Looking ahead, the next lecture will transition to Informed Search Strategies, focusing on how to leverage heuristic information to guide search more efficiently. We previewed the A* search algorithm, a prime example of informed search, which uses a heuristic function to estimate the distance to the goal. The airline distance heuristic for the Romania problem was introduced as an example of an admissible heuristic, setting the stage for a deeper exploration of A* search and heuristic design in our next session.

This concludes our discussion on fundamental search algorithms for today. We will continue to build upon these concepts in the upcoming lectures.

--- title: "Lecture 5: Search Algorithms" author: "Your Name" date: "2025-02-10" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction ## Course Logistics and Questionnaire Welcome to the fifth lecture on Artificial Intelligence. Today's topic will be search algorithms. Please note that this lecture will conclude slightly earlier than usual, and we will forgo the break due to a scheduling conflict with a research committee meeting. Kindly ensure the door is closed to minimize external disturbances. Before we proceed, I would like to remind everyone to complete the course questionnaire. We observed a significant increase in submissions following the last reminder; however, some students present in the classroom have yet to participate. Your feedback is valuable, so if you have not already done so, please take a moment to complete the questionnaire at your earliest convenience. ## Review of Previous Lectures To set the stage for today's topic, let's briefly recap what we have covered in the initial lectures. We began with introductory discussions on the fundamental question: *What is Artificial Intelligence?* We explored its origins, historical evolution, and the various approaches that have shaped the field. ### Definition of AI and Agents A significant portion of our early discussions was dedicated to establishing a comprehensive definition of Artificial Intelligence. We aimed to move beyond superficial understandings and delve into the core principles that define intelligent systems. Furthermore, we introduced and elaborated on the concept of an *agent*, particularly *intelligent agents*. This notion is central to the study of AI, as it provides a framework for understanding how intelligent systems interact with their environment and pursue goals. The concept of agents and intelligent agents is foundational, and much of the subsequent material in this course, as reflected in the textbook, will build upon these ideas. ### Introduction to Search In our previous lecture, we initiated our exploration of *search* as a core topic in AI. We started to examine how agents can exhibit what we term, in a somewhat loose sense, \"intelligent\" behavior by employing search techniques. Specifically, we discussed how agents could find solutions or achieve goals by systematically exploring a *state space*. This lecture will directly continue from where we left off, delving deeper into search algorithms and strategies within state spaces. # Defining Search Problems In the realm of Artificial Intelligence, problem-solving often involves searching for a sequence of actions that lead to a desired goal. To formalize this process, we define a *search problem* through several key components. These components provide a structured way to represent and solve problems using search algorithms. ## Components of a Search Problem ::: definition **Definition 1** (Components of a Search Problem). *A search problem is formally defined by the following six elements, which collectively specify everything needed to formulate a problem for algorithmic solution:* 1. ***State Space** ($S$): This is the set of all possible configurations or situations that the agent can be in. Each element in $S$ is a *state*. The state space can be discrete or continuous, finite or infinite.* 2. ***Initial State**: This is the state in which the agent starts. It is the starting point of the search. There may be multiple possible initial states, but typically we consider a single, well-defined initial state for simplicity.* 3. ***Goal State(s)**: This defines the desired state or condition that the agent is trying to achieve. There can be one or more goal states. Often, for simplicity, we refer to a single goal state, but in general, it can be a set of states. The goal is what defines success in problem-solving.* 4. ***Actions** ($ADS$): For each state $s \in S$, there is a set of applicable actions, given by the function $ADS(s)$. These are the actions that can be executed by the agent when it is in state $s$. The actions define how the agent can move or change its state within the state space.* 5. ***Transition Model**: This describes the result of performing an action in a given state. In the simplest form, which we consider initially, the transition model is deterministic. This means that for each state $s$ and action $a \in ADS(s)$, the outcome is a single, uniquely determined next state. More complex scenarios might involve non-deterministic transition models, where an action could lead to multiple possible outcomes, each with a certain probability.* 6. ***Cost Function**: Each action has an associated cost, representing the 'expense' of performing that action. This cost can be measured in terms of time, resources, distance, or any other relevant metric. The path cost is the sum of the costs of the actions taken to reach a state. The objective in many search problems is to find a solution with the minimum total path cost, known as an *optimal solution*.* ::: ## Examples of Search Problems To better understand these components, let's consider a couple of illustrative examples. ### Romania Travel Problem ::: example **Example 1** (Romania Travel Problem). *The *Romania travel problem* is a classic example used to illustrate search algorithms. In this problem, the state space is defined by cities in Romania. The goal is to travel from a starting city, say Arad, to a destination city, Bucharest, by following a sequence of roads.* - ***States**: Cities in Romania (e.g., Arad, Bucharest, Sibiu, etc.).* - ***Initial State**: Arad.* - ***Goal State**: Bucharest.* - ***Actions**: Driving from one city to an adjacent city. For example, from Arad, possible actions are to drive to Sibiu, Timisoara, or Zerind.* - ***Transition Model**: Driving from city A to city B results in being in city B. This is deterministic.* - ***Cost Function**: The cost of each action (driving from one city to another) is the distance between the cities, typically measured in kilometers or miles. The objective is to find a sequence of cities to visit (path) that minimizes the total distance traveled from Arad to Bucharest.* *This example is particularly useful because it is intuitive and allows us to visualize the search process on a map. It is important to note that while this example involves geographical locations, the concept of state space search is far more general and not limited to physical spaces or trajectory planning.* ::: ### Vacuum Cleaner Robot ::: example **Example 2** (Vacuum Cleaner Robot). *Consider a simplified environment with two cells, where a vacuum cleaner robot needs to clean up dirt. This example illustrates that states can represent more than just physical locations; they can include properties of the environment.* - ***States**: A state is defined by the robot's location (cell 1 or cell 2) and the dirt status of each cell (dirty or clean). For instance, a state could be represented as (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty). There are $2 \times 2 \times 2 = 8$ possible states.* - ***Initial State**: Could be any state, for example, (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty).* - ***Goal State**: Any state where both cells are clean, regardless of the robot's location. For example, (Location=Cell 1, Cell 1=Clean, Cell 2=Clean) or (Location=Cell 2, Cell 1=Clean, Cell 2=Clean).* - ***Actions**:* - **Move Right*: Move from cell 1 to cell 2 (if in cell 1).* - **Move Left*: Move from cell 2 to cell 1 (if in cell 2).* - **Suck*: Clean dirt in the current cell.* - **NoOp*: Do nothing.* - ***Transition Model**: For example, in state (Location=Cell 1, Cell 1=Dirty, Cell 2=Dirty), performing *Suck* leads to (Location=Cell 1, Cell 1=Clean, Cell 2=Dirty).* - ***Cost Function**: Each action can have a cost, e.g., 1 for *Move Right* and *Move Left*, and 1 for *Suck*, and 0 for *NoOp*. The goal is to find a sequence of actions to reach a goal state with minimum cost.* *In this example, a state is not merely a position in physical space but an abstraction representing the robot's configuration and the environment's condition. This highlights the versatility of state space representation in search problems.* ::: ## State Space Graphs To visualize and analyze search problems, we use *state space graphs*. These graphs provide a graphical representation of the state space and the transitions between states. ### Nodes and States ::: definition **Definition 2** (Nodes and States in State Space Graphs). *In a state space graph, each **node** represents a **state** from the state space $S$. There is a direct, one-to-one correspondence between states and nodes. While it is formally correct to distinguish between a node in the graph and the state it represents, in practice, and for ease of discussion, we often use the terms interchangeably. Thus, we might say \"node Arad\" when we technically mean \"the node in the state space graph that corresponds to the state of being in Arad.\"* ::: ### Arcs and Actions ::: definition **Definition 3** (Arcs and Actions in State Space Graphs). *The **arcs** (or edges) in a state space graph represent the **actions** that allow transitions between states. A directed arc from node $A$ to node $B$ indicates that there is an action that can be performed in state $A$ to transition to state $B$. In a weighted state space graph, each arc is associated with a cost, representing the cost of the corresponding action.* ::: ### Solutions and Optimal Solutions ::: definition **Definition 4** (Solution in State Space Graphs). *A **solution** to a search problem, within the context of a state space graph, is a **path** from the node representing the initial state to a node representing a goal state. This path is a sequence of connected arcs in the graph.* ::: ::: definition **Definition 5** (Optimal Solution in State Space Graphs). *An **optimal solution** is a path from the initial state to a goal state that has the minimum total cost. The cost of a path is typically the sum of the costs of all arcs along the path. If all actions have a uniform cost (e.g., cost of 1 for each action), then the optimal solution is the path with the fewest arcs, i.e., the shortest path in terms of path length. However, when actions have varying costs, the optimal solution is the path with the minimum sum of these costs, not necessarily the one with the fewest steps. For the Romania travel problem, the state space graph is weighted, with the weights on the arcs representing the distances between connected cities. These distances, often given in miles in textbooks, serve as the cost for moving between cities.* ::: ## Search Trees While state space graphs represent the problem structure, *search trees* are used by search algorithms to explore potential solutions. A search tree is derived from the state space graph and represents the exploration process. ### Construction from State Space Graphs ::: definition **Definition 6** (Search Tree Construction). *A **search tree** is built starting from the initial state, which becomes the **root** of the tree. The process of building the tree involves **expanding** nodes. To expand a node means to consider the actions applicable in the state corresponding to that node and to generate the successor states. Each successor state becomes a child node in the search tree, connected to the parent node by an edge representing the action taken. This process is repeated level by level, exploring paths from the initial state towards potential goal states. The search tree essentially unfolds paths in the state space graph starting from the initial state.* ::: ### Node Repetition ::: remark **Remark 1** (Node Repetition in Search Trees). *A key difference between a state space graph and a search tree is that a single state (and thus, a single node in the state space graph) can appear multiple times in a search tree. This happens because there can be multiple paths leading to the same state. Consider a state space where state E can be reached from state S directly, and also through an intermediate state D. In the search tree, state E will appear as a child of S and potentially again as a descendant of D, even though in the state space graph, there is only one node for state E. Each occurrence of a node in the search tree represents a unique **path** from the initial state to the corresponding state in the state space graph.* ::: ### Representing Paths as Nodes ::: remark **Remark 2** (Paths as Nodes in Search Trees). *Each node in the search tree can be thought of as representing not just a state, but an entire **path** from the initial state to the current state in the state space graph. This is why a state can be repeated in the search tree -- each repetition corresponds to a different path to reach that state.* ::: ### Potential for Infinite Trees ::: remark **Remark 3** (Infinite Search Trees). *If the state space graph contains cycles, the search tree derived from it can be infinite. For example, if we have states S, A, and B, and transitions S $\rightarrow$ A, A $\rightarrow$ B, and B $\rightarrow$ A, starting from S, we can generate an infinite search tree with paths like S-A-B-A-B-A-\... and S-B-A-B-A-B-\... This is a crucial consideration for search algorithms, as naively exploring such a tree can lead to infinite loops and prevent finding a solution, even if one exists.* ::: <figure id="fig:state_space_search_tree"> <figcaption>Illustration of a State Space Graph and a corresponding partial Search Tree, showing node repetition. In the search tree, node ’A’ and ’B’ are repeated, representing different paths from the initial state ’S’.</figcaption> </figure> To manage potentially infinite search trees and avoid redundant exploration, it is crucial to keep track of the paths already explored and the states already visited. As the adage goes, \"Those who do not know history are destined to repeat it.\" In the context of search algorithms, this translates to: if we do not remember the paths we have already taken, we risk revisiting states and exploring redundant paths, leading to inefficiency or infinite loops. Effective search algorithms must therefore incorporate mechanisms to remember and utilize the history of the search process. # Systematic Search and the Frontier In the quest to build intelligent agents, it is crucial that these agents can find solutions to problems in a reliable and efficient manner. This necessitates the use of *systematic search* methods. Unlike random exploration, systematic search ensures that no part of the search space is overlooked, guaranteeing that a solution will be found if one exists within the explored space. ## The Need for Systematic Search Imagine an agent navigating a maze or searching for a specific file on a vast computer system. If the agent explores randomly, it might stumble upon the solution by chance, but there's no guarantee of success, especially in complex or infinite environments. **Systematic search** is essential because it provides a structured approach to explore the state space. By methodically examining states and transitions, we ensure that if a path to a goal exists, the search algorithm will eventually discover it. Consider a simple grid world example. If a goal is located at a finite distance from the starting point, a systematic search, such as exploring layer by layer, will eventually reach the goal. In contrast, a random walk might miss the goal entirely or take a highly inefficient path. Systematicity is particularly important in scenarios where solutions are not immediately obvious or where the search space is vast or even infinite. For instance, in automated planning or complex problem-solving tasks, a haphazard approach is unlikely to yield satisfactory results. Therefore, for an agent to be truly intelligent and effective, its search for solutions must be systematic and well-organized. ## The Frontier: Separating Explored and Unexplored States To implement systematic search, we introduce the concept of a *frontier*. The frontier is a crucial abstraction that helps us manage the search process by clearly delineating the boundary between the parts of the state space we have explored and those we have yet to examine. At any point during the search, we can categorize all nodes in the state space into three disjoint sets: ### Expanded Nodes (Explored Set) ::: definition **Definition 7** (Expanded Nodes (Explored Set)). ***Expanded nodes**, also referred to as the *explored set*, are the states that the search algorithm has already processed and explored. When we \"expand\" a node, we generate its successors and evaluate them. In the lecture's visual examples, these nodes are depicted in violet. Essentially, these are the states for which we have already determined the next possible steps and added them to our list of states to consider further.* ::: ### Frontier Nodes (Pending Exploration) ::: definition **Definition 8** (Frontier Nodes (Pending Exploration)). ***Frontier nodes** represent the current boundary of our exploration. These are the states that we have discovered and know about, but have not yet explored in detail. They are \"on the edge\" of the explored region, waiting to be selected for expansion. In the visual analogy, these are shown in green. The frontier is the set of nodes that are candidates for the next step of expansion. It acts as a buffer between the explored and unexplored regions of the state space.* ::: ### Unexplored Nodes (Unseen States) ::: definition **Definition 9** (Unexplored Nodes (Unseen States)). ***Unexplored nodes** are all the states in the state space that the search algorithm has not yet encountered or considered. These are the vast, unknown parts of the state space that lie beyond the frontier. In our visual representation, these are in grey. These states have not yet been generated or added to the frontier.* ::: The process of **expanding a node** from the frontier is the core operation in systematic search. When we expand a node: 1. We move it from the *frontier set* to the *expanded set*, signifying that we have now fully processed this state. 2. We examine the state to determine the possible actions and resulting next states (successors). 3. For each successor state, if it is a new state (i.e., not already in the expanded set or the frontier), we add it to the *frontier set*. This expansion process ensures that the frontier always represents the interface between the explored and unexplored parts of the state space. By systematically selecting and expanding nodes from the frontier, search algorithms can methodically explore the state space and find solutions. ## A General Tree Search Algorithm To formalize the concept of systematic search using the frontier, we can define a general tree search algorithm. Algorithm [\[alg:tree_search\]](#alg:tree_search){reference-type="ref" reference="alg:tree_search"} presents a pseudo-code outline for such an algorithm. ::::: algorithm ::: tcolorbox **Objective:** Find a solution path from an initial state to a goal state in a search problem. **Input:** - `problem`: Definition of the search problem, including the initial state, goal state(s), actions, transition model, and cost function. - `strategy`: A strategy that dictates how to choose the next node to expand from the frontier. Different strategies lead to different search algorithms (e.g., Depth-First, Breadth-First, Uniform Cost). **Output:** A solution path (sequence of actions) if a goal state is reachable, or `failure` if no solution is found. ::: ::: algorithmic Initialize the *frontier* using the `initial state` of the `problem`. This often involves creating a node representing the initial state and adding it to the frontier. `failure` `node` $\leftarrow$ **if** `node` is a `goal state` **then** Expand `node`, generating its successors. Add successors to the *frontier* if they are not already in the *frontier* or *expanded set*. Add `node` to the *expanded set*. ::: ::::: This `Tree-Search` algorithm provides a high-level framework for various search algorithms. It takes a problem definition and a search strategy as input. The algorithm begins by initializing the frontier with the initial state. Then, it enters a loop that continues until a solution is found or the frontier becomes empty. Inside the loop: - **Check for Empty Frontier:** It first checks if the frontier is empty. If it is, it means there are no more states to explore, and the algorithm returns `failure`, indicating that no solution was found in the explored search space. - **Node Selection:** If the frontier is not empty, the algorithm selects a node from the frontier using a `strategy`. This `strategy` is a crucial parameter that differentiates various search algorithms. For example, different strategies will dictate whether to explore deeper paths first or broader paths first, or paths with lower costs. - **Goal Test:** The selected `node` is then checked to see if it represents a goal state. If it is a goal state, the algorithm has found a solution and returns the solution path, which is typically reconstructed by tracing back from the goal node to the initial node, keeping track of the parent pointers or actions taken to reach each state. - **Node Expansion:** If the selected `node` is not a goal state, it is **expanded**. This involves generating all possible successor states reachable from the current state through applicable actions, as defined by the problem's transition model. - **Frontier Update:** The newly generated successor nodes are added to the *frontier*, provided they meet certain conditions (e.g., not already explored or in the frontier, depending on whether we are doing tree search or graph search). The expanded `node` is then moved to the *expanded set* to keep track of visited states and prevent redundant exploration in some search variants. The efficiency and characteristics of different search algorithms derived from this framework depend heavily on the `strategy` used to select nodes from the frontier. In the following sections, we will explore several uninformed search strategies, which vary in how they implement this node selection process, and analyze their properties. **Complexity Analysis:** The time and space complexity of this general tree search algorithm are highly dependent on the specific search strategy and the properties of the state space. In the worst case, for tree search without cycle detection, the algorithm might explore paths of exponential length relative to the depth of the search space. For graph search (which avoids repeated states), the complexity is often related to the size of the state space itself and the branching factor. Specific complexity analyses will be provided when we discuss concrete search strategies like Breadth-First Search, Depth-First Search, and Uniform Cost Search. # Uninformed Search Strategies Informed search strategies are essential for navigating state spaces when we lack specific information about the location of the goal. These methods, also known as blind search strategies, explore the state space based solely on the problem definition, without any heuristic guidance about which paths are more promising. We will now delve into several fundamental uninformed search algorithms: Depth-First Search (DFS), Breadth-First Search (BFS), Iterative Deepening Depth-First Search (ID-DFS), and Uniform Cost Search (UCS). ## Depth-First Search (DFS) *Depth-First Search (DFS)* is a strategy that explores the state space by always expanding the deepest node in the current frontier. It proceeds as far as possible along each branch before backtracking. Imagine exploring a maze; DFS is like choosing a path and following it to the end, and if you reach a dead end, you backtrack to the last decision point and try another path. ### LIFO Queue (Stack) Implementation ::: definition **Definition 10** (DFS Implementation using LIFO Queue). *DFS is typically implemented using a Last-In-First-Out (LIFO) queue, commonly known as a **stack**, to manage the frontier. When a node is expanded, its successors are added to the top of the stack. The algorithm then picks the node from the top of the stack to expand next. This LIFO structure ensures that the search explores deeper into the tree whenever possible.* ::: ### Properties of DFS: Completeness, Optimality, Complexity To evaluate search algorithms, we consider several key properties: completeness, optimality, time complexity, and space complexity. For DFS: - **Completeness:** ::: remark **Remark 4** (Completeness of DFS). *DFS is **not complete** in infinite state spaces or in state spaces with cycles. In such scenarios, DFS can follow an infinite path and never return to explore other parts of the state space, potentially missing goal states. If the state space is finite and we implement cycle detection (i.e., avoid revisiting states), DFS is complete. However, without cycle detection in a cyclic graph, it can fail to find a solution even if one exists.* ::: - **Optimality:** ::: remark **Remark 5** (Optimality of DFS). *DFS is **not optimal**. It explores paths deeply and may find a goal state that is far from the initial state in terms of path cost, even if shorter paths to goal states exist. DFS prioritizes depth over cost, so the first solution it finds is not guaranteed to be the optimal one.* ::: - **Time Complexity:** ::: remark **Remark 6** (Time Complexity of DFS). *In the worst case, DFS can explore the entire search tree. For a state space with a maximum depth $m$ and branching factor $b$, the time complexity of DFS is $O(b^m)$. In the worst case, it might explore all paths up to depth $m$. However, if DFS happens to stumble upon a solution early in a deep path, it can be much faster.* ::: - **Space Complexity:** ::: remark **Remark 7** (Space Complexity of DFS). *DFS has a space complexity of $O(b \cdot m)$, where $m$ is the maximum depth of the search tree. This is because DFS only needs to store the current path from the root to the deepest node in the frontier, along with the unexpanded siblings for each node on the path. This makes DFS space-efficient compared to BFS, especially for large search spaces with deep solutions.* ::: ## Breadth-First Search (BFS) *Breadth-First Search (BFS)* systematically explores the state space layer by layer. It expands all nodes at the current depth before moving on to nodes at the next depth level. BFS is like exploring a maze by examining all possible paths of length 1, then all possible paths of length 2, and so on, until a solution is found. ### FIFO Queue Implementation ::: definition **Definition 11** (BFS Implementation using FIFO Queue). *BFS is implemented using a First-In-First-Out (FIFO) queue to manage the frontier. When a node is expanded, its successors are added to the back of the queue. The algorithm always selects the node from the front of the queue to expand next. This FIFO structure ensures that nodes are explored in the order of their depth from the starting node.* ::: ### Properties of BFS: Completeness, Optimality, Complexity For BFS, the properties are as follows: - **Completeness:** ::: remark **Remark 8** (Completeness of BFS). *BFS is **complete** for finite state spaces. If a solution exists, BFS is guaranteed to find it. For infinite state spaces, BFS is complete if there is a solution at a finite depth (i.e., a finite number of steps from the initial state). If a solution exists at some finite depth $d$, BFS will find it.* ::: - **Optimality:** ::: theorem **Theorem 1** (Optimality of BFS for Uniform Costs). *BFS is **optimal** if all step costs are uniform (i.e., each action has the same cost, typically considered as 1). In this case, BFS finds the solution with the shortest path in terms of the number of steps (path length). However, if step costs are not uniform, BFS is not guaranteed to find the least-cost solution. It will still find a solution with the minimum number of steps, but not necessarily the minimum total cost.* ::: - **Time Complexity:** ::: remark **Remark 9** (Time Complexity of BFS). *In the worst case, BFS explores all nodes at depth up to the depth of the shallowest goal state. If the shallowest goal is at depth $d$, and the branching factor is $b$, BFS may explore $1 + b + b^2 + \dots + b^d = O(b^d)$ nodes. Thus, the time complexity is $O(b^d)$.* ::: - **Space Complexity:** ::: remark **Remark 10** (Space Complexity of BFS). *BFS must keep all nodes at the current depth in memory to explore their children in the next step. In the worst case, if the shallowest goal is at depth $d$, BFS stores all nodes at depth $d-1$ in the frontier, leading to a space complexity of $O(b^d)$. Space is often the limiting factor for BFS, as the number of nodes at each level grows exponentially.* ::: ### Comparison of BFS and DFS ::: remark **Remark 11** (Comparison of BFS and DFS). *The choice between BFS and DFS depends on the problem characteristics and priorities:* - ***When to use BFS:** BFS is preferred when the solution is expected to be at a shallow depth in the search tree, or when finding the shortest path (in terms of steps) is crucial and step costs are uniform. BFS is also favored when completeness is a must,and we need to guarantee finding a solution if one exists in a finite state space.* - ***When to use DFS:** DFS can be more efficient in terms of space and time if solutions are known to be deep in the search tree, or if only one solution is needed and optimality is not a concern. DFS might also be suitable when the search space is very large, but there's a good chance of finding a solution by exploring a deep path early on. However, DFS risks getting lost in infinite paths and is not guaranteed to find the shortest path.* ::: ## Iterative Deepening Depth-First Search (ID-DFS) *Iterative Deepening Depth-First Search (ID-DFS)* aims to combine the space efficiency of DFS with the completeness and optimality (for uniform costs) of BFS. ID-DFS performs a sequence of DFS searches, each with a progressively increasing depth limit. ### Combining DFS and BFS for Efficiency ::: remark **Remark 12** (Iterative Deepening Process of ID-DFS). *ID-DFS works as follows:* 1. *Perform DFS to depth limit 0 (only root node).* 2. *If no solution is found, perform DFS to depth limit 1.* 3. *If no solution is found, perform DFS to depth limit 2.* 4. *Continue increasing the depth limit by one at each iteration until a goal is found.* *In each iteration, ID-DFS starts from the initial state and explores in a depth-first manner, but it cuts off the search at the current depth limit. This iterative process ensures that the algorithm explores the search space in layers, similar to BFS, but using DFS for each layer.* ::: ### Completeness and Optimality of Iterative Deepening ID-DFS inherits the desirable properties of both BFS and DFS to some extent: - **Completeness:** ::: remark **Remark 13** (Completeness of ID-DFS). *ID-DFS is **complete** in finite state spaces and for state spaces with solutions at finite depth. Because it explores layer by layer, it will eventually reach any reachable goal state, similar to BFS.* ::: - **Optimality:** ::: theorem **Theorem 2** (Optimality of ID-DFS for Uniform Costs). *ID-DFS is **optimal** when step costs are uniform, just like BFS. It finds the shallowest goal state, which corresponds to the least number of steps in uniform cost scenarios.* ::: - **Time Complexity:** ::: remark **Remark 14** (Time Complexity of ID-DFS). *Although ID-DFS repeats searches at shallower depths, the total time complexity remains comparable to BFS. For a branching factor $b$ and solution depth $d$, the number of nodes expanded in ID-DFS is approximately $O(b^d)$. The re-exploration of shallower nodes is not as computationally expensive as it might first appear because the number of nodes at each depth level grows exponentially. Most of the nodes are at the deepest level explored.* ::: - **Space Complexity:** ::: remark **Remark 15** (Space Complexity of ID-DFS). *ID-DFS has the space complexity of DFS, which is $O(b \cdot d)$, where $d$ is the depth of the solution. In each iteration, it performs a DFS, and the space required is only for the current path being explored. This is a significant advantage over BFS, especially for problems with large search spaces and deeper solutions.* ::: ::: remark **Remark 16** (Use Cases for ID-DFS). *ID-DFS is often preferred in scenarios where space is a constraint and optimality (for uniform costs) is desired. It effectively balances the benefits of BFS and DFS.* ::: ## Uniform Cost Search (UCS) *Uniform Cost Search (UCS)*, also known as Dijkstra's algorithm, is an uninformed search algorithm that expands nodes based on the cost of the path from the start node to the current node. UCS is designed to find the least-cost path to a goal, making it optimal for problems with varying step costs. ### Dijkstra's Algorithm in AI ::: remark **Remark 17** (UCS and Dijkstra's Algorithm). *In the field of computer science, particularly in algorithms and graph theory, UCS is recognized as Dijkstra's algorithm. In the context of Artificial Intelligence search, it is often referred to as Uniform Cost Search, emphasizing its strategy of expanding nodes in order of their path cost uniformity.* ::: ### Cost Function G(n): Path Cost ::: definition **Definition 12** (Path Cost Function G(n) in UCS). *UCS uses a cost function, denoted as $G(n)$, which represents the accumulated cost of the path from the initial state to reach node $n$. For the initial state, $G(\text{initial state}) = 0$. For any successor $n'$ of node $n$ reached by action $a$ with cost $c(n, a, n')$, the path cost is updated as $G(n') = G(n) + c(n, a, n')$.* ::: ### Priority Queue Implementation ::: definition **Definition 13** (UCS Implementation using Priority Queue). *UCS employs a **priority queue** to manage the frontier. The priority queue orders nodes based on their $G(n)$ values. At each step, UCS selects the node from the frontier that has the lowest $G(n)$ value for expansion. This ensures that paths with lower costs are explored first.* ::: ### Properties of UCS: Completeness, Optimality, Complexity The properties of UCS are crucial for understanding its applicability and performance: - **Completeness:** ::: theorem **Theorem 3** (Completeness of UCS). *UCS is **complete** under the condition that the cost of every step is greater than some small positive constant $\epsilon > 0$. This condition ensures that the path costs increase monotonically and prevents infinite paths with zero or near-zero costs from being explored indefinitely. If there is a solution, UCS is guaranteed to find it.* ::: - **Optimality:** ::: theorem **Theorem 4** (Optimality of UCS). *UCS is **optimal**. It always finds the least-cost path to a goal state. Because it expands nodes in order of increasing path cost, the first time UCS reaches a goal state, it is guaranteed to have done so via the cheapest path.* ::: - **Time Complexity:** ::: remark **Remark 18** (Time Complexity of UCS). *The time complexity of UCS is related to the cost of the optimal solution, let's say $C^*$, and the minimum step cost, $\epsilon$. In the worst case, UCS might explore all nodes with path cost less than or equal to $C^*$. If we consider the 'effective depth' in terms of cost as $C^*/\epsilon$ and branching factor $b$, the time complexity can be roughly approximated as $O(b^{C^*/\epsilon})$. In practice, it is often described in terms of the number of nodes whose path cost is less than the cost of the optimal solution.* ::: - **Space Complexity:** ::: remark **Remark 19** (Space Complexity of UCS). *Similar to time complexity, the space complexity is also related to the number of nodes explored, which can be in the order of $O(b^{C^*/\epsilon})$ in the worst case, as UCS needs to store all nodes in the frontier.* ::: ### Water Maze Example: BFS vs. UCS ::: example **Example 3** (Water Maze Example: BFS vs. UCS). *Consider a water maze where different regions have varying depths, representing different costs for movement. In a shallow region, moving one step might cost 1 unit, while in a deep region, it might cost 2 units.* - ***BFS in Water Maze:** BFS would explore the maze uniformly in all directions, expanding layer by layer based on the number of steps. It would find a path with the fewest steps, regardless of the cost associated with each step. In the water maze example, BFS might lead the robot through deeper, more costly regions if that path happens to have fewer steps.* - ***UCS in Water Maze:** UCS, on the other hand, would prioritize paths through shallower, less costly regions. It expands nodes based on the accumulated cost, so it would prefer to move through shallow water even if it means taking a slightly longer path in terms of steps. UCS is guaranteed to find a path that minimizes the total 'effort' or cost, which is more relevant when actions have different costs.* *In scenarios with varying action costs, UCS is generally more appropriate than BFS if the goal is to minimize the total cost, not just the number of steps. BFS is only optimal when all step costs are uniform.* ::: ## Best-First Search: A General Framework *Best-First Search* is not a specific algorithm but rather a conceptual framework that encompasses several search algorithms, including BFS, DFS, and UCS, as special cases. The core idea of Best-First Search is to expand nodes based on an evaluation function that estimates the \"desirability\" of each node. ### Using a Cost Function F(n) ::: definition **Definition 14** (Evaluation Function F(n) in Best-First Search). *Best-First Search uses a generic evaluation function, $F(n)$, to determine the order in which nodes in the frontier are expanded. At each step, the algorithm selects the node $n$ from the frontier for which $F(n)$ is minimum (or maximum, depending on the definition of 'best'). The function $F(n)$ is designed to estimate how promising each node is, guiding the search towards potentially better paths.* ::: ### BFS, DFS, and UCS as Best-First Search Instances ::: remark **Remark 20** (BFS, DFS, and UCS as Best-First Search Instances). *Different choices for the evaluation function $F(n)$ in Best-First Search lead to different search algorithms:* - ***BFS as Best-First Search:** In BFS, we prioritize nodes based on their depth. We can define $F(n) = \text{Depth}(n)$. By minimizing $F(n)$, we are effectively choosing to expand the shallowest nodes first, which is exactly what BFS does.* - ***DFS as Best-First Search:** In DFS, we prioritize deeper exploration. We can define $F(n) = -\text{Depth}(n)$. By minimizing $F(n)$ (which is equivalent to maximizing $-\text{Depth}(n)$ or maximizing $\text{Depth}(n)$ in terms of absolute value), we prioritize expanding the deepest nodes, thus mimicking DFS behavior.* - ***UCS as Best-First Search:** In UCS, we prioritize nodes based on their path cost from the start node, $G(n)$. We can set $F(n) = G(n)$. By minimizing $F(n)$, we are selecting nodes with the lowest path cost to expand, which is the core strategy of UCS.* *Thus, BFS, DFS, and UCS can all be viewed as instances of Best-First Search, each employing a different evaluation function to guide the search process. This perspective highlights the underlying common structure of these algorithms and how their behavior is determined by the node selection strategy defined through the evaluation function. The textbook may indeed introduce Best-First Search as a general algorithm first, and then present BFS, DFS, and UCS as specific implementations derived by choosing particular evaluation functions.* ::: # Optimizing Search To enhance the efficiency of search algorithms, various optimization techniques have been developed. One notable approach is *Bidirectional Search*, which aims to reduce the search effort by simultaneously exploring from both the start and goal states. ## Bidirectional Search *Bidirectional Search* is an optimization technique designed to speed up the search process by running two simultaneous searches: one forward from the initial state and one backward from the goal state. The idea is to meet in the middle, hoping to find the solution faster than searching in a single direction. ### Forward and Backward Search ::: definition **Definition 15** (Forward and Backward Search in Bidirectional Search). *Traditional search algorithms, like those discussed so far, operate by searching forward from the **initial state** towards the **goal state**. **Bidirectional search** enhances this by concurrently initiating a second search process that operates **backward** from the **goal state** towards the **initial state**.* - ***Forward Search**: This search starts at the initial state and explores the state space in the usual direction, moving from predecessors to successors.* - ***Backward Search**: This search starts at the goal state and explores in reverse, moving from successors to predecessors. To perform a backward search, we need to be able to determine the predecessors of each state, which requires reversible actions. In some problems, reversing actions might be straightforward, while in others, it may require more complex inverse operations or might not be possible at all.* *The process continues until the two search frontiers meet. When a state is reached that has been explored by both the forward and backward searches, a path from the initial state to the goal state has been found.* ::: ### Mechanism of Bidirectional Search ::: remark **Remark 21** (Mechanism of Bidirectional Search). *To implement bidirectional search, we need to manage two frontiers:* - ***Forward Frontier** ($F_f$): This frontier is used by the forward search, starting from the initial state. It contains nodes to be expanded in the forward direction.* - ***Backward Frontier** ($F_b$): This frontier is used by the backward search, starting from the goal state(s). It contains nodes to be expanded in the backward direction.* *The algorithm proceeds in steps, typically alternating between expanding a node from the forward frontier and a node from the backward frontier. In each step, we:* 1. *Select a node from either $F_f$ or $F_b$ (the selection strategy can vary, e.g., alternating turns, or based on the size of the frontiers).* 2. *Expand the selected node, generating successors (for forward search) or predecessors (for backward search).* 3. *Check if any of the newly generated nodes are present in the *other* frontier. If a node is found in both $F_f$ and $F_b$, it means the two searches have met, and a path has been found.* 4. *If no intersection is found, add the newly generated nodes to the respective frontier ($F_f$ for forward search, $F_b$ for backward search).* *When an intersection occurs, and a common state $S_{meet}$ is found in both frontiers, a complete path from the initial state to the goal state can be constructed by concatenating the path from the initial state to $S_{meet}$ (found by the forward search) and the reversed path from the goal state to $S_{meet}$ (found by the backward search).* ::: ### Reduced Complexity :::: remark **Remark 22** (Reduced Complexity of Bidirectional Search). *The primary advantage of bidirectional search is the potential for reduced time and space complexity. In a standard unidirectional search, if the solution is at depth $M$ and the branching factor is $b$, the search might explore up to $O(b^M)$ nodes in the worst case.* *In contrast, bidirectional search aims to meet in the middle. Ideally, each of the forward and backward searches only needs to explore up to approximately half the depth, say $M/2$. If both searches explore roughly $O(b^{M/2})$ nodes, the total number of explored nodes becomes approximately $2 \times O(b^{M/2}) = O(b^{M/2})$, which is significantly less than $O(b^M)$ for larger values of $M$ and $b$.* ::: tcolorbox ***Unidirectional Search (Worst Case):** Complexity $\approx O(b^M)$ **Bidirectional Search (Ideal Case):** Complexity $\approx O(2 \cdot b^{M/2}) = O(b^{M/2})$ Where:* - *$b$ is the branching factor.* - *$M$ is the depth of the solution.* ***Note:** The actual reduction in complexity depends on various factors, including the branching factor, the depth of the solution, and the efficiency of checking for intersection between the two frontiers. The $O(b^{M/2})$ complexity is an ideal case scenario.* ::: *To realize these complexity benefits, bidirectional search requires:* - ***Reversible Actions**: It must be possible to efficiently compute predecessors, meaning actions should be reversible to allow searching backward from the goal.* - ***Efficient Intersection Check**: A mechanism to efficiently check if a node generated by one search is also present in the frontier of the other search is needed. Hash tables or similar data structures can be used for quick lookups.* - ***Strategy for Frontier Selection**: A strategy to decide whether to expand from the forward or backward frontier at each step. Simple alternation or strategies based on frontier sizes can be used.* *While bidirectional search offers a promising approach to reduce search complexity, its effectiveness is contingent on the problem structure and the feasibility of implementing backward search and efficient frontier intersection checks.* :::: # Introduction to Informed Search While uninformed search strategies systematically explore the state space, they can be inefficient for large or complex problems because they do not leverage any knowledge about the location of the goal. *Informed search strategies*, also known as heuristic search, address this limitation by using additional information to guide the search process, making it more efficient and focused. ## The Need for Heuristics **Heuristics** are the cornerstone of informed search. In the context of search algorithms, a heuristic is a function that estimates the cost from the current state to the nearest goal state. This estimation allows the search algorithm to prioritize paths that seem more promising, i.e., those that are estimated to be closer to a goal. ::: tcolorbox In the context of informed search, a **heuristic function** $H(n)$ is: - An **estimate** of the cost of the cheapest path from the current state (node $n$) to a goal state. - **Problem-specific**: Heuristics are tailored to the particular search problem. A good heuristic leverages domain knowledge to make informed estimates. - Used to **guide the search**: By evaluating heuristics for different paths, the search algorithm can decide which paths are more promising and should be explored first. A well-designed heuristic can significantly reduce the search space that needs to be explored, leading to faster and more efficient problem-solving. ::: Unlike uninformed search methods that explore blindly, informed search methods use heuristics to make more intelligent decisions about which paths to explore. This guidance is crucial for efficiently solving complex problems where the search space is vast. By using heuristic estimates, informed search algorithms aim to find solutions more directly, avoiding the exploration of less promising branches of the search space. ## A\* Search: Informed Search (Preview) *A\* Search* is a widely used and prototypical example of an informed search algorithm. It is an extension of Uniform Cost Search (UCS) that incorporates a heuristic function to improve efficiency. A\* search is particularly effective in finding optimal solutions while significantly reducing the search space compared to uninformed methods. ### Heuristic Function H(n): Estimating Distance to Goal ::: definition **Definition 16** (Heuristic Function H(n) in A\* Search). *A\* search enhances the node evaluation process by using a heuristic function, denoted as $H(n)$. For each node $n$, $H(n)$ calculates an estimated cost of the cheapest path from node $n$ to a goal state. It is important to note that $H(n)$ is an **approximation** and not the actual cost, as the true cost to the goal is generally unknown during the search.* *For A\* search to be both efficient and optimal, the heuristic function $H(n)$ should ideally be **admissible**.* ::: :::: tcolorbox ::: definition **Definition 17** (Admissible Heuristic). *An admissible heuristic $H(n)$ is one that:* - ***Never overestimates** the actual cost to reach the goal. That is, $H(n) \leq h^*(n)$ for all nodes $n$, where $h^*(n)$ is the true cost of the optimal path from node $n$ to the nearest goal state.* - *Ensures that A\* search, when using it, will find an **optimal solution** if one exists, provided that the heuristic is also consistent (a condition often, but not always, implied by admissibility, and to be discussed further).* *Admissibility is a crucial property for heuristics used in A\* search to guarantee optimality.* ::: :::: ### Airline Distance Heuristic for Romania Problem :::: example **Example 4** (Airline Distance Heuristic for Romania Problem). *To illustrate the concept of a heuristic and admissibility, let's revisit the Romania travel problem. For this problem, a useful heuristic is the **airline distance** (straight-line distance) from each city to Bucharest, the destination. Let $H(n)$ be the airline distance from city $n$ to Bucharest.* - ***Why Airline Distance is a Heuristic**: The airline distance provides an estimate of the remaining distance to Bucharest. It is based on geographical knowledge and is easy to calculate (or pre-calculate).* - ***Admissibility of Airline Distance**: The airline distance is an admissible heuristic because the straight-line distance between two points is always less than or equal to any actual road path distance between those points. In reality, roads are rarely straight and often involve detours, curves, and changes in elevation, making the road distance longer than the straight-line distance. Therefore, the airline distance never overestimates the actual shortest path distance by road.* ::: tab:airline_distances ***City*** ***Airline distance to Bucharest*** ------------------ ------------------------------------- *Arad* *366* *Bucharest* *0* *Craiova* *160* *Fagaras* *176* *Lugoj* *244* *Mehadia* *241* *Neamt* *234* *Oradea* *380* *Pitesti* *100* *Rimnicu Vilcea* *193* *Sibiu* *253* *Timisoara* *329* *Urziceni* *80* *Vaslui* *199* *Zerind* *374* : *Airline Distances to Bucharest from Various Romanian Cities (Example Heuristic Values)* ::: *Table [1](#tab:airline_distances){reference-type="ref" reference="tab:airline_distances"} provides example airline distances from several Romanian cities to Bucharest. For instance, the airline distance from Arad to Bucharest is 366 km. Using this heuristic in A\* search, when deciding which city to visit next from Arad, the algorithm would consider not only the cost to reach the current city (as in UCS) but also this heuristic estimate of the remaining distance to Bucharest. By incorporating the heuristic, A\* search is guided to explore paths that are not only cheap in terms of accumulated cost but also appear to be closer to the goal, thus significantly improving search efficiency.* :::: # Conclusion In this lecture, we have explored fundamental search algorithms essential for intelligent agents to solve problems by navigating through state spaces. We began by defining the components of a search problem, including state space, initial state, goal state, actions, transition model, and cost function. We then differentiated between state space graphs and search trees, highlighting the concept of node repetition in search trees and the potential for infinite search spaces. We introduced the concept of systematic search and the frontier, which separates explored from unexplored states, providing a structured approach to search. We discussed the general tree search algorithm framework and then delved into several key *uninformed search strategies*: - **Depth-First Search (DFS)**: Explores deeply along each path. Implemented using a LIFO queue (stack). Known for space efficiency but is incomplete and not optimal in general cases. - **Breadth-First Search (BFS)**: Explores layer by layer. Implemented using a FIFO queue. Guaranteed to find the shortest path in terms of steps for uniform cost scenarios and is complete, but can be space-intensive. - **Iterative Deepening Depth-First Search (ID-DFS)**: Combines DFS's space efficiency with BFS's completeness and optimality (for uniform costs) by iteratively deepening the search depth. - **Uniform Cost Search (UCS)**: Expands nodes based on path cost, using a priority queue. Guarantees finding the least-cost path and is complete under certain conditions on step costs. - **Best-First Search**: A general framework unifying BFS, DFS, and UCS, where node expansion is guided by an evaluation function. We also briefly touched upon **Bidirectional Search** as an optimization technique to reduce search complexity by simultaneously searching from the initial and goal states. Looking ahead, the next lecture will transition to **Informed Search Strategies**, focusing on how to leverage heuristic information to guide search more efficiently. We previewed the **A\* search algorithm**, a prime example of informed search, which uses a heuristic function to estimate the distance to the goal. The *airline distance* heuristic for the Romania problem was introduced as an example of an admissible heuristic, setting the stage for a deeper exploration of A\* search and heuristic design in our next session. This concludes our discussion on fundamental search algorithms for today. We will continue to build upon these concepts in the upcoming lectures.