Jérémy Castéra
email: jeremycastera@gmail.com

Tago Sarapuu

Pierre Clément

Alain Abadie

Martine Choltus

Comparison of French and Estonian students' conceptions in genetic determinism of human behaviours PrePrint

Keywords: determinism, human behaviours, genetics, students' conceptions, innatism

We particularly thank the teachers who gathered data in Estonia

Introduction

Evolution of conceptions about genetic determinism in occidental societies

The debate on nature versus nurture is an old and persistent one [START_REF] Meaney | Nature, nurture and the disunity of knowledge[END_REF], albeit scientifically outdated, because the two concepts are in strong interaction, and not in opposition or addition. [START_REF] Jacquard | Eloge de la différence[END_REF] developed an analogy: trying to measure if bricks or cement contribute more to a wall is pointless, because without interaction between both there is no wall. When the debate is in favour of nature, this dominant belief is called 'innatism' and history reminds us that innatism is an ideology with serious consequences for our societies. Indeed, in the early twentieth century, French research in genetics led to the foundation of institutes of genetics and eugenics and in the US to the American Eugenics Society [START_REF]Les politiques eugénistes aux Etats-Unis dans la première moitié du XXe siècle[END_REF]. Eugenic laws were passed in some countries: 400,000 people were sterilized in Germany, 60,000 i n Sweden, 50,000 in the US, inter alia, in order to avoid the transmission of so-called hereditary diseases such as mental disability, prostitution, alcoholism, crime, epilepsy, etc. [START_REF] Garland | The social and economic origins of genetic determinism: a case history of the American Eugenics Movement, 1900-1940 and its lessons for today[END_REF]. Moreover, in Germany innatism was at the base of the Nazi ideal of a 'pure' race. After the Second World War, although these practices were fortunately abandoned, implicit innatist ideology is still propagated by the mass media [START_REF] Nelkin | The DNA mystique: the gene as a cultural icon[END_REF]. In fact, a simplistic method is often used by media to explain behaviours: one of the most famous was the supposed chromosome of crime in the 1970s [START_REF] Clément | Le mythe tenace du "chromosome du crime", encore appelé "chromosome de l'agressivité[END_REF]. Today, with the development of genetic sequencing, the press has latched on to 'the smart gene', although scientists do not use this expression (e.g. The Times article titled 'Smart genes?'; see [START_REF] Tang | Genetic enhancement of learning and memory in mice[END_REF]. Nevertheless, at least in France, several scientists (e.g. [START_REF] Jacquard | Eloge de la différence[END_REF][START_REF] Testart | Génétique: puissance et illusions[END_REF][START_REF] Atlan | La fin du "tout génétique[END_REF][START_REF] Kupiec | Ni Dieu, ni gène[END_REF][START_REF] Jacquard | L'avenir n'est pas écrit[END_REF] and philosophers (the most famous being Sartre and de Beauvoir, but also, more recently, [START_REF] Stengers | La vie et l'artifice : les visages de l'émergence[END_REF][START_REF] Keller | The mirage of a space between nature and nurture[END_REF] have alerted the public about these reductionist and dangerous ideas. They explain that we cannot reduce a complex behaviour to a simple genetic explanation: genes code for proteins and do not code directly for a behaviour which is always a complex interaction between a person and his/her surroundings in a precise situation. Today, different words are used to designate such conceptions: genetic essentialism [START_REF] Nelkin | The DNA mystique: the gene as a cultural icon[END_REF], geneticism [START_REF] Dambrun M Kamiejski R Haddadi | Why does social dominance orientation decrease with university exposure to the social sciences? The impact of institutional socialization and the mediating role of ''geneticism[END_REF], hereditarianism [START_REF] Forissier | Teaching "biological identity" as genome / environmental interactions[END_REF], and also the classical term innatism [START_REF] Castéra | Interaction entre connaissances scientifiques et valeurs dans les conceptions d'enseignants français sur le déterminisme génétique de comportements humains[END_REF]. [START_REF] Forissier | Teaching "biological identity" as genome / environmental interactions[END_REF] as well as [START_REF] Resnik | Genetic modification and genetic determinism[END_REF] and other researchers noticed that belief in a strong genetic determinism is often used to justify fatalism on the ground that behaviours are dictated by genes and consequently we are not responsible for our own acts. Moreover, psychologists such as [START_REF] Dambrun M Kamiejski R Haddadi | Why does social dominance orientation decrease with university exposure to the social sciences? The impact of institutional socialization and the mediating role of ''geneticism[END_REF] in France and [START_REF] Keller | In genes we trust: The biological component of psychological essentialism and its relationships to mechanisms of motivated social cognition[END_REF] in Germany showed that this innatism is linked with intolerant attitudes to several human groups (e.g. sexism, racism), genetic or biological differences being used for instance to justify belief in the superiority of some human groups [START_REF] Brun | Introduction à l'histoire de la controverse "inné/acquis[END_REF]. That is why teaching genetics for better citizenship is a great challenge. One of the aims of the BIOHEAD-Citizen Project (Biology, Health and Environmental Education for Better Citizenship, FP6, 2004-2008, European Community CIT2-CT 2004-5006015) was to analyse conceptions of genetic determinism of teachers of 19 nationalities with a questionnaire [START_REF] Castéra | Enjeux de l'enseignement de la génétique humaine[END_REF]Clément, 2008, 2010;[START_REF] Castéra | Enjeux de l'enseignement de la génétique humaine[END_REF]. The results showed a strong tendency to group teachers by country according to their answers about genetic determinism. The findings indicate the presence of different trends of conceptions according to country. Estonian teachers tend to be a little more innatist than French teachers.

Conceptions of determinism in education

What are conceptions?

According to [START_REF] Clément | Didactic transposition and the KVP Model: Conceptions as interactions between scientific knowledge, values and social practices[END_REF][START_REF] Clément | Conceptions, représentations sociales et modèle KVP[END_REF] conceptions are models of reference which enable the learner to understand concepts. Clément analyses conceptions according to three influences:

• Scientific knowledge (K): knowledge published and identified as scientific by the scientific community at a precise moment: usually current, but sometimes several years ago.

• Values (V): what we use for our decision-making. They justify opinions, ideologies or beliefs. For instance, innatism is a value because it is the belief that only genetics determines human features without scientific knowledge (or with some outdated knowledge).

• Social practices (P): this pole represents all individual or collective social practices, whether professional, religious, political, or other.

Clément explains that in order to analyse a conception of a person about a precise topic, it is necessary to place this person in different situations related to this topic (in this paper the different questions of a questionnaire). This enables us to mobilize several facets of their conceptions: several situated conceptions. From these it is possible to formulate hypotheses about trends of conceptions related to the specific topic [START_REF] Clément | Représentations, conceptions, connaissances[END_REF][START_REF] Clément | Conceptions, représentations sociales et modèle KVP[END_REF]. In this way it is possible to analyse the trends of conception differences in a group of subjects such as nations, religious groups, etc.

Goal and research questions

Students' conceptions were not taken into account in the BIOHEAD-Citizen Project, which only analysed teachers' conceptions on the determinism of human behaviours and performance. The goal of this study is to investigate the trends of students' conceptions on this topic. Clearly, we would hope not to find eugenic conceptions like those of the early twentieth century described earlier, but possibly a trace of innatism values as found in the mass media. The present work, conducted in France and Estonia, analyses students' conceptions on determinism of human features. These students' conceptions are then compared with the known teachers' ones.

(1) What are the main conceptions of Estonian and French students relating to the genetic determinism of some human behaviours? Are some of these conceptions dominated by values such as innatism? Are they correlated with other values such as intolerant values (e.g. sexism)?

(2) Are these students' conceptions correlated with other parameters apart from nationality?

(3) Are these students' conceptions coherent with teachers' conceptions (according to previous studies)?

Methods

Questionnaire

The questionnaire used in the present study is derived from the one designed for the BIOHEAD-Citizen project. The aim of this project was to analyse how aspects of citizenship can be promoted through biology, health and environmental education, taking into account the renewal of scientific knowledge as well as the social and affective dimensions. The project was structured by two main axes: a critical analysis of curricula and school textbooks and an analysis of in-service and pre-service teachers' conceptions from their answers to a questionnaire. The teams of 19 countries associated with this project, are composed by researchers with competencies in biology, health or environment and in human and social sciences, mainly in science education. We took two full years to design the BIOHEAD-Citizen questionnaire collectively (more details in [START_REF] Clément | Biology, health and environmental education for better citizenship: teachers' conceptions and textbook analysis in 19 countries[END_REF][START_REF] Munoz F Bogner | Teachers' conceptions of nature and environment in 16 countries[END_REF]. In the present study, the questionnaire is used to analyse students' conceptions thanks to five questions related to the possible biological/genetic determinism of some human behaviours. Some personal information was also asked of students: their gender, age, religion, degree to which they believed in God, and the education level of their parents.

Questions were structured in such a way as to analyse conceptions about genetic determinism of human behaviours as interactions between K (knowledge on genetics), V (mostly innatism, sexism and racism) and P (social practices). In the present work, we used the five questions which were the most important to differentiate teachers' conceptions in the BIOHEAD-Citizen Project [START_REF] Castéra | A gender effect related to teachers' conceptions of biological gender differences: A survey in 14 countries[END_REF]: see Table I.

Table I:

Five questions related to genetics and determinism of some human features.

Q1

Ethnic groups are genetically different and that is why some are superior to others.

I agree I don't agree

Q2

There are genetic factors in parents that predispose their children to be good in school. I agree I don't agree

Q3

The human genome contains more genes than the genome of any other living being. I agree I don't agree

Q4

It is for biological reasons that women more often than men take care of housekeeping.

I agree I don't agree

Q5

There are genetic factors in parents that predispose their children to become very good violinists.

I agree I don't agree

These five questions are based on a Likert scale: each student had to tick one of the four boxes from 'I agree' to 'I don't agree'. Q2 and Q5 convey only innatism ideology; scientists have never found clear evidence of music or intelligence genes.

Some journals have claimed the existence of such genes but most scientists agree that there is no proof of the genetic heredity of complex human behaviours. If Q1 and Q4 are linked to innatism ideology, they are also linked to intolerant attitudes like racism (Q1) or sexism (Q4). Indeed, according to the Oxford English Dictionary (http://oxforddictionaries.com/), racism is the belief that all members of a race possess characteristics, abilities, or qualities specific to that race which distinguish it as inferior or superior to another race. Sexism is defined by prejudice, stereotyping, or discrimination, typically against women, on the basis of gender. In the BIOHEAD-Citizen questionnaire, five questions deal with a possible biological argument justifying some gender differences; we observed a very strong correlation between the answers to these five questions and that is why we decided to keep only one of them in the present work. Q3 is linked to knowledge related to genome size, but can also be influenced by innatism: the belief that typically human performance is explained by a superior number of genes. We know that the number of human genes is approximately the same as those of the mouse, a few more than in a nematode, and twice as few as those in rice or roses, and human performances are correlated with the number and organization of neurones and synapses (cerebral epigenesis: [START_REF] Edelman | Neural Darwinism: the theory of neuronal group selection[END_REF][START_REF] Fernando | Copying and Evolution of Neuronal Topology[END_REF].

The sample

In total, 1,060 students (average aged 16-18) from the last two grades of upper secondary school filled out the questionnaire:

• Five hundred and fifteen in France, collected in four schools chosen to represent four different geographical areas (one rural, one urban, one suburban, and one combining all three in a medium-sized town). In two schools our data came from scientific, economic and literature classes, in one school from only technical and scientific classes and in one other school only from a scientific class. In scientific classes there are more lessons in biology than in others.

• Five hundred and forty-five in Estonia collected randomly in 17 different schools. Five schools come from rural and 12 from urban area, as it is not possible to differentiate more areas in Estonia. In the Estonian school system, there is no big difference between schools as in France. For instance, the number of biology lessons is the same in all schools -the only difference is in some optional courses. Nevertheless, few special schools introduce deeper foreign languages and cultures (e.g. British, German, French). One French orientated school is presented in our sample. In this school, students have to learn French language as well as French history, philosophy and culture since the first grade of elementary school (from the age of 6).

Procedure

The questionnaire was distributed to the students by the teachers during lessons. They generally needed between 10 and 15 minutes to answer the questions. The teachers ensured that the process was totally anonymous, collected the completed questionnaires immediately, and sent them to the researcher.

Data analyses

All computations were performed with the statistical software R with the multivariate analysis package ade4. Traditional χ2 tests were used with Bonferroni correction in order to avoid type I errors (when there is a chance difference owing to the multiple comparisons). Multivariate statistical methods were also used, mainly between-class analyses [START_REF] Dolédec | Rythmes saisonniers et composantes stationnelles en milieu aquatique II-Prise en compte et élimination d'effets dans un tableau faunistique[END_REF], to discriminate between groups of individuals (countries, gender, religions, etc.) according to the five questions together, in order to analyse which trends of conceptions differed the most between these groups. A Monte-Carlo permutation test [START_REF] Romesburg | Exploring, confirming, and randomization tests[END_REF] implemented in the ade4 libraries was then used to test the statistical significance of the difference between groups from the five instrumental variables (the five questions).

Results and discussion

Comparison of Estonia and France

Figures 1 to 3 show the distribution of the students' answers to the five questions in

France and in Estonia. Q5 and Q2 (Figure 1) concern the possible hereditability of being good at school or at music. In both cases the difference between the Estonian sample and the French sample is clearly significant (Q5: χ 2 = 90.7, df = 3, P < 0.001 and Q2: χ 2 = 203.4, df = 3, P < 0.001). Estonian students agree or rather agree with the genetic heredity of these performances more than French students (Q5: 46% in Estonia and 24%

in France; Q2: 63% in Estonia and 27% in France). The same trend for these two questions was found in the teachers' answer in both countries [START_REF] Castéra | Interaction entre connaissances scientifiques et valeurs dans les conceptions d'enseignants français sur le déterminisme génétique de comportements humains[END_REF][START_REF] Castéra | Enjeux de l'enseignement de la génétique humaine[END_REF]. At right: Q2 -Genetic factors and being good at school.

The result is quite similar for Q4 and Q1 (Figure 2). In Estonia, 40% of students agree or rather agree that : It is for biological reasons that women more often than men take care of housekeeping and 32% agree or rather agree that: Ethnic groups are genetically different and that is why some are superior to others. French students agree or rather agree to the same degree (10%) for both questions. The difference between

French and Estonian students is strongly significant (Q4: χ 2 = 209.1, df = 3, P < 0.001; Q1: χ 2 = 150.3, df = 3, P < 0.001). At left: Q4 -Biological reasons why women take care of housekeeping.

At right: Q1 -Ethnic groups are genetically different and superior to others.

Q3 (Figure 3) concerns the number of genes in the human genome. Figure 3 shows that 34% of French students versus 50% of Estonian students agree or rather agree that: The human genome contains more genes than the genome of any other living being. This difference is also strongly significant (χ 2 = 38.3, df = 3, P < 0.001).

Although this result could show a lack of knowledge about the number of genes in some species, it also shows that the idea of genetic determinism is stronger in Estonia. At the beginning of the Human Genome Project, researchers expected to find 100,000 to 150,000 genes in the human genome. Nevertheless, today we know that it contains fewer than 25,000 genes while some other species contain more genes. This information is more known or accepted by French (2/3) than by Estonian (1/2) students. In summary, the differences between the two countries are significant for the five questions, related to innatism (being a good violinist, Q2, or good at school, Q5; or thinking that human beings have more genes than other living beings, Q3), racism (Q1) and sexism (Q4). Moreover, between-analysis, followed by a Monte-Carlo test, showed very significant (P < 0.001) difference between French and Estonian students when questions were tested all together. This analysis also reveals a strong correlation between the answers to these five questions, Estonian students being more innatist than French ones. In consequence, our findings confirm a clear association of innatism with intolerant attitudes (like sexism and racism), as already shown by other researchers (e.g. [START_REF] Keller | In genes we trust: The biological component of psychological essentialism and its relationships to mechanisms of motivated social cognition[END_REF][START_REF] Dambrun M Kamiejski R Haddadi | Why does social dominance orientation decrease with university exposure to the social sciences? The impact of institutional socialization and the mediating role of ''geneticism[END_REF]. An intolerant answer was given (Q1) by 10% of French students and 32% of Estonian students. A preceding survey showed that only 5% of Estonian teachers and 3% of French teachers agreed or rather agreed with the same racist affirmation Q1 [START_REF] Castéra | Enjeux de l'enseignement de la génétique humaine[END_REF]. In both countries, the difference between As regards Q4, sexism is more present in Estonian students' answers (40%) than in French students' (12%), and even more present in Estonian teachers' answers (47%) than in French teachers' (3%), as shown in earlier works [START_REF] Castéra | Interaction entre connaissances scientifiques et valeurs dans les conceptions d'enseignants français sur le déterminisme génétique de comportements humains[END_REF][START_REF] Castéra | Enjeux de l'enseignement de la génétique humaine[END_REF]. In Estonia, the difference between teachers and students is not significant, but in France students are significantly more sexist than teachers when answering this question (12% v. 3%). There is an influence of age and, more probably, of the level of instruction. We discuss below the differences among Estonian and French students' answers.

These findings show trends of conceptions (all questions together) more innatist in Estonia than in France. Consequently, in comparison with our earlier work, it is possible to see strong similarities between students and teachers in both countries, even though some small differences can be found, with an effect of the level of instruction.

Sociocultural explanation

Do the results reflect a possible influence of media on the conceptions related to genetic determinism of human behaviours [START_REF] Nelkin | The DNA mystique: the gene as a cultural icon[END_REF][START_REF] Dambrun M Kamiejski R Haddadi | Why does social dominance orientation decrease with university exposure to the social sciences? The impact of institutional socialization and the mediating role of ''geneticism[END_REF]?

There is probably a difference between French and Estonian media in these terms. In France, several scientists and philosophers regularly warn that genetic determinism can be used as a justification for social fatalism regarding political or religious issues. An interesting example is the strong reaction of the scientific community to Nicolas Sarkozy's assumption of the genetic determinism of some human behaviours, e.g. juvenile violence or suicide, during the French presidential campaign in 2007 (Philosophie Magazine, 2007).

We note also that philosophy is an obligatory course in the last grade of French secondary school. The curriculum specifies that students have to learn the concept of determinism. This notion is studied in association with human liberty and free will. For instance, in 2011 the final national examination (the Baccalauréat) at the end of secondary school asked students to discuss this question: La culture dénature-t-elle l'homme? (Does culture change the nature of human beings?). To answer this question, students had to discuss the inseparable concepts of culture and nature (nature and nurture) and to support their argument by showing that we cannot be satisfied with simple genetic determinism. In Estonia, philosophy is only optional and depends on the school specialty. Even when schools choose this course, however, the concept of determinism is not under consideration. This difference between curricula can also partly explain the variation in answers between French and Estonian students, which are more generally anchored in the specific culture and history of the two countries. In France, the between-class analysis shows no significant difference between the schools: in the Monte Carlo test, the variance of the sample is no different from 1000 variances obtained randomly (Figure 4). The French sample is very homogeneous, which is why in a subsequent test (Figure 6) we can compare the different Estonian classes with the French sample (without differentiating between French classes).

The French sample

No difference between French schools

Factors distinguishing students in France

The between-class analyses and Monte Carlo permutation test do not show any difference between the religions (Muslims, Catholics, Protestants and agnostics/atheists) or between levels of religious practice and belief in God. There is also no significant difference according to the socio-professional categories of students' parents. Students following scientific curricula (with more knowledge on biology) do not differ from other students.

The gender of students is the only parameter significantly differentiating the students' answers according to the Monte Carlo test. The difference only relates to Q4:

It is for biological reasons that women more often than men take care of housekeeping (Figure 5). The difference between female and male students in France is strongly significant (χ2 = 42.7, df = 3, P < 0.001). French female students are more opposed than male students to this sexist affirmation. Only 5% of French female students agree or rather agree with it whereas 20% of French male students do. In France, female students are significantly more feminist than male students (Q4). 6a. This proximity was confirmed by a between-class analysis of French students (FR) and Estonian students from school E10, which does not show any significant differences (Monte Carlo test). The students' conceptions in the E10 school also significantly differ from those in other Estonian schools (Figure 6a).

The traditional French presentation of the question of determinism of human behaviours is linked to the history and the culture of the nation. Indeed, France has a long tradition of philosophical questions about the universality of human rights, egalitarianism [START_REF] Montesquieu | De l'esprit des lois[END_REF]Rousseau, 1755, etc. during the Century of Lights) and feminism (de [START_REF] Beauvoir | Le deuxième sexe[END_REF]. These philosophers have deeply influenced French society's thought on egalitarianism and feminism. That is probably why our results

show that feminist and anti-racist positions are stronger in France than in Estonia. This finding highlights the influence of cultural heritage. Conceptions of Estonian students in the school oriented to the French culture are very close to conceptions of French students. These Estonian students learn French history, literature, etc. and this has an impact on their own conceptions. The difference between Estonian schools remains even if we suppress school E10, showing strong disparities of trends of conceptions among schools in Estonia

Other factors distinguishing Estonian students

The same factors tested in France were used in between-class analyses and Monte Carlo permutation tests. As in France, there is no significant difference in terms of religion (Orthodox, Catholics, Protestants and agnostics), the levels of religious practice and belief in God, or the socio-professional categories of students' parents. In Estonia, the difference between male and female students' answers is not significant (from the between-analysis and Monte Carlo test), even if it is at the limit of signification for Q4 (χ 2 = 9.5, df = 3, P = 0.024), where the female answers are a little less sexist than the male answers (Figure 7). Female students are more feminist than male students (Q4), significantly in France but less significantly in Estonia. This result reinforces the idea that feminist heritage in France is stronger than in Estonia, especially for French females.

Conclusion and educational implications

The results, based on the answers of students, shows that the majority of students in both countries are not influenced by innatism, but a non-negligible proportion of answers is influenced by an innatist value. This is more important in Estonia than in France. It is shown also that students influenced by innatism agree more with sexist or racist affirmations. This finding is consistent with a structured mental model (a conception) whereby innatism can justify intolerant attitudes against some human groups. Few factors other than 'the country effect' distinguish students' conceptions on genetic determinism. These factors are always under influence of sociocultural aspects. This finding reinforces our hypothesis that the culture, history and media of each country have a very strong influence on the analysed conceptions. Interactions between science and sociocultural aspects are ubiquitous in human genetics.

We are aware that these findings relate only to answers to five questions about genetic determinism of human behaviours, but they are in total accordance with the results previously found for teachers' answers on a longer questionnaire. Similar trends of conceptions are present in Estonia and in France among students and teachers.

This work shows that, at least for one topic learnt during secondary school, the conceptions of students can differ from one European country to another. The sociocultural influence is undeniable. If we want to improve the role of schools in Europe in order to develop better citizenship, it is necessary to consider these sociocultural influences. Comparative studies are very important for European citizenship and can lead to specific teacher training and recommendations for school curricula in a particular country.

In the light of our results, we recommend introducing this epistemological and historical approach to genetics in schools. Teachers and students should learn from Garland (1997, p.77), with reference to the eugenic experiments of the past: 'There is an important lesson to learn from the past: genetic arguments are put forward to mask the true -social and economic -causes of human behavioural defects'. Explaining how science was used to justify ideology can help teachers and students to become aware of their own conceptions. Indeed, we suggest that epistemological genetics education can also lead to better tolerance, which is a pillar of citizenship, especially in context of the European construction. Moreover, an unclear conception of genetic determinism leads to an inability to participate fully in social life and potentially a lack of support for new genetic technologies (Marks, 2009, p. 1). The role of education is to give keys to citizens for their own decision-making.

Figure 1 :

 1 Figure 1: Comparison between Estonian and French students' answers about:

Figure 2 :

 2 Figure 2: Comparison between Estonian and French students' answers about:

Figure 3 :

 3 Figure 3: Comparison between Estonian and French students' answers about:

  students' answers is significant for Q1, showing a possible generational effect or an effect of education level.

Figure 4 :

 4 Figure 4: Monte Carlo permutation test on the variation between French schools. The test is not significant because the variation could be obtained by chance.

Figure 5 :

 5 Figure 5: Comparison between female and male students' answers about:

  culture. These students give answers very close to the French students' answers as represented in Figure

Figure 7 :

 7 Figure 7: Comparison between answers of Estonian female students and Estonian male students about: Q4 -Biological reasons why women take care of housekeeping.

This work has been supported by ERMOS (Estonian Research Mobility Scheme) in conjunction with the FP7 Marie Curie COFUND 'People'.

The Estonian sample

Differences between Estonian schools: a comparison with the French sample

The between-analysis based on the answers of students related to the five questions, followed by a Monte Carlo permutation test, shows a significant difference between Estonian schools (variance between only Estonian schools is different from variance obtained randomly, P < 0.001, Figure 6b). It means that the analysed students' conceptions differ in certain Estonian schools. The less innatist students' conceptions are observed in school E10 (Figure 6a), where Estonian students have a curriculum


Motivation ◮ Modern driver assistance systems require high standard security qualifications before entering the market. Konzernforschung What does "validate" mean? On road On software basis Test Drive many different scenarios and detect environment through sensors affected by errors Tests on different scenarios Collect data Collect driven data Collect simulated data Compare Among all the data how do we define a too early/late activation of ADAS warning or maneuver? Virtual Test Maker: Specification -Scenario Exemplary scenarios according to the VW database, collected by "GIDAS" (German In Depth investigation Accident Study) Most frequent scenarios considering all level of injuries (all MAIS) for occupants of car in both rural and urban roads (all local positions) Situations of conflict before a collision for occupants of passenger cars, all injuries (all MAIS), all local positions

Motivation

◮ Modern driver assistance systems require high standard security qualifications before entering the market.

◮ Important is to find mistakes in the software packages considering the sensor accuracy.

Motivation

◮ Modern driver assistance systems require high standard security qualifications before entering the market.

◮ Important is to find mistakes in the software packages considering the sensor accuracy.

◮ Currently, this requires exhaustive tests in real world scenarios, demanding high costs.

Motivation

◮ Modern driver assistance systems require high standard security qualifications before entering the market.

◮ Important is to find mistakes in the software packages considering the sensor accuracy.

◮ Currently, this requires exhaustive tests in real world scenarios, demanding high costs.

◮ Release testing of todays ADAS requires up to 2 million test km and 1.000 test drivers.

Goal

◮ We create a virtual test maker to shift the test from the street to simulation by using different optimal control techniques.

◮ Here, we focus on validating Collision Avoidance systems using Steering (CAS) and Braking (CAB) maneuvers. In particular, we investigate the activation times, which may be too early or too late due to sensor errors or algorithmic errors.

◮ We validate ADAS algorithms for driver assistance systems in collision avoidance (collision avoidance by braking and steering) through Virtual Test Maker (VTM).

Interpret the data to define when and why is ADAS algorithm giving a too early/late activation warning or maneuver Evaluate How can ADAS be improved? Look at specific scenarios where the activation of ADAS warning or maneuver is too early/late. How errors in sensor data affect a collision avoidance perspective.

What does "validate" mean?

z ′ (t) = f (z, u, t) a.e. t ∈ [0, T ], z(0) = z 0 ∈ R n . 4D Point Mass Model z = (x, y, ψ, v ), u = (w ψ , F B ). 7D-1 Single Track Model z = (x, y, ψ, w ψ , vx , vy , δ), u = (w δ , F B ).
7D-2 Single Track Model z = (x, y, v , ψ, w ψ , α, δ), u = (w δ , F B ).

◮ road geometry and obstacle geometry, position and motion → state constraints:

∀t ∈ (0, T ), z(t) ∈ K ⇔ g(z(t)) ≤ 0

◮ safety target → boundary constraints: ◮ compute an (optimal) trajectory to a secure target state: we need the objective function.

z(T ) ∈ Ω ⇔ ϕ(z (
◮ compute the reachable set from an initial state z 0

F R(T , z 0 ) = {z(T ) ∈ R n | given z 0 ∈ R n , ∃u ∈ U , z(u, z 0 )(t) is admissible for OCP, ∀t ∈ [0, T ]}
◮ compute the backward oriented reachable set starting from a secure state

BR(T , z 0 ) = {z 0 ∈ R n | ∃u ∈ U , z(u, z 0 )(t) is admissible for OCP, ∀t ∈ [0, T ]}
◮ often a projected reachable set is of interest, where π(z(T )) or π(z(0)) needs to be calculated with π being a projection from R n to the 2D or 3D space.

The mathematical details are in: ◮ output of CAB (three warning levels given as distance to the collision obstacle).

◮ acoustical warning is given in distance to collision obstacle w 1 ;

◮ brake warning is given in distance to collision obstacle w 2 ;

◮ automatic braking is given in distance to collision obstacle w 3 .

Comparison with CAB -Output of VTM

Comparison with collision by braking algorithm -Example of testing process

Input

Output of VTM

◮ Last point to brake and last point to steer for each warning level (top to bottom): acoustic warning braking warning automatic braking

Comparison with collision by braking algorithm -Example of testing process

Output of VTM

Comparison with collision by steering algorithm -Example of testing process

Output of VTM

◮ verify if an avoidance optimal trajectory is still admissible also with sensor errors;

States: xpos, ypos, vel, yaw angle, yaw angle vel, slip angle, steering angle. Controls: steering angle vel, braking force.

Comparison with collision by steering algorithm -Example of testing process

Output of VTM

◮ define r such that the optimal (red) trajectory is still admissible if sensor tolerance (in figure below is represented by r ) is smaller than a value depending on the scenario and on the trajectory; we have that for this specific case:

The

ODE-Sensitivity

The ODE-Sensitivity of the state is defined as the partial derivative of the state mapping with respect to p for a fixed optimal control:

S(•) := ∂z ∂p (û, p)(•)
and it is given by solving the sensitivity differential equation

S ′ (t) = f ′ z (ẑ(t), û(t))S(t), S(0) = dz 0 dp (p).
Considering the approximation to the optimal perturbed trajectory

z(û(p), p)(•) ≈ ẑ(•) + dz dp (û, p)(•)(p -p) = ẑ(•) + ∂z ∂p (û, p)(•)(p -p),
for fixed optimal control û, we can approximate trajectories for neighboring parameters.

back

FIACCO-Sensitivity

The Fiacco-Sensitivities of the state and the control are based on a parametric sensitivity analysis of the optimal solution: Such derivatives exist and can be computed using the linearized necessary Karush-Kuhn-Tucker conditions in an optimal solution (ẑ, û), as shown by A. V. Fiacco.

Considering the approximation to the optimal perturbed trajectory

z(û(p), p)(•) ≈ ẑ(•) + dz dp (û, p)(•)(p -p),
we can perform the perturbed trajectories.

Figure :

 : Figure : Several sensors to detect scenario (left). Warning of Advanced Driver Assistance Systems (ADAS) (right).

Figure :

 : Figure : ADAS algorithm (left) can give a false warning detected by tests on road (right).

Figure :

 : Figure : Several sensors to detect scenario (left). Warning of Advanced Driver Assistance Systems (ADAS) (right).

Figure :

 : Figure : ADAS algorithm (left) can give a false warning detected by tests on road (right).

Figure :

 : Figure : Several sensors to detect scenario (left). Warning of Advanced Driver Assistance Systems (ADAS) (right).

Figure :

 : Figure : ADAS algorithm (left) can give a false warning detected by tests on road (right).

Other◮

  Figure : Example of scenario construction.

Figure :

 : Figure : Example of scenario construction.

Figure◮

  Figure : Example of scenario construction.

  T )) ≤ 0 Virtual Test Maker: the OCP ◮ car model and initial states → states, controls and dynamics: Let u ∈ L ∞ ([0, T ], U ) a control policy with T > 0 and U ⊂ R m non-empty and compact, and z solution of the dynamicsz ′ (t) = f (z, u, t) a.e. t ∈ [0, T ], z(0) = z 0 (p), p ∈ R n parameter. 4D Point Mass Model z = (x, y, ψ, v ), u = (w ψ , F B ). 7D-1 Single Track Model z = (x, y, ψ, w ψ , vx , vy , δ), u = (w δ , F B ).7D-2 Single Track Model z = (x, y, v , ψ, w ψ , α, δ), u = (w δ , F B ).◮ road geometry and obstacle geometry, position and motion → state constraints:∀t ∈ (0, T ), z(t) ∈ K ⇔ g(z(t)) ≤ 0◮ safety target → boundary constraints:z(T ) ∈ Ω ⇔ ϕ(z(T )) ≤ 0◮ sensor tolerance → sensitivity analysis: it investigates the dependence of the solution ẑ := z(û, p) of the initial value problem on p for a fixed (optimal) control û = û(p) and the nominal parameter p. more Virtual Test Maker: the OCP ◮ question:

◮

  R. Baier, M. Gerdts, I. Xausa, Approximation of Reachable Sets using Optimal Control Algorithms, Numerical Algebra, Control and Optimization, 2013. ◮ I. Xausa, R. Baier, M. Gerdts, M. Gonter, C. Wegwerth, Avoidance Trajectories for Driver Assistance Systems via Solvers for Optimal Control Problems, Proceedings of the 20th International Symposium on Mathematical Theory of Networks and Systems, 2012. Compute an optimal trajectory for avoiding a collision by steering (optimal in the sense that is the fastest or the closest to the obstacle) in a particular scenario (P2) Compute the set of all initial points from which it is possible to avoid a collision in a particular scenario (P3) Compute the set of all end points that the car can reach from a given initial point in a particular scenario Verification part (V1) Validate collision avoidance by braking algorithm (CAB) for a test collision scenario (V2) Validate collision avoidance by steering algorithm (CAS) for a test collision scenario Comparison with CAB -Input of VTM ◮ a scenario (shape of road, obstacle positions and velocities, car position and velocity);

  radius of a ball around all initial values is 0.07873597 meters The radius of xpos is 9.32604041 meter The radius of ypos is 0.49497475 meter The radius of vel is 9.27426502 meter/sec The radius of yaw angle is 0.11286939 rad The radius of yaw angle vel is 1.27863692 rad/sec The radius of slip angle is 0.19859987 rad The radius of steering angle is 0

on road What does "validate" mean?

		On road On road On road	On software basis On software basis On software basis
	Test Test Test	Drive many different scenarios and detect environment through sensors affected by errors Drive many different scenarios and detect environment through sensors affected by errors Drive many different scenarios sensors affected by errors and detect environment through	Tests on different scenarios Simulations for different scenar-Simulations for different scenar-ios ios
	Collect data Collect data Collect data	Collect driven data Collect driven data Collect driven data	Collect simulated data Collect simulated data Collect simulated data
	Compare	Among all the data how do we	Interpret the data to define
		define a too early/late activation	when and why is ADAS algo-
		of ADAS warning or maneuver?	rithm giving a too early/late ac-
			tivation warning or maneuver
	Evaluate	How can ADAS algorithms be improved? Look at specific sce-
		narios where the activation of ADAS warning or maneuver is too
		early/late. How errors in sensor data affect a collision avoidance
		perspective.
	Our software aims to

Compare

Among all the data how do we define a too early/late activation of ADAS warning or maneuver?

Interpret the data to define when and why is ADAS algorithm giving a too early/late activation warning or maneuver Evaluate How can ADAS be improved? Look at specific scenarios where the activation of ADAS warning or maneuver is too early/late. How errors in sensor data affect a collision avoidance perspective.

Our software aims to substitute tests Compare Among all the data how do we define a too early/late activation of ADAS warning or maneuver?

Interpret the data to define when and why is ADAS algorithm giving a too early/late activation warning or maneuver Evaluate How can ADAS be improved? Look at specific scenarios where the activation of ADAS warning or maneuver is too early/late. How errors in sensor data affect a collision avoidance perspective.

Our software aims to substitute tests on road with virtual tests What does "validate" mean?

substitute tests on road with virtual tests to answer the unique evaluation question. Virtual Test Maker: Specification -Validation Goals

	Capabilities of VTM
	(P1) Compute an optimal trajectory for avoiding a collision (optimal in the sense that is the
	fastest or the closest to the obstacle) in a particular scenario
	(P2) Compute the set of all initial points from which it is possible to avoid a collision in a
	particular scenario
	(P3) Compute the set of all end points that the car can reach from a given initial point in a
	particular scenario
	1.)	2.)	3.)
		6,8% (873)	6,6% (848)		5,9% (761)
	4.)	5.)	6.)
	Verification part	5,1% (659)	4,6% (593)	301	4,4% (566)
	(V1) Validate collision avoidance by braking algorithm (CAB) for a test collision scenario
	7.)	8.)
	(V2) Validate collision avoidance by steering algorithm (CAS) for a test collision scenario 3,9% (505) 3,5% (450)
			Basis: 12.819 Passenger car occupants

