Problem Solving Agent

• Kind of goal-based agent
  • Uses atomic representations
  • With no internal structure visible to the agent

Problem Solving Agent

• Goal Formulation
  • Based on current situation and agent’s performance measure
  • Goal \(\rightarrow\) Set of world states
    • Those in which the goal is satisfied
  • Agent has to find a way to act in order to reach a goal state

Problem Solving Agent

• Problem Formulation
  • Process of deciding what actions and states to consider
    • Given a goal
• What to do if there are several immediate options of unknown value
  • Examine future actions
  • Eventualy lead to states of known value

Problem Solving Agent

• Search
  • The process of looking a sequence of actions to reach the goal
• Search algorithm
  • Input: Problem
  • Output: Solution \(\rightarrow\) as a sequence of actions
• Execution phase
  • Performing the solution, the sequence of actions

• Problem Solving Agent: FORMULATE \(\rightarrow\) SEARCH \(\rightarrow\) EXECUTE

• Open Loop systems
  • While agent executes solution sequence, when choosing an action, it ignores percepts

Problem Solving Agent

Well-defined Problems and Solutions

• Problem defined by five components
  • Initial state
  • Actions
  • Transition model
  • Goal test
  • Path cost

Well-defined Problems and Solutions

• Problem defined by five components
  • Initial State
  • Actions
    • \(ACTIONS(s)\) returns actions applicable in \(s\)
  • Transition model, \(RESULT(s,a)\)
    • Returns the state resulting from doing action \(a\) in state \(s\), the successor state
    • State space: initial state, actions and transition model
    • Graph: State space forms a graph or network. Nodes are states, edges are actions.
    • Path: Sequence of states connected by sequence of actions

Well-defined Problems and Solutions

• Problem defined by five components
  • Goal test Verifies if a given state is a goal state
  • Path cost
    • Assigns a cost to each path
    • Step cost: cost of taking action \(a\) in state \(s\) to reach state \(s'\), \(c(s,a,s')\)
    • Optimal solution: has the lowest path cost among all solutions

Example of Problem Solving Agent - Romania

• Agent is in Arad, Romania
• Performance measure
  • Get to Bucharest on time for his flight the next day
  • Know other cities
  • Minimize cost travel

Example of Problem Solving Agent - Romania

Formulating Problems

• Abstraction
  • State descriptions
    • Remove irrelevant detail to the task
    • States will only describe relevant information
  • Actions
    • Also remove detail from actions
    • Omit irrelevant actions
  • Which is the appropriate level of abstraction?
    • Remove irrelevant detail but keep validity and ensure abstract actions are easy to follow

Toy Problems

• Vacuum World
  • States: Given by agent location & dirt locations, \(2x2^2=8\)
    • Larger environment with \(n\) locations: \(n x 2^n\) states
  • Initial state: Any
  • Actions: \(Left\), \(Right\), \(Suck\)
  • Transition model: the expected effect except that:
    • \(Left\) in the left square has no effect
    • \(Right\) in the right square has no effect
    • \(Sucking\) in a clean square has no effect
  • Goal test: check if all squares are clean
  • Path cost: each step costs 1

Toy Problems

Toy Problems

• 8-puzzle

Toy Problems

• 8-puzzle
  • States: A state specifies location of each of eight tiles and the blank in one of the 9 squares
  • Initial state: Any
  • Actions: Movements of blank space Left, Right, Up, Down
  • Transition model: Returns the resulting state, i.e. move space left in initial state of figure 4, switches space & 5
  • Goal text: goal state shown in figure 4
  • Path cost: the number of steps in the path (1 per step)

Toy Problems

• 8-puzzle belongs to family sliding-block puzzles
  • Used to test AI algorithms
  • Family of problems known to be NP-complete
  • 8-puzzle has \(9!/2 = 181,440\) reachable states, easily solved
  • 15-puzzle (4x4 board) has around 1.3 trillion states
    • random instances can be solved optimally in few milliseconds by best search algorithms
  • 24-puzzle (5x5 board) has around \(10^{25}\) states
    • random instances take several hours to be optimally solved

Toy Problems

• 8-queens problem
  • Place 8 queens on chessboard, no queen attacks any other

Toy Problems

• 8-queens problem
  • Also used as test problem for search algorithms
  • Incremental formulation, each state adds a queen to the state
  • Complete state formulation, starts with 8 queens on the board and moves them around

Toy Problems

• 8-queens problem (first incremental formulation)
  • States: Any arrangement of 0 to 8 queens on the board
  • Initial state: Empty board
  • Actions: Add queen to board (on empty square)
  • Transition model: Returns board with new added queen
  • Goal test: all queen on the board, none attacked

