Search Algorithms

• States: "places" the search can visit
• Search space: the set of possible states
• Search path: sequence of states the agent actually visits
• Solution: A state which solves the given problem
• Initial State: Where the search starts
• Operators: What can the agent do to transition to another state (what states are reachable)
• Goal Test: How the agent knows if solution state has been found

• Heuristic: A estimated measure of how close we are to the final answer. Like an approximate fitness function

• Def. An artifact is the final goal only
• Def. The path is not the final goal but rather how the agent found the goal

Route finding

Known destination, must find the route (path)

Anagram puzzle

Doesn’t matter how you find the word
Only the word itself (artefact) is important

Machine learning

Usually only the concept (artefact) is important

Theorem proving

The proof is a sequence (path) of reasoning steps

• Task may require one, many or all solutions
  • Ex. How many different ways to get from A to B?

Complete search space contains all solutions

Exhaustive search explores entire space (assuming finite)
Will find solution if one exists

Pruning rules out certain operators in certain states

Space still complete if no solutions pruned
Strategy still complete if not all solutions pruned

• A sound search contains only correct solutions!
• An unsound search contains incorrect solutions
  • Caused by unsound operators or goals checks

Dangers

• Find solutions to problems with no solutions

  Find a route to an unreachable destination
  Prove a theorem which is actually false
  (This doesn't matter if your problem has a solution)

• Produce incorrect solution to problem

• Fast programs can be written
  • But they often use too much memory
• Memory efficient programs can be written
  • But they are often slow

Different search strategies have different memory/speed tradeoffs

• Given initial state, operators and goal test
  • Can you give the agent additional information?

Uninformed search strategies

Have no additional information to help your search

Informed search strategies

Uses problem specific information
Heuristic measure (guess how far from goal we are)

1. Start by searching all immediately reachable states
2. Search all immediately reachable states of those states
3. Repeat

• Def. Newly found states are put at the bottom of the priority queue
• Guarantees the shortest (but not least costly) path.
• Requires a lot of memory

1. Start with the first reachable state
2. Move to that state's first reachable state that hasn't been discovered yet
3. Move to that state's first reachable state that hasn't been discovered yet
4. If we reach a dead end move backwards until you have more states to search

• Def. Newly found states are put at the top of the priority queue
• Not complete because of indefinite paths or depth limit
• But is memory efficient

For infinitely deep search spaces (or just large ones) a depth limit can be set.

This is basically a combination of breadth and depth first search

1. Run depth first search with a small depth limit
2. Check if answer is good enough
3. If not increase depth limit by 1
4. Fully run depth first search again

• Def. Repeated depth first searches with increasing depth limit
• Combines the best of DFS and BFS
  • Both complete and memory efficient
  • However it is slower than either

You have to completely redo the previous search after each iteration, this seems inefficient however because of the way the algorithm scales a small percentage of the time is actually spent redoing searches.

• Def. Search from both sides of a search space and hope to meet in the middle.
• Only have to go half depth

Difficulties:

Do you really know the solution?
Must be able to reverse operators
Record all paths to check if they meet - Memory Intensive

• Evaluation function give the cost for each state.

  • Then. Choose state with smallest to search
• Many different strategies depending on f

  • For Uniform Cost Search
  • Informed search strategies defines based on a heuristic function

• Def. Estimate of path cost

A state closer to is more likely but not always guaranteed to be better.

In Uninformed Search Strategies we never determine which states look most promising for expansion at a given time point. We never “look-ahead” to the goal. However, we have some knowledge about the merit of states.

• Def. Choose to expand the node with the least path *cost
• This method is optimal and complete - but very slow

• Def. Always take the biggest bite
• Ignores full path cost and only pays attention to the operation cost
• Stuck in local minima
• Not complete!

Combines Uniform Cost Search and Greedy Search.

• Let. Path cost = and heuristic function =

  • Choose smallest overall path cost (known + estimate)

• Can prove that A is complete and optimal*, but only if is admissible,

  i.e. underestimates the true path cost from state to solution

• Very memory intensive as you have to record all states

Solves the memory problems with A* Search using the same iterative deepening trick as IDS

• But iterate over rather than depth
• Ex. Define contours: , , etc...
• Both complete and optimal but much less memory than A*