To solve problem $P$, the following 6 components are required:

1. Initial State ($s_0$): The starting point of the problem.
2. Actions ($A(s)$): The set of move (next state) or operations that the AI agent can perform in state $s$.
3. State Space ($S$): The set of all possible states, including the
4. State Transition Function ($\tau(s, a)$): Defines how the state changes when action $a$ is performed in state $s$.
5. Path Cost ($c(s, a, s')$): The cost of transitioning from state $s$ to state $s'$ via action $a$.
6. Goal Test ($G(s)$): A function that determines whether state $s$ is a goal state.

$P = \langle S, s_0, A, \tau, c, G \rangle$ is how we model it. And it is represented as a directed graph on S. The graph isnt given to us, it is generated as the problem is being solved.

The optimal solution will minimise the cost. Alternatively if actions have rewards then we want to do reward maxing.

Actions and Results

• When 1 action -> 1 result (next state) its deterministic. $\tau: S \times A \rightarrow S$
• When 1 action -> many results (set of states) its non deterministic. $\tau: S \times A \rightarrow 2^S$
• When 1 action -> many results over a probability distribution, its stochastic. $\tau: S \times A \rightarrow \Delta(S)$

Using Search

Here we will be taking a look at uninformed search where there is no distinction between the non goal states, only between the goal and non goal state.

• Brute force goes through all the possible action sequences to find one that gets to goal state.

This brings us to the question how to measure performance:

• completeness: is the solution guaranteed to be found in the state space
• time complexity: how much computation is requiredss
• space complexity: how much memory is required
• optimality: is it a good solution (low path cost function)

A general search algorithm works as such:

• Agenda: maintain an “agenda” (a list of states to explore).
• Expansion: pick a state from the agenda and generate all its successors (children) by applying valid actions .
• Goal Test: check if the new state matches the goal. If not, add the new state to the agenda.

depending on which data structure is used for agenda, the technique used can be either depth first search (DFS) or breadth first search (BFS).

BFS vs DFS Comparison

Feature	Breadth First Search (BFS)	Depth First Search (DFS)
Expansion Order	Shallowest node first (layer by layer)	Deepest node first (branch by branch)
Agenda Structure	Queue (FIFO)	Stack (LIFO)
Completeness	Yes (Guaranteed)	No (Can loop forever)
Optimality	Yes (Finds shortest path)	No (First solution found may be long)
Memory Usage	High (Exponential $b^d$)	Low (Linear $b \times d$)