Source: GIDAS

Warning level CAB Virtual test maker output acoustic warning w 1 last point to steer and last point to brake

	optimal	trajectory,	reachable area, initial
	initial state is w 1 ,	state is w 1 , considering
	considering	sensor	sensor errors
	errors

with controls (w δ , F B ) ∈ U 1 ⊂ U 2 ⊂ U 3

braking warning w 2 last point to steer and last point to brake with

			optimal	trajectory,	reachable area, initial
			initial state is w 2 ,	state is w 2 , considering
			considering	sensor	sensor errors
			errors
	automatic braking w 3	last point to steer	optimal	trajectory,	reachable area, initial
		and last point to	initial state is w 3 ,	state is w 3 , considering
		brake with controls	considering	sensor	sensor errors
		(w δ , F B ) ∈ U 3	errors

controls (w δ , F B ) ∈ U 2 ⊂ U 3

Comparison with collision by braking algorithm -Example of testing process

		Initial data		CAB warning distance	Virtual test maker
		vel	vel	acc	upper bound	lower bound	lptb [m]	lpts [m]
		car [km/h]	obst [km/h]	obst [m/s 2 ]	[m]	[m]
	w1	50	0	0	43.8889	32.222	34.229	16.880
	w2	50	0	0	31.6667	20.5556	18.589	13.750
	w3	acoustic warning 50 0 0	braking warning 19.4444 2.22222	13.462	automatic braking 11.342
	w1	150	0	0	130	100	270.345	45.148
	w2	150	0	0	98.3333	75	143.637	43.078
	w3	150	0	0	73.3333	2.72853	100.415	36.325

