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:
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.