David A. Bennett, Marc P. Armstrong, and Greg A. Wade

ABSTRACT

Environmental problems often result from the distributed and uncoordinated land use management practices of individual decision-makers that, when taken together, cause significant environmental impacts. To develop feasible and politically acceptable solutions to such problems it is often necessary to foster compromise and consensus among a diverse set of special interest groups who possess overlapping sets of objectives; some quantifiable, some not. The union of these sets forms a criteria space that constrains the set of feasible solutions that may be adopted by resource managers. As interest groups work toward the common goal of a mutually acceptable resource management plan they often require assistance in the development, representation, and analysis of this criteria space. Furthermore, new tools are needed that form explicit links between criteria space and the geographic space that is being managed. This paper illustrates how genetic algorithms are used to construct a link between criteria and geographic space and to evolve mutually acceptable solutions to complex environmental problems. Intelligent agents help decision-makers invoke various criteria and learn from the successes and failures of generated solutions in both geographic and criteria space. This knowledge is used to help users assess the fitness of alternative solutions and generate improved solutions to complex environmental problems.

1.0 INTRODUCTION

Research in cumulative impact assessment illustrates how individually insignificant land use decisions can have significant deleterious impacts on the environment (Johnston et al., 1988; Preston and Bedford, 1988). To properly manage environmental resources in privately owned landscapes it is necessary to understand how these individual decisions affect environmental processes across space and through time. The tools used by resource managers to promote environmental objectives in a privately owned landscape depend largely on education, incentive-based policy initiatives (e.g. conservation reserve program) and quasi-regulatory compliance programs (e.g. commodity programs). Furthermore, private and public concern about the environmental ramification of land management is only one of many competing issues that must be addressed by land managers. To develop feasible and politically acceptable solutions to environmental problems generated by the cumulative impact of multiple decision-makers it is often necessary to foster compromise and consensus among a diverse set of special interest groups who possess overlapping objectives; some quantifiable, some not. Environmental management, therefore, is often a semi-structured problem that requires a collaborative effort among multiple stakeholders.

The difficulties associated with environmental problem solving have parallels in other problem domains. In practice, spatial problem solving tends to be a semi-structured and collaborative effort that crosses managerial and disciplinary bounds. Geographic information systems (GIS) often lack the problem-specific analytical tools needed to adequately explore the solution space of semi-structured problems. Though spatial decision support systems (SDSS) are often designed specifically to address semi-structured problems, they often lack support for collaborative decision making (Armstrong, 1994). Recognizing the limitations of existing geoprocessing technologies, the National Center for Geographical Analysis (NCGIA) established a new research initiative (I-17) designed to address the technological needs of collaborative spatial decision making (CSDM). In September, 1995, the first I-17 specialist meeting was held to identify technological impediments to the development of group-based spatial modeling and decision making environments. Five research topics were identified for discussion at this meeting (NCGIA, 1995):

1. The development of metaplanning capabilities to elicit, capture, and manipulate knowledgebases that support spatial problem solving.
2. The design and implementation of methods to improve decision-makers' interaction with such spatial analysis tools.
3. The provision of mechanisms that enable decision-makers to evaluate alternative solutions to a problem.
4. The identification, selection and incorporation of methods for resolving spatial conflicts in interactive, CSDM environments, including multicriteria decision making.
5. The characterization of CSDM processes, including but not limited to the specification of task models in specific problem domains.

The research presented here is directed toward research topics 2, 3, and 4. In particular, we consider the utility of two technologies, intelligent digital agents and genetic algorithms, as a means of exploring a multicriteria solution space.

2.0 THE CACHE RIVER WATERSHED STUDY

This research is, in part, motivated by a complicated set of resource planning activities that are occurring in the Cache River watershed in southern Illinois. This watershed is largely privately owned and contains an internationally significant cypress/tupelo wetland (a RAMSAR site). There is considerable concern that this unique wetland community is threatened by agricultural land use practices. In this watershed there are three general classes of decision-makers in the watershed who impact land use patterns and, thus, the wetland. These classes are:

