Mohamed Benazouz
email: mohamed.benazouz@gmail.com

Jean-Marc Faure
email: jean-marc.faure@ens-cachan.fr

Safety-Level Aware Bin-Packing Heuristic for Automatic Assignment of Power Plants Control Functions

Keywords: Dependable control, distributed systems, critical systems, vector bin-packing, multiple-choice

Finding a suitable set of controllers to which a large set of control functions with different safety levels can be assigned, while minimizing cost, is a significant task during the design of the operational control system of a critical process, like a power plant. This task is currently performed by experts and extremely time-consuming, which explains why its automation is a real concern. This paper shows first that the above assignment problem can be identified as a Multiple-Choice Vector Bin-Packing with Conflicts problem, a combination of different variants of the well-known one-dimensional bin-packing problem. Such a problem is known to be strongly NP-Hard and exact techniques to solve it on large-sized examples are too time and/or space consuming because of the combinatorial explosion. To solve this problem in polynomial time, this article proposes a fast heuristic based on a FFD (First-Fit Decreasing) approach. Two strategies to perform this heuristic and several criteria to rank the functions before assignment are defined. These strategies and criteria are then compared on the basis of numerous experiments. These experiments show that the proposed heuristic scales well and provides results that are very close to optimum; the difference in the worst case is less than 1%.

Note to Practitioners: Abstract-Designing the operational control architecture of a critical process, like a power plant, is an extremely time-consuming task that requires in particular to find a suitable and minimum-cost set of industrial controllers to which the numerous control functions can be assigned and thereafter implemented. This design task is currently performed by experts who imagine, evaluate and compare different solutions. Hence, several iterations of the assignment process are necessary during this task. The practical aim of this research is to automate this process to facilitate and speed up architecture design. This work has been made in the frame of a cooperative research project with a company which designs and implements control systems of power plants. Nevertheless, the generic results that are presented in this article can be used for other critical processes (oil, chemical processes, water management) where a large number of control functions with different impacts on safety is to be assigned to controllers, because the proposed heuristic scales well.

I. INTRODUCTION

F ROM a functional point of view, the control system of a power plant is composed of several thousands of functions (actuators control, processes synchronization, variables monitoring, etc.) that are aiming at ensuring the correct operation of the electrical power production process as well as safety of people and environment in case of failure of a component of the plant. This set of functions is defined in the earliest phases of design and is the starting point of this work. The internal structure of every function, in the form of ECC (Execution Control Chart) [START_REF] Dai | Redesign distributed plc control systems using iec 61499 function blocks[END_REF] or SFC (Sequential Function Chart) [START_REF] Basile | On the implementation of industrial automation systems based on plc[END_REF] for instance, is unknown at these phases and in what follows. A control function will be seen as a black-box and only the requirements to implement the function, like its number of input/output data and its CPU consumption, will be considered. Moreover, a power plant is a critical system and some functions are more important for safety than other ones. Hence, a safety level, letter that represents the importance of the function with regard to safety, is associated to every function and the whole set of functions is divided into several subsets, termed classes. All the functions of a given class own the same safety level. Last, among every class, some functions are redundant, i.e. they may perform the same service in different operation modes. When an active function is no more able to perform its service because the plant components that it controls have failed, it is replaced by a redundant one that ensures the same service with other faultless plant components.

On the other side, from an operational point of view, the control system is composed of a set of some hundreds of industrial controllers, processing devices (Programmable Logic Controllers, industrial computers) connected to sensors and actuators and that execute the control functions. The internal structure of an industrial controller is not considered in this paper, only its capacities (overall number of input and output interfaces, processing capacity) are known. Moreover, it matters to underline that different categories of controllers, with different abilities to be fault-tolerant to internal failures, are available to implement the control functions. The ability of a controller to be fault-tolerant is represented by an integer which is termed its criticality factor. The smaller this factor, the more fault-tolerant the controller is. It is obvious that the cost of the controller increases when its criticality factor decreases.

Before implementing every function on a given controller, an assignment process must be performed. The first aim of the assignment process (Fig. 1) is to find a suitable set of controllers such that every function is assigned to one and only one controller while satisfying two kinds of constraints: capacity constraints and safety constraints. Capacity constraints mean merely that several functions can be assigned to a given controller if and only if the capacities of this controller are large enough to host all these functions. It is obviously not possible, for instance, to assign three functions with M/2 input data each to a controller that owns only M input interfaces. Two kinds of safety constraints must be introduced in addition. The first one relates the safety level of a function to the criticality factor of the controller to which this function may be assigned. It is not allowed for instance to assign a function which strongly impacts safety to a controller which is not very fault-tolerant. The second safety constraint, termed separation constraint, means that two redundant functions must not be assigned to the same controller, to avoid that the failure of this controller provokes the loss of the service. A formal definition of the assignment problem will be given in the next section.

Assuming that there always exists a controller which can host the larger function (otherwise this function must be decomposed in smaller ones), a trivial assignment solution is to choose as many controllers as there are functions and to define the criticality factor of every controller according to the safety level of the only function it hosts. The separation constraint will be automatically satisfied because only one function will be assigned to every controller. This solution is obviously not economically viable 1 . Hence, the overall objective of the assignment process is not only to find a feasible solution that satisfies all constraints, as presented in [START_REF] Lemattre | Designing operational control architectures of critical systems by reachability analysis[END_REF], but to minimize the cost of the set of controllers of this solution.

Currently, the assignment process is performed by experts 1 The observation of existing solutions in power plants shows that a controller hosts on average several tens of functions.

in companies that design and implement large control systems. This process is extremely tedious and time consuming. Moreover, minimization of the cost is generally achieved only by comparing several feasible solutions. This work aims to tackle out these issues by proposing a bin-packing heuristic to assign automatically the control functions, while minimizing the cost, in a short time. Preliminary results have been presented in [START_REF] Benazouz | Safety-Level Aware Bin-Packing Approach for Control Functions Assignment[END_REF]. This article extends these results by proposing another novel assignment strategy and comparing the two strategies on the basis of a larger set of experiments.

The outline of the paper is the following. An ILP formulation of the assignment problem is given in the next section. It is shown in the third section that this problem is a Multiplechoice Vector Bin-Packing (MVBP) with Conflicts problem. Two strategies are then proposed in the fourth section to assign the different classes of functions. For both strategies, a heuristic based on a FFD (First Fit Decreasing) approach is detailed in section V. Several criteria to sort the functions before applying the FFD are also defined in this section. The relative performances of the two strategies and the sorting criteria are compared and discussed on the basis of experimental results in the sixth section, while concluding remarks and outlooks are drawn up in the seventh one.

II. PROBLEM FORMULATION

In this section, the problem adressed in this paper is modelled by an ILP. For the sake of comprehension and without impacting generality, the formulation is limited to the 2-dimensional case (only 2 capacities will be considered). The ILP formulation can be unlimitedly extended to multiple capacities given that they follow a linear additive consumption scheme.

Capacities considered are cpu processing capacity and the number of inputs (resp. outputs) from (resp. to) the physical processes of the plant that are required for a control function to perform its task. Inputs and outputs are considered interchangeable as controllers dispose of cards that can be adapted following requirements. Therefore, the number of inputs and outputs required by a function are summed and this sum is noted inout.

Let us consider a set of functions F and a set of controllers C. Each function f i ∈ F is characterized by its

• inout i : the number of its inputs and outputs, • cpu i : its cpu consumption, and • sl i : its safety level. Four safety levels are defined in IEC standards [START_REF] Lahtinen | Comparison between IEC 60880 and IEC 61508 for Certification Purposes in the Nuclear Domain[END_REF] for power plants control functions: A, B, C and N C. A function f i with sl i = A (resp. B,C,N C) is said to be of class A (resp.

B,C,N C).

A function whose safety level is A impacts safety more than a function of class B which itself is more significant for safety than a function of class C. N C functions (not classified) do not impact safety.

On the other hand, each controller C j ∈ C is characterized by its

• IN OU T j : its capacity in terms of inputs/outputs, • CP U j : its processing capacity, • CF j : its criticality factor with CF j ∈ {0, 1, 2},

• COST j : its cost. A controller C j with CF j = 0 (resp. 1,2) is said to be of category 0 (resp. 1,2). Controllers with smaller criticality factor are more reliable. The cost of a controller is proportional to its characteristics. Since in the addressed problem all controllers are considered to have the same processing capacity CP U , i.e.

∀C j ∈ C, CP U j = CP U, and the same capacity of inputs/outputs IN OU T , i.e.

∀C j ∈ C, INOUT j = IN OU T,
the cost of a controller depends only on its criticality factor. The more reliable it is, the more expensive it is.

The most critical functions (class A) must be assigned to the most reliable controllers (category 0) and the less critical functions (class NC) must be assigned to the cheapest, then less reliable controllers (category 2). Moreover, two functions whose safety levels are too different (for instance A and C, A and NC, B and NC) must not be assigned to the same controller because development, testing and monitoring of the codes which will implement these functions must be different. Hence, a controller of A graphical representation of these compatibility relations is given in Table I. The X mark indicates that a category of controllers is compatible with the class of functions.

A B C NC 0 X X 1 X X 2 X X
A loose upper bound on the number of controllers of each category can then be derived. Let us define by

