For the fundamentals we’ve looked at, including state space formulation, forward search, heuristics, calculating utility and managing constraints, we’ve assumed that everything is certain. That is, the current state and all states in the problem are known.
Introduction to Uncertainty
We look at different issues:
- Observability: is the state fully observable or only partially?
- Single or multi-agent: how many agents are affecting the state at once?
- Determinism: is the world determinism or stochastic? (does it hold) Does an action actually get you to the intended state or not.
- Episodic: are our actions only influenced by the current state or do we need require additional memory?
- Static: does the environment change or not change over time?
- Discrete: does time operate as discrete steps or is it continuous?
All the problems we’ve looked at so far are:
- Fully Observable: current state, all states, and all actions are known
- Deterministic: we assume that a given action will always go to a certain state
Example: Simple Maze
Lets say we are navigating in a maze. It is simple to solve using uninformed or heuristic-driven search, but challenging when the problem space is not deterministic.
 |  |
|---|
Non-deterministic actions mean that the state transition system is no longer consistent.
For example, we could move in a different direction that the intended one in some cases: 
Our original plan now has a 33% success rate.