Toy Problems

• 8-queens problem…
  • Previous formulation: 64 * 63 … * 57 approx. \(1.8 \times 10^{14}\) possible sequences

  • Better formulation: don’t place a queen in a square being attacked

  • States: All possible arrangements of \(n\) queens (0 \(\leq n \leq\) 8), one per column in the leftmost \(n\) columns, no queen attacking another

  • Actions: Add queen to any square in leftmost empty column, verify it is not being attacked by another queen

  • Reduces 8-queens state space from \(1.8 \times 10^{14}\) to 2,057, solutions easy to find

Real-world Problems

• Airline travel problems solved by travel-planning Web site
  • States: Location, current time. Cost of segment may depend on previous segments: fare bases, domestic or international.
  • Initial state: Specified by user’s query
  • Actions: Take a flight from current location, in any seat class, leaving after current time, leaving enough time for within-airport transfers
  • Transition model: State resulting from taking a flight, the flight’s destination and arrival time
  • Goal test: Is this the final destination for the user?
  • Path cost: Monetary cost, waiting time, flight time, customs and immigration procedures, seat quality, time of day, type of airplane, frequent-flyer mileage awards, etc.

Real-world Problems

• Touring problems
  • Similar to route-finding problems
  • i.e. “Visit every city in Figure 2 at least once, starting and ending in Bucharest”

Real-world Problems

• Traveling Salesperson Problem (TSP)
  • A touring problem
  • Each city must be visited exactly once
  • Find the shortest tour
  • An NP-hard problem

Real-world Problems

• VLSI layout problem
  • Positioning millions of components and connections on a chip
  • Minimize area, circuit delays, stray capacitances
  • Maximize manufacturing yield

Real-world Problems

• Robot navigation
  • Generalization of route-finding problem
  • But robot moves in continuous space \(\rightarrow\) infinite set of possible actions and states
  • 2D or 3D
  • Deal with errors in their sensor readings and motor controls

Real-world Problems

• Automatic Assembly Sequencing
  • Find order in which to assemble the parts of some object
  • Wrong order \(\rightarrow\) there won’t be a way to add some part later without undoing some work

Real-world Problems

• Protein Design
  • Find a sequence of amino acids that fold in 3D protein with properties to cure some disease

Search

• Solution is an action sequence
• A search algorithm considers many possible action sequences
• Possible action sequences, starting at initial state, form a search tree
• Branches represent actions
• Nodes represent states in the state space of the problem

Search

Search

• Expanding current state
  • Apply a legal action to current state
  • This generates a new set of states
• Parent node: In(Arad)
• Child nodes: In(Sibiu), In(Timisoara), and In(Zerind)
• Leaf node: A node with no children
• Frontier: Set of all leaf nodes available for expansion (or open list)
• Search strategy: The way of choosing which state to expand next
• Repeated state: As in Arad in fig. 6
• Loopy Path: State spaces become infinite
• Redundant paths: There is more than one way to get from one state to another

Search

Search

• Rectangular grid
  • Important in games, each state has 4 successors
  • Search tree of depth \(d\) with repeats has \(4^d\) leaves, only \(2d^2\) are distinct states with \(d\) steps of a given state
  • For \(d\) = 20, a trillion nodes, only about 800 distinct states
  • Avoid exploring redundant paths
    • Store explored set (or closed list), all expanded nodes
    • Discard new generated states matching previous generated ones
    • See GRAPH-SEARCH
  • Separator, the frontier separates state-space graph into the explored region and the unexplored region

Search

Search

Infrastructure for Search Algorithms

• Data structure for search algorithms
  • Keep track of search tree
• Each node in the tree
  • n.STATE, state in the state space
  • n.PARENT, node that generated this node
  • n.ACTION, action applied to the parent to generate the node
  • n.PATH-COST (\(g(n)\) from initial state to the node)

Infrastructure for Search Algorithms

Infrastructure for Search Algorithms

Infrastructure for Search Algorithms

• Data structure for the frontier, a queue
• Operations
  • EMPTY?(queue)
  • POP(queue)
  • INSERT(element, queue)
• Types of queues: FIFO, LIFO, Priority
• Canonical Form: logically equivalent states should map to the same data structure

Measuring Problem-solving Performance

• Completeness
• Optimality
• Time complexity
• Space complexity
• Complexity expressed in terms of:
  • \(b\), branching factor (max. number of successors of any node)
  • \(d\), depth (of the shallowest goal node)
  • \(m\), max length of any path in the state space

