• View
• Edit
• History
• Print

Search

Advanced AI: A Modern Approach (AIMA) - Russell & Norvig

Basic Search Types:

• Best First Search
• Uniform Cost Search
• Depth First Search
• Breadth First Search
• Recursive Breadth First Search
• A* Search
• Anytime A*
• Hierarchical A*
• Bidirectional Search
• Djikstra’s Algorithm

Blind Search:

Bread-First Search (BFS )

• Complete, Optimal
• Space and Time complexity: O(b^d+1)

Depth-First Search (DFS)

• NOT Complete, NOT Optimal
• Time complexity is O(b^m)
• Space complexity is O(bm)
• Primary advantage is linear space, though this can be a problem for very deep trees.

Depth-Limited Search (DLS)

• NOT Complete, NOT Optimal
• Time complexity is O(b^l)
• Space complexity is O(bl)
• Only advantages over DFS is the bound on computation time and that it avoids problems with cycles in graphs.

Iterative Deepening Search (IDS)

• Complete, Optimal
• Time complexity is O(b^d)
• Space complexity is O(bd)
• Cheaper than all other search methods in space and time by virtue of the fact we keep a DFS path at any given point and do not search deeper than optimal solution.

Uniform Cost Search (UCS)

• Complete, Optimal
• Space and Time complexity: O(b^c*/eta)
• We use a greedy policy on the g(n) measurement.

Bi-Directional Search (BDS)

• Complete, Optimal
• Space and Time complexity: O(b^d/2)

Only DFS and DLS are not complete / optimal.

Heuristic Search Greedy Best-First Search (GBFS) Recursive Best-First Search (RBFS) A* IDA* SMA* RTA*

Anytime A* Basic idea is the longer you run the better answers you get.

CSPs: GSAT Backtracking Search Heuristic Repair Hillclimbing

Reinforcement Learning MDPs POMDPs HMMs

CSP:

Heuristic Repair using Min-Conflicts Heuristic:

1. Define conflicts for a variable’s assignment to be the number of neighboring territories of the saqme color. 2. Create a random assignment of variables to their domains 3. Randomly choose a variable (or choose the most conflicted one) and identify its minimally conflicted value (break ties evenly). Assign it that value. 4. Repeat

Hierarchical Search

Abstract nodes within a certain distance of each other to a single abstract node. Search within the abstract space to find an abstract goal node. Search within the abstract nodes to find the paths between real nodes for each abstract node; thus building the whole path to the goal in real nodes.

If there are a number of hs that are very small, you should weight the g() factor higher since it will give you a better direction estimate. We want to apply more accurate heuristics early on to prune the search space closer to the start node; but only if the cost of applying the heuristic is less than the time required to search the additional nodes. Cheaper heurstics let you find a solution faster. Better heuristics let you find the solution faster if your h values are already small.

Real Time A* (RTA*)

• Achieves goals of limited search horizon and commitment to moves in constant time.
• RTA makes locally optimal actions and is guaranteed to find a solution.

  The search horizon reachable with RTA  grows (paradoxically?) with the branching factor.

• Minimax lookahead search
• Alpha pruning

1. Planning / Minimin Lookahead Phase. The algorithm searches forward from the current state to a fixed depth and then applies the A* evaluation function to the frontier nodes.
2. Execution Phase. The smallest (best) f-values are then backed up and a single step in the direction of the best child is executed.
3. Loop. We go back to step 1 using the new state of the system as the initial search node.

• If a dead-end is encountered, a value of infinity is backed up for that node.
• Given a monotonic f (and h), we can apply alpha pruning. We maintain alpha, the lowest f-value encountered on the frontier. When we generate a node, we immediately prune it if it’s f-value is greater than alpha. This is possible because a monotonic f means that children of the pruned node could not have better f-values than alpha. Each time we enter the planning phase again, we initially set alpha to infinity.
• We don’t immediately move to the best fronteir node so as to employ a strategy of least commitment. Additional information may be available after the first move that may affect the search frontier and the next move.
• After each minimin lookahead search in planning mode, an action is executed in execution mode, then we enter back into planning mode starting at the new state.
• Simply re-applying minimin search will cause the algorithm to loop infinitely between certain states. Excluding previously visited states wont help either. We want to prevent infinite loops while permitting backtracking when it is favorable.
• Minimin lookahead is for planning phase. RTA* is for execution phase.

  In RTA , the merit of a node n is the evaluation function. However, g(n) in RTA* is relative to the last state we just physically executed.

