Petr Šauer
email: sauer@vse.cz

Petr Fiala
email: pfiala@vse.cz

Antonín Dvořák

Water Pollution Reduction: Reverse Combinatorial Auctions Modelling Sup porting Decision-Making Processes

Keywords: environmental protection, environmental management, decisionmaking, CRAB software, water pollution, combinatorial auctions

This paper presents a model that contributes to finding cost-effective solutions when making decisions about building wastewater treatment plants in the planning process defined in the Framework Directive 2000/60/EC of the European Parliament and of the European Council. The model is useful especially when construction and operation of joint wastewater treatment plants is possible for several (neighbouring) municipalities, where a huge number of theoretical coalitions is possible. The paper presents the model principles for one pollutant and for multiple pollutants, describes the CRAB software used for computing the optimal solutions and presents selected applications. It concludes that the computations can contribute directly to decision-making concerning environmental protection projects and also serve for calculating background models for economic laboratory experiments in the area.

Introduction

There are still situations in the area of surface water quality that require solutions in the Czech Republic and other advanced countries, in spite of a noticeable improvement since the 1980s, as municipalities with more than 2000 equivalent inhabitants have had to ensure sewerage and wastewater treatment by the end of 2010 pursuant to the implemented Framework Directive 2000/60/EC of the European Parliament and of the Council [1]. It is important to respond to the need for timely adaptation to climate change in progress, secure drinking water sources, increasing demands for recreational water quality as a consequence of improving living standards, enhancements in nature protection, and creation of conditions for further scientific and technical development in water quality improvement. Planning for river basins consists of a series of decisions leading to the implementation of appropriate water protection projects. A new planning process concerning waters is defined in the Directive 2000/60/EC, establishing a framework for Community action in the field of water policy. This Framework Directive has been progressively transposed into the Czech legal system by a series of legislative standards. This fact has brought about a significant change to the whole system since 2004, and new national documents in the area of water management planning have had to be developed. Planning concerning waters has become a systematic policy area managed by the national government. Updates of the plans are made every 6 years.

Our modelling support relates to so-called sub-catchment plans. They define goals in protection of water as an environmental component (i.e., environmental goals) to be achieved in water bodies by 2015 or in the next two six-year planning periods. New functional forms of coordination of involved parties are being sought, i.e., not only those responsible for developing the plans but also other stakeholders, including professional and non-governmental organizations.

Increasing emphasis is placed on the economic efficiency of proposed and implemented measures, not only due to the current economic situation. This is particularly true in cases where a subsidy from public sources is offered to relevant projects (at the national or EU level). There is a wealth of literature dealing with finding costefficient solutions in wastewater treatment.

One of the ways of ensuring cost-effective solving of surface water quality problems is to find technical projects/designs shared by multiple polluters (so-called "coalition designs"). A new strategy is being promoted: reducing the risks caused by increasingly smaller sources. The specific feature of this strategy is that it allows implementation of so-called coalition projects, i.e., joint projects implemented by multiple polluters. A typical example is the construction and operation of joint wastewater treatment plants for several (neighbouring) municipalities.

Auctions are important market mechanisms for the allocation of goods and services. Reverse combinatorial auctions serve as a theoretical framework for the approach presented in the paper. Combinatorial auctions [START_REF]Combinatorial Auctions[END_REF] are those auctions in which bidders can place bids on combinations of items, so-called bundles. The advantage of combinatorial auctions is that the bidder can express his preferences more fully. It is possible to formulate single-sided combinatorial auctions, forward auctions and reverse auctions. In forward auctions, a single seller sells resources to multiple buyers. In reverse auctions, a single buyer attempts to source resources from multiple suppliers.

The paper intends to demonstrate the possibilities of model support to this decision-making process in two areas: (i) model support to finding a cost-effective solution to a given task of reducing pollution by a specified key pollutant. A typical example is the task of reducing phosphorus emissions to a certain level to reduce eutrophication in surface waters; (ii) and model support to decision-making, which includes multiple criteria. The CRAB software [START_REF] Fiala | CRAB -CombinatoRial Auction Body Software System[END_REF], which makes it possible to compute results for quite complex situations, is described, followed with a presentation of selected applications. Based on the documents elaborated within the first analysis of the problem, it is decided if the solved problem is complex and requires optimization with using a combinatorial auction model. If yes, input data are collected and verified and it is decided whether they are of sufficient quality for the modeling. If yes, the optimal solution is calculated and is commented within the draft plan by experts and stakeholders. In the case the plan is approved, the stages of Environmental impact assessment procedure, the plan final approval and its publication follow.

The calculation model supporting the decision-making process is shown in steps 3-7 in particular. For a more detailed description of the whole process, see the Methodology for economic and environmental optimization of reducing pollution in watercourses approved by the Czech government [START_REF] Šauer | Methodology for economic and environmental optimisation of reducing pollution in watercourses[END_REF].

3

Models for Calculating a Cost-Effective Solution with Environmental Criteria

Model with One Environmental Criterion

We propose to use a model for reverse combinatorial auctions searching for a costeffective combination of projects to reduce pollution. We assume that one environmental indicator is reduced to the desired level for all the projects. Therefore, it is possible to focus on the cost side of the problem. We present a reverse combinatorial auction [START_REF]Combinatorial Auctions[END_REF] of projects with one authority and several polluters. Let us suppose that m potential polluters S 1 , S 2 , ..., S m offer a set R of r projects, j = 1, 2, …, r, to one buyer A.

A bid made by the polluter S h , h = 1, 2, …, m, is defined as

b h = {C, c h (C)},
where C ⊆R is a combination of pollution sites, and c h (C) is the price offered by the polluter S h for the combination C.

The objective is to minimise the buyer's costs given the bids made by polluters. Constraints establish that the procurement provides at least a set of all items.

Bivalent variables are introduced for the model formulation: y h (C) is a bivalent variable specifying whether the combination C is bought from the polluter S h (y h (C)= 1).

The reverse combinatorial auction can be formulated as follows

1 m h= ∑ C R ⊆ ∑ c h (C)y h (C)→ min subject to 1 m h= ∑ C R ⊆ ∑ y h (C) ≥ 1, ∀ j∊R,
(1)

y h (C) ∊ {0,1}, ∀ C ⊆ R, ∀ h, h = 1, 2, …, m.
The objective function expresses the costs. The constraints ensure that the selection of projects includes all the pollution sites.

See section 5 for an illustration of this approach.

Model with Multiple Environmental Criteria

The basic model (1) can be extended for situations with multiple environmental criteria. We assume k environmental indicators, i = 1, 2, …, k. A bid made by the polluter S h is extended by e ih (C) is the reduction in the environmental indicator i offered by the polluter S h for the combination C.

The reduction in the environmental indicator i in the whole region is given by the limits E i , i = 1, 2, …, k. Then the environmental aspect of the problem can be modelled by a set of constraints

e ih (C)y h (C) ≥ E i , i = 1, 2, …, k. (2)
In situations without limits, the problem can be extended in a multi-objective version of the problem (1) with a set of added objective functions

