prt%3A978-0-387-35973-1%2F16

quality of the stored data with respect to the actual world being modelled [1]. On the other hand, the management (i. e., representation, indexing, querying) of the spatial data for applications such as GIS, in which the entities of interest are objects with particular geographic and dimensionality attributes (e. g., location, shape, extent) was investigated [20]. One of the Þrst commercially-important applications in which the efÞcient management of the (location, time) information for a large number of mobile users is a paramount, was the cellular telephony. Various data management architectures were proposed for the efÞcient tracking, call-forwarding and billing of users [18]. Around the same time, motivated by various LBS applications, researchers recognized the need for more thorough treatment of spatio-temporal data, i. e., data whose spatial attributes (e. g., location) change over time. In particular [22], introduced the concept of dynamic attributes and spurred the development of the Þeld of moving objects databases [12]. Due to the dynamic nature of the entities involved, data management in MOD settings has a number of distinguishing features, with respect to the traditional data management aspects of modelling/representing the data [11], indexing structures for accessing the data items [15,24], and algorithms and methodologies for processing the spatio-temporal queries [7,10,12]. In particular, the most widely used queries (range, (k)nearest-neighbor, join) become continuous. In other words, their answers change over time due to the changes in the locations of the moving objects, and efÞcient techniques are needed for maintaining the correctness of the answers.

Different works have used different models to represent the motion plans of the moving objects and, based on the model chosen, a plethora of indexing structures and algorithms for processing the popular categories of spatio-temporal queries have been proposed [12,24]. However, irrespective of the chosen representation, the uncertainty of the moving objects remains an inherent component. As has been pointed out in many works (e. g., [27,29]), unless the uncertainty is captured in the model itself, the burden of factoring it out from the meaning/answers of the various spa- tio-temporal queries will fall on the end user. Hence, we need the following: (1.) Models of the uncertainty as part of the objectsÕ motion model. (2.) Linguistic constructs

that will enable the users to specify queries in the presence of uncertainty. (3.) Techniques for efÞcient query processing for uncertain moving objectsÕ data.

Scientific Fundamentals

Traditionally, there are three main models for representing the future motion plans of moving point objects. As a consequence of the chosen model, the researchers have developed corresponding algorithms for the processing of continuous spatio-temporal queries.

¥At one extreme is the model in which the objects periodically send their (location, time) updates to the MOD

¥In the Òmiddle-landÓ is the model in which the moving objects are assumed to periodically send (location, time, velocity) updates to the MOD server [22], as illustrated by the middle portion of Fig. 2. EfÞcient algorithms for processing continuous queries in MOD under this model were presented in [13], and [10] addressed the distributed processing of such queries, by delegating some of the responsibilities to the moving objects themselves. One peculiar feature of this model is that in-between two consecutive updates, the objects are allowed to deviate from the expected route which is calculated using the velocity parameter of the most recent update, for as long as the deviation is within certain tolerance bounds [29]. This is illustrated by the shaded circles in the middle portion of Fig. 2, which shows the actual locations-in-time, as opposed to the expected ones that would be along the dotted arrowed line.

¥The other extreme model is the one in which the entire future motion plan of a given object is represented as a trajectory (right-most portion in Fig. 2). Under this model, each object is assumed to initially transmit to the MOD server the information about its start_location,

end_location, and start_time of the trip, plus (possibly) a set of Òto-be-visitedÓ points. Using the information available from the electronic maps, plus the knowledge about the distribution of the trafÞc patterns in a given time-period, the server will apply an A*-like variant of the time-aware DijkstraÕs algorithm to generate the optimal travel plan [27]. A trajectory is essentially a sequence of 3D points (2D geography + time) of the form (x1, y1, t1), (x2, y2, t2), . . . , (xn, yn, tn), where t1 < t2 < . . . tn and in-between two points the object is assumed to move along a straight line and with a constant speed. The peculiarity of this model is that it enables answering continuous queries pertaining to the further-future; however, the consequence is that a disturbance of the trafÞc patterns in a small geographic region may affect the correctness of the queries in wide- ly-dispersed areas and at different time-intervals [7].

