Vincent Delos
email: v.delos@i2m.u-bordeaux1.fr

Denis Teissandier
email: d.teissandier@i2m.u-bordeaux1.fr

Minkowski sum of HV-polytopes in R n

Keywords: Computational Geometry, Convex Polytope, Minkowski Sum, Normal Fan, Polyhedrical Cone

Minkowski sums cover a wide range of applications in many different fields like algebra, morphing, robotics, mechanical CAD/CAM systems ... This paper deals with sums of polytopes in a n dimensional space provided that both H-representation and V-representation are available i.e. the polytopes are described by both their half-spaces and vertices. The first method uses the polytope normal fans and relies on the ability to intersect dual polyhedral cones. Then we introduce another way of considering Minkowski sums of polytopes based on the primal polyhedral cones attached to each vertex.

Introduction

In mechanical design, tolerancing analysis consists in simulating the geometric variations due to the manufacturing process. A common way to simulate the variations of an over-constrained mechanical system is to manipulate sets of constraints in R 6 , to limit the 6 degrees of freedom (3 translations and 3 rotations), see [START_REF] Homri | Tolerancing analysis by operations on polytopes[END_REF]. In order to compute the cumulative stack-up of variations we need to calculate the Minkowski sums [START_REF] Srinivasan | Role of Sweeps in Tolerancing Semantics[END_REF] and intersections of sets of contraints modelled by polytopes in R 6 . Two algorithms were developped in this direction in [START_REF] Teissandier | Algorithm to calculate the Minkowski sums of 3-polytopes based on normal fans[END_REF] and [START_REF] Wu | Improvements to algorithms for computing the Minkowski sum of 3-polytopes[END_REF] but only in R 3 . In [START_REF] Delos | Minkowski sum of polytopes defined by their vertices[END_REF] and [START_REF] Fukuda | From the zonotope construction to the Minkowski addition of convex polytopes[END_REF], Delos and Fukuda introduce other methods summing polytopes in R n but they only work with the polytopes V-description and in tolerancing analysis, the polytopes are first defined by half-spaces. We can take advantage of this important property in order to set up the following algorithm. Moreover, making use of the H-representation can speed up the algorithm and is a key element in computing intersections further on. And finally, as we are in small dimensions, computing the double description is not a problem as stated in [START_REF] Fukuda | From the zonotope construction to the Minkowski addition of convex polytopes[END_REF] we can find cases where: "the number of facets of the convex hull of a set of k points in Euclidean n-space can be of order O(k ⌊n/2⌋ ) even when n is considered fixed".

The goal of this paper is to describe two ways of computing Minkowski sums of polytopes, whether we choose to work in the primal or dual spaces. The dual space approach has come to an algorithm implemented and tested in C++ while the other one is still under investigation. We finally introduce some promising perspectives to reach the objective of having a stable algorithm in the field of tolerancing analysis.

Basic properties 2.1 Minkowski sums

Given two sets A and B, let C be the Minkowski sum of A and

B C = A + B = {c ∈ R n , ∃a ∈ A, ∃b ∈ B/c = a + b}.
(1)

Polytopes

A polytope is defined as the convex hull of a finite set of points, called the V-representation, or as the bounded intersection of a finite number of half-spaces, called the H-representation. The Minkowski-Weyl theorem states that both definitions are equivalent.

Normal fans

For each vertex v of a polytope, we define the set E of its edges oriented towards its neighbours. With E = {e 1 , ..., e l } we build a polyhedral cone C(v) named the primal cone of v:

C(v) = {u 1 e 1 + ... + u l e l , ∀u j ≥ 0}. (2)
We can note that a polytope can be written as the intersection of all the primal cones attached to its vertices. Let A be a R n -polytope and V A the list of its vertices such as card(V A ) = m:

A = m i=1 C(v i ). (3)
For each vertex v of a polytope, we define the set N of the outer normals of its corresponding facets. With N = {n 1 , ..., n k } we build a polyhedral cone C D (v) named the dual cone of v:

C D (v) = {t 1 n 1 + ... + t k n k , ∀t i ≥ 0}. ( 4
)
It is also the set of hyperplane outer normals which find their maximum on this specific vertex:

C D (v) = {y ∈ R n : v, y = sup x∈A x, y }. (5)
N (A) is defined as the set of all the dual cones of a given polytope, it forms a partition of the whole space R n which is called the normal fan of the polytope.

Dual algorithm

As stated in [START_REF] Weibel | Minkowski sums of polytopes[END_REF] by Weibel "The normal fan of polytopes contains all of their combinatorial organization. It is therefore enough to compute the normal fan of a Minkowski sum to have its combinatorial properties. We can then easily deduce the polytope itself by combining these informations with the summand polytopes. We know that the normal fan of a Minkowski sum is the common refinement of the normal fans of its summands." This is why we developped such an approach in a previous article named Algorithm to calculate the Minkowski sums of 3-polytopes based on normal fans in R n . To extend the results in R n we need some theoritical results.

Main properties

Ziegler and Gritzmann give the normal fan of the sum of two R n -polytopes in [START_REF] Ziegler | Lectures on Polytopes[END_REF] and [START_REF] Gritzmann | Minkowski addition of polytopes: computational complexity and applications to Grbner bases[END_REF]. Let A and B with their respective lists of vertices V A and V B :

N (A + B) = N (A) ∧ N (B). ( 6
)
where

N (A)∧N (B) = {C D (a i )∩C D (b j ) : C D (a i ) ∈ N (A) ∀a i ∈ V A , C D (b j ) ∈ N (B) ∀b j ∈ V B } is called the common refinement.
So it is clear that computing the sum of two polytopes can be performed by intersecting polyhedral cones. This is illustrated in Fig. 1.

In the following we will emphasize on how finding the Minkowski vertices i.e. the vertices of the two operands sum.

Minkowski vertices

Let c ∈ V C , from [START_REF] Fukuda | From the zonotope construction to the Minkowski addition of convex polytopes[END_REF] we know that the vertex c can only be the sum of a face from A and a face from B. For reasons of dimension, c is necessarily the sum of two vertices a ∈ V A and b ∈ V B . Let's characterize now the dual cone of c. Let A and B be R n -polytopes of full dimension n, V A and V B be their vertices lists. Let a ∈ V A , and b ∈ V B :

c = (a + b) ∈ V C ⇒ C D (c) = C D (a) ∩ C D (b). (7) Let u ∈ C D (a) ∩ C D (b)
c = (a + b) ∈ V C ⇔ dim(C D (a) ∩ C D (b)) = n. (8)
In [START_REF] Fukuda | Computing all faces of the Minkowski sum of V-Polytopes[END_REF], Fukuda and Weibel indicate that "Faces of a polytope and their normal cones have dual properties. In particular, if F is a i-dimensional face of A, then the normal cone

C D (F ) is a (n -i)-dimensional cone of R n ." So ∃a ∈ V A , ∃b ∈ V B /c = (a + b) ∈ V C ⇒ dim(C D (a) ∩ C D (b)) = n as c is a 0-face. Reciprocally if dim(C D (a) ∩ C D (b)) = n then ∃u ∈ Int(C D (a)) ∩ Int(C D (b)) such as ∀x ∈ A, u, a > u, x and ∀y ∈ B, u, b > u, y . So u, a + u, b = u, c > u, x + y , ∀(x + y) ∈ C. Hence dim(C D (a) ∩ C D (b)) = n ⇒ c ∈ V C .
Following the same idea we can find the facets of the polytope C from N (C) edges. We now have all the tools to build Minkowski vertices and facets.

A first dual algorithm

Complexity and implementation

To perform such an operation, in [START_REF] Fukuda | Double Description Method Revisited[END_REF] Fukuda gives interesting insights and efficient-to-use strategies de-

Algorithm 1 Calculate C = A + B with A and B, two R n -polytopes of full dimension n Require: List of dual cones of A {C D (a i ), a i ∈ V A } Require: List of dual cones of B {C D (b j ), b j ∈ V B } for all a i ∈ V A and b j ∈ V B do Compute C D (a i ) ∩ C D (b j ) if dim(C D (a i ) ∩ C D (b j )) = n then (a i + b j ) ∈ V C Get the half-spaces passing through (a i + b j ) from C D (a i ) ∩ C D (b j ) edges end if end for
spite the fact, as the author says, "that we can hardly state any interesting theorems on its time and space complexities". The underlying physical problem we designed this algorithm for, is in low dimension so obtaining the polytopes double description is not a problem. In tolerancing analysis, it can even be done in an analytical way but beware that the number of vertices and facets can be exponential according to the dimension of the space we work in. As a example a tetraedon in R n has only (n+1) vertices and (n+1) facets but a cube has 2n facets and 2 n vertices. In [START_REF] Chazelle | An optimal convex hull algorithm in any fixed dimension[END_REF] one can find an optimum algorithm, when n is constant, to compute convex hulls that runs in time O(k ⌈n/2⌉ ) for n ≥ 4, k being the number of vertices. Such an upper bound cannot be reduced as it is of the order of the larger output. So in high dimensions the kind of polytopes you handle can have a very strong impact on the performances of the Minkowski sum algorithm. In [START_REF] Avis | How good are convex hull algorithms?[END_REF] we can find a good introduction on families of polytopes and the way they behave in algorithmic contexts.