1 m h= ∑ e ih (C)y h (C)→ max, i = 1, 2, …, k.
(

The multi-objective programming problem can be solved by corresponding approaches.

See section 5 for an illustrative example of this approach.

CRAB -CombinatoRial Auction Body Software System

A need for an input problem generator arose during our research into combinatorial auctions. The CATS [START_REF] Leyton-Brown | Towards a Universal Test Suite for Combinatorial Auction Algorithms[END_REF], software developed by Stanford University can be used for combinatorial auction problems, but it does not meet the specific needs of our problem. To satisfy our needs, we have developed our own software tool: CRAB [START_REF] Fiala | CRAB -CombinatoRial Auction Body Software System[END_REF]. This tool has several advantages comparing CATS, namely:

• fast problem generation,

• combinations are generated in a more predictable way,

• combinations are generated only in given subset of all items,

• CSV is used as the primary data format,

• fine-grained control over problem generated,

• built-in linear problem solver,

• multiple output formats.

This tool is implemented in Ruby. We choose Ruby for performance reasons, mainly for its dynamic, agile nature with enables us to quickly experiment with different approaches.

Overview

A combinatorial auction problem is given by the number of buyers and the number of all feasible combinations of goods -bundles. Prices of bundles -bids -and a budget are also needed for each buyer. The number of goods is read in the vector form where the number of vector components (comma separated) is equal to the number of bundles. Each vector component corresponds to the number of goods in the bundle.

All the combinations of goods in each bundle (except the empty set) are generated in the first phase. This step is done for every bundle. In this way, all the bundles are generated. The list of these bundles is saved in a file (*.csv) -one bundle per rowand one column is prepared for each buyer. The first row contains a column label and the second row is given to the buyer's budget.

The user of the CRAB software can load the CSV file into a text editor or a spreadsheet and fill in the bids (i.e., the price offered by the buyer for a particular bundle) and budgets for each buyer. If the user uses CRAB only for tests, he/she can use automatically generated prices and budgets. In both cases, the final file has to be saved in the CSV format again.

In the second phase, the file is transformed into a binary programming problem. The bundles correspond to variables and the bids correspond to prices of the objective function that is being maximized. The problem consists of automatic constraints for each good (each good can be sold only once) and each buyer (a buyer cannot exceed his budget). The user is free to change the automatically generated constraints and remove or add (for example non-typical) constraints. All the data have to be saved in the CSV format again.

Finally, the problem can be passed to the built-in binary programming solver to find out the optimal solution for the given combinatorial auction. If so, the problem is transformed into a form with minimizing the objective function with non-negative prices and all the constraints in the "less or equal" form. Afterwards, the transformed model is passed to the Balas algorithm [START_REF] Balas | An Additive Algorithm for Solving Linear Programs with Zero-one Variables[END_REF]. The CRAB architecture gives a possibility to extend the system, especially about the implemented models and algorithms.

Practical Use

CRAB can operate in two modes: (i) an interactive mode, and (ii) a command line mode. CRAB can be run in an interactive mode, which means that the user is prompted for data interactively. Contrary to interactive mode, the CRAB can operate in a command line mode, which means that all input data as well as all options have to be supplied on the command line.

The CRAB can generate combinatorial problems. The principal command is:

ruby crab.rb --output <outfile> generate --buyers <nb> -bundles <bundlespec>

where <nb> is the number of buyers (non-negative integer value) and <bundlespec> is a vector specifying the number of items in each bundle. The number of bundles is determined by the dimension of the vector. The vector should be entered as a comma-separated sequence of positive integer values with no spaces in between. CRAB can also generate random prices for each bundle as well as a budget for each buyer.

The generated file is an ordinary CSV (Comma Separated Values) file and thus editable by almost every spreadsheet application. The first row contains only column labels and no data. The second row contains a budget for each buyer. The rest of the rows specifies bids of bundles given by each buyer.

The first two columns contain only labels and no data. The first column denotes the bundle, the second one denotes the particular goods combination within the bundle. A bundle is denoted by the ID of the first and last goods item in the bundle; the combination is denoted by a minus-separated list of goods IDs. The following columns contain the bids made by the buyers.

Transforming Combinatorial Auction to Binary Programming Problem

Once the combinatorial auction is generated, it can be transformed to the form of a binary programming problem and passed to the binary programming solver afterwards. The principal command for the combinatorial auction transformation is:

./ruby crab.rb --output <output file> transform --bids <input file>

where <input file> is the CSV file specifying the combinatorial auction. The form of the input file must be the same as the output of the generate command. Optionally, the user can use the --format option to specify the output format. CRAB currently supports two output formats: (i) CSV (which is the default) and (ii) XA. The first one is the one used by the built-in solver; the latter can be passed directly to the XA integer solver [START_REF] Xa | Linear Optimizer System[END_REF].

The following command will transform the file bids.csv into a binary programming problem, saving the output to a file named problem.csv using the CSV format.

./ruby crab.rb --output problem.cvs transform --bids bids.csv

The following command will create a binary programming problem specification file as used by the XA solver:

./ruby crab.rb --output problem.lp transform --format xa --bids bids.csv

4.4

Solving CRAB contains a built-in binary programming solver based on Balas's method [START_REF] Balas | An Additive Algorithm for Solving Linear Programs with Zero-one Variables[END_REF]. The form of the input file must be the same as the output of the transform command using the CSV format. The CRAB tool also provides a few options to control the Balas algorithm. The first option controls the overall strategy to walk through the state space. Two strategies are available: depth-first (specified by the --depth-first option) and breadth-first (which is the default, specified by the --breadth-first option).

The second option deals with branching logic. If --one-first is specified, then the one-filled branch is tried first, if --zero-first is specified, the zero-filled branch is taken first. The one-first strategy is the default. Based on a few experiments, breadth-first combined with one-first gives the best results (measured by the number of iterations required to solve a particular problem).

The output of the built-in solver is as follows:

As the solver is solving the problem, it prints some statistical information: the total number of partial solutions in the queue, the delta from the last output and the values of a few other internal variables. After the solver finishes the computation, it prints out the number of iterations made, the solution and the value of the objective function.

5

Case Studies Results

Case with Single Environmental Criterion

The Rozkoš recreational lake in Eastern Bohemia serves as a practical example of application where a single environmental criterion was introduced. Phosphorus pollution reduction has become an issue, since it has a significant impact on the water quality for recreational purposes. It was taken as the most important (single) environmental criterion in the case. The experts evaluated investment costs for: Vector[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], Z = 5203

Iteration
• all of the 20 individual projects (i.e., a situation where each of the municipalities would build its own wastewater treatment plant); they were coded as A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, D4, E1, E2, E3, E4; • all of the 14 "promising" coalition projects, i.e., costs of such coalition projects that cannot be excluded from the analysis beforehand for technical, economic, environmental, morphological, political or other reasons; they were coded as A1+A2, A3+A4, A3+A4+B1+B3, B2+B3, B2+B3+B4+C2, B4+C1+C2, C3+C4, C3+C4+D2, C3+C4+D1+D3, D1+D2+D3, D1+E1, D4+E2, D4+E2+E3.

The CRAB software was used. The calculated optimal solution is as follows:

• 7 individual projects: B1, C1, C3, C4, E1, E3, E4

• 3 two-member coalitions: A1 +A2, A3 + A4, D4+ E2

• 1 three-member coalition: D1 + D2 + D3

• 1 four-member coalition: B2 + B3 + B4 + C2

Total costs of coalition solutions = CZK 720,600 thousand Total costs of individual solutions = CZK 1,212,400 thousand Cost saving if the coalition solutions are applied = CZK 491,800 thousand; i.e., about 40%.

See the simplified case in section 5.2 for the design of the mathematical model of this exercise.

Case with Multiple Criteria

An ideal case, close to a practical situation, has been created and called the Powder Brook case. It is an illustrative application to a case of a small river basin with 4 municipalities polluting a brook with one tributary. In spite of some necessary simplifications, the authors have striven for maximum approximation to the real situation in one of the tributaries to the Elbe river basin in Bohemia (Czech Republic). Environmental criteria entering the analysis in this case were adopted from pollution production monitored pursuant to Government Regulation No. 61/2003 Coll. [8], and ČSN 75 6401 [START_REF]ČSN 75 6401 Sewage treatment plants for more than 500 of population equivalents[END_REF], which specifies the daily production of BOD 5 at 0.06 kg/EI, P total at 0.0025 kg/EI, N total at 0.015 kg/EI, and N-NH 4 + at 0.011 kg/EI. These environmental parameters were adopted and modelled as a set of constraints (2) as described in section 3.2.

The mathematical model of the exercise for the analysis is as follows: The optimum solution to this exercise: y A = 0, y B = 0, y C = 0, y D = 0,y AB = 0, y BC = 0, y BD = 0, y CD = 0, y ABC = 0, y BCD = 0, y ABCD = 1.

N = 6500 y A +
One coalition project -ABCD -should be implemented.

The total costs N = CZK 73,000 thousand = saving of CZK 11,500 thousand compared to individual projects (common practice; CZK 84,500 thousand).

The case was very simple (only 4 subjects-municipalities where the presented software is not actually needed) for two reasons: (i) it serves as an understandable illustration of the methodology mentioned above developed by the authors of this paper [START_REF] Šauer | Methodology for economic and environmental optimisation of reducing pollution in watercourses[END_REF]; and (ii) the results served as a background model for economic laboratory experiments, which are mentioned in the discussion. The authors of this paper are currently working on quite sophisticated applications.

Discussion and Conclusion

The calculations using the CRAB software produce very usefully information for support of decision-making of a public authority (government) when finding the cheapest solutions to water pollution reduction in situations where coalition (common) projects exist and experts are able to assess all the important information. The result is a cost-effective solution, which, in complex situations, would be very difficult to find by traditional computational methods.

In reality, especially in situations where the polluters are offered some financial support from public funds (subsidies), there is an information asymmetry between the authority and the polluters. It means that the polluters do not tell the truth about their abatement costs and try to apply for as much as possible from the funds. In such situations, the calculation using the CRAB software can help to calculate the optimal solution for testing the polluters' behavior in the form of economic laboratory experiments. The experiments then test how close or far from the optimal solution the negotiated outcomes are. For more details about these experiments, see [START_REF] Fiala | Application of Combinatorial Auctions on Allocation of Public Financial Support in the Area of Environmental Protection: Economic Laboratory Experiment[END_REF] and [START_REF] Šauer | Environmental negotiation under information asymmetry: a laboratory experiment for coalitions of four parties[END_REF]. In other words, the laboratory experiments can help test alternative institutional settings in the field, including settings where multiple criteria are introduced. See [START_REF] Soukopova | Methodology for the Efficiency Evaluation of the Municipal Environmental Protection Expenditure[END_REF] and [START_REF] Soukopova | Assessing the efficiency of municipal expenditures regarding environmental protection[END_REF] for a costs-effectiveness analysis of public spending on environmental protection when multiple criteria are applied in the Czech conditions. Computing optimal solutions would also be helpful when testing alternative settings with public participation in decision-making. See [START_REF] Koontz | One size does not fit all: Matching breadth of stakeholder participation to watershed group accomplishments[END_REF] and [START_REF] Priscoli | What is public participation in water resources management and why is it important?[END_REF] for a discussion of public participation in decision-making, and [START_REF] Slavikova | Implementing the Public Participation Principle into Water Management in the Czech Republic: A Critical Analysis[END_REF] for a typical Czech research in this area.

Fig. 1 .

 1 Fig. 1. Diagram of the planner's (entire) workflow

  1000: 47 solutions in queue (delta 46) z_f = 25930.0, z = 32702, z_max = 26433.0] Iteration 2000: 123 solutions in queue (delta 76) z_f = 25930.0, z = 32702, z_max = 26807.0] Iteration 3000: 269 solutions in queue (delta 146) z_f = 25991.0, z = 32702, z_max = 26812.0] Iteration 4000: 321 solutions in queue (delta 52) z_f = 27285.0, z = 32702, z_max = 28251.0] Iterations done: 4214 Solution:

  [START_REF] Slavikova | Implementing the Public Participation Principle into Water Management in the Czech Republic: A Critical Analysis[END_REF],250 y B + 29,000 y C + 32,750 y D + 27,750 y AB + 41,750 y BC + 59,000 y BD + 65,000 y CD + 50,000 y ABC + 69,000 y BCD + 73,000 y ABCD → min

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011

