Search Graphs
BFS and DFS are blind search algorithms meaning we have no further information about the tree.
Solving Problems by Searching
Considering that there is a goal-based agent that want to bring about a state of affairs by completing some actions. These actions need to be ordered in order to reach the goal. We may also want to minimise time or fuel consumption. This is all part of the problem formulation.
- Describing the Goal
- Describing the Relevant State of the Environment
- Describing the Possible Actions
- Describing the Optimality Criterion
Once the problem has been formulated, looking for a sequence of actions that lead to a goal state and is optimal is called search.
Formulating the Search Graph
S are the possible states or nodes in a graph. There can be:
- S$_\textrm{start}$ for the starting point.
- S$_\textrm{goal}$ for the goal states.
- A set of A actions that can be performed that will take the agent from one state in S to another state in S.
- There can sometimes be a cost function that states how expensive an action is. If all actions are equally expensive, we set $\textrm{cost}(a)=1$
A solution to the search problem is a sequence of actions such that when performed in the start state S$\textrm{start}$, that agents reaches a goal state in S$\textrm{goal}$. A solution is optimal if there is no less expensive solution.
Notation
For any node S, which is a state:
- The children are called successor states (s)
- The parents are called predecessor states (s’)
Abstraction
As the real world is very complex state space must be abstracted for problem solving. This can be seen as an abstract state could be any number of real states. In addition and abstract action could be any complex combination of real actions.
A good abstraction sound guarantee reasonability. E.g. Any one real state must get to another real state following the abstracted actions.
An abstract solution is a set of real paths that are solutions in the real world.