1. Farmers who: 1) want to retain full control over their land (private property rights issue); 2) want to maximize farm revenue; and 3) have concern for erosion control.
2. Conservationists (public and private) who want to conserve the ecological vitality of the wetland community.
3. Regional economists who are looking for ways to diversify and bolster the weak economy of this area through: 1) agricultural; 2) industrial; and 3) recreational opportunities.

A multi-disciplinary research team from Southern Illinois University at Carbondale is investigating the impact of alternative resource policy and management scenarios on the economy, hydrology, and ecology of the Cache River watershed. One goal of this research effort is to develop a land use management plan that is generally acceptable to each of these three classes of decision-makers. To evaluate the acceptability of specific management scenarios it is necessary to trace their effect through economic, sociologic, hydrologic, and biologic systems.

3.0 INTELLIGENT AGENTS AND CSDM

Stakeholders in the context of environmental problem solving represent several interests and bring to the negotiation table different types of training, levels of education, experience with computing technologies, and familiarity with the problem that is being addressed. This differential in knowledge can have important interaction effects. For example, a person knowledgeable about the characteristics of soil maps would likely treat a soil layer in a GIS much differently than a person without such knowledge. In spite of their differences, group members must work together to devise solutions to complex problems. If they are unable to overcome the conceptual and technical barriers that inhibit the effective use of alternative technologies then geoprocessing software cannot be used to its fullest capacity.

One way to provide support in heterogeneous decision-making environments is to provide users with intelligent software agents. Two basic forms of software agents have been identified (Shoham, 1993). Personal agents assist users in the execution of routine tasks such as prioritizing electronic mail or maintaining appointment calendars (see for example Kautz et al., 1994). These types of agents learn from repeated interaction with specific users and use this knowledge to guide subsequent behavior. In the context of spatial decision making one can envision a personal agent that properly interprets fuzzy spatial language (e.g., near vs. far) or anticipates the type of information that a decision-maker will require to analyze a new alternative. Autonomous agents, on the other hand, are instantiated with a "belief system" (Shoham, 1993) and possess the ability to act on and react to changing stimuli based on this belief system. Deadman and Gimblet (1994) illustrate how autonomous agents can be used to facilitate recreation management. Edmonds et al. (1994) implemented five classes of autonomous agents (user, group, floor, conference, and application agents) to facilitate CSDM.

4.0 GENETIC ALGORITHMS

Genetic algorithms are modeled after those processes that drive biological evolution. Alternative solutions in the search space represent individuals in an evolving population. Characteristics that can be used to evaluate the relative success of individual solutions are stored in classifiers. These classifiers are often implemented as bit-strings that document whether a specific solution possesses a given characteristic (Booker et al., 1989; Armstrong and Bennett, 1990). For example, an automobile classifier may record whether a vehicle has the characteristic of "four doors". This information can be used to construct a criterion that suggests that a vehicle possessing four doors is more fit as a "family car" than one that does not. The perfect "family car" will, of course, possess a large set of characteristics and it may be that no one vehicle will meet all criteria. So, how is a vehicle designed such that it approximates, as closely as possible, the ideal family car? A genetic algorithm approach would start with the existing population of vehicles and recombine characteristics that best meet the stated criteria. Genetic algorithms, therefore, explore the solution space by adding new alternatives derived from those existing alternatives considered to be most fit. Fitness in this context is proportional to how well a particular solution meets stated criteria.

Three genetic operators are used to combine existing solutions to create new individuals: cross-over, mutation, and inversion. Cross-over is the most powerful of these operators (De Jong, 1990). The cross-over operation generates two new offspring by duplicating two individuals (parents) and swapping "genetic code" beyond some randomly selected cross-over point. To understand the utility of cross-over consider the example discussed below.

4.1 An Example