Acknowledgement

The paper was developed with the support of the Czech Science Foundation, grant no.13-07036S "Modelling of Negotiations in Environmental Policy under Information Asymmetry".


Robert Power
email: robert.power@csiro.au

Bella Robinson
email: bella.robinson@csiro.au

Lachlan Rudd
email: lachlan.rudd@csiro.au

Andrew Reeson
email: andrew.reeson@csiro.au

Scenario Planning Case Studies Using Open Government Data

Keywords: urban planning, environmental planning, decision support, government data, public transport

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This paper addresses the issue of characterising the demand for community services, and presents a framework for evaluating existing service locations in terms of their accessibility by public transport and ability to meet demand. To demonstrate the approach, we fit simplistic models to show the types of policy enhancing results that are possible. The main objective is to encourage government to push more data into open access; then more complex models could be fit to the actual datasets. The simplistic models we use show the results that are possible and highlight the power of the mapping tool for policy makers to interpret large amounts of data. This approach can be applied to a range of services. Here we demonstrate its applicability using two case studies drawing on publicly available datasets. The first focuses on government shopfronts (used in Australia for the delivery of welfare and other government services), and the second looks at environmental services in the form of urban parks.

The framework allows users (modelers, decision-makers or other interested parties) to explore and evaluate scenarios using an interactive map-based website. This exploration allows the user to define appropriate parameters to the decision making model. The model results are then computed in a database to produce the final results which are made available on the map-based website.

The demand for services varies across the community. This demand can be categorised based on the expected community need. Different categorisations define scenarios to help assess services which form the basis of the decision making model. An example of a service is a school, shopping centre, swimming pool, playground, government service centre or shopfront. The community need for these services varies. Some services will be needed by the general public, but will be used more by some than others; for example a shopping centre or swimming pool. Other services will predominantly be used by specific community subgroups; for example schools are used by families with school aged children.

The aim of our investigation is to explore how publicly available datasets can be used to help assess services using a methodical, repeatable, transparent and evidence based process that makes use of an interactive map-based website to allow modelers to better explore the data and its interrelationships. The focus is on services provided at specific locations, and we consider that demand is determined by demographics, accessibility by public transport (since not all have access to private cars), and the availability of alternatives.

Related Work

Demand for services varies spatially, with population density, demographics and transport as key determinants of accessibility. Location-allocation models are used to optimise the locations of service centres. A specific review in the health sector, found that greater availability of geographic data (e.g. GIS) and enhanced computing power has greatly expanded the range of data applications [START_REF] Tanser | Location-allocation Planning[END_REF]. More recent applications include using mathematical optimisation techniques to identify optimal locations for defibrillators in urban areas [START_REF] Tsai | Optimizing locations for the installation of automated external defibrillators (AEDs) in urban public streets through the use of spatial and temporal weighting schemes[END_REF][START_REF] Chan | Identifying locations for public access defibrillators using mathematical optimization[END_REF]. A decision support system was developed using a mixed integer programming model to determine the efficient location of government service delivery offices by identifying which offices could be closed with the least impact on customers [START_REF] Narasimhan | Efficient service location design in government services: A decision support system framework[END_REF]. Such models can be used to explore a number of different scenarios, and provides decisionmakers with an objective method of making, and justifying, service delivery decisions. A review of the use of geo-information technologies to support collaborative and participatory decision-making found that this can help to engage a greater range of stakeholders and elicit more local knowledge [START_REF] Mccall | Geo-information tools for participatory spatial planning: Fulfilling the criteria for 'good' governance?[END_REF].

The simplest approach to accessibility considers Euclidean distance from locations, while more detailed models include roads and other transport features [START_REF] Noor | Modelling distances travelled to government health services in Kenya[END_REF]. Accessibility by private car can be estimated from traffic flow models, but public transport has proved more complex due to the vagaries of routes and timetables [START_REF] Tanser | Location-allocation Planning[END_REF]. Spatial optimi-sation has been applied in environmental management, including conservation [START_REF] Moilanen | Spatial conservation prioritization: quantitative methods and computational tools[END_REF] and natural resource management [START_REF] Bryan | Landscape futures analysis: Assessing the impacts of environmental targets under alternative spatial policy options and future scenarios[END_REF].

Methodology

The following process describes the steps taken to develop the interactive map-based website for use by a domain matter expert: the modeler. This process requires expertise in data management and website administration. While these skills are available in the Information Technology (IT) section of most organisations, they are also becoming a common skill set within reach of researchers. We believe the skills required to accomplish the tasks outlined below are increasingly within the capability of modelers themselves, especially as supporting software tools become available in the field of semantic web and linked data.

Problem Definition

The first step is to clearly define the problem to be solved. While this may seem obvious, it is sometimes assumed to be self-evident and therefore overlooked. By taking the time to define the problem to be solved using clear and unambiguous language, all participants in the task will share a common understanding of the goal to be achieved.

Obtain the Data

Central to the methodology is the need to understand the community for whom services are being provided (usually using census information) and the preferred means of accessing the services (in our case public transport). A summary of these two critical datasets are described in Section 4 below. The other necessary dataset for the decision making process is the locations of the services being evaluated. This is expected to be available to the subject matter expert: the modeler. There may be other datasets necessary and again, it is the responsibility of the modeler to provide these and describe how they are to be used.

In some cases the required data will not be available and so proxies must be identified. This occurs when the necessary level of detail is not available and so approximations are required or where the specific data is not available, but known correlations can be found. An example is presented in the first case study where the home locations of customers for a government shopfront are not known, but are approximated using the Department of Social Security (DSS) payment recipients by postcode data from data.gov.au.

