Emna Sellami-Kaaniche

Bernard De Gouvello
email: bernard.degouvello@leesu.enpc.fr

Marie-Christine Gromaire
email: gromaire@leesu.enpc.fr

Ghassan Chebbo
email: chebbo@leesu.enpc.fr

Evaluation of roofing materials emissions at the city scale: Statistical approach for computing roofing area distribution Evaluation des émissions des matériaux de couverture à l'échelle de la ville : approche statistique de calcul de la répartition des surfaces des toitures

Keywords: City scale, Representative sample, Roofing material, Statistical approach

Aujourd'hui, les matériaux de couverture sont considérés comme une source importante de contamination des eaux de ruissellement urbaines. Dans le cadre de la directive européenne sur l'eau (2000/60 CE), une évaluation des flux de contaminants issus des ruissellements des toitures est donc nécessaire à l'échelle de la ville. Or, en passant à l'échelle de la ville, on se confronte à la réalité d'une diversité très importante et difficile à quantifier les matériaux de couverture. Le but de ce papier est de résoudre la problématique « comment quantifier les matériaux de couverture à l'échelle de la ville ? ». Pour ce fait, nous avons développé une approche statistique basée sur deux étapes. La première étape utilise la théorie de l'échantillonnage qui a pour but de définir la bonne taille de l'échantillon à tirer qui représente la proportion R (%) de la surface totale de toute zone urbaine à étudier. Pour déterminer la valeur de R (%), nous avons calculé et analysé les erreurs absolues E a . Cette analyse montre qu'un tirage avec remise de R=4% de la zone d'étude donne de bons résultats. La deuxième étape consiste à appliquer la théorie d'estimation. En effet, après avoir déterminé la proportion R (%) d'échantillonnage, nous allons estimer les caractéristiques inconnues d'une autre zone en tirant un échantillon représentant R(%) de la surface totale de la zone étudiée. La validation de la taille d'échantillonnage a été effectuée sur deux zones de caractéristiques différentes.

INTRODUCTION

