Laurent Turpin
email: laurent.turpin@inria.fr

Thierry Gautier
email: thierry.gautier@inrialpes.fr

Jonathan Rouzaud Cornabas
email: jonathan.rouzaud-cornabas@inria.fr

Christian Perez
email: christian.perez@inria.fr

P-Aevol: an OpenMP Parallelization of a Biological Evolution Simulator, Through Decomposition in Multiple Loops

Keywords: Loop scheduling, Irregular iterations, Multi-core, OpenMP, in-silico simulation

This paper presents how we have achieved the parallelization of Aevol, a biological evolution simulator, on multi-core architecture using the OpenMP standard. While it looks like a simple for-loop problem with independent iterations, the stochastic nature of Aevol makes the duration of the iterations unpredictable and it conveys a high irregularity. Classical scheduling algorithms of OpenMP runtimes turn out to be inecient. By analysing the origin of this irregularity, this paper present how to transform the highly irregular Aevol for-loop to a sequence composed by a small duration irregular for-loop followed by work intensive for-loop easy to schedule using classical LPT algorithm. This method leads to a gain up to 27% from the best OpenMP loop schedule.

Introduction

Scientic applications made the development of High Performance Computing more and more relevant. Frequently, these applications are based on independent iterations loops. Aevol is an example of such application. The purpose of Aevol is to simulate millions of generations of an evolving population of micro-organisms. Each generation consists of a for loop iterating over the population. For each individual, the model simulates their evolution through stochastic selection and mutations that consist on random modications of their structures. Our goal is to parallelize with OpenMP the evolutionary loop of Aevol, that is, at rst glance, a simple for-loop with independent iterations. The OpenMP API standard proposes 3 loop schedulers: static, dynamic and guided. Due to the Aevol stochastic model, the irregularity of the application requires a dynamic scheduler, like other scientic applications [START_REF] Lucco | A dynamic scheduling method for irregular parallel programs[END_REF][START_REF] Banicescu | Load balancing highly irregular computations with the adaptive factoring[END_REF], in order to well balance the workload between the threads of the parallel region.

We, as most of HPC developers, are concerned with the following questions. Can better schedule be computed for our application? What would be the gains? How to implement it? The underlying problem was at rst glance a list scheduling problem with unknown duration of tasks. Thanks to an analysis of the application structured as compositions of functions, we rene the problem by decomposing the loop in two sub-loops: the rst one being a loop scheduling problem with unknown durations that permits to estimate the iteration's duration of the second loop. By doing so, it becomes possible to use a clairvoyant list scheduling algorithm. Using a method inspired by LPT scheduling [START_REF] Graham | Bounds on Multiprocessing Timing Anomalies[END_REF] for the second loop, and thanks to a well balanced rst loop and a limited impact of sorting tasks, we gain up to 27% more performance than the OpenMP dynamic.

The remainder of this paper is organized as follows: Section 2 introduces the Aevol software, how its computation is structured and how it is characterized. Section 3 explains the methodology developed to split the loop and how we use the application data to design a new scheduling method and some practical implementations done with OpenMP. Section 4 deals with the experimental evaluations of these implementations. Related work is discussed in Section 5. Last, Section 6 concludes the paper and opens up some future work. [START_REF] Caballero | Developments in the prediction of eective population size[END_REF] Aevol, an Irregular Stochastic Program

This section presents Aevol, a computational biology software. It describes its computational model and characterizes the underlying main loop to parallelize.

Aevol: A Simulation of Darwinian Evolution

Biologists run in-vitro experiments in Petri dishes to observe the growth and evolution of simple organisms [START_REF] Card | Historical contingency in the evolution of antibiotic resistance after decades of relaxed selection[END_REF]. Aevol3 proposes to run the same kind of experiments but in-silico [START_REF] Hindré | New insights into bacterial adaptation through in vivo and in silico experimental evolution[END_REF]. Aevol is a C++ implementation of the biological model presented in [START_REF] Knibbe | Structuration des génomes par sélection indirecte de la variabilité mutationnelle : une approche de modélisation et de simulation[END_REF]. It makes use of a stochastic model that puts uni-cellular organisms in a well dened environment and lets them evolve. Each organism, or individual, encloses genetic code in the form of a sequence of characters representing its DNA. The information contained in the genetic code is treated and eventually forms the phenotype of the individual, i.e., its macroscopic behaviour or appearance. The phenotype is compared to an environmental target that models the environment where the micro-organisms leave. The dierence tells how well the individual ts the environment. In Aevol, the tness is represented as a scalar. For each generation, the whole population follows the three evolution steps:

1. Selection: the tness of each individual is computed. The higher the tness of an individual, the higher its probability of reproduction.

2. Reproduction: the survivors have the opportunity to pass their genetic code to their ospring. It is the principle of heredity.

3. Mutation: the new-born individuals may get random variations on the genetic code that may modify their phenotype and their tness.

The world in which individuals evolve is a 2D toric grid. In each cell of the grid lies one and only one individual. For each cell, competition is made among the 9 individuals of its neighborhood and only one of these 9 individuals is selected as the reproducer for this cell. That means that a single individual can reproduce multiple times within its neighborhood. After selecting all the reproducers for the entire grid, the population is wiped out and the reproducers are copied in the cells where they reproduce. Then mutation may occur randomly, depending on a mutation rate parameter dened by the user, on the DNA of the new population.

Their new phenotype and tness are computed. At runtime, the computation time of a generation is very short i.e., around 10 ms, thanks to a simple model and a small population. For instance in [START_REF] Liard | The Complexity Ratchet: Stronger than selection, weaker than robustness[END_REF], the population size was 1024 individuals for a 32 × 32 square grid with dierent mutation rates (10 -4 , 10 -5 and 10 -6 ). But they computed for a total of 81 millions of generations demanding weeks of computations. Improving the performance of one generation becomes essential especially since Aevol is evolving toward a more complex model [START_REF] Liard | A 4-base model for the aevol in-silico experimental evolution platform[END_REF].

Selection

Prepare mutation

List of mutations:

-type: switch loc: 236 -type: duplication loc: [26, 430, 14] -...

End of iteration

Translation

List of Proteins: -M: .2 H: .3 L: .1 -... -M: .4 H: .1 L: .4 -...

Compute Phenotype

Phenotype:

Compute Fitness

3.18x10 -18

Start of iteration space of iterations is the list empty ? no yes Fig. 1. Workow followed by each cell for one generation. The data (orange boxes) pass through the dierent functions (white boxes). The output is the tness value.

Computational Workow of Aevol

As mentioned previously, Aevol runs forward generation by generation. For each generation n, the population of generation n-1 is known. The evolutionary loop iterates on each cell. The selection step is a stencil computation. Each cell clones the selected individual (DNA, phenotype and tness) from neighborhood cells from generation n -1. In that way, all cell computations are independent and can be computed in any order. At the end of the generation, individuals have to wait for their neighbors to start the new generation. However, a global barrier is used to simplify the synchronization at the end of each generation.

Once the selection is done, the remaining computation of an iteration can be viewed as a sequential workow, as shown in Figure 1. An individual has a probability to mutate depending on the size of its DNA and the mutation rate specied as an user parameter. There are several kinds of mutation such as a one bit modication of the genetic code or duplication of the entire genetic code or even more. If an individual does not change, then all its information is known by its parent. For the others, so called mutants, their new DNA must be processed to compute their new tness. It consists mainly on reading and recognizing sequences of characters. These functions are mostly memory-intensive computation.

Dynamic Characterization of the Computation

The time to process an individual (i.e., a single iteration of a generation) strongly depends on its data (DNA) and if it is a mutant or not. The computation loop over the individuals is said to be irregular and it requires dedicated scheduling as discussed hereafter. The rst origin of irregularity comes from the distinction between mutants and non-mutants which do not follow the same process. Non-mutants are significantly faster to compute i.e., around 1% of the total runtime of a generation. This proportion depends on the mutation rate which inuences the number of mutants. Nevertheless, mutants always count for the large majority (99%) of the computation time. Besides, even among the mutants, we observe a large irregularity. As shown in Figure 2, a high density of individuals takes a similar amount of time to be processed, but there are still some individuals that can last up to 10 times longer than the others. In addition the distribution of these iterations varies depending on the generation and experimental parameters specied by the user. It is especially true for the mutation rate that can be strongly linked to size of the DNA [START_REF] Fischer | A model for genome size evolution[END_REF]. Last, because the evolutionary model is stochastic, it is not possible to know which and how individual will mutate before its computation. The duration of each individual is therefore a priori unpredictable.

Parallelization of the Evolutionary Loop

To accelerate the simulation time, it is necessary to parallelize the evolutionary loop. The main issue is a loop scheduling issue, with time per iteration at ne grain. We limit our presentation to multi-core architecture for which OpenMP is an acceptable parallel environment with good performance.

/* original pattern in Aevol */ for i = 1.. N do f itness[i] = compute(indiv[i]) Listing 1.1. Evolutionary loop. 1 # pragma omp parallel loop \ 2 schedule ( < arguments >) 3 for i = 1.. N do 4 f itness[i] = compute(indiv[i])
Listing 1.2. First parallelisation.

Straightforward performance with OpenMP loop schedulers

With OpenMP, a direct parallelization is to add a #pragma omp parallel for construct around the evolutionary loop that computes the new generation (see Listings 1.1 and 1.2). However, due to the irregular work load, one should not use the default static scheduler and should use instead dynamic or guided. Indeed, for our case static scheduler only performs a speedup up to 16 on 32 cores for the best conguration with lowest mutation rate. Table 1 reports the measured performance of this approach on a 16, 32 and 64-core machine against a sequential execution. By summing the duration d i of each iteration, we are able to compute the work W of a complete generation 4 in order to express the idle proportion