Load the Data

In order to load the data into a database, the data needs to be in a machine readable format. This process may require the data to be 'cleaned' (free of errors or inaccuracies), restructured (only relevant data extracted) and pre-processed (transformed to be suitable for the database loading tools) before it can be loaded. In some cases the data may need to be modified to make it compatible with other datasets. For example, the identifiers used to reference common artifacts (such as postcodes, suburbs, street names and so on) may need to be modified to match other datasets. This is often necessary when combining data managed by different custodians.

Define the Decision Making Model Function

There are three elements to the definition of the decision making model, outlined below. Note that this is intentionally a simplistic approach that is quick to implement with available datasets as a proxy for actual usage data. As actual data is released, more powerful models can be used.

1. Categorise the community to reflect different service demands.

For the example case studies below, we categorised the community into demand groups (e.g. levels of high, medium and low demand). The number of categories and how their membership is defined is dependent on the problem under investigation and at the discretion of the modeler. It is likely to include demographics (e.g. families with young children and families living in high density housing, are likely to have a higher demand for urban parks) and the availability of alternatives (e.g. households with broadband internet are more likely to access government services online, and so will have reduced demand for shopfronts).

Combine the different measures of service accessibility.

The service accessibility includes public transport travel time but can also include other measures (e.g. walking or driving distance).

3. Include parameters to account for relative competing service demands.

The contribution of each variable parameter to the overall result will change based on modeler supplied weights. This is how outcomes are prioritised. For example, decision-makers may assign a higher weighting to certain disadvantaged groups, or long travel times.

Update the Website

Geographic data can be explored visually in order to gain deeper insight into the available data. As well as making the input datasets available, the parameterised decision making model function is included as a derived data layer. This is how the modeler explores different scenarios -by providing different model parameters and viewing the results.

Gathering Data

Public Transport Travel Times

One of the measures of accessibility to a service is the travel distance to its location.

A different accessibility measure is the travel time using public transport. Websites exist for people to plan travel on road networks, see for example Google Travel Planner 1 . Similarly, public transport journey planners are available for all Australian capital cities and some regional areas. It would not be feasible to manually use these journey planner websites to calculate the travel time to the nearest service. Software was used to perform this task. Public Application Programming Interfaces (APIs) are available that provide a software interface to public transport journey planners, such as Google's Directions API 2 and the SilverRail3 Journey Planner. However, these APIs have strict licensing conditions and/or only allow a small number of requests before a fee is required. For example, Google's Directions API only allows 2,500 requests per day and the results must be displayed on a public Google Map. An alternate open source solution was found along with timetable information, based on OpenTripPlanner and OpenStreetMap. By installing this software locally, we could make as many requests as necessary.

Software was written to systematically use OpenTripPlanner to generate travel plans for the 34,172 SA1s (62%) that were within the regions of Australia for which we had public transport data. For each SA1, travel plans were generated from the SA1 centroid to all service locations that were within a specific radius of the SA1. Open-TripPlanner can generate several alternate itineraries for each SA1 service location combination. Only the journey with the shortest duration was recorded in the database. Further details are provided in the case studies below.

Government Office Locations Case Study

Description

Government services have traditionally been provided to citizens through face-to-face interactions at shopfronts or through telephone services provided by call centre staff. More recently, there has been a push to transition customers to self-management through digital services with the aim of reducing service delivery costs while maintaining customer satisfaction. Over time, face-to-face government services can be combined between departments and call centres consolidated providing efficiencies.

Process

For this investigation we worked with the Australian Government Department of Human Services (the department) to evaluate alternative options for service delivery to meet anticipated customer needs balanced against the department's resources. There are 304 existing government shopfront locations, referred to as customer service centres, or simply offices, available from data.gov.au. Another public dataset used was Detailed Payment Demographic Data which included payment recipient numbers by postcode for the March 2014 quarter 4 . There were 27 payment categories such as age pension, carer allowance, disability support, unemployment benefit and so on. This data was de-aggregated from postcodes to SA1 regions using ABS socioeconomic indicators by matching the expected customer profile to the different benefit types. For example, areas of high socio-economic need are allocated more customers for specific benefit types, such as unemployment payments, compared to areas of lower socio-economic need [START_REF] Power | Planning the Future Face to Face Service Delivery Footprint[END_REF]. In summary, the aim of the investigation was to evaluate the accessibility of existing offices in terms of public transport for the department's customers and to model the potential for customers to transition to self management through digital services.

The ability of citizens in the different geographic areas to transition to self management through digital services can be approximated by the broadband availability and usage in their local area. The idea being that digital services are best provided to areas that are currently well serviced and utilised by the community. This information was available from two sources: the ABS census data (which includes an indication of the Internet availability for dwellings for each SA1 region) and the Australian Government Department of Communications MyBroadband website 5 .

The demand for services was modeled by categorising the customers into three groups; high, medium and low, using the payment demographic data. Those customers with high need likely require regular and possibly intensive meetings with front line customer service staff. Those with low need are expected to understand their obligations and (mostly) meet these requirements using self service interactions, preferably online. Customers categorised as medium fall between these two and will have some irregular face-to-face or phone contact with the government while also fulfilling some aspects of their interactions through self service mechanisms.

A demand (d) measure for each SA1 region is calculated by combining the customer category numbers (customers categorised as being high (h), medium (m) or low (l) need) with the services expected to support them. This is a weighted combination using parameters (w h for high weightings, w m medium and w l for low) as follows:

𝑑𝑑 = 𝑤𝑤 ℎ • ℎ • 𝑡𝑡 𝑖𝑖 + 𝑤𝑤 𝑚𝑚 • 𝑚𝑚 + 𝑤𝑤 𝑙𝑙 • 𝑙𝑙 • 𝑏𝑏 𝑠𝑠
Here t i is the travel interval in a range of 1-10 and b s is the broadband scale. In both cases, 1 is good (short travel time or good broadband) and 10 is bad. The demand measures for the SA1 regions close to an office are then summed, normalised and scaled and the results ranked to allow comparisons between offices.

The rankings were used to divide the centres into deciles loosely based on customer need. If the need was low, policy makers could consider downsizing the centre and shifting more services online. Demand for a centre's services was defined as the sum of the SA1 rankings in the centre's catchment. This sum accounts for the volume of customers weighted by their service requirements (high, medium or low) and their access to public transport or broadband.

Once demand was calculated and centres were arranged into deciles, policy makers could look at the distribution of customers at any given service centre. Univariate statistics like the mean, median, skew and kurtosis were generated to help evaluate large groups of service centres within a decile and a histogram of customer need scores was generated for each individual centre.

Using the univariate statistics, policy makers are able to identify centres with concentrations of one particular customer type, or centres with skewed distributions indicating a wider mix of customer demand. The histograms of key centres can then be analysed prior to considering changes to the services offered by a centre. This allows the impact of change on the full spectrum of customer types to be considered.

The data is available to explore on the http://rapt.csiro.au/rprc website.

Urban Parks Accessibility and Demand Case Study

Description

The next case study examined the expected use of parks in the Brisbane metropolitan area. Urban parks offer a range of environmental services, which are likely to become increasingly important as housing density increases. The 2,042 park locations and descriptions of their facilities were obtained. The park facilities indicate, among other information, the presence of playgrounds, sporting areas (fitness exercise equipment, netball courts, soccer fields), recreation areas (bike paths, skating areas, bushwalking) and picnic facilities (barbeques and seating). The aim of this investigation was to measure park accessibility and demand by using public transport. Some parks will be more attractive than others based on the facil-ities they provide. This equates to an 'attractiveness' measure, defined by the number of facilities provided, ranging from 0 (no facilities), 1 (one of playgrounds, sporting areas, recreation areas and picnic facilities) up to 4 (includes all facilities).

Process

Two stages of data preparation were required: calculate the walking and public transport travel times to the various parks from the SA1 regions and identify members of the community most likely to want to use the different parks.