◮ Reachable set, robust reachable set and trajectories to reachable set (top to bottom) for each warning level (left to right) ( with perturbation ): Table : Summary of exemplary results.

Konzernforschung

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Virtual Test Maker

7D-2 Single

Comparison with CAS -Input of VTM

The tool should provide:

◮ a scenario (shape of road, obstacle positions and velocities, car position and velocity);

◮ output of CAS (a collision avoidance trajectory is computed).

Konzernforschung

Comparison with CAS -Output of VTM

◮ compute the backward reachable set for such scenario;

◮ compute sensitivity analysis for CAS avoidance trajectory to study the influence of parameters on the CAS trajectory;

◮ compute a maximum sensor tolerance in initial data measurements such that the CAS avoidance trajectory is still admissible.

Konzernforschung

Comparison with CAS -Example of testing process

Input

Output of VTM

◮ verify if the starting point from which the CAS draws the optimal trajectory is in a safety area (blue) or in a collision area (white);

Konzernforschung

Thanks for your attention!

◮ Questions? ◮ Further Information: ilaria.xausa@volkswagen.de Konzernforschung z := z(û, p) is the solution of the perturbed OCP with fixed optimal control û = u(p), and initial data z0 = z 0 (p) ∈ B(z 0 , r ) for some r > 0.

