CampusLearn
← CSC 315 Artificial Intelligence

Informed Search Strategies and Heuristics

Notes

Introduction to Search in Artificial Intelligence Search algorithms form the foundational problem-solving paradigm in classical artificial intelligence. When an agent lacks direct procedural knowledge to achieve a specific goal, it explores a state space. A state space comprises an initial state, a set of viable actions defined by a transition model, a goal test function, and a path cost. Uninformed search strategies, such as Breadth-First Search and Depth-First Search, traverse state graphs systematically without domain knowledge. Conversely, informed or heuristic search strategies utilize domain-specific insights to assess which non-goal state is most promising to expand, dramatically pruning the search frontier. The A* Search Algorithm A* search represents the benchmark of informed search strategies. It assesses candidate nodes using an evaluation function f(n) = g(n) + h(n). In this formulation, g(n) measures the exact cumulative cost incurred from the start state to the current node n, while h(n) represents an estimated cost from node n to the nearest goal state. For tree search, A* is mathematically guaranteed to be optimal and complete if the heuristic function h(n) is admissible, meaning it never overestimates the true remaining cost to achieve the goal. In graph search, where nodes may be revisited through distinct paths, the heuristic must additionally satisfy consistency, also known as the triangle inequality constraint. Practical example Consider an intelligent navigation agent designed to route commuter matatus across Nairobi County from Nairobi Central Business District to Ongata Rongai during peak traffic hours. The state space consists of road intersections including Nyayo Stadium, Bomas of Kenya, Galleria Mall, Langata Road junctions, and Magadi Road. The initial state is Nairobi CBD, and the goal state is Ongata Rongai Tuskys Stage. The cost function g(n) records actual travel time accumulated in minutes, considering known road bottlenecks. The heuristic function h(n) uses straight-line Euclidean distance divided by the legal maximum speed limit of eighty kilometers per hour, providing an admissible and consistent estimate because real road transit cannot be faster than direct flight speed. Suppose the agent evaluates two frontiers at Bomas of Kenya: Branch A via Magadi Road has an accumulated g(n) of 45 minutes and an estimated h(n) of 20 minutes, yielding f(n) of 65 minutes. Branch B via Langata South Road towards Karen has an accumulated g(n) of 50 minutes but an estimated h(n) of 25 minutes, yielding f(n) of 75 minutes. A* prioritizes expanding Branch A. If heavy gridlock at Maasai Lodge raises Magadi Road costs such that f(n) exceeds 75, A* dynamically switches exploration to the Karen detour, ensuring optimal arrival time.

Quiz

1. In the evaluation function f(n) = g(n) + h(n), what does g(n) represent?

2. What condition must a heuristic function satisfy to guarantee optimal solutions in A* tree search?

3. In the Nairobi navigation example, why is straight-line distance divided by maximum speed considered an admissible heuristic?

Sign in to submit and securely grade your quiz.