F A (resp. F B , F C ,F NC ) the set of A-class (resp. B,C,N C) functions such that F = F A ∪F B ∪F C ∪F NC .
Then, as we seek to minimize the cost of controllers, we need at most

|F A | (resp. |F B |, |F C | + |F NC |) controllers of category 0 (resp. 1, 2) 2 .
In fact, if we consider the solution that consists in each controller hosting only one function, functions of F A would be packed in controllers of category 0, those of F B would be packed into controllers of category 1, and functions of F C and F NC would be packed into controllers of category 2.

Using this loose upper bound and following safety constraints, we can construct S, the set of couples (f i , C j ) ∈ F×C such that the class of f i is incompatible with the category of C j .

Besides, as an input of our problem we are given a list L of couples of redundant functions

(f i , f i ). The redundancy relation is commutative (i.e. if (f i , f i ) ∈ L then (f i , f i ) ∈ L)
2 |F| represents the cardinality of the set F. and transitive (i.e. if

(f i , f i ) ∈ L and (f i , f i ) ∈ L then (f i , f i ) ∈ L).
Let us consider also the following Boolean variables

• x ij that should take the value 1 iff the function f i is assigned to controller C j , and • U sed j that should take the value 1 iff the controller C j is used, i.e. hosting at least one function. Then, the assignment problem can be modelled by the following Integer Linear Program (ILP):

minimize Cj ∈C COST j • U sed j subject to ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∀f i ∈ F, Cj ∈C x ij = 1 (1) ∀C j ∈ C, fi∈F inout i • x ij ≤ IN OU T (2) ∀C j ∈ C, fi∈F cpu i • x ij ≤ CP U (3) ∀(f i , C j ) ∈ F × C, x ij ≤ U sed j (4) ∀C j ∈ C, ∀(f i , f i ) ∈ L, x ij + x i j ≤ 1 ( 5 ) ∀(f i , C j ) ∈ S, x ij = 0 (6) ∀(f i , C j ) ∈ F × C, x ij ∈ {0, 1} (7) ∀C j ∈ C, U s e d j ∈ {0, 1} (8)
This ILP minimizes the global cost of used controllers. Constraint (1) models the fact that a function must be assigned to one and only one controller. Constraints (2) and (3) satisfy the limited capacities of controllers in terms of CPU and INOUT. Constraint (4) indicates whether a controller is used or not. Constraint [START_REF] Lahtinen | Comparison between IEC 60880 and IEC 61508 for Certification Purposes in the Nuclear Domain[END_REF] ensures the separation of redundant functions, i.e. their assignment to different controllers. Constraint [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF] ensures the compatibility of the classes of functions with the categories of controllers to which they are assigned.

For solvers that may be more efficient on ILPs without Boolean constraints, the domain of variables x ij in [START_REF] Kou | Multidimensional bin packing algorithms[END_REF] and U sed j in (8) can be relaxed to N. In fact, the minimization objective and the set of contraints (1) and (4) bind their values to 0 or 1.

III. PROBLEM IDENTIFICATION

The assignment problem addressed in this paper can be seen as a generalization of more than one variant of the Bin-Packing problem (BP) [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF]. This combinatorial problem consists of packing items of different sizes into the minimum possible number of identical bins with a given capacity. In its multidimensional variant also known as Vector Bin-Packing (VBP), items and bins are multi-dimensional [START_REF] Kou | Multidimensional bin packing algorithms[END_REF]. The VBP problem is an important problem that arises in a variety of industrial applications such as virtual machine placement [START_REF] Panigrahy | Heuristics for vector bin packing[END_REF]. In control functions assignement, dimensions may correspond to cpu and memory consumption and the number of inputs/outputs required.

When considering separation constraints, the problem becomes a VBP with conflicts [START_REF] Sadykov | Bin packing with conflicts: A generic branch-and-price algorithm[END_REF]. This problem combines the VBP with the Vertex Coloring problem and has many applications [START_REF] Basnet | Heuristics for determining the number of warehouses for storing non-compatible products[END_REF]. A conflict graph in which each vertex corresponds to a conflicting item is provided. A couple of conflicting items that cannot be assigned to the same bin are represented by an edge in the conflict graph between the two corresponding vertices. The number of conflicts of an item, which indicates the number of items it is in conflict with, is then given by the degree of its corresponding vertex in the conflict graph.

The conflict-free version of our problem, i.e. without considering separation constraints, can be seen as an instance of a Multiple-Choice VBP (MVBP) [START_REF] Patt-Shamir | Vector bin packing with multiplechoice[END_REF]. In this variant of the binpacking problem, different types of bins with differents costs and characteristics are provided, and items have different incarnations depending on these types. Due to safety constraints, the addressed problem is a special case of the MVBP in which a function would have no incarnation for incompatible types of controllers.

Both the bin-packing and the vertex coloring problems are strongly NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Thus, as a generalization of these two problems, the control functions assignment problem addressed in this paper is also strongly NP-hard. Real instances we are aiming at may have around ten thousand functions and need hundreds of controllers with an average number of functions per controller that may exceed 40. Such instances are beyond the solving capacity of exact algorithms for which there exists instances of two hundred items that are still open, i.e. for which no optimal solution is known [START_REF] Brandão | Bin packing and related problems: General arc-flow formulation with graph compression[END_REF]. On the other hand, for such instances with high number of items per bin, heuristics provide good solutions because the waste in bins tends to be smaller.

A. Contribution

The main contribution of this paper is a safety-level aware vector bin-packing approach that mimimizes the cost of the set of controllers of the operational architecture by assigning functions to safety compatible controllers while satisfying capacity and separation constraints. This is accomplished as follows.

First, two strategies are introduced in order to handle the multiple-choice facet of the problem that results from safety compatibilities between functions classes and controllers categories. These strategies, a class oriented and a category oriented one, specify orders into which the different classes of functions are assigned.

Then, at each step of these strategies, a bin-packing algorithm is called to assign functions. A heuristic that is an improved version of the First-Fit Decreasing algorithm (FFD) is proposed. The FFD, that is a greedy algorithm, has been shown to be a powerful fast heuristic to solve the one-dimentional bin-packing problem. The version proposed was developed specifically to manage the multi-dimensional and the conflicts aspects in accordance with the proposed strategies. The FFD operates by first sorting functions which may greatly impact the results. Three different sorting criteria are proposed that alternate between giving priority to capacity constraints satisfaction and conflicts resolving.

Finally, several experiments are performed in order to check the accuracy of the ordering strategies proposed and the adapted version of the FFD.

B. Related works

In [START_REF] Lemattre | Designing operational control architectures of critical systems by reachability analysis[END_REF], the authors propose a technique based on the verification of a reachability property on a network of communicating automata to model the assignment problem. However, this technique is meant more to find a feasible solution that satisfies constraints than to obtain an optimized one. Besides, controllers are considered of the same cost no matter their criticality factor.

As mentioned before, the problem addressed in this paper is one of several variants of bin-packing problem. Despite the extremely rich literature in this field, we were not able to find works that consider jointly both the multiple-choice of bins and the conflicting items when solving a vector bin-packing problem. In [START_REF] Brandão | Bin packing and related problems: General arc-flow formulation with graph compression[END_REF] and [START_REF]Multiple-choice vector bin packing: Arc-flow formulation with graph compression[END_REF], the authors propose an exact technique based on an Arc-Flow formulation that represents all the feasible packing solutions of a problem in a compact graph. Different arc-flow models are then built using this formulation for the VBP, the one-dimensional BP with conflicts and the MVBP. Though it seems possible to combine these models in order to build an arc-flow model for our specific problem and for general MVBP with conflicts, we will be quickly limited by the instances that can be treated using such formulation. In fact, in addition to the size of our real instances that may exclude the use of any exact methods, this arc-flow technique is very sensitive to the number of items per bin (10 items per object is a maximum limit).

In [START_REF] Patt-Shamir | Vector bin packing with multiplechoice[END_REF], a polynomial-time approximation algorithm for the MVBP is proposed; the approximation ratio depends on the number of dimensions. On the other hand, VBP with conflicts are hard to approximate for general graphs of conflicts. Then, in most of the existing works this variant is considered on restricted graphs of conflicts. The authors in [START_REF] Epstein | Two-dimensional packing with conflicts[END_REF] propose approximations for the 2-dimensional bin-packing with perfect and bi-partite conflicts graphs. In our instances specification, separation constraints do not follow a specified pattern; their conflict graph should then be considered as general. In [START_REF] Gendreau | Heuristics and lower bounds for the bin packing problem with conflicts[END_REF], a heuristic named ModifiedFFD, which adds a test for the absence of conflicts, is proposed to solve the BP with Conflicts. The approach we propose in the present work extends, in some way, this heuristic with multidimensional and multiple-choice aspects.

IV. SAFETY-LEVEL MANAGEMENT

In this section, two assignment strategies are proposed to manage safety compatibilities between functions and controllers with the objective of reducing the cost of the global set of controllers of the architecture. Both strategies specify an order in which the classes of functions are assigned to compatible controllers.

A. Class based strategy