In first approximation we have (for r small) g(ẑ(θ)) + r M ⊥ θ ∇g(ẑ(θ)) ≤ 0 and so:

back

Comparison with collision by steering algorithm -Example of testing process

Input of VTM Scenario:

back

Comparison with collision by steering algorithm -Example of testing process

Input of VTM Scenario:

back

Comparison with collision by steering algorithm -Example of testing process

Input of VTM Scenario: CAS output: ◮ Car:


E Chasseigne Briani

Homogenization

Hamilton-Jacobi equations in εΩ i

λu ε (x) + H 1 (x, x ε , Du ε (x)) = 0 in εΩ 1 , λu ε (x) + H 2 (x, x ε , Du ε (x)) = 0 in εΩ 2 ,
(1.1)

ε ց 0 λ > 0 H i (x, y , p) := sup α i ∈A i {-b i (x, y , α i ) • p -l i (x, y , α i )} x ∈ R N , y ∈ Ω i , p ∈ R N .
Hamilton-Jacobi equations on εH : Ishii conditions

Assumptions

Standard assumptions on costs and dynamics in Ω i

Convexity assumption:

∪ α i ∈A i (b i (x, y , α i ), l i (x, y , α i )) is convex
Strong controllability assumption:

B i (x, y ) := b i (x, y , α i ) : α i ∈ A i ⊃ {|z| ≤ δ}, δ > 0
Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C

