 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ODL 129 TEAM B Coursework 1 |
|
|
|
Question 1. |
|
|
|
Investigate the history of search teqniques and search algorithms in the development of AI as a research area in Computer science. Illistrate one or more of those algorithms in relation to the typical kinds of problem solving system to which they have been applied. You might start with the early work in AI by Newell and Simon (1972), N,J Nilsson (1980), Patrick Winston (1984) and R. Korf (1985) |
|
|
|
Answer |
|
|
|
Machines are able to carry out defined tasks very quickly and accurately, but they are unable to think or reason about those tasks. AI attempts to emulate human intelligence in a machine i.e the ability to make decisions based upon feedback mechanisms from our surroundings. AI aims to design computer systems that can rationalise & think like a human being. A machine capable of understanding, learning, decision making & problem solving. It studies mental abilities through the use of computational models, and the development of search techniques was considered to be one of the early successes of AI research. |
|
|
|
The modern field of AI began in the 1950's when Alan Turing proposed that machines could be programmed to exhibit intelligent behaviour, and he developed the Turing Test. A few years later, John McCarthy (who coined the term AI), suggested that a study should be carried out to investigate the idea that every aspect of learning or any other feature of intelligence could be defined in such a way that it was possible to develop a machine that could simulate it. In the late 50's Newell & Simon developed The Logic Theorist, (a program that represented problems as a tree, attempting to solve them by selecting branches that were most likely to reach the desired conclusion in the most efficient way (quicker))! |
|
|
|
Search Trees are very useful in problem-solving. The structure of a search tree is basically as it's name implies, it has nodes and branches (pathways between nodes). The search starts from a specific start node with branches leading from it to nodes on the next level. The 'branching' continues until the goal state is reached. |
|
|
|
AI search techniques are used to find a sequence of steps to get from an initial state to a goal state(s) by either searching backwards from the goal, or forwards from the initial state. |
|
|
|
Forward and backward chaining are examples of search techniques, and which method is used depends upon the problem. In Forward Chaining you start at the initial state and move to the goal state, this is known as a data driven search, and is useful when there are many potential goals, if it's difficult to form a goal, or if there are not many paths to follow. With Backward Chaining you start at the goal, the data of the problem is not given. There are many paths to follow, and each level of the search has a large number of nodes. An example of Backward Chaining was a program called MYCIN which was developed by Shortliffe in 1976. It was used to diagnose infectious diseases, so would start with the disease itself, i.e. the symptoms and characteristics displayed, and then search for a match of those symptoms from its list, and when it found a correct match it diagnosed the disease. |
|
|
|
In 1963 Newell and Simon developed the GPS (General Problem Solver), and this was the first AI program to use an idea called Means-End Analysis. It was used for information processing, and tried to explain all behaviour as functions of memory, control processes and rules. The theories were tested in computer simulations, and the results compared with human behaviour for the same task. It used forward and backward chaining within the context of the same problem. It solved parts of the problem seperately and then brought all the parts back together into one solution. It first of all identified the difference between initial and goal states, and then tried to find an operator such as PUSH(obj,loc), PICK-UP(obj), MOVE(obj,loc), and DROP(obj), in order to move from the initial to the goal state. If unable to solve the problem it would break it down into sub-problems, and then apply the same technique. The GPS uses a set of rules and a difference table. It was supposed to provide a set of processes that could be used to solve various types of problems, but in reality it could only be used with well defined problems such as proving logic theorems, word puzzles and chess. |
|
|
|
Depth Fisrt Search uses search trees, and as a tree search does not require as much memory as some other techniques, as it only records the nodes on the current path. This is similar to the way humans conduct a search, i.e. if we are given a choice, then we would be more likely to choose the option that looked most promising and follow it, rather than persuing several options at the same time. If there are a lot of solutions to the problem, all occurring at a comparable depth, then you may reach a solution after exploring just a small part of the tree, although it may not be the best solution. A disadvantage of this technique is that you may get stuck exploring long (potentially infinite) paths, when there could be a solution with a path of only one or two steps. It is not very useful where there is only one solution, or if you want to find the shortest route. Click here to see an example of a Depth-first Search. |
|
|
|
Next we will take a look at Breadth First Search, this uses more memory than the previous example, but it will always find the shortest path, or the one that involves the least number of steps. This technique is useful when exploring very large search spaces, where there is an expected solution in a relitavely small number of steps. It is also useful if you want to explore all solutions, and you set a depth limit on the search. Click here to see an example of a Breadth-first Search. |
|
|
|
There are two main types of search methods utilized to solve problems, algorithmic & heuristic. |
|
|
|
Search Algorithms are a technique used when building certain types of AI systems. An algorithm is a group of clearly defined instructions enabling a solution to be reached to a given problem in a finite number of steps. They are perfomance oriented, based on probability and statistics.They are useful in planning systems which involve automatic generation and evaluation of plans to achieve specific goals, for example: what route will take me from node 0 to node 9? Real AI planning systems actually involve more complex tasks such as planning routes for robots to take through real environments. E.g. Through an uncontrolled environment such as space exploration or searching the surface of a planet/moon. |
|
|
|
Heuristic Search is a good technique to use if the whole search space is very large. Rather than try all of the possible paths you would focus on the ones that seem to be nearer to the goal state. This type of search contains an evaluation function that gives a score or value to a node in the search tree, dependant upon how close it seems to be to the goal state. Hueristic search strategies therefore follow the most appropriate solution of several posed at each successive step within a program. E.g. Chess program (will alter its strategy depending on the move of the opposing player). |
|
|
|
There are several heuristic search algorithms, to follow are a few examples:- |
|
|
|
A good example of a Heuristic Search is the 8 puzzle. This is a board type game for just one player, and consists of 8 square tiles on a 3 x 3 board, with numbers one through to eight marked on them, and one empty space without a tile. Moves can be made by sliding a tile which is horizontally or vertically adjacent to the blank space into that position. This exchanges the positions of the tile and the blank space, there are several versions of this puzzle, but in our example the object of the puzzle is to move the tiles around until they are in clockwise order from 1 to eight, with the blank space in the centre of the board. The things that need to be considered in the search to solve this puzzle are: the start state, the number of possible states of the board, the average number of possible moves from a given position of the board, and the minimum number and maximum number of possible moves between the start and goal states. Click here to see an example of the 8 Puzzle |
|
|
|
Generate and Test - this algorithm generates a possible solution, and then tests it to find out if it is a real solution by comparing it with a set of acceptable goal states. If it finds a solution it then quits, but if it doesn't it repeats the loop, and so on. |
|
|
|
Simple Hill Climbing starts with the initial state, which becomes current state, it then moves to the next state and evaluates it. If the new state is a goal state, it returns the result and quits. If it is not a goal state, but it is better than the current state i.e. nearer to the goal state, it will then make this its current state. If it is no better than the current state, it continues in the loop. |
|
|
|
Best First Search is similar to the Hill Climbing, except that it combines Depth First Search and Breadth First Search. It follows a single path at a time, but switches paths if it finds a more promising one. A disadvantage of this technique is that it doesn't take into account the cost of a path so far when choosing the next node to search from. It may reach a solution, but it may not be a very good one. |
|
|
|
A* Search Technique attempts to find a solution which minimises the total lenght or cost of a solution path. It also combines breadth first, where the shortes path is found first, with depth first, where the node which seems closest to a solution is explored next. It also gives a score or value to a node, but this is a combination of the cost so far and the estimated cost to a solution. This technique will always find the shortest path first. |
|
|
|
Although the history of AI as a research area in Computer Science is a relatively young (approximately 50 years), major steps forward have been taken in terms of achieving the goal of developing a machine that can adapt and learn (the primary aim of many AI programs). Several search techniques and algorithms have been developed such as A* Search Technique, Best First Search and Simple Hill Climbing to name a few. Although still a long way off from developing a machine that can think, learn & understand like a human, if AI research continues to progress at the same rate as it has to date, the goal of creating a machine with artificial intelligence that can emulate human intelligence is possible within the next 50 years. |
|
|
|
 |
|
|
|
 |
|
|
|
References |
|
|
 |
|
|
|
|
|
|
|
|
|
|
[1] Brookshear, J. G., "Computer Science An Overview", 2000.
[2] "GPS (A.Newell & H.Simon)."http://tip.psychology.org/simon.html
[3] "Search Algorithms & Research Papers on Internet Searching." http://vcolaso.port5.com/ai/vicdoc/
[4] "CS 381K: Heuristic Search: 8 Puzzle." http://www.cs.utexas.edu/users/novak/asg-8p.html
[5] "A Brief History of Artificial Intelligence." www.javacoffeebreak.com/tutorials/aisearch/chapter1.html
[6] "Simple Tree Searches" http://www.generation5.org/simple_search.shtml
[7] "The History of Artificial Intelligence" http://library.thinkquest.org/2705/history.htm |
|
|
 |
|
|
|
|
|
To top |
|
|
|
|
|
|
|
|
|
|
|
Question 2 |
|
|
|
|
|
|
|
Question 3 |
|
|
|
|
|
|
|
Question 4 |
|
|
|
|
|
|
|
|
|
Question 5 |
|
|
|
|