3. Problem Solving Through Search

Introduction ¹

• The purpose of the agent can be thought of as a problem solver.
• Problem solving can be represented as a “search” for a solution; that is, searching through a space of possible solutions (graph space).
• The basic idea behind an uninformed search is that the graph or ‘tree’ is searched methodically without any knowledge of or regard for the location of the actual goal.
• If we have some additional information beyond the set of nodes that make up the tree that would make our searching more efficient, we would refer to this as an informed search or what is typically called a Heuristic.

Lowest-cost-first search

• The basic idea of a Heuristic search is that you use information that you have about the space (tree or graph) that you are searching to improve the efficiency of the search.
• A Heuristic might be employed, for example, to decide how nodes are added to a tree such that the nodes whose eventual paths may be the best locations to find the goal quickly.
• The frontier represents the next node to be added and searched.
• In a depth-first search, nodes are added down paths and in a breadth-first search the nodes are added across all of the potential paths leading out of known nodes.
• The frontier itself can be thought of as a queue or stack where nodes are placed and then processed.
• You should recognize three things:
  • This approach could be referred to as a ‘greedy’ algorithm because it is always selecting the best option that is presented at the moment.
  • This process produces the path to the goal that has the least cost.
  • The process can be asymptotically inefficient as you may be required to search many paths and backtrack before finding the best goal.

Best-first Search

• The best first search uses a Heuristic to estimate (guess) at the cost of a particular path.
• The basic idea of a heuristic is that you use information that is readily available about the nodes to compute a cost.
• The search process needs to be altered using a heuristic determined by the user.
• Example, in searching for the best path between two cities:
  • Defining method of transportation (train, car, plane) becomes a heuristic, that changes the results when changed.
  • Applying the heuristic to the search process may not generate the shortest path or lowest cost path, but it will choose the solution best suited to the heuristic.

A* Search

• In the lowest-cost-first search we see an approach that can guarantee the selection of the most optimal solution, if it finds a solution, however, the search is potentially asymptotically expensive.
• In the best-first approach, we see an example of how we can employ a heuristic to use readily available information to inform our search, which has the potential of efficiently finding a solution.
• Both approaches are not optimal and both have significant shortcomings.
• A* Search incorporates both searches into a single search. It does this by defining a cost function (let’s call it ƒ) that combines the lowest cost first (we will refer to this as cost(p)) of a node with the heuristic (we will refer to this as h(p)) to yield the heuristic function: ƒ(p) = cost(p) + h(p).

Chapter 3: Searching for Solutions ²

3.1 Problem Solving as Search

• This notion of search is computation solely inside the agent.
• Search is different from searching in the world, when an agent may have to act in the world; for example, a robot searching for keys, lifting up cushions, and so on.
• Search is different from searching the web, which involves indexing data and searching within the indexes.
• Search means finding a path to a goal node within a graph.
• It is often believed that humans are able to use intuition to jump to solutions to difficult problems. However, humans cannot find optimal solutions to computationally difficult problems.
• This extra knowledge beyond the search space is called heuristic knowledge.
• Humans usually find satisfactory solutions, not optimal solutions, aka, good enough solutions.
• Humans use intuition to jump to solutions, but they can not solve computationally difficult problems.
• Humans solve instances of problems they know much more about beyond the search space.
• Public key cryptography is an example of a problem that is computationally difficult to solve for both humans and computers.

3.2 State Spaces

• A state contains all of the information necessary to predict the effects of an action and to determine whether a state satisfies the goal.
• State-space searching assumes:
  • The agent has perfect knowledge of the state space.
  • At any time, it knows what state it is in; the world is thus fully observable.
  • The agent has a set of actions with known deterministic effects.
  • The agent has a goal to achieve and can determine whether a state satisfies the goal.
• A solution to a search problem is a sequence of actions that will get the agent from its current state to a state that satisfies the goal.
• A state-space search problem consists of:
  • A set of states.
  • A start state.
  • For each state, a set of available actions to the agent at that state.
  • An action function that takes a state and an action and returns a new state that results from applying the action to the state.
  • A goal specified as a function that takes a state and returns boolean (true) if the state satisfies the goal.
  • A criteria that evaluates the quality of an acceptable solution.
• A solution that is best according to some criterion is called an optimal solution. An agent may be satisfied with any solution that is within, say, 10% of optimal.

3.3 Graph Searching

• Searching in graphs provides an appropriate abstract model of problem solving independent of a particular domain.
• A directed graph consists of a set of nodes and a set of directed arcs between nodes. The idea is to find a path along these arcs from the start node to a goal node.
• Nodes represent states and arcs represent actions.
• The arc ⟨n1,n2⟩ is an outgoing arc from n1 and an incoming arc to n2.
• Node n2 is a neighbor of n1 if there is an arc from n1 to n2; that is, if ⟨n1,n2⟩ ∈ A.
• Note that being a neighbor does not imply symmetry; just because n2 is a neighbor of n1 does not imply that n1 is a neighbor of n2.
• Arcs may be labeled, for example, with the action that will take the agent from a node to its neighbor or with the cost of an action or both.
• Sometimes there is a cost, a non-negative number, associated with arcs. The cost of arc ⟨ni,nj⟩ is written as c⁢o⁢s⁢t⁢(⟨ni,nj⟩).
• An optimal solution is one of the solutions that has the lowest cost.
• A cycle is a non-empty path where the end node is the same as the start node; that is, ⟨n0,n1,…,nk⟩ such that n0=nk.
• A tree is a DAG where:
  • There is one node with no incoming arcs and every other node has exactly one incoming arc.
  • The node with no incoming arcs is the root.
  • A node with no outgoing arcs is a leaf.
  • An arc goes from a parent to a child.