I = 1-W
p×Tp where the p cores stay idle during the time T p of the for-loop execution, with no iteration left to distribute and wait for others to nish their work. There are two important remarks. First, the work is inated when running on parallel NUMA architecture [START_REF] Olivier | Characterizing and mitigating work time ination in task parallel programs[END_REF]. That explains the poor eciency with respect to a lower idle proportion. Second, the eciency is not that good. It is important to realise that the number of iterations (the population size) is not that large in respect with the number of cores. Moreover, there are even fewer iterations that represent the treatment of mutants: Function compute of listing 1.2 is very fast for non-mutants. This kind of irregularity makes the guided scheduler ineffective [START_REF] Lucco | A dynamic scheduling method for irregular parallel programs[END_REF]. For the case of the dynamic scheduler, even with 64 cores, speed-up is only around 33. The idle proportion of the cores varies from 9% to 36%. This reveals work imbalance due to not so good schedule. The population size is a very important parameter for a biological point of view [START_REF] Caballero | Developments in the prediction of eective population size[END_REF]. Doing experiments with small, medium or large population will not produce the same results and cannot be interpreted the same way. Thus, we cannot blindly increase the size of population to convey more parallelism because the experiments will not be the same.

Scheduling Iterations Based On Their Data

A ner inspection of the evolution loop of Aevol shows that it iterates over a composition of functions

f n •...f 2 •f 1 applied to each individual (see Listing 1.3).
The classical list-scheduling algorithms [START_REF] Graham | Bounds for Certain Multiprocessing Anomalies[END_REF] such as implemented in OpenMP runtimes delivers medium level of performance with parallel eciency ranging from 37% to 63% as shown in the previous section. To increase performance of the loop scheduler, we need extra information to schedule loop with a better clairvoyance. For instance, LPT [START_REF] Graham | Bounds on Multiprocessing Timing Anomalies[END_REF] requires the knowledge of execution time for a better competitive ratio.

1 for i = 1.. N do 2 f itness[i] = fn • ...f2 • f1(indiv[i])
Listing 1.3. Initial evolutionary loop.

1 for i = 1.. N do 2 r[i] = f k • ...f2 • f1(indiv[i]) 3 for i = 1.. N do 4 f itness[i] = fn • ...f k+2 • f k+1 (r[i])
Listing 1.4. Our loop decomposition.

Our approach is to look whether the data generated during the execution of a function f k may give clues on the remaining computation of this iteration.

Accordingly, our methodology is to split the functions into two groups and to specialize the scheduling algorithm for each part: i) let schedule the rst k function calls f k • ...f 2 • f 1 with a non-clairvoyant scheduling algorithm, and ii) let use the data produced after this step to gain in information to better schedule the remaining function calls f n • ... • f k+1 by a clairvoyant scheduling algorithm. Listing 1.4 illustrates the resulting loops after having split the loop in two. The remaining questions are: Why not to split in more than two the composition? Which kind of clairvoyant loop scheduling algorithm? and nally: How to nd the right separator k to split the composition of functions? The rst question is related to the structure of the computation and we show a posteriori that splitting the loop in two is enough. Moreover, each loop decomposition implies a synchronization and we have found that a good trade-o for this application is two.

Because the computation is at ne grain, we have decided to select an existing loop scheduler with low overhead at runtime. Our nal choice was to base our second loop scheduler on the original LPT algorithm [START_REF] Graham | Bounds on Multiprocessing Timing Anomalies[END_REF] where individuals are sorted according to the size of their DNA after mutation. This information strongly correlates to the execution time of a mutant and the next sections focus on it.

Predicting the Execution Time

A deep analysis of the Aevol code and, more precisely, the underlying computational biological model, leading to the creation of the Figure 1, was necessary. Knowing, for instance, that the Translation function take as input the list of all the genes of an individual, we could induce the time of this function with the number of genes i.e., thanks to the output of the Find_Genes function. Going backward again, as genes are segments of characters inside RNA (which is also a segment of characters inside the total DNA), the more RNA will be found in the function Find_RNA, the more time function Find_Genes will take.

Finally, keeping the same logic, Figure 3 illustrates that the size of the DNA after mutation linearly correlates with the execution time of the iterations of the loop f n • ...f 2 (r[i]), where f 1 applies the mutations on one individual. The parameter of the linear model changes over the generations, but the linearity between size of DNA and execution time permits us to schedule loop with the LPT algorithm where individuals are sorted accordingly to their DNA sizes.

Simulation of LDNA schedule. To test our hypothesis, we collect the execution time of each function f i call on all the individuals and we simulate our scheduler called LDNA: as for LPT individuals are sorted decreasingly with their DNA size after mutation. We compare our LDNA with respect to LPT thanks to the postmortem simulation with known execution times. Figure 4 displays the simulated eciency for 100 generations with the dynamic scheduler of OpenMP (Dyn), LPT, and LDNA on a 64 cores machine. We see that LDNA almost achieves the performance of LPT which is almost optimal most of the time. Next sections present how to build LDNA for the evolution loop. Because the duration of the iterations of this loop are small and with less irregularity than the initial problem, we can apply a static scheduling. At this point, the computation for the non-mutants is nished and we only have to deal with mutants. As previously, we applied the simplicity of LPT schedule with the DNA size of the mutant. Iterations are sorted with this data by synchronize_sort() as shown in the listing 1.5. This function hides the complexity of managing the list of mutants which is a data structure shared by all the working threads. Multiple implementations of this list are discussed in the next section. Finally, the second loop is executed in parallel using the LPT rule with the mutant list as iteration space. The next section will present how we implement the LPT rule with OpenMP.

OpenMP Implementation of LDNA

The LPT rule is originally an o-line scheduling technique. Therefore, if one wants to implement it with OpenMP as an o-line scheduler, one must touch the OpenMP runtime. However, because our goal was to apply our solution without touching to the OpenMP runtime, we used the dynamic schedule with 1 iteration per chunks using an already sorted list for the iteration space as shown in Listing 1.5. This conguration will complete an LPT schedule if we assure that an idle thread will pick the next iteration on the logical order, i.e., the longest available iteration. Fortunately, OpenMP4.5 [START_REF]OpenMP Application Program Interface[END_REF] introduces the monotonic modier to be added to the scheduler (as shown on the second loop): it ensures that chunks are assigned in the increasing logical iteration order. An other issue was the management of the list of mutants shared between all threads and subject to concurrent accesses. Because of ne grain operation, the best implementation is a compromise between an algorithmic variant and the overhead at runtime. We have followed a pragmatic experimental evaluation of several variants that relies on dierent OpenMP features to manage it.

Our two promising implementations distribute the list where each thread keeps a local sorted list, then synchronization_sort (Line 7) merges all the data. In our rst implementation, the merge operation is be done in two ways: i) using the reduction construct of OpenMP4.0 or ii) do it ourselves. The rst implementation views concurrent list insertion as reduction operation between lists. It relies on the declaration of reduction operator, called by the OpenMP runtime, in charge of merge two lists. We call this implementation LDNA_Omp_Redux.

In our second implementation, all the local lists are merged by our program using a binary merge tree. This is LDNA_Par_Tree. Parallel merge may be of interest but it depends on the size of the list. A rst attempt has shown that parallelism variant does not outperform sequential binary merge with useful data size for our problem. So we call this implementation LDNA_Seq_Tree.

omp for vs taskloop The OpenMP standard propose another way of parallelism using tasks. The taskloop construct allows to execute and schedule chunks of iterations as tasks. One could even turn each sub function of an iteration in a new task and the program could convey more parallelism. However, the current implementations of OpenMP have tremendous overhead at the creation of tasks [START_REF] Gautier | On the Impact of OpenMP Task Granularity[END_REF] prohibiting their use in the case of lots of small tasks. This is why we only use the omp for construct for our implementation waiting for evolution in the tasks management by the OpenMP runtimes. Experimental Results

This section deals with the evaluation of LDNA against the dynamic schedule of OpenMP. For the experimentation, the program was compiled with GCC 8.3, linked with jemalloc5.2.1 [START_REF] Evans | A Scalable Concurrent malloc(3) Implementation for FreeBSD p[END_REF] as a memory allocator more suited for parallel allocations. The OpenMP runtime is libGOMP and the execution was done on a yeti node running on Debian 10 from the Grid5000 platform. A node is equipped, with 4 Skylake Intel Xeon Gold 6130 processors for a total of 64 cores (Hyper-Threading was not used) and 768 GiB of memory on 4 NUMA sockets. The memory allocation policy is the rst-touch policy. As the computation of a mutant asks the thread to copy (meaning memory allocation) the ancestor and then work on the copy a thread will then work on his local NUMA node to process a mutant. We select the libGOMP runtime because other runtimes (from LLVM or Intel), did not show signicant dierence in performance.

Protocol of Experimentation

All the experiments were populated with 1024 individuals (see reason in section 2.1). Three mutation rates are used: 10 -4 , 10 -5 and 10 -6 . For each mutation rate, we did 4 repetitions with dierent seeds for the random generator. For each experiment, we selected 6 starting generations separated by 50,000 generations from Generation 1000 to Generation 251,000. For each the 72 starting generations, the protocol of execution was the following: for doubling numbers of cores from 4 to 64 (using the least NUMA nodes possible thanks to numactl), we computed 100 generations in which we timestamped the beginning and the end of each iteration. During our preliminary study of Aevol, we observed that the behavior of the computation only changes on large scale of generations. This explains why we take this few contiguous generations but spread on 251,000 generations.

Results

