© University of Toronto Press Incorporated 1991

Zycor Inc, Austin, Texas / United States

ABSTRACT Computer programs that place feature labels on maps are often cited as the one successful application of expert systems to automatic map compilation. This paper argues that that the map label placement programs which are claimed to be expert systems stretch the defining boundaries of expert systems and that the most significant use of expert systems technology in existing label placement programs is an inappropriate use of that technology. The results which have been achieved using expert systems technology in this one cartographic application are not sufficient justification for assuming that similar technology will solve other map design problems.

INTRODUCTION

Map label placement is often cited as the one map design problem for which cartographic expert systems exist (Robinson and Jackson 1985; Robinson et al. 1986; Fisher and Mackaness, 1987; Mark and Buttenfield 1988; Weibel and Buttenfield 1988; Kasturi, et al. 1989). In fact, the map label placement programs which are claimed to be expert systems stretch the defining boundaries of expert systems and represent an inappropriate application of that technology.

According to one authority, an expert system is "a knowledge-intensive program that solves problems normally requiring human expertise." And according to the same authority, expert systems "make major decisions by elucidating many of the relevant criteria and by making many of the educated guesses that experts would if they were forced to verbalize the thought process" (Hayes-Roth 1984). Expert systems are characterized by the use of heuristics and symbolic reasoning - often represented by IF-THEN rules; formal problem solving procedures such as goal directed backward chaining; and the rigorous separation of problem specific data, expert knowledge, and program control procedures. Textbooks and articles on expert systems emphasize the critical role of human experts as the source of domain specific knowledge (Bell 1985; Bobrow et al. 1986; Keller 1987; Slagle and Wick 1988).

Most map label placement programs incorporate one or more of the characteristics of expert systems, and many of these programs are identified by their authors as expert systems (Ahn 1984; Ahn and Freeman 1984; Basoglu 1984; Freeman and Ahn 1984; Phefferkorn, et al. 1985; Mower 1986; Freeman and Ahn 1987; Doerschler 1988; Cook 1988; Doerschler and Freeman 1989; Drinnan et al. 1989; Johnson and Basoglu 1989; Jones 1989; Jones and Cook 1989; Mower 1989; Cook and Jones 1990). Some of the maps created by these programs are impressive; many of the label positioning and data handling techniques developed for use in them are innovative; and the programs themselves represent large investments of time and effort. However, good results and the use of some expert system technology are not enough to make a particular computer program a good example of an expert system. At a minimum, a cartographic expert system should be based on detailed cartographic knowledge obtained from experts in map compilation, and it should solve a problem that cannot be solved by the use of algorithms. None of the existing map label placement programs satisfy both of these criteria.

The one critical part of the label placement problem for which the majority of label placement programs rely most strongly on expert system technology is in the use of heuristic search techniques to resolve overplot conflicts between labels and between labels and map symbols. But label conflict resolution is an optimization problem (Mommonier 1982, p 162) for which well-defined mathematical algorithms already exist. Mathematical algorithms can be expected to provide better solutions to the conflict resolution problem than are provided by expert systems, and they are likely to provide less expensive solutions as well.

EXISTING MAP LABEL PLACEMENT PROGRAMS

Algorithms play an important part in all label placement programs. Procedures to position labels along linear features or inside area features are naturally implemented as algorithms, as are procedures for detecting conflicts between labels and between labels and map features. Some of those algorithms are quite sophisticated. For example, the procedures implemented in several programs to align labels along the skeletons of area features are innovative applications of pattern recognition algorithms to automated cartography.

A feature in many label placement programs which is typical of expert systems is the use of formatted files on disk to store label hierarchies and the rules which determine the preferred location, orientation, font, and format of individual labels. Maintaining a separation between rules and the rest of a program is an important part of an expert system and the use of such easily edited disk files certainly increases the flexibility of label placement programs. But maintaining program rules on disk files does not make a map label placement program an expert system; by itself, it is just good automated cartography. In fact, writing any software so that its performance can be altered at low cost is simply good computer programming.

Now consider the resolution of overplots conflicts between map labels and between labels and map symbols. This is a particularly difficult part of the whole label placement problem, and it is where most label placement programs are applying expert system technology. Heuristic search techniques incorporating backtracking and graph-search procedures are used to generate different combinations of label placements, which are then evaluated to identify cartographically acceptable solutions to label overplot problems (Jones 1990). This reliance on heuristics for label overplot resolution appears to be the principal reason existing label placement programs are often identified as expert systems.

