State And Problem Space on Methods of Inference
Kamis, 2011-11-24, 10:35:02

Oleh : Frieyadie

Graphs can be applied to many practical problems. A useful method of describing the behavior of an object is to define a graph called the state space. A state is a collection of characteristics that can be used to define the status or state of an object. The state space is the set of states showing the transitions between states that the object can experience. A transition takes an object from one state to another.

Examples of State Spaces

As a simple example of state spaces, consider the purchase of a soft drink from a machine. As you put coins into the machine, it makes a transition from one state to another. Figure 3.5 illustrates the state space assuming that only quarters and nickels are available and that 55¢ is required for a drink. Adding other coins such as dimes and fifty-cent pieces makes the diagram more complicated and is not shown here.



Figure 3.5. State Diagram for a Soft Drink Vending Machine Accepting Quarters (Q) and Nickels (N)

The start and success states are drawn as double circles to make them easier to identify. The states are shown as circles and the possible transitions to other states are drawn as arrows. Notice that this diagram is a weighted digraph, in which the weights are the possible coins that can be input to the machine in every state.

This diagram is also cafied a finite state machine diagram because it describes the finite number of states of a machine. The term machine is used in a very general sense. The machine can be a real object, an algorithm, a concept, and so forth_ Associated with every state are the actions that chive it to another state. At any time, the machine can be in only one state. As the machine accepts input to a state, it progresses from that state to another. If the correct inputs are given, the machine will progress from the start to the success or final state_ If a state is not designed to accept a certain input, the machine will become hung up in that state. For example, the soft drink machine has no provision to accept dimes. If someone puts a dime in the machine, the response is undefined. A good design will include the possibility of invalid inputs from every state and provide for transitions to an error state. The error state is designed to give appropriate error messages and take whatever action is necessary.

Finite state machines are often used in compilers and other programs to determine the validity of an input. For example, Figure 3.6 shows part of a finite state machine to test input strings for validity. Characters of the input are examined one at a time. Only the character strings WHILE, WRITE, and BEGIN will be accepted. Arrows are shown from the BEGIN state for successful input and also for erroneous input going to the error state. For efficiency, some states, such as the one pointed to by "L" and "T," are used for testing both WIT/LE and WRITE.



Figure 3.6 Part of a Finite State Machine for Determining Valid Strings WHILE, WRITE, and BEGIN.
Note:Only some of the error state transitions are shown

State diagrams are also useful in describing solutions to problems. In these kinds of applications we can think of the state space as a problem space, in which some states correspond to intermediate stages in problem solving and some states correspond to answers. In a problem space there may be multiple success states corresponding to possible solutions. Finding the solution to a problem in a problem space involves finding a valid path from start (problem statement) to success (answer). The animal decision tree can be viewed as a problem space where the yes/no responses to questions determine the state transition.

Another example of a problem space occurs in the classic Monkey and bananas problem shown in Figure 3.7. The problem is to give instructions to a monkey telling it how to retrieve some bananas hanging from the ceiling. The bananas are out of reach. Inside the room are a couch and a ladder. The initial starting configuration is typically with the monkey on the couch. instructions might be

jump off couch
move to ladder
move ladder under bananas position
climb ladder
grab bananas




Figure 3.7 The State Space for the Monkey and Bananas Problem

The instructions will vary depending on the initial configuration of monkey, couch, and ladder. Because there are a number of initial start states, the special double circle for the start is not shown. For example, another possible starting state is with the monkey on the couch under the bananas. The monkey will then have to push the couch out of the way before moving the ladder under the bananas. In the simplest starting state, the monkey is already on the ladder under the bananas.

Although this problem seems obvious to a human, it involves a considerable amount of reasoning. A practical application of a reasoning system like this is giving instructions to a robot concerning the solution of a task. Rather than assuming that all objects in the environment are fixed in place, a general solution is a reasoning system that can deal with a variety of situations. A rule-based solution to the monkeys and bananas problem is distributed with the CLIPS disks.

Another useful application of graphs is exploring paths to find a problem's solution. Figure 3.8 (a) shows a simple net for the traveling salesman problem. In this example, assume the problem is to find a complete path from node A that visits all other nodes. As usual in the traveling salesman problem, no node can be visited twice. Figure 3.8 (b) shows all the possible paths starting from node A in the form of a tree. The correct paths ABDCA and ACDBA are shown as thick lines in this graph.



(a) Graph of a Traveling Salesman Problem



(b) Search Paths (optimal path shown by thick edges)
Figure 3.8 A Traveling Salesmen Problem

Depending on the search algorithm, the exploration of paths to find the correct one may involve a considerable amount of backtracking. For example, the path ABA may first be searched unsuccessfully and then backtracked to B. From B, the paths CA, CB, CDB, and CDC will be unsuccessfully searched. Next the path BD13 will be unsuccessfully searched until the first correct path ABDCA is found.

Ill-structured Problem Spaces

A useful application of state spaces is in characterizing ill-structured problems (Pople 82). In Chapter 1 an ill-structured problem was defined to have uncertainties associated with it. These uncertainties can be specified more precisely by a problem space. As an example of an ill-structured problem, let's consider again the case of a person who is thinking about traveling and visits a travel agent, as discussed in Chapter 1. Table 3.1 lists some characteristics of this ill-structured problem as a problem space, indicated by the person's responses to the travel agent's questions.

If you compare Table 3.1 to Table 1.10 (page 19), you'll see that the concept of a problem space lets us specify more precisely the characteristics of an ill- structured problem. It is essential to characterize these parameters precisely to determine if a solution is feasible, and if so, what is needed for a solution. A problem is not necessarily ill-structured just because it has one, some, or even an of these characteristics since much depends on the severity. For example, all theorem-proving problems have an infinite number of potential solutions, but this does not make theorem proving an ill-structured problem.

As you can see from Table 3.1, there are many uncertainties, and yet travel agents cope with them everyday. While not all cases may be as bad as this, it indicates why an algorithmic solution would be very difficult.

Table 3.1 Example of an Ill-structured Problem for Travel

Characteristic	Response
Goal not explicit Problem space unbounded Problem states not discrete Interediate states difficult to achieve State operators unknown Time constraint	I'm thinking about going somewhere I'm not sure where to go I just like to travel; the destination is not important I don't have enough money to go I don't know how to get the money I must o soon

A well-formed problem is one in which we know the explicit problem, goal, and operators that can be applied to go from one state to another. A well-formed problem is deterministic because when an operator is applied to a state, we are sure of the next state. The problem space is bounded and the states are discrete. This means that there are a finite number of states and that each state is well- defined.

In the travel problem the states are unbounded because there are infinite possible destinations that a traveler might choose. An analogous situation occurs with an analog meter, which may indicate an infinite number of possible readings. if we consider each reading of the meter to be a state, then there are an infinite number of states and they are not well defined because they correspond to real numbers. Since there are an infinite number of real numbers between any two real numbers, the states are not discrete because the next state differs only infinitesimally. In contrast, the readings of a digital meter are bounded and discrete.

Source : Giarratano, Joseph. 1998. Expert Systems Priciples and Programming, Third Edition. PWS Publishing: USA