Search techniques

Part of the School of Computer Science
Topic:Artificial intelligence
Artificial intelligence
History of artificial intelligence Intelligent Agents Search techniques Constraint satisfaction Knowledge Representation and Reasoning Logical inference Reasoning under Uncertainty Decision Making Learning and neural networks Bots

Purpose of searching: Find path to desired Goal State from all future states possible.

Uninformed search

Uninformed search, also called blind search, is a class of general purpose search algorithms that operate in a brute-force way. These algorithms can be applied to a variety of search problems, but since they don't take into account the target problem.

Breadth-first search

• Each level (or depth) of the search tree is explored before expanding its nodes to search their children.
• Uses a FIFO QUEUE
• Advantage: Simple to implement
• Disadvantage: Heavy memory requirements

Depth-first search

• Drills deep into the hierarchy, exploring one lineage until it reaches the child/leaf node with no successors (or it's goal, of course).
• Advantage: Improves on the memory requirements by deleting entire line once explored.
• Disadvantage: Potential to run into infinitely deep search path (non-complete)

Depth-limited search

• Depth-first search with a limit on the depth.
• Mitigates infinite depth path of Depth-first search by cutting the tree on the limit depth
• Will fail to reach goal if goal resides deeper than depth limit .

Iterative deepening depth-first search

• Performs iterations of depth-limited searches with increasing depth limits.
• Advantage: Unlike normal depth-first search and depth-limited search, it is complete. It also does this without greatly increasing the expected runtime.

Bidirectional search

• Searches from initial state to last state and also from the last state to initial state, stopping when the two searches meet at a node in between (or when found the goal state).
• Advantage: Time and memory requirements good, comparatively
• Disadvantage: Not always feasible, or possible, to search backward through possible states.

Informed search

• If information is available about the problem this could guide the search (for example in finding the shortest route in a map: information about distances between places on map).
• Information is put in an evaluation function f(n) to be able to give a value to each state.
• Sometimes a heuristic function h(n) is used to guess the value if the information isn't perfect.

(Greedy) best-first search

• Define f(n) to be the distance to the goal (Or a good guess to the goal h(n), then f(n)=h(n)).
• Expand child with lowest f(n) value.
• advantage:
• Disadvantage: Does not always find the shortest path to the goal.

A* (A star) search

• Define f(n) to be the distance to the current state plus the expected distance to the goal: f(n) = g(n) + h(n).
• h(n) must be an admissible heuristic, ie it doesn't overestimate the distance to the goal.
• Expand child with lowest f(n) value.
• Advantage: Always finds most optimal solution.

Self Guided Projects on Search Techniques

1. Uninformed Search Project - Make a program that can help Homer Simpson find his way around Springfield
2. Simulated Annealing and Gradient Descent - Use simulated annealing to find the correct placement of baby lizards in a nursery so that they can't eat each other