• The forward branching factor of a node is the number of outgoing arcs from the node.
• The backward branching factor of a node is the number of incoming arcs to the node.
• Bounded branching factor: The number of outgoing and incoming arcs from every node is less or equal to a positive integer b.

3.4 A Generic Searching Algorithm

• The algorithm calls procedures that can be coded to implement various search strategies.
• The intuitive idea behind the generic search algorithm, given a graph, a start node, and a goal predicate, is to explore paths incrementally from the start node.
• The frontier contains all of the paths that could form initial segments of paths from the start node to a goal node.
• Initially, the frontier contains the trivial path containing just the start node, and no arcs. As the search proceeds, the frontier expands into the unexplored nodes until a goal node is encountered.
• Different search strategies are obtained by providing an appropriate implementation of the frontier.

3.5 Uninformed Search Strategies

• 4 uninformed search strategies:
  • Depth-first search.
  • Breadth-first search.
  • Iterative deepening search.
  • Lowest-cost-first search.
• Breadth-first search:
  • The frontier is a FIFO queue.
  • It is not used very often for large problems where the graph is dynamically generated because of its exponential space complexity.
  • Frontier size: b^d, where b is the branching factor and d is the depth of the shallowest goal node.
• Depth-first search:
  • The frontier is a LIFO stack.
  • Searching one path to its completion before trying an alternative path using backtracking.
  • Some paths may be infinite when the graph has cycles or infinitely many nodes, in which case a depth-first search may never stop.
  • Frontier size: bm, where b is the branching factor and m is the maximum depth of the search tree.
  • DFS is useful when space is limited, there are many solutions in the search space, or if the way nodes are added to the graph can be manipulated so solutions are always found in the first tries.
  • DFS is NOT useful if there is a infinite or cyclic paths, if the solutions are shallow (BFS is better), or if there are multiple paths to the goal (e.g., 4*$ grid with the ability to move in 4 directions).
• Iterative deepening search:
  • It combines the benefits of BFS and DFS.
  • It calls a depth-bounded searcher with increasing depth limits.
  • When it reaches the final depth bound, it exits and reports that no solution was found.
  • It is complete and optimal if the path cost is a non-decreasing function of the depth of the node.
  • Frontier size: bd, where b is the branching factor and d is the depth of the shallowest goal node.
• Lowest-Cost-First Search:
  • It selects the path with the lowest cost.

3.6 Informed (Heuristic) Search

• A heuristic function h⁢(n) takes a node n and returns a non-negative real number that is an estimate of the cost of the least-cost path from node n to a goal node.
• The function h⁢(n) is an admissible heuristic if h⁢(n) is always less than or equal to the actual cost of a lowest-cost path from node n to a goal.
• Heuristic depth-first search:
  • DFS with a heuristic function that sorts the frontier before selecting the next node to expand.
• Greedy best-first search:
  • It selects the node with the lowest heuristic value.
• A * Search:
  • It uses both path cost, as in lowest-cost-first, and a heuristic function, as in greedy best-first search, in its selection of which path to expand.
• Designing a Heuristic Function:
  • An admissible heuristic is a non-negative function h of nodes, where h⁢(n) is never greater than the actual cost of the shortest path from node n to a goal.

3.7 Pruning the Search Space

• Cycle Pruning:
  • Cycle detection is important in graph searching to avoid infinite loops.
  • It checks that a node has not been visited before (not on the stored path).
• Multi-Path Pruning:
  • It checks that a node has not been visited before (maybe through a different path if more than one path is possible).

Strategy	Selection from frontier	Path found	Space
Breadth-first	First node added	Fewest arcs	O⁢(bd)
Depth-first	Last node added	✘	O⁢(b⁢d)
Iterative deepening	N/A	Fewest arcs	O⁢(b⁢d)
Greedy best-first	Minimal h⁢(p)	✘	O⁢(bd)
Lowest-cost-first	Minimal c⁢o⁢s⁢t⁢(p)	Least cost	O⁢(bd)
A∗	Minimal c⁢o⁢s⁢t⁢(p)+h⁢(p)	Least cost	O⁢(bd)
DF B&B	N/A	Least cost	O⁢(b⁢d)

3.8 Search Refinements

• The direction of search:
  • Searching from the start to a goal or from a goal to the start can make a difference in efficiency.
  • Backward search can be used to find policies that give an optimal path from any position, and can be used to improve a heuristic function.
  • Bidirectional search can be used to find the shortest path between two nodes.