The following gures summarize data averaged on all the executions. We observed that the rst 3 generations had a strange behavior certainly due to a warming up eect and they are not counted in these means. Figure 5 compares the proportion of the time taken by the synchronization_sort step during one generation. LDNA_Seq_Tree shows itself the best option over the two solutions. For the case of LDNA_Omp_Redux, the results were surprising and further analysis shows that all the operations of reduction occur sequentially with lots of time spent in the OpenMP runtime. We chose to continue experiments with LDNA_Seq_Tree as our LDNA scheduler.

Figure 6 compares the speedup of our LDNA scheduler with the reference dynamic scheduler of OpenMP (Dyn). It is clear that LDNA outperforms Dyn. For 64 cores the LDNA scheduler is on average 19%, 21% and 27% faster for respectively 10 -4 , 10 -5 and 10 -6 mutation rates. In Figure 7, an example of the execution of one generation with mutation rate 10 -5 is given. It shows how LDNA With the latter, the mutants (blue) and non-mutants (red) are treated in a random order, explaining why large mutants are computed only at the and. For LDNA, non-mutants are all treated in the rst part which is scheduled statically. This reduces the schedule overhead that the non-mutants induce compared to the Dyn scheduling. The second part only computes what remains for the mutant in a specic order that permits to compact all the iteration. The blank part corresponds to the sort and merge of the list of mutants. For this example, it takes about 0.03 ms which represents 5% of the computation time (On average for a mutation rate at 10 -5 , it is 5.8%, gure 5). For 10 -4 and 10 -5 mutation rates, the idle time proportion, without counting synchronization and sort, dropped to a maximum of 7%. In the case of 10 -6 mutation rate, we can see that it scales less than the others, and the idle time is more dicult to reduce. In fact, the mutation rate is so low that the number of mutants reaches is about 60 individuals. Therefore, the number of iterations is very close to the number of cores and sometimes less. The program lacks of parallelism and a solution would be to parallelize at the sub-functions grain. As seen in section 3.5 this could be easily done with task parallelism but will suer the large overhead due to the current OpenMP runtime.

Evaluation on Larger Populations

If the size of the population is 10 times larger than in previous experiments, and future use of Aevol could use this for biological interests, the parallelism would be greater. As the number of iterations rises, a simple dynamic schedule could be enough and LDNA could suer from the overhead from the management of the mutant list. Nevertheless, LDNA succeeds to scale up the population better than Dyn. Larger experiments with 9.216 individuals on 64 cores show that our scheduling stay better but not as much. The dierence is around 12% with mutation rate at 10 -6 and 2% at 10 -4 . With the smaller mutation rate, mutants are enough so that Dyn suers from the irregularity. At the end, a larger population would mean that any scheduling algorithm would approach optimal result but simulations with small population will still be used in the future. However, to avoid prohibitive computation times, in the case of a larger population, we will have to use a larger number of cores and thus return to a similar scheduling problem that the one with 1.024 individuals on 64 cores. Still, LDNA could do better because we observe that NUMA eects became important and it is clear that the cores wait because of communication latency during the rst loop.

Taking NUMA into account would certainly improve LDNA scalability.

Related Work

Our scheduling problem is largely studied since at least 50 years. In [START_REF] Graham | Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey[END_REF], the P ||C max problem is presented as N P -complete. Two approaches exist to deal with this problem: whether the duration of iteration is known in advance or not. [START_REF] Hochbaum | Using Dual Approximation Algorithms for Scheduling Problems Theoretical and Practical Results[END_REF] is certainly the best o-line algorithm but LPT [START_REF] Graham | Bounds on Multiprocessing Timing Anomalies[END_REF] is a well known heuristic with great performance [START_REF] Coman | A Generalized Bound on LPT Sequencing[END_REF] and simplicity and an even better version has been developed by Cheng et al. [START_REF] Cheng | Algorithms better than LPT for semionline scheduling with decreasing processing times[END_REF].

When the information about the iterations is unknown before execution, the list-scheduling algorithm described by Graham [START_REF] Graham | Bounds for Certain Multiprocessing Anomalies[END_REF] is the upper-bound limit and the basic technique for most of the dynamic scheduler developed since. After an initial static distribution of the iterations, Durand et al. [START_REF] Durand | An Ecient OpenMP Loop Scheduler for Irregular Applications on Large-Scale NUMA Machines[END_REF] implemented a workstealing method with memory location awareness. Lucco [START_REF] Lucco | A dynamic scheduling method for irregular parallel programs[END_REF] presented a guided self-scheduling scheme improved with statistics computed on early iterations. In overall, the idea is to nd information during execution to rene the scheduling. Besides an approach applied in [START_REF] Penna | Design methodology for workload-aware loop scheduling strategies based on genetic algorithm and simulation[END_REF][START_REF] Penna | A comprehensive performance evaluation of the BinLPT workload-aware loop scheduler[END_REF] consists on letting the user provides workload estimation of the iterations before execution to perform near-optimal static scheduling and balance the nal workload with dynamic work-stealing to catch up the possible mistakes of the estimation. Our approach is similar but cannot use user-provided estimation because of the stochasticity of Aevol. Instead, it has to use estimation from the application itself and these estimation change generation after generation. Our method cannot be easily embedded into an OpenMP loop scheduler because it requires (manual) loop decomposition and analysis of the structure of the application. At this expense, we are able to improve existing loop OpenMP schedulers with up to 27% on ne grain loop. In this paper, we present a new methodology to schedule irregular independent iterations of an application structured as a composition of functions. Mixing non-clairvoyant and clairvoyant techniques, we show that splitting the execution of the loop in several loops is a valid approach if the data gathered in the rst loop help the scheduling of the next one. Applying our method to Aevol, a computational biology software, we implemented the algorithm LDNA to schedule the computation of evolving uni-cellular organisms. Experimental evaluations on a multi-core architecture computer show that our scheduler improves by about 27% the performance of the dynamic scheduler of OpenMP often used for irregular applications. We discuss on the implementation of the method and how to manage the synchronization to optimize the execution of our solution. As other work [START_REF] Penna | A comprehensive performance evaluation of the BinLPT workload-aware loop scheduler[END_REF] that uses workload-aware scheduler, we think that allowing the user to inform the runtime through the OpenMP standard would help this kind of method. The standard could accept an estimation function or even a way to pass a scheduler to be used by the runtime.

The management of the list of mutants brought to use a binary merge tree that we kept sequential. However, this part take up to 10% of the total computing and more work could certainly nd a way to parallelize eciently this part.

Finally, it would be on interest to evaluate if the methodology used to nd where to split the evolutionary loop could be generalized and automated to other parallel applications.