The idea of this first strategy is to define an order such that it is easy to remove the uncertainty (i.e. disambiguate) about the category of the controller into which a function will be assigned. Therefore, functions of classes that are compatible with only one category are assigned first since there is no ambiguity about the category of controllers to which they can be assigned. The other classes with multiple choices are then treated in a second time.

Since functions of class A and class NC can only be packed respectively into controllers of category 0 and 2, the strategy proceeds by packing them first. Packing first the functions of class A permits to set definitely the number of controllers of category 0 which are the most expensive ones but the only ones able to host A functions; the B functions which are compatible with A functions (see Table I) may be assigned later to cheaper controllers of category 1 if there is no more room available in the controllers of category 0. On the other hand, the number of controllers of category 2 obtained by assigning functions of class NC is only a lower bound on the number of controllers of this category. These assignments are represented by steps (1) and ( 2) of Algorithm 1. Since they involve different classes of functions and different categories of controllers, these steps can be interchanged and even parallelized. Notice, for these last two steps, that it is important to proceed as detailed in the specified order so as to avoid the ambiguity that can arise if these steps are inverted. Indeed, if functions of class C are packed first, it would be difficult to determine whether new created controllers should be of category 2 or category 1 in anticipation of the possible assignment of functions of class B into these controllers.

B. Category based strategy

In this second strategy, the order is specified such that the number of controllers created for each category is minimized according to their cost. The categories of controllers are first ordered from the most to the least expensive. Then, following this order, new controllers of each category are allowed to be created only by the functions that have no choice for a cheaper compatible category. Unlike the class oriented strategy, this approach prevent revisiting the number of controllers of a category once it has been treated.

Since controllers of category 0 are the most expensive, they are treated first. This category is compatible with functions of classes A and B. However, for this last class, there is another choice of category of controllers that is cheaper. Thus, at this first step, only functions of class A are assigned and allowed to create controllers of category 0. Afterwards, category 1 is processed. For similar reasons, the only functions allowed to be assigned at this step are those of class B. However, since they are compatible with category 0 and in order to preserve the objective of minimizing the cost of the global architecture, the use of remaining space in the controllers of category 0 takes priority over the creation of new controllers of category 1. Finally, functions of class C are packed together with functions of class NC since they are both compatible with category 2 that is the cheapest one. Nonetheless, functions of class C that fit in the available space provided by already created controllers of category 1 must be assigned in these controllers before using controllers of category 2 for obvious reasons.

The predetermined orders specified by these strategies allow handling the multiple choice facet of the MVBP with conflicts. In fact, at each step of Algorithms 1 and 2 the category of controllers to be created is defined. Thus, at each one of these steps, the assignment problem to be solved is a VBP with conflicts for which a heuristic is proposed in the next section.

V. HEURISTIC FOR THE VBP WITH CONFLICTS

The algorithm to solve the VBP with conflicts problem is first presented in this section. Since this algorithm relies on a FFD approach, several criteria to sort the functions to be assigned are then defined. Complexity of the heuristic is finally addressed.

A. First-Fit Decreasing Assignment Approach

The first-fit decreasing packing algorithm (see. Algorithm 3) consists in going through the list of functions (lines 4-16) and for each function to pack it in the first encountered controller in which it can fit in (lines 5-10). If there is no already created controller in which the function can fit in, then a new controller is created and the function in assigned to this controller (lines [START_REF] Patt-Shamir | Vector bin packing with multiplechoice[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF] Brandão | Bin packing and related problems: General arc-flow formulation with graph compression[END_REF][START_REF]Multiple-choice vector bin packing: Arc-flow formulation with graph compression[END_REF][START_REF] Epstein | Two-dimensional packing with conflicts[END_REF]. In this decreasing variant, the functions are first sorted in a non-increasing order following their characteristics (line 2) before they are packed, which corresponds to the simple policy that consists of packing big items first in the original algorithm.

Note that each time a function is assigned to a controller, the remaining capacities of this controller must be updated (lines 7 and 13).

Initially the FFD was designed for the one-dimensional binpacking problem and without considering conflicts between the items to be assigned. Thus, the FFD algorithm has to be for All controllers C j ∈ C/j ← 1 to nbrControllers do 6:

if f i fits in C j then 7: Assign f i to C j 8:
Break the inner loop to assign the next function return C 17: end function extended and adapted to consider these new constraints. First, the fitting in conditions must be defined which is detailed in the next subsection. Besides, the policy of controllers creation has to be specified since for some classes of functions different categories may be compatible (Subsection V-C). Finally, since the addressed problem is multidimensional, it is necessary to define how functions are sorted (Subsection V-D).

B. Fitting in conditions

A function f i fits in a controller C j if and only if the following conditions are satisfied • the safety level sl i is compatible with the criticality factor CF j . • the controller C j has enough remaining cpu and inout capacities to perform f i . • f i is not in conflict with any already assigned function f i to the controller C j .

Several ways exist to check quickly the last condition. One way is to keep for each function a list of controllers to which a conflicting function has already been assigned. These lists are updated as the assignment process advances. Then, if a controller satisfies the first two fitting in conditions but belong to this list, it is excluded.

C. Controllers creation policy

The policy used to set the category of a new created controller is defined in Algorithm 4

The consistency of a creation policy with the cost minimization objective is ensured by the order in which functions of different classes are packed. Notice that the policy specified in Algorithm 4 is compatible with the orders defined by both the class and the category based strategies presented in Section IV.

Algorithm 4 Create a new controller

input: A function f i output: A new controller C j of a compatible category with f i 1: function CREATENEWCONTROLLER(f i ) 2: if f i is of class A then 3:
Create a new controller C j of category 0

D. Sorting criteria

In the original version of the bin-packing problem, items are sorted based on their unique dimension: their size. Given the additional set of constraints to be treated, several criteria can be adopted to sort functions. The generic idea in that case is to aggregate subsets of characteristics of an object to get only one characteristic that represents this object. In one sense, this will have for effect to reduce the multidimensional problem into a mono-dimensional one for which the original version of the algorithm can be applied [START_REF] Kou | Multidimensional bin packing algorithms[END_REF], [START_REF] Panigrahy | Heuristics for vector bin packing[END_REF].

Two aggregators were adopted whereby functions are sorted according to:

• maxConsumption: the relative maximum of the consumption of inout and cpu capacities max(

cpu i CP U , inout i IN OU T ).
• meanConsumption: the relative mean of the consumption of inout and cpu capacities

cpu i CP U + inout i IN OU T .
It is necessary to use relative values instead of absolute ones as in the general case dimensions are not of the same nature. Note also that these aggregators present the advantage of being easily extensible to more than 2 dimensions. Nonetheless, they present the disadvantage of giving priority to resolving capacity constraints and ignore the conflicting aspect of the problem addressed, which may lead to an overestimation of the necessary number of controllers. This can be highlighted by the following example.

Let us suppose that at the end of an assignment process two last functions f j , f k remain such that f j > f k according to both previously defined sorting criteria. It is also supposed that there exists only two controllers C 1 and C 2 that offer enough capacities to host f j and f k but cannot host both of them at the same time (Fig. 2). Then, according to Algorithm 3 and a criterion based on relative consumption, f j is assigned first to C 1 . Now, if it is supposed that a function f i that is in conflict with f k is already assigned to C 2 , then a new controller C 3 must be created to assign f k (Fig. 2a) while a better solution would have been to assign f k to C 1 and f j to C 2 (Fig. 2b). In order to overcome such a case another aggregator is considered. This agregator sorts functions according to

• nbrConflicts: their number of conflicts +( cpui CP U + inouti INOUT )/2.
According to the first term of this sum, the more a function has conflicts with other functions the more it is preferable to assign it first. Functions with no conflicts will be assigned at last. The second term is a relative mean of capacities consumption that permits to differentiate functions with the same number of conflicts. The value of this second term is intentionally smaller than one in order to avoid disrupting the influence of the first term.

The impact of these different criteria will be discussed through experiments in the next section.

E. Complexity of the heuristic

In its original version, the First-Fit Decreasing algorithm has a complexity O(n log n + kn); n being the number of monodimensional items to be assigned and k the number of bins in the solution. The first part O(n log n) is the result of the sorting of items performed at the beginning of the algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] and the second part O(kn) is due to the fitting-in test. This last part supposes that the FFD will have to visit all the bins before being able to assign any item. Using a 2-3 tree data structure [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF], the complexiy of finding the first bin with enough capacity can be improved to O(n log k) instead of O(kn). However, this structure assumes that bins can be ordered (i.e. sorted) which cannot be done when considering conflict constraints. In fact, conflicts are functions dependent unlike capacities that are controllers inherent.

In the d-dimensional case, the first part becomes O(n log n + dn) and the second part O(d × kn). If we assume that the number of conflicts of a function is of the same order of magnitude as the final number of controllers, the global complexity of the heuristic is

O(|F| log |F| + d|F| + d|C||F|) which is equal to O(|F| log |F| + d|C||F|).

VI. EXPERIMENTAL RESULTS AND DISCUSSION

The objective of this section is twofold:

