Problem Formulation

• a problem consist of 4 parts:
  • initial state
  • set of operators or successor function
  • goal test function
  • path cost function
• state space - environment of the problem
• path - a set of states starting with root

Knowledge and Problem Types

• single-state problem - environment is accessible and actions are deterministic
• multiple-state problem - environment is in-accessible and/or actions are non-deterministic
• contingency problem - a problem requires interleaving of search and execution
• exploration problem - initially, agent has no info about the effects of its actions. agent must learn effects of actions and the possible states of environment

Types of Search Algorithms

• breadth first search (bfs)
• uniform cost search (ucs)
  • bfs with expanding the lowest-cost node based on g() on the fringe
  • this will find optimal solution when g() is always positive
• depth first search (dfs)
• depth limited search (dls)
  • dfs with with cutoff at max depth of a path
• iterative deepening search (ids)
  • execute multiple dls with increasing values of max depth
  • mix of bfs and dfs
• bidirectional search
  • search both:
    • forwards from initial state
    • backwards from goal state

Performance of Search Algorithms

• judged on the basis of:
  • completeness - is the strategy guaranteed to find a solution when there is one
  • optimality - does the strategy find the highest-quality solution when there are several different solutions
  • time complexity - how long does it take to find a solution
  • space complexity - how much memory does it need to perform the search

Avoiding Repeated States

• 3 ways to avoid repeated states (increasing order of effectiveness and computational overhead):
  • do not return to the state you just came from
    • have (expand-function or operator-set) NOT generate successor(s) that’s the same as node’s parent
  • do not create paths with cycles in them
    • have (expand-function or operator-set) NOT generate successor(s) that’s the same as any of the current node’s ancestors
  • do not generate any state that was ever generated before
    • requires every generated state to be stored in memory - resulting in space complexity of O(|states|)

Constraint Satisfaction Problem (CSP)

• CSP - a special kind of problem
  • states - defined by the values of a set of variables
  • goal - set of constraints that the values must obey
  • solution - assigned values to all variables such that the constraints are satisfied
• constraints
  • can be either
    • unary constraint - the allowable subset of the variable’s domain
    • binary constraints - the allowable subset of the cross-product of the 2 variable’s domains
    • n-nary/global constraints - the allowable subset of the cartesian-product of the n variable’s domains
  • can be either
    • absolute constraint - violation of which rules out a potential solution
    • preference constraint - determines which solutions are preferred
• variables
  • each variable has its own domain
  • domain
    • is a set of possible values that the variable can take on
    • can be discrete or continuous
• backtracking search
  • before the successor generation step check whether any constraint has been violated by the variable assignments made up to this point, if violated backtracks to try something else
• forward checking
  • special case of arc consistency
  • each time variable is instantiated, look ahead to detect unsolvability by deleting from domains of uninstantiated variables. then check for any empty domains, if there exists an empty domain, backtrack immediately
• arc consistency
  • a state is arc consistent if every variable has a value in its domain that is consistent with each of the constraints on that variable
  • arc consistency can be achieved by deletion of values that are inconsistent with constraint
  • as values are deleted in domains, other values may become inconsistent because they relied on the deleted values
  • arc consistency exhibits a form of constraint propagation