RENATER and several Universities as well as other organizations (see https: //www.grid5000.fr).

- 6 Fig. 2 .

 62 Fig. 2. Density in function of the time to process mutants (in µs). The colors correspond to distinct experiments. Top (bottom) plots are extracted at generation 101,000 (resp 251,000). Time scale is cut at 350 µs as very few (0.01%) individuals last longer.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Scatter plot with duration of iterations vs the size of DNA after mutation. The dierent color represent dierent point in time of the execution.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Average proportion of time used for synchronization with the dierent implementations depending on mutation rate

Fig. 7 .

 7 Fig.7. Example of the execution of one generation with two scheduler. Blue rectangles correspond to mutants and red to non-mutants. At the top Dyn, where iteration executes at random order, and at the bottom LDNA, where the few step of evolution are performed with a static scheduler, then the mutant list is merged and sorted (blank part) and then only mutants are evaluated to nd their tness.

6

  Conclusion and Future Work

Table 1 .

 1 Performance of Aevol with several mutation rates using dynamic and guided schedulers. Environment : gcc8.3, libGOMP on 4 SkyLake Xeon Gold 6130.

		Mutation	SpeedUp	Eciency	Idle proportion
	# cores	rate	Dynamic Guided Dynamic Guided Dynamic Guided
		10 -4	11.2	10.9	70%	68.1%	4.1%	7.5%
	16	10 -5	11.2	10.1	70%	63.1%	5.0%	14.6%
		10 -6	10.2	8.6	63.8% 53.8% 11.2% 27.0%
		10 -4	20.3	19.5	63.4% 60.9%	9.2%	15.3%
	32	10 -5	20.0	17.0	62.5% 53.1% 11.1% 26.3%
		10 -6	16.5	13.1	51.6% 40.9% 21.4% 41.7%
		10 -4	34.4	32.8	53.8% 51.3% 18.2% 27.0%
	64	10 -5	33.1	26.2	51.7% 40.9% 22.1% 41.1%
		10 -6	23.9	18.2	37.3% 28.4% 36.6% 56.5%

http://www.aevol.fr/

Iterations only perform computation.

Acknowledgement

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientic interest group hosted by Inria and including CNRS,


Guillaume Deffuant
email: guillaume.deffuant@inrae.fr

Omid Roozmand

Sylvie Huet

Kamilla Khamzina

Armelle Nugier

Serge Guimond

Can biases in perceived attitudes explain anti-conformism?

come

Introduction

Climate change, energy and food requirements of a growing world population could lead societies to operate deep social changes. In general, social changes start from activist minorities which challenge the established norm and adopt anti-conformist behaviours. It is therefore important to better understand the emergence and the development of such behaviours. In this paper, we focus on a specific understanding of anti-conformism, which is the negative correlation between the intention and the perceived group norm. The purpose of the paper is to investigate the hypothesis that such anti-conformist intentions can be generated by a bias in the perception of attitudes.

We first attest the existence of anti-conformist intentions in two already published case studies [START_REF] Khamzina | Conformity or dissent ? The psychological implications of a mismatch between personal attitudes and collective norms[END_REF] . One is about Eastern European farmers' intention to convert to organic farming (N = 269) and the second about French agricultural college students intention to become an organic farmer (N = 220). Indeed, both data sets share the following features:

• Among participants whose personal attitude about organic farming is higher than the average, the intention to become an organic farmer is negatively correlated with the perceived group norm. In other words, when participants are in favour of organic farming more than the average, the less they think others are in favour of organic farming, the higher is their intention to become an organic farmer. Therefore, their intention tends to be reinforced if it goes against the perceived group norm, which can be seen as an anti-conformist intention.

• Among participants whose personal attitude about organic farming is lower than the average, on the contrary, the intention is positively correlated with the perceived group norm. In this case, the intention is, as more usual, rather conformist.

We make the hypothesis that some biases on the perception of attitudes could explain these observations. Roughly, the bias can increase the difference between the perception of the attitude of close others, which determines the intention, and the perception of the attitude of others in general, which determines the perceived group norm. In some cases, this additional difference could lead to negative correlation.

In order to investigate this hypothesis, we adopt a modelling approach. We design computational models of the perception biases, the intention and the perceived group norm. We simulate a population of virtual agents holding these perception biases that impact their intention and perceived group norm. We determine for which parameter values the model displays correlations between intention and the perceived group norm that are similar to the ones measured on the case studies. Such agent-based approaches are now rather common [START_REF] Mason | Situating social influence processes: Dynamic, multidimensional flows of influence within social networks[END_REF][START_REF] Smith | Agent-based modeling: A new approach for theory building in social psychology[END_REF][START_REF] Hedström | Causal mechanisms in the social sciences[END_REF] .

The model of biases on the perception of attitudes is inspired by the theory of Social Judgment [START_REF] Sherif | Social Judgment. Assimilation and contrast effects. Communication and attitude change[END_REF] . This theory assumes, in the light of robust observations, that people tend to perceive (or judge) close attitudes closer than they are, and far attitudes further than they are. Moreover, the limit between close and far depends on the extremity of the attitude ( 5 p. 139). People with extreme attitudes tend to perceive most of other attitudes as farther while people with moderate attitudes see most other attitudes as closer (there is actually an important relation with ego-involvement [START_REF] Sherif | Social Judgment. Assimilation and contrast effects. Communication and attitude change[END_REF][START_REF] Sherif | Attitude, ego-involvement, and change[END_REF][START_REF] Mc Ginnies | Initial attitude, source credibility, and involvement as factors in persuasion[END_REF] ).

The model of intention is based on the well empirically supported Theory of Reasoned Action (TRA) [START_REF] Fishbein | Predicting and changing behavior: The reasoned action approach[END_REF] , assuming that the intention is mainly determined by the attitude of the considered agents and the perceived attitudes of their important others. Here, the subjective norm, based on the perceived attitudes of close or important others, is distinguished from the perceived group norm, based on the perceived attitudes of other group members, beyond close others (e.g., other farmers). We choose the Theory of Reasoned Action (TRA) rather than the more complete theory of Planned Behaviour (TPB) [START_REF] Ajzen | The theory of planned behavior[END_REF] because in the case studies [START_REF] Khamzina | Conformity or dissent ? The psychological implications of a mismatch between personal attitudes and collective norms[END_REF] , the anti-conformist intentions are observed only at early stages of decision processes. Indeed, the first case study only includes answers from farmers who have not envisaged the conversion to organic farming yet and in the second case study, the participants are students in an agricultural college who are not yet farmers. Therefore, in both case studies, the perceived behavioural control, added to the TRA in the classical TPB [START_REF] Ajzen | The theory of planned behavior[END_REF] , is likely to play a negligible role in the determination of the intention. Indeed the perceived behavioural control measures the perceived easiness to perform the action in practice hence it supposes to envisage with some details the practical implications of the action. People who are at the beginning of the process of changing their behaviour are not likely to have in mind the many practicalities that could hamper the behavioural change. The situations that we consider can be seen as the first step towards a potential major change [START_REF] Sutherland | Triggering change: Towards a conceptualisation of major change processes in farm decision-making[END_REF] , or a transformational adaptation [START_REF] Moser | A framework to diagnose barriers to climate change adaptation[END_REF][START_REF] Gifford | The dragons of inaction: psychological barriers that limit climate change mitigation and adaptation[END_REF][START_REF] Kates | Transformational adaptation when incremental adaptations to climate change are insufficient[END_REF] .

We study the agent-based model by making a large number of simulations. Our method involves two main steps:

• We first adopt an Approximate Bayesian Computing (ABC) approach. We generate a large number of parameter values uniformly drawn from chosen intervals and we select the ones that lead to simulations reproducing the features of the data. The results show that only the parameter sets corresponding to a significant perception bias are selected. The average of the distribution of attitudes should also be significantly positive.

• We focus on a typical selected simulation, and we analyse how the perception biases modify differently the subjective and perceived group norms for individuals with more or less extreme attitudes. We observe that the perception biases create a slope change for both the subjective and the perceived group norm in the vicinity of the extreme opinions. This change takes place further from the extremities for the perceived group norm and this explains the emergence of the anti-conformist intention.

The paper is organised as follows: the next section presents the two case studies showing anti-conformist intentions. Section 3 describes the model. Section 4 explains the method adopted for studying the model. Section 5 reports the results. The final section discusses the results and draws future perspectives.

Two case studies showing anti-conformist intentions

Intention to convert to organic farming among Eastern European farmers

We only summarise the survey and focus on some specific features of the data analysis. All details can be found in [START_REF] Khamzina | Conformity or dissent ? The psychological implications of a mismatch between personal attitudes and collective norms[END_REF] . The survey took place in 2007 in Estonia, Hungary, Latvia, Lithuania, Poland, and Slovenia with respectively 187, 182, 170, 193, 192, and 157 farmer interviews. The questionnaires were designed in a large part in the framework of the TPB [START_REF] Ajzen | The theory of planned behavior[END_REF] , thus they provide the necessary information for applying the TRA, since TPB extends TRA. They include questions about personal attitude towards organic farming, subjective norm, perceived behavioural control and behavioral intention towards organic farming. They include additional questions about the perceived group norm.

The questions use 7-point Likert scale where 1 indicates extremely unlikely/disagree/bad and 7 indicates extremely likely/agree/good. We computed the personal attitude of a farmer as the average of the 4 questions about different aspects of the personal attitude and the attitude of important others (subjective norm) as the average of the 6 questions about different aspects of the subjective norm. The perceived attitude of other farmers at large (perceived group norm) was asked in a single question as well as the intention to convert to organic farming. We restrict our study to the farmers who are at the very beginning of the decision process and have not concretely envisaged to convert to organic farming yet. The size of the sample is 269.

Figure 1 shows the distribution of the personal attitudes, subjective norm and perceived group norm translated into a range between -1 and +1. Note that the average of the personal attitudes is significantly positive ( ā1 = 0.33) and the standard deviation is σ 1 = 0.33. The average of subjective and perceived group norms are lower than the one of the attitudes, with a significantly larger number with low values (2 or 3). The shape of the attitude distribution appears reasonably close to the one of a Gaussian.

Figure 2 shows linear regressions of the intention to convert to organic farming as a function of the perceived group norm for low and high attitude farmers. The low attitudes a are such that a < ā1 -0.2σ 1 and the high attitudes are such that a > ā1 + 0.2σ 1 . On the left the regression involves only farmers with a personal attitude lower than the average and on the right only farmers with a personal attitude higher than the average. The details of the regressions are provided by table 1.

Figure 3 shows the correlations between attitudes, subjective norm, perceived group norm and intention to convert to organic farming. They confirm the regressions: there is a significant positive correlation between intention and perceived group norm within farmers of low attitude while there is a significant negative correlation between the intention to convert and the perceived group norm within farmers of high attitude. Figure 3 also shows that the intention to convert has an even stronger correlation with the subjective norm, in conformity with the theory of reasoned action. These results suggest that the intention to convert increases with the perceived group norm for farmers with a low attitude while it decreases in the contrary for farmers with a high attitude. The latter case is more significant and probably more surprising. It indicates indeed a tendency which is antagonist to the one of the group, hence an anti-conformist intention.

Intention to become an organic farmer among French agricultural college students

Like previously, we only summarise the study, focusing on the main features that will be compared with the model. The sample includes 220 participants from agricultural colleges in Rhône-Alpes, France, surveyed in 2017. The study assesses personal attitudes towards organic farming using an 11 items scale with three reversed items (e.g., "Organic farming practices are desirable for the region's future"). It assesses perceived group norm about organic farming by transforming the personal attitudes questions into measures of the perception of others' attitudes by adding the phrases such as "most farmers believe that. . . " or "my friends believe that..." at the beginning of each item in place of "I believe". The items starting with "Most farmers" contribute to the perceived group norm while the ones starting with "My friends" contribute to the subjective norm.

Figure 4 represents the histograms of attitudes, subjective norm, and perceived group norm, on a scale between -1 and +1 (translated from the 5 item Likert scale). In the model, we consider more particularly the distribution of attitudes which has a mean of ā2 = 0.28 and standard deviation of σ 2 = 0.38. On average, the attitudes about organic farming are positive, like in the previous survey.

Figure 5 shows the regression of the intention as a function of perceived group norm for low (left) and high attitudes (right). The low attitudes are attitudes a such that a < ā2 -0.2σ 2 and the high attitudes are such that a > ā2 + 0.2σ 2 . For high attitudes, the regression coefficient is negative while it is positive for low attitudes. The negative coefficient for the high attitudes is more significant than the positive coefficient for low attitudes (see Table 2).

These features are confirmed by the correlation analysis presented on Figure 6 which shows the correlations between attitude, subjective norm, perceived group norm and intention for low and high attitude respondents. Indeed, a significant negative correlation between the intention and the perceived group norm can be noticed for high attitudes respondents, while this correlation is positive for low attitude respondents. This pattern replicates the observations made with Eastern European farmers. We can note a few other features, that are less important for this paper: There is a significant positive correlation between attitudes and intention as well as between subjective norm and intention for low attitude respondents. The correlation between the subjective norm and the intention is not significant for high attitudes.

The model

The model includes a population of virtual agents, each holding an attitude, drawn from a Gaussian distribution. Each agent is connected to a set of other agents, representing her acquaintances in the group at large among which a smaller set represents her close or important others. The subjective and perceived group norms are average of the perceived attitudes of respectively the acquaintances and the close others. The intention is the average of the attitude and the subjective norm. Hence, we can compute regressions and correlations of the intention with the perceived group norm.

Attitudes and biased perception of attitudes

The model includes n virtual agents and each agent i is then characterised by an attitude a i . In practice, we draw the attitudes a i at random from a Gaussian distribution of mean 0 < δ < 0.5 and of standard deviation σ . The scale of attitudes is continuous on the segment [-1, 1]. Therefore, attitude -1 is the most against the issue while 1 is the most in favour. Attitude 0 is indifferent. Only the values which fall within the segment of attitudes [-1, 1] are kept. Therefore, the average attitude ā of the population is generally a bit different from δ .

In accordance with the Social Judgement Theory, we introduce biases in the agents' perception of attitudes.

The attitude a j of agent j perceived by agent i is denoted p i (a j ) and it is ruled by threshold τ i , as follows:

• If the difference between a i and a j is lower than τ i then the perception p i (a j ) of a j by agent i is closer to a i than a j is;

• If the difference between a i and a j is on the contrary greater than τ i , then the perception p i (a j ) of a j by agent i is further from a i than a j is;

The threshold τ i depends on the extremity of attitude a i . It is assumed to increase linearly for a i between -1 and 0 and to decrease linearly for a i between 0 and 1. More precisely (β and τ M being parameters of the model), we have:

4/17
τ i = τ M (1 + β a i ), if a i < 0; τ i = τ M (1 -β a i ), if a i ≥ 0. (1)
Figure 7 represents how parameters β and τ M affect the value of the threshold τ i based on the given attitude. Parameter β defines the slope of the segments. Parameter τ M , the maximum threshold which corresponds to the neutral attitude 0.

Then, p i (a j ) the attitude of j perceived by i, is given by (ρ being a parameter):

p i (a j ) = a j + ρ(a i -a j ) if τ i > |a i -a j |, p i (a j ) = a j -ρ(a i -a j ) otherwise. (2)
To be compatible with the extreme ends of attitude's scale, p i (a j ) is blocked in the range [-1, 1]. Indeed, this equation ensures that, if

τ i -|a i -a j | > 0, then |p i (a j ) -a i | < |a j -a i | and if τ i -|a i -a j | < 0, then |p i (a j ) -a i | > |a j -a i |.
Figure 8 shows how one agent with a high attitude (attitude = 0.9, on the left), and a neutral attitude (attitude = 0, on the right) perceive (red triangles) the attitude of others (black squares). We observe on the left that the agent having an attitude 0.9 views the attitudes closer than its threshold as even closer, while the attitudes further than the threshold are perceived even further. On the right, the agent with an attitude 0 sees all other attitudes closer than they are.

Subjective norm, perceived group norm and intention

For each agent i we draw uniformly in the population a set R i g of agents that represents the agents in interaction with agent i and gives the agent an idea of the attitude of the whole group. The size s g of this set is assumed the same for all the agents. The perceived group norm N i g of agent i is modelled as the average of the attitudes in the set R i g as they are perceived by agent i:

N i g = 1 s g ∑ j∈R i g p i (a j ). (3)
A subset R i c of R i g that represents the important others (close to the considered agent) who are the base for the computation of the subjective norm. The set R i c is built by drawing at random s c agents j in the set R i g with a probability decreasing with the difference between a i and a j : The subjective norm is finally computed as the average of the attitudes of important others (in set R i c ) as perceived by agent i. It is denoted N i c :

P( j ∈ R i c ) = exp -α|a i -a j | 2 ; ( 4
) 5/17
N i c = 1
s c ∑ j∈R i c p i (a j ). (5)
The intention I i of agent i to act (e.g. intention to convert to organic farming) is approximated from the TRA as the sum of the agent's attitude and subjective norm:

I i = 1 2 (a i + N i c ). (6)

Method for studying the model

Parameter selection by Approximate Bayesian Computing (ABC)

Approximate Bayesian Computing (ABC) [START_REF] Beaumont | Approximate bayesian computation in evolution and ecology[END_REF][START_REF] Csilléry | Approximate bayesian computation (abc) in practice[END_REF][START_REF] Marin | Approximate bayesian computational methods[END_REF][START_REF] Lenormand | Adaptive approximate bayesian computation for complex models[END_REF] is a class of methods rooted in Bayesian statistics that is used to estimate the distribution of model parameter settings for which the model satisfies some criteria. Starting from a large number of parameter settings, each drawn uniformly in a chosen interval (prior distribution), we select the parameter settings for which the simulation shows the features identified in the case studies and this determines the approximation of the posterior distribution. More precisely, Figure 9 describes the items of the ABC process:

• 1) We have chosen to investigate parameter settings: p =(σ , δ , β , τ M , ρ, α) (table 3 recalls the meaning of each parameter symbol). Using the Latine Hypercube Sampling (LHS) package in R we generate N = 25, 000, 000 parameter 6/17