A decision-maker believes that an ideal family car must possess the following characteristics: four seats, four wheel drive, large cargo area, and enclosed cargo area. These four characteristics can be mapped to a classifier (Figure 1). A fitness value for automobile design can be defined as the total number of desired characteristics possessed by existing or proposed vehicles. Assume that the known universe of automobiles includes only sport cars, four wheel drive trucks, sedans and station wagons, none of which meet all of the desired characteristics. Realizing that the ideal car design has not been invented (no fitness value equal to 4) the genetic algorithm begins to explore the solution space by creating two new car designs by merging the characteristics of a four wheel drive truck and a station wagon (see Figure 1). The generation of new alternatives continues until some terminating criteria is met (e.g., the decision-maker gets a car design that meets stated criteria, a patent is issued, and lots of money is made selling sport utility vehicles).

Figure 1. Genetic algorithms evolve new and better solutions through the application of genetic operators (cross-over, mutation, and inversion). The most important of these operators is cross-over.

4.2 A Formal Description of a Genetic Algorithm

A more formal description of the genetic algorithm is as follows (after De Jong, 1990; Koza, 1994):

1. Generate an initial population, P(0), of solutions. These individual solutions are often created as random combinations of identified characteristics.
2. Do until the termination criteria are satisfied:
   1. For each individual, m_j, in the current population, P(i), calculate a fitness, F(m_j).
   2. Select n individuals from P(i) that will be used to generate n new solutions for P(i+1) via cross-over, inversion, and/or mutation. The probability, p, that individual m will be used to create new alternatives for population P(i+1) is a function of its fitness, F(m):
      

   3. Copy the contents of P(i) and the newly created alternatives to P(i+1).
   4. Store the "best-so-far" solution.
   5. Remove m individuals from P(i+1) (based on user defined criteria).
   6. Advance to the next generation i+1.
3. Report results to users.

Although geographical applications of this approach are rare, Dibble and Densham (1993) illustrate the utility of genetic algorithms in the solution of location/allocation problems.

5.0 AGENT-DIRECTED GENETIC ALGORITHMS FOR ENVIRONMENTAL PROBLEM SOLVING

As can be seen in the Cache River watershed example, to solve spatial problems it is often necessary to identify management strategies that are acceptable to multiple decision-makers (e.g. farmers, conservationists, and regional economists). As suggested above in Section 2, the actions of these decision-makers will be guided by different sets of criteria. The union of these sets forms a criteria space that constrains the set of acceptable solutions. Genetic algorithms are used here to establish a link between criteria space and geographic space and to evolve mutually acceptable solutions to complex environmental problems. Autonomous agents help evaluate how well alternative land use patterns meet user specific criteria and build consensus among competing interests.

5.1 Genetic Algorithms for Two Dimensional Space

Traditional genetic algorithms operate on a finite set of well defined characteristics that are easily mapped to a linear data structure that supports cross-over operations. To use this approach to generate alternative landscapes it is necessary to extend the notion of a linear sequence of genetic code into two dimensional space. Fortunately, the linearization of space is a well studied problem. One of the most useful indexing schemes for accomplishing this task is the Morton sequence which provides a linear indexing scheme for raster-based geographic data sets (Samet, 1990). Using this linear indexing scheme and two randomly selected cross-over points we have a mechanism to create new landscapes that possess characteristics of two parent landscapes (Figures 2 and 3).

5.2 Multicriteria Decision Space

As suggested above, to solve spatial problems it is often necessary to consider the impact of alternative management scenarios on several competing criteria. Furthermore, the set of relevant criteria and the relative importance of specific criteria vary with the goals and objectives of the decision-maker. The classifier and fitness function illustrated in our simple car design example lacks the complexity needed to capture and explore a semi-structured, multicriteria decision space. To overcome these limitations we recast

Figure 2. To use genetic algorithms to develop interesting landscape alternatives space is "linearized" using a Morton index.

Figure 3. Two new landscapes created by the "genetic cross-over" illustrated in Figure 2.