This algorithm has been coded in C++ and is available under the Gnu General Public Licence v3.0 at http://i2m.u-bordeaux.fr/politopix. It has been tested and is now fully operational in R 6 in the frame of tolerance analysis in mechanical engineering, as well as it is in any dimension given the limitations we previously described.

An optimized dual algorithm

The basic idea behind this algorithm is quite simple. As soon as we get C D (a i ) and C D (b j ) such as dim(C D (a i )∩C D (b j )) = n, we do not pick dual cones from A in a random way but we rather select the list of C D (a i ) neighbours to intersect them with C D (b j ). While we find intersections of dimension n, we keep on picking up the neighbours of the neighbours and 4 Minkowski sum of polytopes with primal cones

We will now consider the primal cones of the polytopes we handle that is to say, for each vertex a ∈ V A , the cones defined by the intersection of the halfspaces { H+ u (a)} attached to this current vertex. In an equivalent manner, we can say that, given a ∈ V A , such cones can be generated by all the edges attached to a and pointing towards its neighbour vertices {a i }. Let's write V A (a) the set of the vertices of V A adjacent to a, with

α i ∈ R + , a i ∈ V A (a) C(a) = a + i α i (a i -a) = u H+ u (a). (11)

Main properties

Let C 1 and C 2 be two cones attached to the origin:

C 1 + C 2 = Conv(C 1 , C 2 ). ( 12
) Let x ∈ C 1 + C 2 then ∃y ∈ C 1 , ∃z ∈ C 2 such as x = y + z = 1 2 2y + 1 2 2z. Yet 2y ∈ C 1 and 2z ∈ C 2 which means that any point in C 1 +C 2 can be written as a point included in the convex hull of C 1 and C 2 hence C 1 + C 2 ⊂ Conv(C 1 , C 2 ). Let x ∈ Conv(C 1 , C 2 ) then ∃y ∈ C 1 , ∃z ∈ C 2 and θ ∈ [0, 1] such as x = θy + (1 -θ)z. Yet θ ≥ 0 so θy ∈ C 1 , 1 -θ ≥ 0 hence (1 -θ)z ∈ C 2
which means that x can be written as the sum of two elements from A and B so

Conv(C 1 , C 2 ) ⊂ C 1 + C 2 .
It is easy to transpose this property to the case of two cones attached to the vertices a and b in the polytopes A and B provided that we translate them first in a + b and hereafter compute the convex hull:

C(a) + C(b) = Conv b + C(a), a + C(b) . (13) If c = a + b is a Minkowski vertex of C = A + B then: C(c) = Conv b + C(a), a + C(b) . (14)
From [START_REF] Fukuda | From the zonotope construction to the Minkowski addition of convex polytopes[END_REF] This property is fundamental in the sense that it can make the connection between a polyhedra intersection problem on one side, and a polyhedra convex hull computation on the other. In the context of the sums of polytopes we're aware that if c = a + b is a Minkowski vertex of C = A + B then computing the convex hull of the two primal cones C(a) and C(b) is equivalent to computing the intersection between their corresponding duals C D (a) and C D (b), see Fig. 2. As a consequence we can compute C(c) ∀c ∈ V C -which means we can find all facets of C -with data coming only from the primal space. Given that a polytope is entirely determined by its vertices or facets we can write the following property for A and B two R n -polytopes with respectively k and l vertices. We can generalize this property to all the sums of vertices as it is easy to proove that whatever a i ∈ V A

Conclusion

We have developped and implemented a dual algorithm based on the intersection of dual cones used in the field of tolerance analysis where it behaves very well in terms of robustness and computation time. However the fact that we handle the double description to sum polytopes could possibly be a limitation if one needs to work in high dimensions. In the second part, we introduced new properties to remain in the primal space and proposed another way to perform the operation. Now we plan to work on a parallel version of the first as well as improving the theoritical background of the second.

Figure 1 :

 1 Figure 1: Sums of two polytopes step by step: a) polygons, b) normal fans, c) common refinement, d) sum.

  then u, a = sup x∈A u, x and u, b = sup y∈B u, y . So u, a + b = sup x∈A,y∈B u, x + y which means that u, c = sup z∈C u, z i.e. u ∈ C D (c). On the other side let u ∈ C D (c), by definition u, c = sup z∈C u, z . If we decompose c in a sum of vertices a and b we get u, a + u, b = sup x∈A u, x + sup y∈B u, y , but we know that in general u, a ≤ sup x∈A u, x and u, b ≤ sup y∈B u, y so for compatibility reasons with the formula of decomposition of c, the inequalities must be equalities. It gives u, a = sup x∈A u, x and u, b = sup y∈B u, y which means u ∈ C D (a) ∩ C D (b). Now we have to ask ourselves what are the conditions to get a Minkowski vertex when we compute the intersection C D (a) ∩ C D (b)?

=

  if c and c ′ are two adjacent vertices in C with their given decomposition in elements of A and B, c = a + b et c ′ = a ′ + b ′ then a et a ′ are either equal or adjacent (respectively b and b ′ ). We deduce that the list of edges defining C(c) is a sublist of L(C(a), C(b)), defined as the list of edges of both C(a) and C(b) translated in c. So C(c) ⊂ Conv(b + C(a), a + C(b)) because Conv(b + C(a), a + C(b)) is entirely defined by L(C(a), C(b)). For the reciprocal we use the dual, we know that C D (c) = C D (a) ∩ C D (b) so C D (c) ⊂ C D (a) C D (c) ⊂ C D (b). These relations are reversed in the primal space: b + C(a) ⊂ C(c) a + C(b) ⊂ C(c). Hence Conv(b + C(a), a + C(b)) ⊂ C(c) because C(c) is convex. Now we can give the property linking primal and dual cones respectively attached to the vertices a i ∈ V A and b j ∈ V B when their sum provide a Minkowski vertex: c ∈ V C ⇒ C D (a) ∩ C D (b) D Conv b + C(a), a + C(b) . (15) The proof is quite straightforward, as c is a Minkowski vertex then C D (c) = C D (a) ∩ C D (b) and the dual of the dual is the primal so (C D (c)) D = C(c) = Conv(b + C(a), a + C(b)).

  Let's note K the set of indices that provide a Minkowski vertex in C = A + B i.e. (i, j) ∈ K A+B ⇔ (a i + b j ) ∈ V C .

so on.

Let's assume that the two dual cones C D (a i ) and C D (b j ) intersects with each other such as, at least one half-space hyperplane H of C D (a i ) separates C D (b j ). Then it is obvious that the neighbour dual cone C D (a k ) that shares H with C D (a i ) has also a non empty intersection with C D (b j ). We can take advantage of this neighbourdhood property to speed up the algorithm.

So we introduce the notion of polyhedral cap. Let A, B and C = A+B be R n -polytopes and V A , V B , V C their respective lists of vertices. For a given vertex a ∈ V A we want to find the list of all the vertices of B that will give a Minkowski vertex in C. We define the polyhedral cap of the vertex a i in the polytope B this way

We want to show that ∀i,

which means that they do not intersect with C D (a i ) or only with its frontier. Given that l j=1 C D (b j ) = R n it must only be the last dual cone in N (B) that intersects with C D (a i ) interior. As a consequence dim(C D (a i )∩ C D (b l )) = n so a i + b l ∈ V C . In all the cases we have at least one vertex in B that verifies this property so

We build the list L of dual cones in N (B) whose intersection is not empty with the segment [u 1 , u 2 ] and that verify the following property: once we leave one of the bounding half-spaces of the current cone C D (b j ), we add to L its neighbour cone that shares with C D (b j ) the frontier of this current half-space. We can note that once we leave a cone, we will never process it again, as we remain on the segment [u 1 , u 2 ] we can never re-enter a bounding half-space we previously left. So L is a finite ordered list. We can

) it is easy to build a point still inside C D (a) that will also be in the interior of C D (b j ), we only have to shift away from [u 1 , u 2 ] by a very small quantity. In all the cases (a + b j ) ∈ V C , moreover two consecutive dual cones in L are connected, so are their corresponding vertices in B. So L is a list having for first and last elements b 1 and b 2 connected through neighbour vertices

