Artificial Intelligence - Old Questions

3.  In problem solving, why problem formulation must follow goal formulation? How state space representation can be used to solve a problem? Support your answer with an example.

In goal formulation, we decide which aspects we are interested in and which aspects can be ignored. In the goal formulation process, the goal is to be set and we should assess those states in which the goal is satisfied. In problem formulation, we decide how to manipulate the important aspects, and ignore the others. So, without doing goal formulation, if we do the problem formulation, we would not know what to include in our problem and what to leave, and what should be achieved. So problem formulation must follow goal formulation. That means problem formulation must be done only after the goal formation is done.

In the state space representation of a problem, nodes of a graph correspond to partial problem solution states and arcs represent steps in a problem- solving process. An initial state, corresponding to the given information in a problem instance, forms the root of the graph. The graph also defines a goal condition, which is the solution to a problem instance. State space search characterizes problem solving as the process of finding a solution path from the start state to a goal state. Arcs of the state space correspond to steps in a solution process and path through the space represent solutions in varying stages of completion. Paths are searched, beginning at the start state and continuing through the graph until either the goal description is satisfied or they are abandoned.

E.g.

State Space representation of Vacuum World Problem:

States: two locations with or without dirt: = 8 states.

Initial state:  Any state can be initial

Actions:  {Left, Right, Suck}

Goal test: Check whether squares are clean.

Path cost:  Number of actions to reach goal.