• 2) For each parameter setting p, the model is run and the results are stored in a csv file.

• 3) The regression coefficients c l (p) and c h (p) are computed.

• 4) The acceptance of a parameter setting p is based on the regression coefficients c l (p) and c h (p) of the intentions as a function of the perceived group norm for respectively the low and the high attitudes, derived from the simulation run with parameter set p. These coefficients are compared to the averages cl = 0.36225 and ch = -0.499 of these coefficients obtained from our two case studies (see tables 1 and2). The acceptance criterion involves the average of standard errors ēl = 0.15195 and ēh = 0.12438 of the regressions of intention by perceived group norm for low and high attitudes of the two case studies. More precisely, a parameter set p is accepted if:

|c l (p) -cl | < 2 ēl and (8) |c h (p) -ch | < 2 ēh . (9)
• 5 and 6) If the conditions 8 and 9 are satisfied, then p is accepted (stage 5), otherwise it is rejected (stage 6).

• 7) The simulation is repeated for N times.

The approximate posterior distribution provides the conditions on the parameters for which the features found in the case studies are reproduced by the simulations. This posterior distribution can be visualised by projecting it on 2D spaces defined by pairs of parameters.

Selecting a single parameter setting.

In the 6-dimensional parameter space (σ , δ , β , τ M , ρ, α), we define 10 4 = 10, 000 6-dimensional boxes as follows:

• For each parameter ω ∈ { σ , δ , β , τ M , ρ, α}, let s ω be the size of the box on the dimension defined by the parameter. It is the range of the prior distribution of this parameter divided by 10:

s ω = (ω h -ω l )/10, (10)
where ω h and ω l are respectively the maximum and minimum of the interval of the prior distribution for parameter ω; • Let δ 0 and σ 0 , be the average of the means and standard deviations of attitudes distributions in our two case studies:

δ 0 = 1 2 ( ā1 + ā2 ) and σ 0 = 1 2 (σ 1 + σ 2 )
. All the boxes are such that:

σ ∈ [σ 0 - s σ 2 , σ 0 + s σ 2 ], (11)
δ

∈ [δ 0 - s δ 2 , δ 0 + s δ 2 ]; (12)
• Then each box is defined by four integers k ω ∈ {1, .., 10}, for ω ∈ { β , τ M , ρ, α} and is such that :

ω ∈ [ω l + (k ω -1)s ω , ω l + k ω s ω ], for ω ∈ {β , τ M , ρ, α}. (13)
Among the 10 4 = 10, 000 boxes, we selected the ones which include a proportion of accepted parameter settings that is higher than 0.95. Then, among the selected boxes, we selected the one for which the parameter setting at the center of the box provides regression coefficients that are the closest to the average ones of the data.

Explaining the anti-conformist tendency on simulations with the selected parameter setting.

In order to analyse the correlations between the attitudes and the norms generated with the selected parameter setting, we repeat the computation of the norms with many different draws of the attitudes and sets of connected agents. More precisely, the procedure is the following:

• Draw a set of 1000 attitudes from the Gaussian distribution, corresponding to 1000 agents. Let (a 0 i ), i ∈ {1, 1000} be this set of attitudes;

• Repeat for j from 1 to 1000 ( j is the index of the replica):

-Draw at random from the Gaussian distribution a set of 1000 attitudes: (a j i ), i ∈ {1, 1000};

for i from 1 to 1000, for attitude (a 0 i ) we compute the perceived group N i j g norm and the subjective norm N i j c from the set of attitudes (a j i ).

8/17 This procedure allows us to reduce the variability of the norms for a given agent and their distributions look almost like curves. Hence we can easily identify parts of them which are almost linear and the sign of the corresponding slope. Thus we can identify more easily how the perceived group norm correlates with the attitudes and the subjective norm and therefore with the intention.

Results

Distribution of parameters selected by ABC. 948,091 parameter settings have been selected among the 25,000,000 tested in the ABC process. Figures 10 and11 show the distribution of these selected settings projected on the planes defined by 8 pairs of parameters which include δ or σ . Each panel of figures 10 and 11 shows a 2D map of 100 × 100 cells representing the proportion of accepted parameter settings in the cell. The color ranges from white to red as the proportion of accepted parameter sets increases. The white color indicates that no parameter settings located in the cell has been accepted. The red color thus corresponds the highest proportion of accepted simulations among all the cells of the considered 2D map. The legend indicates this maximum. The line shows the points for which the value of δ or σ is the average of the ones of our case studies (δ = δ 0 = 0.305 and σ = σ 0 = 0.355).