Optimal control characterization of extremal Ishii-solutions : Trajectories

Ẋ ε x0 (t) ∈ B X ε x0 (t), X ε x0 (t) ε a.e. t ∈ (0, +∞) ; X ε x0 (0) = x 0 B(x, y ) :=    B 1 (x, y ) if y ∈ Ω 1 B 2 (x, y ) if y ∈ Ω 2 co B 1 (x, y ) ∪ B 2 (x, y ) if y ∈ H Dynamics on the interface: y ∈ H, a = (α 1 , α 2 , µ) α i ∈ A i , µ ∈ [0, 1] b H (x, y , a) := µb 1 (x, y , α 1 ) + (1 -µ)b 2 (x,

Control characterization of extremal Ishii solutions: tangential Hamiltonians

Dynamics and cost at the interface y ∈ H:

b H (x, y , a) := µb 1 (x, y , α 1 ) + (1 -µ)b 2 (x, y , α 2 ) l H (x, y , a) := µl 1 (x, y , α 1 ) + (1 -µ)l 2 (x, y , α 2 )
Tangential Hamiltonians:

H T (x, y , p) := sup a∈A0(x,y ) {-< b H (x, y , a), p > -l H (x, y , a)} H reg T (x, y , p) := sup a∈A reg 0 (x,y ) {-< b H (x, y , a), p > -l H (x, y , a)} H T (x, y , p) ≥ H reg T (x, y , p)

Proposition

The tangential Hamiltonians are as regular as the data

Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C

Infinite horizon optimal control problems

Cost = J(x 0 ; (X ε x0 , a)) := +∞ 0 l X ε x0 (t), X ε x 0 ε (t), a(t) e -λt dt l (X ε x0 (t), X ε x0 ε (t), a(t)) := l 1 (X ε x0 (t), X ε x0 ε (t), α 1 (t))1 E1 (t) + l 2 (X ε x0 (t), X ε x0 ε (t), α 2 (t))1 E2 (t) + l H (X ε x0 (t), X ε x0 ε (t), a(t))1 E H (t)
Value functions:

V - ε (x 0 ) := inf (X ε x 0 ,a)∈T ε x 0 J(x 0 ; (X ε x0 , a)) V + ε (x 0 ) := inf (X ε x 0 ,a)∈T reg,ε x 0 J(x 0 ; (X ε x0 , a)) V - ε (x 0 ) ≤ V + ε (x 0 )
Known facts: BBC 2013-2014

Theorem V - ε and V + ε are viscosity solutions of the Hamilton-Jacobi-Bellman equations (1.1)-(1.2). V - ε is a subsolution of λv (x) + H T (x, x ε , D H v (x)) ≤ 0 for x ∈ εH. Theorem V - ε = U - ε V + ε = U + ε global (on R N ) (

Theorem (The cell problem for U

- ε ) ∀x ∈ R N , ∀p ∈ R N (frozen) ∃! C := H-(x, p) such that H -(x, y , Dv (y ) + p) = C has a Lipschitz continuous, Z N -periodic viscosity solution V -. Proof.
Classical, uses a stability result for the existence and the comparison result for H -for the uniqueness (ρ-problem)... Proposition H-(x, p) is regular (Lipschitz and coercive) and a comparison principle for the effective problem holds true.

Theorem (Main theorem for U - ε ) (U - ε ) ε>0 converges locally uniformly to U -the unique solution of λU -(x) + H-(x, DU -) = 0
Proof The classical methods of Lions-Papanicolaou-Varadhan and Evans-perturbed test function apply (the local comparison principle for H -is an essential tool).

Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C

Theorem (The cell problem for

U + ε ) ∀x, p ∈ R N (frozen) ∃! H+ (x, p) ∈ R such that ∃V + Lipschitz continuous, periodic function ∀τ ≥ 0, y 0 ∈ R N ( * )V + (y 0 ) = inf (Yy 0 ,a)∈T reg y 0 { τ 0 (l (x, Y y0 (t), a(t)) + b(x, Y y0 (t), a(t)) • p + H+ (x, p))dt + V + (Y y0 (τ ))} Proof.
Dynamic Programming Principle for the existence and uniqueness follows from the definition ( * ) and regularity of V + Proposition H+ (x, p) is regular (Lipschitz and coercive) and a comparison principle for the effective problem holds true.

Proof. Characterisation of the solution of the approximate cell problem as maximal subsolution.

Theorem (Main theorem for U

+ ε ) (U + ε ) ε>0 → U + unique viscosity solution of λu(x) + H+ (x, Du(x)) = 0 in R N .
Proof.

U + is a supersolution: EDP proof as in the U -case thanks to a local property of maximality. U + is a subsolution: a comparison principle concerning supersolutions and U + ε does not hold First case: b i (x, y , a) = b i (y , a), l i (x, y , a) = l i (y , a). Main tool: the perturbed test function is almost super-optimal The general case:

Trajectories in the definition of correctors: Żε(t) ∈ B x, Zε(t) ε Trajectories in the homogenization problem: Ẋε(t) ∈ B Xε(t), Xε(t) ε Approximating problems with dynamics constant in the slow variable Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C

  min{λu ε (x) + H 1 (x, x ε , Du ε (x)), λu ε (x) + H 2 (x, x ε , Du ε (x))} ≤ 0 on εH , a max{λu ε (x) + H 1 (x, x ε , Du ε (x)), λu ε (x) + H 2 (x, x ε , Du ε (x))} ≥ 0 on εH , (1.2) (1.1)-(1.2) is NOT a well-posed problem U + ε :=maximal sub-solution U - ε :=minimal super-solution

  y , α 2 ) Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C Optimal control characterization of extremal Ishii-solutions : regular and singular trajectories b H (x, y , a) := µb 1 (x, y , α 1 ) + (1µ)b 2 (x, y , α 2 ) REGULAR SINGULAR tangential : b H (x, y , a) • n i (y ) = 0 REGULAR: tangential and b i (x, y , α i ) • n i (y )≥0 ∀i = 1, 2 SINGULAR: tangential and b i (x, y , α i ) • n i (y )≤0 ∀i = 1, 2 n i (y ) unitary normal exterior vector to Ω i in y Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C

  and local) strong comparison principle for Lipschitz continuous subsolutions satisfying λv (x) + H T (x, x ε , DHv (x)) ≤ 0 lsc supersolution Notation λv (•)+H -(•, •, Dv (•)) = 0 ⇔ (1.1)-(1.2) and λv (•)+H T (•, •, D H v (•)) ≤ 0 Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C Plan Hamilton-Jacobi equations and optimal control problem Setting Assumptions The optimal control problems The homogenization result for U - ε The cell problem and the definition of the effective Hamiltonian. The homogenization result The homogenization result for U + ε The cell problem and the definition of the effective Hamiltonian. The homogenization result The 1-D case: an example when H+ (x, 0) = H-(x, 0) Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C Homogenization Results for a Deterministic Multi-domains Periodic Control Problem The homogenization result for Uε The cell problem and the definition of the effective Hamiltonian.