• So, g(n) is always computed from the current state of execution, not from an initial, static, node. We could simply maintain a n open list of nodes and then as a move is made in the real world, increment/decrement appopriate nodes g(n) values to reflect their new distance to the current state.
• The problem here is that (1) time to make a move is is linear in size of open list. (2) it is not clear how to update the g-values, (3) it is not clear how to find the path to the next destination node chosen from open.
• All these problems can be solved in constant time by maintainina hash table of nodes that have been visited by an actual move, together with an h-value for them.
  1. Expand current state and generat neighbors and apply heurstic function applied to each state no in hash table.
  2. For states in hash table, we use stored value of h instead.
  3. We update the f-values to reflect actual distance from current state.
  4. The node with minimum is is chosen for the state and a move is executed.
  5. The previous state is stored in the hashtable, with its f-value being the best f-value of it’s child nodes.

Hierarchical A*

• Based on the notion that searching can be done in a space of abstract states that each corresponding to multiple “base states”.
• Search in the abstract space (and heurstics computed from it) therefore expands fewer nodes, but this must be weighed against the computational cost of the abstraction.

Hierarchical A*

• Based on the notion that searching can be done in a space of abstract states that each corresponding to multiple “base states”.
• Search in the abstract space (and heurstics computed from it) therefore expands fewer nodes, but this must be weighed against the computational cost of the abstraction.

Hierarchical A*

• Based on the notion that searching can be done in a space of abstract states that each corresponding to multiple “base states”.
• Search in the abstract space (and heurstics computed from it) therefore expands fewer nodes, but this must be weighed against the computational cost of the abstraction.

Blackboard Architectures:

• Blackboard Architectures consist of (1) multiple Knowledge Sources, (2) a Blackboard Area, and (3) a Control Mechanism.
• Hypotheses are potential partial solutions generated by knowledge sources and posted to the blackboard area.
• Knowledge Sources (KSs) are independent modules that accept hypothesis (from potentially many levels of abstraction) as input, then process them and generate new hypothesis along with a confidence measure (aka credibility). KSs can be schematized as <condition, action> pairs, since they have conditions that must be met prior to the application of their actions to the blackboard.
• The control mechanism in a blackboard architecture manages posting and notification of hypothesis, as well as scheduling application of actions. It also is responsible for directing the search, and thereby embodies the general strategy by which the blackboard executes its goal-directed search for a complete solution.
• The Blackboard Area is structured as a loose hierarchy of levels, intended to abstract and categorize hypothesis stored in it.
• Blackboards combine collaboration across multiple knowledge sources to generate, modify, and promote/eliminate hypotheses. The inputs and outputs from a knowledge source often come from different levels of abstraction, and are shared in an entity called the blackboard. Knowledge sources are notified when something is posted to the blackboard and given the chance to modify its contents by a control mechanism.
• Blackboard Search creates a space of candidates and then searches for a satisficing solution. This narrows down the total search space by promoting the most likely partial solutions and then combining them into aggregate solutions. The aggregate solutions are then pruned or modified to maximize their credibility across multiple knowledge sources. The blackboard is thus competitive from the point of view of hypothesis and collaborative from the point of view of knowledge sources.
• Blackboard search is useful in situations with very large search spaces, noisy or incomplete input data, and imprecise or incomplete problem-solving knowledge. It allows for incremental solution building, and multiple concurrent lines of reasoning at multiple levels of abstraction. Additionally, blackboard search can take advantage of islands of certainty (hypothesis with high confidence) to further constrain the search space.
• Selective Attention attempts to allocate computational resources to the most promising hypothesis. Alternatives compete for resources.
• Globally significant actions are those that contribute to the detection, formation, or extension of commbinations of redundant hypothesis. These are applied in order of importance by a heuristic scheduler.

Other search terminology

• Open List - the list of unexpanded nodes (e.g. the FIFO queue in BFS, or the priority queue in A*)
• Closed List - the list of explored nodes no longer being considered by the search algorithm
• Fringe - The open list (the nodes along the edge of the graph that have not been explored)

Converting N-Sat into 3-Sat

• 3-SAT works on large propositional variable descriptions
• A+B+C+D → (A+B+E)(E’+C+D)
• Do truth table, this collapses across a row
• 2-SAT is polynomial time, but can’t map all into 2-sat