Parks with playgrounds were expected to be used by families with small children, recreation parks used by teenagers, parks with picnic areas by people who live in dwellings without a yard and so on. To reduce the calculations required, thresholds were placed on the distance people will travel to a park based on the attractiveness measure: people are expected to only walk up to two kilometers to a '0' park (attractiveness measure of 0, i.e. a park with no facilities) and optionally use public transport to travel to the other parks. For a '1' park, the maximum distance travelled is set to 3 kms, 5 kms to a '2', 7 kms to a '3' and 10 kms to a '4'. We are assuming that people will be willing to travel further on public transport to parks with more facilities (ie those with a higher attractiveness score). The travel planner software was configured to calculate public transport travel plans for each SA1 -park combination that meets these park attractiveness and distance constraints.

The model used is an arbitrary proxy to demonstrate the types of inferences that can be drawn from this type of data. More powerful models could be constructed using the local council's actual usage statistics. Our model's advantage is in using publicly available data and easy to implement methods for early stage exploratory analysis and to demonstrate what can be learned if more data is pushed into open access. Additionally the linking of public transport information and the readily interpreted map-based display of model outputs is of high utility to policy makers.

The data is available to explore on the http://rapt.csiro.au/parks website.

Discussion and Future Work

There have been a few lessons learned in undertaking these case studies. While there is an abundance of open government data published in Australia, the same data is available from different agencies, in different formats, with different structures and includes different content. The data.gov.au site is a central repository of authoritative government data, however state governments maintain the same data on their own data repositories or agency specific websites with content that is more up to date and more extensive. For example, the Brisbane park data was obtained from the Brisbane City Council website 6 not data.gov.au. Finding data relevant for a particular investigation has become easier and governments are more willing to describe and share their data. However, improvements in data related outcomes can still readily be achieved if governments are able to interlink their releases with existing public and private datasets. Interactive map-based websites are becoming ubiquitous and user expectations of the features available from them are increasing. This is in our view an opportunity and was the motivation for our case studies: combining readily available open government data for new purposes and making it available in a publicly accessible and interactive website. However to achieve these aims we have had to exploit specialist skills in data management, software engineering, web application development and statistics.

While the short term aim was to demonstrate the benefits of combining these skills to deliver the solutions presented, this process is not sustainable. Instead, tools need to be developed to allow users to readily incorporate web accessible datasets of their own choosing. This integration needs to be more than simply making datasets appear as a new 'layer' on the website. It needs to be combined in the context of the datasets already present. This can be achieved by utilising emerging standards and supporting tools in the field of the semantic web. This is an ongoing area of our research.

Another area of further work is to move away from a data warehouse solution and utilise a services oriented architecture. This requires the data custodians to introduce suitable services which adopt appropriate standards. While these services are not currently universally available, it is expected they will be established over time.

Other future work includes automating the process of exploring and evaluating the scenario generation process, mechanisms to combine private data using authentication controls and to extend the public transport analysis. For example, to preference trains over buses, use different thresholds for the maximum number of transfers, varying the maximum walking times for different customer cohorts and including more timetable options, such as weekends and different times of the day.

Conclusions

We have presented a methodology for characterising the demand for community services, with a focus on evaluating existing service locations in terms of their accessibility by public transport and ability to meet demand. The methodology has been demonstrated by two case studies using publicly available datasets. It provides a methodical, repeatable, transparent and evidence based process for users to perform scenario planning. The scenarios are explored by users providing parameters to the decision making model with the results available as an interactive map-based website. The aim of the first case study was to demonstrate what could be done without actual access to the required data. We weren't subject matter experts, did not have access to the detailed customer data, and did not try to build the most accurate model. Our objective was to demonstrate what could be achieved if government were to open access to more data. We showed possible results and how they could be used by decision makers to enhance policy outcomes.

If the data was to become open, our model for demand would change drastically (mixed integer programming, approximate Bayesian computation, hierarchical regression models with spatial correlations). We could tailor the model to the data itself. In this paper we are using a balance between simplicity and general applicability to make a case for releasing more data. The second case study examined the expected use of parks in the Brisbane metropolitan area based on park facilities, demand and accessibility by using public transport.

These examples show that the decision making process is available to non-expects such as members of the general public who have an interest in exploring such issues in their community. In order to fully realise this aim, the user needs to be able to integrate their own data and define their own decision model function. The availability of relevant public datasets goes some way to achieve this aim. The next stage is to develop advanced tools based on semantic technologies and linked data to allow users to integrate content, visually explore data and to model relationships. The result would be a general purpose web accessible 'spatial spreadsheet', combining features found in web mapping, databases, Geographical Information Systems and spreadsheet tools.

  The Australian Bureau of Statistics (ABS) divides the country into a structure of hierarchical non-overlapping regions called the Australian Statistical Geography Standard (ASGS). These regions are used to present aggregate statistical information, such as population density, economic indicators, and so on. The main regions are termed Statistical Areas defined in four levels: SA1 (Statistical Area Level 1), SA2, SA3 and SA4. A collection of SA1 regions are grouped to form an SA2; the SA2s are grouped to form an SA3 and so on. There are 54,805 SA1s; 2,214 SA2s; 351 SA3s; 106 SA4s. SA1 data has been used in the case studies described below. These are the smallest regions for which the ABS releases census data and they vary in size to have a population of 200 to 800 people with an average of about 400 people.

	4.1	The Australian Statistical Geography Standards (ASGS)

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011

http://maps.google.com.au/intl/en/landing/transit/

https://developers.google.com/maps/documentation/directions/

http://www.silverrailtech.com/journeyplanner

http://data.gov.au/dataset/dss-payment-demographic-data

https://www.mybroadband.communications.gov.au/

http://data.brisbane.qld.gov.au/index.php/datasets/

Acknowledgements

This work was funded under the Human Services Delivery Research Alliance between the CSIRO and the Australian Government Department of Human Services. Thanks go to David Lovell (CSIRO) who provided helpful advice during the project.


Uwe Rosebrock
email: uwe.rosebrock@csiro.au

Peter R Oke
email: peter.oke@csiro.au

Gary Carroll
email: gary.carroll@csiro.au

An Application Framework for the Rapid Deployment of Ocean Models in Support of Emergency Services: Application to the MH370 Search

Keywords: integrated environmental modeling, software control framework, connectivity, large data management, model management

Ocean models are beneficial to many different applications, including industry, public-good, and defence. Many applications use high-resolution models to produce detailed maps of the ocean circulation. High-resolution models are historically time-consuming to configure -often taking weeks to months to properly prepare. A system for automatically configuring and executing a model to predict the past, present, or future state of the ocean -named TRIKEhas been developed. TRIKE includes a sophisticated user interface allowing a user to easily set a model in minutes, control data management and execute the model run on a supercomputer almost instantly. TRIKE makes it feasible to configure and execute high-resolution regional models anywhere in the world at a moments notice. TRIKE was used to support the recent search for MH370 that is thought to have crashed somewhere in the South Indian Ocean.

Introduction

Ocean models are routinely applied to predict the past, present, and future state of the ocean to better understand ocean dynamics and to support a range of industrial, public-good and defense applications. Since the advent of the Global Ocean Data Assimilation Experiment (GODAE; www.godae.org), a global initiative to develop operational ocean forecasting capabilities, several global and basin-scale ocean forecast systems have been developed with resolution of up to 10 km [START_REF] Hurlburt | High-resolution Global and Basin-Scale Ocean Analyses and Forecasts[END_REF]. This is beneficial to many applications, but delivers forecasts at insufficient resolution for many situations that require resolution of up to 1 km. For these applications requiring high-resolution, it is common to configure and run regional models, where the domain extends only a few hundred kilometres or less. Historically, regional ocean models are timeconsuming to configure, requiring an expert modeller to configure a grid -carefully setting the spatial extent of the model domain and the model resolution. The expert continues the process by acquiring the data to support the running of the ocean model. This generally involves the gathering of the data from multiple sources to set the ba-thymetry, coastline, initial conditions as well as forcing fields. The modeller then reformats the various datasets to meet the requirements of the specific ocean model and configures the ocean model dynamics for the chosen region -carefully considering the dominant physical processes and requirements to properly represent the important characteristics of the regional circulation. The modeller selects a suite of model parameters, numerical schemes, and boundary conditions that are appropriate for the chosen application. In the past, this process would take several weeks for an experienced modeller, and several months for a less-experienced modeller, making realtime applications inconceivable. Moreover, the idea of a non-expert user (e.g. a marine biogeochemist) was merely a pipe dream. However, the development of a system called TRIKE (or 'wheels for modellers'), by the CSIRO has made the configuration and execution of a regional ocean model simple. With a sophisticated user interface, a user can quickly and easily set up a model domain, select the desired input data sources, and execute the model. TRIKE allows a user to run a model simulation for any historical period, or for a forecastpredicting the ocean circulation for several days into the future. This paper documents the salient features of TRIKE, and describes a recent application that supported the Australian Maritime Safety Authority in the search for the ill-fated flight MH370.

