Heuristics and Problem Solving | Artificial Intelligence

In this article we will discuss about the need and types of heuristics for problem solving.

Travelling Salesman Problem – Need of Heuristics:

Will the control strategy which causes motion and is systematic, lead always to the solution?

This is not so always, for example, consider the following problem:

A salesman has a list of cities, each of which he must visit exactly once. There are direct roads between each pair of cities on the list. Find the route the salesman should follow for the shortest possible round trip that both starts and finishes at anyone of the cities.

This is a classic problem in graph theory, which has no closed, analytic, algorithmic solution. This problem can be solved for very short list of cities. But it breaks down as the number of cities grows. If there are N cities, and the starting point is arbitrary if the distance between each pair of cities is same regardless of the direction of travel there will be N (N-1)!/2 possible paths. Suppose we have a computer which can list all possible solutions of a 20 city problem in one hour.

Then using the above formula would clearly take 20 hours to solve a 21 city problem and 17.5 days to solve a 22 city problem. A 25 city problem would take nearly 6 centuries. Because of this exponential growth in computing time with the size complete enumeration is clearly a non-starter.

This phenomenon is called combinatorial explosion. Even if a computer could process each move in one millisecond it would take infinitely long time to arrive at a solution. This type of search is called BLIND search. There is no solution to such problems, except invoking some special type of control strategies where in the requirements of mobility and systematicity have to be sacrificed. A guaranteed solution is found by making use of HEURISTICS.

In Tic-Tic-Tic the first player has 9 board positions, the second gets 8 board positions. So the first player is confronted with 9! (362,880) complete games. However, the four fold symmetry of tic-tac-toe reduces the first play to three unique positions; corner, side or center; a bilateral symmetry appears after two moves and the average game takes about 6 plays rather that those allowed. These symmetries and realities (Heuristics) reduce the number of actual games sub-statically.

The complete state space is a graph rather than a tree, as some states on the third and deeper levels can be reached by different paths. However, there are no cycles in the state space because the directed arcs of the graph do not allow a move to be undone. It is impossible to go back up the structure once a state has been reached.

Thus, exhaustive searches are impossible, except for very simple games such as tic-tac-toe and even in this case the use of heuristics is advisable for making the program run a reasonable speed. The phenomenon of combinatorial explosion can be tackled by heuristics search.

The heuristics search improves the efficiency of a search process though the completeness is rarely achieved. They are like TOUR GUIDES good to the extent that they point in generally interesting direction, bad to the extent that they miss points of interest to particular individuals.

In the process of heuristic search an excellent path may sometime be overlooked, which was in sight earlier but in general they improve the quality of paths which are explored. Using heuristics we can hope to get good solution to the hard problem such as Travelling Salesman Problem, (TSM) in less than exponential time.

Heuristics play a very important role in many AI programming efforts, and therefore we examine the concept in more detail. As an adjective, heuristic means. “Helping to discover or learn; guiding or furthering investigation”. Various AI researchers have offered the following definitions of heuristics and heuristic programming.

According to Newell, Shaw, and Simon (1958):

“A process that MAY solve a given problem, but offers no guarantees of doing so is called a heuristic for that problem.”

According to Marvin Minsky (1963):

A heuristic is “… any method or trick used to improve the efficiency of a problem-solving program” and that heuristic methods are “related to improving problem-solving performance.”

Feigenbaum and Feldman (1963):

“A state heuristic (heuristic rule, heuristic method) is a rule of thumb, strategy, trick, simplification, or any other kind of device which drastically limits search for solutions in large problem spaces. Heuristics do not guarantee optimal solutions; in fact, they do not guarantee any solution at all. At the most what can be said for a useful heuristic is that it offers solutions which are good enough most of the time.”

According to Judea Pearl (1983):

