f

• Frontier


  Set of all leaf nodes available for expansion at any given time
• Search Strategy


  How a search algorithm chooses which node to expand next
• Branching Factor


  Maximum number of successors of any node
• Heuristic Function


  Estimates cost of cheapest path from current state to goal state
• Deterministic Environment


  Next state of environment is fixed by current state and action
• Dynamic Environment


  Environment can change while agent is deliberating
• Agent Function


  Maps any given percept sequence to an action
• Fully Observable


  Sensors give the complete state of environment at each time
• Uninformed Search


  Uses no additional information beyond problem definition
• Informed Search


  Uses problem-specific knowledge beyond problem definition
• A* Search


  Tries to minimize the total estimated solution cost
• Greedy Best-first Search


  Tries to expand the node believed to be closest to the goal
• Consistent Heuristic


  For n' a successor of n from action a, h(n) ≤ cost(n, a, n') + h(n')
• Admissible Heuristic


  Never over-estimates cost of cheapest path to a goal state
• Solution to a CSP


  A complete and consistent assignment
• Complete Assignment


  Associates values with some or all variables
• Constraint Graph


  Nodes correspond to variables, links connect variables that participate in a constraint
• Arc Consistency


  All values in a variable's domain satisfy its binary constraints
• Forward Checking


  When variable X is assigned, delete any value of other variables that is inconsistent with the assigned value of X
• Domain


  Set of allowed values for some variable
• Constraint


  Specifies an allowable combination of variable values
• Consistent Assignment


  The values assigned to variables do not violate any constraints