Nicoletta Tchou with G. Barles, A. Briani and E. ChasseigneHomogenization Results for a Deterministic Multi-domains Periodic C

Plan

Hamilton-Jacobi equations and optimal control problem Setting Assumptions

The optimal control problems

The homogenization result for U - The 1-D case: an example when H+ (x, 0) = H-(x, 0)

The data are independent of the x variable, then U + and U -are constants and only p = 0 is relevant in H± . Ergodic charactecterisation implies:

The best strategy is "singular" α 1 = 1 α 2 = -1 and cannot be used in the H+ -case. Finally H-= 0, H+ < 0

Nicoletta Tchou with G. Barles, A. Briani and E. Chasseigne Homogenization Results for a Deterministic Multi-domains Periodic C


Olivier Guéant

V(i) ⊂ N \ {i} the set of nodes j for which a directed edge exists from i to j (cardinal: d i ).

V -1 (i) ⊂ N \ {i} the set of nodes j for which a directed edge exists from j to i.

Asymptotic super-linearity of the cost functions: ∀i ∈ N , ∀K > 0, lim

λ∈R d i + ,|λ|→+∞ inf µ∈[0,K ] N L(i, λ, µ) |λ| = +∞.
We define the Hamiltonian functions

H(i, •, •) by: ∀i ∈ N , (p, µ) ∈ R d i × R N + → H(i, p, µ) = sup λ∈R d i + λ • p -L(i, λ, µ).

Nash-MFG equilibrium

We denote by A the set of admissible controls λ (L ∞ and deterministic).

For a given differentiable function