Roofing materials are considered as a major source of urban runoff metal contamination. This observation was revealed by several research programs conducted since the 1990s [START_REF] Förster | Patterns of roof runoff contamination and their potential implications on practice and regulation of treatment and local infiltration[END_REF][START_REF] Gromaire-Mertz | Characterisation of urban runoff pollution in paris[END_REF][START_REF] Wallinder | The influence of patina age and pollutant levels on the runoff rate of zinc from roofing materials[END_REF]. Further undergoing research aims at extending runoff rates at the city scale [START_REF] Robert-Sainte | Contribution des matériaux de couverture à la contamination métallique des eaux de ruissellement[END_REF][START_REF] Gromaire | -Zn and Pb emissions from roofing materials-Modelling and mass balance attempt at the scale of a small urban catchment[END_REF]. The roof area estimation is a fundamental input for evaluating roofing materials emissions. However, at the city scale, the information concerning roofing materials and their surfaces on an urban district does not exist currently in urban data banks. Some methods have already been developed for the evaluation of roof surface on a large-scale, in order to study building-integrated solar-energy applications [START_REF] Izquierdo | A method for estimating the geographical distribution of the available roof surface area for large-scale photovoltaic energy-potential evaluations[END_REF][START_REF] Bergamasco | Scalable methodology for the photovoltaic solar energy potential assessment based on available roof surface area: Application to Piedmont Region (Italy)[END_REF] or to explore the potential of green infrastructure in adapting cities for climate change [START_REF] Gill | Adapting Cities for Climate Change: The Role of the Green Infrastructure[END_REF]. But, in these studies, the roofing materials were not taken into account. Other approaches (Le [START_REF] Bris | Classification of roof materials for rainwater pollution modelization[END_REF][START_REF] Gromaire | Incidence of zinc roofing on urban runoff pollutant loads: The case of Paris[END_REF] have evaluated roofing materials surfaces using data obtained from aerial photographs and image classification software. The classification method based on aerial images was applied to an urban catchment with 2.25 km² of surface (Le [START_REF] Bris | Classification of roof materials for rainwater pollution modelization[END_REF]. The obtained results show about 75% of well classified roofing surfaces. Nevertheless, this classification method presents some limitations especially in terms of confusion between different classes (eg: zinc in the shadow and slates in the sun). On the other hand, in order to apply this method, we need a high resolution image which requires an expensive cost and it is not usually available in every study site. Therefore, a method must be developed to estimate roofing materials distribution at the city scale. Ideally, a method to calculate the roofing materials surfaces should: (a) be accurate; (b) be reliable, with the possibility of computing or bounding the error of roofing materials areas estimation; (c) be inexpensive (low cost); (d) require few, global, available and standard input data; (f) produce geo-referenced results; (g) be scalable from local to global scales.

Given the size of the city, a complete census of the roofing material surfaces was unfeasible. Instead, a stratified random sampling technique was employed in conjunction with aerial photograph interpretation of surface roofing materials types. It is preferable to divide the city into distinctive homogenous strata in order to accurately characterize it. Stratified random sampling ensures that results can be extrapolated to the city level and is suitable for a heterogeneous population. Dividing a city into fairly homogeneous units reduces the variance of the estimates, thereby leading to more precise results [START_REF] Nowak | The Urban Forests Effects (UFORE) Model: Field Data Collection Manual[END_REF].

Several considerations must be made in order to compute the roofing materials surfaces area. In fact, the choice of roofing material is extremely dependent on the history of the building (age, renewal), the urban planning (land use, building typology...), the social characteristics, the town regulation framework… For instance, in a previous work (Sellami-Kaaniche et al, 2012), a set of rules have been developed for identifying the use of a roofing material at the city scale and have applied these rules to Créteil city. New maps of this city were then obtained from which homogeneous strata have been defined for identifying the distribution of roofing materials using a statistical approach.

In this work, a methodology based on a statistical approach to compute an estimation of roofing materials area distribution for a stratum is described. The methodology is applied to Créteil city (France). The data are processed with the aid of a Geographical Information System (QGIS) and Matlab was used to implement the statistical approach.

The remainder of this paper is organized as follows. In section 2, we describe the study site and the databases used. Then the developed methodology for computing roofing materials data is addressed in section 3. In section 4, experimental results are presented and discussed, and finally some conclusions are drawn in section 5.

CASE STUDY SITE

Urban Characterization

The goal of our research work is to develop a general method to quantify roofing material surfaces at the city scale. In this context we need to choose a case study to achieve two objectives. The first one is to validate the methodology. The second one is to make it possible to apply the methodology to other cities. Therefore we need to choose a complex site in which we try to have the different aspects of the city. In fact, the city should present a sufficient urban diversity. The selected city is Créteil (Department 94) located about 10 km from Paris (France). Créteil has 89 304 inhabitants (INSEE, 2008) distributed over 11.5 km² which represents a reasonable size for our research. This city is divided into four major historical urban areas: Old center, Mont Mesly, New Creteil I, New Créteil II. Each area presents a specific urban organization which depends especially on the period of construction (PLU, 2010). The recent zone is New Créteil II. Figure1.b shows the interesting urban and functional diversity of Créteil. In fact, we can see different land use represented by different color: industrial activities located nearby, health equipment, different types of building (apartment, individual houses). The land use is not homogeneous in the different urban areas of the city. For example the Old center mainly consists of individual habitat. However Mont Mesly is composed of collective habitat. This distribution is mainly due to historical factors. Finally, Créteil is easily accessible from the laboratory.

Databases

Créteil city presents a big diversity and a large number of buildings which represents an area of 6.18 km ², about 54% of the city area. To quantify the different roofing materials, urban data banks (cadastre), land use database MOS-IAU1 (IAU-IDF, 2008) have been consulted and interviews have been conducted with various actors and stakeholders (eg: master of work, contracting authority, architect). These contacts showed that informations relating roofing materials and their surfaces on an urban district does not exist currently in urban data banks. Therefore, in a previous work (Sellami-Kaaniche et al, 2012), we have developed a set of rules for identifying the use of a roofing material at the city scale. These rules have been applied to Créteil city. In this work, we have associated different databases for Créteil: land use database MOS-IAU, images database BD-topo2 and BD-ortho3 (IGN, 2008). The obtained results correspond to two maps of Créteil city (see Figure 1).

Issue

By overlaying these two maps (Figure 1), we consider that each building class in Figure 1.b located in an area of the Figure 1.a is a homogeneous urban area in terms of building types and the historical location. We define homogeneous urban area as an area representing specific probabilities of roofing material distribution. In this context, the question that arises is: "How to evaluate the roofing materials distribution for each homogeneous urban area?"

METHOD FOR ROOFING MATERIALS AREA ESTIMATION, AND APPLICATION TO CRÉTEIL

In this section, we focus on describing the method of evaluating the roofing materials distribution for a stratum. We define a stratum as a building class in Figure 1.b located in an area in Figure 1.a. For each stratum we are looking to evaluate the proportion p i of each material i.The proposed methodology is explained through its application to Créteil. To solve the previous problem, we propose to apply an inferential statistic which aims to extend the observed sample properties to the entire population and to validate or invalidate hypotheses made a priori or after an exploratory phase [START_REF] Saporta | Probabilités, analyse des données et statistiques. Editions technip[END_REF].

The method developed is based on two steps. The first step is the sampling theory which aims at determining the number of samples n r which is required for all existing materials in a stratum. This step involves taking a stratum with known characteristics area (N (m²)), proportion of different existing materials (p i (%)), which allows us to make the sampling. To make a choice of an optimized sample size, absolute error E a has been computed. The second step is the application of the estimation theory. Indeed, after determining the number of required samples n r , we determine the proportion R = n r /N and then we estimate the unknown characteristics of a population by selecting a sample representing R (%) from the total population area. To validate this proportion R (%) we have tested two other stratums with different characteristics.

In what follows, we will use the different symbols defined in table 1.

Table 1 : Symbols definition

Sampling Strategy-Monte Carlo simulation

The chosen stratum is zone 1: the individual houses class (Figure 1.b) located in area (1) (Figure 1.a).

For this zone we have associated, with QGIS, the different previous maps with BD-topo and BD-ortho images and we have obtained a database T of existing buildings (numbered 1…N b ) and their roofing materials (see Table 2). For each building, roofing material has been identified by looking to the orthophoto. From this database we have identified the roofing materials distribution for zone 1 (see Table 3).

To study the impact of sampling on the roofing materials proportions uncertainty, we have used a Monte Carlo simulation. To perform this study, samples should be representative. In fact, it is necessary that each element of the zone has an equal chance of belonging to this sample. Thus, a random sampling technique of independent individuals of 1 m² from a population composed of the total roofs surfaces areas (N (m²)) was employed. In this case, the observations become random variables following a probability law that will be identified [START_REF] Saporta | Probabilités, analyse des données et statistiques. Editions technip[END_REF]. The random variable is the roofing material. Each sample has a statistical parameter: the proportion p e,i of each material i for which related statistical law has to be defined.

To proceed, a number of samples n (individuals of 1 m²) (where n ≤ N) was randomly generated among the surface N (m²). To generate each sample n, a variable r between 1 and C b (see Table 1) has been generated (with and without replacement, the final choice of the draw strategy is defined in confidence interval E a (%) absolute error r a value selected in an uniform random variable between 1 and C b section 4.3). Then, in table 1, for each value r we seek (in the column of cumulative area) for the first surface greater or equal to r and we identify the roofing materials corresponding to that surface. Finally, we obtain the proportion for each material for each sample. The process is repeated k times for each value of n (the choice of k value is defined in section 4.1).

For each material, we plot the different statistics of its distribution (the mean, maximum and minimum values, confidence interval at level of 95% computed using the method of percentiles) and for the two draws (repeated k times) with and without replacement. We also plot the actual distribution for each material to be compared with the simulation results. In addition, we have verified, using the Shapiro-Wilk normality test at the 5% threshold, that for n ≥ 2, the normal distribution of each material is readily accepted. Finally, we have determined from the different value of n the number of samples n r which is required for all roofing materials. This was being done for each material.

Estimation

The objective of this section is to describe the method of estimating roofing materials distribution (p i : proportion of material i) in a given zone by sampling (see Figure 2). For this purpose, we need to apply the Theorem for Proportions [START_REF] Saporta | Probabilités, analyse des données et statistiques. Editions technip[END_REF] in which the sampling distribution for samples (with size n ≥ 30 and p e,i : proportion of material i in the sample is approximately normal, so :

           n p p p N i i p i i ) 1 ( ; p i e,



The point estimate of p i is p e,i and an estimation of standard error is given by: choose the number of samples n r and the draw strategy. Thus, we have compared the different statistics computed for each draw (with and without replacement) with statistics related to the Theorem for Proportions. In fact, we have applied this theorem for zone 1 with the same previous conditions.

n p p i e i e p i ) 1 ( , ,    A confidence-

RESULTS AND DISCUSSIONS

The number of draws

To choose the required k value for each value n, we have tested some arbitrarily values of k for different values of n. The illustration was made for clear tile material as an example (see Figure 3). In this Figure, from k=1000 upwards, the different computed statistics (mean value, confidence interval) become stable. In what follows, we have kept k=1000.

Analysis of sampling simulations

Sampling simulations with and without replacement were applied. In Figure 4, confidence intervals, the mean, maximum and minimum value and the actual proportion for clear tile material are illustrated.

As we can see in Figure 4, the mean computed over 1000 draws (with and draw without replacement) for each sample n coincides with the actual proportion of the clear tile. This observation confirms our choice of k=1000 and shows that the sampling strategy represents the reality of the roofing material distribution in zone1. This result was validated for all roofing materials (slates, steel, dark tile…).

Sampling strategy choice

The comparison of the different statistics computed for each draw (with and without replacement) with statistics related to the Theorem for Proportions, shows that the mean values computed from the theorem coincide with those calculated for each draw. The illustration was made for the slates material as an example (see Figure 5). Theoretically, the draw with replacement is used to ensure that each independent element of the population has an equal chance of belonging to the sample. Figure 5 shows that the sampling simulation results obtained from the draw with replacement (dotted red line (-)) coincide with those of the Theorem for Proportions (solid blue line). In addition, for n ≤ 250, limits of the confidence interval for the two draws (with and without replacement) coincide with those of the Theorem for Proportion. However, for n>250 the limits of the confidence interval for the draw without replacement (green point in Figure 5) do not coincide with those of the theorem. Therefore, draw without replacement could be used only for n<<N.

In what follows, for the estimation method, the draw with replacement will be elaborated.

The sample number choice

The objective of this section is to determine the number of samples n r which is required for all roofing materials. Table 4 shows that sample size greatly varies from one material to another for the same confidence interval. In fact, to obtain a confidence level of ± 20% for clear tile, we need a sample of 182 m², whereas for steel, we need n=5250 m². This large difference can be explained by the actual roofing material distribution in zone 1. Indeed, table 3 shows that clear tile represents 33.7 % of the zone 1 area while steel represents only 2%.

In this context, absolute error E a was computed for each material. This error is the result of the multiplication of confidence interval obtained for each n with the real proportion of the material i. Results are obtained in Figure 6. Figure 6 shows the evolution of the absolute error E a with the sample size for each roofing material. The analysis of the shape of the different curves shows that the zone Z is a critical zone for the E a evolution. In fact, for the left hand side of the zone Z (n≤n -), E a fluctuations become much more important when fewer samples have been taken. However, for the right hand side of the zone Z (n≥n + ), E a has progressively stabilized. We can observe that when E a is very low, the roofing material proportions are closer to the real distribution. Therefore, the range of acceptable sample size is the range n -for n + corresponding to a range of absolute errors between 1% and 7% for all roofing materials. From this range, we choose n r =250 m² (a value in the middle of zone Z) as the required sampling size. In fact, for n values close to n -, absolute error is very high and for n close to n + , the sampling size becomes important. In addition, we look to optimize this size. Thus, we define n r representing R=4% of the zone area as the size sampling needed. For this size we get a confidence level ≤ 30% for the roofing materials with high densities but absolute error low values (see Table 5).

Estimation and validation of the sampling size

In this section, we firstly describe the operational method for roofing material distribution estimation in an unknown area. Then, we will validate the choice of sampling size by estimating roofing material distribution in two new stratums (zones 2 and 3). In each stratum, we have identified the real roofing material distribution as described in section 3.1 for zone 1. For each zone, a random sample representing R=4% of the zone area was generated with replacement. The sampling strategy is based on randomly generating independent individuals of 1 m² representing 4% of the stratum roofs area (N (m²)). Each 1 m² belongs to a specific building with specific roofing material. So, we obtain two databases, the first one is a database of different buildings (with their roof surface) existing in the stratum, and the second one is composed of the selected surfaces for each building in the sample. By associating BD-topo and BD-ortho we identify its roofing material. Therefore, we compute for each material i:

-in the stratum (area (N (m²)): surface area of each material i and the proportion of different existing materials (p i (%)), -in the sample e representing 4% of the stratum area (N) : surface area of each material i and the proportion of materials (p e,i (%))

Finally, we have computed the confidence interval, and the absolute error values (see table 6 and7).

The two zones 2 and 3 are described as follows: 6 and7 show that E a absolute error values are low for the two zones. It is also less than 1% for all roofing material. The computed confidence level is very low for roofing material distribution with high density, this is the case of flat roof with 92% of real proportion in zone 2 and 87% in zone 3, we get a confidence level ≤ 1% so a high precision. For material with confidence level ≥ 30%, E a is still low and their real proportions do not exceed 2% in the whole zone 2 or 3. This indicates that the results gained through this method are truly representative and can be used with confidence.

CONCLUSIONS

In this paper we have developed a statistical method to quantify roofing materials distribution at the city scale. Given the size of the city, a stratified random sampling technique was proposed. We have divided the city into distinctive homogenous strata. In this paper, we have focused on describing the statistical approach to evaluate roofing materials distribution for a stratum. This method is based on two steps. The first one is the sampling theory which aims to determine the number of samples n r required for all roofing materials. The second step is the application of the estimation theory. Indeed, after determining the number of samples n r , we determine the proportion R = n r /N and then we estimate the unknown characteristics of a stratum by generating a sample representing R (%) from the total area of the new stratum. To validate this proportion R we have tested two other stratums with different characteristics. The obtained results show that a random sample representing R=4% of the zone area could be drawn from the available population with and without replacement. In fact, we consider that a sample representing 4% of the whole stratum area is very small, thus the draw without replacement could be used. Then, the estimated roofing material distribution of the zone will be established by applying theorem for proportions. Thus, we will obtain an estimation of each roofing material proportion by computing the confidence interval.

The object of our future study is to evaluate the roofing materials distribution for the entire city. Firstly, the city should be divided into fairly homogenous urban areas, and each urban area represents a stratum. Then, for each stratum (with known area) a sample representing R=4% of the stratum area is randomly generated. After that, using GIS software we associate different maps BD-topo, BD-ortho and the map of strata to identify the roofing material sample generated for each stratum. Finally we obtain the roofing materials proportions and their confidence intervals.

Figure 1 :

 1 Figure 1 : (a) Material distribution map (b) Building class map The first map represents the roofing material distribution (see Figure 1.a). Each color represents an area with the same material distribution. The second one is a building class map (see Figure 2.b) established from reorganizing the MOS-IAU database. Each color represents a building class. These maps are the basis of the statistical approach.

Figure 2 :

 2 Figure 2 : (a) Créteil city divided into homogeneous stratums; (b) Estimation strategy for a stratum

Figure 3 :

 3 Figure 3 : k value variability-case of Clear tile and for n = 30

Figure 4 :

 4 Figure 4 : Computing statistics for the clear tile material for the two draws strategies -Zone1-

Figure 5 :

 5 Figure 5 : Comparison computed statistics for draws with replacement and without replacement with computed statistics for the Theorem for Proportions -Slates case -

Figure 6 :

 6 Figure 6 : E a variability for different samples sizes for each material

  N 2 =81100.11 m²): apartment class (Figure1.b) located in area (2) (Figure1.a) -zone 3 (N 3 =105304.04 m²): secondary activity class (Figure 1.b) located in area (2) (Figure1.a) Table

Table 2 :

 2 Urban database for zone 1

	Table 3 :

  level coefficient of α= 0.05 has been chosen and therefore: Before applying this theorem in a given zone to estimate its roofing material distribution, we need to

		Building	Area (m²)				Cumulative area (m²) Roofing material (i)
		1	S 1 =100					C 1 =100			Clear tile
	T	2	S 2 =40					C 2 =S 1 + S 2 =140		Slates
		…	…											…						…
		N b	S	N	b							C b 	N
			Material							Area (m²)				Proportion p i (%)
			Clear tile						2107.05						33.68
			Dark tile						1228.71						19.64
			Slates							889.67							14.22
			Zinc								833.95							13.33
			Flat roof						983.38							15.72
			Steel								116.58							1.86
		Other material				97.50								1.56
			Total (N)						6256.84						100.00
			i p			e p	,	i		. 96 , 1 	p	,	i	,	e p	,	i		. 96 , 1 	p	,	i	

Table 4 :

 4 Computed confidence interval for each material for different sample size value

				CI confidence interval (±) (%)
	Material Sample size (n) (m²)	Clear Tile	Dark Tile	Slates	Zinc	Flat roof	Steel	Other material
	100	28	42	40	43	44	111	168
	300	15	23	26	30	23	75	76
	600	12	15	19	18	17	60	60
	3000	5	6	9	8	9	26	28
	6000	4	5	6	6	6	17	20

Table 5 :

 5 E a value for n r =250

n=250 m² Clear Tile Dark Tile Slates Zinc Flat roof Steel Other material E a (%)

		18
		16							Clear Tile
		14							Dark Tile
									Slates
		12							Zinc
	Ea (%)	8 10							Flat roof Steel Other material
		6
		4
		2
		0 0	100	200	300	400	500	600	800 1000 1500 2500 4500 7000
						Sample size (n)
	6.37		4.79		4.05		4.14	4.65	1.36	1.24

Table 6 :

 6 Results obtained for zone 2

Table 7 :

 7 Results obtained for zone 3

IAU: Institut d'Aménagement et d'Urbanisme d'Ile-de-France: institute of planning and development for the Greater Paris region.

BD-Topo is a database for Topographic Information IGN roughly corresponding to the traditional content of the map at 1: 25,000, with a much higher precision of the order of 1:10000 or 1:5000, made from an aerial image. These images define only the built by masking inbuilt areas (roads, gardens ...).

BD-ortho images come from IGN's (Institut Géographique National) which contains digital colour ortho-photos with three or four (red-green-blue-near infrared) bands and with a 50 cm ground resolution

ACKNOWLEDGEMENTS

This study has been conducted as part of the OPUR research program. The authors gratefully acknowledge the Centre Scientifique et Technique du Bâtiment (CSTB) for their financial support and Ali Hannouche for his helpful suggestions in the statistical approach.


Jilles S Dibangoye
email: gdibango@ift.ulaval.ca

Guy Shani
email: guyshani@microsoft.com

Brahim Chaib-Draa

Abdel-Illah Mouaddib

Topological Order Planner for POMDPs

Over the past few years, point-based POMDP solvers scaled up to produce approximate solutions to mid-sized domains. However, to solve real world problems, solvers must exploit the structure of the domain. In this paper we focus on the topological structure of the problem, where the state space contains layers of states. We present here the Topological Order Planner (TOP) that utilizes the topological structure of the domain to compute belief space trajectories. TOP rapidly produces trajectories focused on the solveable regions of the belief space, thus reducing the number of redundant backups considerably. We demonstrate TOP to produce good quality policies faster than any other pointbased algorithm on domains with sufficient structure.

Introduction

POMDPs provide a powerful framework for planning in domains involving hidden states and uncertain action effects. While exact solvers can only handle small domains [START_REF][END_REF], approximate methods have shown the ability to handle larger problems. A well known approach for computing approximate solutions is the point-based method [Pineau et al., 2003a]. Point-based algorithms compute a policy using point-based backups (updates) over a finite subset of reachable belief states, hoping that the computed policy will generalize well to other, unobserved beliefs.

In many cases, real world environments contain much structure. Indeed, several forms of structure have been investigated in the past [START_REF] Shani | [END_REF]Pineau et al., 2003b]. Algorithms that take advantage of such structure can solve structured problems much faster than generic algorithms.

While generally it is possible for an agent to move back and forth between world states, in many cases effects of actions cannot be undone. In a manufacturing plant, for example, robots may glue together two components. After the components are glued, it is impossible to "unglue" them. Thus, transitions into the state where the components are glued cannot be traversed backwards. In such cases we can divide the problem state space into layers -groups of states; the agent can move between each two states of a layer; when the agent leaves a layer, it cannot return to it. We call this a topological structure [START_REF] Dai | [END_REF][START_REF] Bonet | Faster heuristic search algorithms for planning with uncertainty and full feedback[END_REF]Abbad and Boustique, 2003] and say that a problem has much topological structure when the problem state space has many layers. These characteristics are embodied in many real-world applications including assembly line optimization; network routing; or railway traffic control. Consider the assembly of a car that consists in multiple steps: first the car moves to the engine installation; then the engine installation crew checks for malfunctions; thereafter finishing the engine installation the car moves respectively to the hood and the wheel stations. Each transition from a station to another is preceded by a quality measurement procedure that prevents car malfunctions. Whenever malfunctions perceived by noisy sensors occurred the car is sent back to the former station. However, once a car has been properly assembled it is never disassembled. In this paper, we aim at tackling real-world applications that yield such a significant topological structure.

Given such topological structure a point-based algorithm can focus its attention on subsets of the belief space where the value function can be improved, reducing the number of redundant backups. Indeed, generic point-based algorithms execute in many cases a very large number of backups that result in no improvements to the value function [Pineau et al., 2003a;[START_REF] Smith | [END_REF][START_REF] Shani | [END_REF]. As the point-based backups lie at the core of a point-based algorithm, reducing the number of executed backups can speed up an algorithm considerably.

In this paper we present the Topological Order Planner (TOP) that uses the topological order of the underlying MDP to find good belief space trajectories. TOP groups together states into layers, creating an acyclic layer graph. Layers are solved in reversed topological order, starting with layers that contain goal states. Belief space trajectories are directed towards the solveable layers of the model. Once a layer has been solved, trajectories that reach that layer can be terminated, resulting in shorter trajectories and thus -less pointbased backups. Before choosing TOP we should first check whether the domain contains multiple layers. When the domain does not contain such structure, choosing other pointbased algorithms is reasonable. However, when the domain contains a significant topological structure, TOP will outperform other point-based algorithms.

We describe the family of topological solvers and explain when such a solver is expected to compute an optimal policy. We then suggest a specific instance of this family, explaining the difficulties in implementing the various parts of the algorithm in a POMDP context. We provide an extensive experimental study of our algorithms in environments with different levels of topological structure, showing how our algorithm gains more power as the number of layers grows.

Background and Related Work

We begin with an overview of Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs). We then discuss the point-based approach to solving POMDPs, focusing on trial-based algorithms in this family.

An MDP is a tuple (S, A, T, R, γ) where: S is a discrete and finite state space; A is a discrete and finite action space; T (s ′ |s, a) is a function of transition probabilities, i.e., the probability of transiting from state s to state s ′ when taking action a; R(s, a) is a real-valued reward function, that defines the outcomes received when taking action a in state s; γ is a discount factor.

A POMDP is a tuple (S, A, T, R, Ω,O,γ,b 0 ) where: S, A, T, R are the same as in an MDP; Ω is a discrete and finite set of observations; O(o|s ′ ,a) is the probability of observing o after executing a and reaching state s;Abelief state, describes the probability distribution over states, providing a sufficient statistic for a given history. b 0 defines the initial belief state, i.e., the agent belief over its initial state. The next belief state, denoted b ′ = τ (b, a, o), that incorporates the latest action-observation pair (a, o) and the current belief state b, is updated as follows: Given a POMDP, the goal is to find a policy, mapping histories or belief states to actions, that maximizes some aspect of the reward stream, such as the average discounted reward (ADR). A popular approach to computing such policies is by computing a value function that assigns values to belief states. A value function V can be represented as a set of α vectors, i.e.,

V = {α 1 ,α 2 , ••• ,α m } , such that: V (b)=max i α i • b.

Point-Based Value Iteration

It is possible to compute an optimal value function for the entire belief space through iterative complete backups [START_REF][END_REF]. However, the number of α-vectors generated by complete backups is exponential in the horizon of the problem -the number of steps required to achieve a reward. As such, exact computation of the value function does not scale beyond small toy problems.

However, V can be iteratively improved using backup operations over specific belief points, known as point-based backups [Pineau et al., 2003a;[START_REF] Spaan | [END_REF][START_REF] Smith | [END_REF]:

g α a,o (s)= s ′ O(o|s ′ ,a)T (s ′ |s, a)α(s ′ ) (3) g b a = r a + γ o arg max g α a,o : α∈V (b • g α a,o ) (4) backup(b) = arg max g b a : a∈A (b • g b a ) (5)
where r a (s)=R(s, a) is a vector representation of the reward function.

Instead of computing an optimal value function over the entire belief space, we can compute V only over a finite subset B of belief states [Lovejoy, 1991]. As a result, the backup operator is polynomial and the complexity of the value function is bounded by the number |B| of belief states. This method yields good policies if an optimal value function over B may generalizes well other belief states. To collect good belief subsets, point-based algorithms collect only belief states that are reachable from the starting belief state b 0 [Pineau et al., 2003a]. Techniques of this family differ on the method used to collect the reachable belief states and the way they order the point-based backups on the collected beliefs.

One approach to collect belief states is the trial-base approach [START_REF] Bonet | Faster heuristic search algorithms for planning with uncertainty and full feedback[END_REF], in which an algorithm executes a trajectory in the belief space, usually starting from b 0 . Trial-based algorithms iteratively compute such a trajectory, execute backups on the belief states in the trajectory, and then compute a new trajectory. The algorithm therefore needs only remember the beliefs of the current trajectory, but can still compute a value function for many belief points.

Of this family of algorithms, heuristic search value iteration (HSVI) has demonstrated an impressive performance on a number of larger domains [START_REF] Smith | [END_REF]. HSVI creates trajectories based on an upper bound and a lower bound over the value function, denoted V and V respectively. Each such trajectory starts with the initial belief state b 0 . HSVI always executes the best action specified by the upper bound, and then selects the successor belief state, which maximizes the gap between the bounds. Once the trajectory is finished, the belief states are updated in reversed order (Algorithm 1).

HSVI generates good trajectories, especially after the bounds become reasonably tight, but the maintenance of the two bounds incur considerable overhead. Hence, the gain resulting from the reduced number of backups does not fully manifest in the total execution time.

The Forward Search Value Iteration algorithm (FSVI [START_REF] Shani | [END_REF]) uses the underlying MDP Q-value function as a heuristic to traverse the belief space (Algorithm 2). Through the traversal, it maintains both the underlying MDP state s and the belief state b, selecting actions based on the current state and the MDP Q-value function. FSVI proceeds then by selecting the next state s ′ and observation o by sampling them from T (•|s, a) and O(•|a, s ′ ) respectively. The advantage of FSVI is that the overhead of computing the MDP Q-value function is negligible and so is the action selections.

One major drawback of FSVI is its inability to recognize traversals that will improve its state information. In fact, by Algorithm 1: The HSVI algorithm.

begin initialize V and V while V (b) -V (b) >εdo EXPLORE(b0, V,V) end EXPLORE(b, V,V) begin if V (b) -V (b) >εγ -t then a * ← arg max a Q V (b, a) o * ← arg max o ( V (τ (b, a, o)) -V (τ (b, a, o))) EXPLORE(τ (b, a * ,o * ), V,V) add( V , backup(b, V )) V ← HV (b) end Algorithm 2: The FSVI algorithm. begin Initialize V repeat Sample s0 from the b0 distribution MDPEXPLORE(b0,s0) until V has converged end MDPEXPLORE(b, s) begin if s is not a goal state then a * ← arg max a Q(s, a) Sample s ′ from T (•|s, a) Sample o from O(•|a * ,s ′ ) MDPEXPLORE(τ (b, a * ,o),s ′ ) add(V, backup(b, V )) end
making use of the optimal Q-value function of the underlying MDP, FSVI limits its ability to create traversals that will visit states that may provide useful observations. Also, FSVI uses a static policy for generating traversals that ignores the current value function. As a consequence, FSVI results in a sub-optimal value function (over visited beliefs) in certain domains.

Both FSVI and HSVI backup the entire path that was explored. It is possible that many of these backups will result in redudant α vectors, mostly because the value of the successor beliefs did not change. As we will later show, on most benchmarks, the number of these redundant backups far outnumber the number of backups that result in useful α vectors.

Topological Structure

In many realistic domains, some actions could not be reversed. That is, once an agent has executed an action that took it from state s to state s ′ , it can no longer go back to state s.

Example 1 A factory may have an assembly line, where products must go through multiple stations. At each station, one or more components are being added to the prod-uct. While there is some partial order required, since some stations must precede other stations, in other cases the order of stations is not important. It is possible, that a product may reach a station with a malfunction, and gets sent back to a former station for repair, but once a station has properly assembled its components, they are never disassembled. The assembly management system can therefore balance the workload by directing products towards free stations. Assuming that components are never disassembled from the product, this domain has a significant topological structure.

Given the topological structure we identify sets of states that we call layers. A layer is a strongly connected component -the agent can move back and forth between any two states that belong to the same layer, but once the agent has left a layer, it can no longer go back to it. The layers of states can be organized as a DAG, where there is an edge from layer S i to layer S j if there exists some state s i ∈ S i ,an action a, and a state s j ∈ S j such that T (s i ,a,s j ) > 0. Indeed, several successful attempts were made in the past to use this topological structure of the state space to speed up MDP solvers [START_REF] Dai | [END_REF][START_REF] Bonet | Faster heuristic search algorithms for planning with uncertainty and full feedback[END_REF]Abbad and Boustique, 2003].

A topological structure in the MDP state space induces a topological structure in the belief space. For example, let b be a belief with non-zero probabilities for some states in a layer S i , and all the probabilities of states belonging to layers that are parents of S i are zero. Let b ′ be some successor (not necessarily immediate) of b that has zero probabilities for states in S i . Then, while the agent can move from b to b ′ , it cannot go back from b ′ to b.

However, as the belief space is infinite, we cannot detect the strongly connected components (layers) of the belief space. There is also no direct mapping from the layers of the belief space into the layer of the state space. Indeed, it is possible for a belief to have non-zero probabilities over states that belong to various layers. Therefore, the belief space has more layers than the MDP state space. In some cases, it is even possible that the number of layers in the belief space will be infinite.

Topological Order Planning

Given the layers of the state space (or the belief space), a solver can exploit this information to update states (or beliefs) in a smart order. Cycles in the state space force value and policy iteration algorithms to repeatedly update the value of the same state, until convergence. In our case, cycles exist only within a layer. However, the layer structure is by definition acyclic. As such, we can solve each layer only once.

To define the correct order by which layers should be solved, we introduce the notion of solved layers and solveable layers. A layer S i is solved if for each state s ∈ S i , V (s) is within ǫ of its optimal value. Thus, the value of all states in a solved layer cannot be further improved. A layer S i is solveable if it does not have any successors, or if all of its successor layers are already solved. A topological order solver executes updates only on states in the solveable layers, because backups on solved layers cannot improve the value function. Backups on other non-solveable layers may not be final -these layers need to be revisited after their successor layers have been solved.

When the domain has goal or terminal states -absorbing states that the agent cannot leave -these states are forming single state layers. These layers are always solveable.

Theorem 1 A topological order solver, that updates only states in solveable layers, converges to an ǫ optimal value function if:

1. Each layer becomes solveable throughout the algorithm. 2. Each solveable layer eventually becomes solved.

Topological Order Planner for POMDPs

In a POMDP, because we cannot compute the topological structure, an implementation of the pure topological solver requires some approximations. A POMDP topological solver requires a number of key components:

• Identifying that a layer is solved.

• Identifying that a layer is solveable.

• Finding beliefs that belong to solveable layers.

Below, we explain the challenges and suggest solutions to all of these components.

Our approach is motivated by the trial-based, point-based, family of POMDP solvers. We execute traversals in belief space towards the solveable layers, and update only beliefs that belong to solveable layers.

Identifying Belief Space Layers

As we explained above, it is impossible to identify the layers of the belief space in the general case. We will therefore map the layers of the POMDP onto the MDP layers. We do so by running trajectories in both belief space and state space at the same time, as was done by the FSVI algorithm. Throughout the trajectory we generate pairs of states and beliefs. We say that a pair (s, b) belongs to a layer S i if s ∈ S i . This approach is only an approximation of the true belief layers. First, it may be that a single belief will be a part of multiple layers, associated with different MDP states. Second, this method maps many different belief layers into the same MDP layer. However, as we will later show, this approximation is very useful in practice, and allows us to estimate whether a belief belongs to a solveable layer.

Formally, a layer S i is solved, if for every state s ∈ S i , and every belief b such that b(s) > 0, the value that b can gain from state s cannot be improved. That is, if V is the current value function, and V * is the optimal value function, let

α b = max α∈V b • α and α * b = max α∈V * b • α, then α b (s)=α * b (s).
We introduce s.SOLVED as a means of checking whether state s and its corresponding layer S i are solved.

While the above is correct, we cannot check every b that has a non-zero probability on a single state s because the number of such beliefs is infinite. We overcome this by maintaining an estimate on whether beliefs associated with a state can be further improved. For each state s we maintain p(s) which is an estimate of the potential improvement to beliefs associated with s. We initialize p(s) = max a R(s, a). Each time a belief associated with s is updated, we set p(s)=0 .

When a backup for a belief b associated with s ′ generates a new α vector that improves the value of s ′ by δ, we iterate over the predecessors of s ′ . For each predecessor s of s ′ ,we set p(s) = max{δ • T (s ′ |s, •),p(s)}. Thus, a state, and all its associated beliefs, are considered solved, when all its successor states and their associated beliefs have been solved. This describes the UPDATE procedure, see Algorithm 3.

Traversing the layers

TOP is a trial-based algorithm, that is, TOP executes traversals in belief space, and afterwards updates beliefs that were observed during the traversal in reversed order. As we are interested only in the solveable layers, we need to create reachable trajectories within these layers. To achieve that, we traverse both the MDP state space and the POMDP belief space together, as was suggested by the FSVI algorithm.

Before the trial begins we choose a start state s 0 randomly and a goal state s g reachable from s 0 for the current trajectory. When there are no solved layers, the goal state can be either a terminal state of the domain, if such a state exists, or any other state of a solveable layer otherwise. After layers have been solved, we choose a goal state from one of the solved layers that is reachable from the selected start state.

Our trials move from the start state to the goal state using the most likely path in MDP state space. We use the Floyd-Warshal algorithm, that computes maximum weight paths in graphs to find the path for us. As we do not select action outcomes stochastically, this method assures that every traversal will end at the goal state.

During the traversal we maintain the observed state-belief pairs. Once the traversal ends, we execute backups in reversed order. However, we limit the value function updates only to state-belief pairs that belong to a solveable layer.

After the update is completed, we check whether the solvable layer we have visited became solved. If all the states in that layer have a potential improvement p(s)=0 , we conclude that the layer is solved. Otherwise, the layer remains solvable. The algorithm is terminated when all the layers become solved.

Algorithm 3: Topological Order Planner for POMDPs. until V has converged end

TOPTRIAL(s, sg,b) begin if ¬s.SOLVED then s ′ ← PICKNEXTSTATE(s, sg) a ← PICKACTION(s, s ′ ) o ← PICKNEXTOBSERVATION(s ′ ,a) TOPTRIAL(s ′ ,sg,τ(b, a, o)) If (s, b) belongs to a solveable layer UPDATE(b, V ) end 6

Empirical Evaluations

We now evaluate the performance of TOP in comparison with other recent forward search algorithms such as HSVI [START_REF] Smith | [END_REF], and FSVI. In addition, we have also added some solvers including PVI, a prioritized POMDP solver [START_REF] Shani | [END_REF], PBVI [Pineau et al., 2003a], and SCVI [Virin et al., 2007]. Experiments have been run on an Intel Core Duo 1.83GHz CPU processor with 1Gb main memory.

Results

We begin by demonstrating the advantage of TOP as the number of layers in the domain increases. To show that, we modified the well known maze navigation domains Hallway and Hallway2, introducing "one way doors" that work only in the direction of the goal. As we can see in Table 1, while the performance of HSVI and FSVI remains roughly fixed for a fixed target ADR as the number of layers grows, TOP performance improves significantly.

As we explain above, TOP reduces the number of redundant backups. Such backups can originate from a number of cases -backups over beliefs that already achieved their maximal possible value, backups on beliefs whose successors have not yet improved, or backups on beliefs that improve the value, but are too early. In the last case, additional backups will later be needed on the same belief. To estimate the first two types of redundant backups by counting the number of backups that did not provide an improving α vector, which we call useless backups. To estimate the last type of redundant backups, we can compare the number of useful backups, by subtracting the useless backups from the total number of backups.

We continue to compare the performance of TOP to other algorithm over well known benchmarks. In non-layered domains, there is no reason to expect TOP to outperform FSVI, as both methods use a similar strategy in selecting their trajectories. We therefore created modified layers of non-layered domains by introducing one-way doors towards the goal. The well known RockSample benchmarks are very structured, indeed when a rock is sampled it cannot be unsampled. In these domains TOP outperforms all other algorithms. We can see that this improvement is mainly because TOP executes much less backups, and almost no useless backups in all problems.

Discussion

Other researchers have suggested to leverage different types of structure. For example, [START_REF] Shani | [END_REF] explain how to solve factored POMDPs using Algebraic Decision Diagrams and [Pineau et al., 2003b] suggested to create hierarchies of POMDPs to solve large problems. Topological structure is orthogonal to such approaches. It is possible that a factored POMDP would also possess a significant topological structure. As such, we believe that our approach is complimentary to most other types of structure and can be integrated into other structured solvers. However, as we work with the state space, some modifications should be made to TOP in order to handle such domains. We intend to investigate such improvements in the future. The idea of using the topological structure of the state space has been studied repeatedly in the context of MDPs [START_REF] Dai | [END_REF][START_REF] Bonet | Faster heuristic search algorithms for planning with uncertainty and full feedback[END_REF].I na n MDP, once the layers (strongly connected components) have been identified, we can execute value iteration only over state in a single solvable layer, until it becomes solved.

As we have discussed above, a direct application of these ideas to POMDPs is challenging. First, the belief space MDP has an infinite state space, making the identification of strongly connected components difficult. Also, beliefs are not continuous -in general we cannot expect that a transition to a close belief (using standard distance metrics) will be more probable than a transition to farther belief state. As such, identifying belief partitions using distance metrics will not honor the topological structure.

Our algorithm also bears some similarity to prioritized solvers. [START_REF] Wingate | [END_REF] has thoroughly discussed prioritization in the context of MDPs, using the Bellman error. In that context, the priority of the state is the poten-tial increase in its value function given a backup. [START_REF] Shani | [END_REF] have extended these ideas into the POMDP space. They also used the Bellman error, but over beliefs rather than states. One problem with this approach is that it is time consuming to update the priorities of beliefs. We note, however, that a high Bellman error does not indicate that a belief belongs to a solveable layer. A belief b, such that b(s) > 0 and R(s, a) > 0 may initially have a high Bellman errors, even though s may belong to a layer far from the solved layers, and TOP will update b only late in the process.

A second prioritization approach was suggested by [Virin et al., 2007]. Their SCVI algorithm partitions the state space into clusters of states with similar MDP value. They collect a finite set of beliefs and assign cluster weights to beliefs based on the probabilities of states in each cluster. Then, they iterate over clusters by decreasing cluster value and update the beliefs associated with the cluster. It is possible to think of SCVI as if it induces layers in domains with no a-priori topological structure. SCVI is not a trial-based algorithm, but it may be that their ideas could be brought into TOP in order to handle generic domains by introducing artificial layers.

For trial based solvers it is crucial to balance between the identification of good trajectories, and the time that is required to compute them. HSVI uses an upper bound and a lower bound over the value function, to identify belief states where the gap between bounds can be reduced. Traversals are therefore not necessarily directed towards the regions where the lower bound, which controls the policy, can be improved. Also, the maintenance of the upper bound is extremely time consuming and therefore HSVI spends much time on computing the trajectories. FSVI, on the other hand, is very fast in computing forward trajectories. As it only uses the static value function of the underlying MDP, computing the next state becomes very fast. However, FSVI does not change its traversal strategy as the value function gets updated. Therefore, FSVI might repeatedly revisit areas of the belief space that were already solved.

Both FSVI and HSVI execute many redundant value function updates, as they do not contain a mechanism for knowing whether a backup will be beneficial, or whether additional backups will be needed afterwards. As we have demonstrated above, TOP reduces the number of redundant backups because it considers only the solveable layers.

Conclusion

We have introduced a new POMDP solution method -topological order-based planning (TOP), that uses the structural properties of POMDPs to reduce the number of costly value function updates. Our method uses the layers of the MDP state space to identify layers in belief space. TOP updates only beliefs that belong to solveable layers and thus reduces the number of times that a belief is visited. We have demonstrated how TOP outperforms other POMDP solvers in domains that contain significant topological structure.

In this paper we identified the general requirements from a TOP solver, and suggested a possible implementation for POMDPs. In the future, we will investigate the integration of methods from other solvers into TOP, such as priorities, and value-directed clustering. We also intend to apply TOP to factored domains, formalizing layers in terms of state variables instead of states as it is currently assessed in a human-robot interaction scenario of sharing a mission of object transportation.

bT

  ′ (s ′ )= O(o|s ′ ,a) s b(s)T (s ′ |s, (s ′ |s, a)O(o|s ′ ,a) (2)

Table 1 :

 1 Performance measurements on layered domains.

	Method	ADR	V (b 0 )	|V |	Time	#Backups	Useless	Scale
					(sec)		#Backups
	Hallway-layered #layers :1 0
	HSVI	0.62	1.46	143	27	199	35	×6.75
	FSVI	0.62	2.08	337	57	612	143	×14.2
	PBVI	0.60	2.18	249	155	3659	1289	×38.7
	SCVI	0.62	1.88	693	58	1420	104	×14.5
	PVI	0.50	0.36	64	288	120	12	×72
	TOP	0.62	1.43	25	4	127	0	×1
	Hallway-layered #layers :1 5
	HSVI	0.62	1.54	57	11	123	10	×11
	FSVI	0.62	2.21	266	49	612	139	×49
	PBVI	0.62	2.24	127	87	2581	1045	×87
	SCVI	0.62	2.0	609	56	1430	109	×56
	PVI	0.50	0.36	64	288	120	11	×288
	TOP	0.62	0.47	12	1	34	0	×1
	Hallway2-layered #layers :1 0
	HSVI	0.48	0.60	357	200	473	64	×10.5
	FSVI	0.48	0.60	450	127	408	293	×6.68
	PBVI	0.47	0.64	32	94	795	23	×4.94
	SCVI	0.48	0.65	1448	435	2230	148	×22.9
	TOP	0.48	0.34	63	19	135	6	×1
	Hallway2-layered #layers :1 5
	HSVI	0.57	2.42	368	244	1114	258	×10.2
	FSVI	0.57	1.51	290	71	357	60	×2.95
	SCVI	0.57	1.61	482	120	1280	127	×5
	TOP	0.57	0.95	48	24	164	0	×1
	Hallway2-layered #layers :2 0
	HSVI	0.57	2.73	296	201	1102	133	×14.4
	FSVI	0.57	1.55	218	65	357	38	×4.64
	SCVI	0.57	1.58	388	48	1240	109	×3.43
	TOP	0.57	0.77	38	14	104	8	×1
	cit-layered #layers :1 2
	HSVI	0.83	0.66	492	2170	873	370	×50
	FSVI	0.83	0.68	403	1278	1122	718	×29.7
	SCVI	0.83	0.72	535	224	550	5	× 5
	TOP	0.83	0.16	36	43	134	0	×1
	Mit-layered #layers :1 1
	HSVI	0.90	0.85	731	1515	1076	214	×39
	FSVI	0.90	0.80	164	494	1275	248	×13
	SCVI	0.90	0.63	496	101	520	4	×2.65
	TOP	0.90	0.53	47	38	196	0	×1
	Rock Sample (4,4) #layers :1 7
	HSVI	18.04	17.92	173	11	239	33	×5
	FSVI	18.04	13.63	79	7	98	12	×3
	SCVI	16.80	15.93	405	520	16350	797	×260
	TOP	18.04	13.60	37	2	63	0	×1
	Rock Sample (5,7) #layers : 129
	HSVI	24.2	22.96	208	2754	461	124	×5
	FSVI	22.2	14.97	353	4057	384	12	×8
	SCVI	21.3	20.22	432	535	800	147	×1.09
	TOP	24.3	14.51	68	488	95	0	×1
	Rock Sample (7,8) #layers : 257
	HSVI	20.1	19.69	178	7641	226	31	×6.87
	FSVI	19.7	18.43	105	4503	185	16	×4.04
	TOP	20.1	17.68	73	1112	72	0	×1


Alexandre Lenoir

Rémy Malgouyres

Marinette Revenu

published or not. The documents may come   L'archive ouverte pluridisciplinaire


K Kardasz

Keywords: FHI Zietlowa, PHI Zietlowa, Financial Health Index, assessment of liquidity risk of bankruptcy Klasyfikacja JEL: G32, G33, L31, M32

 trading company -a network of grocery stores,  a financial institution -one of the leading banks in Poland.

Job involve not only the presentation of the method, manner and methodology of calculation.

It also relates to the problem of practical use FHI. The issue of the application is primarily due to the fact that it was created in order to assess the financial condition of non-profit organizations. Article points out, however, that the use of FHI combined with the basic knowledge about the activities of the company and the segment in which it operates, allows to determine the financial position of the entity.

Praca obejmuje nie tylko prezentację metody, sposób i metodologię obliczania. Odnosi się również do problemu związanego z praktycznym zastosowaniem FHI. Problematyka zastosowania wynika przede wszystkim z faktu, iż został on stworzony w celu oceny kondycji finansowej instytucji non-profit. Artykuł wskazuje jednak, iż zastosowanie FHI w połączniu z podstawową wiedzą o działalności przedsiębiorstwa i segmentu w którym funkcjonuje, pozwala określić sytuację finansową podmiotu.

Słowa kluczowe: FHI Zietlowa, PHI Zietlowa, Financial Health Index, ocena płynności finansowej, zagrożenie bankructwem Use the financial health of an organization in financial planning.

Summary

This article presents a new method to assess the financial situation, developed by John Zietlowa, and its use to estimate the Financial Health Index for three entities:

 non-profit organization whose aim is to educate people not connected professionally with the legal system,

Wstęp

Artykuł zawiera przedstawienie nowej metody oceny sytuacji finansowej instytucji non-profit, tj. Financial Health Index, który został opracowany w roku 2012 przez Johna Zietlowa. W celu zaprezentowania sposobu implementacji FHI, wartości wska nika zostały oszacowane dla fundacji non-profit , przedsiębiorstwa realnej sfery gospodarki oraz instytucji finansowej.

Zastosowanie metody do oceny zdrowia finansowego instytucji należących do różnych sfer gospodarki pozwoliło wskazać pewne trudności związane z przystosowaniem przez Zietlowa Indeksu Zdrowia Finansowego (FHI) do oceny instytucji non-profit. Powoduje to brak możliwości bezpośredniego porównania wartości oszacowań w celu określenia względnej płynności finansowej.

W pierwszej części pracy przedstawiono obszary działalności organizacji, które stanowią podstawę do budowy parametrów składających się na wartość Financial Health Index. Punkt 3 zawiera krótki opis obszaru działalności analizowanych firm. Punkt 4 to przedstawienie wniosków wynikających z oszacowanych wartości parametrów.

Podsumowanie artykułu zawarto w Zakończeniu.

Financial Health Index Zietlowa

Indeks zdrowia finansowego (ang. Financial Health Index, FHI) zaproponowany przez Zietlowa jest jednym ze wska ników, mających za zadanie syntetyczną ocenę płynności finansowej instytucji. Krótkoterminową sytuację finansową opisano następującymi współczynnikami: operacyjnych przepływów finansowych (ang. Operating Cash Flow Ratio), aktywów (ang.

Asset Ratio) oraz wydatków administracyjnych (ang. Administrative Expense Ratio).

Nadwyżka netto (ang. Net Surplus), współczynnik udziału (ang. Contribution Ratio), współczynnik finansowania własnego (ang. Self-Financing Ratio), współczynnik długu finansowego (ang. Financial Debt Ratio) oraz koszt pozyskania kapitału (ang. Fundraising Cost Ratio) zostały zaliczone do kategorii średnioterminowej.

Źokładniejszy opis poszczególnych parametrów (wraz z definicjami i metodą obliczania), które stanowią elementy składowe FHI Zietlowa, można je znale ć w A Financial Health Index for Achieving Nonprofit Financial Sustainability. [START_REF]Rozwój/historia[END_REF] Dla oznaczenia wartości Financial Health Index, autor przyjmuje grecką literę Φ (phi).

Syntetyczny wska nik zdrowia finansowego jest obliczany zgodnie z poniższym równaniem. Φ może maksymalnie przyjąć wartość 100, co oznaczałoby idealną płynność finansową. Celem, jakim kierował się Zietlow, było opracowanie syntetycznego wska nika, który umożliwiałby wiarygodną ocenę sytuacji finansowej fundacji, tj. organizacji nienastawionych na maksymalizację zysku. [START_REF]Informacje podstawowe[END_REF] Optymalizacja wska nika pod kątem oceny płynności instytucji, których celem nie jest przynoszenie zysku właścicielom, powoduje pewne problemy z zastosowaniem tej miary do oceny przedsiębiorstw rynkowych.

W celu przedstawienie sposobu interpretacji wska nika FHI Zietlowa, jego wartości zostały oszacowane dla instytucji należących do trzech grup podmiotów gospodarczych: organizacji non-profit, instytucji finansowych oraz przedsiębiorstw działających w realnej sferze gospodarki.

Metodologia szacowania

W celu możliwie wszechstronnego przedstawienia wska nika płynności finansowej

Financial Health Index, zastosowano go na przykładzie trzech organizacji:

1. Organizacji non-profit, której celem jest edukowanie ludzi niezwiązanych zawodowo z systemem prawnym w zakresie lepszego rozumienia reguł prawnych. 5 2. Przedsiębiorstwo realnej sfery gospodarki -sieć sklepów spożywczych, które specjalizują się w segmencie premium, dostarczając produkty wysokiej jakości. 6 3. Instytucja finansowa -spadkobierca najdłużej działającego, prywatnego banku w powojennej Polsce, jeden z czołowych banków, oferujący produkty dla klientów indywidualnych, spółek prawa handlowego i organizacji non-profit. [START_REF][END_REF] Oszacowania dokonano zgodnie z instrukcją załączoną do artykułu przez autora metody. [START_REF]Bilans sporządzony na dzień 2011-12-13[END_REF]

Streszczenie

  Artykuł prezentuje nową metodę oceny sytuacji finansowej, opracowaną przez Johna Zietlowa, oraz jej zastosowanie do oszacowania Financial Health Index dla trzech podmiotów: organizacji non-profit, której celem jest edukowanie ludzi niezwiązanych zawodowo z systemem prawnym,  przedsiębiorstwa realnej sfery gospodarki -sieć sklepów spożywczych,  instytucji finansowej -jeden z czołowych banków w Polsce.

11

 11

4. Ocena sytuacji finansowej 1 .

 1 Organizacja non-profit Wartości Φ dla lat 2010-2012 wskazują na umiarkowaną poprawę zdrowia finansowego fundacji w analizowanym okresie. Po najniżej ocenionym roku 2010, nastąpiła poprawa płynności finansowej, która została odnotowana przez dziesięciokrotny wzrost wska nika FHI. Poprawa nastąpiła przede wszystkim w obszarze płynności natychmiastowej i krótkiego okresu, por. Tabela 1. Największy wzrost w tym okresie odnotowały parametry: współczynnik wystarczających rezerw gotówkowych, wska nik bieżącej płynności oraz współczynnik aktywów i współczynnik operacyjnych przepływów pieniężnych. Uogólnieniem równań definiujących wymienione wska niki jest stwierdzenie, że oceniają one stosunek rezerw gotówkowych lub aktywów obrotowych do krótkoterminowych zobowiązań.

  [START_REF] Zietlow | A Financial Health Index for Achieving Nonprofit Financial Sustainability[END_REF] W przeciwieństwie do innych miar stabilności finansowej, autor FHI miał na celu opracowanie miary właściwej dla fundacji non-profit.

	Zaletami wska nika zaproponowanego przez Zietlowa są wszechstronność opisu,
	rozważenie wszystkich horyzontów czasowych oraz orientacja na płynności finansowej. 2 FHI
	składa się z 15 parametrów, które odzwierciedlają różne aspekty sytuacji finansowej
	instytucji. Zostały one zgrupowane w cztery kategorie:
	1. Ocena sytuacji ogólnej;
	2. Ocena okresu natychmiastowego;
	3. Ocena krótkiego okresu;
	4. Ocena średniego okresu.
	By uzyskać ocenę każdej z kategorii, należy obliczyć średnią ważoną przypisanych do
	niej parametrów. Standardowo wagi są sobie równe, co oznacza de facto użycie średniej
	arytmetycznej, choć Zetlow zaznacza, że użytkownik może użyć innych wag, by podkreślić
	istotę specyficznych aspektów działalności analizowanej instytucji.
	Ogólna sytuacja jest odzwierciedlana przez wiek (ang. age) i wielkość instytucji (ang.
	size), które w przybliżeniu określają reputację, jaką cieszy się organizacja oraz stabilność
	wzrostu (ang. instability). Cztery parametry opisują natychmiastową płynność finansową
	(ang. Immediate-Term), zdefiniowaną przez Zietlowa jako oczekiwane i nieoczekiwane
	przepływy finansowe w ciągu trzech najbliższych miesięcy. Źwa parametry opisują płynność
	(wska nik płynności bieżącej oraz współczynnik wystarczalności rezerw). Ponadto, w celu
	oceny natychmiastowej płynności finansowej wzięto pod uwagę wypłacalność
	(zmodyfikowany stosunek gotówki -ang. Modified Cash Ratio) oraz elastyczność, którą
	opisano wska nikiem płynność celowa lambda (ang. Target Liquidity Lambda).

  Ze względu na przystosowanie FHI do oceny instytucji nonprofit, w przypadku oszacowania FHI Przedsiębiorstwa oraz Instytucji Finansowej, należało nieznacznie zmodyfikować niektóre parametry. Ponadto, pominięto parametr numer 15, tj. współczynnik kosztu gromadzenia funduszy, gdyż obliczenie jego wartości możliwe jest jedynie w przypadku fundacji nienastawionych na zysk. Wartości FHI Zietlowa zostały obliczone w oparciu o roczne sprawozdania finansowe z lat 2010, 2011 i 2012, pochodzące z serwisów relacji inwestorskich wybranej Instytucji Finansowej 9 oraz Przedsiębiorstwa Realnej Sfery Gospodarki 10 . Roczne sprawozdania finansowe Organizacji non-profit pochodzą z bazy organizacji pożytku publicznego.

Tabela 1: Oszacowania parametrów Financial Health Index dla Organizacji non-profit.

  Pierwszym aspektem zdrowia finansowego, na jaki warto zwrócić uwagę, są niższe wartości wska nika FHI dla spółki niż dla analizowanej powyżej fundacji. Taka obserwacja

		8 współczynnik operacyjnych przepływów pieniężnych	1,71	17,50	20,35
		9 Współczynnik aktywów	1,00	90,89		1,00
		10 Współczynnik wydatków administracyjnych	2,36	0,13		1,00
	Ocena krótkiego okresu nie musi oznaczać, że sieć sklepów spożywczych charakteryzuje się wyższym ryzykiem 1,69 36,18 11 nadwyżka netto 0,26 6,66 12 współczynnik udziału 1,00 1,00 finansowym. Po pierwsze, ze względu na rynkowy charakter działalności nie było możliwe	7,45 0,92 1,00
	13 współczynnik finansowania własnego 14 współczynnik długu finansowego oszacowanie parametru wielkości współczynnika kosztu gromadzenia funduszy. Po drugie, 1,75 1,75 -0,28 -0,05	1,75 -0,04
	15 współczynnik kosztu gromadzenia funduszy obszar, w którym Przedsiębiorstwo prowadzi działalność, charakteryzuje się niskim 0,00 0,00 Ocena średniego okresu 0,55 1,87 Financial Health Index 1,80 20,42 poziomem ryzyka operacyjnego i finansowego ze względu na niskie wahania popytu. Za taką ródło: Opracowanie własne. interpretacją przemawiają bardzo niskie wartości oszacowań współczynnika wystarczających 10,23 0,00 0,72
	Poprawa krótkoterminowej płynności finansowej Organizacji wiązała się przede rezerw gotówkowych oraz zmodyfikowanego współczynnika gotówki, które wskazują za
	wszystkim z prawie siedmiokrotnym wzrostem aktywów obrotowych w latach 2010-2011 przyczynę niskiej wartości FHI przede wszystkim optymalizację d wigni finansowej przez
	(z 13 500,53 do 89 835,69 zł). odnotowana przede wszystkim przez parametry, które zanotowały najwyższy wzrost w roku zarząd spółki.
	2011, została spowodowana dziesięcioprocentowym spadkiem przychodów z działalności
	Nr	Nazwa parametru	2010	2011	2012
	1 Wiek statutowej oraz zwiększeniem wielkości kosztów poniesionych przez organizację, choć warto 2,77 2,83	2,89
	2 Rozmiar 3 wskaźnik niestabilności aktywów podkreślić działania zarządu na rzecz dalszego zmniejszenia kosztów administracyjnych. 15 10,15 11,51 8,12 9,24	11,38 9,23
		Ocena sytuacji ogólnej	7,02	7,86		7,83
		4 współczynnik wystarczających rezerw gotówkowych	1,33	42,06	23,09
		5 zmodyfikowany współczynnik gotówki	0,47	0,94		0,94
		6 celowa płynność lambda 7 wskaźnik bieżącej płynności 2. Przedsiębiorstwo Realnej Sfery Gospodarki	0,91 2,20	4,41 36,69	4,45 42,22
		Ocena natychmiastowego okresu	1,23	21,03	17,67

[START_REF]Rachunek wyników na dzień 2011-12-13[END_REF]

Stro a i ter etowa Spółki ; 26.02.2014.

[START_REF]Skonsolidowane sprawozdanie finansowe za[END_REF]

Stro a i ter etowa Spółki ; 26.02.2014

[START_REF] Stefański | Nowe regulacje dotyczące wymagań kapitałowych wobec banków[END_REF]

Departa e t Pożytku Pu li z ego http://pozytek.gov.pl/BAZA,OPP,3403.html; 26.02.2014.

[START_REF] Dluhosova | Multi factor sensitivity analysis in the investment decision-making[END_REF]

Tak duża poprawa krótkoterminowej sytuacji finansowej prawdopodobnie wynika ze zmiany sposobu zarządzania fundacją na bardziej efektywną.

W roku 2011 około czterokrotnie wzrosły przychody z działalności statutowej.

[START_REF] Dluhosova | An analysis of financial performance using the EVA method[END_REF]

Ponadto, zarząd fundacji osiągnął znaczne sukcesy w obniżeniu kosztów administracyjnych, których wartość wyniosła w roku 2011: 2 156, w porównaniu do 22117,98 w poprzednim roku. 14 Kolejny rok przyniósł obniżenie oceny zdrowia finansowego Φ. Zmiana płynności, 12 Bila s sporządzo y a dzień -12-13,Spółki . 13 Ra hu ek wy ików a dzień -12-13,Spółki . 14 Ibid. 15 Ra hu ek wy ików a dzień 2-12-13,Spółki . Tabela 2:

Oszacowania parametrów Financial Health Index dla Przedsiębiorstwa Realnej Sfery Gospodarki.

  celu dokonania właściwej oceny zdrowia finansowego banku należałoby przeprowadzić badania porównawcze w sektorze instytucji finansowych, z zastosowaniem Financial Health Index Zietlowa. Pomimo braku takich analiz, biorąc pod uwagę stabilność oszacowań parametrów dla kolejnych lat oraz wzrost wartości PHI Zietlowa w roku 2012, Instytucja wydaje się być w dobrej kondycji finansowej.

	ródło: Opracowanie własne.
	Rok 2011 przyniósł znaczną poprawę FHI. Wartość Φ wzrosła z około 4 do ponad 12
	punktów (por. Tabela 2) przede wszystkim w związku ze znaczącą poprawą oszacowań
	współczynnika aktywów oraz współczynnika operacyjnych przepływów pieniężnych. Takie
	zachowanie wartości FHI, po dokładniejszej analizie sprawozdań finsansowych, wskazuje na
	możliwość wyciągnięcia błędnych wniosków w przypadku stosowania wska nika Zietlowa do Tabela 3:
	oceny zdrowia finansowego przedsiębiorstw, a nie fundacji. Teoretyczny wzrost zdrowia
	finansowego wiązał się z chwilowym zwiększeniem aktywów obrotowych, co w połączeniu
	ze znacznym spadkiem sprzedaży 16 pozwala przypuszczać, że wzrost aktywów obrotowych
	był spowodowany negatywnym szokiem popytowym, jakiego doświadczyło przedsiębiorstwo
	w 2011.
	3. Instytucja Finansowa
	Nr Nazwa parametru 1 Wiek finansowe Instytucji zostało ocenione najwyżej (por. Tabela 3). Przyczyn 2010 2011 2012 2,94 2,9 3,04
	2 Rozmiar wysokich wartości oszacowań parametrów wchodzących w skład Φ należy upatrywać 14,02 14,15	14,23
	3 wskaźnik niestabilności aktywów Ocena sytuacji ogólnej w przynależności do innego sektora gospodarki. Instytucją finansowa, podlega szczególnym 5,17 11,08 7,38 9,41	10,24 9,17
	4 współczynnik wystarczających rezerw gotówkowych 5 zmodyfikowany współczynnik gotówki regulacjom, określającym szczególne wymogi kapitałowe. 17 , poza wysokimi oszacowaniami 0,82 0,81 -0,28 -0,27		0,82 -0,31
	6 celowa płynność lambda parametrów płynności, które wynikają z wypełniania odpowiednich regulacji związanych ze 2,70 2,12 7 wskaźnik bieżącej płynności 0,20 0,21 Ocena natychmiastowego okresu 0,86 0,72 szczególną rolą banku w systemie gospodarczym, charakteryzuje się również lepszymi		2,34 0,08 0,73
	8 współczynnik operacyjnych przepływów pieniężnych 9 Współczynnik aktywów wartościami wska ników niezwiązanych bezpośrednio z powyższym. Ocena zdrowia 1,71 17,49 1,00 90,89	20,35 1,00
	10 Współczynnik wydatków administracyjnych Ocena krótkiego okresu finansowego instytucji zyskuje dzięki wielkości posiadanych aktywów oraz rozmiaru 2,36 0,13 1,69 36,17	1,00 7,45
	11 nadwyżka netto Instytucji.	0,87	1,77		0,06
	12 współczynnik udziału	0,01	0,01		0,01
	13 współczynnik finansowania własnego	46,01	14,24	11,80
	14 współczynnik długu finansowego	-0,20	-0,17		-0,21
	15 współczynnik kosztu gromadzenia funduszy	nie dotyczy nie dotyczy nie dotyczy
	Ocena średniego okresu	11,67	3,96		2,92
	Financial Health Index	3,92	12,87		4,03

[START_REF] Kopa | Financial Modelling[END_REF]

str. 9. Stro a i ter etowa Spółki ; 26.02.2014

[START_REF] Kulhanek | The relationship between stock markets and gross domestic product in the Central and Eastern Europe[END_REF]

Stefański M., Nowe regula je doty zą e wy agań kapitałowy h wo e a ków [w:] Materiały i Studia, nr 212, Narodowy Bank Polski, 2006.

W

Oszacowania parametrów Financial Health Index dla Instytucji Finansowej.

  Zastosowanie wska nika oceny zdrowia finansowego FHI Zietlowa do oceny płynności różnych instytucji pozwala stwierdzić, że jest to miara przystosowana, zgodnie z zamierzeniami autora, do analizy instytucji non-profit. Takie przeznaczenie powoduje trudności w oszacowaniu PHI Zietlowa przedsiębiorstw rynkowych. Jeden z parametrów został pominięty, co powoduje brak możliwości bezpośredniego porównania oszacowań pomiędzy fundacją, przedsiębiorstwem i instytucją finansową.Ze względu na nowość metody, która została opracowana niespełna dwa lata temu, interpretacja otrzymanych wyników może powodować problemy. Przede wszystkim brak jest badań na temat empirycznego rozkładu PHI Zietlowa wśród instytucji non-profit. Zietlow podaje jedynie maksymalną teoretyczną wartość, jaką może przyjąć Financial Health Index, jednak zarówno wartości obliczone na przykładzie Armii Zbawienia 18 jak również oszacowania Φ dla instytucji omówionych w artykule znacznie odbiegają od maksymalnej wartości. Przeprowadzenie szerszych badań porównawczych wydaje się być konieczne do właściwego zrozumienia absolutnych wartości Financial Health Index Zietlowa oraz opracowania poziomów referencyjnych, wskazujących zagrożenie płynności.

	Nr	nazwa parametru	2010	2011	2012
		1 Wiek	3,04	3,09	3,14
		2 Rozmiar	21,09	21,30	21,29
		3 wskaźnik niestabilności aktywów	12,84	12,62	12,65
		Ocena sytuacji ogólnej	12,32	12,34	12,36
		4 współczynnik wystarczających rezerw gotówkowych	3,31	3,13	3,73
		5 zmodyfikowany współczynnik gotówki	-0,04	0,66	-0,03
		6 celowa płynność lambda	91,19	67,79	126,01
		7 wskaźnik bieżącej płynności	8,12	7,48	12,78
		Ocena natychmiastowego okresu	25,64	19,76	35,62
		8 współczynnik operacyjnych przepływów pieniężnych	2,35	1,21	11,49
		9 Współczynnik aktywów	172,75	170,79	217,89
		10 Współczynnik wydatków administracyjnych	0,17	0,13	0,14
		Ocena krótkiego okresu	59,15	59,38	76,79
		11 nadwyżka netto	1,06	1,08	1,06
		12 współczynnik udziału	0,55	0,19	0,19
		13 współczynnik finansowania własnego	-24,05	14,25	11,80
		14 współczynnik długu finansowego	-0,30	-0,30	-0,31
		15 współczynnik kosztu gromadzenia funduszy	nie dotyczy nie dotyczy nie dotyczy
		Ocena średniego okresu	-5,68	3,80	3,19
	Financial Health Index ródło: Opracowanie własne.	28,10	27,11	39,16
	4. Zakończenie

Zietlow, John, A Financial Health Index for Achieving Nonprofit Financial Sustainability (September

[START_REF] Michalski | Strategie finansowe przedsiębiorstw (Business Financial Strategies in Polish)[END_REF] 2012), http://ssrn.com/abstract=2049022 (27. lutego 2014).

Zietlow, J., op. cit.

Zietlow J., op. cit.

Zietlow J., op. cit.

Stro a i ter etowa Spółki , 27. lutego 2014.

Stro a i ter etowa Spółki , 27. lutego 2014.

Stro a i ter etowa Spółki , 27. lutego 2014.

Zietlow, Table 1:Financial Health Index Indicators Calculation Formulas [w:] A Financial Health... op. cit.