Search lecture 1

Hypothetical Reasoning

What state will I be in after taking certain actions, or after certain sequences of events?

From this we can reason about particular sequences of actions one should execute to achieve a desirable state.

Search is a computational method for capturing a particular version of ths kind of reasoning.

Modeling a problem as a search problem

We need

  • State space
    • A state is a representation of a configuration of the problem domain. The state space is a set of states included in our model of the problem.
  • Actions or state space transitions
    • Actions these model the actions of the problem domain. In our model the domain actions are modeled as allowed transitions between state.
  • Initial or start state and goal
    • The initial state and the finial goal state (or goal condition)
  • Heuristics
    • Things to guide the search process

Algorithms

Once the problem has been formulated, we can use various algorithms to solve the problem.

Knowledge States

States need not map directly to world configurations. Instead, a state could map to knowledge states. A knowledge state is a set of world states, every world state that you believe to be possible.

If you look at every world state in a knowledge state, and ask what is true in every one of them, that that is the fact you know.

If the agent knows nothing, the every world state is within the knowledge state.

More Complex Situations

  • Actions can lead to multiple states: flip a coin
    • This lead to probabilistic models that we will discuss later
  • Agent might be equipped with sensing actions
    • Solution could contain branches, for example if dirt then suck.

Search lecture 2

AI search algorithms work with implicitly defined state spaces. There are typically an exponential number of states, which means we are impossible to explicitly define them all.

Usually we only construct states we need to. Hence the actions are given as compact successor state functions that when given a state x return the set of state S can be transformed to by the available actions. * This means that the state must contain enough information to allow the successor state function to perform its computation.

Inputs for search

  • a specified initial state I
  • a successor function S(x) yields the set of all states action pairs (y,a) such that state y can be reached from x by applying an action a. The successor function returns all states reachable by a single action from state x.
  • a goal test function G(x) that can be applied to a state x and returns true if x satisfies the goal condition.
  • an action cost function C(x,a,y) which determines the cost of moving from state x to state y using action a.

Output of search

  • a sequence of actions that transforms the initial state to a state satisfying the goal test.
    • or just the sequence of states that arise from these actions.
  • Depending on the algorithm, different output maybe outputted.

A path in the search space is a sequence of states connected by actions. The cost of the path is simply the sum of all costs (the cost function C).

Paths can be stored as a pair containing the final state of the path and a pointer to the previous state.

We maintain a set of paths called the OPEN set (or frontier). Initially we set OPEN = {\<Start State\>}.

At each step we select a path p from OPEN.

  • Check if p.final() satisfies the goal.
  • If not we add all extensions of p to OPEN
    • for all successor states y in S(p.final()), create a new path p_y = \<p,y\> (extend the path p to include a transition to the state y).
    • Remember to remove p
Search(open, S, goal?):
    open.insert(<start>):
    while not open.empty():
        p = open.extract() # remove path from OPEN
        if goal?(p.final()):
            return p
        else:
            for succ in S(p.final()):
                open.insert(<p, succ>)
    return false

When a path p is extracted from open, we say that the algorithm expands p.

The order paths are selected from OPEN has a critical effect on the operation of the search: * Whether or not a solution is found * The cost of the solution found * The time and space required by the search

Basically we are asking how to order the OPEN set.

  • Completeness
    • Will the search always find a solution if a solution exists?
  • Optimality
    • will the search always find the least cost solution?
  • Time complexity
    • what is the maximum number of paths that can be expanded or generated?
  • Space complexity
    • maximum number of path that are put on OPEN

Uninformed Search Strategies

These are strategies that adopt a fixed rule for selecting the next state to be expanded.

For example: BFS, Uniform Cost, DFS, Depth Limited, Iterative Deepening Search.

Place the new paths that extend the current path at the end of OPEN. OPEN is a queue. Always extract first element of OPEN.

Completeness? Yes, we will examine all paths, so we will find a solution if it exists. (but we might have a infinite layer).

Optimality? Not really, however we do always find the shortest solution.

Time complexity? Let b be the maximum number of successors of any state (maximal branching factor). Let d be the depth of the shortest solution. The time complexity is $O(b^{d+1})$.

Space complexity? $O(b^{d+1})$

BFS typically run out of space before we run out of time in most applications.

Search lecture 3

  • Keep OPEN ordered by increasing cost of the path.
  • Always expand the least cost path.
  • Identical to breadth first if each action has the same cost.

Can use a min-heap to achieve this.

Completeness?

  • If each transition has costs $\geq \epsilon > 0$
  • Argument for BFS holds here

Optimality?

  • Finds optimal solution if each transition has cost $\geq \epsilon > 0$
  • Explores paths in the search space in increasing order of cost. So must find minimum cost path to a goal before finding any higher costs paths leading to a goal.