Transcription
100IEEE TRANSACTIONS OF SYSTEMS SCIENCE AND CYBERNETICS, VOL.ssc-4, NO. 2,JULY1968[N1 J. E. Falk, "Lagrange multipliers and nonlinear programming,"J. Math. Anal. Appl., vol. 19, July 1967.[6] 0. L. Mangasarian and J. Ponstein, "Minimax and duality innonlinear programming," J. Math. Anal. Appl., vol. 11, pp. 504518, 1965.[7] J. Stoer, "Duality in nonlinear programming and the minimaxtheorem," Numerische Mat hematik, vol. 5, pp. 371-379, 1963.[8] R. T. Rockafellar, "Duality and stability in extremum problems involving convex functions," Pacific J. Math., vol. 21, pp.[17] R. Fletcher and C. M. Reeves, "Function minimization byconjugate gradients," Computer J., vol. 7, July 1964.[I8] D. Goldfarb, "A conjugate gradient method for nonlinearprogramming," Ph.D. dissertation, Dept. of Chem. Engrg., Princeton University, Princeton, N. J., 1966.[19] L. S. Lasdon, "A multi-level technique for optimization,"Ph.D. dissertation, Systems Research Center, Case Institute ofTechnology, Cleveland, Ohio, Rept. SRC 50-C-64-19, 1964.120] L. S. Lasdon and J. D. Schoeffler, "A multi-level technique for167-187, 1967.optimization," Preprints, Joint Automatic Control Conf., Troy,[9] P. Wolfe, "A duality theorem for nonlinear programming," N. Y., June 22-25, 1965, pp. 85-92.[21] '-,"Decentralized plant control," ISA Trans., vol. 5,Q. A ppl. Math., vol. 19, pp. 239-244, 1961.[10] R. T. Rockafellar, "Nonlinear programming," presented at the pp. 175-183, April 1966.[22] C. B. Brosilow and L. S. Lasdon, "A two level optimizationAmerican Mathematical Society Summer Seminar on the Mathematics of the Decision Sciences, Stanford University, Stanford, technique for recycle processes," 1965 Proc. AICHE-Symp. onApplication of Mathematical Models in Chemical Engineering ReCalif., July August 1967.[1ll D. G. Luenberger, "Convex programming and duLality in search, Design, and Production (London, England).[21] L. S. Lasdon, "Duality and decomposition in mathematicalnormal space," Proc. IEEE Systems Science and Cybernetics Conf.programming," Systems Research Center, Case Institute of Tech(Boston, Mass., October 11-13, 1967).[12] J. M. Danskin, "The theory of max-min with applications," nology, Cleveland, Ohio, Rept. SRC 119-C-67-52, 1967.[24] A. V. Fiacco and G. P. McCormick, Sequential UnconstrainedJ. SIAM, vol. 14, pp. 641-665, July 1966.113] W. Fenchel, "Convex cones, sets, and functions," mimeo- Minimization Techniques for Nonlinear Programming. New York:graphed notes, Princeton University, Princeton, N. J., September Wiley, 1968.12] R. Fox and L. Schmit, "Advances in the integrated approach1963.[14] R. Fletcher and M. J. D. Powell, "A rapidly convergent to structural synthesis," J. Spacecraft and Rockets, vol. 3, p. 858,descent method for minimization," Computer J., vol. 6, p. 163, July June 1966.[261 B. P. Dzielinski and R. E. Gomory, "Optimal programming of1963.[115 L. S. Lasdon and A. D. Waren, "Mathematical programming lot sizes, inventory, and labor allocations," Management Sci., vol.11, pp. 874-890, July 1965.for optimal design," Electro-Technol., pp. 53-71, November 1967.[271 J. E. Falk, "A relaxed interior approach to nonlinear pro[16] J. B. Rosen, "The gradient projection method for nonlinearprogramming, pt. I, linear constraints," J. SIAM, vol. 8, pp. 181- gramming," Research Analysis Corp., McLean, Va. RAC-TP-279,1967.217, 1960.AFormal Basis for the Heuristic DeterminationofMinimum Cost PathsPETER E. HART, MEMBER, IEEE, NILS J. NILSSON, MEMBER, IEEE,Abstract-Although the problem of determining the minimumcost path through a graph arises naturally in a number of interestingapplications, there has been no underlying theory to guide thedevelopment of efficient search procedures. Moreover, there is noadequate conceptual framework within which the various ad hocsearch strategies proposed to date can be compared. This paperdescribes how heuristic information from the problem domain canbe incorporated into a formal mathematical theory of graph searchingand demonstrates an optimality property of a class of search strategies.I. INTRODUCTIONA. The Problem of Finding Paths Through GraphsMANY PROBLEIVIS of engineering and scientificimportance can be related to the general problem offinding a path through a graph. Examples of such problems include routing of telephone traffic, navigationthrough a maze, layout of printed circuit boards, andManuscript received November 24, 1967.The authors are with the Artificial Intelligence Group of theApplied Physics Laboratory, Stanford Research Institute, MenloPark, Calif.AND BERTRAMRAPHAELmechanical theorem-proving and problem-solving. Theseproblems have usually been approached in one of twoways, which we shall call the mathematical approach andthe heuristic approach.1) The Inathematical approach typically deals with theproperties of abstract graphs and with algorithms thatprescribe an orderly examination of nodes of a graph toestablish a minimum cost path. For example, Pollock andWiebensonf11 review several algorithms which are guaranteed to find such a path for any graph. Busacker andSaaty[2' also discuss several algorithms, one of which usesthe concept of dynamic programming. [3] The mathematicalapproach is generally more concerned with the ultimateachievement of solutions than it is with the computationalfeasibility of the algorithms developed.2) The heuristic approach typically uses special knowledge about the domain of the problem being represented bya graph to improve the computational efficiency of solutions to particular graph-searching problems. For example,Gelernter's 41 program used Euclidean diagrams to directthe search for geometric proofs. Samuel[1 and others haveused ad hoc characteristics of particular games to reduce
101HART et al.: DETERMINATION OF MINIMUM COST PATHSthe "look-ahead" effort in searching game trees. Proceduresdeveloped via the heuristic approach generally have notbeen able to guarantee that minimum cost solution pathswill always be found.This paper draws together the above two approaches bydescribing how information from a problem domain canbe incorporated in a formal mathematical approach to agraph analysis problem. It also presents a general algorithm which prescribes how to use such information to finda minimum cost path through a graph. Finally, it proves,under mild assumptions, that this algorithm is optimal inthe sense that it examines the smallest number of nodesnecessary to guarantee a minimum cost solution.The following is a typical illustration of the sort ofproblem to which our results are applicable. Imagine a setof cities with roads connecting certain pairs of them.Suppose we desire a technique for discovering a sequenceof cities on the shortest route from a specified start to aspecified goal city. Our algorithm prescribes how to usespecial knowledge-e.g., the knowledge that the shortestroad route between any pair of cities cannot be less thanthe airline distance between them-in order to reduce thetotal number of cities that need to be considered.First, we must make some preliminary statements anddefinitions about graphs and search algorithms.path has a cost which is obtained by adding the individualcosts of each arc, ci,i l, in the path. An optimal path fromni to nj is a path having the smallest cost over the set of allpaths from ni to nj. We shall represent this cost by h(ni, n3).This paper will be concerned with the subgraph G, fromsome single specified start node s. We define a nonemptyset T of nodes in GU as the goal nodes.1 For aniy node n inG., an element t e T is a preferred goal node of n if and onlyif the cost of an optimal path from n to t does not exceedthe cost of any other path from n to any member of T.For simplicity, we shall represent the unique cost of anoptimal path from n to a preferred goal node of n by thesymbol h(n); i.e., h(n) min h(n,t).teTC. Algorithms for Finding Minimun Cost PathsWe are interested in algorithms that search G, to findan optimal path from s to a preferred goal node of s. Whatwe mean by searching a graph and finding an optimal pathis made clear by describing in general how such algorithmsproceed. Starting with the node s, they generate some partof the subgraph G, by repetitive application of the successor operator r. During the course of the algorithm, ifP is applied to a node, we say that the algorithm hasexpanded that node.We can keep track of the minimum cost path from s toeach node encountered as follows. Each time a node isexpanded, we store with each successor node n both thecost of getting to n by the lowest cost path found thus far,and a pointer to the predecessor of n along that path.Eventually the algorithm terminates at some goal node t,and no more nodes are expanded. We can then reConstructa minimum cost path from s to t known at the time oftermination simply by chaining back from t to s throughthe pointers.We call an algorithm admissible if it is guaranteed tofind an optimal path from s to a preferred goal node of sfor any 8 graph. Various admissible algorithms may differboth in the order in which they expand the nodes of G, andin the number of nodes expanded. In the next section, weshall propose a way of ordering node expansion and showthat the resulting algorithm is admissible. Then, in a following section, we shall show, under a mild assumption,that this algorithm uses information from the problemrepresented by the graph in an optimal way. That is, itexpands the smallest number of nodes necessary to guarantee finding an optimal path.B. Some Definitions About Graphsof elements calledA graph G is defined to be a setnodes and a set {eij} of directed line segments called arcs.then we say that thereIf epq is an element of the set {is an arc from node np to node n, and that nq is a successorof n,. We shall be concerned here with graphs whose arcshave costs associated with them. We shall represent thecost of arc eij by cij. (An arc from ni to nj does not implythe existence of an arc from nj to ni. If both arcs exist, ingeneral cij cji.) We shall consider only those graphs Gfor which there exists 8 0 such that the cost of every arcof G is greater than or equal to 6. Such graphs shall becalled 8 graphs.In many problems of interest the graph is not specifiedexplicitly as a set of nodes and arcs, but rather is specifiedimplicitly by means of a set of source nodes Sc n} and awhose value for eachsuccessor operator P, defined onni is a set of pairs { (nj, cij) }. In other words, applying r tonode ni yields all the successors nj of ni and the costs cijassociated with the arcs from ni to the various nj. Application of r to the source nodes, to their successors, and soforth as long as new nodes can be generated results in anII. AN ADMISSIBLE SEARCHING ALGORITHMexplicit specification of the graph thus defined. We shall A. Description of the Algorithmassume throughout this paper that a graph G is alwaysIn order to expand the fewest possible nodes in searchinggiven in implicit form.The subgraph G,, from any node n in { ni} is the graph for an optimal path, a search algorithm must constantlydefined implicitly by the single source node n and some r make as informed a decision as possible about which nodedefined on {ni}. We shall say that each node in G,, is to expand next. If it expands nodes which obviously cannotbe on an optimal path, it is wasting effort. On the otheraccessible from n.A path from n, to nk is an ordered set of nodes (n1, n2, hand, if it continues to ignore nodes that might be oIn an. , nk) with each ni a successor of ni. There exists a pathI We exclude the trivial case of s e T.from ni to nj if and only if nj is accessible from ni. EveryI nileijj,nil},
102IEEE TRANSACTIONS ON SYSTEMS SCIENCE AND CYBERNETICS, JULY1968optimal path, it will sometimes fail to find such a path andthus not be admissible. An efficient algorithm obviouslyneeds some way to evaluate available nodes to determinewhich one should be expanded next. Suppose some evaluation function f(n) could be calculated for any node n.We shall suggest a specific function below, but first we shalldescribe how a search algorithm would use such a function.Let our evaluation function f(n) be defined in such aFig. 1.way that the available node having the smallest value offis the node that should be expanded next. Then we cansubgraph shown in Fig. 1. It consists of a start node s anddefine a search algorithm as follows.three other nodes, n3, n2, and n3. The arcs are shown withSearch Algorithmn A*:arrowheads and costs. Let us trace how algorithm A* proin generating this subgraph. Starting with s, weceeded1) Mark s "open" and calculatef(s).obtainsuccessorsni and n2. The estimates 0(n1) and &(n2)2) Select the open node n whose value of f is smallest.thenSuppose A * expands ni nextareandrespectively.37,Resolve ties arbitrarily, but always in favor of any nodestage g(n3) 3 2 5,Atthiswith successors n2 and n3.n E T.3) If n e T, mark n "closed" and terminate the algorithm. and g(n2) is lowered (because a less costly path to it has4) Otherwise, mark n closed and apply the successor been found) to 3 3 6. The value of 0(no) remainsoperator P to n. Calculate f for each successor of n and equal to 3.Next we must have an estimate h(n) of h(n). Here wemark as open each successor not already marked closed.Remark as open any closed node n, which is a successor of rely on information from the problem domain. Manyn and for which f(ni) is smaller now than it was when n, problems that can be represented as a problem of finding aminimum cost path through a graph contain some "physiwas marked closed. Go to Step 2.cal" information that can be used to form the estimate A.We shall next show that for a suitable choice of the In our example of cities connected by roads, h(n) might beevaluation function f the algorithm A* is guaranteed to the airline distance between city n and the goal city. Thisfind an optimal path to a preferred goal node of s and thus distance is the shortest possible length of any road conis admissible.necting city n with the goal city; thus it is a lower bound onh(n). We shall have more to say later about using informaB. The Evaluation Functiontion from the problem domain to form an estimate f, butFor any subgraph GU and any goal set T, let f(n) be the first we can prove that if h is any lower bound of h, thenactual cost of an optimal path constrained to go through n, the algorithm A* is admissible.from s to a preferred goal node of n.Note that f(s) h(s) is the cost of an unconstrained C. The Admissibility of A *optimal path from s to a preferred goal node of s. In fact,We shall take as our evaluation function to be used in A*f(n) -f(s) for every node n on an optimal path, and(2)f(n) A(n) Ai(n)f(n) f(s) for every node n not on an optimal path. Thus,although f(n) is not known a priori (in fact, determination where g(n) is the cost of the path from s to n with minimumof the true value of f(n) may be the main problem of inter- cost so far found by A *, and J(n) is any estimate of theest), it seems reasonable to use an estimate of f(n) as the cost of an optimal path from n to a preferred goal node ofevaluation function f(n). In the remainder of this paper, n. We first prove a lemma.we shall exhibit some properties of the search algorithm A *when the cost f(n) of an optimal path through node n is Lemma 1estimated by an appropriate evaluation function f(n).For any nonclosed node n and for any optimal path PWe can write f(n) as the sum of two parts:from s to n, there exists an open node n' on P with g(n')(1) g(n').f(n) g(n) h(n)Proof: Let P (s no, n1, n2,nk n). If s is openwhere g(n) is the actual cost of an optimal path from s to n, (that is, A* has not completed even one iteration), letand h(n) is the actual cost of an optimal path from n to a n -s, and the lemma is trivially true since 0(s) g(s)0. Suppose s is closed. Let A be the set of all closedpreferred goal node of n.nodes ni in P for which g(ni) g(ni). A is not empty,themweofcouldaddifweestimatesandhadh,gNow,to form an estimate of f. Let g(n) be an estimate of g(n). since by assumption s e A. Let n* be the element of A withAn obvious choice for g(n) is the cost of the path from s to highest index. Clearly, n* 5 n, as n is nonclosed. Let n'n having the smallest cost so far found by the algorithm. be the successor of n* on P. (Possibly n' n.) NowNotice that this implies 0(n) g(n).0(n') . g(n*) cn*,w, by definition of 0; -(n*) - g(n*)A simple example will illustrate that this estimate is because n is in A, and g(n') g(n*) Cn*,n, because Peasy to calculate as the algorithm proceeds. Consider the is an optimal path. Therefore, g(n') g(n'). But in
103HART et al.: DETERMINATION OF MINIMUM COST PATHSgeneral, g(n') g(n'), since the lowest cost g(n') from s nodes in x(M) must be forever closed. Since no nodes outto n' discovered at any time is certainly not lower than side x(M) can be expanded, A* must terminate.the optimal cost g(n'). Thus O(n') g(n'), and moreover,Case 3n' must be open by the definition of A.Termination is at a goal node without achieving miniCorollarymum cost. Suppose A* terminates at some goal node tSuppose h(n) h(n) for all n, and suppose A* has not with f(t) g(t) f(s). But by the corollary to Lemma 1,terminated. Then, for any optimal path P from s to any there existed just before termination an open node n' onpreferred goal node of s, there exists an open node n' on P an optimal path with f(n') f(s) f(t). Thus at thiswith f(n') f(s).stage, n' would have been selected for expansion ratherProof: By the lemma, there exists an open node n' on P than t, contradicting the assumption that A* terminated.with g(n') g(n'), so by definition of fThe proof of Theorem 1 is now complete. In the nextsection, we shall show that for a certain choice of thef(n') - (n') hf(n')function h(n), A* is not only admissible but optimal, in- g(n') hJ(n')the sense that no other admissible algorithm expandsfewer nodes. g(n') h(n') f (n').III. ON THE OPTIMALITY OF A*But P is an optimal path, so f(n') f(s) for all n'e P,which completes the proof. We can now prove our first A. Limitation of Subgraphs by Informationfrom the Problemtheorem.In the preceding section, we proved that if h(n) is anylower bound on h(n), then A* is admissible. One suchTheorem 1lower bound is h(n) 0 for all n. Such an estimate amountsIf ii(n) h(n) for all n, then A* is admissible.to assuming that any open node n might be arbitrarilyProof: We prove this theorem by assuming the contrary, close to a preferred goal node of n. Then the set { Gn isnamely that A* does not terminate by finding an optimal unconstrained; anything is possible at node n, and,inpath to a preferred goal node of s. There are three cases to particular, if g is a minimum at node n, then niode n mustconsider: either the algorithm terminates at a nongoal node, be expanded by every admissible algorithm.fails to terminate at all, or terminates at a goal node withOften, however, we have information from the problemout achieving minimum cost.that constrains the set { Gn} of possible subgraphs at eachnode. In our example with cities connected by roads, noCase 1subgraph G01 is possible for which h(n) is less than theTermination is at a nongoal node. This case contradicts airline distance between city n and a preferred goal city ofthe termination condition (Step 3) of the algorithm, so it n. In general, if the set of possible subgraphs is conmay be eliminated immediately.strained, one can find a higher lower bound of h(n) thanone can for the unconstrained situation. If this higher lowerCase 2bound is used for h(n), then A* is still admissible, but, asThere is no termination. Let t be a preferred goal node of will become obvious later, A* will generally expand fewers, accessible from the start in a finite number of steps, nodes. We shall assume in this section that at each node n,with associated minimum cost f(s).
is anarcfromnodenpto noden,andthatnqis a successor of n,. Weshall be concerned here with graphs whose arcs have costs associated with them. Weshall represent the cost of arc eij bycij. (Anarc fromni to nj does not imply the existence of anarc fromnj to ni. If both arcs exist, in g