• First, the accuracy of the results which are provided by the proposed heuristic is assessed by comparing these results to optimal solutions. This comparison must clearly be done on the basis of samples of reduced size (200 functions) because optimal solutions cannot always be obtained for full scale problems (10,000 functions), otherwise heuristics would not be needed. The impact of the three sorting criteria defined at Subsection V-D is studied too in this set of experiments with reduced size samples. • Second, the two safety-level management strategies developed in Section IV are compared on the basis of full scale samples.

A. Accuracy evaluation

The input data of the experiments whose results are given and discussed in this part are one thousand samples of 200 functions each. Those samples were generated automatically according to characteristics provided in a specification of anonymized data that specifies by mean of intervals and their proportions: cpu loads, number of inouts, number of functions by class, number of conflicting functions and for each conflicting function its number of conflicts (see. provided datasets).

Cost computation has been based on the assumption that a controller of a certain category is twice more expensive than a controller of the immediately below category and the optimal solutions were obtained by solving the ILP proposed in Section II by using the CPLEX solver [START_REF]IBM-ILOG[END_REF].

Before a thorough analysis of the results, two general conclusions can be drawn up: • In most cases, the optimal solutions were delivered by CPLEX in less than one minute per sample; however, some samples needed more than one hour to be solved.

The proposed heuristic provided a solution in less than one millisecond per sample thanks to the adopted greedy approach. If this solution is accurate, i.e. near the optimal, enough, as it will be shown in what follows, this very short runtime is a clear benefit of our contribution, even on small-sized examples. • For the optimal solutions, the controllers are on average filled up to 76% in INOUT and 96% in CPU. These optimal occupancy rates indicate how much of the capacities offered by the controllers are consumed in an optimal solution and, for bin-packing problems, may help to evaluate how hard is a sample to solve to the optimum using a heuristic. The high rates which were experimentally obtained, in particular for the cpu consumption, point out that the addressed problem was not trivial. However, the heuristic may provide for some samples an overestimation of the cost of the set of controllers that is required to host every function of this sample. This overestimation may come from the strategies to manage the different safety levels which are described in Section IV, the underlying packing FFD algorithm or the adopted sorting criterion used to solve the VBP with conflicts problem. The impact of the last two causes is studied in the remainder of this subsection; that of the first cause is the topic of the next part.

1) Impact of the FFD algorithm:

In order to isolate the impact of this algorithm from that of the safety-level management strategy, focus must be put only on the number of controllers of category 0 that is obtained at the end of the first step of Algorithm 1 (or 2); the numbers of the controllers of the other categories are not considered because they are computed at following steps and therefore depend on the strategy. Hence, experiments were performed to compute this number by using separately the three criteria described in Subsection V-D for each sample. The best solution, among the three obtained, was kept to evaluate the impact of the FFD algorithm.

Those experiments showed that the FFD algorithm computed the optimal number of controllers of category 0 for 97.3% of samples. This very high performance of the heuristic is closely related to the large number (several tens) of functions per controller that characterizes the solutions and that allows reducing the unused capacities. In fact, the FFD is known for suffering from a high fragmentation rate of unused capacities due to its policy that consists in choosing the first encountered controller in which a function can fit in. As a result, while the total of unused capacities in already created controllers might be several times greater than the needed capacities to host a function, the heuristic may not be able to assign this function otherwise than by creating a new controller because of the fragmentation. Fortunately, for cases with a high number of functions per controller, these unused parts of capacities are quickly and progressively filled in by the numerous small functions. The excellent result obtained using the adapted FFD proposed avoids adapting more advanced and consuming techniques to solve the VBP with conflicts [START_REF] Muritiba | Algorithms for the bin packing problem with conflicts[END_REF].

A detailed analysis of the results pinpointed that the criterion nbrConflicts that prioritizes conflicts resolution allowed by itself obtaining 96.8% of optimal solutions while each one of the other two criteria provides only 55% of such solutions. However, at this stage, it was too early to decide definitely whether to prune or not those criteria that consider only consumptions and not conflicts. Therefore, it was decided to deepen the analysis on the impact of the sorting criteria and their interaction with the safety-level management strategies.

2) Impact of Sorting Criterion:

Each step of Algorithm 1 or 2 requires to sort the functions that are considered at this step before assigning them. As three sorting criteria have been defined at Subsection V-D, two approaches are worth considering: using only one criterion for every step of a strategy or selecting several criteria for the different steps. The results obtained for these two approaches and the two strategies are given respectively at Table I and Table II. Three indicators were adopted to compare the criteria:

• NbrOptimal: The number of optimal solutions obtained.

• AvgRelInc: The average relative increase in cost.

• MaxRelInc: The maximum relative increase in cost. The second indicator is an average value over the thousand samples whereas the third indicator highlights the worst case performance.

a) Sorting according to only one criterion: Comparison of the first and second rows of Table II shows that sorting functions according to the relative mean of their capacities consumption performs slightly better than sorting by using the maxConsumption criterion for the class-based strategy. This is not true for every indicator for the other strategy; only 103 optimal solutions are obtained with the meanConsumption criterion whereas 116 such solutions are given when the functions have been sorted according to maxConsumption criterion. Hence, no definite conclusion about the relative interest of these two criteria can be stated from these results. This result must not be misinterpreted as a dominance of the vertex coloring facet of the addressed problem over the binpacking one, in which case the heuristic proposed at Section V would be considered as a greedy coloring technique, i.e. a technique that computes a coloring of the vertices by means of a greedy algorithm [START_REF] Kučera | The greedy coloring is a bad probabilistic algorithm[END_REF]. Actually, additional experiments have shown that, if the capacity constraints are removed, i.e. the capacities of controllers are considered infinite, the global number of controllers is reduced more than three times for every sample. This result highlights that, even if conflicts resolution may greatly impact the size of the solution, the bin-packing facet is what constrains the most the addressed problem.

This is confirmed by the last row of Table II, Best solution, that keeps for each sample the best solution amongst the three solutions obtained with the sorting criteria. Comparison of the results of this line with those of the third line shows clearly that the optimal solution can be obtained with another criterion than nbrConflicts for some samples, whatever the strategy. For instance, the percentage of optimal solutions obtained by the class-based strategy is equal to 56.2% with this only criterion and 59.8% for the best solution.

To sum up, if only one criterion must be selected for every step of a strategy, nbrConflicts is the most relevant choice. Nonetheless, better solutions may be provided exclusively by consumption-based criteria, for some samples. Consequently, the combined use of several criteria is a promising idea that is investigated in the following part.

b) Sorting according to several criteria: Table III reports the results of experiments where two (first three rows) or three (last row) sorting criteria have been combined for the different steps of the strategies. When the three criteria are used, 3 4 = 81 and 33 = 27 combinations are respectively possible for the class-based and the category-based strategies. This approach increases of course the execution time; nevertheless, this increase is not prohibitive, due to the short running time of the heuristic proposed to solve the VBP with conflicts (less than one millisecond per sample per combination) and to the possibility of running simultaneously several occurrences of Algorithms 1 and 2 with different combinations of criteria.

All indicators are improved, whatever the strategy, which shows that, within the same sample, different classes of functions may need different sortings. Combining maxConsumption with meanConsumption enhances the results which nevertheless stay far behind those obtained when one of these criteria is combined with nbrConflicts. More than 65% (resp. 75%) of exact solutions with the class (resp. category) based strategy are yielded in these cases (rows 2 and 3 of Table III). This is an improvement of more than 10% in comparison with the third row of Table II. The combination of the three criteria allows getting 2% more of exact solutions. Hence, this study clearly highlights that the combination of at least one consumption-based sorting criterion (preferably meanConsumption) with the conflicts-based sorting criterion is mandatory for more accurate results. Moreover, it matters to underline that the solutions obtained with these combinations of two or three criteria are very close to the optimal ones. The average relative increase in cost (AvgRelInc) is smaller than 1.5% and the maximum relative increase in cost (MaxRelInc) is less than 14%. This shows experimentally the quality of our contribution.

Last, no detailed comparison of the results that are provided by the two strategies from Table III will be carried out, even if it is clear that the category-based strategy seems better than the class-based strategy from this table. The results presented have been obtained with reduced size samples (200 functions each) indeed, while our objective is to deal with full scale samples (10,000 functions each). Comparison of the two strategies on this basis is the aim of the following subsection.

B. Safety-level management strategies comparison

At full scale, all indicators, and in particular the maximum relative increase MaxRelInc, are expected to be improved. This expectation relies on well-known results for the onedimensional bin-packing problem. In that case indeed, the FFD heuristic has been shown to use at most ( 11 9 • Optimal + 1) bins 3 [START_REF] Coffman | Approximation algorithms for np-hard problems[END_REF], where Optimal is the number of bins for the optimal solution, which in the worst case corresponds to a maximum relative increase of

( 11 9 •Optimal+1)-Optimal Optimal = 2 9 + 1
Optimal . Hence, higher is the number of bins in the optimal solution, better is the performance of the heuristic. Even if these formulas are using the number of bins and not the cost of this set of bins, a similar behavior is expected for the adapted FFD proposed in Section V to address the VBP with conflicts.

Several experiments have been carried out to compare the two strategies and assess their scalability. The input data of these experiments are one thousand samples of ten thousand These experiments reproduced at full scale the ones performed in the previous subsection, using several criteria, with the exception that no optimal solution was searched because this solution could not be obtained with CPLEX for this size of problem.