m : t ∈ [0, T ] → (m(1, t), . . . , m(N, t)) ∈ P N (total mass=1) we define: J m (i, t, λ) = E ˆT t (-L(X s , λ s (X s , •), m(s)) + f (X s , m(s))) ds + g (X T , m(T )) for (X s ) s∈[t

Nash-MFG equilibrium

Nash-MFG equilibrium A differentiable function m : t ∈ [0, T ] → (m(1, t), . . . , m(N, t)) ∈ P N is
said to be a Nash-MFG equilibrium, if there exists an admissible control λ ∈ A such that:

∀ λ ∈ A, ∀i ∈ N , J m (i, 0, λ) ≥ J m (i, 0, λ), and ∀i ∈ N , d dt m(i, t) = j∈V -1 (i) λ t (j, i)m(j, t) - j∈V(i) λ t (i, j)m(i, t)

G-MFG equations

The G-MFG equations consist in a system of 2N equations:

G-MFG equations N Hamilton-
d dt m(i, t) = j∈V -1 (i) ∂H(j, •, m(t)) ∂p i (u(k, t) -u(j, t)) k∈V(j) m(j, t) - j∈V(i) ∂H(i, •, m(t)) ∂p j (u(k, t) -u(i, t)) k∈V(i) m(i, t) with (m(1, 0), . . . , m(N, 0)) = m 0 .
Remark: in the literature on MFG, people usually do not care about verification (why?). On graphs, there is no issue as we shall find C 1 solutions. Under the assumptions made above, there exists a C 1 solution (u, m) of the G-MFG equations.

To prove this result we need a Lemma. This lemma is a comparison principle.

Let m : [0, T ] → P N be a continuous function. Let u : [0, T ] → R n be a C 1 function that verifies: ∀i, - d dt u(i, t)-H i, (u(j, t) -u(i, t)) j∈V(i) , m(t) -f (i, m(t)) ≤ 0 with u(i, T ) ≤ g(i, m(T )). Let v : [0, T ] → R n be a C 1 function that verifies: ∀i, - d dt v (i, t)-H i, (v (j, t) -v (i, t)) j∈V(i) , m(t) -f (i, m(t)) ≥ 0 with v (i, T ) ≥ g(i, m(T )). Then, ∀i ∈ N , ∀t ∈ [0, T ], v (i, t) ≥ u(i, t).
sup i∈N u(i, •) ∞ ≤ sup i∈N g(i, •) ∞ +T sup i∈N ,µ∈P N |H(i, 0, µ)| + T sup i∈N ,µ∈P N |f (i, µ)|.

Classical uniqueness result

It is possible to derive a uniqueness result equivalent to the one presented in Lasry-Lions' initial paper:

Theorem (Classical Uniqueness)
Assume that g is such that:

∀(ν, µ) ∈ P N × P N , N i=1 (g(i, ν) -g(i, µ))(ν i -µ i ) ≥ 0 =⇒ ν = µ.
Assume that f is such that: In words, this says that if people do not want to live together and if the cost to move does not depend on the number of people at specific nodes, then uniqueness is ensured. How can this be extended? By adding m in the the Hamiltonian functions! → Congestion models for instance.

∀(ν, µ) ∈ P N × P N , N i=1 (f (i, ν) -f (i, µ))(ν i -µ i ) ≥ 0 =⇒ ν = µ

General uniqueness result

Theorem (Uniqueness)

Assume that g is such that:

∀(ν, µ) ∈ P N × P N , N i=1 (g(i, ν) -g(i, µ))(ν i -µ i ) ≥ 0 =⇒ ν = µ.
Assume that f is such that:

∀(ν, µ) ∈ P N × P N , N i=1 (f (i, ν) -f (i, µ))(ν i -µ i ) ≥ 0 =⇒ ν = µ Assume that H is such that ∀i ∈ N , ∀j ∈ V(i), ∂H ∂p j (i, •, •) is a C 1 function on R d i × R N + .

General uniqueness result

Theorem (Uniqueness (continued))

Let us define A : (q 1 , . . . , q N , µ) ∈ N i=1 R d i × P N → (α ij (q i , µ)) i,j ∈ M N by: α ij (q i , µ) = - ∂H ∂µ j (i, q i , µ).
Let us also define ∀i ∈ N , B i :

(q i , µ) ∈ R d i × P N → β i jk (q i , µ) j,k
∈ M N,d i by:

β i jk (q i , µ) = µ i 2 ∂ 2 H ∂µ j ∂q ik (i, q i , µ).

General uniqueness result

Theorem (Uniqueness (continued))

Let us also define, ∀i ∈ N , C i : (q i , µ) ∈ R d i × P N → γ i jk (q i , µ) j,k
∈ M d i ,N defined by:

γ i jk (q i , µ) = µ i 2 ∂ 2 H ∂µ k ∂q ij (i, q i , µ).
Let us finally define, ∀i ∈ N ,

D i : (q i , µ) ∈ R d i × P N → δ i jk (q i , µ) j,k
∈ M d i defined by:

δ i jk (q i , µ) = µ i ∂ 2 H ∂q ij ∂q ik (i, q i , µ).

General uniqueness result

Theorem (Uniqueness (continued))

Assume that ∀(q 1 , . . . , q N , µ) ∈ N i=1 R d i × P N :             A(q 1 , . . . , q N , µ) B 1 (q 1 , µ) • • • • • • • • • B N (q N , µ) C 1 (q 1 , µ) D 1 (q 1 , µ) 0 • • • • • • 0 . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 C N (q N , µ) 0 • • • • • • 0 D N (q N , µ)             ≥ 0.
Then, if ( u, m) and (ũ, m) are two C 1 solutions of the G-MFG equations, we have m = m and u = ũ.

General uniqueness result -Proof

Sketch of proof:

Classical idea of computing the value of

I = N i=1 ˆT 0 d dt (( u(i, t) -ũ(i, t))( m(i, t) -m(i, t))) dt
in two different ways.

We first know directly that

I = N i=1 (g(i, m(T )) -g(i, m(T )))( m(i, T ) -m(i, T )).

General uniqueness result -Proof

We introduce: M(q 1 , . . . , q N , µ) the matrix of the Theorem Convex combinations of solutions:

u θ = θ u + (1 -θ)ũ and m θ = θ m + (1 -θ) m
A vector V :

V (t) = ( m(t)-m(t), (( u(k, t)-ũ(k, t))-( u(1, t)-ũ(1, t))) k∈V(1) , . . . , (( u(k, t) -ũ(k, t)) -( u(N, t) -ũ(N, t))) k∈V(N) ).

General uniqueness result -Proof

If we differentiate the expression in I and rearrange the terms (not obvious), we have:

I = - ˆT 0 N i=1 (f (i, m(t)) -f (i, m(t)))( m(i, t) -m(i, t))dt + J,
where

J = ˆT 0 ˆ1 0 V (t)M((u θ (k, t) -u θ (1, t)) k∈V(1) , . . . , (u θ (k, t) -u θ (N, t)) k∈V(N) , m θ (t))V (t) ′ dθdt.
Uniqueness then comes from M ≥ 0 and f and g decreasing.

Potential games

We consider the special case where:

The Hamiltonian functions (or equivalently the cost functions) do not depend on m.

There are two functions F and G such that:

∂F ∂m i = f (i, •) and ∂G ∂m i = g(i, •)

Potential games

We consider the problem of one planner:

sup λ∈A J (0, m 0 , λ) where J (t, m t , λ) = ˆT t F (m(s)) - N i=1 L(i, (λ s (i, j)) j∈V(i) )m(s, i) ds + G(m(T )) where ∀i ∈ N , m(t, i) = m t i and ∀i ∈ N , ∀s ∈ [t, T ], d ds m(s, i) = j∈V -1 (i) λ s (j, i)m(s, j) - j∈V(i) λ s (i, j)m(s, i).

Potential games -HJ equation

The HJ equation associated to this problem is:

∂Φ ∂t (t, m 1 , . . . , m N ) + H(m 1 , . . . , m N , ∇Φ) + F (m 1 , . . . , m N ) = 0 Terminal conditions: Φ(T , m 1 , . . . , m N ) = G(m 1 , . . . , m N ). The Hamiltonian function is H(m 1 , . . . , m N , p) = sup (λ i,j ) i∈N ,j N i=1     j∈V -1 (i) λ j,i m j - j∈V(i) λ i,j m i   p i -L(i, (λ i,j ) j∈V(i) )m i   = N i=1 m i H i, (p j -p i ) j∈V(i)

Framework

  Mean Field Games: Continuum of anonymous and identical (indistinguishable) players Graph G. Nodes indexed by integers from 1 to N. ∀i ∈ N = {1, . . . , N}:Each player's position: Markov chain (X t ) t with values in G Distribution of players: t → m(t) = (m(1, t), . . . , m(N, t))Instantaneous transition probabilities at time t:λ t (i, •) : V(i) → R + (∀i ∈ N )Introduction MFG on graphs: setup Existence result Uniqueness result Potential games and Master equation Assumptions Continuity: ∀i ∈ N , the functions L(i, •, •), f (i, •) and g(i, •) are continuous. Convexity of the cost functions: ∀i ∈ N , ∀µ ∈ R N + , L(i, •, µ) is a strictly convex function.

N

  transport equations defines a function F : u → m Bounds on u lead to bounds on dm dt Ascoli + Schauder permit to obtain a fixed point to m → F (B(m)).

  Uniqueness (continued))Assume that H does not depend on m. Then, if ( u, m) and (ũ, m) are two C 1 solutions of the G-MFG equations, we have m = m and u = ũ.

  Sketch of proof for the TheoremN HJ equations defines a function B : m → u Comparison principle leads a priori bounds on u

	Introduction
	MFG on graphs: setup
	Existence result
	Uniqueness result
	Potential games and Master equation

  This would be the HJ equation of the initial MFG equation, had we considered m a state variable. This is the Master equation!

	Introduction MFG on graphs: setup Existence result Uniqueness result Potential games and Master equation The Master equation Differenciating formally we obtain for U = ∇Φ the following equations: 0 = ∂U + N j=1 m j k∈V(j) ∂U i ∂m k -∂U i ∂m j ∂H(j, •) ∂p k MFG on graphs: setup Existence result Uniqueness result Potential games and Master equation Conclusion With potential games: 1 HJ equations N equations (Master equation) 2N equations for the underlying MFG problem. A solution is: m(0) = m 0 , d dt m(t, i) = (U Introduction j∈V -1 (i) ∂H(j, •) ∂p i (U -j∈V(i) ∂H(i, •) ∂p j (U k (t, m(t)) -U i (t, m(t))) k∈V(i) m(t, i)

i ∂t + H i, (U j -U i ) j∈V(i) l -U j ) l∈V(j) + f (i, •) U i (T , m) = g(i, m) k (t, m(t)) -U j (t, m(t))) k∈V(j) m(t, j) ∀i ∈ N , u(t, i) = U i (t, m(t, 1), . .

. , m(t, N))

Olivier Guéant Université Paris-Diderot. Laboratoire Jacques-Louis Lions. Mean field games on graphs

Questions?


The Bellman equation ◮ V fulfills the Bellman equation

V (x) = inf u∈U {c(x, u) + V (f (x, u))} =: L[V ](x)
with boundary condition V (T ) = 0.

◮ optimal feedback F (x) = argmin u∈U {c(x, u) + V (f (x, u))} (whenever the min exists) Numerical treatment

◮ assume V ∈ F ◮ approximation space A ⊂ F, dim(A) < ∞ ◮ projection Π : F → A ◮ discretized Bellman operator Π • L : A → A
◮ value iteration: choose V (0) ∈ A with V (0) (T ) = 0, V (n+1) := Π • L[V (n) ], n = 0, 1, . . . ◮ typical A: finite differences, finite elements (order p)