our fitness function into a modified multicriteria evaluation function. To compare criteria (e.g., minimize erosion and maximize agricultural profit) it is necessary to first standardize criteria scores. This can be accomplished as follows (Carver, 1991):

In the context of genetic algorithms, the maximum and minimum raw scores must be tracked through the generations. If these values cannot be determined a priori then the standardized score must be recalculated for all individuals in the population for each generation. Otherwise, it is necessary to calculate a standardized score only for the individuals added to the population in the current generation. By defining the maximum and minimum scores to be cross generational, and using these scores to standardize multiple criteria, the identification of superior solutions in this genetic algorithmic approach is analogous to an ideal point analysis (see for example Carver, 1991) except that the computer is used to create the set of alternatives that are analyzed. The fitness of landscape l is, therefore, calculated as the weighted average of standardized scores.

where:

F(l) = fitness value for landscape l.

sc_i = standardized score for criteria i given landscape l.

w_i = relative weight for criteria i.

These criteria weights reflect a qualitative assessment of a single decision-maker or, perhaps, class of decision-makers. One way to calculate a global fitness value for a landscape is, therefore, the mean of independently calculated fitness values:

where:

Fg(l) = Global fitness value for landscape l.

Fi(l) = Fitness value for landscape l and decision-maker i.

N = Total number of decision-makers.

5.3 Agent Driven Processes

As geoprocessing software becomes more sophisticated, it is able to support the analysis of an increasingly broad set of problems. This richness, however, has a downside: software has become increasingly complex and, thus, more difficult to use. In addition, because of the number of options available, users may not always understand the implications of their choice of a particular method for performing a needed function. In many cases, additional knowledge may be required to support informed use. To reduce the technological burden on the decision-maker, we drive this software system using intelligent agents. At this point, two classes of agents have been implemented, mediating agents and user agents (Figure 4) and the behavior of the agents is straight-forward. A user agent acts on behalf of a specific decision-maker, calculate Fi(l) for each individual landscape l, and returns these values to the mediating agent. Using this information the mediating agent calculates Fg(l), selects individuals for cross-over, generates new alternatives and removes unfit individuals from the population.

Figure 4. The genetic algorithms are implemented with two classes of autonomous agents: user agents and mediating agents.

6.0 FUTURE DIRECTIONS

With this initial research effort we have implemented a relatively simple and straight-forward integration of genetic algorithms and multicriteria evaluation. From this basic foundation we have identified several avenues for future research. First, we will allow the agents to evolve their own landscapes and contribute locally fit landscapes back into the global population. It is hoped that this modification will accomplish three goals: 1) "allopatric speciation" of landscapes will increase the chances of finding unique and innovation alternatives and create a more diverse "genetic pool" from which to build the solution space; 2) users will have more control over domain-specific models and, thus, more control over the development of alternatives; and 3) by distributing some of the responsibility for the generation and analysis of alternative solutions we will be able to take better advantage of parallel processing technologies. In the next phase of our research we will improve on the agent's ability to learn from and assist users. To address the semi-structured nature of spatial problems the decision-maker must be an integral part of the problem solving process (Densham, 1991). As such, these decision-makers must be able to query the system, develop and apply new models, build management scenarios, engage in "what if" simulations, and purposefully alter the criteria space. These requirements call for intelligent interfaces and modelbase management capabilities. Finally, we want to enhance the ability of the mediating agent to support consensus building. One possibility is to include the development of delta maps in the behavior of mediating agents (Armstrong et al., 1992). These maps will focus attention and debate on areas of possible contention and allow the agents to hold constant those areas for which there is agreement.

7.0 CONCLUSION

