The Avoidance of (Relative) Catastrophe, Heuristic Competence, Genuine Dynamic Weighting and Computational Issues in Heuristic Problem Solving

Session 2 Theory of Heuristic Search

THE AVOIDANCE OF (RELATIVE) CATASTROPHE, HEURISTIC COMPETENCE, GENUINE DYNAMIC WEIGHTING AND COMPUTATIONAL ISSUES IN HEURISTIC PROBLEM SOLVING

Assistant Professor Ira Pohl Information Sciences, University of California Santa Cruz, California

that searches or-graphs using a merit order­ ing. It was developed by this author (Pohl 1969, 1970) to generalize the methods of Doran and Michie (1966) and Hart, Nilsson and Raphael (1968). The critical difference from the latter's algorithm A>~ is the use of a weighted merit function f(x) = (1-,.,.r)g(x) + wh (x), 0 ~ w ~ 1 (see Table 1). Suitable gener­ alizations of HPA have been used by Kowalski (1969) and Michie (1972) for resolution theo­ rem proving. In this domain, Kowalski's criticisms (Kowalski 1972) are especially astute. He notes that "diagonal search strategies" (his term for w ""' 0.5) have a critical defect. They investigate all equally meritorious alternative paths. In OTificult problem spaces where any solution path is de­ sired, this procedure is inappropriately breadth first.

Computational Catastrophes

When a computational procedure is forced to terminate having used up its time and space resources without finding a solution--this will be called a~ 1 catastrophe.>'<

When a computat1onaT procedure terminates with an insufficiently good solution--this will be called a ~ ~ catastrophe. This type 2 catastrophe can only occur in problems that have an ordered set of feasible solu­ tions.

Examples: Type 1 catastrophe occurs all the t1me 1n artificial intelligence research. An early example was SAINT's failure on 2 integration problems (Slagle 1961). A typical Type 1 catastrophe is the failure of a resolu­ tion search procedure to find a proof within a preset level bound. ·

Type 2 catastrophe can only occur in pro­ blems that require "best" solutions. The simplest local refinement strategy for the Traveling-Salesman problem is the nearest­ neighbor rule (1-opt in Shen Lin's terminol­ ogy). The rule is to select the nearest node not yet included in the sub-tour. Using this rule on the graph in figure 1 leads to a very bad tour, a type 2 catastrophe.

Other examples of type 2 catastrophe are not generating the only winning or drawing move in a game playing program, or remaining on a "heuristic plateau" (Minsky 1961), which is distinctly sub-optimal, in a problem space.

Over-relaxation, admissibility and dynamic weighting

When using HPA to solve various 15-puzzle (see figure 2) problems, it was found that values of "' > 0. 5 were most efficient. This weighting of the heuristic function no longer guaranteed "admissibility", i.e. a minimum length solution. The overreliance on the heu­ ristic term is called overrelaxation because of the analogous technique in the

>'<Space and time catastrophe will be dis ting­ uished as separate types in a later paper.

Abstract

To solve difficult problems heuristically, requires detailed attention to computational efficiency. This paper describes how a heur­ istic problem solving system, HPA, attempts to find a near optimal solution to the trav­ eling salesman problem. A critical innova­ tion over previous search algorithms is an explicit dynamic weighting of the heuristic information. The heuristic information is weighted inversely proportional to its depth in the search tree--in consequence it pro­ duces a narrower depth first search than tra­ ditional weightings. At the same time, dy­ namic weighting retains the catastrophe pro­ tection of ordinary branch and bound algor­ ithms.

Key Words. Heuristic Search, Branch and Bound, HPA, Traveling Salesman Problem, Bi­ nary Tree Sort, Dynamic Weighting, Precon­ ditioning, Heuristic Combinatorics, Artifi­ cial Intelligence, Pruning.

Artificial intelligence can be defined as the art of computational compromise. Pro­ blem spaces in artificial intelligence are sizeable and are non-analytic in the sense that smooth convergence to a solution is un­ available. Hence computational methods must attempt to use their resources--space and time--cleverly. This paper discusses a heu­ ristic search procedure for the Travel Sales­ man problem--n! in size, emphasizing computa­ tional efficiency and search organization.

The problem (symmetric costs)

There is a complete graph of n nodes. Each edge of the graph has a non-negative length. A tour is a path in the graph visiting every node once and only once and returning to the initial node. The length of a tour is the sum of the lengths of the edges of the tour. A tour is called optimal, if among all possible tours, it is the shortest. Since tours are cyclic, the in­ itial node can be fixed as node 1. The space of all tours are the (n-1)! permuta­ tions of the nodes 2 through n.

It is well known (Lawler and Wood, 1966) that ordinary operations research algorithms require exponential time to solve the pro­ blem. Thus large (n>l5) problems are either solved by branch-and-bound methods or by lo­ cal-refinement methods (Shen Lin 1965). Branch-and-bound methods guarantee an optim­ al solution, if they terminate within their allotted time (of course the method is guar­ anteed to terminate in exponential time). Local-refinement methods generate solutions in polynomial time which are not guaranteed to be optimal.

Heuristic Path Algorithm (HPA)

HPA is a general graph search algorithm computational solution of partial differen­ tial equation problems. The weight w was set to a constant using previous experience to obtain an efficient setting. The 15 puzzle experiments demonstrated the computational utility of overrelaxation. However, these solutions were rarely near the minimum length solution. In the traveling salesman problem this type of search would result in type 2 catastrophe.

To avoid a type 2 catastrophe, HPA would like to retain admissibility or at least be within a known percentage of error (Pohl 1970). This can be accomplished by using a technique to be called "dynamic weighting". Dynamic weighting makes w a function of the state. HPA now uses f(x) g(x) + w(x)h(x) where 1 < w(x) ~ ~.

Let x be a state in the search for a tour. Let the depth (x) = the number of edges in­ cluded in the subtour represented by x and define

The effect of having w decrease with depth is to insure a depth first search, if and only if the added cost decreases within ever tighter bounds. If at some point in the depth first search a type 2 catastrophe were to occur, the search would revert to ordinary branch-and-bound behavior. The dynamic weighting provides incentive to proceed in a depth first manner provided no unforseen in­ crease in cost occurs. The resulting solu­ tion is within (1 + e) of the optimal solu­ tion (see appendix for proof).

Heuristic Estimators for the Traveling Sales­ man Problem

There are several known bounds on the Traveling Salesman Tour . One is the Assign­ ment Problem (Lawler and Wood 1966), and another is the Minimum Spanning One-tree (Held and Karp 1971). A third estimator used in my experiments on symmetric distance pro­ blems (i.e. undirected graphs) is a variant of the Little estimator (Little, et al 1963), to be called the in-out estimator.

The Traveling Salesman Tour is the minimum weight connected graph, whose nodes are all of degree 2. The assignment problem is the minimum weight graph whose nodes are all of degree 2. The minimum spanning tree is the minimum weight connected graph. A 1-tree is a minimum spanning tree over nodes [2, ... ,n} with the addition of the two shortest edges out of node 1. In the case of the assignment problem a solution graph may be a set of cycles. In the case of the 1-tree a solution may contain many nodes of degree not equal to 2. Each relaxes a constraint of the Travel­ ing Salesman Problem, hence each contains many nodes of degree not equal to 2. Each relaxes a constraint of the Traveling Sales­ man Problem, hence each contains the solution of the Traveling Salesman Problem as a feas­ ible solution. (see Figure 3)

The in-out estimator, due to the author, is particularly simple to calculate. It is a lower bound on the Assignment Problem, but where an assignment problem is calculated in O(n 3 ) steps, this bound is c a 1 c u la ble in 0 ( n) steps given that the edges are in sorted order. The in-out estimator is cal­ culated by summing the 2 shortest edges out of each node not already included in the subtour and such that these edges are not connected to interior nodes of the subtour. This sum is added to the shortest edge out of each end node of the subtour, and the total divided by 2. The in-out estimator is easily seen to be a lower bound on the remaining length of a tour from the given subtour.

Example:

let x be the subtour ABF

then A and F are end nodes and B is an internal node with

g(x) = 2 + 3 = 5

in-out (x) = 0.5 (2 + 2 + 2 + 2 + 2 + 3 +

C

D

E

FDCEA is the best remaining order for a true cost of 10. The in-out heuristic like the one-tree bound in computed in linear time when the edge lengths are previously sorted.

Experiments, at this time, have been carried out using a hybrid heuristic function and dynamic weighting:

f(x) = g(x) + w(x) *

if h 1 (x) > h 2 (x) then h 1 (x) else h 2 (x);

where hl is the in-out estimator and h 2 is

the one-tree PStimator. The experiments on a 20 node graph of known difficulty (Croes 1958) showed clearly that dynamic weighting found near optimal solutions relatively cheaply when compared to ordinary branch-and-bound using the same heuristic estimator (see table 2).

Additional Comhutational Techniques for In­ creasing Searc Efficiency

The candidate set is kept as a sorted bi­ nary tree, where merit (left son) < merit (parent) ~ merit (right son). The next node to be expanded is always the left-most node of this sorted candidate set. New nodes are en­ tered into the tree in approximately log 2 (m) time, where m is the size of the candidate set.

The bound on the tour is initially the best nearest-neighbor tour. Such a nearest­ neighbor tour is generated using each node as a starting subtour. During the execution of HPA this may be updated by a tour found in the course of expanding depth = n- 5 search nodes The most important savings are obtained from preconditioning the edge lengths. The edges are sorted by length which requires 2 0 (n log 2 n) steps. Furthermore, the edges are stored in completely sorted order and in

• sorted order for each node.
• 1 rsort. points at a triple (j, k, m) and means 1 the edge (j, k) of length m is the ith smallest edge in the graph
• 2 order (j, i) is an integer k where edge (j, k) is the ith smallest edge originat­ ing at node j.

The one-tree and in-out computations only re­ quire linear time when the edges are already sorted by length. This reduces these compu­

tations from quadratic time; at the expense of a single (n 2 log n) computation and extra storage for the §orted lists. In all cases an overall saving will occur because at least 0 (n 2 ) heuristic functions need to be calcu­

lated.

Summary

An important guiding principle in heuris­ tic programming is the avoidance of catas­ trophe. This principle overshadows its com­ petitor--the pursuit of the optimal solution-­ as a pragmatic guideline in large search spaces. The whole notion of min-max ration­ ality in game theory is an explicit axiomati­ zation of this conservative rule.

A dynamic weighting approach is proving computationally efficient in obtaining near optimal solutions to the Traveling Salesman Problem. It offers a highly depth first search along with guarantees of avoiding type 2 catastrophes.