• Island-Driven Search:
  • Decompose the search space into isolated subspaces called islands; and start searching in each of these islands separately, in parallel if possible.
  • You may also need to divide the problem into subproblems according to the islands.
  • Example: In a path from city A to city D, you may divide the problem into subproblems of finding a path from A to B, B to C, and C to D; and find paths in parallel.

3.9 Summary & Social Impact

• Route planning may have unintended side-effects:
  • If the route planner is advising many people, and advises them all to take the same route, that route may become more congested because of the advice.
  • The system needs to do some load balancing so that all suggested routes have the same cost.
  • Collecting real-time location information for the purposes of congestion avoidance, also has privacy concerns if this information is used for other purposes or passed to third parties, such as advertisers or governments.

Lecture 1: Uninformed Search ³

• Search process:
  • We don’t have an algorithm to solve the problem. We only have a specifications of the solution.
  • We start searching all the possible solutions in the search space to find one that satisfies the specifications.
  • Usually, an agent is in a specific state S and it has to find a sequence of actions to reach a goal state G.
  • Many AI problems can be abstracted as finding a path in a directed graph.
  • There is more than one way to represent a problem as a graph.
• DAG: Directed Acyclic Graph:
  • A graph with a set of N nodes, and set A of ordered pairs of nodes, called arcs.
  • Node n2 is a neighbor of node n1 if there is an arc from n1 to n2, that is, (n1, n2) ∈ A.
  • A path from node n1 to node nk is a sequence of nodes n0, n2, …, nk such that (ni, ni+1) ∈ A for all i = 0, 1, 2, …, k-1.
  • The length of a path is the number of arcs in the path (K).
  • Given a start nodes and goal node(s), a solution is a path from the start node to the goal node.
• Searching a graph:
  • Given a start node S, and a goal node G, we want to find a path from S to G by incrementally exploring possible paths and adding them to a frontier.
  • The frontier changes as we advance in the search process, with nodes being added and removed.
  • The way the frontier is managed determines the search strategy, which can be uninformed or informed.
  • Uniformed search strategies may include depth-first search, breadth-first search, and iterative deepening search.
• DFS: Depth-First Search:
  • The frontier is a stack.
  • It always selects the last node added to the frontier.
  • It does not give the optimal solution.
• BFS: Breadth-First Search:
  • The frontier is a queue.
  • It always selects the first node added to the frontier.
  • It does not give the optimal solution.

Lecture 2: Informed Search ⁴

• Informed search directs the search process by giving some more information about the optimal goal; hence, increasing the possibility of finding the optimal solution.
• A heuristic is a function that estimates the cost of reaching the goal.
• Underestimate Heuristic:
  • It is a function that estimates the cost of reaching the goal where no other path can be cheaper.
• Admissible Heuristic:
  • It is a non-negative function that is an underestimate of the cost of reaching the goal.

Summary of Search Strategies

• Finding a path (p) from start node S to goal G at a node (N): f(p) = cost(p) + h(p):
  • f(p) is the total cost of the path from the S to N, including the cost of the path and the heuristic.
  • cost(p) is the cost of the path from S to N.
  • h(p) is the heuristic function that estimates the cost of reaching the goal from N (N to G).

	f(p)	cost(p)	h(p)
Covers	S to N	S to N	N to G
Description	Total	Cost so far	Estimate for the remaining

Strategy	Frontier Selection	Complete	Halts	Space
Depth First	Stack (LIFO)	No	No	Linear
Breadth First	Queue (FIFO)	Yes	No	Exponential
Heuristic DFS	Local Min Heuristic h(p)	No	No	Linear
Best First	Global Min Heuristic h(p)	No	No	Exponential
Lowest Cost	Global Min Cost cost(p)	Yes	No	Exponential
A* Search	Global Total Min f(p)	Yes	No	Exponential

• Characteristic of strategies:
  • Complete:
    • If a solution exists, the strategy will always find it, even in an infinite search space (graph).
    • Complete strategies: BFS, Lowest Cost, A* Search.
    • All complete strategies are exponential in space.
  • Halts:
    • This means the algorithm will eventually terminate (finish running) on a finite graph.
    • Without measures like cycle detection, some strategies (e.g., Depth First Search) might not halt in graphs with cycles or infinite branches.
    • A good strategy should halt when it finds a cycle or a loop; it should backtrack or exit.
  • Space:
    • This refers to the maximum memory required during the search, usually measured in the number of nodes stored in memory, aka, the length of the frontier.

References

---

1. Learning Guide Unit 3: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=454696&chapterid=555032 ↩

2. Poole, D. L., & Mackworth, A. K. (2017). Artificial Intelligence: Foundations of computational agents. Cambridge University Press. https://artint.info/2e/html/ArtInt2e.html Chapter 3 – Searching for Solutions ↩

3. Taipala, D. (2014, September 22). CS4408 Artificial Intelligence unit 3 lecture 1 [Video]. YouTube. ↩

4. Taipala, D. (2014, September 22). CS4408 Artificial Intelligence unit 3 lecture 2 [Video]. YouTube.

   ‌ ↩