Research in cumulative impact analysis illustrates how small, individually insignificant disturbances to the landscape can accumulate through space and time to produce significant environmental problems. Yet natural resource management strategies, and the tools that we used to evaluate and implement these strategies, are often directed toward large land areas. To support effective resource management practices new tools are needed that allow us to build consensus among multiple stakeholders and to investigate the cumulative impact of individual decision-makers. This research investigates two technologies that offer promise for such collaborative spatial decision making processes, agent-oriented programming and genetic algorithms. Genetic algorithms are used here to evolve landscapes that meet predetermined criteria. Intelligent agents provide a means of evaluating the fitness of these landscapes based on weighted criteria. Through this interaction between intelligent agents and genetic algorithms management strategies can evolve in such a way that multiple stakeholders are satisfied.

8.0 REFERENCES

Armstrong, M.P. 1994. Requirements for the development of GIS-based group decision support systems. Journal of the American Society for Information Science, v. 45, n. 9, pp. 669-677.

Armstrong, M.P. and Bennett, D.A. 1990. A bit-mapped classifier for groundwater quality assessment. Computers and Geosciences, 16 (6): 811-832.

Armstrong, M.P., Densham, P.J., Lolonis, P., Rushton, G. 1992. Cartographic displays to support locational decision-making. Cartography and Geographic Information Systems, v. 19, n. 3, pp. 154-164.

Booker, L.B., Goldberg, D.E., Holland, J.H. 1989. Classifier Systems and Genetic Algorithms. Artificial Intelligence, v. 40, pp. 235-282.

Carver, S.J. 1991. Integrating multi-criteria evaluation with geographical information systems. International Journal of Geographical Information Systems, v. 5, n. 3, pp. 321-339.

Deadman, P. and Gimblet, R.H. 1994. A role for goal-oriented autonomous agents in modeling people-environment interactions in forest recreation. Mathematical Computer Modelling, v. 20, n. 8, pp. 121-133.

Densham, P.J. 1991. Spatial decision support systems. In Geographical Information Systems: Principles and Applications edited by D.J. Maguire, M.F. Goodchild, and D. Rhind. Wiley, New York, NY.

De Jong, K. 1990. Genetic-algorithm-based learning. In Machine Learning edited by Y. Kodratoff and R. Michalski. Morgan Kaufmann, San Mateo, CA.

Dibble, K., Densham P.A. 1993. Generating interesting alternatives in GIS and SDSS using genetic algorithms. In Proceedings of GIS/LIS '93 ,Volume 1. Bethesda, MD: American Congress on Surveying and Mapping, pp. 180-189.

Edmonds, E.A., Candy, L., Jones, R., Soufi, B. 1994. Support for collaborative design: Agents and emergence. Communications of the ACM, v. 37, n. 7, pp. 41-47.

Koza, J.R. 1994. Introduction to genetic programming. In Advances in Genetic Programming edited by K.E. Kinnear. MIT Press, Cambridge, MA.

Kautz, H.A., Selman, B., Coen, M. 1994. Bottom-up design of software agents. Communications of the ACM, v. 37, n. 7, pp. 143-147.

Johnston, C.A., Detenbeck, N.E., Bonde, J.P., Niemi, G.J. 1988. Geographic information systems for cumulative impact assessment. Photogrammetric Engineering and remote Sensing, v. 54, n. 11, pp. 1609-1615.

NCGIA 1995. I-17: Collaborative Spatial Decision-making. http://www.ncgia.ucsb.edu/research/i17.html.

Preston, E.M., Bedford, B.L. 1988. Evaluating cumulative effects on wetland function: A conceptual overview and generic framework. Environmental Management, v. 12, n. 5, pp. 565-583.

Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison Wesley, Reading, MA.

Shoham, Y. 1993. Agent-oriented programming. Artificial Intelligence, v. 60, pp. 51-92.

David A. Bennett, Department of Geography, Southern Illinois University, Carbondale, IL 62901-4514, dbennett@siucvmb.siu.edu.

Marc P. Armstrong, Department of Geography and Program in Applied Mathematical and Computational Sciences, University of Iowa, Iowa City, IA 52242, marc-armstrong@uiowa.edu.

Greg A. Wade, Departments of Geography and Computer Science, Southern Illinois University, Carbondale, IL 62901-4514, wade@cs.siu.edu.