Well-Defined, Knowedge Lean Problems

A problem is well-defined if all the relevant information (initial configuration of pieces on the board)all the problem-solver's options ("moves")the desired end state (configuration of pieces where opponent is checkmated)can be specified completely and unambiguously.

A problem is knowledge-lean if the knowledge required to solve itcan be specified completely and succinctly.

Solution depends only on limited knowledge (knowledge of possible chess moves) and does not depend upon extensive general knowledge.

Knowledge-lean problems are self-contained, in that the knowledge required to solve them can be specified completely and succinctly

Well-defined, knowledge lean problems : CHESS

Ill-defined, knowledge-rich problems: becoming a millionaire   or achieving world domination

Can characterise well-defined, knowledge-lean problems in terms of the transformation of problem states

A state is a snapshot of the problem solving situation. It is a complete description of all objects relevant to the problem, including features of those objects and relations between objects, at a given point in time. 

Solving a problem involves figuring out how to transform the initial state into a desired state via a sequence of allowable moves.

Well-defined, knowledge-learn problems consist of three elements: a completely specified initial state, a finite set of operators, and either a complete specification of the desired (or goal) state of a specification of a condition which is true of all and only goal states

Chess: state = conguration of pieces on the boardTowers of Hanoi: state = conguration of disks and pegsMissionaries and cannibals: state = conguration of missionaries, cannibals, and boat

When a state space is augmented with information concerning the problem's initial and desired states it is referred to as a problem space. Within the problem space perspective, successful problem solving is simply a matter of selection of moves, in sequence, which transform the initial state of the problem into a desired state.

Adopting the problem space view of problem solving makes clear that the principal issue in solving a problem concerns the selection, in an appropriate sequence, of a series of moves.

2 questions: Typically several moves are applicable in any state. Given a particular state, then, how do we determine which moves are applicable? Once a set of applicable moves has been determined, how do we select from that set one move to apply?

Problem Solving as a search within a problem space.To solve a problem it is necessary to search for a path from the initial state to a desired state. The "most efficient solution" is the one corresponding to the shortest path.

Breadth-first search: Consider all paths from the initial state of length one. If none of these terminate at a desired state then consider all possible paths from the initial state of length 2. Repeat the procedure extending the length of the path by one each time until a path that terminates at the desired state is found. If the problem can be solved in a finite number of moves, this procedure is guaranteed to terminate with a solution.

Well-defined Problem Solving

Knowledge-Learn Problem

State Spaces and Problem Spaces

Problem Solving as Search within a Problem Space