An important observation is that when it comes to the past portion of the objectsÕ motion, all three models, in a sense, converge, and represent it as a trajectory (bottom part of Fig. 2).

Any model of the uncertainty of the moving objects, as well as its implications on the query processing algorithms, is closely associated with the adopted model for representing the objectsÕ motion plans.

As we already have illustrated in Fig. 1, even a single location update at a given time-instance is associated with its own uncertainty. Furthermore, if the motion plan of the moving objects is represented as a sequence of (location, time) updates, then there are other consequences of the uncertainty. As an illustration, observe the left portion of Fig. 3. Assume that it represents a scenario in which an exact value of of the locations of a given object is known at times t1 and t2 (also assuming that the consecutive updates were sent at those times). However, even under this assumption (and, again, ignoring the fact that these very values already have uncertainty associated with them, c.f, Fig. 1.), there is still some imprecision regarding the objectÕs motion. Namely, given only the velocity bounds of the object o1, its location at a time t (t (t1, t2)) cannot be exactly determined. As illustrated in the left portion of Fig. 3 (assuming that (t − t1) < (t2 − t)), at t, o1 can be anywhere inside the lens obtained as the intersection of the of the two circles bounding the objectÕs possible locations with respect to its maximum speed limit. It can be demonstrated that all the possible whereabouts of the object for the time-interval (t1, t2) are bound by an ellipse with foci at the locations reported at the respective times [17]. If one assumes a certain probability distribution corresponding to the objects uncertainty [4], then algo-

rithms can be developed for answering the spatio-temporal queries with uncertainty. As a particular example, illustrated by the right portion of Fig. 3, one can pose the range query: QR1: “What is the probability that the object o1 will be inside the region R between tb and te”, for which the value is obtained by calculating the area of the intersection of the circular ring bounding the location of the object between tb and te, with the polygon bounding the region R, and dividing the result with the area of the circular ring. Another variant of the continuous range query with uncertainty is: QR2: “Retrieve all the objects that have more than 75% chance of being inside the region R between tb and te”. One can easily envision the impact of the uncertainty on the other types of continuous spa- tio-temporal queries. For example, a variant of the nearestneighbor query would be: Q-NN: “Retrieve all the objects that have more then 90% chance of being nearest neighbors to the object o1 between tb and te”.

When the motion plan of the moving object is modelled as a sequence of (location, time, velocity) updates (c.f., the middle portion of the Fig. 2), the uncertainty is already incorporated as a part of the contract/agreement between the MOD server and the individual mobile objects. Namely, in order to minimize the communication overhead, after each update, the particular mobile object knows what is the expected location that the server calculates based on the velocity parameter. For as long as the expected location does not deviate by more than a certain pre-deÞned threshold, say, ε, from the actual location of the object obtained by some measurement (e. g., an on-board GPS device), the object will not send new updates to the MOD server. This kind of update policy is known as a dead-reckoning, and different variants of it have been explored in detail in [29], along with the analytic expressions for deriving the overall information cost of keeping the (im)precision of the MOD data within desired bounds. Clearly, every spatio-temporal query under this model has an explicit uncertainty in its answer, due to the location error-bound of ε. Recent algorithms for efÞcient processing of the spa-

tio-temporal queries under these settings were presented in [10].

For the case when the future motion plan of a moving object is represented as a trajectory, since one of the parameters used in its construction is the distribution of the speed-patterns on the road-segments, the uncertainty represents the acceptable deviation of the objects due to trafÞc ßuctuations.

The implications of this assumption are illustrated in Fig. 4. Namely, if the object is expected to be at some loca-

tion, say, (x1, y1) at a given time t1, the uncertainty area M of its whereabouts is a disk with a radius d, centered at