The results are reported in Table IV, where the indicator NbrOptimal has been replaced by NbrBest that features, for a given strategy and a criterion or a combination of criteria, the percentage of best solutions among those that have be obtained for every strategy and combination of criteria. The other indicators are also computed in a relative way. The execution time is a hundred times longer than in the previous experiment, where each sample was composed of 200 functions, which confirms the linearithmic (i.e. O(|F| log |F|) running time of the heuristic. Consequently, the proposed heuristic scales well and can be selected for the industrial application that motivated its development and for which only one sample is considered generally.

At full scale, the domination of the nbrConflicts criterion over the consumption based criteria is clearly confirmed. No best solution is obtained with one of these criteria or their combination. Moreover, it may be noticed that, for the classbased strategy, using the only nbrConflicts criterion provides 92.7% of the best solutions.

Unlike what was observed on reduced size samples, the class-based strategy takes the lead at full scale by delivering more than 97% of the best solutions. With only 42.3% of best solutions, among which only a little more than 6% are not already included in the set obtained by the class-based strategy, the category-based strategy obtains a very low score. However, despite this result, the overestimation of this strategy amounts to the cost of one controller of category 1 on average and two controllers of category 0 in the worst case. Brought back to the hundreds of controllers that compose the solution, this overestimation is around 0.1% on average and therefore not very significant. As the runtimes are short, the two strategies may be performed in parallel to be sure to always obtain the best solution when dealing with a given sample.

The accuracy of obtained best solutions was assessed by comparison to a lower bound that was computed on the basis of capacity constraints as follows. The smallest number of controllers of category 0 is computed such that the sum of their capacities exceeds the sum of consumptions of functions of class A. The sum of the remaining capacities of these controllers is then substracted from the sum of consumptions of functions of class B that is in turn used to compute the smallest number of controllers of category 1. This process is repeated again for functions of class C and NC to determine the smallest number of controllers of category 2.

The difference between the best solution and this bound is less than 0.9% in the worst case and 0.15% on average. These results highlight the accuracy of the heuristic to solve the problem addressed in this paper.

VII. CONCLUSION

This paper has shown that the industrial issue that consists in assigning a large set of control functions with different safety levels to safety compatible controllers, while satisfying capacity and separation constraints and minimizing cost, can be modeled as a Multiple-choice Vector Bin Packing with Conflicts problem. Two strategies have been proposed to solve this NP-hard problem; both are based on a FFD heuristic for which several sorting criteria have been defined.

Experiments on small-size sets of functions have clearly highlighted the accuracy of the results of this heuristic. Experiments with full scale sets have shown that both strategies scale well. The proposed method has been tested by a major company on a real instance of nuclear power plant including around 30,000 functions. The engineers performing the work confirmed that the technique scales well (a solution was obtained for every variant of the initial data set) and that the number of controllers was always smaller than that of usual solutions.

Nevertheless, it must be underlined that sets and not architectures have been considered in this work. Data exchanges between functions and communications on networks between controllers [START_REF] Kim | Design of networks for distributed digital control systems in nuclear power plants[END_REF] have not been taken into account. Considering these features for control functions assignment is a challenging issue for further work.

  Set of N controllers that hosts the whole set of functionsObjective : Minimize the cost of the set of controllers

Fig. 1 .

 1 Fig. 1. Overview of the assignment process.

• category 0

 0 can only host A-class and B-class functions, • category 1 can only host B-class and C-class functions, • category 2 can only host C-class and NC-class functions.

Algorithm 1

 1 Class based strategy 1: Pack functions of class A into controllers of category 0 2: Pack functions of class NC into controllers of category 2 3: Pack functions of class B into the remaining space of already used controllers of category 0 or 1, otherwise use new controllers of category 1 4: Pack functions of class C into the remaining space of already used controllers of category 1 or 2, otherwise use new controllers of category 2 Afterwards, the algorithm resumes at step 3 by packing functions of class B. It uses at first the remaining capacities in already created controllers of category 0 at step 1, and if this is not sufficient, it creates new controllers of category 1 as they are compatible and cheaper. Finally, at step 4, functions of class C are packed into the available space provided by already created controllers at step 2 and 3 and by creating new controllers of category 2 if necessary.

Algorithm 2

 2 Category based strategy 1: Pack functions of class A into controllers of category 0 2: Pack functions of class B into the remaining space of already used controllers of category 0 or 1, otherwise use new controllers of category 1 3: Pack functions of class C and NC into the remaining space of already used controllers of category 1 (only class C is compatible) or 2, otherwise use new controllers of category 2

Algorithm 3 4 :

 34 First-Fit Decreasing input: A set of functions F output: A set C of nbrControllers new controllers to which the functions of F are assigned 1: function FFD(F) 2:sortedF ← sorted functions of F in a non-increasing defined order 3:C ← ∅ and nbrControllers ← 0 for All functions f i ∈ sortedF/i ← 1 to |sortedF| do 5:

4 : 5 : 6 : 7 :

 4567 else if f i is of class B then Create a new controller C j of category 1 else if f i is of class C or NC then Create a new controller C j of category

Fig. 2 .

 2 Fig. 2. Impact of sorting functions according to their number of conflicts.

  This is not the case for the third criterion nbrConflicts. The third row of Table II confirms that sorting functions according to this criterion far outperforms sorting based on maxConsumption or meanConsumption.

			TABLE III
		COMBINING CRITERIA (VALUES IN %)
		Running time per sample per combination of criteria < 1ms
	Combined criteria	CLASS BASED STRATEGY NbrOptimal AvgRelInc MaxRelInc	CATEGORY BASED STRATEGY NbrOptimal AvgRelInc MaxRelInc
	maxCons. & meanCons.	31.2	4.28	21.43	23.2	4.77	20.00
	maxCons. & nbrConfl.	65.8	1.37	13.33	75.0	1.01	11.76
	meanCons. & nbrConfl.	65.9	1.34	13.33	76.0	0.95	10.35
	All three criteria	67.9	1.24	13.33	77.6	0.88	9.68

TABLE IV COMPARISON

 IV OF STRATEGIES AT FULL SCALE (VALUES IN %) Running time per sample per combination of criteria < 60 ms

	Combined criteria	CLASS BASED STRATEGY NbrBest AvgRelInc MaxRelInc	CATEGORY BASED STRATEGY NbrBest AvgRelInc MaxRelInc
	maxConsumption	0.0	3.16	4.35	0.0	4.09	5.27
	meanConsumption	0.0	2.76	3.93	0.0	3.47	4.57
	nbrConflicts	92.7	0.005	0.13	42.3	0.08	0.51
	maxCons. & meanCons.	0.0	2.69	3.93	0.0	3.40	4.57
	maxCons. & nbrConfl.	93.1	0.005	0.13	42.3	0.08	0.51
	meanCons. & nbrConfl.	97.2	0.002	0.13	42.3	0.08	0.51
	All three criteria	97.4	0.002	0.13	42.3	0.08	0.51
	functions each. The distribution of the functions into the
	different classes and the features of every function in a sample
	were generated automatically, as explained at the beginning
	of the previous subsection (see. provided datasets).

The worst-case ratio11 9 of the FFD can be even smaller when the items are much smaller than a fraction of the bin capacity; the interested reader is referred to[START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF] for further details on FFD performance ratios.

ACKNOWLEDGMENT

This work has been funded by the French Ministry of Industry as part of the CONNEXION project (Control systems for power plants) of the "Investments for the Future" program.


Frédéric Prost
email: frederic.prost@imag.fr

On the Impact of Information Technologies on Society: an Historical Perspective through the Game of Chess

The game of chess as always been viewed as an iconic representation of intellectual prowess. Since the very begining of computer science, the challenge of being able to program a computer to play chess, and to beat humans, has been alive and has been used both as a mark to measure hardware/software progresses and as an ongoing programming challenge leading to numerous discoveries. In the early days of computer science it was an affair of specialists. But as computers were democratized, and the strength of chess engines started to increase, chess players started to appropriate to themselves these new tools. We show how these interactions between the world of chess and information technologies have been herald of broader social impacts of information technologies. The game of chess, and more broadly the world of chess (chess players, litterature, computer softwares and website dedicated to chess, etc.), turns out to be a surprisingly and particularly sharp indicator of the changes induced in our every day life by the information technologies. Moreover in the same way that chess is a modelization of war that captures the raw features of strategic thinking, chess world can be seen as small society making the study of the information technologies impact easier to analyse and to grasp.

Chess and computer science

Alan Turing was born when the Turk automaton was finishing its more than a century long career of illusion 1 . The Turk automaton was supposed to be a machine playing chess. Actually it was operated by a human hidden in it (it took many years for the hoax to be found). Last year the french chess federation has suspended three titled players. They have been convicted of cheating during the chess Olympiad that took place in Khanty-Mansiysk on September 2010. In a century tables have completely turned: nowadays it is the machine that is hidden within the player.

Computer science, and more broadly information technologies, have changed the world so deeply, so quickly and so unexpectedly that it is difficult to grasp. Economists are found of paradoxical indexes such as the Big-Mac index [START_REF] Pakko | Burgernomics: A big mac guide to purchasing power parity[END_REF] (illustrating the purchasing-power parities among currencies) or the skyscraper index [START_REF] Andrew | The skyscraper index: Faulty towers[END_REF] (a correlation between skyscraper building and economic crises) that underly strange and funny correlations between a priori unrelated phenomenons. In this paper we develop such an index by showing how the interactions between the world of chess and computer science turn out to be particularly illuminating regarding the societal impacts of information technologies. In the same way that chess is a metaphor of war, we advocate that the interplay between information technologies and the chess world can be viewed as a metaphor of the more general issue of how information technologies and society have interacted together. Moereover, as we will show, it has not been exceptional that the chess world use of information technologies have precedeed mainstream uses. Thus, looking at todays relations between the world of chess and information technologies could be telling for the future of our digitalized era. Finally, the wolrd of chess is smaller than the real society. In the same way than chess captures the essence of strategic thinking in a concise and formalized way, the world of chess can be seen as a miniature version of society making it much easier to grasp and analyse.

The game of chess has already been used as an index of the social, and geopolitical, situation of the world. In [START_REF] Kasparov | My Great Predecessors -Part 1[END_REF] G. Kasparov shows how the best chess masters (and style of play) of every epoch have deep links with the most prominent ideas, and geopolitical conflicts. One of the first famous chess players was Ruy Lopez, a spanish priest of the 16th century. At the time Spain was dominating the world and was conquering the "new world". Then came the Renaissance and not surprisingly one of the best players, Domenico Lorenzo Ponziani, was from Modena in Italy. The next century was the one of the philosophers of the enlightment and its blind beliefs in rationalism: the best player was of course a french, François-André Philidor, and his famous saying 'the pawns are the soul of chess' was a clear announcement of the french revolution. The great rivalry between France and Great-Britain during the 18th and 19th centuries found an echo in the fights between french and britton players : La Bourdonnais vs Mc Donnell and Saint-Amand vs Staunton to cite but a few. The parallel between the world of chess and the one of ideas and geopolitical standings has continued until today (with the more than famous match Fisher vs Spassky in the middle of the cold-war). t suffices to look at the reigning world champions to see that the world has changed: Viswanathan Anand comes from India and the women world champion, Hou Yifan, is Chinese.

Chess as a tool to discover computer capacities

The game of chess is intimately related with computer science from the early beginnings of the latter. Indeed, the founding fathers of computer science, artificial intelligence and information theory, respectively Alan Turing, Norbert Wiener and Claude Shannon proposed programs and principles for chess programs in the early fifties. A time where computers were rather product of the minds than real objects.

At the time the questions in computer science were very fundamental and theoretical. The computer was a new artefact and it was not clear at all at what it could be used for, and where were lying its limits both from a theoretical and a practical point of view. It may look paradoxical since a computer is a very elaborated machine, thus it has not been invented or found by serendipity. Nonetheless, once created its scope remained largely unknown. So one could ask itself: how come that someone has built a very elaborated machine for which he did not knew exactly what to do with it? The short answer is that Turing machines were invented as a (negative) solution to the very fundamental question of the decidability of logic. The universal Turing machine was a byproduct of a proof regarding a theorem about the foundations of mathematics, more precisely the question was to find a generic method to state whether any given mathematical formula is true or not, together with a proof of this. One could argue that there is nothing farther from a practical perspective than these issues.

Therefore, it is natural that the first interactions between chess and computer science were focused on the investigation of the potentialities of the computers. In this perspective, the game of chess was seen as an interesting problem in order to unveil computer capabilities. The answers of the three funding fathers were all about the possibilities of the computers examined along three different perspectives: from an algorithmical point of view, from a practical point of view and from a philosophical/fundamental point of view.

In [START_REF] Wiener | Cybernetics, Second Edition: or the Control and Communication in the Animal and the Machine[END_REF] Wiener gives an algorithmic answer to the problem of chess programming. He exposes the raw principles of chess programming (which have not fundamentally changed until today), and shows how it is conceptually possible to program a decision algorithm by the combination of a minimax algorithm paired with an evaluation function (he considered a fixed depth search).

In [START_REF] Shannon | Programming a computer for playing chess[END_REF] Shannon gives very telling motivations on why the game of chess is especially well suited in order to discover the possibilities of computers. Indeed he wrote:

This paper is concerned with the problem of constructing a computing routine or "program" for a modern general purpose computer which will enable it to play chess. Although perhaps of no practical importance, the question is of theoretical interest, and it is hoped that a satisfactory solution of this problem will act as a wedge in attacking other problems of a similar nature and of greater significance.

It is clear for him that the quality of play, or the strength, of the computer are not the primary aim: he is looking for a problem that is not a mere computation. Indeed, he adds some very interesting remarks that strike by their premonitory status (remember that the paper was written in 1950 in an era where computers were barely existing), on why the game of chess is very interesting to study:

Machines of this general type are an extension over the ordinary use of numerical computers in several ways. First, the entities dealt with are not primarily numbers, but rather chess positions, circuits, mathematical expressions, words, etc. Second, the proper procedure involves general principles, something of the nature of judgement, and considerable trial and error, rather than a strict, unalterable computing process. Finally, the solutions of these problems are not merely right or wrong but have a continuous range of "quality" from the best down to the worst.

In [START_REF] Turing | Faster than thought, chapter Digital Computer applied to games[END_REF] Turing goes even deeper and unfolds the question "Coul'd one make a machine to play chess" from the bare problem of enumerating legal moves: i) Could one make a machine which would obey the rules of chess, i.e. one which would play random legal moves, or which could tell one whether a given move is a legal one ? to deeper philosophical questions: iv) Coul'd one make a machine to play chess, and to improve its play, game by game, profiting from the experience? To these we may add two further questions, unconnected with chess, which are likely to be on the tip of the reader's tongue. v) Could one make a machine which would answer questions put to it, in such a way that it would not be possible to distinguish its answers from those of a man? vi) Could one make a machine which would have feelings like you and I do?

