problem

In the field of artificial intelligence, a problem is a collection of information that an agent can use to decide what to do. Different types of problems are defined in different ways, but the most basic problem, the single-state problem, is defined by 4 characteristics:

• the initial state
• the set of operators (or alternately the successor function)
• the goal test
• the path cost function

A state is a set of parameters that describe the part of the world at a given point in time that is relevant to the problem. The initial state is the state the agent knows it will be in when it starts. For example, in the two water jugs problem the initial state is "both jugs empty."

An operator is an action that the agent can perform at a given state. Operators available to an agent at the initial state of the water jugs problem are "fill jug 1" and "fill jug 2". The set of all possible operators together with the initial state defines the state space, all possible states that can be reached from the initial space. A path in this state space is simply a series of actions that lead from one state to the next.

The goal test is a test which the agent can apply to a single state description to see if it has "solved" the problem. In the water jugs problem, the goal test would return true when the specified amount of water is in the correct jug. A solution is a path that leads from the initial state to a goal state. A path cost function assigns a cost to a path. An optimal solution to a problem is the least expensive solution possible.

Only slight modifications to this definition are necessary for a multi-state problem, such as when the world is not accessible to the agent (i.e., the agent is unable to determine exactly which state it is in at any given point in time). The initial state is replaced by an initial state set, the set of all possible initial states (which may well be the entire state space), and the state space is replaced by the state set space, which is all possible state sets that can be reached from the initial state set. An operator is applied by returning the union of the results of the operator on each individual state in the current state set, and a solution consists of a path that leads to a state set in which all states are goal states.

Prob"lem (?), n. [F. probleme, L. problema, fr. Gr. anything thrown forward, a question proposed for solution, fr. to throw or lay before; before, forward + to throw. Cf. Parable. ]

1.

A question proposed for solution; a matter stated for examination or proof; hence, a matter difficult of solution or settlement; a doubtful case; a question involving doubt.

Bacon.

2. Math.

Anything which is required to be done; as, in geometry, to bisect a line, to draw a perpendicular; or, in algebra, to find an unknown quantity.

⇒ Problem differs from theorem in this, that a problem is something to be done, as to bisect a triangle, to describe a circle, etc.; a theorem is something to be proved, as that all the angles of a triangle are equal to two right angles.

Plane problem Geom., a problem that can be solved by the use of the rule and compass. -- Solid problem Geom., a problem requiring in its geometric solution the use of a conic section or higher curve.

 

© Webster 1913.