TRIKE

The TRIKE user interface (Fig. 1) allows a user to use a graphical interface to set the model domain, the model resolution, the input data sources, and other key specifications of the model run (e.g., what time-period to simulate, and when to execute the model). The back-end of TRIKE then configures a state-of-the-art ocean model [START_REF] Herzfeld | Improving stability of regional numerical ocean models[END_REF] for a specific area. Ocean models solve mathematical equations on a computer to simulate the time-evolution of the ocean circulation; representing impacts of surface forcing (e.g. wind) and tides [START_REF] England | Ocean modeling and prediction[END_REF]. A large amount of data is needed for every application. TRIKE automates this process of configuring the model and massively reduces the setup time required to less than a minute (historically weeks to months). TRIKE consists of several software components, including an extensive data management and interrogation component. The software components manage the user interactions and apply extensive heuristics to create the scientific modelling domain.

Fig. 1.

The TRIKE user interface and wizard.

Defining the Model Domains

TRIKE provides a simple-to-use application that uses the notion of a "run wizard" to select model characteristics such as the model type and the temporal and geographical extent. The original aim in developing TRIKE was to provide a facility to allow the running of complex models with minimal human effort. This was extended to also allow users with minimal understanding of the actual modelling process access to initiate, configure and execute model runs independently. The result is a "desktopclient" leading a user through the process of setting up a model run with simple steps. (Depending on the permissions of users more sophisticated options are made available.) The complexity of the various parameter ranges from output directives to creating sophisticated interpolations of a domains bathymetry. In addition TRIKE provides the facility of high level scheduling and repetitions (e.g. run process every 12 hours). The scheduling extends from simple run-later to creating dependencies between runs (e.g. process x starts after process y has finished).

Data Preparation

The nature of numerical models dictates very comprehensive input data requirements. TRIKE is capable of maintaining an extensive database of forcing data and automates the process of data preparation for a particular model; configuring a model process and selects, extracts, prepares and assembles the appropriate input data. To be able to utilise different data sources and to meet the requirements of an ocean model, a matching from provided to the required data is necessary. As an example of a data provider; the Australian Bureau of Meteorology performs many weather forecasts each day. Internationally, many weather centers perform equivalent forecasts to the Bureau, generating equivalent data, but disseminating data in different formats (e.g., with different variable names, units etc). TRIKE matches the data sources it manages to what is required by a model by using metadata vocabularies and runs processes to convert data so the receiving model can ingest the data correctly. The regional data used can be available through online services or stored locally. The ingestion of data can also be localised or provided through online services. The provisioning of the data is a very important aspect of the model preparation process, particularly for data sets updated on a regular basis, the TRIKE sub-system is capable of monitoring and re-sponding to changes in the data availability.

Running a Model

Once the modeling process has been prepared it can then be run on a remote highperformance computer, on a local compute server, or the workspace can be made available as an archive to be run on user infrastructure outside TRIKE. The progress of the computational process can be monitored through the application's user interface as the modelling process is executed (see Fig. 1). The execution may utilise high per-formance computing job queues or simply execute a process remotely. Either is mon-itored and can be aborted. Deployment into cloud-based compute-resources has also been implemented as a prototype. TRIKE consists of several components that function independently of each other and communicate with each other via dedicated protocols. Fig. 2 shows an overview of the management component Run Coordination System (RCS), the Data Management Framework (DMF) and the interface to the individual modelling components. Fig. 3 shows a generalised workflow of creating a modeling process. Once the process has successfully finished, post-processing can consist of further analysis and/or packaging. After a process is complete, results are transferred to a server for further analysis. Scientific users of TRIKE can receive bundled model run workspaces that allow the user to fine-tune the model configuration and rerun the process. Originally TRIKE was developed for the Royal Australian Navy (RAN), under the Bluelink partnership [START_REF] Schiller | Taming Australia's last frontier[END_REF]. Today the RAN uses a dedicated customised system routinely for tactical briefings prior to operations. TRIKE also has enormous potential benefits for public applications including search and rescue at sea, modelling of effluent dispersal following oil spills, environmental prediction of ocean currents to inform industry of risks during operations (e.g. oil and gas exploration), and storm surge prediction during tropical cyclones.

As a research tool it can provide easy access to determine for example biological connectivity, path of invasive species [START_REF] Brinkman | Could ocean currents be responsible for the west to east spread of aquatic invasive species in Maritime Canadian waters?[END_REF], marine debris in general [START_REF] Hardesty | Understanding the types, sources and at-sea distribution of marine debris in Australian Waters[END_REF], abandoned fishing equipment [START_REF] Wilcox | Ghostnet impacts on globally threatened turtles, a spatial risk analysis for northern Australia[END_REF] or support more general coastal inundation modelling. TRIKE currently supports several ocean models and wave models as well as a regional at-mospheric model. It has the capacity for further integration of models or any other data driven processes as well as creating dependencies between modelling process (nesting of one model within the data space of another, parameter estimation).

Current and Future Work