The figures suggest the following comments (table 3 recalls the definition of each parameter):

• Parameter δ should be larger than approximately 0.05 and parameter σ should be larger than approximately 0.25;

• Parameter β should be larger than approximately 0.3. This indicates that the perception bias should be significantly different at the extremes of the opinion range.

• The graph in the space δ , τ M does not provide any condition on τ M . However, τ M should increase with σ .

• For low values of both δ and α, and also low values of both σ and α, no parameter set is accepted. By increasing these two parameters, the number of accepted results increases. This indicates that the attitudes of the close others should be significantly correlated with the attitude of the considered agent.

• For β < 0.3 and σ < 0.25 no parameter set is accepted. By increasing these two parameters, the number of accepted results increases and then decreases for very high β and very high σ .

Selecting a single parameter setting.

The blue points on the lines represented on Figures 10 and11 are the projections of the middle of the four 4-dimensional boxes (among 10,0000) in space (β , τ M , α, ρ) for which the proportion of accepted sets is the highest. Box 1 in table 4. It includes 18 accepted parameter sets over 18 tested is the only one with 100% of accepted parameter sets. We also found three boxes that hold higher than 0.95 % of accepted parameter sets (see table 4).

These boxes belong to different regions of the parameter space. In order to select one of them, we pick the center of each box as a parameter setting representing this box and we make the average of coefficients of regression for low and high attitude of 1000 replicas using this parameter setting for each box. Table 5 shows the average of coefficients of regression for low and high attitude for 1000 replicas.

We observe that the centers of boxes 1 and 3 yield regression coefficients that are the closest to the average coefficients derived from the data sets (the average of coefficient for low attitude is 0.36225, and the average of coefficient of regression for 10/17 Analysing the model for the selected parameter values.

Figure 12 shows the results obtained for the selected parameter values (see table 6) when making the same analysis as the ones done on the case studies. The low attitudes a are such that a < δ -0.2 σ and the high attitudes such that a > δ + 0.2 σ ( δ and σ are respectively the average and standard deviation of attitudes). As expected, the regression coefficient of the intention by the perceived group norm is positive for low attitudes and negative for high attitudes and so are the correlation coefficients between intention and perceived group norm. The very high positive correlations between intention and both attitudes and subjective norm for both low and high attitudes were also expected because the intention is modelled as the average of the attitude and the subjective norm.

Moreover, the following observations are noticeable:

• For the low attitudes, there is a small positive correlation (0.18) between attitudes and perceived group norm and a stronger positive correlation between subjective norm and perceived group norm (0.51) ;

• For the high attitudes, there is a strong negative correlation (-0.80) between attitudes and perceived group norm and a weaker negative correlation between subjective norm and perceived group norm (-0.11).

These observations can be related to Figure 13 which shows the average over 1000 replicas of the whole population and averaging the perceived group norm and subjective norm over the 1000 populations ( Ni g and Ni c in the procedure described in ). Let us first comment the shape of the perceived group norm (red curve). Without perception bias, this curve would be flat at the value of the average attitude. Instead, because of the perception biases, it starts at its highest value for the lowest attitudes, decreases until a local minimum located just below 0 then increases until a local maximum located just above the average attitude and finally decreases until reaching a very its lowest value for the highest attitudes. Indeed, when an agent's attitude is very low, this agent tends to perceive most other attitudes as higher than they are, and hence her perceived group norm is higher than the actual average attitude. When her attitude increases, the proportion of others' attitudes that are perceived higher than they are decreases, hence the perceived group norm decreases. It decreases until reaching a point where most others' attitudes are seen closer than they are, and from this point, the perceived group norm increases with the attitudes. It increases until reaching a point close enough to the high extreme in which most others' attitudes are seen lower than they are, and this is more and more so when approaching the extreme of the attitude axis. In this last part, the perceived group norm decreases. Without perception bias, the subjective norm (green curve) should be close to a local average of the attitude distribution, because the close others tend to have attitudes which are close to the one of the considered agent. Hence it should be growing with the attitude. Instead, with the perception bias, like the perceived group norm, the curve initially decreases until a minimum, then increases until a maximum and finally decreases again. The local minimum is lower than the one of the PGN and reached for a lower value of attitude, while the maximum is higher and reached for a higher attitude. The effect of the bias is smaller on the subjective norm than on the PG norm because the attitudes taken into account for computing the subjective norm are closer on average to the considered agent's attitude.

These features of the curves can be related to the correlations shown on Figure 13:

• In the low attitudes (below the left dotted vertical line), the perceived group norm decreases and then increases, explaining a low correlation between attitudes and perceived group norm (0.18). Moreover, both norms first decrease and then increase, which explains a positive correlation (0.51);

• On the contrary in the high attitudes (above the right dotted vertical line), the perceived group norm is significantly decreasing, explaining a negative correlation (-0.80) with the attitudes. Moreover, the subjective norm first increases and then decreases, thus there is a low correlation between the norms (-0.11).

This analysis suggests that:

• the positive correlation between intention and perceived group norm within low attitudes is mainly driven by the positive correlation between perceived group norm and subjective norm;

• the negative correlation between intention and perceived group norm within high attitudes is mainly due to the negative correlation between perceived group norm and attitudes;

This analysis can be qualitatively summarized as follows. The bias on the perception of attitudes creates a border effect for both norms: in the vicinity of the extremes of the attitude range, the norms tend to decrease when the attitude increases. This border effect is weaker for the subjective norm, because the attitude of the close others is less likely to be very different from the considered agent's attitude. When the distribution of attitudes is not centred (say δ > 0), in the low attitudes, both norms decrease and then increase together for a significant segment of attitudes. Hence, they are positively correlated. This explains 15/17 the positive correlation between the perceived group norm and the intention for low attitudes. On the contrary, in the high attitudes, because its border effect is stronger, the perceived group norm is mostly decreasing and is thus negatively correlated with the attitudes. This explains the negative correlation between the perceived group norm and the intention. These qualitative explanations hold for the parameter settings determined by the 3 other boxes of table 4.

Discussion

For a large set of parameter values, the model reproduces the main features observed in the case studies, namely a positive correlation between perceived group norm and intention in the low attitudes and a negative correlation in the high attitudes. For the selected parameter setting, in the low attitudes, the model also displays a positive correlation between the perceived group norm and the subjective norm, in accordance with the data.

However, for the same setting, in the high attitudes, the model shows a negative correlation between attitudes and perceived group norm which is not observed in the data. Nevertheless, this discrepancy between the case studies and the model might not be statistically relevant because the attitudes have been cut into low and high values, and in each set the variability is thus significantly diminished.

Overall, the approach therefore suggests that the anti-conformist intentions observed in the case studies might be due to biases in the perception of attitudes. This explanation is very different from other possible explanations related to the feeling of some kind of moral superiority. The idea behind this alternative explanation is that people with a high attitude perceive themselves as more advanced than the rest of the group and this reinforces their intention to increase their superiority hence their intention to act against the group norm. It can be related to the willingness to increase the rewarding feeling of being a pioneer. Therefore, this explanation postulates that for these people, a low perceived group norm has some causal effect on reinforcing the anti-conformist intention. On the contrary, in the explanation based on the perception biases, the anti-conformist intention is an accidental correlation, without any causality.

This paper only establishes the possibility of the explanation based on perception biases. It does not give any evidence for privileging it over the other explanation. Moreover, it is important to underline the following limitations of our work:

• We did not compare the distributions of perceived and subjective norms with the ones of the case studies. This would require introducing noise into the model of attitude perception;

• The model assumes that the agents determine their perceived group norm only from direct interactions with other agents of the group. Yet indirect relations (gossip) and exposure to media can play an important role;

The relevance of the explanation of anti-conformist intention on perception biases can be further assessed by checking the model predictions on new case studies. For instance if the average of the distribution of attitudes is located close to the centre of the attitude scale (δ ≈ 0), then the features observed in the case studies presented in this paper should not be found (see figure 10). The model also predicts that if the average of attitudes is negative (δ < 0) and is sufficiently large, then the anti-conformist intention should be expected in the low attitudes.

Figure 3 .

 3 Figure 3. Correlation between personal attitude (Attitude), subjective norm (SN), intention to convert (Intention), and perceived group norm (PGN) for Eastern European farmers for low attitudes (on the left), high attitudes on the right.

Figure 4 .

 4 Figure 4. Distribution of attitudes, subjective norms, and perceived group norms of French Agricultural College students.

Figure 5 .

 5 Figure 5. Regression of intention to become organic farmer against perceived group norm for both low and high attitude of French Agricultural College students

Figure 6 .

 6 Figure 6. Correlations between personal attitude (Attitude), subjective norm (SN), intention to become organic farmer (Intention), and perceived group norm (PGN) for French Agricultural College students.

Figure 7 .

 7 Figure 7. Example of function determining the perception threshold τ i defined by parameters β = 0.2, 0.6, and 1, and τ M = 1, 1.5, and 2.

Figure 8 .

 8 Figure 8. Examples of how real attitude is perceived. Left: attitude of perceiving agent = 0.9. Right: attitude of perceiving agent = 0.

9 / 17 Figure 9 .

 9179 Figure 9. The schema of Approximate Bayesian Computing for accepting/rejecting parameter settings.

Figure 10 . 17 Figure 11 .

 101711 Figure 10. Results of ABC: Proportion of accepted simulations presented on 2D spaces where δ is on the horizontal axis and β , τ M , α or ρ are on the vertical axis.

13 / 17 Figure 12 . 17 Figure 13 .

 1317121713 Figure 12. Example of results the selected parameter setting. Top line: regressions of intention (y-axis) as a function of the perceived group norm (x-axis) for low attitudes (on the left), high attitudes (on the right); bottom line: correlations for low attitudes (on the left), high attitudes (on the right).

2/17 Figure 1. Distribution

  of attitudes, subjective norms, and perceived group norms of Eastern European farmers

		Estimate Std. Error t value	Pr(>|t|)
	(Intercept) Low attitudes	1.1559	0.5096	2.268	0.0255 *
	l1[, 4] Low attitudes	0.3243	0.1406	2.307	0.0232 *
	(Intercept) High attitudes 3.96441	0.43876	9.035 1.94e-15 ***
	l2[, 4] High attitudes	-0.28801	0.09776	-2.946	0.00381 **

Table 1 .

 1 Details of the regressions of intention by perceived group norm for farmers with attitudes lower than average (top lines) and higher than average (bottom lines).

3/17 Figure 2.

  Regression of intention to convert against perceived group norm for both low and high attitudes Eastern European farmers

		Estimate Std. Error t value	Pr(>|t|)
	(Intercept) Low attitudes	1.1342	0.4826	2.350	0.0208 *
	l1[, 4] Low attitudes	0.4002	0.1633	2.451	0.0161 *
	(Intercept) High attitudes	6.2702	0.4816	13.019 < 2e-16 ***
	l2[, 4] High attitudes	-0.7100	0.1510	-4.702 8.82e-06 ***

Table 2 .

 2 Details

of the regressions of intention by perceived group norm for students in French Agricultural College with attitudes lower than average (top lines) and higher than average (bottom lines).

Table 3

 3 breaks down the parameter definitions.

	Symbol	Definition
	n	Size of the population
	δ	Mean of attitude distribution
	σ	Standard deviation of attitude distribution
	s c s g α	Size of the set of close others R i c Size of the set of others representing group R i g Coefficient ruling probability to be in close agent set R i c
	β	Slope of the perception threshold function τ i
	τ M	Maximum perception threshold (for attitude equal 0)
	ρ	Coefficient ruling the modification made by the perceived attitude

Table 3 .

 3 Break-down of model parameters.

Table 4 .

 4 The boxes that hold more than 95% of accepted parameter settings.

	12/17

Table 5 .

 5 Average and standard deviation of coefficients of regression of 1000 replicas for low and high attitudes for different parameters that are the center of selected boxes. high attitude is -0.499005). We select the center of box 1 for further analysis. Table6shows these parameter values. Remember that the other parameter values are: n = 1000, s c = 5, s g = 30, δ = 0.305, σ = 0.355.

	(15)