A primal algorithm

With the property 14, it is quite easy to set up an algorithm computing the polytope C = A + B.

Starting from a first Minkowski vertex c 1 = a 1 + b 1 we just need to compute its edges making sure they belong to the convex hull of the cone C(c 1 ). Following such edges will leed to c 1 neighbours where we will compute their corresponding convex hulls. At this step it is important to note that, to identify Minkowski vertices, if

Complexity

We have reduced our problem to a convex hull algorithm. However as stated in [START_REF] Fukuda | Frequently Asked Questions in Polyhedral Computation[END_REF] "we are still very far from knowing the best ways to compute the convex hull for general dimensions" and the author adds "in the general case, there is no known polynomial algorithm". Despite the current state-of-the-art we believe we do not have only a theoritical achievement with property 17. The reason is due to the fact that it is not just about computing the convex hull of a set of edges coming from cones C 1 and C 2 but rather computing the convex hull of two sets of edges, each one of them being already convex. As building a convex set from two convex sets is easier, we plan to explore this track in the future.


Stéphane Caro Corousso

INTRODUCTION

Currently, serial and parallel manipulators have become more and more popular for a variety of technological processes, including high-speed precision machining [START_REF] Brogardh | Present and future robot control development -an industrial perspective[END_REF] [START_REF] Chanal | A study of the impact of machine tool structure on machining processes[END_REF]. This growing attention is inspired by their essential advantages over serial manipulators, which have already reached the dynamic performance limits. In contrast, parallel manipulators are claimed to offer better accuracy, lower mass/inertia properties, and higher structural rigidity (i.e. stiffness-to-mass ratio) [START_REF] Merlet | Parallel Robots[END_REF].

These features are induced by their specific kinematic structure, which resists to the error accumulation in kinematic chains and allows convenient actuators location close to the manipulator base. This makes them attractive for innovative robotic systems, but practical utilization of the potential benefits requires development of efficient stiffness analysis techniques, which satisfy the computational speed and accuracy requirements of relevant design procedures.

Generally, the stiffness analysis evaluates the effect of the applied external torques and forces on the compliant displacements of the end-effector. Numerically, this property is defined through the "stiffness matrix", which gives the relation between the translational/rotational displacement and the static forces/torques causing this transition [START_REF] Koseki | Kinematic Analysis of Translational 3-DOF Micro Parallel Mechanism Using Matrix Method[END_REF]. Similar to other manipulator properties (kinematical, for instance), the stiffness essentially depends on the force/torque direction and on the manipulator configuration [START_REF] Alici | Enhanced stiffness modeling, identification and characterization for robot manipulators[END_REF].

Several approaches exist for the computation of the stiffness matrix, such as the Finite Element Analysis (FEA), the matrix structural analysis (MSA), and the virtual joint method (VJM). Each of methods has their own assumptions and in general approximate/linearized the stiffness model with adequate accuracy for the specific problem. Let us consider the recent modification of the VJM proposed by the authors [START_REF] Pashkevich | Stiffness analysis of overconstrained parallel manipulators[END_REF]. It allows extending it to the over-constrained manipulators and applying it at any workspace point, including the singular ones. The method is based on a multidimensional lumped-parameter model that replaces the link flexibility by localized 6-dof virtual springs that describe both the linear/rotational deflections and the coupling between them. The spring stiffness parameters are evaluated using FEA modelling to take into account real shape of the manipulator components. This gives almost the same accuracy as FEA but with essentially lower computational effort because it eliminates re-meshing through the workspace.

In contrast to previous works, the novelty of this report appears in the computation of the stiffness matrix for the loaded mode in the neighborhood of static equilibrium with true dimensions links. This report focuses on the performance evaluation of the milling process for the composite materials via enhancing the precise stiffness model for the compliance errors estimation. VJM is used for the stiffness modeling. It incorporates accurate stiffness properties of links via improved FEA-based stiffness calculation algorithm. This leads to adequate estimation of deflections and allows improving accuracy of manufacturing via accurate planning of the technological process. The main problem to be solved in this report is the accuracy evaluation during the manufacturing step for specific parallel manipulators and technological process. Position accuracy and performances characteristics for the industrial manipulators depend on the technological process, kinetostatic and geometry properties of both manipulator and workpiece. Therefore specializing of the manipulator for the current manufacturing process with respect to the required performances properties allows increasing the position accuracy of the tool.

Mechanical stiffness is one of the most important properties which are influence on the position accuracy of low mass parallel mechanisms. As it is mentioned in [START_REF] Pashkevich | Enhanced stiffness modeling of serial manipulators with passive joints[END_REF] Cartesian stiffness is a nonlinear function of the external loading and depends on the configuration of the manipulator and, as result, of the position of end effector in the workspace [START_REF] Pashkevich | Stiffness analysis of multichain parallel robotic systems with loading[END_REF]. Cartesian stiffness both depends on the stiffness of the links and stiffness model accuracy.

So the aim of this report is to specialize a parallel manipulator for the milling of products made of composite material with known geometric sizes. The idea is to improve the accuracy for the high-speed milling via mass reduction and improving of the stiffness model. • the measures based on geometric, kinematic and kinetostatic properties; these measures are based on simple models that evaluate the geometric, kinematic and kinetostatic properties of a mechanism. Their specificity is that they only use the primary geometric parameters of the mechanism, i.e., the size of the base, the length of links, etc.

• the measures based on dynamic, elastostatic and elastodynamic properties; these measures mostly use more complicated models. Their specificity is that they not only use the primary geometric parameters of the mechanism, but also the secondary geometric parameters, as for example, the cross-section of links.

Let us now describe them.

Geometric, kinematic and kinetostatic performances

The most commonly used geometric, kinematic and kinetostatic performances are:

• the velocity transmission factors;

For appreciating the speed capability of a manipulator, several kinematic performance indices are defined using the Jacobian matrix J (see [START_REF] Merlet | Jacobian, manipulability, condition number, and accuracy of parallel robots[END_REF]), such as the condition number, the largest/smallest singular value (also called the maximal/minimal transmission factor and denoted as max , respectively -Figure 1a), the dexterity, the manipulability, etc. However, as mentioned by Merlet in [START_REF] Merlet | Jacobian, manipulability, condition number, and accuracy of parallel robots[END_REF], the previously cited indices does not take into account the 'technological reality' of the mechanism, as they are based on the use of the Euclidian norm of the input velocity vector are the actual and maximal velocities for the actuator i (i = 1 to n). Thus, it is necessary to redefine the transmission factors.

Two types of transmission factors may be used: (i) the velocity transmission factors along all directions of the workspace; in such a case, the unit square is mapped into a parallelepiped (Figure 1b) and (ii) the velocity transmission along some particular directions of the workspace; in such a case, the unit square is mapped into a hexagon (Figure 1c) [START_REF] Briot | Optimal Technology-Oriented Design of Parallel Robots for High-Speed Machining Applications[END_REF]. • the accuracy transmission factors;

The accuracy of a mechanism may be due to different factors. However, as pointed out by Merlet [START_REF] Merlet | Computing the worst case accuracy of a PKM over a workspace or a trajectory[END_REF], activejoint errors are the most significant source of errors in a properly designed, manufactured, and calibrated parallel robot. The classical approach consists in considering the first order approximation that maps the input error to the output error:

Φ J p δ δ = (1)
Projet COROUSSO Livrable n°1.

COROUSSO

where δΦ represents the vector of the active-joint errors, δp the vector of end-effector errors. This method will give only an approximation of the end-effector maximum error, but at an optimization stage, this model may be sufficient.

It is possible to show that, due the use of the expression (1) as the accuracy model, the accuracy transmission factors are similar to the velocity transmission factors. More information about the computation of these transmission factors is proposed in [START_REF] Briot | Optimal Technology-Oriented Design of Parallel Robots for High-Speed Machining Applications[END_REF].

• the force transmission factors;

For 3-DOF translational parallel manipulators, the input efforts τ are related to the forces f applied on the platform by the following relation:

τ J f T - = (2)
Looking at expression ( 2), it appears that the relationship for the accuracy is similar to the relationship for the velocity, but J -T is used instead to J. Moreover, it is also clear that the effort τ i of one actuator is comprised between -τ max and +τ max , τ max being the maximal effort admissible by the actuated pair. So, the force transmission factors may be computed in the same manner as the velocity transmission factors. The maximal and minimal force and moment transmission factors will be denoted as min f k and max f k respectively. To have more information about the computation of these transmission factors, the reader is proposed to refer to [START_REF] Briot | Optimal Technology-Oriented Design of Parallel Robots for High-Speed Machining Applications[END_REF].

• the size of the workspace;