A web-based user interface has been developed under the MARVL (http://www.marvl.org.au) project to simplify maintenance and expand the user uptake. It forms the basis for several other projects within CSIRO such as eReefs (http://www.ereefs.org.au). Further developments under the 'Australian Wave Energy Atlas' are underway to incorporate the advances provided by accessing the local graphical processing unit (GPU) from within a web-browser to present and edit complex geometries defining the modelling domain. The intention for future development is to also move some of the processes, like interpolations currently performed on the server, into the GPU to improve the user experience.

Application to MH370

Malaysian Airlines Flight 370 disappeared on 7 March 2014 at 17:20 UTC. A multinational search effort subsequently began, initially focusing on the Gulf of Thailand and the South China Sea, before shifting to the South Indian Ocean. Using a range of different techniques, several possible "splash-points" were identified -but all with relatively high-levels of uncertainty. Many groups around the world began trying to predict the possible fate of surface debris that may have resulted from the crash. Many different estimates of surface velocities were used to support the search, including near-real-time maps of sea-level and surface velocities from satellite altimetry (e.g. oceancurrent.imos.org.au), estimates of the past, present, and future ocean circulation from operational ocean forecasts and regional ocean forecasts generated by TRIKE. An example of the type of analysis performed using 2-km resolution TRIKE forecasts (limited by computation resources) are shown in Fig. 4, showing the locations of a cluster of hypothetical particles (intended to represent debris from a possible crash site) at the time that MH370 is thought to have crashed, and locations of the particles 19 days later. In this example, there was a front separating relatively warm water (yellow-orange in Fig. 4) and colder water (green-blue in Fig. 4). For this simulation, the model predicts that if the plane crashed into the ocean along this front, then any resulting surface debris would likely spread along the front. Information like this was disseminated to decision-makers who were coordinating the search effort for MH370.

The data produced by TRIKE that formed the basis of the analysis outlined as well as the imagery shown in Fig. 4, can easily be incorporated as a post-processing step of a modeling process managed in TRIKE.

Conclusion

As environmental computational modelling is becoming a more and more standard tool used in science and environmental services, it appears crucial that a supporting infrastructure is also developed. TRIKE has demonstrated to be capable of supporting numerous numerical models as well as the versatility to meet a broad set of demands. The current state of TRIKE is the result of many years of development. The Royal Australian Navy has made use of a derived version of TRIKE called ROAM (Relocatable Ocean and Atmosphere Modelling framework) for some time. The lessons learnt from that deployment and the re-investment into the concept have saved innumerous hours of science time and promises to lower the hurdle of access to numerical modeling further through the current developments.

Although the search of the MH370 plane did not result in a positive detection of the remains of the aircraft, the applications allowed the developers of TRIKE to showcase its versatility. It will undoubtedly be used for future applications such as support for search and rescue, oil spill response and as a research tool.

Fig. 2 .

 2 Fig. 2. An overview of the TRIKE framework.

Fig. 3 .

 3 Fig. 3. The general workflow to initiate a TRIKE process, the background colours correspond to the location and correspondence of components in Figure 2.

Fig. 4 .

 4 Fig. 4. Examples of the modelled ocean temperature (colour) and modelled particles (black cells) tracking the possible trajectories of surface debris from a possible crash site of the MH370 plane for 7 March 2014 and 26 march 2014. The pink arrowheads show the location and velocity of surface drifters.

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011


Claire Miller
email: claire.miller@csiro.au

James Hilton
email: james.hilton@csiro.au

Andrew Sullivan
email: andrew.sullivan@csiro.au

Mahesh Prakash
email: mahesh.prakash@csiro.au

SPARK -A Bushfire Spread Prediction Tool

Keywords: level set, bushfire, wildfire, modeling, simulation

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Although a natural occurrence in the Australian landscape, bushfires have the ability to be devastating, particularly when they come into contact with urban environments. Improving knowledge of how these fires spread is critical for effective management and timely issuing of warnings. Unfortunately, it is difficult to predict the rate of spread of a fire as there are many elements influencing fire behavior occurring over a range of length and time scales. Fully physical computational fluid dynamics models attempt to incorporate a large number of these elements, but are computationally intensive and are not practical in an operational environment. Instead, operational models usually propagate the perimeter of the fire using spread rates based on empirical expressions. These empirical models can give an approximation of expected fire area in a significantly shorter computational time than physical models. Two operational tools currently in use in Australia are Phoenix Rapidfire [START_REF] Tolhurst | Phoenix: development and application of a bushfire risk management tool[END_REF] and Australis [START_REF] Johnston | Efficient simulation of wildfire spread on an irregular grid[END_REF], both developed over the last ten years. SPARK has been developed with the goal of easy adaptability. It allows user defined spread models, as opposed to the hard-coded spread models found in current operational tools. This functionality enables many aspects of simulated fire spread to be tested and investigated. One such aspect is the non-homogeneity of a bushfire's local environment, which we explore in this paper.

This paper aims to familiarize readers with SPARK's architecture and development path, and to demonstrate its analysis capability for a simple fire scenario. We explore the functionality of SPARK in dealing with non-homogeneity, which highlights the requirement for correct consideration of local environmental conditions.

SPARK Overview

SPARK uses a level set method for the representation of the fire perimeter, which propagates over a domain according to a one-dimensional algebraic rate of spread. The model sits within a workflow environment, allowing a broad range of flexibility in the analysis and the input and output of data types. Core elements of the model are explained in further detail below, along with details on the data aspects of the tool.

Level Set Method

The level set method is used to model the propagation of the fire perimeter. Use of this method is still fairly novel for fire simulation, particularly for large-scale wildland fires. The level set method was first implemented as an interface propagation solution by [START_REF] Osher | Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations[END_REF] and has since been found useful over multiple application areas (eg. [START_REF] Sethian | Crystal growth and dendritic solidification[END_REF] and [START_REF] Sussman | A level set approach for computing solutions to incompressible two-phase flow[END_REF]). In contrast to traditional simulation methods which define front locations and propagate these locations forward in time, the level set method defines a surface over the domain according to a distance function. In this implementation the value of the distance function, Φ, is equal to the closest distance to the fire perimeter. The function is defined as positive where the fire is yet to burn and negative in burnt areas. This allows for simple identification of the front location at Φ = 0. Evolution of the surface in time is determined for each grid cell using some rate of spread value, S, in a direction normal to the fire front, according to

𝜕𝜕Φ 𝜕𝜕𝜕𝜕 + 𝑆𝑆|∇Φ| = 0. (1)
For a more detailed explanation of the model, see [START_REF] Hilton | Incorporation of variation into wildfire spread models using a level set approach[END_REF].

One Dimensional Spread Rates

The value of S in Equation ( 1) is calculated for each cell according to a one dimensional rate of spread model. This spread rate model is a function of the environmental conditions at that grid point. The level set method in SPARK uses OpenCL [7], allowing the spread rate model governing the value of S to be directly passed to the OpenCL compiler as a text string written in the C programming language. This allows the flexibility of incorporating a range of aspects and functional forms of fire spread model. An example input is shown in the lower right panel of Fig. 1.

Workflow System

The SPARK solver sits within a modular workflow environment, developed by CSIRO, called Workspace [START_REF][END_REF]. The Workspace GUI with an example workflow is shown in Fig. 1, where operations are represented by colored triangles and connections between operations are represented by the black lines. The directions of flow of information between the operations are shown as arrowheads superimposed onto the connecting lines. Workspace allows users to build computational solutions using a catalogue of these operations, shown in the panel on the left in Fig. 1. Each operation has its own function, for example fire propagation by the level set method is performed within the SPARK 'Bushfire solver' operation, circled in red. Operations are dragged from the catalogue to the main canvas, where all the operations currently in use can be seen. Input and output container types are predefined and passed between the operations to create a workflow. These connections can only be made if connected container types are compatible. Users can interchange operations by simply passing the new operation's output to replace the old one. New user-defined operations can easily be added to analyze or visualize data. The Workspace is based on the Qt framework, and all operations are written in C++. Data is held in memory to allow efficient sharing and passing between operations. Work-space allows the data to be read and written at any stage of workflow operation. This allows users to visualize progressive fire spread output from SPARK. New operations and data types are compiled as shared libraries (.dll, .so or .dylib) which act as plugins to Workspace. For example, the SPARK model and analysis operations are all contained within a single plugin. This plugin architecture allows transparent access between different data types and operations within the framework. C++ stub code for new operations and data types can be generated using code generation wizards and compiled using the included CMake build system and scripts for cross platform compilation.

As well as the Workspace GUI shown in Fig. 1, workflow execution is supported from the command line through batch execution or exposed through an API. Close integration with Qt allows complex user interfaces to be designed and transparently connected with an underlying workflow, allowing custom applications to be easily developed. Parallel APIs, such as OpenMP and OpenCL, are fully supported. Operations for running scripts in both ECMAScript and Python within Workspace are also available for non C++ developers. Furthermore, a number of existing open-source software systems have been natively compiled with the Workspace framework. These modules include; OpenCV for image analysis, which can be used to convert fire imagery to SPARK inputs, NetCDF for large data file support, which is useful for SPARK's environmental inputs and spread information outputs, and GDAL for geospatial analysis and conversion, which can convert to meter grids from latitudes and longitudes for compatibility with fire spread rate equations.

2.4

Integration with the Amicus Decision Support Tool SPARK has been built with the capability to be integrated with the decision support tool Amicus [START_REF] Sullivan | Amicus: a national fire behaviour knowledge base for enhanced information management and better decision making[END_REF] through Workspace. Amicus is a knowledge base and tool informing users on expected fire behavior metrics given a set of fuel, weather, and topographic conditions. It has been built around a number of well-established fire spread models developed for Australian vegetation. The rate of spread model functions in Amicus exist as separate operations within Workspace and can be used and tested within Amicus before being implemented dynamically within SPARK.

Data Inputs

Fires can occur over a vast range of vegetation and fuel types. By using gridded inputs for fuel properties it is possible for a variety of fuel types to occur within the same simulation, bounded only by grid size. This can include areas of un-burnable fuel, such as roads and water bodies. The development of SPARK within a workflow environment allows users to easily incorporate these environmental inputs. Fuel grids can be pre-populated and read directly into the workflow, or manipulated from other inputs, such as satellite imagery, within the workflow.

Weather conditions, in particular significant changes in weather conditions, contribute significantly to fire consequence. Atmospheric condition inputs, which often include air temperature, relative humidity, wind speed, and wind direction, are gener-ated as time series. The time series inputs for the model are implemented as a Workspace data type with arbitrary temporal spacing between the samples.

Data Sources

In order to run SPARK, data is required for the atmospheric conditions, fuel conditions, topography, and initial fire location. This can be sourced from a range of databases discussed below, depending on the scenario. A current aim is to integrate web services into the model, such that data can be directly used by the system. Historical data for atmospheric conditions are available from the Australian Bureau of Meteorology at half hourly intervals for a number of stations nationally. This data can be used to set parameters such as the wind, temperature, and moisture levels for simulating large historical fire events. Issues arise when the stations available are not close, in both location and environment, to the ignition location. In the future, we hope to gain access to data recorded during fire events, or gridded hindcast data, which may provide a more accurate record of the conditions. For small experimental fires, such as the case demonstrated in Section 3, atmospheric data is commonly recorded at a high frequency in locations close to the fire.

Fuel inputs are slightly more difficult to obtain. They can be manually created using basic satellite imagery, such as from Google maps. A related, but more sophisticated, method is to create classifications using satellite band imagery from LandSat. A third option is to use land use grids which can be converted to fuel types, however these tend to lack the critical details of unburnable areas such as roads and water bodies. Which of these inputs are most useful depends on the scale of the area of interest and the fuel information that is required for the rate of spread formula used.

The last input is initial fire location information. Fire ignition locations and progression maps are available online for some historical fires and hence are simple to implement. For more recent fires, fire agencies will often use airborne thermal imagery to determine current fire extent. This imagery is geo-tagged and can be converted to a fire front map. For example, some images may be false colored with the fire appearing as red in the image with the surrounding area blue. It is straightforward to split the image by color and threshold according to the value of the red channel. Additionally, this entire process can be performed within the workflow.

Data Output

The output from SPARK consists of gridded forms of both the value of the level set function at a user specified frequency and the time of ignition over the domain. This allows users to easily investigate both long term and time specific consequence of the fire.

A series of small scale, 35 m square, experimental burns were conducted in Ballarat, Victoria, Australia in January, 2014 [START_REF] Cruz | Grass curing and fire behavior[END_REF]. Weather data was recorded during the fires, for both the wind speed and bearing, at a frequency of 10 Hz. The fire used in this example burnt for 28 seconds, with wind speeds averaging around 4 ms -1 . Quadcopter footage was taken of each fire, which was then stabilized and rectified to provide clear observations of the spread. For this example, simulated spread was governed by a generic rate of spread model with an added curvature dependent component. The grid size was 0.1 m. A qualitative comparison of simulated spread to actual fire imagery indicates a good match for both fire shape and rate of spread, as shown in Fig. 2. This is largely influenced by the ability to incorporate curvature. Without the inclusion of a shape-related variable in the spread model, simulated fires on flat ground tend to maintain their initial shape.

A Study of Non-Homogeneity

A major challenge in simulating bushfire spread is dealing with the complexities of the environments in which they occur. This can include complex topographies, often large varieties of fuel types, and local variations in weather and fuel. Operational fire spread models developed for large scale fires assume fires will attain a quasi-steady rate of spread for conditions averaged over considerable time and distance, invariably smoothing out local scale environmental variations. SPARK was used to investigate the effect of this local variation on fire spread. The use of a gridded input system allows the methods for the inclusion of variation explained below to be simply implemented. The application of these mechanisms is demonstrated in Section 5.

The Inclusion of Variation

At most scales, our environment is far from homogeneous. The software architecture has the functionality to easily incorporate spatial and temporal variation into both the fuel and wind inputs.

In order to include fuel variation, a grid was populated prior to the running of the model. Fuel values for each cell were chosen randomly, and independently of surrounding cells, from a predefined distribution. The distribution used could be different for different fuel varieties according to a fuel input grid. The random selection process enabled reproducibility by setting a seed value for the random number generator. Fig. 3 is a diagram showing the fuel population process. Variation was also included in wind, for both speed and direction, in a similar manner. For the wind however, the value of each parameter was randomly chosen from its predefined distribution for each grid cell spread calculation at each time step. For this preliminary investigation, the variation in both fuel and wind was assumed to be normally distributed.

The workflow system allowed the implementation of variation to be straightforwardly incorporated in the execution of the model. The seed value was given to a random number generation operation which gave a new random value every time one was requested. The random operation in this case was used for both the population of the fuel layer and the wind strength and direction.

Probability of Arrival Maps

The addition of variation into the model in this manner adds an element of randomness into the arrival time of the fire at a given location. As such, the same simulation run with a different randomly selected set of environmental values, based on the same distributions, could potentially produce a different set of arrival times. This leads to the concept of an ensemble of simulations run with different seed values for the random selection process. Producing intuitive visualizations of these results is challenging. The method we use in this paper is maps indicating the probability of arrival of the fire. These maps show, for each grid cell, the proportion of simulations in which the front passed through that cell in a given time frame. As such, they can give an indication of the probability of the fire reaching a location at a given time.

Complex Fire Scenario with Variation

The Deans Gap fire burned within the City of Shoalhaven, New South Wales, Australia, for over a week in January, 2013 [START_REF] Mackie | Community Understanding and Awareness of Bushfire Safety: January 2013 Bushfires[END_REF]. It was a highly complex fire in terms of weather, fuel, and topography. Consequently, it provides an interesting scenario in which to demonstrate how the addition of variation can provide an increased understanding of expected spread. Our scenario focused on the first 24 hours, January 7th to 8th. Fire location data was obtained from the NSW Rural Fire Service. For these simulations the Dry Eucalypt Fire Model [START_REF] Cheney | Predicting fire behaviour in dry eucalypt forest in southern Australia[END_REF] rate of spread for Australian forest vegetation was used. This rate of spread model was chosen as it is the most suitable for the vegetation in the fire area. The domain was an 850 by 740 grid with a cell size of just less than 30 m. Total simulated fire time was 31 hours. Wind was a triangulation of data from the surrounding weather stations of Nowra, Ulladulla, Jervis Bay, and Goulburn. The variation in the wind had standard deviation 1 km/h and 10 degrees for speed and direction respectively. Fuel height was variable with mean 50 cm and standard deviation 30 cm. The surface fuel hazard score used in the model was 2, and near-surface fuel hazard 3.5. Maximum slope over which the fire was considered able to run was 40 degrees.

Simulation results for several times are shown in Fig. 4a. Results indicate a slow spread over the first 12 hours, which is the period over the evening and night. The fire picks up during the morning of the next day as the temperature starts to heat up. There is a further increase in spread rate in the afternoon, which is the hottest and driest time of day, as would be expected.

The concept of a probability of arrival map was applied to the Deans Gap scenario using 100 simulations run from different seeds, Fig. 4b. This map highlights that the addition of variation over a 24 hour period, from a known ignition location, has a significant impact on spread. Within the 10 minute interval possible front locations stretch almost four and a half kilometers. These results show how unpredictable the fire can be, and in which areas this variation is greatest. This has implications both educationally and operationally. It shows that the influence of common local environmental events can have an impact on the final spread, which the straight empirical models do not capture. Operationally, it provides an enhanced knowledge set to assist decision making.

Summary

We have provided a general introduction to SPARK, our bushfire prediction tool. The model uses a level set method for fast and simple spread propagation, combined with well-established empirical spread rates. The simple fire example demonstrated the use of a generic fire spread rate that incorporated curvature. SPARK has been developed with the goal of providing the functionality to easily incorporate, and hence investigate, additional complexities in the model. The use of a visual workflow tool such as Workspace has made this relatively straightforward to do. This is expected to be useful for researchers to determine the roles and importance of these complexities. The complexity considered here was the addition of variation into the environmental components. Applying this to a complex bushfire scenario has indicated that this variation over an extended period of time can introduce a large amount of uncertainty into the results. Highlighting this effect, and the areas in which it is most significant, could potentially provide a more well-informed information set to fire management.

Fig. 1 .

 1 Fig. 1. An example workflow. The panel on the far left shows a catalogue of available operations. Operations and connections are shown in the upper right panel. An example operation circled in green has its outputs displayed. The lower right panel displays the C code for the rate of spread model used in the bushfire solver operation, which is circled in red.

Fig. 2 .

 2 Fig. 2. A simple fire example. Simulated fire fronts (solid white line) are overlaid on fire imagery for the ignition configuration, left, and then at 25 seconds, right.

Fig. 3 .

 3 Fig. 3. The process by which fuel grids are populated. The left column focuses on the definition of multiple fuel types, the right column focuses on the incorporation of variation into the grid.

Fig. 4 .

 4 Fig. 4. Simulation results for Deans Gap; (a) A single simulation with the ignition point (yellow, top left) at 17:30 on January 7, and the simulation results for each subsequent 6 hourly interval finishing at 17:30 on January 8. Each new 6 hour interval is represented by a change in color, (b) Probability of arrival map for the time frame 17:20 to 17:30 on January 8. Red indicates a high proportion, and blue low, of simulations predicting the same arrival time in each cell.

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011

SPARK is currently being used to further investigate the effect of this variation. Future work will also be to consider the inclusion of wind and spotting models.