Table 6 .

 6 Selected parameter values.

Acknowledgement

This work has been partly supported by the Agence Nationale de la Recherche (ANR) through the FuturICT2.0 project from the Flagera program (https://www.flagera.eu/).

Author contributions statement G.D. designed the model and the experimental protocol for studying the simulations from the selected parameter settings, O.R. implemented the model and the ABC method and conducted the simulation experiments, K.K. and S.G. designed the questionnaire of the second case study and K.K. participated in the data collection, S.H., K.K., A.N. and S.G. identified the anti-conformist intentions in the case studies, discussed the model and its results. All authors reviewed the manuscript.

Additional information

To include, access to R code ? (Omid).

The authors declare no competing interests.


F Lamiraux

J.-P Laumond

Smooth motion planning for car-like vehicles

I. Introduction

In the framework of motion planning for nonholonomic systems, the car-like vehicle has been the most investigated system. Numerous motion planners including obstacle avoidance capabilities are today available (e.g. 3], 4], 17], 15], 8], 21], 11], 24], 29]). All these approaches consider the car-like as a 3-dimensional system moving in the plane and subjected to constraints on the curvature (in addition to the nonholonomic constraint of rolling without slipping). The pioneering work by Dubins 7], and then by Reeds and Shepp 23], showed that the minimal length 1 paths for a car-like vehicle consist of a nite sequence of two elementary components: arcs of circle (with minimal turning radius) and straight line segments. From then, almost all of the proposed motion planners compute collision-free paths constituted by such sequences. As a result the paths are piecewise C 2 , i.e. they are C 2 along elementary components, but the curvature is discontinuous between two elementary components. To follow such paths, a real system has to stop at these discontinuity points in order to ensure the continuity of the linear and angular velocities.

To overcome this inconvenience several authors have proposed to smooth the sequences straight line-arc of circle by clothoids (e.g., 12], 9]). The paths are then C 2 between two cusp points. However, this approach raises another problem: clothoids do not have a closed form making the control of their shapes di cult and dangerous in the presence of obstacles. This smoothing technique usually a ects the completeness of the motion planner. The only exception is the work appearing in 24].

In this paper, we propose to revisit the problem by considering a car as a 4-dimensional system from a control point of view: the steering angle is a con guration variable. Such a system has been investigated from a control point of view (e.g., 30]) but without considering the ob-A shorter version of this paper appears in the 6th International Conference on Intelligent Autonomous Systems Florent Lamiraux and J.-P. Laumond are with LAAS-CNRS, Toulouse, France. E-mail: f orent|jplg@laas.fr 1 More precisely, the length here is the length of the path followed by the middle of the rear wheel axis. stacle avoidance problem.

After introducing the model of the car (Section II), we present the steering method which is derived from a method previously developed by the authors for a mobile robot pulling trailers (Section III). This approach guarantees the curvature of the path to be C 2 between cusp points. Then we show how to plug the steering method within two di erent nonholonomic motion planning schemes (Section IV). In the rst scheme, the algorithm computes a collisionfree holonomic path in R 2 S 1 (the nonholonomic constraints are ignored, only the obstacles of the environment are taken into account); then the path is approximated by a sequence of admissible paths computed with the steering method applied to the 4-dimensional control system. In the second case, the local method is plugged into PRM (Probabilistic Roadmap Planner): A graph is constructed by picking random free con gurations and by connecting them by collision-free paths returned by our local method. To ensure the completeness of these schemes, the steering method has to account for the small-time controllability of the system: to connect con gurations close to each other, the steering method has to produce paths that remain close to these con gurations 25].

The main contribution of this paper is not to provide a completely new method, but to combine existing techniques from an adequate model of the car and to propose a practical well-grounded algorithm for planning collisionfree paths such that the curvature is continuous between cusp points.

II. Controllability of a car and admissible paths

Control model. The modeling of vehicles according to their locomotion systems is well understood (see 6]). Let us consider the system represented in Figure 1. The distance between the reference point (x; y) and the middle point of the driving wheels is assumed to be 1. The orientation of the car is denoted by . The con guration space C = R 2 (S 1 ) 2 of this system is 4-dimensional. The two controls of a car are the velocity v of the driving wheels and the time derivative ! of the steering angle . The steering angle is constrained by mechanical bounds: j j max .

A con guration X = (x; y; ; ) is said to be admissible if j j < max . A car corresponds to the following control system:

0 B B @ _ x _ y _ _ 1 C C A = 0 B B @ cos cos cos sin sin 0 1 C C A v + 0 B B @ 0 0 0 1 1 C C A ! (1)
Applying the technique of the Lie bracket rank condition, such a system is proved to be small-time controllable at any point (see for instance 20]). This means that, starting from any con guration, for any time T , the domain reachable with bounded velocity (jvj < 1, j!j < 1) and in time less than T always contains a neighborhood of the starting con guration.

In a lot of path planning work, the steering angle is not a con guration variable. In this case, the model can be simpli ed as follows. By setting ṽ = v cos and ! = v sin we get the following 3-dimensional control system:

0 @ _ x _ y _ 1 A = 0 @ cos sin 0 1 A ṽ + 0 @ 0 0 1 1 A ! (2)
This system looks like the kinematic model of the so called unicycle. The main di erence lies in the admissible control domains. Here the constraints on ṽ and ! are no longer independent. By setting v max = p 2 and max = 4 we get: 0 j!j jṽj 1. The curvature of the path should be smaller than 1, whenever it is de ned. The various existing motion planners for cars usually consider this 3dimensional model.

In the next section, we build a steering method based on the combination of canonical paths. The idea is to combine two paths passing by two di erent con gurations to get a feasible path that goes from the rst to the second conguration. We de ne now what we call a canonical path associated to a con guration. Canonical paths, canonical curves Let us consider a suciently smooth path followed by the reference point. Simple computations show that the tangent to the path gives the orientation of the car, while the steering angle is related to the curvature2 of the path by = tan . These relations de ne a one-to-one mapping between the space of admissible con gurations and R 2 S 1 1; 1]. In other word, any con guration can be parameterized by a vector (x; y; ; ) where is the curvature de ned above. Now, given a con guration X = (x; y; ; ), there exists a unique feasible path passing by X and keeping constant. This canonical path, denoted by (X; s), is obtained by integrating system (1) with v = 1 and ! = 0 over the time interval 0; s]. The corresponding curve (X; s) followed by the reference point (x; y) is an arc of circle if 6 = 0 and a straight line if = 0. Let us notice that this curve is parameterized by arc-length s. (X; s) is called the canon-ical curve associated to X. By construction we get the following property:

Property 1: The canonical path of an admissible conguration veri es the curvature constraint.

III. A steering method

To any con guration X, the de nition above associates a path passing by this con guration. We are now going to show how to use these canonical curves to build a feasible path between two con gurations.

We de ne a smooth increasing function from 0; 1] into 0; 1] verifying: (0) = 0, (1) = 1, _ (0) = (0) = _ (1) = (1) = 0. Let X 1 and X 2 be the initial and goal con gurations respectively.

