Building a system to solve a problem requires the following steps

1 define the problem precisely including detailed specifications and what constitutes an acceptable solution;

2 analyse the problem thoroughly for some features may have a dominant affect on the chosen method of solution;

3 isolate and represent the background knowledge needed in the solution of the problem;

4 choose the best problem solving techniques in the solution.

DEFINING THE PROBLEM AS STATE SPACE SEARCH

In order to solve the problem play a game, which is restricted to two person table or board games, a topic which will be fully discussed later in the course, we require the rules of the game and the targets for winning as well as a means of representing positions in the game. The opening position can be defined as the initial state and a winning position as a goal state, there can be more than one. legal moves allow for transfer from initial state to other states leading to the goal state. However the rules are far to copious in most games especially chess where they exceed the number of particles in the universe 10[120]. Thus the rules cannot in general be supplied accurately and computer programs cannot easily handle them. The storage also presents another problem but searching can be achieved by hashing.

The number of rules that are used must be minimised and the set can be produced by expressing each rule in as general a form as possible. The representation of games in this way leads to a state space representation and it is natural for well organised games with some structure. This representation allows for the formal definition of a problem which necessitates the movement from a set of inital positions to one of a set of target positions. It means that the solution involves using known techniques and a systematic search. This is quite a common method in AI.

THE WATER JUG PROBLEM

There are two jugs called four and three ; four holds a maximum of four gallons and three a maximum of three gallons. How can we get 2 gallons in the jug four.

The state space is a set of ordered pairs giving the number of gallons in the pair of jugs at any time ie (four,three) where four = 0, 1, 2, 3, 4 and three = 0, 1, 2, 3.

The start state is (0,0) and the goal state is (2,n) where n is a don't care but is limited to threeholding from 0 to 3 gallons.

The major production rules for solving this problem are shown below:

initial condition goal comment

1 (four,three) if four < 4 (4,three) fill four from tap

2 (four,three) if three< 3 (four,3) fill three from tap

3 (four,three) If four > 0 (0,three) empty four into drain

4 (four,three) if three > 0 (four,0) empty three into drain

5 (four,three) if four+three<4 (four+three,0) empty three into four

6 (four,three) if four+three<3 (0,four+three) empty four into three

7 (0,three) If three>0 (three,0) empty three into four

8 (four,0) if four>0 (0,four) empty four into three

9 (0,2) (2,0) empty three into four

10 (2,0) (0,2) empty four into three

11 (four,three) if four<4 (4,three-diff) pour diff, 4-four,

into four from three

12 (three,four) if three<3 (four-diff,3) pour diff, 3-three,

into three from four

and a solution is given below

four three rule

0 0

0 3 2

3 0 7

3 3 2

4 2 11

0 2 3

2 0 10

The control strategy for selecting the rules has not yet been fully discussed but if all the rules are applied to each of the states those that are applicable will produce new states and the required goal state can be searched for.

We need to be able to create a formal description of the problem and eventually it will be possible for programs to take an informal description aof a problem and produce a formal description of the same problem. For simple problems it is easier to achieve this goal by hand but there will be cases where this is far too difficult.

Summarising, we must perform the following tasks to produce a formal specification of a particular problem:

FORMAL DESCRIPTION OF A PROBLEM

1 Define a state space that contains all possible configurations of the relevant objects, without enumerating all the states in it;

2 Define some of these states as possible initial states;

3 Specify one or more as acceptable solutions, these are goal states;

4 Specify a set of rules as the possible actions allowed. This involves thinking about the generality of the rules, the assumptions made in the informal presentation and how much work can be anticipated by inclusion in the rules.

The control strategy is again not fully discussed but the AI program needs a structure to facilitate the search which is a characteristic of this type of program.

PRODUCTION SYSTEMS

1 a set of rules each consisting of a left side the applixcability of the rule and the right side the operations to be performed;

2 one or more knowledge bases containing the required information for each task;

3 a control strategy that specifies the order in which the rules will be compared to the database and ways of resolving conflict;

4 a rule applier

Control strategies.

The first requirement is that it causes motion,-- in a game playing program the pieces move on the board and in the water jug problem water is used to fill jugs.

The second requirement is that it is systematic, this is a clear requirement for it would not be sensible to fill a jug and empty it repeatedly nor in a game would it be advisable to move a piece round and round the board in a cyclic way. We shall initially consider two systematic approaches to searching

Algorithm Breadth-First Search

1. Create a variable called NODE-LIST and set it to the initial state.

2. UNTIL a goal state is found OR NODE-LIST is empty DO

(a) Remove the first element from NODE_LIST and call it E.

IF NODE-LIST was empty quit.

(b) FOR each way that each rule can match the state described in E DO

(i) Apply the rule to generate a new state

(ii) IF the new state is a goal state quit and return this state.

(iii) Otherwise add the new state to the end of NODE-LIST.

Algorithm Depth-First Search

1. IF the initial state is a goal state, quit and return success.

2. Otherwise DO the following until success or failure is signalled

(a) Generate a successor,E, of the initial state. If there are no more successors signal failure.

(b) Call Depth-First Search with E as the initial state.

HEURISTICS

A heuristic is a method that might not always find the best solution but is guaranteed to find a good solution in reasonable time. By sacrificing completeness it increases efficiency. It is particularly useful in solving tough problems which could not be solved any other way and if a complete solution was to be required infinite time would be needed ie far longer than a lifetime. In the case of the weather forecast longer than a day.

Heuristic Search

To use heuristics to find a solution in acceptable time rather than a complete solution in infinite time. The next example illustrates the requirement for heuristic search as it needs a very large time to find the exact solution.

EXAMPLE

TRAVELLING SALESMAN

A salesperson has a list of cities to visit and she must visit each city only once. There are distinct routes between the cities. The problem is to find the shortest route between the cities so that the salesperson visits all the cities once.

Suppose there are N cities then a solution that would work would be to take all N! possible combinations and to find the shortest distance that being the required route. This is not efficient as with N=10 there are 3 628 800 possible routes. This is an example of combinatorial explosion.

There are better methods for solution , one is called branch and bound.

Generate all the complete paths and find the distance of the first complete path. If the next path is shorter save it and proceed in this way abandoning any path when its length so far exceeds the shortest path length. Although this is better than the previous method it is still exponential.

Heuristic Search

Applying this concept to the travelling salesperson problem.

1 select a city at random as a start point;

2 repeat

3 to select the next city have a list of all the cities to be visited and choose the nearest one to the current city , then go to it;

4 until all cities visited

This produces a significant improvement and reduces the time from order N! to N[2].

It is also possible to produce a bound on the error in the answer it generates but in general it is not possible to produce such an error bound.

In real problems the value of a particular solution is trickier to establish, this problem is easier as it is measured in miles, other problems have vaguer measures..

Although heuristics can be created for unstructured knowledge producing cogent analysis is another issue and this means that the solution lacks reliability.

Rarely is an optimal solution required good approximations usually suffice.

Although heuristic solutions are bad in the worst case the worst case occurs very infrequently and in the most common cases solutions now exist. Understanding why heuristics appear to work increases our understanding of the problem.

This method of searching is a genaral method which can be applied to problems of the following type.

Problem Characteristics.

1. Is the problem decomposable into a set of nearly independent smaller or easier subproblems?

2. Can the solution steps be ignored or at least undone if they prove unwise?

3. Is the problem's universe predictable?

4. Is a good solution to the problem obvious without comparison to all other possible solutions?

5. Is the desired solution a state of the world or a path to a state?

6. Is a large amount of knowledge absolutely required to solve this problem or is knowledge important only to constrain the search?

7. Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?