While the particular heuristics used to resolve label conflicts vary from program to program, they all depend upon three important assumptions. The first assumption is that each individual label can be placed in one of a relatively small number of positions near or on the feature it annotates. (The search for a new label position may be a continuous process, but only a few positions for each label are actually evaluated by any label placement algorithm.) The second assumption is that the relative quality of individual label positions can be measured. The third assumption is that each label should be placed relative to its feature in the best possible position that avoids overplotting of other labels or map symbols. But any problem involving the placement of discrete objects in a range of fixed positions, subject to a finite number of constraints, is a combinatorial optimization problem (Hoffman and Padberg 1985). And good solutions to this particular combinatorial optimization problem can be found by formal mathematical techniques.

COMBINATORIAL OPTIMIZATION AND THE MAP LABEL PLACEMENT PROBLEM

To use the terminology followed by mathematicians and computer scientists who study combinatorial optimization, the conflict resolution part of map label placement can be formulated as a multiple choice integer-programming problem (Healy 1964). Many combinatorial optimization problems fit into this category, including problems from job scheduling, facility location and menu planning. The common characteristic these problems share is that each person, plant, or menu item under consideration must be assigned to a particular job, location or food type so as to minimize an objective function while also satisfying certain additional constraints. In job scheduling the usual objective is to minimize the total time required to finish a set of tasks, and the additional constraints might include a requirement that not more than one person work at a particular task at one time. In map label placement the usual objective is to place as many labels as possible near their optimal positions, and the additional constraints are that two labels or a label and a map symbol may not overplot.

Multiple choice integer programming problems have been studied extensively (Sweeney and Murphy 1981; Bean 1984). Within the general field of combinatorial optimization, a language has been developed which can be used to describe characteristics of these problems, and special techniques have been implemented to model those characteristics in optimization algorithms. For example, the requirement that each label must be accounted for by placing it in one of a finite number of positions on the map is a generalized upper bounding set constraint. The additional constraint that two labels are not allowed to overplot each other is a degree-two constraint (Johnson and Padberg 1982). A modified special ordered set constraint (Johnson, et al. 1985) can be used to limit the number of labels deleted from a map. Relaxation techniques can be used to dynamically identify binding label conflict constraints during the optimization process. The fact that a label either is or is not in one of its possible positions is accounted for by using 0-1 integer programming.

The problem of placing many labels on a large, densely labeled map formulated as an optimization problem can have thousands of variables and thousands of constraints. Much recent research in combinatorial optimization has been directed at developing algorithms which can find optimal solutions to large 0-1 integer programming problems (Crowder et al. 1983; Johnson et al. 1985; Kedia 1985; Fisher and Kedia 1990). Considerable success has been obtained in these research efforts, enough to expect that a label placement problem involving scores of map features placed close together could be solved to optimality in a few minutes of CPU time on a modern computer workstation. Other research efforts in combinatorial optimization have shown how larger problems with thousands of variables and thousands of constraints can be solved efficiently and reliably to within a few percentage points of optimality (Fisher 1981).

It has been suggested that the complexity of the label conflict problem is so great that obtaining mathematical solutions to large problems impractical (Doerschler 1988; Mower 1989). In fact, programs which treat the point label placement problem as an optimization problem exist today and at least one is being used in map production. In separate papers Cromley (1985, 1986) and Zoraster (1986, 1990) have described how standard mathematical techniques can be used to solve these problems. Algorithm-based programs do not necessarily find the optimal solution to any particular problem, but they can reliably find good solutions which satisfy most map users, even when working on large, densely labeled maps. Running on workstations typical of those now used for automated cartography, and implemented in procedural programming languages like FORTRAN, algorithm-based label placement program can place thousands of labels on a map, while resolving thousands of label and symbol conflicts (Zoraster and Bayer 1987).

EXPERT SYSTEMS AND MAP LABEL PLACEMENT

Heuristics have their place in all parts of computer science, including combinatorial optimization, but I know of no engineering or scientific discipline in which experts systems are the preferred way to solve optimization problems when cost effective mathematical algorithms are readily available. Even computer scientists involved in the development of expert systems say that when a mathematical algorithms exists, using the algorithm is usually a better choice than using an expert system (Keller 1987; Slagle and Wick 1988). The conflict resolution part of map label placement is an example of a problem for which mathematical algorithms exist, execute relatively quickly, and are not very difficult to implement.

Of course, expert systems can call algorithms to perform particular tasks, and a combinatorial optimization algorithm could simply be another tool incorporated into a cartographic expert system. In this environment, the cartographic knowledge and the inference engine of the expert system would be available to evaluate particular label patterns; to suggest new label placements that might resolve conflicts while maintaining high cartographic quality; and to perform related map compilation tasks such as identifying particular map features to label. However, the existing expert systems for label placement have not made a significant start in this direction because the "'expert' part of the expert system technology has been largely ignored. An expert system is supposed to encode the unique knowledge of an expert. But there is hardly any reference contact with cartographic experts in papers on map label placement programs. Among the sixteen reports on rule-based or expert system-based label placement programs cited in the introduction to this article, only one mentions input from cartographers during program development (Drinnan et al. 1989). Instead of experts the standard sources for label placement rules are one paper by Yoeli (1072), one paper by Imhof (1975), and the study of existing maps by the person developing the expert system. Expert evaluation of automatically generated label-configurations is discussed in only one of the sixteen reports (Mower 1989).