It can be easily veri ed that the curve P (t) = (1 (t)) (X 1 ; t) + (t) (X 2 ; t 1) has the same position, tangent, and curvature as (X 1 ; t) for t = 0 and as (X 2 ; t 1) for t = 1. Therefore, it corresponds to a feasible path X(t) in C going from X 1 to X 2 when t goes from 0 to 1. The congurations along X(t) are computed from the curve P (t), the orientation of its tangent, and its curvature using the relation = arctan . The key point here is that is continuous along X(t).

This construction de nes a steering method that allows the car to reach any con guration from any other one. However, this steering method is not suitable for integration in our collision free scheme described below since it does not account for small-time controllability as de ned now (see 25] for details).

De nition: A steering method Steer is said to account for small-time controllability if it satis es the following property: 8" > 0; 9 > 0; 8(X 1 ; X 2 ) 2 C 2 d(X 1 ; X 2 ) < ) Steer(X 1 ; X 2 ) B(X 1 ; ") where d is a distance in the con guration space C of the system and B(X 1 ; ) is the ball of radius centered on X 1 (using distance d), and Steer(X 1 ; X 2 ) is the path followed by the steering method between X 1 and X 2 .

To account for small-time controllability, it can be easily stated that a steering method has to generate cusp points.

In 14], we show how to build a steering method accounting for small-time controllability using the above convex combination of canonical curves. We brie y recall here the main ideas of this construction. Let X 1 = (x 1 ; y 1 ; 1 ; 1 ) and X 2 = (x 2 ; y 2 ; 2 ; 2 ) be initial and nal con gurations. We de ne M 2 as the orthogonal projection of (x 2 ; y 2 ) on (X 1 ; t). We de ne v 2 the parameter of this projection on (X 1 ; t): M 2 = (X 1 ; v 2 ). Then we slightly modify the above construction of P (t) as follows:

P (t) = (1 (t)) (X 1 ; v 2 t) + (t) (X 2 ; v 2 (t 1)):
The corresponding path in C, that we denote by Steer (X 1 ; X 2 )(t), still represents a feasible path going from X 1 to X 2 . Importantly, if X 2 is on the canonical path associated to X 1 , Steer (X 1 ; X 2 )(t) is exactly the canonical * Steer 00000 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 11111 path (X 1 ; t). The continuity of Steer w.r.t. X 1 and X 2 enables us to prove that an open set around the canonical path (X 1 ; t) (the shaded area in Figure 2) is reachable by Steer without escaping the ball of radius " centered on X 1 .

1 X X3 X1 X2 1 X 2 X ( , ) 2 B( X 1 X ,α) ,ε) B( 1 X ,t) γ( γ( ,t)
Using now the continuity of (X; t) w.r.t. X, we establish that if a con guration X 3 is close to X 1 , (X 3 ; t) intersects the open set we have just de ned close to X 1 and we can chose a con guration X 2 in this intersection. This process de nes another steering method Steer as follows:

1. if X 3 is in the open set reachable by Steer , then Steer(X 1 ; X 3 ) = Steer (X 1 ; X 3 ), 2. otherwise Steer(X 1 ; X 3 ) is composed of two sub-paths. The rst one goes from X 1 to X 2 following Steer (X 1 ; X 2 ) between X 1 and X 2 . The second one goes from X 2 to X 3 following (X 3 ; t). With this construction Steer can access a neighborhood of a con guration X 1 without escaping any given ball centered on X 1 (Figure 2). It accounts for small-time controllability. As a consequence, if X 1 and X 3 are admissible con gurations close enough, then 1 and 3 are close enough in ] max ; max to guarantee that all the con gurations (x; y; ; ) generated by Steer(X 1 ; X 3 ) are admissible, i.e., they verify 2] max ; max . Gathering this result with the curvature continuity result we get the following property:

Property 2: For two su ciently close admissible congurations X 1 and X 3 , all the con gurations of the path Steer(X 1 ; X 3 ) are admissible. The path followed by the reference point is C 2 between X 1 and X 2 and between X 2 and X 3 . Remark: The collision free path planning scheme we de ne later builds paths composed of sequences of sub-paths generated by Steer. The continuity of the curvature between two sub-paths ensures us that a real system can follow these paths without stopping between each sub-paths. The rst path planning scheme works for any small-time controllable system. Introduced in 17] it consists in approximating a collision-free (holonomic) path by a sequence of collision-free admissible ones. It only requires a steering method accounting for small-time controllability (De nition Section III).

A. Approximation of a holonomic path Geometric planner: The rst step is to nd a geometric path, that is a collision free path that does not take into account the nonholonomic constraints. The car is viewed as a polygon moving freely in translation and rotation in R 2 among obstacles. The con guration space of this system is then R 2 S 1 . Numerous techniques are available to address the motion planning problem in that case 16]. Among them we chose the \distributed representation approach" 2] that leads to resolution-complete algorithms (such algorithms are guaranteed to nd a solution when a solution exists at a given resolution when modeling the search space by a grid). This algorithm is based on the construction of a potential eld over the con guration space, the global minimumof which is the goal con guration. This potential eld is built from two potential elds in the plane applied to two control points of the robot. Then the algorithm consists of an alternating sequence of gradient descent and a procedure lling the potential wells. Figure 4 shows an example of a path computed using this method. Approximation step Let us denote by hol the geometric path computed in R 2 S 1 by the previous step. From now on, we consider hol as a path in C by setting = 0. The approximation step recursively decomposes hol as follows. A con guration X is chosen in the middle of hol . This con guration is connected to X start and X goal using Steer, generating two feasible sub-paths. Collision with obstacles and the curvature constraint j j < max are checked along these sub-paths. If one of these constraints is violated, the corresponding sub-path is discarded and a new subgoal is chosen on hol between the beginning and the end of the discarded sub-path.

Figure 4(right) shows the result of the approximation scheme performed on the holonomic path of Figure 4(left). All the computation are performed in a few seconds.

B. Probabilistic roadmap approach

We have plugged our local method in Move3D, a generic platform for path planning 27]. Move3D can solve path planning problems for any system as long as a geometric description of the system and a local steering method is provided. We have implemented the steering method dened in Section III within Move3D. Move3D plans path using the probabilistic roadmap approach 13]. Free congurations are randomly picked. A roadmap is built by connecting to each other con gurations between which the steering method returns a local path without collision. A path planning problem is solved once the initial and goal con gurations lie in the same connected component of the roadmap.

Figures 5 and6 show paths computed for a car by Move3D. The maximal steering angle max is 30 degrees in both cases.

C. Convergence and completeness

The convergence of the approximation step is guaranteed to nish in nite time as soon as the holonomic path belongs to an open domain of the collision-free con guration space and the steering method accounts for small-time controllability as de ned above. The completeness of the algorithm thus inherits from the completeness of the geometric planner: it is resolution complete.

The probabilistic roadmap approach is probabilistically complete (i.e. the probability of nding a path if one exists tends toward 1 when the searching time increases) if the steering method accounts for small-time controllability. Smoothing step: Both planning algorithm provide a sequence of elementary admissible paths computed by Steer. This sequence usually include useless maneuvers and detours. A smoothing step tries to connect pairs of con gurations randomly chosen on the path using the steering method to shorten the rst solution path. Remark on optimal paths The minimal length paths for the system 2 have been characterized by Reeds and Shepp 23]. This result is proven in the absence of obstacles. Adding obstacles give rise to a challenging problem: solutions exist via dynamic programming approaches 3], approximated approaches 26] or for special classes of obstacles 1], 5]. All these work do not consider any constraint on the continuity of the path curvature. Computing minimal length paths for the system 1 remains today an open problem even in the absence of obstacle 28]. Therefore the paths computed by the algorithm presented in this paper are not optimal. We just argue that they are satisfactory from a practical point of view.

V. Conclusion

A path for car-like robot is a nite sequence of curves linking cusp con gurations. Between two cusps the curves should be su ciently smooth to allow non zero velocity at any point. In other words, the curvature should be continuous on these curves. The main purpose of this paper is to propose an e cient steering method for a car-like vehicle that computes such piecewise smooth paths. Moreover the proposed steering method has been integrated within two motion planning schemes. In the approximation scheme, the global solution path of Figure 4 has been computed within a few seconds. In the probabilistic approaches (Figures 5 and 6) the solution paths have been computed within a few seconds after a pre-processing time of a few minutes.

The main idea underlying the method proposed in this paper is to consider the car as a four-dimensional system. In such a way the constraint on the steering angle is treated as an obstacle. The approach avoids numerical issues such as the one arising in previous methods based on clothoids.

Fig. 1 .

 1 Fig. 1. Model of a car and a canonical curve.

Fig. 2 .

 2 Fig. 2. Steer accounts for small-time controllability.

Fig. 3 .

 3 Fig. 3. Two paths generated by Steer. The rst one (left) without cusp is a convex combination of the canonical curves associated to each con guration. the second one (right) is composed of a convex combination between the rst con guration (bottom) and a cusp con guration, and of the canonical path associated to the second conguration (top).

Fig. 4 .

 4 Fig. 4. A rst geometric path and the feasible path generated by the approximation scheme with max = 60 deg

Fig. 5 .

 5 Fig.5. A path computed by Move3D. The environment is a Mayan city with a pyramid. The car has to make a U-turn in a constrained corridor. Initial con guration is shown on the right. Final con guration is the same with opposite direction. This problem necessarily requires a long detour.

Fig. 6 .

 6 Fig.6. A path computed for a car-like toy using Move3D.

This property derives from the notion of atness recently introduced in control theory 10].

Ackowledgment We are grateful to Elodie Sims for providing the picture of Figure 6. Elements of environments of Figures 5 (Mayan city) and 6 come from http://www.3dcafe.com.