Using the set of geometric parameters, the workspace W may be generated using the kinematic equations and the (passive and active) joint limits [START_REF] Merlet | Parallel Robots[END_REF]. Since, for the considered application, the desired regular workspace is a parallelepiped W 0 of size {a 0 × b 0 × c 0 }, the relevant measure may be defined by the largest similar object

W abc = {µa 0 × µb 0 × µc 0 } inscribed in W, i.e. { } W W T T W T W 0 T 0 ⊂ = = ) ( max arg ) , ( ); ( , μ μ μ μ μ abc (3)
where µ, T are respectively the scalar scaling factor and the coordinate transformation operator in the Cartesian space. An algorithm that is able to compute the size largest parallelepiped inside a given workspace is presented in [START_REF] Briot | Optimal Technology-Oriented Design of Parallel Robots for High-Speed Machining Applications[END_REF] Let us now introduce the dynamic, elastostatic and elastodynamic performances.

Dynamic, elastostatic and elastodynamic performance

The most commonly used dynamic, elastostatic and elastodynamic performances are:

• the total mass of the robot; This is probably the simplest performance measure. The masses of the different elements of a robot have a direct influence on its dynamic behaviour. For one given structure with fixed value of links length, the robot that will have the smallest mass will be the one with the smallest input efforts, and as a result, the highest acceleration capacity.

• the input efforts;

The input efforts, denoted as τ, depend on the mass and axial moment of inertia of links, such as friction in joints and position, velocity and acceleration of the robot. There expression is given by:

f J q G q q q C q q M τ T + + + = ) ( ) , ( ) (
where M is the mass matrix, C the matrix of the Coriolis, centrifugal and viscous friction effects, G is the matrix of the gravity and Coulomb friction effects. q, q & and q & & represent the vectors of the positions, velocities and accelerations of the actuators. f is an external force applied on the platform. Generally, it is considered that, given a desired trajectory, the robot that has the lowest input efforts along the trajectory has the best performance.

• the maximal deformations;

For parallel manipulators, elasticity is an essential performance measure since it is directly related to the positioning accuracy and the payload capability. Mathematically, this benchmark is defined by the stiffness matrix K, which describes the relation between the linear/angular displacements t of the end-effector and the external forces/torques f applied on the tool:

t K f δ = (5)
It is obvious that elasticity is highly dependent upon geometry, materials and link shapes that are completely defined with the CAD model. The stiffness matrix may be computed using three methods: the finite element analysis (FEA) [START_REF] El-Khasawneh | Computation of Stiffness and Stiffness Bounds for Parallel Link Manipulators[END_REF][START_REF] Bouzgarrou | Rigidity Analysis of T3R1 Parallel Robot Uncoupled Kinematics[END_REF], the matrix structural analysis (SMA) [START_REF] Deblaise | Systematic Analytical Method for PKM Stiffness Matrix Calculation[END_REF][START_REF] Ghali | Structural Analysis: A Unified Classical and Matrix Approach[END_REF] and the virtual joint method (VJM) [START_REF] Pashkevich | Stiffness analysis of overconstrained parallel manipulators[END_REF][START_REF] Gosselin | Stiffness Analysis of Parallel Mechanisms Using a Lumped Model[END_REF][START_REF] Majou | Parametric Stiffness Analysis of the Orthoglide[END_REF].

Whatever will be the way to compute the deformations of the robot, the mechanism that will have the best elastostatic performances will be the one that will have the smallest deformations under a given force, along a specific trajectory or in the totality (or some portions) of the workspace.

External forces are caused the coupling of the mashing tool and mashing piece. But previous stiffness models calculate stiffness matrix in the neighborhood of initial point and operate with links approximations. Such

Problem of stiffness modeling

To evaluate the manipulator stiffness, let us apply the VJM method that assumes that the traditional rigid model is extended by adding virtual joints, which describe stiffness of the actuator and links. Thus, the endeffector position for each chain of the manipulator can be described as

( , ) = t g q θ (6)
where (...) g is the geometry function which depends on the passive q and virtual joint θ coordinates, the vectors

( , , ..., ) T n q q q = q includes all passive joint coordinates, the vector This expression includes both traditional geometric variables (passive and active joint coordinates) and stiffness variables (virtual joint coordinates).

To evaluate the manipulator ability to respond to external forces and torques, it is necessary to introduce additional equations that define the virtual joint reactions to the corresponding spring deformations. For analytical convenience, corresponding expressions may be collected in a single matrix equation

= ⋅ θ θ τ K θ (7)
where ( ) For the compliant link, the matrix K can be computed using the FEA-based techniques, which usually produce rather accurate result. Using the FEA, the stiffness matrix K (or its inverse k) is evaluated from several numerical experiments, each of which produces the vectors of linear and angular deflections (t, ϕ) corresponding to the applied force and torque (F, M). Then, the desired matrix is computed from the linear system

,1 ,2 , , , ...
1 1 1 1 ... ... ... ... m m m m + ⎡ ⎤ ⎡ ⎤ = ⋅ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ F F t t k M M φ φ (8)
where [ ] + is pseudoinverse of the rectangle matrix, m is the number of experiments ( ) and the matrix pseudoinverse is replaced by the inverse in the case of . It is obvious that this case with special arrangement of the forces and torques is numerically attractive (for more detail see [START_REF] Pashkevich | Accuracy Improvement for Stiffness Modeling of Parallel Manipulators[END_REF]).

In order to increase accuracy it is worth to improve the deflection estimation technique. It is proposed to evaluate (t, ϕ) from the displacement field describing transitions of rather large number of nodes located in the neighborhood of reference point (RP). where the first component define the node initial location (before applying the force/torque), refers to the node displacement due to the applied force/torque, and n is the number of considered nodes. Then, assuming that all the nodes are close enough to the reference point, this set can be approximated by a "rigid transformation"

, 1,2,..., i n = (9)
that includes as the parameters the linear displacement t and the orthogonal 3×3 matrix R that depends on the rotational displacement ϕ. Then, the problem of the deflection estimation can be presented as the best fit of the considered vector field by equation ( 4) with respect to six scalar variables incorporated in t, R.

In general case, the desired stiffness model is defined by a non-liner relation

( ) = F ξ Δt (10)
that describes resistance of a mechanism to deformations Δt caused by an external force/torque F [START_REF] Brogardh | Present and future robot control development -an industrial perspective[END_REF]. It should be noted that the mapping Δt → F is strictly mathematically defined and physically tractable in all cases, including under-constrained kinematics and singular configurations of the manipulator. However, the converse is not true.

In engineering practice, function (...) ξ is usually linearized in the neighborhood of the static equilibrium ( , ) q θ corresponding to the end-effector position t and external loading F . For the unloaded mode, i.e. when = F 0 and = 0 θ 0 the stiffness model is expressed by a simple relation

( , ) ≈ ⋅ 0 0 F K q θ Δt ( 11
)
where K is 6×6 ''stiffness matrix" and the vector 0 0 1 0 2 0 ( , ,..., ) T n q q q = q defines the equilibrium configuration corresponding to the end-effector location 0 t , in accordance with the manipulator geometry.

However, for the loaded mode, stiffness model have to be defined in the neighborhood of the static equilibrium that corresponds to another manipulator configuration ( , ) q θ , which is caused by external forces F . In this case, the stiffness model describes the relation between the increments of the force δF and the position δt

( , ) ≈ ⋅ F K q θ t δ δ (12)
where = + 0 q q Δq and = + 0 θ θ Δθ denote the new position of the manipulator, Δq and Δθ are the deviations of the passive joint and virtual spring coordinates.

Hence, the problem of the stiffness modeling in the loaded mode may be divided into two sequential subtasks: (i) stiffness model identification from the vector field of displacements and (ii) linearization of relevant force/position relations in the neighborhood of the loaded configuration. Let us consider these two subproblems consequently.

Stiffness model identification

To estimate the desired deflections (t, ϕ), let us apply the least square technique that leads to minimization of the sum of squared residuals

t R t p R p p , n i i i i f min ) ( 1 2 → - - Δ + = ∑ = ϕ ( 13
)
with respect to the vector t and the orthogonal matrix R representing the rotational deflections ϕ. The specificity of this problem (that does not allow direct application of the standard methods) are the orthogonally constraint and non-trivial relation between elements of the matrix R and the vector ϕ. To reduce the computational efforts, let us linearize the rotational matrix R [START_REF] Pashkevich | Accuracy Improvement for Stiffness Modeling of Parallel Manipulators[END_REF]. This allows to rewrite equation of the 'rigid transformation' (9) in the form

n i i i , 1 ; = + × = Δ t p p ϕ (14)
that can be further transformed into a linear system of the following form [ ]

n i i i , 1 ; = Δ = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ p t P I ϕ ( 15
)
where i P is a skew-symmetric matrix corresponding to the vector i p . Then, applying the standard least-square technique and shifting the origin of the coordinate system to the point

∑ = - = n i i c n 1 1 p p leading to expression ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ Δ Δ ⋅ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ∑ ∑ ∑ = = - = - n i i T i n i i n i i T i n 1 1 1 1 1 ˆp P p P P 0 0 I t ϕ ( 16
)
that requires inversion of the matrix of size 3×3. Here, following the adopted notation, i P ˆ is a skew-symmetric matrix corresponding to the vector

c i i p p p - = ˆ.
By its general principle, the FEA-modeling is an approximate method that produces some errors caused by the discretization. Beside, even for the perfect modeling, the deflections in the neighborhood of the reference point do not exactly obey the equation ( 4). Hence, it is reasonable to assume that the 'rigid transformation' (9) incorporates some random errors

n i i i i i , 1 ; ) ( = + + ⋅ = Δ + ε t p R p p ϕ (17)
that are supposed to be independent and identically distributed Gaussian random variables with zero-mean and standard deviation σ.

In the frame of this assumption, the expression for the deflections ( 16) can be rewritten as

= - = = - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + = + = n i i T i n i i T i n i i n 1 1 1 ο 1 1 o ; ε P P P ε t t ϕ ϕ ( 18
)
where the superscript 'o' corresponds to the 'true' parameter value. This justifies usual properties of the adopted point-type estimator [START_REF] Gosselin | Stiffness Analysis of Parallel Mechanisms Using a Lumped Model[END_REF], which is obviously unbiased and consistent. Furthermore, the variancecovariance matrices for t, ϕ may be expressed as

[ ] [ ] 1 1 2 2 ĉov ; cov - = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = = ∑ n i i T i n P P I t σ σ ϕ ( 19
)
allowing to evaluate the estimation accuracy using common confidence interval technique.

Another practical question is related to detecting zero elements in the compliance matrix or, in other word, evaluating the statistical significance of the computed values compared to zero. Relevant statistical technique [START_REF] Akin | Finite Element Analysis With Error Estimators: An Introduction to the FEM and Adaptive Error Analysis for Engineering Students[END_REF] operates with the p-values that may be easily converted in the form a k σ , where k is usually from 3 to 5 and the subscript ' a ' refers to a particular component of the vectors t, ϕ.

To evaluate the standard deviation σ describing the random errors ε , one may use the residual-based estimator obtained from the expression

2 1 2 ) 6 3 ( ) ( E σ - = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ⋅ - Δ + ∑ = n n i i i i t p R p p ϕ . ( 20
)
The latter may be easily derived taking into account that, for each experiment, the deflection filed consist of n three-dimensional vectors that are approximated by the model containing 6 scalar parameters. Moreover, to increase accuracy, it is prudent to aggregate the squared residuals for all FEA-experiments and to make relevant estimation using the coefficient

2 ) 6 3 ( σ m n -
, where m is the experiments number.

In addition, to increase accuracy and robustness, it is reasonable to eliminate outliers in the experimental data. They may appear in the FEA-field due to some anomalous causes, such as unsufficient meshing of some elements, violation of the boundary conditions in some areas of the mechanical joints, etc. The simplest and reliable method that is adopted in this report is based on the 'data filtering' with respect to the residuals.

Stiffness model in the loaded mode

To compute the desired stiffness matrix, let us consider the neighborhood of the loaded configuration and assume that the external force and the end-effector location are incremented by some small values δF , δt . Besides, let us assume that a new configuration satisfies the equilibrium conditions [START_REF] Pashkevich | Enhanced stiffness modeling of serial manipulators with passive joints[END_REF]. Hence, it is necessary

COROUSSO

to consider simultaneously two equilibriums corresponding to the manipulator state variables ( , , , ) F q θ t and ( , , , ) + δ + δ + δ + δ F F q q θ θ t t . Relevant equations of statics may be written as

; 0 T T q θ θ ⋅ = ⋅ ⋅ = F J K θ F J (21) and ( ) ( ) ( ) ( ) ( ) ; 0 T
T + δ ⋅ + δ = ⋅ + δ + δ ⋅ + δ = θ θ θ q q F F J J K θ θ F F J J (22)
where ( , ) q δJ q θ and ( , ) θ δJ q θ are the differentials of the Jacobians due to changes in ( , ) q θ . Besides, in the neighborhood of ( , ) q θ , the kinematic equation may be also presented in the linearized form:

( , ) ( , )

q θ = ⋅ + ⋅ δt J q θ δθ J q θ δq , (23)
Hence, after neglecting the high-order small terms and expending the differentials via the Hessians of the function ( , ) T Ψ = g q θ F , equations ( 21), ( 22) may be rewritten as

( ) ( ) ( ) ( ) ( ) ( )
T F F q T F F q q q q θ θ θ θ θ θ ⋅ δ + ⋅ δ + ⋅ δ = ⋅ δ ⋅ δ + ⋅ δ + ⋅ δ =
J q,θ F H q,θ q H q,θ θ K θ J q,θ F H q,θ q H q,θ θ 0

and the general relation for the stiffness matrix in the loaded mode can be presented as

1 F T F F F q q q T F F T F F F F q q q q q q - θ θ θ θ θ θ θ θ θ θ θ θ ⎡ ⎤ ⎡ ⎤ + = ⎢ ⎥ ⎢ ⎥ * * + + ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ K K J k J J J k H J H k J H H k H (25)
Hence, the presented technique allows computing the stiffness matrix in the presence of the external load and to generalize previous results both for serial kinematic chains and for parallel manipulators.

Industrial problem

Let us demonstrate the efficiency of our design approach on a concrete problem coming from the industrial sector of the region of Nantes (France). One of the most important activity areas of this region is the manufacturing of bathroom components (shower cabin, washbasin, bathtub, etc.). Most of parts used during the assembly process are made of thermosetting materials. The main operations achieved on these parts is trimming, i.e. the suppression of the edges of the parts in order to obtain a good surface roughness.

The tools used for milling are specific mills, which are composed of a large number a diamond glued on its surface. Therefore the number of tooth is supposed to be infinite. However, the use of these specific tools allows the simplification of the model for computing the milling forces.

Let us consider the trimming operation depicted at Figure 2. The milling force may be decomposed into two components, denoted as F t (the tangential force) and F f (the radial force) (the vertical component can be neglected for such kind of operation

Architecture of the manipulator

For the milling process let us specialize the Orthoglide manipulator (Figure 4) [START_REF] Chablat | Architecture Optimization of a 3-DOF Parallel Mechanism for Machining Applications, the Orthoglide[END_REF]. COROUSSO Force size analyses. Results for the same four workpoints are presented on Figure 6. The force-deflection relationship for the force less than 1000 N is linear, but depends on the manipulator configuration. Another conclusion is that in the work point x=y=z=0, the required accuracy can be satisfied for the force up to 600 N, while for all other tested workpoints, it can be satisfied only for forces inferior to 100 N. Moreover, taking into account the force direction, maximum compliance errors for the force 300 N may raise up to 1 mm and more.

Workspace analysis. For the accuracy control through the whole workspace, error maps for opposite planes (z = -200 mm Figure 7a and z = 300 mm Figure 7c) and for the "zero plane" (z = 0 mm Figure 7b) of workspace are presented. It should be noted that the position accuracy depends on the configuration of the manipulator and vary from 0,1 mm to more than 0.5 mm for z=-200 and z=300. The accuracy of the "zero plane" is satisfied for the operation, while for z=-200 mm, guaranteed accuracy is only 0.4 mm, and for z=300, 0.5 mm. But milling in the strongest direction of the manipulator leads to an accuracy more than 0,2 mm. So, optimizing the milling process for the specialized Orthoglide manipulator may improve the accuracy more than 3 times.

COROUSSO 3 30

 3 The reminder of the report is organized as follows. In the Section 2, it is defined the set of problems which are considered in the report. Section 3 presents performance evaluation factors. Section 4 proposes a new method for the stiffness modeling of parallel manipulator. Section 5 illustrate the efficiency of the propose technique on the Orthoglide manipulator by specializing it for milling of bathroom component. And, finally, section 6 summarizes the main contributions of the report. Projet COROUSSO Livrable n°1.3 Comparaison de robots en fonction d'indices locaux et globaux ANR-10-SEGI-003-LI1.

  mapping of the unit sphere (b) mapping of the unit cube. (c) mapping of the velocity transmission in the xy plane.

Figure 1 :

 1 Figure 1: Mapping, using the Jacobian matrix.

COROUSSO

3 30

 3 Projet COROUSSO Livrable n°1.3 Comparaison de robots en fonction d'indices locaux et globaux ANR-10-SEGI-003-LI1.3 30/09/2014 indice A Page 12/24 Auteur : Stéphane CARO COROUSSO models can't guarantee good accuracy. Therefore let us consider the stiffness model improvement and deflections evaluation. Projet COROUSSO Livrable n°1.3 Comparaison de robots en fonction d'indices locaux et globaux ANR-10-SEGI-003-LI1.

  joint coordinates, n is the number of passive joins, m is the number of virtual joints.

,

  is the aggregated vector of the virtual joint reactions, stiffness matrix of the size m×m, and ,i θ K is the spring stiffness matrix of the corresponding link.

  problem strictly, let us denote the displacement field by a set of vector couples

COROUSSO

Figure 2 :

 2 Figure 2: Trimming operation for composite material. The machines tools that are used for the trimming of the bathroom components proposed on the Figure 3 must be designed such as they attain the following characteristics: workspace W abc of size {0.5 m × 0.5 m × 0.5 m}; -||v xy || = 60 m/min (v xy contains the components of the platform velocity vector v in the xy plane); -||f xy || = 300 N (f xy contains the components of the external effort vector f in the xy plane); -||δp xy || = 0.25 mm (δp xy contains the components of the platform deformations vector δp in the xy plane).

Figure 4

 4 Figure 4: CA

Figure 5 :

 5 Figure 5: Influence of the force direction on the deformations of the manipulator in the four test points: (a)-(d) in the polar coordinates (

  deflections in x and y directions); (e)-(h) in the Cartesian coordinates (

Table 1 :

 1 Stiff

	CORO
	design obje
	required wo
	and 14 m/s
	following pa
	and r is the
	and whole m
	4.3 Perfo
	Figure 3:
	manufa
	Model
	Original Bar [
	Revised Bar
	Since the w
	represented
	technique f
	(

This architecture was built in Institut de Recherche en Communications et Cybernetique de Nantes (IRCCyN) and satisfies the following

Table 1

 1

& & & &(4)

The accuracy of milling of composite materials depends on the number of factors such as accurate kinematic and stiffness modeling, performance evaluation, force control, planning of milling process and others. This report contributes to the methodology which is used for the accurate stiffness modeling for the manipulator and it links for the estimation of the deflections errors. It allows evaluating compliance errors caused by the technological process and detecting strongest and lowest directions for the compliance errors. Using this information for the planning of the milling process allows increasing the accuracy of processing of the pieces made of composite materials.

The method is efficiently illustrated on the milling of bathroom components produced in the Nantes region. For the manufacturing, Orthoglide manipulator was revised, and deformations for different forces and work points were presented. The results allow estimating the accuracy of technological process and improving it by the accurate planning of the milling.

While analyzing the modeling results, the several directions for prospective research activities were identified. They include accurate modeling of milling, improving stiffness of the manipulator for the working direction and compliance deformation compensation in the milling process.


André De Palma
email: andre.depalma@ens-cachan.fr

Mohammed Abdellaoui

Moshe Ben-Akiva

Helga Fehr-Duda

Ido Erev

William Davidson

Dennis Fok

Craig R Fox

Ralph Hertwig

Nathalie Picard

Peter P Wakker

Joan L Walker

Martin Weber

Beware of black swans and do not ignore white ones?

Keywords: Black swans, risk, ambiguity, four-fold pattern, (non)-expected utility, probabilistic choices, experience-based decision making, description-based decision making

Uncertainty pervades most aspects of life. From selecting a new technology to choosing a career, decision makers often ignore the outcomes of their decisions. In the last decade a new paradigm has emerged in behavioral decision research in which decisions are "experienced" rather than "described", as in standard decision theory. The dominant finding from studies using the experience-based paradigm is that decisions from experience exhibit "black swan effect", i.e. the tendency to neglect rare events. Under prospect theory, this results in an experience-description gap. We show that several tentative conclusions can be drawn from our interdisciplinary examination of the putative experience-description gap in decision under uncertainty. Several insights are discussed. First, while the major source of under-weighting of rare events may be sampling error, it is argued that a robust experience-description gap remains when these factors are not at play. Second, the residual experience-description gap is not only about experience per se, but also about the way in which information concerning the probability distribution over possible outcomes is learned.

Additional econometric and empirical work might be required to fully flech out these tentative conclusions. However, there was a consensus that an initially polemical literature turns out to be constructive in drawing researcher towards greater rapprochements.

Introduction

The standard paradigm for studying decision under uncertainty entails presenting participants with choices between prospects that are described as event-contingent outcomes (e.g. lose $50 with probability .5, and nothing otherwise; gain $100 if the home team wins and nothing otherwise). The decision maker is either provided with objective probabilities from the outset (risk), or has to assign subjective likelihoods to events (ambiguity). Most of the accumulated empirical findings observed a robust tendency for people to overweight small probabilities, and to underweight moderate to high probabilities under risk (e.g. [START_REF] Tversky | Advances in prospect theory: Cumulative representation of uncertainty[END_REF]. Similarly, under ambiguity people tend to overweight events that they perceive to be unlikely, and underweight events that they perceive to be likely [START_REF] Tversky | Weighing risk and uncertainty[END_REF][START_REF] Fox | A belief-based account of decision under uncertainty[END_REF][START_REF] Wakker | Prospect theory: For risk and ambiguity[END_REF]).

In the last decade a new paradigm has emerged in behavioral decision research in which decision are "experienced" rather than "described". Both probabilities and outcomes must be learned through sampling, i.e. repeated draws with replacement from a probability distribution unknown to the decision maker [START_REF] Hertwig | Decisions from experience and the effect of rare events in risky choice[END_REF]). The dominant finding from studies using this paradigm is that decisions from experience are characterized by diminished impact of rare events (see [START_REF] Barron | Small feedback-based decisions and their limited correspondence to description-based decisions[END_REF][START_REF] Hertwig | Decisions from experience and the effect of rare events in risky choice[END_REF]. [START_REF] Taleb | The black swan: The impact of the highly improbable[END_REF] refers to a related under-sensitivity to rare events as the Black Swan effect. The contrast between decisions from experience and decisions under risk is usually referred to as the "experiencedescription gap."

In this paper we take a critical look at the experience-description gap. First, we take stock of prior contributions to this literature. Second, we propose to investigate ways to enrich the study of the experience-description gap using advanced econometric tools that explicitly account for errors and heterogeneity. Third, we attempt to reconcile the literature on decisions from experience with recent empirical literature on (description based) decision under ambiguity [START_REF] Attanasi | Eliciting ambiguity aversion in unknown and in compound lotteries: A smooth ambiguity model experimental study[END_REF].

Risk and Ambiguity in Prospect Theory

In standard decision making under uncertainty paradigm, an alternative, or a prospect, is described by a list of event-contingent outcomes. To illustrate, let x E y denote the prospect that pays $x if event E obtains, and $y otherwise. For instance, setting x = 10, y = 1, and R = "rain tomorrow," the prospect 10 R 1 denotes a prospect yielding $10 if there is rain tomorrow and $1 otherwise. The evaluation of such alternatives requires an assessment not only of the desirability of outcomes (utilities), but also of the likelihoods of the corresponding events (probabilities or their generalizations). Under risk, standard decision theory recommends evaluating an alternative using expected utility (EU), i.e. the probability-weighted average utility of the outcomes. Thus, the EU of 10 R 1 is P(R)u( 10) + (1-P(R))u(1) (P: probability; u: utility). Risk aversion, the preference of a sure outcome over a risky prospect with equal or higher expected value, is commonly assumed to hold. For risk, with p = P(E), we often write x p y instead of x E y. EU explains risk aversion using a concave utility function over states of wealth-for example if gaining $200 adds less than twice the utility of gaining $100, then a decision maker should prefer $100 for sure to a prospect that offers a 50-50 chance of $200 or nothing.

Several empirical results challenge the descriptive validity of EU. Allais ' (1953) famous example for risk challenged the descriptive validity of EU. It suggests that people do not weight the utilities by their probabilities. More generally, the assumption of risk aversion is violated by the commonly observed fourfold pattern of risk preferences: risk aversion for moderate to high probability gains and low probability losses, coupled with risk seeking for low probability gains and moderate to high probability losses [START_REF] Tversky | Advances in prospect theory: Cumulative representation of uncertainty[END_REF]. Rabin (2000) showed that moderate risk aversion for small-stakes mixed (gain-loss) gambles at all levels of wealth (assuming a strictly increasing and concave utility function) implies an implausible level of risk aversion for large-stakes gambles.

These empirical and theoretical violations of EU are accommodated by prospect theory (PT), the leading descriptive model of decision under uncertainty [START_REF] Kahneman | Prospect theory: An analysis of decision under risk[END_REF][START_REF] Tversky | Advances in prospect theory: Cumulative representation of uncertainty[END_REF]. Under PT, outcomes are evaluated with respect to a reference point, normalized to 0. Utility u is strictly increasing and u(0)=0. It exhibits diminishing sensitivity: marginal utility diminishes with the distance from the reference point, leading to concavity for gains but convexity for losses. Diminishing sensitivity contributes to risk aversion for gains and risk seeking for losses. The latter goes against conventional wisdom, but has been confirmed empirically. Furthermore, utility u is characterized by loss aversion in which the function is steeper for losses than gain-typically this is modeled by multiplying utility for losses by a coefficient λ > 1 (Figure 1). Loss aversion accommodates risk-aversion for modest stakes gambles that scales up reasonably proportionally.

Probabilities are transformed by a weighting function w + for gains and by w -for losses, both normalized so that w(0)=0 and w(1)=1, and strictly increasing (Figure 2). Hence; x p y is evaluated by: w probability interval [0,q] has more impact than the middle interval [p, p+q], which is bounded away from the lower and upper endpoints. Similarly, the upper interval [1-q, 1] has more impact than the middle interval [p, p+q]. The underweighting of moderate to large probabilities reinforces the tendency implied by the S-shaped utility function toward risk averse for gains and risk seeking for losses, but reverses this pattern for very low probabilities, which are overweighted.

+ (p)u(x) + [1-w + (p)]u(y) if x ≥ y ≥ 0; w -(p)λu(x) + [1-w -(p)]λu(y) if x ≤ y ≤ 0; w + (p)u(x) + w -(1-p)λu(y) if x > 0 > y.

The Description-Experience Gap

Research on "decisions from experience" (DFE) employ paradigms in which individuals learn outcomes and their likelihoods through the sequential sampling of outcomes. Three experimental paradigms (see [START_REF] Hertwig | The description-experience gap in risky choice[END_REF]) and variants thereof have been used. All involve a choice between two or more payoff distributions. In the most popular sampling

+ - . 1 1 0 1 -1 - + 1 -
paradigm, people first sample from the distributions as long as they wish without costs. Once search is terminated, they decide from which distribution to make a single incentivized draw.

In the full-feedback paradigm, each draw adds to a person's income, and she receives drawby-draw feedback about the actual and forgone payoffs. Finally, the partial-feedback paradigm restricts feedback to the actual payoffs. Comparisons of DFE with decisions from descriptions (DFD; made on described distributions as in the studies of decision-making under risk; Section 2) reveal a large experience-description gap [START_REF] Hertwig | The description-experience gap in risky choice[END_REF].

Figure 3 illustrates this gap using six representative decision problems. In DFE, people behave as if the rare events have less impact than they deserve according to their objective probabilities, whereas in DFD people behave as if the rare events have more impact than they deserve (consistent with PT). Choice patterns in all three experience-based paradigms are surprisingly similar with the tendency to "underweight" rare events particularly robust in the full-feedback paradigm. It should be noted that when all possible payoffs are identified explicitly, this eliminates underweighting of rare events in the sampling paradigm (see Abdellaoui et al. 2011b, Hadar and[START_REF] Hadar | Information asymmetries in decisions from description versus decisions from experience[END_REF] though this does not appear to occur in the full-feedback paradigm (see [START_REF] Yechiam | The role of personal experience in contributing to different patterns of response to rare terrorist attacks[END_REF].

What causes the description-experience gap?

Five broad contributors to the gap have been advance in prior research-the first two relate to DFE and choices consistent with underweighting and neglect of rare events; the next two relate to DFD, and choices consistent with overweighting of rare events; the final relates to both.

Sampling error and sheer unawareness of the rare events' existence

A world in which all risks and hazards are fully described is unattainable. Therefore, we often cannot help but be unaware of rare events. A close cousin of unawareness is obliviousness due to reliance on the wrong model such as estimating financial risks with tools that assume a normal distribution in non-Gaussian environments [START_REF] Taleb | The black swan: The impact of the highly improbable[END_REF]. Unawareness of rare events can also occur in the sampling paradigm in which people tend to sample little (see [START_REF] Hertwig | Decisions from experience and the effect of rare events in risky choice[END_REF]) and likely contributed to the experience-description gap documented using the original sampling paradigm (cf. [START_REF] Hadar | Information asymmetries in decisions from description versus decisions from experience[END_REF]. In fact, when one accounts for sampling error in the seminal study of [START_REF] Hertwig | Decisions from experience and the effect of rare events in risky choice[END_REF] so that decisions are analyzed with respect to sampled probability distributions over outcomes (i.e. what participants actually experienced) rather than the "objective" probability distributions from which outcomes were sampled (which was opaque to participants), choices accord well with prospect theory (Fox and Hadar 2006).

Selective reliance on past experiences

Reliance on past experiences contributes to the attenuated impact of rare events in DFE.

In many settings people behave as if they rely on small samples drawn from their past experiences (e.g. those more recently experienced; see [START_REF] Hertwig | Decisions from experience and the effect of rare events in risky choice[END_REF], and tend to choose as if they underweight rare events that they have, in fact, experienced. The impact of this tendency also emerged in two choice prediction competitions focusing on the full-and the partial-feedback paradigms (Erev et al. 2010a(Erev et al. , 2010b)): the winning models in both competitions implied reliance on small set of past experiences.

Tallying

A factor amplifying the gap concerns the way people search in the sampling paradigm.

Hills and Hertwig (2010) found that those who frequently switch between the payoff distributions are likely to choose options that win most of the time in round-wise comparisons.

Such comparisons ignore the magnitude of the win (defeat), thus giving little weight to rare events. Frequent switchers thus strongly contribute to the description-experience gap, whereas infrequent switchers are more likely to take account of impactful rare events by forming a running mean.

The mere-presentation effect: Analogical vs. propositional representations [START_REF] Erev | What impacts the impact of rare events[END_REF] have argued that a mere-presentation effect may contribute to overweighting in DFD but not DFE. Specifically, DFD involve propositional representations -e.g., 32 with probability 0.1; 0 otherwise -thus putting more equal emphasis on outcomes than their actual probabilities warrant. If attention translates into decision weights, rare and common events' weights will regress toward the mean. DFE, in contrast, invoke an analogical representation: for instance, draws from the aforementioned option could lead to this sequence: {0, 0, 0, 0, 0, 32, 0, 0, 0, 0}. More attention is allocated to the processing of the frequent than the rare events.

Unpacking and Repacking

When participants sample an entire distribution of outcomes without replacement so that there is no sampling error, and therefore no unawareness, there appears to remain a reduced but significant description-experience gap in their choices, and selective reliance on past experiences may not play a role, as judgments are quite accurate [START_REF] Ungemach | Are probabilities overweighted or underweighted, when rare outcomes are experienced (rarely)?[END_REF]). [START_REF] Fox | Unpacking decisions from description and experience[END_REF] validated the robustness of this finding and argued that it was due to the fact that decisions from experience using the sampling paradigm "unpack" occurrence of outcomes (and therefore attention afforded them) in proportion to their objective probabilities (Similar to Erev et al, 2008 cited above). [START_REF] Fox | Unpacking decisions from description and experience[END_REF] show that decisions from description can be made to resemble decisions from experience if described outcomes are explicitly unpacked. For example, describing the outcome of a game of chance in a "packed" manner (e.g., "get $150 if a 12-sided die lands 1-2; get $0 otherwise") leads to PT-like preferences. In contrast, "unpacking" the same description using a table of outcomes by die roll (e.g., "$150 if the die rolls 1; $150 if the die rolls 2; $0 if the die rolls 3; $0 if the die rolls 4"; etc.) leads to the opposite pattern of risk preferences, much like decisions from experience.

Moreover, [START_REF] Fox | Unpacking decisions from description and experience[END_REF] show that prompting decisions makers to mentally "repack" events that are sampled from experience (by postponing identification of outcomes associated with sampled events until after sampling is completed) leads to choices that accord with prospect theory. This result accords with the aforementioned observation of [START_REF] Hills | Information search and decisions from experience: Do our patterns of sampling foreshadow our decisions?[END_REF] that participants who sample each distribution separately tend toward more prospecttheory like behavior-one presumes that such sampling facilitates a spontaneous "repacking" of probabilities (i.e. consideration of overall impressions of probability of each outcome).

This work is important because it suggests that the putative experience-description gap is not about experience per se but rather about the way in which information is presented.

Decision under described ambiguity

It seems a little odd to some of us that evidence for the experience-description gap has relied almost exclusively on comparisons between DFE paradigms involving sampled experience to DFD under risk. Because outcome probabilities are generally ambiguous to decision makers in the DFE paradigms, a more apt comparison might be between DFE and DFD under ambiguity.

The presence of ambiguity introduces two complications to decision weighting under prospect theory. First, decision makers must judge the likelihood of events for themselves.

Several studies suggest that to a first approximation, choices accord with a two-stage model [START_REF] Tversky | Weighing risk and uncertainty[END_REF][START_REF] Fox | A belief-based account of decision under uncertainty[END_REF]Fox and See, 2003) in which the probability weighting function from prospect theory is applied judged probabilities of events, consistent with support theory (Tversky and Koehler, 1994;[START_REF] Rottenstreich | Unpacking, repacking, and anchoring: Advances in support theory[END_REF].

Generally people tend to overestimate the likelihood of rare events and underestimate the likelihood of very common events, which would tends to amplify the characteristic pattern of over-and underweighting-in prospect theory. That said, with the standard sampling paradigm in which a small number of outcomes is sampled in a very compact period of time, judged probabilities are generally quite accurate (e.g., Fox and Hadar, 2006), perhaps due people's natural facility in counting (e.g. [START_REF] Hasher | Automatic processing of fundamental information: The case of frequency of occurrence[END_REF].

Second, the shape of the weighting function can vary by domain or source of uncertainty, which is defined as a group of events that -being generated by the same mechanism of uncertainty -have similar characteristics (see Tversky andFox 1995, Wakker and[START_REF] Tversky | Weighing risk and uncertainty[END_REF]Abdellaoui et al., 2011a). There is accumulating experimental evidence that the probability weighting function is systematically affected by specific characteristics of the decision situation, whereas the curvature of the utility function is not (e.g., Fehr-Duda and Epper 2012). For example, departures from linear weighting are more pronounced in affectladen situations than in comparatively pallid ones (Rottenstreich and Hsee, 2001), and highstake prospects are evaluated much less optimistically (i.e. lower elevation) than low-stake prospects are [START_REF] Fehr-Duda | Rationality on the rise: Why relative risk aversion increases with stake size[END_REF]). More to the point, people typically exhibit aversion to betting on ambiguous events [START_REF] Ellsberg | Risk, ambiguity and the Savage axioms[END_REF], particularly when they feel relatively ignorant or incompetent assessing those events (Heath and Tversky, 1991;[START_REF] Tversky | Weighing risk and uncertainty[END_REF]Fox and Weber, 2002) though ambiguity seeking is occasionally observed, especially for losses (Camerer and Weber, 1991).

If ambiguous probabilities are weighted comparatively more pessimistically than chance (risky) probabilities, it stands to reason that sampled outcomes will also be evaluated more pessimistically (especially when directly contrasted with described risk; cf. [START_REF] Tversky | Weighing risk and uncertainty[END_REF]. In fact, Abdellaoui et al. (2011b) observe such a difference in elevation of probability weighting functions between DFD and DFE, consistent with this point of view.

Calibration and estimation

We assert that the study of the putative experience-description gap can be enriched by applying advanced econometric estimation of decision parameters, first individual, then for (heterogeneous) groups (See [START_REF] Ben-Akiva | Process and Context in Choice Models[END_REF][START_REF] Wilcox | Stochastic models for binary discrete choice under risk: A critical primer and econometric comparison[END_REF]. We assume observed preferences between J pairs of prospects x p y and x' q y' The vector δ denotes the subjective parameters determining (w,u,λ). We assume only gains, writing w = w + . The PT value of x p y, PT δ (x p y), ,depends on δ. Our general notation facilitates applications of the following techniques to decision models other than PT and can allow us to examine robustness of an experience-description gap.

Deterministic models

One way to estimate δ is by minimizing some distance function. If we can, say, derive certainty equivalents from our data, then we can take δ such that the certainty equivalents predicted by δ are as close as possible to the observations. Another way is to minimize the number of observed choices in J that δ mispredicts. This will usually give a region of optimal δs.

Stochastic models

Thus far we have assumed a deterministic model of choice and specified no error theory. We next consider a number of probabilistic choice models. After describing an error process, maximum likelihood (ML) estimation can be used to estimate δ.

Trembling or misreporting

Decision makers can get confused and choose randomly, say with probability π. In this case the probability of a "wrong" choice becomes π/2. It can be shown that the likelihood is then maximized by maximizing the number of correctly predicted choices, agreeing with the aforementioned second deterministic way. The ML estimate of π is twice the proportion of incorrect prediction choices.

Continuous error

An alternative error process entails that a random and independent, continuously distributed noise term ε is added to each PT value, or that each PT value is multiplied by a random positive factor. It can be seen that we obtain the well-known logit model when ε has an extreme value distribution. In the additive case, the decision maker now chooses x p y over

x' q y' with probability

exp[ ] exp[ ] + exp[ ′ ′ ] ,
where σ > 0 denotes the scale parameter of the extreme value distribution. The bigger σ is, the closer we are to random, fifty-fifty, choice. For σ tending to 0, we approximate deterministic choice. ML can again be used to estimate σ and δ.

Random parameters

Some error models assume that in each choice situation a new PT model is chosen according to some probability distribution over δ. For example, the power of the utility function may be determined randomly for each choice. Whereas the above models allow for implausibly frequent violations of stochastic dominance (when the PT value is close between two options, but one stochastically dominates another prospect), these models allow for no such violation. The resulting likelihood functions are more complex and require simulation methods [START_REF] Train | Discrete choice methods with simulation[END_REF]) especially when several individual parameters have to be measured simultaneously (e.g. the power of the utility function, the kink of utility between gains and losses, and the parameter of the probability weighting function, as in de Palma and Picard, 2010).

Error theories for decision from experience

In DFE, probabilities of outcomes are not described to subjects, but subjects have to learn them from sampling. To formulate this learning one could define the decision maker's knowledge about the unknown probabilities p and q as the (prior) probability distribution f(p,q). One can then apply PT using f(p,q) and invoke the above error theories, combined with theories of learning and updating. This may lead to new explanations of the discrepancies between DFE and DFD, such as regarding the weighting for rare events (black swans).

Group models and heterogeneity

While the above models focus on parameters at the individual level, the techniques can also be used to estimate population or group level parameters. Heterogeneity of δ can either

Conclusions

Several tentative conclusions can be drawn from our interdisciplinary examination of the putative experience-description gap in decision under uncertainty.

First, while the major source of under-responsiveness to rare and "Black Swan" events may be sampling error (which can cause sheer unawareness that rare events could occur) and misplaced faith in Gaussian distributions (which can give rise to misplaced confidence that rare events will not occur), a robust experience-description gap remains when these factors are not at play.

Second, the residual experience-description gap is not only about experience per se but also about the way in which information concerning the probability distribution over possible outcomes is learned by a decision maker. Thus, methods that draw decision makers' attention to possible outcomes in proportion to their probabilities of occurrence (in any sort of analogical fashion) may cause decision makers to weight them more linearly.

Third, if one accounts for the fact that DFE paradigms entail ambiguity then one ought to compare DFE to DFD under ambiguity (rather than risk), where decision makers generally tend toward more "pessimistic" decision weights; the presence of ambiguity may therefore account for some of the putative experience-description gap.

Finally, much future empirical and econometric work is required to fully flesh out these tentative conclusions, but we are encouraged to see that an initially polemical literature has spawned so much constructive new empirical work that is drawing researchers toward greater rapprochement.

FigureFigure 2

 2 Figure 1: Prospect theory utility function

Figure 2 :

 2 Figure 2: Probability weighting function Numerous studies surveyed by Wakker (2010) have confirmed the above qualitative

Figure 3 :

 3 Figure 3: The experience-description gap

  systematically vary across the population in the logit equation above (by interacting the parameters with individual characteristics) or randomly vary as in the random parameter model. The random parameter distribution is assumed to be a distribution across a population rather than across decision instances of a single individual. The random distribution can be either continuous or discrete. The discrete case (a latent class choice model) allows one to estimate segments of the population that have distinctly different decision behaviors. The resulting model describes both who is likely to be in the segment as well as the segmentspecific behavior (Walker and Ben-Akiva 2011). This could be useful in capturing different probability weighting functions and loss aversion characteristics as influenced by the experimental design. In one early attempt at econometric estimation, Fox et al. (2013) compared choices in a DFE sampling paradigm to choices in decision under risk by the same participants over a number of studies. They relied on the most successful parameterization of PT from a horse race run by Stott (2006), which included a logit error model. A common utility function parameter and error parameter were assumed to apply to DFE and DFD, but the (single) weighting function parameter was allowed to vary across methods. Estimation was accomplished using simple MLE. Results of this investigation found that data accord well with a stochastic PT model in which decisions from description are characterized by an inverse-S shaped weighting function and decisions from experience are characterized by decision weights that almost exactly linear (i.e., w(p) = p).