Measuring Problem-solving Performance

• Time measured in terms of number of nodes generated during search
• Space in terms of max. number of nodes stored in memory
• Search cost: usually depends on time complexity but could include memory usage
• Total cost: combines search cost and path cost of the solution found

Uninformed Search Strategies

• Also called blind search
• No additional information, only the problem definition
  • Generte successors and test for a goal state
  • Strategies differ by the order in which nodes are expanded
• Strategies that know if a non-goal state is more promising than another
  • Informed search
  • Heuristic search

Breadth-first Search

• All nodes are expanded at given depth in search tree before any nodes at next level are expanded
• An instance of the general graph-search algorithm
  • The shallowest unexpanded node is chosen for expansion
• Uses a FIFO queue for the frontier

Breadth-first Search

Breadth-first Search

Breadth-first Search

• BFS
  • Complete?

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time?

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time? \(1 + b + b^2 + b^3 + \dots + b^d + b(b^d - 1) = O(b^{d+1})\)

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time? \(1 + b + b^2 + b^3 + \dots + b^d + b(b^d - 1) = O(b^{d+1})\)
    
  • Space?

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time? \(1 + b + b^2 + b^3 + \dots + b^d + b(b^d - 1) = O(b^{d+1})\)
    
  • Space? \(O(b^{d+1})\) (keeps every node in memory)
  • \(b\) is the number of nodes generated by each node
  • \(d\) is the depth of the solution

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time? \(1 + b + b^2 + b^3 + \dots + b^d + b(b^d - 1) = O(b^{d+1})\)
    
  • Space? \(O(b^{d+1})\) (keeps every node in memory)
  • Optimal?

Breadth-first Search

• BFS
  • Complete? YES if \(b\) is finite
    
  • Time? \(1 + b + b^2 + b^3 + \dots + b^d + b(b^d - 1) = O(b^{d+1})\)
    
  • Space? \(O(b^{d+1})\) (keeps every node in memory)

  • Optimal? YES (if cost = 1 per step); not optimal in general (i.e. smaller cost of another node in the frontier)

  • Space is the problem!, time is also bad!

Breadth-first Search

Uniform-cost Search

• BFS optimal if all step costs equal
• Algorithm optimal for any step-cost function: uniform-cost search
  • Expands the node \(n\) with the lowest path cost g(n)
  • Store the frontier as a priority queue ordered by \(g\)
  • Differences with BFS
    • Goal test applied when node is selected for expansion
      • The first goal node generated may be a suboptimal path
    • Test added in case better path is found to a node currently on the frontier

Uniform-cost Search

• UCS
  • Search guided by path costs rather than depths
  • \(C^{*}\) is the cost of the optimal solution, every action costs at least \(\epsilon\)
  • Worst case time complexity: \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)

Uniform-cost Search

Uniform-cost Search

Uniform-cost Search

• UCS
  • Complete?

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time?

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
    
  • Space?

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
    
  • Space? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
    
  • Space? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
  • Optimal?

Uniform-cost Search

• UCS
  • Complete? YES if step cost \(\geq \epsilon\)
    
  • Time? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
    
  • Space? # of nodes with \(g \leq\) cost of optimal solution, \(O(b^{1+\lfloor C^{*}/\epsilon \rfloor})\)
  • Optimal? Yes, nodes expanded in increasing order of \(g(n)\)

Depth First Search

• Always expands deepest node in current frontier of the search tree
• An instance of the graph-search algorithm
• Uses a LIFO queue
  • The most recently generated node is chosen for expansion
  • Can also be implemented as a recursive function

Depth First Search

Depth First Search

• Properties depend on implementation
  • Graph-search
    • Avoids repeated states and redundant paths, is complete in finite state spaces
  • Tree-search
    • Not complete, i.e. may follow loops forever
  • Both versions are nonoptimal

Depth First Search

• DFS
  • Complete?

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time?

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time? \(O(b^{m})\): terrible if \(m\) is much larger than \(d\), but if solutions are dense, may be much faster than breadth-first
  • \(b\) is the branching factor
  • \(m\) is the maximum depth
  • \(d\) the depth of the shallowest solution

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time? \(O(b^{m})\): terrible if \(m\) is much larger than \(d\), but if solutions are dense, may be much faster than breadth-first
  • Space?

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time? \(O(b^{m})\): terrible if \(m\) is much larger than \(d\), but if solutions are dense, may be much faster than breadth-first
  • Space? \(O(bm)\), i.e., linear space!

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time? \(O(b^{m})\): terrible if \(m\) is much larger than \(d\), but if solutions are dense, may be much faster than breadth-first
  • Space? \(O(bm)\), i.e., linear space!
  • Optimal?

