1. Description of the ongoing project

The proposal described below is based on 3 ongoing grants:


1.1. Project nr 1: EASE - Emission Abatement Strategies and the Environment

The EASE project is an interdisciplinary project funded by the European Commission under the Programme for Cooperation in Science and Technology. It has involved research teams from the Czech Republic (Charles University in Prague, and the Institute of Landscape Ecology in Ceskie Budejovice), Poland (Warsaw University of Technology and the Technical University of Wroclaw), and Imperial College in the UK which also co-ordinated the work. Total support 500 000 ECU (Warsaw University of Technology 60 000 ECU). Period of project realisation 1.04.1994 - 31.03.1997.

1.1.1. Present state of knowledge EASE is an interdisciplinary study of environmental damage due to sulphur emissions in the Black Triangle on the borders of Poland, the Czech Republic and the former East Germany. Project began during development of the second sulphur protocol under the Convention on Long Range Transport of Air Pollutants (CLRTAP) UN Economic Commission for Europe (UN ECE). In order to derive future emission ceilings for the different countries of Europe to reduce acidification an integrated assessment was adopted. This brought together information on the emissions of sulphur dioxide and potential abatement measures and their costs, and combined it with environmental data. Critical loads of sulphur have been used as a measure of environmental capacity.

1.1.2. Objectives of the proposed research As the Black Triangle is one of the most polluted regions in Europe, the EASE project was aimed at a more critical look at sulphur dioxide emissions and their transboundary transport in the Black Triangle region, taking the approach used by UN ECE in developing the second sulphur protocol as a starting point. The emphasis have been on protection of natural ecosystems, especially forests.

1.1.3. Significance of the proposed research and its expected achievements The work has involved an interdisciplinary team of scientists undertaking both field work on forest health and atmospheric chemistry, and computer modelling studies and GIS (Geographical Information systems). The more fundamental experimental science has gone beyond the rather simplified representations of reality within the models, and helped to indicate the validity and limitations of the latter.

1.1.4. Technical description At Warsaw University of Technology the following tasks has been realised: sulphur dioxide emission inventory for Poland, development of an Eulerian grid regional air pollution model , calculations of sulphur concentrations and depositions for the area of Poland, the Czech Republic and Germany, development of clustering method for area valorization model, calculations of area valorization indexes for the area of Black Triangle region, estimation of emission abatement costs for chosen emission sources, assessment of environmental/population risk of given control strategy and minimisation of environmental/population risk in cost optimal way.

1.1.5. Organisation and Management In Warsaw project is situated in the Institute of Environmental Engineering Systems at Warsaw University of Technology and co-ordinated by Dr Katarzyna Juda-Rezler. Overall project co-ordinator is Dr Helen ApSimon from the Imperial College in the UK. Progress reports are prepared each half-year. Also six monthly progress meetings have been organised.





1.2. Project nr 2: Grant KBN No 8 T 11C 010 10 - Applications of evolutionary algorithms to path planning and navigation problems

