Standard/Planning Search Problems

-

Standard search problems

  • Solution to a standard search problem: a plan
    • Use a search algorithm to find the plan and solve the search problem
    • Search algorithms are performed on the search tree (of the problem) to find the solution to the search problem
  • All search algorithms follow the same algorithm, but just use a different data structures for the fringe
 

Types of standard searches

➤ UNINFORMED SEARCH

uninformed search - a search that does not know information about the goal's location

Types of uninformed searches

  • Depth first search (DFS) - a search strategy that expands the deepest node first
    • Implementation: uses a last-in-first-out (LIFO) stack as the fringe
    • Time complexity: $O(b^m)$, for a finite tree where $m$ is the maximum depth and $b$ is the branching factor
    • Space complexity: $O(bm)$
      • DFS expands only the nodes on a single path from the deepest level to the root
  • Breadth first search (BFS) - a search strategy in which the root is expanded 
    • Implementation: uses a first-in-first-out (FIFO) queue as the fringe
    • Time complexity: $O(b^s)$, where $s$ is the depth of the shallowest solution, and $b$ is the branching factor
    • Space complexity: $O(b^2)$
      • At worst case, BFS's fringe contains all the nodes in the level corresponding to the shallowest solution, which is located at depth s of the search tree
  • Uniform cost search (UCS) - a search strategy that expands the cheapest node first
    • BFS vs. UCS
      • While BFS is guided by length of path via the number of edges of the search tree, UCS is guided by cost
      • BFS finds the shortest path while UCS finds the lowest-cost path
    • Implementation: uses a priority queue, with the priority value being the cumulative (backward) cost, as the fringe
      • backward cost - the sum of the edge weights in the path from the root to the current node/state
      • Whenever a node is chosen for expansion, a lowest-cost path to that node has been found
    • Time complexity: $O(\frac{b^{C^*}}{\epsilon})$, where $C^*$ is the cost of the optimal solution (the destination cost), $\epsilon$ is the cost of every action, and $b$ is the branching factor
    • Space complexity: $O(\frac{b^{C^*}}{\epsilon})$ 

 ➤ INFORMED SEARCH

informed search - a search that takes into account information about the goal node's location in the form of a heuristic function

Heuristic functions

  • heuristic function, $h(n)$ - a function that estimates how close a state/node is to a goal node
    • A heuristic value is a guess/prediction
    • Each search problem has its own (customized) heuristic function for solving the particular problem
    • More effective heuristics return values closet to the actual cost of reaching the goal (the best heuristic is one that returns the true cost (i.e. one that estimates perfectly))
  • Good heuristics
    • Good heuristics are needed to find the optimal path in an informed search
    • admissible heuristic - a heuristic $h(n)$ in which $0 \leq h(n) \leq h^*(n)$, $h^*(n)$ is the true cost to the nearest goal
      • An admissible heuristic always underestimates the true cost of reaching the goal
      • The maximum of 2 admissible heuristics is also admissible, and is in fact better than the two alone
    • consistent heuristic - a heuristic $h(n)$ in which $h(n) \leq cost(n, n') + h(n')$, where $cost(n, n')$ is the cost of going from node $n$ to node $n'$ and $h(n')$ is the heuristic value of going from node $n'$ to the goal state (for all neighboring nodes, $n'$, of node $n$)
      • Equivalently, $h(n) - h(n') \leq cost(n, n')$
      • The difference in heuristic values must be $<=$ the actual cost of going from node $n$ to node $n'$
      • A consistent heuristic is admissible, but an admissible heuristic may not be consistent
      • The maximum of 2 consistent heuristics is also consistent

Types of informed searches

  • Greedy search - a search algorithm that expands the node closest to the current node
    • Implementation: uses a priority queue, with the priority value being the estimated forward cost
      • forward cost (heuristic value) - an estimated cost of getting to the goal node
    • Time and space complexities: Greedy search is unpredictable (its performance depends on different scenarios)
  • A* search - a search algorithm that expands the node with the lowest total estimate, which is the sum of a node's backward and forward costs
    • Implementation: uses a priority queue, with the priority value being the estimated total cost from the start to goal node
      • total cost = cost(start node, current node) + estimate(current node, goal node)
        • cost(start node, current node) is the cost of the path already traveled from the start to current node (backward cost)
        • estimate(current node, goal node) is the estimate of the remaining cost to reach the goal node from the current node (forward cost)
    • Time complexity: $O(b^m)$
    • Space complexity: $O(b^m)$

Graph search algorithm 













Comments

Post a Comment

Popular posts from this blog

AI Search Problems Overview

-
Image
What is an agent? agent - an entity that perceives and acts planning agent - an agent that make decisions based on (hypothesized) consequences of actions Planning agents simulate situations and performs/executes the best action according to its simulations done in the "planning" stage Planning agents consider how the world would be Planning agents must have a model of how the world evolves in response to actions Planning agents must formulate a goal (test) Planning agents are complete (i.e. they never get stuck and always find a solution, since the plan ahead) The agent does not actually perform all the plans out in the real world The planning is all done "in simulation" search agent - a planning agents that solves search problems Search problems search problem - a type of planning problem with the four components (listed below); the environment in which a rational planning agent exists in Search operates over models of the real world ...
Read more

Tips on Pointers and Arrays in C

-
Image
*p++ vs. (*p)++   *p++ means *(p++) ++ binds to p , not to *p ++ will increment "p," not "*p," which is the thing that "p" points to The value of the expression *p++ is the value that p pointed to before being incremented ( *p ) Two useful charts Pointer arithmetic notes (~pointer~) += (~number~);  means  (~pointer~) += ~number~) * sizeof((~type~)); Pointer arithmetic addition adds multiples of the type size to the memory address Ex. If p is a pointer to an integer, then p += 1 means p += 1 * sizeof(int)   (~pointer name~) + 1 points to the next object in memory (returns a pointer to the next element)  (~pointer name~) + i points to the i -th object beyond (~pointer name~) in memory  (~pointer name~) += i increments (~pointer name~) to point to i elements beyond itself  Types of valid pointer arithmetic Adding an integer to a pointer Subtracting 2 pointers (in the same array) Comparing...
Read more