Problem Types, Well-defined Problems, Constraint Satisfaction Problem

Problem types

The types of problems are discussed below:

Single-state problem

A single-state problem is considered to be deterministic and accessible. This is because the agent knows everything about the world which means the agent is familiar with the exact state. Due to this, the agent becomes able to calculate optimal action sequence to reach the goal state. For example: While playing chess any action will result in an exact state.

Multi-state problem

While the single-state problem is deterministic and accessible the multi-state problem is deterministic and inaccessible. This is because the agent does not know the exact state which means it could be any of the possible states. It may not have any sensor at all. In this type of problem, the assumption is made while working towards goal state. For example: Walking in a dark room. If you are at the door, going straight will lead you to the bedroom. If you are in the bedroom, going left leads you to the kitchen.

Senseless problem

The second name given to the senseless problem is a confirmative problem. This type of problem does not have any sensor. If the agent has no sensor, it could be in any one of the several possible initial states and each action might lead to one of several possible successor states.

Contingency problem

A contingency problem is said to be non-deterministic and inaccessible. This type of problem must use sensors during execution. If the environment is partially observable then agents' perception provide new information after each action. Each possible perception defines a contingency that must be planned for. For example A new skater in the arena. There may be a sliding problem and could be many skaters around.

Exploration problem

This problem has an unknown state space. This means the states and actions of the environment are unknown. The agents must act to discover them. So far we have assumed that the robot is ignorant about which room are dirty. But the robot knows how many rooms are there and the effect of each action. If the robot is completely ignorant then such type of problem is exploration. Another example is the maze where the agent discovers and learn about the environment while taking actions.

Components of a well-defined problem

• Initial state
• Available actions are given by successor function where initial state + successor function define state space. The path is a sequence of states connected by actions.
• Goal test that determines whether the current state is a goal state or not.
• Path costs which is the sum of step costs.

Solution to a well-defined problem is a path from an initial state to a goal state. An optimal solution has the lowest path cost among all the solutions. That means a quality of a solution is measured by the path cost.

Constraint satisfaction problem

The general problem is to find a solution that satisfies a set of constraints. A heuristic is used not to estimate the distance to the goal but to decide which node to expand next. Examples of this technique are designed problem, labeling graph, robot path planning, and cryptarithmetic.

Cryptarithmetic puzzle is an example of constraint satisfaction problem in which the goal to be discovered satisfies a given set of constraints.

States: A cryptarithmetic puzzle w/ some letters replaced with digits.

Actions: Replacing a letter with an unused digit.

Goal test: Puzzle contains only digits.

Path cost: ZERO. All solutions equally valid.

References:

1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.