Nonlinear approximation

Theorem [Girosi,Anzellotti,'92]

If f ∈ H s,2 (R d ), s > d/2, we can find ◮ n coefficients c i ∈ R, ◮ n centers x i ∈ R d , ◮ and n variances σ i > 0 such that f - n i=1 c i e - x-x i 2 2σ 2 i 2 ∞ = O(n -1 ).

Scattered data interpolation

Problem

Given

◮ sites X = {x 1 , . . . , x N } ⊂ Ω ⊂ R d ◮ data f 1 , . . . , f N ∈ R, find a function a ∈ A such that a(x i ) = f i , i = 1, . . . , N. For A = span{a 1 , . . . , a N } we get Ac = f , with A ij = a j (x i ).

Radial basis functions

◮ radial basis functions a( • , x j ) = ϕ( • -x j 2 ) ◮ examples: ◮ Gaussian: ϕ(r ) = exp(-r 2 ), ◮ Wendland function: ϕ(r ) = (1 -r ) 4 + • (4r + 1)
◮ scaling:

a j = a ε j = ϕ(ε • -x j ) -1 -0.5 0 0.5 1 0 0.2 0.4 0.6 0.8 1 ε = 5 -1 -0.5 0 0.5 1 0.4 0.6 0.8 1 ε = 1
Oliver Junge Dynamic programming using radial basis functions

The Kruzkov transform

◮ problem: V (x) increasing, but ϕ(x) decreasing as x → ∞ ◮ Kruzkov transform: V → V = e -V (•) ◮ Kruzkov-Bellman equation V (x) = sup u∈U {e -c(x,u) • V (f (x, u))} =: L[V ](x), x ∈ Ω\T with boundary condition V (T ) = 1.
◮ under the assumption c(x, u) ≥ δ > 0 for x ∈ T , the Kruzkov-Bellman operator L is a contraction on L ∞ .

Dynamic programming using radial basis functions ◮ approximation space

A = A X ,ε = span{ϕ(ε • -x 2 ) : x ∈ X } ◮ interpolation operator on X Π : F → A ◮ discretized Kruzkov-Bellman operator Π • L : A → A ◮ value iteration: choose V (0) ∈ A with V (0) (0) = 1, V (n+1) := Π • L[ V (n) ], n = 0, 1, . . . Weighted least squares Problem Given ◮ sites X = {x 1 , . . . , x N } ⊂ Ω ⊂ R d , ◮ data f 1 , . . . , f N ∈ R, ◮ approximation space A = span{a 1 , . . . , a m }, m < N, ◮ weight function w : Ω → R with associated scalar product f , g w := N k=1 f (x k )g(x k )w (x k ) and induced norm find a function a ∈ A such that f -a w ! = min Optimal coefficient vector c: Gc = f A with Gram matrix G = ( a i , a j w ) ij and f A = ( f , a j w ) j .

Moving least squares

Idea

In computing an approximation to the function f : Ω → R at x ∈ Ω, only the values at sites x j ∈ X close to x should play a role.

◮ moving weight function w : Ω × Ω → R ◮ w (x, y ) small for x -y 2 large ◮ inner product: f , g w (•,x) := N k=1 f (x k )g(x k )w (x k , x) ◮ moving least squares approximation a of data f is a(x) = a x (x),
where a x ∈ A is minimizing fa x w (•,x) . ◮ given by solving the Gram system G x c x = f x A Shepard's method D. Shepard, A two dimensional interpolation function for irregularly spaced data, Proc. 23rd Nat. Conf. ACM, 1968.

◮ simply choose A = span{1} ◮ Gram matrix G x = 1, 1 w (•,x) = N i=1 w (x i , x) ◮ right hand side f x A = f , 1 w (•,x) = N i=1 f (x i )w (x i , x) ◮ thus we get c x = f x /G x = N i=1 f (x i ) w (x i , x) N i=1 w (x i , x) =:a i (x)
◮ and so the Shepard approximant is

Sf (x) = c x • 1 = N i=1 f (x i )a i (x)
◮ advantage: Shepard approximation requires no matrix solve

A = span w (x i , •) N i=1 w (x i , x) , x i ∈ X ◮ Shepard approximation operator S : F → A ◮ discretized Kruzkov-Bellman operator S • L : A → A ◮ value iteration as usual
Convergence of the value iteration

◮ f → Sf is linear, ◮ for each x ∈ Ω, Sf (x) is a convex combination of the values f (x 1 ), . . . , f (x n ), therefore ◮ the Shepard operator S : (L ∞ , • ∞ ) → (A, • ∞ ) has norm 1,
thus we get

Lemma

Value iteration with the discretized Kruzkov-Bellman operator S

• L : (A, • ∞ ) → (A, • ∞ ) converges to the unique fixed point of S • L. fill distance of X ⊂ Ω h = h(X , Ω) = sup x∈Ω min x j ∈X x -x j 2 If f : Ω → R is Lipschitz continuous with constant L then f -Sf ∞ ≤ CLh for some constant C > 0. ◮ sequence (X n ) n of nodes sets, X n ⊂ Ω, fill distances h n , Shepard operators S n , ◮ K < 1 contraction constant of L, ◮ V fixed point of L, Vn fixed point of S n • L Theorem If V is Lipschitz continuous, then V -Vn ∞ ≤ CL 1 -K h Example 1 A simple 1D example f (x, u) = aux, c(x, u) = ax, x ∈ [0, 1], u ∈ [-1, 1] ◮ optimal feedback u(x) = -1 ◮ optimal value function V (x) = x ◮ nodes X k equidistant with spacing 1/k ◮ T = [0, 1/(2k)] ◮ Ũ = -1 : 0.1 : 1 ◮ φ σ : Wendland function of order 4, σ = k/5
Example 1

A simple 1D example L ∞ -error fill distance h k = 1/k 10 -3 10 -2 10 -1 10 -3 10 -2 10 -1
Example 2

shortest path, geometrically complicated state constraints

We consider a boat in the mediteranian sea surrounding Greece which moves with constant speed 1, i.e.

f (x, u) = x + hu, c(x, u) ≡ 1, x ∈ neighborhood

Conclusion Pros

◮ simple convergence theory ◮ simple implementation, independent of state dimension ◮ easy to incorporate complicated state constraints Cons ◮ delicate choice of the shape parameter ◮ does not solve the curse of dimension ;-)

◮

  problem: dim(A) ∼ O(n d ) for error O(n -p )

◮◮

  of Greece with time step h = 0.1 and u ∈ {u ∈ R 2 : u = 1} ◮ T = neighborhood of the harbour of Athens ◮ X = equidistant in the sea on a 275 x 257 grid (50301 nodes) ◮ Ũ = {exp(2πij/20) : j = 0, . . . , 19} ◮ φ σ : Wendland function of order 4, σ = 10 of the forced pendulum ◮ c: quadratic deviation from the origin + quadratic in control ◮ T : neighborhood of the origin ◮ X : equidistant grid of 100 x 100 nodes ◮ Ũ = -128 : 8 : 128 ◮ φ σ : Wendland function of order 4, σ = 2.22 ◮ CPU time: 7 Jv + U), cost function c quadratic in s, v and u ◮ Ω: suitably chosen box ◮ Ũ = {6 • 10 3 u 3 | u ∈ {-1, -0.99, . . . , 0.99, 1}} ◮ T : neighborhood of the equilibrium (0.01, 0, 17.155) ◮ X : equidistant grid of 30 × 30 × 30 nodes ◮ φ σ : Wendland function of order 4, σ = 11.2 (x , u ) ... c = @ (x , u ) ... phi = @ ( r ) max ( spones ( r ) -r ,0) .ˆ4.*(4* r + spones ( r ) ) ; T = [0 0]; v˙T = 1; shepard = @ ( A ) spdiags (1./ sum (A ') ' ,0 , size (A ,1) , size (A ,1) ) * A S = [8 ,10]; L = 33; U = linspace ( -128 ,128 , L ) '; N = 100; X1 = linspace ( -1 ,1 , N ) ; [ XX , YY ] = meshgrid ( X1 * S (1) , X1 * S (2) ) ; X = [ XX (:) YY (:) ]; ep = 1/ sqrt ((4* prod ( S ) *20/ N ˆ2) / pi ) ; A = shepard ( phi ( ep * sdistm ( f (X , U ) ,[ T ; X ] ,1/ ep ) ) ) ; C = c (X , U ) ; v = zeros ( N ˆ2+1 ,1) ; v0 = ones ( size ( v ) ) ; TOL = 1e -12; while norm (v -v0 , inf ) / norm (v , inf ) ¿ TOL v0 = v ; v = [ v˙T ; max ( reshape ( C .*( A * v ) ,L , N ˆ2) ) ']; end contour (...