# Week 1c - General Search
###### [Video Link](https://www.dropbox.com/s/ufo6a11uhj057fu/Week%201c%20-%20General%20Search.mp4?dl=0)

## Outline
- Formulate a problem in terms of state space, initial state, goal test, actions, transition model, path cost
- Understand the general characteristics behind search strategies

## Problem Solving Agents
### Motivating Example: Romania Holiday
- Formulate Goal:
- What is the desired end state?
- Goal: Reach Bucharest
- Formulate search problem
- What actions & states to consider?
- States: Individual cities
- Actions: Move from city to city
- Search for solutions
- Determine the sequence of actions that lead to the goal
- e.g. Arad -> Sibiu -> Fagarus -> Bucharest

### Search Problem Formulation
- State space, e.g. At(Arad)
- Initial state, e.g. At(Arad)
- Actions
- Transition model (State+Action=State), e.g. Result(At(Arad),Go(Zerind)) -> At(Zerind)
- Path cost (additive), e.g. sum of distances, number of actions
- Goal test (explicit or implicit). Explicit means that the goal is at a particular state (e.g. At(Bucharest)). Implicit means that the goal can exist in multiple states (e.g. checkmate(x), there are multiple states of checkmate situation)

### Search Problem Solution
A **solution** is a sequence of actions from the initial state to a goal state.
An **optimal solution** is a solution with the lowest path cost.

### Problem Formulation
There are various things to consider:
Many different possible representations for states, actions, transition model, path cost. The choice affects the combinatorial search space and how fast we can find a solution.

### Exercise: Vacuum-cleaner world

### Exercise: 8-Puzzle

### Selecting a State Space
Real world is very complex, and thus state space must be abstracted for problem solving.

Abstract state is actually a set of real states
Abstract action is actually a complex combination of real actions.
Abstract solution is then the set of real paths that are solutions in the real world.

Each abstract action should be easier than the real problem. This means, once the actions are abstracted, we are focusing on a smaller subset that still exists in a real world but provides a simpler representation of the problem that could be solved easier using an agent.

## General Search

### Basic Search Algorithms
Finding solutions to search problems require searching the state space. The complexity of space hence depends on the state representation.

Explicit Tree Generation:
Root = initial state
Nodes and leaves = generated through transition model (successor function)

Tree search treats different paths to the same state as distinct.

#### General Tree Search
###### Question: in GTS, is there any loop detection mechanism
Exploring all possible states in the state space. States are expanded by generating successors of already-explored states.

Pseudocode:


The frontier is the set of states that are available for expansion (i.e. can be applied actions to)
In this example, the frontier is only the state of Arad.

Choosing which leaf node to expand determines our search strategy.


### States and Nodes
A **state** is a representation of a physical configuration.

A **node** is a data structure constituting part of a search tree. It comprises state, parent-node, child-node(s), action, path-cost, depth.

In contrast, states do not have parents, children, depth, or path cost.

The Expand function creates new nodes and their various fields using the Actions and Transition Model to create the corresponding states.

### Search Strategies
A **search strategy** is defined by picking the **order of node expansion**, i.e. which node to remove from the frontier.
Strategies can be evaluated using the following dimensions:
- Completeness: does it always find a solution if it exists?
- Optimality: does it always find a least-cost solution?
- Time complexity: number of nodes generated/expanded
- Space complexity: maximum number of nodes in memory.

Branching factor: number of child nodes that a parent node expands to.

### Tree Search Problem
In the Bucharest Holiday Problem, there is a problem of repeated states. Redundant paths can cause a tractable problem to become intractable.
This will lead to an infinite depth.
A solution is to treat this as a Graph search.
The tree search is modified to keep track of previously visited states (to not revisit).
But potentially large number of states to track, which is a memory tradeoff.

## Graph Search vs Tree Search

This is merely a general algorithm. Graph coloring can be implemented for a more optimized solution (rather than storing the array of nodes).

## Types of Search
- Uninformed Search: No additional information about states beyond that in the problem definition (aka blind search)
- Informed Search: Uses problem-specific knowledge beyond the definition of the problem itself
- Adversarial Search: Used in multi-agent environment where the agent needs to consider the actions of other agents and how they affect its own performance.