Once again we see that at the heart of Turing's concern is the study of the computer capabilities (from raw computations to deep metaphysical concerns), and that chess is used as tool to discover them.

Chess as a measure of hardware and software progress

One of the interesting features of chess is that it can be used to measure a rich intellectual performance (a game of chess includes computations, spatial vizualisation, memory, long-term planing etc.) in a simple and relatively unbiased.

Moreover, due to the popularity of the game one can easily find players, or even tournaments, in order to measure the strength of a program.

Arpad Elo designed a rating system, which bears its name, based on the assumption that the chess performance of each player in each game is a normally distributed random variable (see [START_REF] Elo | The Rating of Chess Players, Past & Present[END_REF]). In doing so the rating of a player can be objectively computed: the basic idea is to compute the average rating of its opponents during a given period. The performance of the player is given by its percentage of wins during this period. If he has scored 50%, then its performance is the average of the rating of its opponents. If he had scored 75% then its performance would be 200 points above the average. The correspondance between the winning percentage and the elo points delta is taken from a gaussian curve generally flattened at 350/400 points (it means that a player with a rating 400 points higher than you is supposed to beat you 100% of the times). This rating system was first adopted by the US chess federation in 1960 and is now in use in most of the world chess federations and the international chess federation as well. Roughly speaking an average club player is ranked around 1500 elo points, over 2000 elo points are national level players. International Masters are over 2400 (around 3000 players in the world), Great International Masters are over 2500 (around 1000 players). The top ten is above 2760 and the all time record is Garry Kasparov's 2851 on the July 1999 and January 2000 lists.

Luke Muehlhauser has compiled the historical elo ratings of the strongest chess engines from 1963 to 2011 in [START_REF] Muehlhauser | Historical chess engines estimated elo ratings[END_REF]. It is remarkable that starting with a rating around 1500 elo for the early version of MacHack2 in the mid sixties towards Deep Rybka 3 and its estimated 3200 elo of 2011, the slope of progress has been strikingly linear. The progress of chess engines is hard to analyse in detail because there are so many factors to take into account, but an intuitive explanation can be the following: Ken Thompson (another founding father of computer science deeply interested in computer chess) made some very interesting experiments with Belle3 , see [START_REF] Condon | Belle chess hardware[END_REF]. He experimentaly discovered that, on average, a single extra ply in search depth corresponds to 200 elo points. If we take this for granted, then the linear rate of progression of chess engine can be seen as a corolarry of the Moore's law: the exponential progression of computers matches (up to some constant) the exponential combinatorics of possible moves in a game, and finally results in a linear progression in engines chess strength.

It became clear to anyone in the early sixties that computers were capable of playing decent chess, among other things. The question slightly shifted towards the speed of improvements and the limits of the computer strength: when will the computer be able to beat chess experts ? The society was slowly integrating the idea of computers and, as it is the case for every major scientific breakthrough, the reaction was a subtle blend of fears and excessiv optimism. The perfect illustration of these contradictory feelings is, once again, symbolically given through chess. It takes the form of a game of chess between a computer, HAL-9000, and an astronaut in Kubrik's "2001, A Space Odyssey" movie.

Chess as a pionneer of a computarized economy