Two papers are a weak foundation on which to build complex expert systems for map label placement, especially since some of the rules contained in those papers have been contradicted by recently completed studies of manually compiled maps (Cook 1988; Wu 1989). In fact, the claim that expert systems for label placement can be developed without discussing the problem with mapmakers is startling. Most books and articles on expert system consider only those problems for which access to one or more domain experts is required. Problems which do not need such 'knowledge engineering' are normally considered to be inappropriate candidates for solution by an expert system (Bobrow et al. 1986; Slagle and Wick 1988).

The arguments given above do not mean that rule-based, heuristic programs cannot perform map label placement. Based on the published results they obviously can. And the authors of those programs may intend to expand them into true expert systems by adding expert knowledge to the book knowledge already encoded in them. However, it is still far from certain that expert systems, even expert systems which call optimization algorithms to resolve label conflicts are the right tool for map label placement. One reason to doubt that they are is their cost relative to alternate solutions. Textbooks and articles on expert systems emphasize that they can be very expensive. Development of a moderate size expert system can be expected to take at least 3 man-years, and probably longer to turn into a useful product (Bobrow et al. 1986; Keller 1987; Bowerman and Glover 1988; Slagle and Wick 1988). Testing, validation and maintenance of expert systems create unique difficulties which add to their long term cost (O'Leary 1988; Baker and O'Connor 1989).

Exactly how long would it take to implement a true expert system for map label placement is uncertain because nobody has written such a program. For comparison purposes, the algorithm-based label placement program developed by Zoraster and Bayer (1987) was completed as a commercial product in less than one and a half man-years. Admittedly, that program places only point feature labels, but it is not unsophisticated: it distinguishes between five different types of point feature labels; handles label made up of multiple lines of text; allows certain single line labels to be rotated away from horizontal; and moves point feature labels from previously positioned area and contour feature labels. Furthermore, that program is installed, maintained, and updated exactly like other complex, algorithm-based cartographic programs, such as production-oriented gridding and contouring programs.

EXPERT SYSTEMS, COMBINATORIAL OPTIMIZATION, AND CARTOGRAPHY

Expert systems are fashionable in cartographic research today. That is understandable given the complexity of many map compilation problems, but the emphasis on expert systems may be overdone. Certainly the existing map label placement programs are not sufficient justification for believing that expert systems will work well in performing other cartographic tasks. In fact, the weaknesses of those programs are reasons to take a closer look at what expert systems really are, what they have to offer to automated cartography, and how they should be used in a cartographic production environment.

On the other hand, combinatorial optimization does not appear to be fashionable among cartographers. The fact that the label conflict resolution part of published label placement algorithms can be formulated as a combinatorial optimization problem, combined with reported successes using optimization techniques to solve label placement problems for point features, should encourage cartographers to become more interested in optimization techniques. A tangential but still relevant point is that the only sophisticated area feature label placement program described in the cartographic literature which is used in map production selects label positions by maximizing an objective function (van Roessel 1989).

In the debate between algorithms and expert systems there may be a lesson to be learned by cartographers from recent developments in the study of motion planning for robotics. Robotics, like automated cartography, is a research field concerned with understanding spatial relationships between features. In the past, motion planning for robotics relied almost completely on heuristics and rule-based programs. Now, researchers working in robotics are showing increased interest in mathematical algorithms in order to obtain better solutions to motion planning problems, and guide them in the search for good heuristic procedures (Sharir 1989).

CONCLUSIONS

Existing computer programs for map label placement which are identified as expert systems stretch the defining boundaries of expert systems. Label conflict resolution, the part of the label placement problem for which the majority of label placement programs rely most strongly on expert systems technology, can also be formulated as a mathematical optimization problem, and at least one production oriented program for the placement of point feature labels which relies on optimization techniques already exists. Furthermore, the developers of existing systems have not yet adequately explored issues such as knowledge engineering in cartography, and the high cost of expert systems. Because of these limitations it is not justified to cite the results achieved using expert systems in map label placement as reasons for believing that expert systems are the correct tool to perform other map compilation tasks.

ACKNOWLEDGEMENTS

Discussions with Mr. Wally Washington of Zycor and Dr. Margaret Ball helped clarify my thoughts on the automation of map label placement and on the use of expert systems to perform that task.

REFERENCES