Depth First Search

• DFS
  • Complete? No fails in infinite-depth spaces, spaces with loops. Modify to avoid repeated states along path \(\rightarrow\) complete in finite spaces
    
  • Time? \(O(b^{m})\): terrible if \(m\) is much larger than \(d\), but if solutions are dense, may be much faster than breadth-first
  • Space? \(O(bm)\), i.e., linear space!
  • Optimal? No

Depth-limited Search

• Depth-first search with depth limit \(l\)
  • Nodes at depth \(l\) treated as if they have no successors
  • Solves the infinite-path problem but introduces additional source of incompleteness if \(l < d\)
  • Non-optimal if we choose \(l > d\)
  • Time complexity \(O(b^l)\)
  • Space complexity \(O(bl)\)

Depth-limited Search

Iterative Deepening Depth-first Search

• General strategy, often combined with depth-first tree search
• Finds the best depth limit
• Gradually increases the limit: 0, 1, 2, \(\dots\), until a goal is found
• Combines benefits of depth-first and breadth-first search
• Memory: \(O(bd)\)
• Complete when branching factor is finite
• Optimal when path cost is a nondecreasing function of the depth of the node

Iterative Deepening Depth-first Search

Iterative Deepening Depth-first Search

Iterative Deepening Depth-first Search

• IDFS
  • Complete?

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time?

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time? \((d+1)b^0 + db^1 + (d-1)b^2 + \dots + b^d = O(b^d)\)

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time? \((d+1)b^0 + db^1 + (d-1)b^2 + \dots + b^d = O(b^d)\)
  • Space?

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time? \((d+1)b^0 + db^1 + (d-1)b^2 + \dots + b^d = O(b^d)\)
  • Space? \(O(bd)\)

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time? \((d+1)b^0 + db^1 + (d-1)b^2 + \dots + b^d = O(b^d)\)
  • Space? \(O(bd)\)
  • Optimal?

Iterative Deepening Depth-first Search

• IDFS
  • Complete? Yes
  • Time? \((d+1)b^0 + db^1 + (d-1)b^2 + \dots + b^d = O(b^d)\)
  • Space? \(O(bd)\)
  • Optimal? Yes, if step cost = 1, can be modified to explore uniform-cost tree

Iterative Deepening Depth-first Search

• IDFS
  • Numerical comparison for \(b = 10\) and \(d = 5\), solution at far right leaf:
  • N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450
  • N(BFS) = 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1,111,100
  • IDS does better because other nodes at depth \(d\) are not expanded
  • BFS can be modified to apply goal test when a node is generated

Bidirectional Search

• Runs two simultaneous searches
  • One from initial state
  • Other from the goal
  • Hoping both searches meet in the midle
  • \(b^{d/2} + b^{d/2}\) is much less than \(b^d\)

Bidirectional Search

Comparing Uninformed Search Strategies

Informed Search

• An informed search strategy uses problem-specific knowledge
  • More efficient than uninformed strategies
• General approach
  • best-first search
  • Instance of general Tree-Search or Graph-Search
  • Chooses node to expand based on evaluation function \(f(n)\)
  • Choice of f determines strategy
  • Some algorithms use heuristic function \(h(n)\)
    • \(h(n)\) = estimated cost of the chepest path from the state at node \(n\) to a goal state

Greedy Best-first Search

• Tries to expand node closest to goal
  • Should it lead to a solution quickly
• Evaluates nodes with heuristic function: \(f(n) = g(n)\)
  • i.e. Straight Line Distance
  • \(h_{SLD}(In(Arad)) = 366\)
  • Arad - Sibiu - Fagaras - Bucharest
• Non optimal: A Shorter path: Arad - Rimnicu Vilcea - Pitesti - Bucharest
• Incomplete: Getting from Iasi to Fagaras
  • Heuristic suggests expanding Neamt, \(\rightarrow\) dead end
• Worst case time and space complexity
  • \(O(b^m)\), \(m\) is the maximum depth of the search step

Greedy Best-first Search

Greedy Best-first Search

\(A^*\) Search

• Minimizing the Total Estimated Solution Cost
• Idea: avoid expanding paths that are already expensive
• \(A^*\), a known form of best-first search
• Evaluation function:
  • \(f(n) = g(n) + h(n)\)
  • \(g(n)\), the cost to reach the node
  • \(h(n)\), the cost to get from the node to the goal
  • \(f(n)\), estimated total cost of path through \(n\) to goal