Everything changed in the eighties with the apparition of personal computers and the democratisation of electronic equipments. Computers suddenly (in a decade give or take) ceased to be an affair of specialists to become everybody's affair. In 1977 Fidelity Electronics Chess challenger 1 is the first chess computer availabe for consumers. It was a computer dedicated to chess that looked like a chess set together with a rudimental interface to input and output the moves that looked like very much like a calculator. Here again we can see that the use of computers by the chess world announced broader social uses. Indeed, the more than famous "Speak and Spell" by Texas Instrument (remember "E.T. the extraterrestrial" ? E.T. was using a hacked "Speak and spell" to call home), often presented as a percursor of the electronic devices and toys of the eighties, is only available from 1978.

Together with the democratization of computers, the eithties marked a turning point in the use of computers. At first computers were used to ... compute things ! Indeed, in order to simulate complicated physical phenomenons like weather forecasts, solving fluid mechanics equations, computing ballistic trajectories etc. you need a lot of computational power. Yet, together with the increasing of storage capacities another important use of computers emerged: databases. Database management do not require complicated computations. It is the amount, and the structure, of informations that are hard to handle by hand. It is exactly where the computer can be useful at. Once again the chess world understood very quickly the advantages of computers to handle a large amount of informations. Chessbase GmbH is a company that was founded in 1985: this company proposed a chess database that was soon adopted by chess experts (whereas at the time chess experts did not used the chess engines that were too weak to help them in any way). As shows the following quote of G. Kasparov from [Che11], the arrival of chess databasses changed everything in the preparation of matches for professional players:

In January 1987 I was back to play another 'simul' against the Hamburg team. This time I had two days to prepare, so we dug out the names of all the players and checked their records in the computer. It was an eye-opener for me. It took about ten minutes to find 192 games. If I ask my trainers to find me a game, going through the books, it could take days. This time, armed with the information I needed, I beat six of the Hamburg team and drew with the other two. The result, 7-1, was extraordinary. They couldn't believe it. Because I knew their habits, I could lead them into traps.

This prefigures in a striking way the corporation's productivity gains thanks to computers and information digitalization. What were repetetitive tasks of information administration done by hand became quicker and automatic. Moreover, it became possible to perform those tasks without having to deal with a third part like a secretary (the trainers looking for specific games in the quote of G. Kasparov), providing a more direct access to information to managers.

Chess over the network

Another unexpected usage of computers started in the early 1990's with the quick democratization of networks: computers became able to communicate and build communities of people sharing common interests across the world. The possibilities opened by this extra feature, at first limited to the accademic world, were quickly developped to play with distant people. The Internet Chess Server opened in January 1992 and was amongst the firsts online game servers. It was not uncommon to find several hundreds of players simultaneously playing. Due to this success many clones appeared in several countries: german ICS, french ICS, dutch ICS etc. It was at a time when there was not yet a web browser (Mosaic appeared in 1993) and where the web traffic was litteraly exploding.

Almost every features of today's social networks were already present, albeit in a primitive way, on those chess servers. It was possible to chat, to give a short presentation of ourself (limited to 10 ascii lines), to define a list of friends, a list of banned people etc. There were also special communication channels regarding the subject of the topic (opening theory, technical issues, french speaking channel, etc.). At the time, in 1992, I was in the first year of study at "Ecole Normale Suprieure de Lyon". I remember that I had problems to make normal people (that is people nwho were not studying computer science) understand what internet was: the easiest way for me was to explain that it allowed me to play a live game of chess with some unknown person located on the other side of the earth.

It is during this period that information spread reached the speed of liberation. The emblematic CNN television channel is often given as the example of the fact that the world was becoming a small village in which everyone was going to know everything almost instantly. Interestingly the same phenomenon occured in the chess world, though in a more premonitory form, notably through M. Crowther's web site : "The Week in Chess" [START_REF] Crowther | The week in chess[END_REF] (often called TWIC). The web site was collecting every week, with the help of volunteers, all results and game scores of chess games played in tournament through the whole world. If CNN was a world-class broadcast news channel, it was still based on the old paradigm of top-down approach to information. What is striking in the example of TWIC is that it announces what had later been pompously called web 2.0 : a society more horizontal in which information does not come from the authorities to the people, but where informations are gathered by individuals. TWIC was quickly adopted by professional players who were feeding their databases with the latest games every week (a phenomenon which gradually announces the digital convergence of the following decades). It also marks the beginning of the end of the age of obscurity (other would say the begining of the era of massive surveilance). Suddenly every tournament chess game became available and known instantly around the world.

On the front of computer chess it gradually became clear that one day computers were going to be better player than the best humans. The only remaining question was when such a step would be done. In 1990 A. Karpov, vice world champion at the time, lost a game in a simultaneous event against Mephisto (a descendant of chess challenger), and in 1992 G. Kasparov won a match of blitz games (five minutes for the whole game) vs Fritz 2, winning 6 games, tying one but losing 4 games. It was the first time that a computer chess program won a game vs the world champion at speed chess. The first victory of a chess computer in standard tournament conditions was the one of Deep Blue vs G. Kasparov in 1996 (though Kasparov won the match 4-2). Finally, G. Kasparov lost a match vs Deep Blue in may 1997 though the history of matches was not finished: in 2002 Kramnik drew a match vs Deep Fritz winning and losing two games.

Even an individual game like chess gave rise to collective intelligence emergence thanks to networks. In 1999 G. Kasparov played a game in which he challenged the whole world over the internet [START_REF] Kasparov | Kasparov Against the World: The Story of the Greatest Online Challenge[END_REF]. Actually G. Kasparov was facing a team experts that gave several moves among which internet individuals had to vote: the most voted move was played. The game had a phenomenal success and it is estimated that more than 50,000 individuals from more than 75 countries participated. From every standard the game was of a very high quality. This game was a peculiar precursor of massively open source projects (i.e. projects not limited to professionals computer experts) in which a loose collection of individuals are gathered together in order to achieve a very elaborate product. Today this is best illustrated through the success of Wikipedia that was launched in 2001.

Digital convergence and pervasive computing

By the beginning of the 2000s the computers, because of their strength and constant availability, started to be used as a sparring partner by chess experts. Chess players tested opening ideas and were starting to use computers to analyse their own games (looking for tactical blunders, missed defences etc.). It was becomming possible for everyone to have an expert at home helping them to progress. It is not unlike what happened in a a lot of domains like music, picture and movie editing etc. in which a lot of what was limited to professionals became consumer grade.

But the most striking feature of the technological evolution was the slow but steady integration of different softwares and information sources together. It was very natural in the world of chess: to pair a chess database together with a chess engine (that can give you some advice on the position you are looking at) was an idea present from the start of chess databases. As we saw, TWIC was a first way to feed the database with a constant flux of information, by collecting every tournament games each week. More and more tournaments were starting to broadcast live the games: the chessboards are equiped with magnets and moves are directly transmited through the internet to chess servers like ICS. On those servers you have hundreds of spectators, and chess engines, giving their evaluation of the position, commenting the moves. The databases started to be feeded live and the computer-aided analysis of the game also becomed instantaneous while few years ago you had to write a book and to analyse the game with the help of Masters to obtain similar results.

The convergence took a step to the next level with the conjunction of smartphones (or ultra portable computers) with pervasive internet access. It is nowadays possible to connect to huge chess databases through the internet almost everywhere and to have world class level software running on your smartphone at the same time. The unexpected result of this combination is the apparition of numerous cheating cases in chess tournaments at every level: from the world championship, and the unglamorous so called "toiletgate" or "Bathroom controversy" of the 2006 chess world championship between V. Kramnik and V. Topalov4 , to local tournaments in which random players are seldom caught using electronic equipment to cheat. Perharps the more striking and elaborate case of cheating is the one mentioned in the introduction. Three titled players of the french team have been convicted of cheat during the 2010 chess olympiads. This case was remarkable in how it illustrates the new capacities of information technologies. In a nutshell the fraud was built like this: games were broadcasted live from Kanty Mansyisk on the internet. In France, a master was analysing the moves with a strong chess engine and a big chess database. Once an interesting move or variation was found he texted through a cellphone the move to a third player (actually the french team coach) who would indicate the move to be played through coded gestures. You have it all: network, databases, strong artificial intelligence, pervasive communications. In [START_REF] Rogoff | Technology and inequality[END_REF] economist K. Rogoff starting from this specific affair go as far as seeing in this the premises of a radical shift in our economy. Consider this quotation:

As skilled labor becomes increasingly expensive relative to unskilled labor, firms and businesses have a greater incentive to find ways to "cheat" by using substitutes for high-price inputs.

What is called cheating in chess translates into productivity gains in business. K. Rogoff argue that it could be the case that a lot of decisions that were taken by humans, and previously thought to be only manageable by humans, could actually be automatized.

The digitalized era

Today, the links between the world of chess and the information technologies are more intricate than ever. In an interview for Time Magazine [START_REF] Harrel | A bold opening for chess player magnus carlsen[END_REF], M. Carlsen, current number one on the chess rating list, said that he was not certain whether he has an actual chess board at his home : "I might have one somewhere. I am not sure". It gives a startling illustration of the degree of virtualisation reached in our society.