“It is the nature of good heuristics both that they provide a simple means of indicating which among several courses of action is to be preferred, and that they are not necessarily guaranteed to identify the most effective course of action, but do so sufficiently often. It is often said that heuristic methods are unpredictable; they work wonders most of the time but may fail miserably some of the time.”

It is thus clear, that heuristic programming differs significantly from algorithmic programming even though heuristic programs themselves must be expressed in algorithmic form. Straight algorithms fail us in the face of the tremendous search spaces and variability of conditions encountered in typical AI applications.

Type of Heuristics:

Domain Specific:

Here more knowledge of the problem is incorporated.

This can be done in two ways-assuming domain specific knowledge can be incorporated into a rule-based search procedure:

1. In the rules them selves. For example, the rules for a chess-playing system might describe not simply the set of legal moves but rather a set of sensible moves, as determined by the rule writer.

2. As a heuristic function which evaluates individual problem states and determines how desirable they are. Heuristic functions are used in Intelligent search techniques such as Hill Climbing.

General Purpose:

Heuristics are useful for a variety of problems. One example of general purpose heuristics useful for Travelling Salesman problem, involving combinatorial explosion is the Nearest neighbour heuristics procedure, which works by selecting the locally superior alternative at each step.

Applying it to the travelling salesman problem we get the following procedure:

1. Arbitrarily select a starting city.

2. To select the next city, look at all cities not visited and select the one closest to the current city. Go to it.

3. Repeat step 2 until all cities have been visited.

The nearest neighbour path through the graph is highly efficient. However, the nearest neighbour is prone to error, as graphs exist for which it does not find the shortest path. But it is a possible compromise when the time required makes exhaustive search impractical.

Another strategy for controlling strategy is Branch and Bound. It generates one path at a time, keeping track of the best path found so far. This value is used as a bound on future candidates. As paths are constructed one city at a time, the algorithm examines each partially completed path.

If the algorithm determines that the best possible extension to a path the branch will have greater cost than the bound, it eliminates that partial path and all of its possible extensions. This reduces search considerably but still leaves an exponential number of paths.

With the heuristic the TSM problem can be executed in time proportional to N², instead of N! a. For example, if N = 4, then in the case of combinational explosion paths to be examined are 4! = 24 whereas by Nearest Neighbour heuristic the help the number of paths which need to be examined are 4² = 16, significant improvement indeed. For many AI problems it is not possible to produce such improvement. Yet heuristics help to a great extent.

Lenant (1983) has shown that heuristics can discover new heuristics since heuristics are a domain of knowledge which too can be discovered via heuristic guidance. Sometimes, a heuristic can be both be ameta heuristic and domain heuristic, which are applied to learn domain knowledge.

Heuristics are often regarded as though they were incomplete or uncertain. This is not always true. Some heuristics have a sound mathematical basis. Some have precise knowledge with high utility. Some are derived from statistical observations. But the standard use of heuristics is to pretend that they are true and they guide the system behaviour.

AI Problem solving techniques using heuristics work satisfactory as quite often we need optimum solution. Most of the problems are based on ‘satisfying extent’ rather than on optimal level i.e., solution is sought which is appropriate in a certain set of circumstances and constraints.

We use heuristics because people, most of the time don’t vie for the optimum solution, but they want to be satisfied with the ‘solution’. Approximations produced by heuristics may not be very good in the worst case, but worst cases are rare in the real world. A heuristic function is the one which maps from problem state descriptions to measures of desirability, usually represented as numbers.

Which aspects of the problem state are considered, how these aspects are evaluated and how the weights given to individual aspects are chosen depends upon the way that the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.

It can be concluded that well designed heuristic function can play an important part in efficiently guiding a search/process towards a solution. Sometimes very simple heuristic function (as in the case of 8 – or 15 – puzzle) can provide a fairly good estimate of whether a path is any good or not.

In other situations more complex heuristic functions (increasing employment trend, less number of people below poverty line etc., for probable chance of winning of the present government in the forth coming elections) may be difficult.