The project aims at applications of evolutionary techniques for modelling the behavior of a mobile robot in partially unknown environments. In particular, the project investigates possibilities of incorporating "genetic memory" in evolutionary algorithms, i.e., possibilities of representing redundant information in a chromosome. Such an approach might be very useful in problems where the optimum changes over time, i.e., where the information about the objective function is updated during the search process, thus influencing the search process itself. Thus the results of this research might be of importance for many application areas, e.g., optimisation of noisy objective functions (where there are incomplete data about the objective function or designing of evolutionary algorithms to path planning and navigation problems in partially known environments (where the planning phase and the execution phase must be merged). Period of project realisation: 1.01.96 - 31.12.97 . Total support: 32 500 z³ (9129 ECU).

1.2.1. Present state of knowledge The problem of optimising noisy objective functions has not been studied extensively so far. However, in most practical, real-world applications, this is just the case! It seems that evolutionary techniques (as adaptive methods) are ideally suited for such problems, since these algorithms just adapt to changes in the environment (i.e., the objective function) without any need for re-starting the algorithm. In the current proposal we have been investigating possibilities of including "genetic memory" within the evolutionary system. The conducted several experiments; these experiments were done in one particular domain: a robot navigating in a partially known environment. The first results confirmed the huge potential of introducing genetic memory into evolutionary processes for non-stationary objective functions.

1.2.2. Objectives of the proposed research The principal investigators of this project have been analysing a few (relatively new) aspects of evolutionary algorithms:

• applications of multi-chromosomal structures,
• optimisation of noisy and non-stationary objective functions,
• the issue of infeasible individuals with a valuable genetic code,
• problem of incorporation of problem-specific knowledge into evolutionary algorithms, in particular, problem-specific genetic operators,
• adaptive (and self-adaptive) capabilities of evolutionary algorithm on the basis of the current information about the environment and the current position of the robot.

1.2.3. Significance of the proposed research and its expected achievements Most of the current approaches for mobile robot navigation suffer from many disadvantages:
• high computational cost. There is an experimental evidence that the complexity of an algorithm grows exponentially with the number of degrees of freedom of the robot,
• low flexibility of the algorithm in cases where a change in the environment is detected,
• inability of dynamic planning, i.e., merging the global planning (which prevents the algorithm from convergence to a local optima) with reactive planning, which precesses the information from the robot's sensors.
It is clear that the proposed project, which represents a new approach to the above problem, requires non-trivial integration of various research issues; these include:
• the integration of algorithms for global and reactive planning,
• various types of representing problem-specific knowledge and reasoning in uncertain environment,
• new aspects of evolutionary computation: multi-chromosomal structures and genetic memory,
• retrieval of the optimal path in the planning problems; the speed of the retrieval process versus the quality of the path,
• methods of adapting a path to discovered changes in the environment (general adaptation mechanisms).
Thus the project aims at applications where the objective function is non-stationary, i.e., it changes in time.

1.2.4. Technical description The project incorporates evolutionary programming techniques. Generally speaking, evolution program is an evolutionary algorithm which incorporates problem specific knowledge into chromosomal data structures and genetic operators. In this project, standard evolutionary algorithm is extended by the following features:
• introduction of "genetic memory" of an individual in the population as a possibility for providing a quick response to changes in the environment,
• construction of an evaluation function for paths, and the initialization methods for generating initial population for the algorithm,
• self-adaptive capabilities of the algorithm to reduce its execution time to minimum,
• passing important genetic material from parents to offspring,
• various methods of representing individuals and the environment and their influence on the speed and modularity of the algorithm,
• investigation of distributed models of evolutionary algorithms to achieve even greater rate of the speed-up,
• adaptive capabilities of the system; design of the feedback loop from the environment and the current position of the robot into the evolutionary engine.
Two symulators were written (in C for Unix) for mobile robot experiments. The first one is based on evolutionary computation techniques, whereas the second one - on potential field method. The latter system will be used for various comparisons of these approaches (precision, speed, flexibility, adaptiveness, etc).

1.2.5. Organisation and Management The project is realised at the Institute of Computer Science, Polish Academy of Sciences. and chaired by prof. dr Zbigniew Michalewicz.




1.3. Project nr 3: Grant KBN No 8 T 11C 027 10 - Knowledge Discovery in Distributed Databases for Intelligent Query Answering


"Knowledge Discovery in Distributed Databases for Intelligent Query Answering" realized in the grant No 8 T11C 027 10 financed by the State Committee on Scientific Research is integration of several research methodologies created independently in three different research centers, an extended model of intelligent distributed intyelligent system is to be proposed. In this project, a system for discovery of deterministic knowledge, based on experiences of the 49-er system, will present its results in terms of equations or taxonomies. Non-deterministic knowledge will be discovered in form of a bayesian network. The integrative task concentrates around the extension of an Cooperative Query Answering system, that has used only knowledge in terms of rules so far, to make use of knowledge in form of equations, taxonomies and bayesian networks during the process of locally unresolved queries. Elaboration of proper techniques of knowledge transformation between the listed formalisms of knowledge representation. Period of project realisation: 1.01.96 - 31.12.97 . Total support: 229 500 z³ (64466 ECU).

1.3.1. Present state of knowledge The research group presenting this proposal has been working for many years on the problems of knowledge representation and repreesentation transformations. In these area there exists for five years now close cooperation between the Institute of Computer Science of polish Academy of Sciences (ICS PAS) and the Institute of Computer Sciences of Warsaw University of Technology as well as between the AI Foundations Group of ICS PAS and the Department of Computer Science of the University of North Carolina in Charlotte and the Machine Discovery Laboratory of the Computer Science Faculty of the Wichita State University in Kansas. In empirical research, after collecting data and introductory exploration of data the researcher put frequently a hypothesis the checking of which is frequently impossible due to missing values of some attributes. Completing the database from "nature" or from other databases or change of hypothesis formulation by the researcher may porove impossible. However, frequently related data bases exist - samples from the same population, elaborated for different purposes, and possissning partially overlapping set of attributesd and containing the missing attributes. Such situastions are frequent in data bases collected by different medical centers.

1.3.2. Objectives of the proposed research The system realized within the grant presents methodology of answering unresolvable queries by an intelligent sistributed information system. An unreachable query should be understood as the one query forwhich there exists at least one non-local value of an attribute for a given node. Applicstion of knowkedge discovery systems in databases for intelligent query answering is particularly justified as the discovered knowledge can be used to create computational procedures used withi the framework of a query to supply unknown values of an attribute. Knowledge discovery in databases can be achieved using various methods. Within this project two methods are to be developed in parallel: (1) bayesian networks and (2) 49er. In this way advantages of both methodologies will be exploited and interesting comparative material will be collected.
1.3.3. Significance of the proposed research and its expected achievements The realization of the project opens new prospectives for cooperation of systems working so far in separated domains like knoweledge discovery, probabilistic reasoning, query answering. The project offers common base enabling to communicate between systems from the doains mentioned, showing how results of one system may be exploited in another system.

1.3.4. Technical description Each node of the system is equipped with a knowledge system (relational database and knowledge base), a system for communication among the nodes and a system for querries answering. The knowledge base contains equations representing numerical dependencies among the attributes used in the database as well as rules and a causal network describing semantical relationships among the attributes. In the project a number of theoretical problems is solved. First of all a new algorithms and tools for the generation of the causal network are proposed. Next a methodology for converting the network into a set of production rules is given. Finally some problems concerning logical integrity of the knowledge base are discussed and an extension of the querry language (allowing numerical querries) is proposed. Causal network is nothing but a graphical knowledge base. It can be generated with the help of deterministic algorithms (producing trees and their extension - polytrees) or with the help of probabilistic algorithms, particularly - genetic algorithms. This last approach allows to produce "optimal" (in a sense prespecified by a user) graphical structures. Having the network and using implemented algorithms of local computations we are able to solve problems belonging to three categories: (a) finding a most plausible value of an attribute knowing the values of a group (specified by the user) of attributes, (b) querry answering, and (c) finding most probable explanation of a given observation. Another problem is answering unresolved queries. To solve it, a node sends the query to the remaining nodes of the distributed system. Answers to this query are send by appropriate nodes in the optimal form. We attempt to extend this idea by the production rules obtained from the causal network as wel as by the numerical equations generated by the 49er system. This way a portion of knowledge expressed in a mixed form (rules+equations) allows to replace the unreachable values of attributes by the locally reachable terms. Since each node of the distributed system can be queried simultaneously by many other nodes we must solve the problem of an effective communication among the nodes of the system. This problem is supposedly solved by using genetic algorithms.

1.3.5. Organisation and Management The project is placed in the Institute of Computer Science, Polish Academy of Sciences and chaired by dr. Maciej Michalewicz. 2.

2. Description of the proposed CRIT2 extension

The main purpose of the project is to investigate possibilities of applying evolutionary computation techniques (extended by genetic memory structures) for a particular optimization process, which aims at reduction of pollution in the area of the whole Poland. A new system would be capable to include all major sources of pollution (70 sources, 300 stacks) as well as the current weather conditions. The outcome of the system would indicate the recommended level of produced energy for each particular pollution source; this is because Poland has an over-supply of the produced energy with respect to the demand. The name of this system is EROS: Evolutionary Real-time Optimisation System for Power Control. The resulting set of recommended levels of production for pollution sources should be generated in a continuous manner, and, as indicated earlier, the process should take into account the current weather conditions and the current energy demands.

2.1. Objectives of the proposed research extension During realisation of EASE project the integrated assessment models have been applied to illustrate where environmental considerations may influence abatement policies. The sensitivity of different environments have been incorporated using valorization index, which represent area cover sensitivity to the sulphur dioxide concentration. Valorization method used should be further developed and extended. Also area of application will be extended to the area of whole country (Poland). Processes of air pollution transport on regional scale are governed by a multilayer, dynamic Lagrangian model, based on numerical solution of the advection-diffusion equations, considered with the respective boundary and initial conditions. The approach is oriented at assessment of environmental effects of sulfur oxides emissions, resulting from power generation related combustion, industrial production processes and domestic burning. The implementation can also be extended to consideration of other types of air pollution, such as dust, nitrogen oxides, etc. Dry and wet deposition processes as well as basic transformations of the polluting species are taken into account. The wind-field in the area is preprocessed by a specialised wind generator, where the vertical profile (wind shear), influece of topography, aerodynamical roughness and urban heat-island effects are considered. As an extension of the approach to the national scale, a single-layer (averaged over the mixing height) trajectory model can be considered. The proposed system will incorporate problem-specific knowledge on controlling emission sources. To facilitate this incorporation, an expert system will be built. The set of rules handled by this expert system will control decision-making process of the real-time optimizer; these rules will be created on the basis of generally accepted local and global control strategies. For the problem discussed earlier in this proposal, we plan to apply evolutionary optimization techniques extended by the concept of genetic memory. All three models and systems (1. the valorisation system, 2. the air pollution transport system based on Lagrangian model and 3. the expert system) will be merged together and the results of their co-operation will constitute the input for the evolutionary optimizer. An important issue considered at this stage is the real-time operations of such evolutionary system.

2.2. Significance of the proposed research and its expected achievements The knowledge about environmental sensitivity to air pollution is fundamental. Species sensitivity to sulphur dioxide concentrations will be adopted after recommended by UN ECE critical levels of SO2 for different receptors. Also population sensitivity to SO2 concentration will be investigated. The solutions which emerge from this research project will constitute an important milestone for many experimental techniques. The overall result will consist of
• an optimization system of a great practical importance, and
• of a methodology for developing evolutionary systems for problems with non-stationary objective functions.
Additionally, it is hard to overestimate the results of the proposed optimization system when applied to the described problem of controlling pollution.

2.3. Technical description The tasks will be the following: establishment of modelling grid covering Poland, collection of needed input data for the area of Poland - population data as well as land-use data (8 different land-use categories), conversion of the original data to the project grid, development of new valorization method, valorization of the area of Poland. The input database characterizes the structure of the domain, the inventory of emission field, and the meteorological forecast - entered as a sequence of the consecutive synoptic situations. Two options of temporal scale are available in model simulation: short-term forecast (up to 96 hrs) and long term forecast (year- or season-averaged). Space discretization step depends on the area dimensions and the computer limits of the discrete problem. Time discretization interval for the input (meteo) data can be assumed 6hrs or 12hrs. The model can be utilized in decision support routines, for air quality forecasting, analysis and planning, searching for the emission abatement strategies or real-time emission control. For the problem discussed earlier in this proposal, we plan to apply evolutionary optimization techniques extended by the concept of genetic memory. This approach will require additional research on the effectiveness of various methods for memory organization, on types of stored information, on strategies of storing and deleting information from the memory, as well as on methodology for incorporating boundary conditions of the objective function. This optimization package will work in a real time. It would be also necessary to introduce several non-trivial modifications and take care of compatibility of this software package.

2.4. Organisation and Management The project will be placed at the Institute of Computer Science, Polish Academy of Sciences and will be supervised by prof. dr Zbigniew Michalewicz.