the expected location (x1, y1). Extending this over a timeinterval, the set of all the possible trajectories of a given moving object deÞnes an uncertainty volume, which in 3D settings (2D geography + time) is represented as a sequence of sheared cylinders, one for each straightline segment of the objectÕs route. Detailed algorithms for processing continuous spatio-temporal queries under these settings were presented in [27], where the qualitative uncertainty of the queries was discussed. Namely, to test for the satisÞability of the spatio-temporal predicates, the quantiÞers possibly and definitely were considered in the spatial dimension, and the quantiÞers considered in the temporal dimension were sometimes and always. The query operators corresponded to the various predicates that can be composed by interleaving the order of the quantiÞcation. Thus, the right portion of Fig. 4 presents an example of an uncertain trajectory which satisÞes the predicate:

“Possibly inside region R, sometimes between t1 and t2”.

An approach assuming quantitative probabilistic values for the answer to such queries, under the assumption of uniform distribution for the probability of the object being inside the disk with radius d was presented in [25].

Clearly, one cannot dwell on query processing for any large data sets unless there are proper indexing techniques for retrieving that data, especially during the Þltering stage in which disk-accesses should be minimized, while ensuring as few false-positives as possible. There has been

a plethora of indexing structures proposed for processing continuous spatio-temporal queries (e. g., see the references in [12]). Furthermore, recent research works have speciÞcally focused on developing efÞcient indexes which explicitly take into consideration the uncertainty of the mobile entities [6]. One of the main beneÞts of incorporating the uncertainty into the index is that certain objects can be pruned from the search earlier during the Þltering part of the processing of probabilistic queries.

Some of the recent works targeting efÞcient management of continuous spatio-temporal queries for moving objects have explicitly focused on deeper exploitation of the fact that in many applications of interest, the objects are moving on road networks [9]. This additional semantic knowledge can be exploited to obtain further gains in the efÞciency of objectsÕ tracking and query processing. Recently, techniques have been developed for efÞcient tracking and indexing of moving objects on road networks [6] and, in particular, the impact of uncertainty under such settings has been investigated in [8].

Key Applications

Moving object uncertainty is of interest in several scientiÞc and application domains.

GIS

Typically, in MOD research, the moving objects are approximated as points whose dimensions (e. g., size) can be neglected with respect to the overall area/volume of the universe of discourse. However, many of the objects of interest in GIS can not be approximated as points Ð namely, rivers have their shapes, forests cover areas typically represented as polygon-bounded regions, Þres are spreading in time and are represented as moving polygons [11]. How-

ever, the boundaries between regions are seldom precise (e. g., a boundary between a prairie and a desert). Hence, one must account for the uncertainty in the representation and use the corresponding mathematical tools to model it and develop query algorithms (e. g., fuzzy-set theory [17]).

LBS

A variety of applications in LBS can use the uncertainty inherent to mobile objects. As a typical example, in tourist-information systems, the main concern is how to provide a context-aware delivery of the data which matches the preferences of a given user based on its location [21]. However, if revealing the exact location of the mobile user can be adversely used for violating some of the privacy issues, uncertainty can be used to provide some forms of location-based privacy. As another example, depending on the trade-offs between the desired uncertainty of the information (e. g., as a function of the distance of a given moving object from a given target) and the size of data kept in the cache, methodologies have been devised which implement various policies for keeping/purging data items in/out a given cache [5].

Meteorology and Seismology

Many of the phenomena of interest in meteorology are entities which move and even change their shape over time (e. g., clouds, ßood regions). Clearly, one cannot exactly model their shapes and bounding regions/volumes and for the purpose of query processing and any kind of reasoning involved, the uncertainty must be incorporated as part of the representation and the evolution of the objects [19]. Furthermore, the probabilistic values due to uncertainty must be properly taken into consideration if the system, which monitors the phenomena of interest, is

expected to exhibit some form of reactive behavior [17,26]. These issues are extremely important when, based on the changes of the monitored values (e. g., the coastal erosion co-related with seismic measurements in tsunami prediction; the CO-concentration co-related sulphur concentration and the temperature increases for predicting volcanoÕs eruption) disaster-preventing alarms need to be issued with certain probabilistic guarantees [23].

Bio-Chemistry

The efÞcient management of a vast body of observational data generated by expensive experiments is a paramount for researchers in biology and chemistry. As a particular example, the modelling of the information representing large sequences of metabolic pathways requires special tools to store, visualize and query such data. Due to the inherent properties of the micro-world, uncertainty is a natural parameter in such data sets. However, an important part of the research in biology and chemistry is related to modelling and reasoning about the reactions that may occur in various experiments. In such settings, the micro-mobility of the compounds which bind themselves in larger structures during the process of a given experiment cannot be speciÞed in a crisp manner. Consequently, some researchers have recently incorporated the uncertainty when modelling the dynamics of the metabolic control [28].

Sensor Networks

The management of spatio-temporal data in sensor networks is a relatively new Þeld with many open challenges and its natural settings simply cannot avoid the uncertainty. Namely, regardless of what kind of sensors are used for tracking mobile objects, the precision of determining their location is limited. Furthermore, due to the discrete coverage of a given geographic region of their deployment, determining the set of sensors that should process a particular query (e. g., the boundary of a given region for a range query) introduces yet another source of uncertainty [2]. Yet another domain-speciÞc problem that arises in these settings, and is a natural source for the imprecision of the data, is due to the fact that the quality of the readings of the sensor nodes are (an inverse) function of the mobile objectÕs distance and, moreover, maintaining the identities of the individual objects (for the purpose of correct answer to the queries) is a challenge of its own [31].

Spatio-temporal Data Reduction and Data Mining

The goal of any data reduction method is to decrease the size of the data-set of interest for a particular applica-

Cross References

Indexing Schemes for Multi-dimensional Moving Objects

Privacy Threats in Location-Based Services

Spatio-temporal Query Languages

Uncertainty, Modeling with Spatial and Temporal

References

1.Bšhlen, M.H., Jensen, C.S.: Temporal data model and query language concepts. Encyclopedia of Information Systems, 4, Academic Press, Inc. (2003)

2.Buragohain, C., Gandhi, S., Hershberger, J., Suri, S.: Contour approximation in sensor networks. In: DCOSS (2006)

3.Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. Journal of Very Large Databases 15(3) (2006)

4.Cheng, R., Kalashnikov, D.V., Prabhakar S.: Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering. 16(9) (2004)

5.Cherniack, M., Galvez, E.F., Franklin, M., Zdonik, S.: ProÞledriven cache management. In: ICDE (2003)

6.de Almeida, V.T., GŸting, R.H.: Indexing the trajectories of moving objects in networks. GeoInformatica, 9(1) (2005).

7.Ding, H., Trajcevski, G., Scheuermann, P.: EfÞcient maintenance of continuous queries for trajectories. GeoInformatica (2007). doi: 10.1007/s10707-007-0029-9

8.Ding, Z. and GŸting, R.H.: Uncertainty management for network constrained moving objects. In: DEXA (2004)

9.Ding, Z. and GŸting, R.H.: Managing moving objects on dynamic transportation networks. In: International Conference on ScientiÞc and Statistical Database Management (SSDBM) (2004)

10.Gedik, B. Liu, L.: Mobieyes: A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing. 5(10) (2006)

11.GŸting, R.H., Bohlen, M.H., Erwig, M., Jensen, C.S., Lorentzos, N., Nardeli, E., Schneider, M., Viqueira, J.R.R.: Spatio-temporal models and languages: An approach based on data types. In: Spa- tio-temporal Databases Ð the Chorochronos Approach. (2003)

12.GŸting, R.H. Schneider, M.: Moving Objects Databases. Morgan Kaufmann, San Francisco, CA (2005)

13.Iwerks, G.S., Samet, H., Smith, K.P.: Maintenance of k-nn and spatial join queries on continuously moving points. ACM Transactions on Database Systems. 31(2) (2006)

14.Mokbel, M.F., Xiong, X., Aref, W.G.: Sina: Scalable incremental processing of continuous queries in spatio-temporal databases. In: ACM SIGMOD Internation Conference on Management of Data (2004)

15.Pelanis, M., Saltenis, S., Jensen, C.S.: Indexing the past, present, and anticipated future positions of moving objects. ACM Transactions on Database Systems. 31(1), (2006)

16.Pfoser D., Jensen, C.: Capturing the uncertainty of moving objects representation. In: SSDB (1999)

17.Pfoser D., Tyfona, N., Jensen, C.: Indeterminacy and Spatiotemporal Data: basic deÞnitions and case study. Geoinformatica. 9(3) (2005)

23.Stora, D., Agliati, P., Cani, M., Neyret, R., Gascuel, J.: Animating lava ßows. In: Graphics Interfaces (1999)

24.Tao, Y., Papadias, D., Sun., J.: The tpr*-tree: An optimized spa- tio-temporal access method for predictive queries. In: VLDB (2003)

25.Trajcevski, G.: Probabilistic range queries in moving objects databases with uncertainty. In: MobiDE (2003)

26.Trajcevski, G., Scheuermann, P., Ghica, O., Hinze, A., Voisard, A.: Evolving triggers for dynamic environments. In: Extending Database Technology (EDBT) (2006)

27.Trajcevski, G., Wolfson, O., Hinrichs, K., Chamberlain, S.: Managing uncertainty in moving objects databases. ACM Transactions on Database Systems. 29(3) (2004)

28.Wang, L., Birol, I., Hatzimanikatis, V.: Metabolic control analysis under uncertainty: framework development and case studies. Biophysical Journal. 87(6) (2004)

29.Wolfson, O., Sistla, A.P., Chamberlain, S., Yesha, Y.: Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7 (1999)

30.Xing, X., Aref, W.: R-trees with update memos. In: ICDE (2006)

31.Zhao, F., Guibas, L.: Wireless Sensor Networks: an Information Processing Approach. Morgan Kaufmann, San Francisco, CA (2004)

Moving Objects

Indexing of Moving Objects, Bx-Tree

Indexing Schemes for Multi-dimensional Moving Objects

Indexing Spatio-temporal Archives

Moving Objects Database

Mobile Objects Databases

Moving Points

Constraint Databases and Moving Objects

Trajectory

Moving Queries

19.Reiners, W.A.: Transport of energy, information and material through the biosphere. Annual Review of Environment and Resources. 28(1) (2003)

20.Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, San Francisco, CA (2006)

21.Schiller, J., Voisard, A.: Location-based Services. Morgan Kaufmann, San Francisco, CA (2004)

22.Sistla, A.P., Wolfson, O., Chamberlain, S., Dao, S.: Modeling and querying moving objects. In: 13th IntÕl Conf. on Data Engineering (ICDE) (1997)

Moving Regions

Constraint Databases and Moving Objects

MRA-Tree

Multi-Resolution Aggregate Tree

M&S Computing

Intergraph: Real Time Operational Geospatial Applications

M-Tree

Indexing, High Dimensional

Multi Agent Systems

WayÞnding: Affordances and Agent Simulation

Multicriteria Decision Making, Spatial

SALEM CHAKHAR, VINCENT MOUSSEAU

LAMSADE, University of Paris Dauphine, Paris, France

Synonyms

Spatial multicriteria decision aid; GIS-based multicriteria decision analysis; Decision-making, multi-criteria; Decision-making, multi-attribute; Decision-making, mul- ti-objective; Decision rules; Analysis, sensitivity; Analysis, robustness; Preference structure; Mathematical programming

Definition

Multicriteria analysis is generally deÞned as Òa decisionaid and a mathematical tool allowing the comparison of different alternatives or scenarios according to many criteria, often conflicting, in order to guide the decision maker toward a judicious choiceÓ [12]. The set of decision alternatives considered in a given problem is often denoted by A and called the set of potential alternatives. A criterion is a function g, deÞned on A, taking its values in an ordered set and representing the decision makerÕs preferences according to some points of view. The evaluation of an alternative a according to criterion g is written g(a).

Spatial multicriteria decision making refers to the application of multicriteria analysis in spatial contexts where alternatives, criteria and other elements of the decision problem have explicit spatial dimensions. Since the late 1980s, multicriteria analysis has been coupled with geographical information systems (GIS) to enhance spatial multicriteria decision making.

Historical Background

It is generally assumed that multicriteria analysis was born and took its actual vocabulary and form at the beginning of 1960s. In fact, most multicriteria analysis practitioners consider that their Þeld stems largely from the research of Simon on satisÞcing and the early works on goal programming. Closely related to decision-making in general and to multicriteria analysis in particular is utility theory. Although utility theory was Þrst used to model simple individual preferences, it has been extended to multicriteria preferences and led to the multiattribute utility theory [7].

The Þrst methods in multicriteria analysis were developed during the 1960s. Goal programming, for example, uses linear programming method to resolve a multicriteria problem. In 1968, Roy conceived the initial version of the ELECTRE method (see [4]).

Throughout the 1970s, the widely dispersed scientiÞc Þeld of multicriteria analysis started to take form. First, in 1971 Roy organized the Þrst independent session speciÞcally devoted to multicriteria research within the 7th Mathematical Programming Symposium, held in The Hague. Second, in 1972 Cochrane and Zeleny organized the First

International Conference on multicriteria decision mak- M ing at the University of South Carolina. Then in 1975,

Roy organized the Þrst meeting of the EURO Working Group on Multi-Criteria Decision Aid in Brussels. Also in 1975, Thiriez and Zionts organized the First Conference of the International Society on multicriteria analysis. In addition to these Þrst scientiÞc meetings, multicriteria analysis research focused in the 1970s on the theoretical foundations of multiobjective decision making.

The 1980s and 1990s witnessed the consolidation and development of a great number of interactive methods. Most of these methods are oriented toward negotiation or multiple decision makers and multicriteria decision support systems.

Multicriteria analysis has been used since its emergence to deal with spatial decision problems. The Þrst works involving GIS-based multicriteria analysis where published in the late 1980s and the early 1990s. Currently, there are a number of relatively important articles devoted to GISbased multicriteria analysis that have been published [10].

Scientific Fundamentals

General Schema of Multicriteria Analysis Methods

Different multicriteria analysis methods are available in the literature [4]. An excellent online bibliography of multicriteria analysis and its applications is available at http://www.lamsade.dauphine.fr/mcda/biblio/. Multicrite-

ria methods are commonly categorized as discrete or continuous, depending on the domain of alternatives. The former deals with a discrete, usually limited, number of pre-speciÞed alternatives. The latter deals with variable decision values to be determined in a continuous or integer domain of inÞnite or large number of choices. Several authors classify them as (i) multiple attribute decision-making (MADM), and (ii) multiple objective decision-making (MODM). In this presentation, the discrete/continuous classiÞcation is chosen since it is in accordance with the conventional representation of data in GIS (vector vs. raster) and it is more general than the MADM/MODM classiÞcation. Figure 1 gives the general schema of discrete and continuous multicriteria methods that will be brießy described in the following two paragraphs.

Discrete Methods The Þrst requirement of nearly all discrete techniques is a performance table containing the evaluations or criteria scores of a set of alternatives on the basis of a set of criteria. The next step consists of the aggregation of the different criteria scores using a speciÞc decision rule (or aggregation procedure). It takes into account the decision maker’s preferences, generally represented in terms of weights that are assigned to different criteria. The aggregation of criteria scores permits the decision maker

to make a comparison between the different alternatives on the basis of these scores. The aggregation procedures represent the identities of the multicriteria analysis techniques. The discrete methods are usually categorized based on their aggregation procedures into two different families:

(1) outranking relation-based decision rules, and (2) utility function-based decision rules.

The uncertainty and fuzziness generally associated with any decision situation require a sensitivity/robustness analysis enabling the decision maker(s) to test the consistency of a given decision or its variation in response to any modiÞcation in the input data and/or in the decision maker preferences.

Continuous Methods The starting point of most continuous methods are a set of constraints and objective functions. The former set contains inequalities which reßect natural or artiÞcial restrictions on the values of the input data. This means that feasible solutions are implicitly deÞned in terms of these constraints.

For continuous methods, the decision makerÕs preferences generally take the form of weights that are assigned to different objective functions. They may also be represented as target values that should be satisÞed with any feasible solution. The decision maker should also indicate, for each objective function, its direction of optimization,

that is maximization or minimization. No other information than the weights and these directions of optimization are required to deÞne the set of non-dominated solutions. This set contains solutions that are not dominated by any other one.

Generally, local and interactive aggregation algorithms are used to deÞne the feasible solutions set. This permits the combination of the decision maker preferences and the computer to solve the decision problem, using methods that alternate calculation steps and dialogue steps. In reality, the local and interactive algorithms require the decision maker preferences to be expressed progressively throughout the resolution process. The decision maker preferences, however, may be expressed a priori (i. e., before the resolution process) or a posteriori (i. e., after the resolution process).

In many practical situations, the decision maker is called upon to relax some of its constraints in order to guarantee that the set of feasible solutions is not empty or, simply, to test the stability of the results.

Spatial Multicriteria Decision Making

A brief description of spatial multicriteria decision making concepts is provided in the following. In the rest of this entry, F = {1,2,· · · ,m} denotes the set of the indices of m evaluation criteria g1, g2, · · · , gm. Accordingly, gj (j F) is the evaluation criterion number j.

Spatial Decision Alternatives Decision alternatives can be deÞned as alternative courses of action among which the decision maker must choose. A spatial decision alternative consists of at least two elements [9]: action (what to do?) and location (where to do it?). The spatial component of a decision alternative can be speciÞed explicitly or implicitly [10]. The second case holds when there is a spatial implication associated with implementing an alternative decision.

The set of spatial decision alternatives may be discrete or continuous. In the Þrst case, the problem involves a discrete set of pre-deÞned decision alternatives. Spatial alternatives are then modeled through one or a combination of the basic spatial primitives, namely point, line, or polygon. The second case corresponds to a high or inÞnite number of decision alternatives, often deÞned in terms of constraints. For practical reasons, the set of potential alternatives is often represented in a ÒdiscretizedÓ form where each raster represents an alternative. Alternatives may be constructed as a collection of rasters.

Evaluation Criteria In the spatial context, evaluation criteria are associated with geographical entities and relationships between entities, and can be represented in the

form of maps. One should distinguish a simple map layer from a criterion map. In fact, a criterion map models the preferences of the decision maker concerning a particular concept, while a simple map layer is a representation of some spatial real data. A criterion map represents subjective preferential information. Two different persons may assign different values to the same mapping unit in a criterion map.

Standardization The evaluation of alternatives may be expressed according to different scales (ordinal, interval, ratio). However, a large number of multicriteria methods (including practically all the utility function-based methods) require that all the criteria are expressed in a similar scale. Standardizing the criteria permits the rescaling of all the evaluation dimensions between 0 and 1. This allows between and within criteria comparisons.

There are a large number of standardization procedures. In all procedures, standardization starts from an initial vector (gj (a1), gj (a2),· · · , gj (am)) to obtain a standardized vector

(r1j, r2j,· · · , rmj) with 0 ≤ rij ≤ 1; j F and i = 1,· · · ,n (n is the number of alternatives). The most used standardiza-

tion procedure in GIS-based multicriteria decision making is the linear transformation procedure. It associates with each alternative ai and for each criterion gj the percentage of the maximum over all alternatives:

rij = gj(ai) , i = 1, . . . , n ; j F . maxi gj(ai)

Pre-Analysis of Dominance In the absence of any preferential information, the only possible operation on the performance table is to eliminate the dominated alternatives. Let a and b be two alternatives from A. The alternative a dominates the alternative b in respect to F, noted as a b, if and only if:

gj(a) ≥ gj(b) ; j F ,

with at least one strict inequality. Then, an alternative a from A is said to be efficient, admissible or Pareto optimal if and only if there is no other alternative b in A such that: b a.

Criteria Weights Generally, in multicriteria problems the decision maker considers one criterion to be more important than another. This relative importance is usually expressed in terms of numbers, often called weights, which are assigned to different criteria. These weights deeply inßuence the Þnal choice and may lead to a non-applicable decision mainly when the interpretations of such weights are misunderstood by the decision maker.

In the literature, many direct weighting techniques have been proposed. When a simple arrangement technique is used, the decision maker sets the criteria in an order of preference. The cardinal simple arrangement technique involves each criterion being evaluated according to a preestablished scale. Other indirect methods are also available such as the interactive estimation method. There are also relatively complex weight assignment techniques such as the indifference trade-offs technique [7] and the analytic hierarchy process (AHP) [13].

Preference Structure and Preference Parameters

When comparing two alternatives a and b, the decision maker will generally have one of the three following reactions: (i) preference for one of the two alternatives, (ii) indifference between the two alternatives or (iii) impossibility to compare the alternatives. These situations are generally denoted as follows: (i) aPb if a is preferred to b (bPa if it is the opposite), (ii) aIb if there is indifference between a and b, and (iii) aRb if there is an incomparability. The binary relations of preference P, indifference I, and incomparability R are respectively the sets of tuples (a,b) such that aPb, aIb, aRb. It is generally admitted that I is reßexive and symmetric, P is asymmetric, and R is irreßexive and symmetric. The three relations (I,P,R) constitute a structure of preference over A if and only if they have the properties mentioned above and only one of the following situations holds [14]: aPb, bPa, aIb, aRb.

Preference models require the deÞnition of one or several thresholds, called preference parameters. The most commonly used preference parameters are the indifference, preference and veto thresholds. These three parameters are used essentially within the outranking relation-based decision rules. The Þrst two parameters are for modeling imprecision and uncertainty in the decision makerÕs preferences. The latter is often used to compute the discordance index.

Decision Rules To compare alternatives in A, it is necessary to aggregate the partial evaluations (i. e., with respect to each criterion) into a global one by using a given decision rule (or aggregation procedure). As mentioned earlier, within the discrete family, there are usually two aggregation approaches: (i) utility function-based approach, and (ii) outranking relation-based approach. The basic principle of the Þrst family is that the decision maker looks to maximize a utility function U(a) = U(g1(a), g2(a),· · · , gm(a)), aggregating the partial evaluations of each alternative into a global one. The simplest and most often used utility function has an additive form: U(a) = j F uj (gj(a)); where uj are the partial utility functions. Within this form, the preference P and indifference I binary relations are deÞned for two alternatives a and b as follows:

aPb U(a) > U(b) and aIb U(a) = U(b) .

In contrast with the Þrst family, the second one uses partial aggregation procedures. Different criteria are aggregated into a partial binary relation S, with aSb used to indicate that Òa is at least as good as bÓ. The binary relation S is called an outranking relation. The most well known method in this family is ELECTRE (see, e. g., [4]). To construct the outranking relation S, for each pair of alternatives