Thursday, January 22, 2009

Measuring problem-solving performance

COMPLElrENESS 0 Completeness: Is the algorithm guaranteed to find a solution when there is one?
OPTIMALUTY 0 Optimality: Does the strategy find the optimal solution, as defined on page 62?
TIME COMPLEXITY 0 Time complexity: How long does it take to find a solution?
SPACE COMPLEXITY 0 Space complexity: How much memory is needed to perform the search?

1. Sensorless problems (also called conformant problems): If the agent has no sensors
at all, then (as far as it knows) it could be in one of several possible initial states, and
each action might therefore lead to one of several possible successor states.
2. Contingency problems: If the environment is partially observable or if actions are
uncertain, then the agent's percepts provide new information after each action. Each
possible percept defines a contingency that must be planned for. A problem is called
adversarial if the uncertainty is caused by the actions of another agent.
3. Exploration problems: When the states and actions of the environment are unknown,
the agent must act to discover them. Exploration problems can be viewed as an extreme
case of contingency problems.