\(A^*\) Search

• \(A^*\) uses an admissible heuristic, one that never overestimates the cost to reach the goal
  • i.e., \(h(n) \leq h^{*}\) where \(h^{*}\) is the true cost from \(n\)
  • Admissible heuristics are then, optimistic
  • E.g., \(h_{SLD}(n)\) never overestimates the actual road distance
• \(A^*\) applied to graph search requires consistency (sometimes called monotonicity)
  • A heuristic is consistent if, for every node \(n\) and any successor \(n'\) of \(n\) generated by any action \(a\)
    • \(h(n) \leq c(n,a,n') + h(n')\)
• Theorem: \(A^*\) search is optimal

\(A^*\) Search

• Optimality of \(A^{*}\) (standard proof)
  • Suppose some suboptimal goal \(G_2\) has been generated and is in the queue
  • Let \(n\) be an unexpanded node on a shortest path to an optimal goal \(G_1\)
    • \(f(G_2) = g(G_2)\) since \(h(G_2) = 0\)
    • \(> g(G_1)\) since \(G_2\) is suboptimal
    • \(\geq f(n)\) since \(h\) is admissible
    • Since \(f(G_2) > f(n)\), \(A^{*}\) will never select \(G_2\) for expansion

\(A^*\) Search

\(A^*\) Search

• Lemma: \(A^{*}\) expands nodes in order of increasing \(f\) value
• Gradually adds “\(f\)-contours” of nodes (breadth-first adds layers)
• Contour \(i\) has all nodes with \(f=f_i\), where \(f_i < f_{i+1}\)

\(A^*\) Search

\(A^*\) Search

\(A^*\) Search

\(A^*\) Search

• \(A^*\) Properties
  • Complete?

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time?

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time? Exponential in [relative error in \(h \times\) length of solution]

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time? Exponential in [relative error in \(h \times\) length of solution]
  • Space?

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time? Exponential in [relative error in \(h \times\) length of solution]
  • Space? Keeps all nodes in memory

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time? Exponential in [relative error in \(h \times\) length of solution]
  • Space? Keeps all nodes in memory
  • Optimal?

\(A^*\) Search

• \(A^*\) Properties
  • Complete? Yes, unless there are infinitely many nodes with \(f \leq f(G)\)
  • Time? Exponential in [relative error in \(h \times\) length of solution]
  • Space? Keeps all nodes in memory
  • Optimal? Yes, cannot expand \(f_{i+1}\) until \(f_i\) is finished
    • \(A^*\) expands all nodes with \(f(n) < C^{*}\)
    • \(A^*\) expands some nodes with \(f(n) = C^{*}\)
    • \(A^*\) expands no nodes with \(f(n) > C^{*}\)

\(A^*\) Search

• Proof of lemma: Consistency
  • A heuristic is consistent if \(h(n) \leq c(n,a,n^{'}) + h(n^{'})\)
  • If \(h\) is consistent we have
    • \(f(n^{'})\) = \(g(n^{'}) + h(n^{'})\) = \(g(n) + c(n, a, n^{'}) + h(n^{'})\) \(\geq g(n) + h(n)\) = \(f(n)\)
    • i.e. \(f(n)\) is nondecreasing along any path.

Heuristic Functions

• Admissible heuristics for the 8-puzzle
  • \(h_1(n)\) = number of misplaced tiles, \(h_1(S) = 8\)
  • \(h_2(n)\) = total Manhattan distance, \(h_2(S) = 3+1+2+2+2+3+3+2=18\)
• If \(h_2(n) \geq h_1(n)\) for all \(n\) (both admissible) then \(h_2\) dominates \(h_1\) and is better for search
  • \(h(n) = max(h_a(n), h_b(n))\)
    • Is admissible and dominates \(h_a\), \(h_b\)

Heuristic Functions

Heuristic Functions

• Branching factor
  • Total number of nodes generated by \(A^{*}\) is \(N\)
  • Depth of solution is \(d\)
  • \(N+1 = 1 + b^{*} + (b^{*})^2 + \dots + (b^{*})^d\).
  • Branching factor is \(b\)

Heuristic Functions

Heuristic Functions

• Admissible heuristics
  • From exact solution cost
  • From relaxed version of problem
• Relax 8-puzzle so that a tile can move anywhere
  • \(h_1(n)\) gives shortest solution
• Relax 8-puzzle so that a tile can move to any adjacent square, even if it is occupied
  • \(h_2(n)\) gives the shortest solution
• Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem