Problem Solving In AI

Problem Solving:(CsIt Nepal)

Problem solving, specifically in AI, may be distinguished as a systematic search through a range of possible actions in order to reach some predefined goal. Problem-solving methods are split into special purpose and general purpose. A special-purpose method is tailor-made for a particular problem and often exploits very specific or certain features of the situation in which the problem is embedded. In contrast, a general-purpose method is applied on to a wide variety of problems. One general-purpose technique used in AI is means-end analysis—a step-by-step, or incremental, reduction of the difference between the present state and the final goal.

Four common steps in problem solving:

• Goal formulation

What are the conceivable successful world states

• Problem formulation

What actions and states to contemplate given the goal

• Search

Determine the possible sequence or flow of actions that lead to the states of known values and then choosing the best sequence.

• Execute

Give the solution perform the actions.

Problem formulation:

A problem can be defined as:

• 1. An initial state: State from which agent start
  2. Successor function: Specification of possible actions available to the agent.
  3. Goal test: Examine whether the given state is goal state or not
  4. Path cost: Sum of cost of each path from initial or start state to the given state.

A solution is defined as sequence of actions from initial to goal state. Optimal solution has the lowest path cost.

Defining the Problem as a State Space Search(CsIt Nepal)

In order to build a program that could play chess, at the very beginning it is necessary to specify the starting position of the chess board, the rules that define the legal moves and the board positions that represent a victory of one side or the other. Moreover, it is necessary to make the game for not only playing a legal game, but also winning the game, if possible. The problem for such program is that there has to be a separate rule for each of the roughly 10 or 20 possible board positions. Hence, numerous rules cause two serious practical difficulties:

1. No person could ever supply a complete set of such rules. It would take long time and could certainly not be done without mistakes.
2. No program could easily handle all such rules. In order to minimize such problems, it should be tried to write the rules describing the legal moves in generalized way as much as possible. For this, it is necessary to introduce some convenient notation for patterns and substitutions.

Here, the problem of playing chess is defined as a problem of moving around in a state space, where each state corresponds to a legal position of the board. The state space representation creates the basis of most of the AI methods. Its structure corresponds to the structure of problem solving in two important ways:

1. It allows a formal definition of a problem necessary to convert some given situation into some desired situation using a set of permissible operations.
2. It allows defining the process of solving a particular problem as a combination of known techniques and search.

A Water Jug Problem: (CsIt Nepal)

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither have any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?

The state space for this problem can be described as the set of ordered pairs of integers (x, y), such that x=0, 1, 2, 3….. and y=0, 1, 2, 3…..; x represents the number of gallons of water in the 4-gallon jug, and y represents the quantity of water in the 3-gallon jug. Here the initial state is (0, 0) and the final state is (2, n) for any value of n (since the problem does not specify how many gallons need to be in the 3-gallon jug). The operators to be used to solve the problem can be described as follows:

1. (0, 0) Empty both jugs
2. (0, 3) Fill the 3-gallon jug
3. (3, 0) Pour all the water from 3-gallon jug to 4-gallon jug
4. (3, 3) Fill the 3-gallon jug

5. (4, 2) Pour water from the 3-gallon jug to 4-gallon jug completely full
6. (0, 2) Empty the 4-gallon jug on the ground
7. (2, 0) Pour all the water from 3-gallon jug to 4-gallon jug

Operationalization is the process of creation of a formal and manipulability description of the problem. It is the first step toward the design of a program to solve a problem. We expect to create such programs which can themselves produce formal descriptions of the problems from the informal ones. In order to provide a formal description of a problem, the following things are to be done:

1. Define a state space that contains all the possible configuration of the relevant objects.
2. Specify one or more states within the space that describe possible situations from which the problem-solving process may start. These states are known as the initial states.
3. Specify one or more states that would be acceptable as solutions to the problem. These states are known as the goal states.
4. Specify a set of rules that describe the actions (operators) available. While doing these, the following issues are to be highlighted:

• What unstated assumptions are present in the informal problem description?
• How much the rules should be generalized?
• How much of the work required solving the problem should be pre-computed and represented in the rules. In combination with an appropriate control strategy, the problem can be solved by applying the rules; moving through the problem space until a path from an initial state to a goal state is found. Hence the search process is fundamental to the problem-solving process. Search is the general technique of exploring the space to try to find some path from the current state t a goal state. In short, search is a general mechanism which can be used when no direct method is known.

Production Systems:(CsIt Nepal)

Since search is a very important process in the solution of hard problems for which no more direct techniques are available, it is useful to structure AI programs in a way that enables describing and performing the search process. Production systems provide such structures. A production system consists of:

1. A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if the rule is applied.
2. One or more knowledge or databases that contain whatever information is appropriate for the particular task.
3. A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
4. A rule applier.

Characteristics of Control Strategy

1. The first requirement of a good control strategy is that it causes motion. Control strategies that do not cause motion will never lead to a solution. For it, on each cycle, choose at random from among the applicable rules. It will lead to a solution eventually.
2. The second requirement of a good control strategy is that it be systematic. Despite the control strategy causes motion, it is likely to arrive at the same state several times during the search process and to use many more unnecessary steps. Systematic control strategy is necessary for the global motion i.e. over the course of several steps as well as local steps i.e. over the course of single step.

Combinatorial explosion: is the phenomenon of the time required to find an optimal schedule (solution) being increased exponentially. In other words, when the time required solving the problem takes more than the estimated time, the phenomenon is known as combinatorial explosion

Constraint Satisfaction Problem:(CsIt Nepal)

A Constraint Satisfaction Problem is defined by:

• a set of variables {x₁, x₂, .., x_n},
• for each variable xi a domain Di with the possible values for that variable, and
• a set of constraints, i.e. relations, that are assumed to hold between the values of the variables. [These relations can be given intentionally, i.e. as a formula, or extensionally, i.e. as a set, or procedurally, i.e. with an appropriate generating or recognizing function.] We will only consider constraints involving one or two variables.

The constraint satisfaction problem is to find, for each i from 1 to n, a value in D_i for x_i so that all constraints are satisfied. Which means that, we must find a value for each of the variables which satisfies all of the constraints.

A Constraint Satisfaction problem can easily be defined as a sentence in first order logic, of the form:

(exist x₁ )..(exist x_n) (D₁(x₁) & .. Dn(xn) => C1..Cm)

A Constraint Satisfaction problem is normally represented as an undirected graph, called Constraint Graph where the nodes are the variables and the edges are the binary constraints. Unary constraints can be disposed of by just redefining the domains to contain only the values

that satisfy all the unary constraints. Higher order constraints are represented by hyperarcs. We restrict our attention to the case of unary and binary constraints in the following.

Formally, a CS problem is defined as a triple (X, D, C), where X is a set of variables, D is a domain of values, and C is a set of constraints. Every constraint is in turn a pair (t, R), where t is a tuple of variables and R is a set of tuples of values; all these tuples having the same number of elements; as a result R is a relation. An evaluation of the variables is a function from variables to values, v: X à D. Such an evaluation satisfies a constraint ((x_1,…,x_n), R) _if (v(x₁),…,v(x_n)) € R . A solution is an evaluation that satisfies all constraints.

Constraints

ï‚· A constraint is a relation between a local collection of variables.

ï‚· The constraint restricts the values that these variables can simultaneously have.

ï‚· For example, all-diff(X1, X2, X3). This constraint says that X1, X2, and X3 must take on different values. Say that {1, 2, 3} is the set of values for each of these variables then: X1=1, X2=2, X3=3 OK X1=1, X2=1, X3=3 NO

The constraints are the key component in expressing a problem as a Constraint Satisfaction Problem.

ï‚· The constraints are determined by how the variables and the set of values are chosen.

ï‚· Each constraint consists of;

1. A set of variables it is over.
2. A specification of the sets of assignments to those variables that satisfy the constraint.

ï‚· The idea is that we break the problem up into a set of distinct conditions each of which have to be satisfied for the problem to be solved.

Reference

CsIt Nepal. (n.d.). Retrieved from csitnepal.com: http://csitnepal.com/elibrary/notes/

Knight., E. R. (n.d.). Artificial Intelligence. In E. R. Knight.. The McGraw-Hill Companies.

Longman, J. F. (n.d.). Computer Netwroking: A top-down approach featuring the Internet. In a. F. Longman, Computer Netwroking: A top-down appriach featuring the Internet (p. 65).

Patterson., D. W. (n.d.). Introduction to Artificial Intelligence and Expert Systems. In D. W. Patterson., Introduction to Artificial Intelligence and Expert Systems. Prentice Hall.

slideshare. (n.d.). Retrieved from www.slideshare.net: http://www.slideshare.net/u053675/artificial-intelligence-1419854

Stuart Russell, P. N. (n.d.). Artificial intelligence : a modern approach. In P. N. Stuart Russell, Artificial intelligence : a modern approach. pearson.

tutorialspoint. (n.d.). Retrieved from www.tutorialspoint.com: http://www.tutorialspoint.com/artificial_intelligence/artificial_intelligence_tutorial.pdf

Winston, P. H. (n.d.). Artificial Intelligence. In P. H. Winston, Artificial Intelligence. addison wesley.