water jug problem in ai: You are given 2 jugs, a 4-gallon one and as any measuring markers on that. there’s a pump l the jugs with water. however are you able to get exactly two A water jug problem three -gallon one. Neither ha that may be used to fill with water gallons of water into the 4-gallon jug?.
The state space for this problem will be described because the set of ordered pairs of integers (t y). such that-0, 1,2,3, or 4 and y- 0, 1,2, or 3; x represents the number of gallons of water within the 4-gallon jug, Water Jug Problem Artificial Intelligence and y represents the quantity of water within the 3-gallon jug. the beginning state is (0, 0). The goal state is (2, n) for any value of n (since the problem doesn’t specify how many gallons must be within the 3-gallon jug) The operators to be used to solve the problem d as shown in Figure 2.3. As within the chess problem, they’re represented as rules whose left sides are matched against this state and whose right sides describe the new state that results from applying the rule.
To solve the water jug problem, all we want, in addition to the problem description given on top of, maybe a control structure that loops through an easy cycle within which some rule whose left side matches this state is chosen, the appropriate change to the state is created as described within the corresponding right side, and therefore the ensuing state is checked to determine if it corresponds to a goal state. As long because it doesn’t, the cycle continues. Clearly the speed with that the matter gets resolved depends on the mechanism that’s used to choose the next operation to be performed. In Chapter three, we tend to discuss several ways that of making that selection.
The extreme of this approach is shown within the 1st tic-tac-toe program of Chapter every entry within the moving vector corresponds to a rule that describes an operation. The left side of every rule describes a board configuration and is represented implicitly by the index position. the right side of every rule describes the operation to be performed and is represented by a nine-element vector that corresponds to the resulting board configuration. each of those rules is maximally specific: it applies only to a single board configuration, and, as a result. no search is needed once such rules are used.
However, the drawback to the current extreme approach is that the problem solver will take no act the least bit during a novel situation. In fact, essentially no problem solving ever extremely happens For a lic-tac-toe enjoying the program, this can be not a serious problem. since it’s possible to enumerate all the situations (i.e., board configurations) which will occur. except for most problems, this can be not the case. in order to solve new problems, additional general rules should be available.
Production Rules for Water Jug Problem
if x < 4
|→ (4, y)||Fill the 4-gallon jug|
if y < 3
|→ (x, 3)||Fill the 3-gallon jug|
if x > 0
|→ (x – d, y)||Pour some water out of 4-gallon jug|
if y > 0
|→ (x, y – d)||Pour some water out of 3-gallon jug|
if x > 0
|→ (0, y)||Empty the 4-gallon jug on the ground|
if y > 0
|→ (x, 0)||Empty the 3-gallon jug on the ground|
if x + y ≥ 4 and y > 0
|→ (4, y -(4 – x))||Pour water from the
3-gallon jug into the
4-gallon jug until the
4-gallon jug is full
if x + y ≥ 3 and x > 0
|→ (x -(3 – y), 3)||Pour water from the
4-gallon jug into the
3-gallon jug until the
3-gallon jug is full
if x + y ≤ 4 and y > 0
|→ (x + y,0)||Pour all the water
from the 3-gallon jug
into the 4-gallon jug
if x + y ≤ 3 and X > 0
|→ (0, x + y)||Pour all the water
from the 4-gallon jug
into the 3-gallon jug
|11||(0,2)||→ (2, 0)||Pour the 2 gallons
from the 3-gallon jug
into the 4-gallon jug
|12||(2,y)||→ (0, y)||Empty the 2 gallons in
the 4-gallon jug on
Figure: Production Rules for the Water Jug Problem
One Solution to the Water Jug Problem
Gallons in the 4-Gallon jug Gallons in the 3-Gallon jug Rule Applied
Figure: One Solution to the Water Jug Problem
A second issue is exemplified by rules 3 and 4 in Figure 2.3. Should they or should they not be included in the list of available operators? Emptying AN unmeasured quantity of water onto the ground is certainly allowed the problem statement. But a superficial preliminary analysis of the problem makes it clear that doing so will never get us any closer to a solution. Again, we see the tradeoff between writing a set of rules that describe just the problem itself, as opposed to a set of rules that describe both the problem and some knowledge about its solution. Rules 11 and 12 illustrate a third issue.
To see the problem-solving knowledge that these rules represent, look at the last two steps of the solution shown in Figure 24 Once the state (4, 2) is reached, it is obvious what to do next. The desired 2 gallons have been produced, but they are in the wrong jug. So the thing does move them (rule 11). But before that can be done, the water that is already in the 4-gallon jug must be emptied out (rule 12).
The idea behind these special-purpose rules is to capture special-case knowledge that can be used at this stage in solving the problem. the less do not actually add power to the system since the operations they describe already provided by rule 9 (in the case of rule 11) and by rule 5 (in the case of rule 12) n fact, depending on the control strategy that is used for selecting rules to use rube are problem solving, the use of these rules may degrade performance. But the use of t rule s may also improve performance if the preference is given to special-case rules (as discussed in Section 6.4.3).
Water Jug Problem Artificial Intelligence
Summarizing what we have just said, in order to provide a formal description of a problem, we must do the following:
- Define a state space that contains all the possible configurations of the relevant objects (and perhaps some impossible ones). It is, of course, possible to define this space without explicitly enumerating all of the states it contains.
- Specify one OR more states within that space that describes possible situations from which the problem-solving process may start. These states called the initial states.
- Specify one or more states that would be acceptable as solutions to the problem.
- Specify a set of rules that describe the actions (operators) available. Doing this e What unstated assumptions are present in the informal problem description? e How much of the work required to solve the problem should be precomputed These states are called goal states. will require giving thought to the following issues: How general should the rules be? and represented in the rules?
Water Jug Problem in ai SUMMARY
The problem can then be solved by using the rules, the combination with an appropriate- ate control strategy, move through the problem space until a path from an initial state to a goal state found. Thus the process of search is fundamental to the problem-solving process. The fact that search provides the basis with the process of problem-solving not, however, mean that other, more direct approaches cannot also be exploited.
Whenever possible, they can be included as steps in the search by encoding them into the rules. For example, in the water jug problem, we use the standard arithmetic operations as single steps in the rules. We do not use the search to find a number with the property that it is equal to y (4 x). Of course, for complex problems, more sophisticated computations will be needed. Search is a general mechanism that can be used when no more direct method is known. At the same time, it provides the framework into which more direct methods for solving subparts of a problem can be embedded.