One can see direct influences of the information technologies on the game of chess. Overall chess players are tougher today, they have a more pragmatic approach and better defensive skills than before. This is largely due to the resilience of chess engines in difficult positions: computers have influenced the style of play of the new generations. Indeed a large amount of children have made their first step as chess players vs chess machines. Another point to notice is that it seems that today's player have a broader chess culture: thanks to database, it is possible to browse through thousands of games very easily. Because of this players tend to change their openings more often instead of repeating the same schemas in order to get over the opponents preparation. P. Svidler (six times champion of Russia), went as far as saying (admitedly he was half serious) that "the future belongs to 1. g3", a completly offbeat way of opening the games just to avoid any kind of preparation and play chess. This is the bright side, there is a darker one.

If the chess culture is broader it is also much lighter than before. Typically in todays tournament the average player goes to the internet to get the pairing of the next round of his tournament. Then he looks for the game of its future opponent in its database and looks quickly what are the openings played by its opponent. Then starts the so called preparation of the game: roughly it consists in the very quick visualisation of 5 to 10 model games (helped with a chess engine to find whether or not the opponent make typical mistakes) just before the round.

In the preparation process the player completly relies on the machine and its judgements. This can lead to disastrous results even at the highest levels. In the 2004 chess world match between V. Kramnik and P. Leko, V.Kramnik lost the 8th game without having play a single move. He blindly trusted an opening preparation (partially based on computer evaluation) that appeared to be flawed (Leko found at the board the refutation). As a chess trainer for kids I can testimony that the faith in the machine sayings is somewhat terrifying. Very young childrens can tell you that this move is better than this one because the computer says it evaluates the position as +0.26 for white in this variation instead of +0.17. I am afraid that this blind faith in machines and lack of critical spirit will generalize in our society. An interesting question is how will be resolved this tension between this blind faith in what the machine says vs the more open mind that machines helps to create. Indeed, thanks to the databases and the evaluation of what would have been called ugly/crazy moves or ideas but which appear to be playable thanks to the computers.

Another important evolution of chess is the ever shortening of time controls, especially regarding online chess. When I started to play chess online the basic time control was 2 minutes with 12 seconds added after each move (say 8 to 10 minutes per side for the whole game since on average a game lasts 40 moves). Nowadays it is almost impossible to find someone to play at such a slow pace.

The average blitz game is 3 minutes per side. There is even a new time category (standard time controls were divided along three categories: classical chess with 2hours for the first 40 moves, rapid chess with 20 minutes and blitz wich was traditionnaly 5 minutes per side for the whole game) called bullet or lightning for games with less than 2 minutes per side for the whole game. Needless to say that if it allows greater quantity, the quality of the play is serverly harmed. From a thinking and meditating game chess has become a game of interactions and reflexes thanks to computers. Because it is so much easier to play quickly with a mouse than with actual pieces and clocks. The field of human-computer interactions has also its word to say in this race: in a lot of chess server interfaces it is possible to make "premoves", that is to actually program your move even before your opponent has made its move. This is another warning for our digitalized society.

Though it can be noted that in 1912 Leonardo Torres y Quevedo built a real machine that could play King and Rook versus King endgames. It is arguably the first real chess playing machine built in history.

Interestingly MacHack won a game vs Hubert Dreyfus in 1967, a professor of philosophy at MIT that was hired to explore the issue of artificial intelligence. He wrote an essay, What Computers Can't Do[START_REF] Dreyfus | What Computer can't Do[END_REF] in which he exposed his controversial views on artificial intelligence. He also stated at the time that "a ten year-old can beat the machine".

Belle won every tournaments and world championships from 1980 to 1983

V. Topalov's team emited suspicions about the fact that V. Kramnik was spending long period of times during in the bathrooms during the games, and that it was the only place not under video and radio surveillance. This controversy led to Kramnik forfeit in game number


Fabio Zottele

Etienne Delay

Chasing the landscape capital in space and time: a model for Val di Cembra

Keywords: Viticulture, terraced landscape, landscape capital, landscape conservation

The landscape is the perception of a territory at a given time: it was shown that the landscape increases the perception of the quality of the wine to the consumer. The terraced, fragmented landscape of the Cembra Valley has been used for decades to identify the wine of the Trentino region (IT). However, we are witnessing a disintegration of the traditional terraced landscape to favor the aggregation of plots and the introduction of mechanization practices, still benefiting of the surrounding characterizing elements. This erosion of the landscape is reflected in the perception of an entire territory and therefore in the ability to bind a portion of the value of the wine to the quality perceived by the consumer through the landscape. In this sense, the landscape becomes a capital distributed in space and both the political choices and the individual choice modify and aggregates this common capital. So we decided to use the Agent Based Modeling to describe the dynamics of this capital in space and time in multiple scenarios spanning from the rigid conservation of the identifying elements of the territory up to the complete destruction of the traditional terraced landscape. We will here present a first attempt to define the landscapital to identify, in the future, its evolution is space and time and so providing the community and policy-makers with an operational tool to understand how today's choices affect the future landscape in the medium and long term.

The conceptual definition of the landscapital

With this work the authors want to summarize a path that starts from their first work and ends with the novel concept for the traditional terraced vineyards: the landscape capital or the landscapital. The imagery and the narration of the terraced, traditional viticultural landscape of Val di Cembra are used to promote concepts like the "viticulture of the mountains" and the "traditional viticulture", and regarding the commodities, to promote the wines produced in the entire region (both on the steep slopes and in the valley bottoms). The vine growers in the latter context benefit lower management costs due to the mechanization, the former must bear higher production costs for the impossibility to replace the manual work with the work o the machine and for the laborious conservation of the (dry)walls. However, the traditional terraced landscapes maintain a strong territorial identity and for such prohibitive working conditions are referred as "heroic viticulture". To describe this concept, the Center for Research, EnvironmentalSustainability and Advancement of Mountain Viticulture (CERVIM) identifies some morphological criteria that the author used to describe the Val di Cembra in their first works [START_REF] Delay | La Dialectique du Systeme: identifier statistiquement des territoires viticoles de terrasses, pour valoriser la viticlulture heroïque[END_REF]Zottele 2012). However, the tool developed by the authors did not explain why similar terraced landscapes with century-old traditions of vine growing evolved differently: some are still flourishing and other -just few kilometers awayare partially or completely abandoned. With their further works, the author developed the theory that a pillar of the resilience of the traditional viticultural landscape is the beneficial role of the co-operative association, potentially of any kind (Delay et al., 2015a). So the authors added another piece of the puzzle in the big picture that called "the existence/resistance of the traditional terraced viticulture". With these tools at hand, the authors focus now on another emerging phenomenon: the destruction of the terraced landscape with the remolding of the slopes to promote mechanization. This emergence fits both the pressure of the climate change on the viticulture and the mercantile dynamics (post)globalization: a) the terraced landscapes are becoming more and more attractive because their excursion of altitude can be a way to reach those quality standards that are more and more difficult to attain at lower altitudes (Delay et al. 2015b); and b) the higher management costs must be decreased due to a wine market that asks for the same quality at lower prices.

So, the approach of obliterating the traditional landscape may seem like a winning approach for the individual vine grower, but could not be convenient for all the community of vine growers: it has been proved that the landscape influences the perception of the quality of a wine [START_REF] Tempesta | The importance of landscape in wine quality perception: An integrated approach using choice-based conjoint analysis and combination-based permutation tests[END_REF]) and the trivialization of the traditional landscape and its symbols could weaken the power of the terraced landscape as a market promotion tool for the entire wine production region. For the authors, the traditional landscape and its symbols, could be consequently seen as a mean of production unevenly distributed in space and time, a capital shared collectively and whose distribution can be influenced by the choice of both single individuals and of the entire community.

The operative definitionof the landscapital

Being the landscape an emerging pattern of complex socio-economic interaction and morphological opportunities, the authors would use the Agent Based Model tool to study the spatial distribution of the landscapital and its possible evolution under multiple scenarios based on the choices of the vine growers that adapt to climatic pressure, economic dynamics, environmental and landscape protection policies. Before facing the formalization of the scenarios, that must be analyzed with an olistic approach, we should find an operational definition of the landscape and a credible way to describe its spatial and temporal attributes.

The author now agrees that the landscapital can be simplified as a two-component capital: a) the intrinsic component linked to the spatiotemporal distribution of the symbols the landscape is made of, and b) an extrinsic component liked to how the landscape is perceived. The latter component is made in turn of an intrinsic component (how the landscape is perceived by the single vine grower and by the local communities) and an extrinsic one (how the landscape is perceived by the strangers and how this perception is linked to the quality of the products). An Agent Based Model is suitable to describe such a complex system made of multiple interaction between a) the humansand the territory: what a vine growers decides to do with a vineyard has consequences on all the landscape;and b) the humansand other humans: the consequence of the choice of one vine grower on the other vine growers. With this tool we would like to shed light on the deep consequences for the simplistic adagiobasedon the evidence that the landscape is changing in just one direction andfora more profitableviticulturethe choice of mechanization must prevail over the conservation of the terraced landscape. The authors believe that, with an operational definition at hand, we could use scenarios based on the Agent Based Modeling to predict how the individual choices could influence the aggregation, dis-aggregation and concentration of such capital and use the result as: a) a guide for the communities to understand the value of the landscape as a mean of production and b) to help the decision makers in setting sustainable medium-long term policies for the development of high-identity wine production zones.