2.6 Types of Problems (BT104CO)
1. Categorizing Problems by Environment Knowledge
In the framework of Russell and Norvig, the nature of the agent’s knowledge about its environment determines the type of problem it must solve. Not all problems are solved by simply searching a map.
Single-State Problems
Status: Deterministic & Fully Observable.
The agent knows exactly which state it is in, and every action has a predictable result.
Multiple-State (Sensorless)
Status: Known & Non-observable.
Also called Conformant Problems. The agent must find a sequence that works for all possible starts.
Contingency Problems
Status: Nondeterministic / Partially Observable.
The agent must calculate a strategy (tree of actions) rather than a single sequence.
Exploration Problems
Status: Unknown State Space.
The agent has no transition model or map. It must experiment and learn while acting.
2. The Concept of "Belief States"
Defining Belief States
For Multiple-State and Contingency problems, the agent doesn't deal with a single physical state. Instead, it deals with a Belief State—the set of all physical states that the agent believes it might be in, based on its history of actions and percepts.
3. Problem Type Comparison
| Problem Type | Knowledge | Sensor Status | Solution Type |
|---|---|---|---|
| Single-State | Known / Det. | Fully Observable | A sequence of actions |
| Multiple-State | Known / Det. | Sensorless | A sequence for all starts |
| Contingency | Uncertain / Stoch. | Partially Observable | A "Tree" or "Policy" |
| Exploration | Unknown | Varies | Learning while acting |
4. Why This Matters
Most "classic" AI algorithms assume a Single-State Problem. However, real-world AI (like a robot on Mars) almost always faces Contingency or Exploration problems, where it must react to the percepts it receives during execution.