Birgitta Dresp-Langley
email: birgitta.dresp@unistra.fr

Geometry and visual preference

Keywords: Visual symmetry, affine projection, fractals, visual sensation, aesthetics, preference

Evolution and geometry generate complexity in similar ways. Evolution drives natural selection while geometry may capture the logic of this selection and express it visually, in terms of specific generic properties representing some kind of advantage. Geometry is ideally suited for expressing the logic of evolutionary selection for symmetry, which is found in the shape curves of vein systems and other natural objects such as leaves, cell membranes, or tunnel systems built by ants. The topology and geometry of symmetry is controlled by numerical parameters, which act in analogy with a biological organism's DNA. The introductory part of this paper reviews findings from experiments illustrating the critical role of two-dimensional design parameters and shape symmetry for visual or tactile shape sensation, and for perception-based decision making in populations of experts and non-experts. Thereafter, results from a pilot study on the effects of fractal symmetry, referred to herein as the symmetry of things in a thing, on aesthetic judgments and visual preference are presented. In a first experiment (psychophysical scaling procedure), non-expert observers had to rate (scale from 0 to 10) the perceived beauty of a random series of 2D fractal trees with varying degrees of fractal symmetry. In a second experiment (two-alternative forced choice procedure), they had to express their preference for one of two shapes from the series. The shape pairs were presented successively in random order. Results show that the smallest possible fractal deviation from "symmetry of things in a thing" significantly reduces the perceived attractiveness of such shapes. The potential of future studies where different levels of complexity of fractal patterns are weighed against different degrees of symmetry is pointed out in the conclusion.

Introduction

Brain evolution has produced highly specialized processes which enable us to effectively exploit the geometry of visual perceptual space. Some data suggest that the human brain is equipped with an in-built sense of geometry (e.g. [START_REF] Amir | Sensitivity to non-accidental properties across various shape dimensions[END_REF][START_REF] Amir | Greater sensitivity to nonaccidental than metric shape properties in preschool children[END_REF], which is a key to conscious knowledge about specific object properties and associations between two-dimensional projections and their correlated three-dimensional structures in the real world (e.g. [START_REF] Biederman | Recognition-by-components: A theory of human image understanding[END_REF][START_REF] Wilson | Symmetry perception: A novel approach for biological shapes[END_REF][START_REF] Pizlo | New approach to the perception of 3D shape based on veridicality, complexity, symmetry and volume: a mini-review[END_REF][START_REF] Li | Symmetry is the sine qua non of shape[END_REF]. These associations favour structural regularities and, above all, symmetry [START_REF] Li | A computational model that recovers the 3D shape of an object from a single 2D retinal representation[END_REF][START_REF] Li | Symmetry is the sine qua non of shape[END_REF]. Thus, it is not surprising that symmetry plays an important role in conceptual processes and the design geometry of complex spatial structures, and is abundantly exploited by engineers and architects. The use of the symmetry of curvature, for example, dates back to the dawn of building shelter and vernacular architecture, which relies, by the nature of the materials and construction techniques used, almost entirely on symmetrical curves (Figure 1, left). In the middle ages, descriptive geometry was used for the planning and execution of building projects for which symmetric curves were the reference model, as in the design of arched hallways and corridors (Figure 1, middle). In the last century, the Spanish designer and architect Gaudi exploited the same kind of geometry for the design of the Sagrada Familia in Barcelona (Figure 1, right) and many of his other fabulous structures, which can be appreciated by taking a walk through the Guëll Park, or by visiting the Guëll museum in Barcelona.

FIGURE 1

Gaudi's structures were largely inspired by nature, which abounds with curved shapes and features (see also Ghyka, 1946), and our perception uses these features as cues to shape or object recognition and image interpretation (e.g. Stevens 1981a and b; Dresp andGrossberg, 1997, 1998;[START_REF] Dresp | Asymmetrical contrast effects induced by luminance and color configurations[END_REF]Dresp andLangley, 2005, 2006;[START_REF] Dresp | Depth perception from pairs of overlapping cues in pictorial displays[END_REF][START_REF] Foley | Visual perception of extent and the geometry of visual space[END_REF][START_REF] Dresp | Which geometric model for the perceived curvature of 2-D shape contours?[END_REF][START_REF] Dresp-Langley | Generic properties of curvature sensing by vision and touch[END_REF][START_REF] Dresp-Langley | 2D geometry predicts perceived visual curvature in context-free viewing[END_REF][START_REF] Mustonen | Visual performance with small concave and convex displays[END_REF][START_REF] Strother | The lemon illusion: seeing curvature where there is none[END_REF]. In biology, curvature guides physical, chemical, and biological processes, such as protein folding, membrane binding, and other biophysical transformations (Grove, 2009). The representation and cognition of curvature ranges from the biochemical level of living organisms capable of sensing this property in their near or distant physical environments [START_REF] Hatzakis | How curved membranes recruit amphipathic helices and protein anchoring motifs[END_REF] to perceptual properties extracted from physical stimuli by the human brain, the ultimate product of evolution. In terms of a mathematical property of the physical world, curve symmetry can be directly linked to affine geometry (see also [START_REF] Gerbino | Visual orientation and symmetry detection under affine transformations[END_REF].

Affine geometry and visual sensation

In affine geometry, curves derived from circles and ellipses share certain properties, the circle being a particular case of the ellipse. Projective geometry permits generating symmetric curves from ellipses by affinity with concentric circles (Figure 2).

FIGURE 2

Their perception is grounded in biology in the sense that most natural objects can be represented in 2D as symmetrically curved shapes with Euclidean properties of ellipses.

Studies comparing between visually perceived curvature by experts in geometry (architects and design engineers) and non-experts (Dresp, Silvestri and Motro, 2006), using symmetric curves derived from concentric circles by affine projection have shown that their perceived magnitude is determined by a single geometric parameter, the curves' aspect ratio. The perceptual responses to such curves are independent of both expertise and sensory modality, given that tactile sensing by sighted blindfolded and congenitally blind observers produces the same results [START_REF] Dresp-Langley | Generic properties of curvature sensing by vision and touch[END_REF]. The symmetry of the curves, however, is a critical factor to these geometry-based perceptual responses [START_REF] Dresp-Langley | 2D geometry predicts perceived visual curvature in context-free viewing[END_REF]. The aspect ratio relates the height (sagitta) to the width of a curve, and in symmetric curves of variable size but constant aspect ratio directly taken from concentric circles (no projection by affinity), perceived curvature is also constant, in both vision and touch. This observation is directly linked to the phenomenon of scaleinvariance in visual curvature discrimination (cf. [START_REF] Whitaker | Geometric representation of the mechanisms underlying human curvature detection[END_REF] and in the detection and recognition of shapes in general (cf. Pizlo, 1994).

Reflection and rotational shape symmetry

The role of reflection symmetry in visual perception was pointed out by Gestalt psychologists at the beginning of the 20th century [START_REF] Bahnsen | Eine Untersuchung über Symmetrie und Asymmetrie bei visuellen Wahrnehmungen[END_REF]Koffka, 1935) as a major factor in shape perception. It refers to specific transformations by transition of points in Euclidean space resulting in mirrored representations. Axial symmetry (e.g.), which results from point-by-point mirroring across an axis (f (x, y, z) = f (-x, y, z)), is an important factor in visual recognition (e.g. [START_REF] Braitenberg | Reading the structure of brains[END_REF][START_REF] Beck | Symmetry perception in humans and macaques[END_REF][START_REF] Tjan | Symmetry impedes symmetry discrimination[END_REF]. Reflection or mirror symmetry is detected fast [START_REF] Barlow | The versatility and absolute efficiency of detecting mirror symmetry in random dot displays[END_REF][START_REF] Wagemans | Detection of symmetry in tachistoscopically presented dot patterns: Effects of multiple axes and skewing[END_REF], in foveal and in peripheral vision [START_REF] Barrett | Discriminating mirror symmetry in foveal and extra-foveal vision[END_REF]. Vertical mirror symmetry facilitates face recognition by human (e.g. [START_REF] Thornhill | Facial attractiveness[END_REF] and non-human primates [START_REF] Anderson | Are monkeys aesthetists? Rensch (1957) revisited[END_REF], and is used by the human visual system as a second-order cue to perceptual grouping [START_REF] Machilsen | The role of vertical mirror symmetry in visual shape perception[END_REF]. Rotational symmetry of shape plays an important role in architecture and design (e;g. [START_REF] Arnheim | Visual Thinking[END_REF]. The design of complex modern spatial structures is a domain of contemporary relevance. Visual-spatial experiments on expert architects as well as novices have shown that perceiving the rotational symmetry of partial shapes which constitute the simplest possible tensegrity (tensile integrity) structure (Figure 4) is an important part of our understanding how they are put together. Only once this symmetry is perceived by the expert or novice, will he/she be able to draw the structure from memory into axonometric or topological reference frames provided to that effect (Silvestri, Motro, Maurin and Dresp-Langley, 2010). Tensegrity structures have inspired current biological models (e.g. [START_REF] Levin | Biotensegrity: The tensegrity truss as a model for spine mechanics[END_REF], from the level of single cells to that of the whole human body. They posses what [START_REF] Mandelbrot | The fractal geometry of nature[END_REF] called "fractal consistency across spatial scales", or "fractal iterations", like those seen in large trees that appear composed of many smaller trees of the same structure.

Nature-inspired design and the symmetry of "things in a thing"

Fractal geometry is also inspired by nature [START_REF] Mandelbrot | The fractal geometry of nature[END_REF], with its many symmetric visual structures like those found in cells, trees, butterflies and flowers. A fractal may be defined as a complex whole (object or pattern) that has the same structural characteristics as its constituent parts. The structural symmetry that results from fractal iterations may be described as the symmetry of things in a thing. The radial symmetry of a sunflower is a choice example of fractal symmetry as it exists in nature. Behavioural studies have shown that various animal species are naturally attracted to two-dimensional representations of objects exhibiting flower-like radial symmetry [START_REF] Lehrer | Shape vision in bees: Innate preference for flower-like patterns[END_REF][START_REF] Giurfa | Symmetry perception in an insect[END_REF]. In complex 3D fractal trees, single fractals ("things") have a symmetrical counterpart within the whole structure (the thing), which may possess radial symmetry, reflection symmetry and manifold rotational symmetries, like many objects in nature (plants, snowflakes, etc.) are bound by both reflection and rotational symmetry, and exhibit multiples of one and the same shape (things) repeated in all directions.

Nature-inspired design occupies an important place in contemporary graphic art, and symmetry has been identified as a major defining feature of visual beauty, compositional order, and harmony. Symmetry directly determines aesthetic preferences and the subjectively perceived beauty of two-dimensional visual images and patterns [START_REF] Eisenman | Complexity-simplicity: I. Preference for symmetry and rejection of complexity[END_REF][START_REF] Berlyne | Aesthetics and psychobiology[END_REF][START_REF] Jacobsen | Aesthetics judgments of novel graphic patterns: Analyses of individual judgments[END_REF][START_REF] Jacobsen | Descriptive and evaluative judgment processes: Behavioral and electrophysiological indices of processing symmetry and aesthetics[END_REF][START_REF] Jacobsen | Brain correlates of aesthetic judgment of beauty[END_REF][START_REF] Tinio | Just how stable are stable aesthetic features? Symmetry, complexity, and the jaws of massive familiarization[END_REF], and symmetrical visual patterns are also more easily remembered and recognized [START_REF] Deregowski | Symmetry, Gestalt and information theory[END_REF][START_REF] Deregowski | The role of symmetry in pattern reproduction by Zambian children[END_REF]Kayert & Wagemans, 2009) compared with asymmetrical ones. [START_REF] Sabatelli | Asymmetry, symmetry and beauty[END_REF] suggested that natural and artistic creative processes rely on common, possibly fractal, transformations. Fractal transformations may describe iterative transitions from simplicity and order (symmetry) to complexity and chaos (asymmetry).

Again, fractal trees seem to be a pertinent example here, where simple 2D mirror trees (Figure 3) with reflection and/or radial symmetry open an almost infinite number of possibilities for adding complexity through further transformations leading to complex projections of 3D structures with multiple rotational symmetries (not shown here).

FIGURE 3

Whether nature-inspired fractal design appeals to our senses in the same way as the real objects found in nature remains an open question. However, on the basis of previous findings summarized here above, we may assume that the symmetry of things in a thing in fractal design plays a decisive role in our perception of their aesthetic content and thereby influence certain preference judgments. Given the multiple levels of complexity of fractal objects, trying to address this question requires starting with simple examples. For this pilot study here, we created a series of fractal mirror trees based on geometric transformations as shown in Figures 2 and3. In two psychophysical experiments, one using a subjective aesthetic rating procedure, the other a preference judgment design, we tested whether the subjective attractiveness of such trees is affected by different degrees of violation of symmetry, from an almost imperceptible lack of mirror detail to massive asymmetry.

Materials and methods

The experiments were conducted in accordance with the Declaration of Helsinki (1964) and with the full approval of the corresponding author's institutional (CNRS) ethics committee. Informed written consent was obtained from each of the participants.

Experimental sessions were organized following conditions of randomized, trial-by-trial free image viewing using a computer with a keyboard and a high resolution monitor. 15 mirror tree images were generated using a comprehensive vector graphics environment (Adobe Illustrator CC) and computer shape library.

Stimuli

The stimuli for the two experiments were generated on the basis of 15 images of fractal trees (Figure 5) drawn in a vector graphics environment (Adobe illustrator CC) using simple principles of 2D geometry, as shown here above in Figure 3. Five of these images (Figure 4, top row) were mirror trees with vertical reflection symmetry and perfect symmetry of things in a thing. Five of them (Figure 4, middle row) were imperfect mirror trees in the sense that their vertical reflection symmetry excluded one of the elementary parts, which was not mirrored on the right side of the tree. In the remaining five, asymmetrical images Figure 4, bottom row), elementary shapes "growing" on the branches of the left side of the trees were not mirrored on the right side. The luminance contrast between figures and backgrounds was constant in the 15 images (same RGB (200,200,200) for all figures, same RGB (20,20,20) for all backgrounds). The height of a fractal tree on the screen was 10 cm, the widest lateral expansion in the vertical direction of any given tree was 4 cm.

FIGURE 4

Task instructions

In the aesthetic rating experiment, subjects were instructed to rate the beauty of each of the fifteen individual images on a subjective psychophysical scale from 0 (zero) for "very ugly" to ten (10) for "very beautiful". In the preference judgment experiment, subjects were instructed to indicate whether they spontaneously preferred the left or the right of an image pair. Hitting the response key initiated the next image pair. Half of the subjects started with the rating experiment, the other half with the preference judgment experiment.

Procedure

Subjects were seated at a distance of 1 meter from the screen and looked at the center of the screen. The images were displayed centrally and presented in random order. In the aesthetic rating experiment, each of the 15 images was presented once to each of the 30 subjects. In the preference judgment experiment, each image from a group of five was paired with its counterpart from the two other groups of five. Their spatial position in a pair (left/right) was counterbalanced. This yielded 20 image pairs that were presented twice each to each of the 30 subjects in an individual session. Individual responses were coded and written into text files for further processing. Inter-stimulation intervals were observer controlled. They typically varied from one to three seconds, depending on the observer, who initiated the next image presentation by striking a given response key on the computer keyboard.

Results

The raw data from the two experiments were analyzed using Systat 11. Data plots showing medians and variances of the rating distributions were generated. Means and their standard errors of the subjective aesthetic ratings and the total number of "preferred" responses from the preference judgment task were plotted for comparison between figure types. One-way analyses of variance testing for statistical significance of differences in means observed for the three figure types: 'symmetrical', 'single detail missing on right' and 'asymmetrical' were performed.

Subjective aesthetic ratings

The medians and variance of the subjective aesthetic ratings between zero and ten produced by the 30 subjects in response to the 15 images were plotted as a function of the three-level figure type factor (Figure 5). With five figures per factor level and 30 individual ratings per figure, we have a total of 150 observations for each level of this factor, and a total of 450 observations. The distribution of observations satisfies criteria of normality and equality of variance for further parametric testing, outliers were not removed from the dataset. One-way ANOVA signaled a significant effect of figure type on raw data for subjective beauty ratings (F(2, 449)=79.47; p<.001). The differences between the means, plotted here in terms of the average subjective rating and its standard error for each figure type (Figure 6), reveal that perfectly symmetrical figures score higher for subjective beauty than figures with a detail missing (t(1, 149)=7.15; p<.001), post hoc Holm-Sidak comparison), and that figures with a detail missing score higher than asymmetrical figures (t(1, 149)=5.42; p<.001), post hoc Holm-Sidak comparison).

The largest difference in average aesthetic ratings is observed between symmetrical and asymmetrical figures (t(1, 149)=12.57; p<.001, post hoc Holm-Sidak comparison). When average beauty ratings are plotted as a function of the individual figures (Figure 7), we see that none of the three figure types produced an average score in the extremes ("very beautiful" or "very ugly"). The five symmetrical ones (1 to 5 on the x-axis) produced average ratings between '5' and '8', the five with a small detail missing on the right (6 to 10 on the x-axis) produced average scores between '4' and '6', and the five asymmetrical figures (11 to 15 on the x-axis) scored between '3' and '4' on average.

Preference judgments

The total number of times each figure of the 15 was chosen as "preferred" in a pair of images in the preference judgment task was counted. One-way ANOVA on the total number of preferences for a figure of each type (N=5 per factor level) signaled a significant effect of figure type on preference (F(2, 14)=368.12; p<.001). The differences between means, plotted here in terms of the average number of "preferred" and its standard error for each figure type (Figure 8), reveal that perfectly symmetrical figures yield larger preferences than figures with a detail missing (t(1, 4)=19.00; p<.001), post hoc Holm-Sidak comparison), and that figures with a detail missing yield larger preferences than asymmetrical figures (t(1, 4)=7.28; p<.001), post hoc Holm-Sidak comparison). The largest difference in number of "preferred" is observed between symmetrical and asymmetrical figures (t(1, 4)=26.28; p<.001, post hoc Holm-Sidak comparison). When the total number of "preferred" responses is plotted as a function of the 15 individual figures (Figure 9), we see that the five symmetrical figures (1 to 5 on the x-axis) produced almost identical high-preference totals, while the other figures produced more variable ones in the lower preference range.

FIGURE 8 FIGURE 9

Discussion

As illustrated by examples from the introduction here above, shape sensation and perception can be related to affine design geometry (e.g. [START_REF] Bahnsen | Eine Untersuchung über Symmetrie und Asymmetrie bei visuellen Wahrnehmungen[END_REF]Koffka, 1935;[START_REF] Braitenberg | Reading the structure of brains[END_REF][START_REF] Gerbino | Visual orientation and symmetry detection under affine transformations[END_REF][START_REF] Dresp-Langley | 2D geometry predicts perceived visual curvature in context-free viewing[END_REF]. Similarly, the topology and geometry of fractal objects may be controlled by a few simple geometric parameters, as in the fractal mirror trees that were used as stimuli here. The term "fractal" was first introduced by [START_REF] Mandelbrot | The fractal geometry of nature[END_REF] based on the meaning "broken" or "fractured" (fractus), with reference to geometric patterns existing in nature. The findings from this study here show that the smallest "fractal" deviation from perfect symmetry of things in a thing in basic mirror trees (any computer shape library can generate them) with vertical reflection symmetry when no fractals are removed, significantly diminishes subjectively perceived beauty and visual preference. These results confirm previous observations from aesthetic perception studies using different two-dimensional configurations [START_REF] Eisenman | Complexity-simplicity: I. Preference for symmetry and rejection of complexity[END_REF][START_REF] Berlyne | Aesthetics and psychobiology[END_REF][START_REF] Jacobsen | Aesthetics judgments of novel graphic patterns: Analyses of individual judgments[END_REF][START_REF] Jacobsen | Descriptive and evaluative judgment processes: Behavioral and electrophysiological indices of processing symmetry and aesthetics[END_REF][START_REF] Jacobsen | Brain correlates of aesthetic judgment of beauty[END_REF][START_REF] Tinio | Just how stable are stable aesthetic features? Symmetry, complexity, and the jaws of massive familiarization[END_REF]. Perfectly symmetrical trees also produced the strongest consensual results, for both subjective aesthetic ratings and visual preferences, while the ones with a small detail missing and the asymmetrical trees produced more disparate data, indicating higher uncertainty (i.e. less confidence) in the subjects' perceptual responses.

In nature, it is indeed difficult to find things which do not have at least one axis of mirror or reflection symmetry, such as palm trees and sunflowers or broccoli and snowflakes (cf. Mandelbrot, 1975), for example. Also, most human beings are basically symmetric around the vertical axis when standing up, and it is therefore almost unsurprising that our aesthetic preferences would mostly go for symmetrical objects (see also [START_REF] Tinio | Just how stable are stable aesthetic features? Symmetry, complexity, and the jaws of massive familiarization[END_REF], on massive familiarization). However, results from earlier studies [START_REF] Eisenman | Preference for complexitysimplicity and symmetry-asymmetry[END_REF]) lead to suggest that things may not be that simple when complexity and symmetry are weighed against each other, and when socio-cultural factors are brought into the equation. Personality and creativity [START_REF] Eisenman | Complexity preference and semantic differential ratings of complexity-simplicity and symmetry-asymmetry[END_REF][START_REF] Arnheim | Visual Thinking[END_REF][START_REF] Cook | Aesthetic preferences for architectural styles vary as a function of personality[END_REF] have been identified as two such variables, and highly creative individuals may have a stronger tendency to prefer asymmetrical objects, especially when these exhibit high levels of complexity, as in the case of fractal objects with multiple rotational symmetries, for example. As pointed out previously [START_REF] Sabatelli | Asymmetry, symmetry and beauty[END_REF], symmetry and asymmetry coexist in many natural and human processes, and the critical role of symmetry in art has been well demonstrated; the complementary role of asymmetry maybe less . Fractal objects offer new perspectives for research on complementary aspects of symmetry and asymmetry in processes of increasing complexity, including processes of visual perception.

Fractals are different from other geometric figures because of the way in which they scale across multiple iterations, yielding increasingly complex repetitive structures which are symmetrical by nature. Fractal symmetry is also referred to as expanding symmetry or evolving symmetry, especially if replication is exactly the same at every scale, as in a detailed pattern that repeats itself across multiple fractal iterations. For the visual scientist, this opens many perspectives as it permits the finely controlled manipulation of each and every shape detail in a given configuration and thereby allows to create visual stimuli where variations in complexity and symmetry can be effectively weighed against each other in further studies.

Conclusion

The visual attractiveness of 2D fractal design shapes closely depends on the symmetry of things in a thing in configurations with simple geometry, as shown in this pilot study here on the example of a few very basic fractal mirror-trees. In these simple displays, the smallest "fractal" deviation from a perfect symmetry of things in a thing is shown to have significantly negative effects on subjectively perceived beauty and preference judgments.

These findings are to encourage further studies, using more sophisticated fractal design objects with increasingly large number of fractal iterations, producing more and more complex 2D mirror designs and shapes with increasingly multiple rotational symmetry in 3D. Such design objects are ideally suited for a numerically controlled manipulation of the smallest of details in the symmetry of things in a thing, perfectly tailored for investigating complex interactions between symmetry and complexity in their effects on visual sensation and aesthetic perception.

Figure captions

FIGURE 1

The importance of the symmetry of curves for human endeavour dates back to the dawn of building shelter and to vernacular architecture (left). Symmetric curve geometry is currently used in contemporary free-form architecture (middle), which has been much inspired by the Spanish architect Gaudi, who largely exploited symmetry of curvature for the design of the hall and archways of the Sagrada Familia in Barcelona (right).

FIGURE 2

Projective geometry permits generating symmetric curves from ellipses by affinity with concentric circles .Their perception is grounded in biology in the sense that most natural objects can be represented in images as symmetrically curved shapes with the Euclidean properties of ellipses. Symmetric curves yield visual and tactile sensations of curvature which increase exponentially with the aspect ratio of the curves (e.g. [START_REF] Dresp-Langley | Generic properties of curvature sensing by vision and touch[END_REF][START_REF] Dresp-Langley | 2D geometry predicts perceived visual curvature in context-free viewing[END_REF] FIGURE 3 Fractal geometry and affine geometry share principles of projection in Euclidean space.

Fractal trees, inspired by nature [START_REF] Mandelbrot | The fractal geometry of nature[END_REF], may be defined as complex wholes where every part repeats itself across multiple fractal iterations, producing symmetry of things in a thing. In the simple fractal mirror-tree shown here, concentric circles are the mathematical basis for describing structural regularities with vertical reflection (mirror) symmetry, which has been identified as a major determinant of the visual attractiveness of image configurations (e.g. [START_REF] Eisenman | Complexity-simplicity: I. Preference for symmetry and rejection of complexity[END_REF].

FIGURE 4

Stimuli from the aesthetic rating and visual preference experiments described herein.

Fifteen images of fractal mirror trees were designed using some of the principles of transformation shown in Figures 2 and3

Subjects

  30 observers, ranging in age between 25 and 70 and unaware of the hypotheses of the study, participated in the experiments. All subjects had normal or corrected-to-normal visual acuity.

  FIGURE 5 FIGURE 6 FIGURE 7

  FIGURE 5Box-plots showing medians and variance of aesthetic ratings (on a scale between zero and ten) produced by 30 naive subjects in response to the 15 images from Figure4, plotted as a function of figure type.

FIGURE 6

 6 FIGURE 6Average aesthetic ratings and their standard errors, plotted for each figure type.

FIGURE 7

 7 FIGURE 7Average aesthetic ratings plotted as a function of the 15 individual images.

FIGURE 8

 8 FIGURE 8Average number of "preferred" responses and their standard errors, plotted for each figure type.

FIGURE 9

 9 FIGURE 9Total number of "preferred" responses plotted as a function of the 15 individual images.

  FIGURE 1


Marco Montemurro
email: marco.montemurro@ensam.eu

A new design paradigm for the analysis and optimisation of composite structures

Keywords: Optimisation, Anisotropy, Polar method, Composite materials, Sandwich panels, Honeycomb core, Genetic algorithm, Additive manufacturing

This work is articulated in three parts. Firstly, the Verchery's polar method [START_REF] Verchery | Les invariants des tenseurs d'ordre 4 du type de l'élasticité[END_REF][START_REF] Vannucci | Plane anisotropy by the polar method[END_REF] (a mathematical representation of the plane anisotropy based upon tensor invariants) is extended to the theoretical framework of both the First-order Shear Deformation Theory (FSDT) [START_REF] Montemurro | An extension of the polar method to the First-order Shear Deformation Theory of laminates[END_REF] and the Third-order Shear Deformation Theory (TSDT) [START_REF] Montemurro | The polar analysis of the Third-order Shear Deformation Theory of laminates[END_REF] of laminates. Concerning the polar analysis of the FSDT, the major analytical result is that the number of independent tensor invariants characterising the laminate constitutive behaviour remains unchanged when passing from the context of the Classical Laminate Theory (CLT) to that of the FSDT. On the other hand, the major analytical results of the application of the polar formalism to the TSDT of laminates are the generalisation of the concept of a quasi-homogeneous laminate as well as the definition of some new classes of laminates. Moreover, for both theories, it is proved that the elastic symmetries of the laminate shear stiffness matrices (basic and higher-order terms) depend upon those of their in-plane counterparts.

Secondly, a new design paradigm for the analysis and optimisation of composite structures consisting in a multi-scale numerical optimisation procedure that relies on the polar formalism and on the use of a special evolutionary algorithm is proposed. In particular, given a hybrid structure to be designed (according to some prescribed requirements), the proposed strategy is articulated into two distinct (but linked) problems as described here below.

1. First-level problem. The aim of this phase is the determination of the optimum shape and the optimum distribution of the material properties of the structure in order to minimise the considered objective function and to meet, simultaneously, the full set of optimisation constraints provided by the problem at hand. At this level each laminate composing the hybrid structure is modelled as an equivalent homogeneous anisotropic continuum whose behaviour at the macro-scale is described in terms of laminate polar parameters, see [START_REF] Montemurro | An extension of the polar method to the First-order Shear Deformation Theory of laminates[END_REF][START_REF] Montemurro | The polar analysis of the Third-order Shear Deformation Theory of laminates[END_REF][START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part I: homogenisation of core properties[END_REF][START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part II: the optimisation strategy[END_REF][START_REF] Montemurro | Simultaneous shape and material optimization of sandwich panels with honeycomb core for additive manufacturing[END_REF][START_REF] Montemurro | A Two-Level Procedure for the Global Optimum Design of Composite Modular Structures-Application to the Design of an Aircraft Wing. Part 1: theoretical formulation[END_REF][START_REF] Montemurro | A Two-Level Procedure for the Global Optimum Design of Composite Modular Structures-Application to the Design of an Aircraft Wing. Part 2: numerical aspects and examples[END_REF]. This level can also involve different scales (typically meso and macro scales) thus the problem must be formulated and solved by considering the full set of design variables intervening at each scale [START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part I: homogenisation of core properties[END_REF][START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part II: the optimisation strategy[END_REF][START_REF] Montemurro | Simultaneous shape and material optimization of sandwich panels with honeycomb core for additive manufacturing[END_REF]. Of course, when different scales are involved within the first-level problem a homogenisation phase (numerical or analytical) of the structure must be considered in order to determine the effective material properties of some parts of the structure that will be used at the macro-scale (which depend upon the geometric/material parameters characterising the lower scale). 2. Second-level problem. At the second level of the strategy, the goal is the determination of the optimum lay-up of the laminates composing the structure (the laminate mesoscale) meeting the optimum combination of their material and geometrical parameters provided by the first level of the strategy. At this stage, the design variables are the layer orientations and the designer can add some additional requirements, e.g. more constraints on the elastic behaviour of the laminate or the orientations of the layers can be restricted to a set of possible values, etc.

For a deeper insight in the matter (especially concerning the mathematical formulation underlying the multi-scale two-level optimisation strategy) the reader is addressed to [START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part I: homogenisation of core properties[END_REF][START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part II: the optimisation strategy[END_REF][START_REF] Montemurro | A Two-Level Procedure for the Global Optimum Design of Composite Modular Structures-Application to the Design of an Aircraft Wing. Part 1: theoretical formulation[END_REF][START_REF] Montemurro | A Two-Level Procedure for the Global Optimum Design of Composite Modular Structures-Application to the Design of an Aircraft Wing. Part 2: numerical aspects and examples[END_REF].

Finally, the effectiveness of this strategy is proved through the resolution of a real-world engineering design problem: the least-weight (multi-scale) design of a sandwich panel composed of CFRP faces and Al honeycomb core. The goal here consists in simultaneously optimising the shape of the unit cell (meso-scale) of the honeycomb core (which will be fabricated by means of an additive manufacturing technique) and the geometrical as well as the material parameters of the CFRP laminated skins (meso and macro scales). This design problem is formulated as an optimisation problem subject to constraints of different nature [START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part I: homogenisation of core properties[END_REF][START_REF] Catapano | A multi-scale approach for the optimum design of sandwich plates with honeycomb core. Part II: the optimisation strategy[END_REF][START_REF] Montemurro | Simultaneous shape and material optimization of sandwich panels with honeycomb core for additive manufacturing[END_REF]: on the positive-definiteness of the stiffness tensor of the core, on the admissible material properties of the laminated faces, on the local buckling load of the unit cell of the core, on the global buckling load of the panel and geometrical as well as manufacturability constraints linked to the fabrication process of the honeycomb core.


Mylène Campana

Jean-Paul Laumond

Ballistic motion planning

This paper addresses the motion planning problem of a jumping point-robot. Each jump consists in a ballistic motion linking two positions in contact with obstacle surfaces. A solution path is thus a sequence of parabola arcs. The originality of the approach is to consider non-sliding constraints at contact points: slipping avoidance is handled by constraining takeoff and landing velocity vectors to 3D friction cones. Furthermore the magnitude of these velocities is bounded. The ballistic motion lying in a vertical plane, we transform the 3D problem into a 2D one. We then solve the motion equations. The solution gives rise to an exact steering method computing a jump path between two contact points while respecting all constraints. The method is integrated into a standard probabilistic roadmap planner. Probabilistic completeness is proven. Simulations illustrate the performance of the approach.

I. INTRODUCTION

Geometrical motion planning is a well-known problem [START_REF] Latombe | Robot Motion Planning[END_REF]. Today, most motion planners are inspired by the random sampling seminal approaches [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF], [START_REF] Lavalle | Algorithmic and Computational Robotics: New Directions[END_REF]. They can also be adapted for systems that handle special types of paths (e.g. splinebased approach [START_REF] Lau | Kinodynamic motion planning for mobile robots using splines[END_REF]), or which embed special constraints (e.g. constrained optimization [START_REF] Zucker | CHOMP: covariant hamiltonian optimization for motion planning[END_REF]).

In this paper we consider the ballistic motion planning for a jumping robot in environments containing slippery surfaces. It is well-known that ballistic motion results in a parabola trajectory. According to the Coulomb friction law, a condition for the robot not to slide during its takeoff is that the contact force belongs to a so-called friction cone. This latter property extends to the landing phase. We consider a simple point mass robot with simplified contact dynamics: we assume that the robot is submitted to an impulse force as soon as it lands, so that the transition between landing and takeoff is instantaneous. This gives rise to a discontinuity between the contact forces and the contact velocities. Moreover we assume that the robot has limited energy resources, which limit the velocity at takeoff. The landing velocity is also constrained to avoid requiring to dissipate too much energy (and damaging the robot). These energy restrictions are realized by limiting the magnitude of the velocity vectors during the takeoff and landing phases. Constraints on the velocity vector magnitudes are named velocity constraints.

How to plan a collision-free path satisfying both sliding and velocity constraints in such a context? This is the question addressed by this paper. *This work has been supported by the project ERC Advanced Grant 340050 Actanthrope 1 {mcampana, jpl}@laas.fr CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France 2 Univ. de Toulouse, LAAS, F-31400 Toulouse, France Ballistic motion planning has been relatively little addressed. [START_REF] Raibert | Experiments in balance with a 3d one-legged hopping machine[END_REF] shows a one-legged robot hopping while keeping balance. [START_REF] Stoeter | Autonomous stair-climbing with miniature jumping robots[END_REF] makes a miniature robot jump to climb horizontal stairs. In [START_REF] Papadopoulos | On robot gymnastics planning with non-zero angular momentum[END_REF], a multi-articulated gymnast robot jumps over obstacles on a horizontal surface, while taking into account the whole-body angular momentum. In [START_REF] Lamouret | Motion Synthesis By Example[END_REF]- [START_REF] Levine | Space-time planning with parameterized locomotion controllers[END_REF] ballistic motion is considered from a character animation viewpoint. Focus is done on jump motion preparation and adaptation. The authors of [START_REF] Wensing | Development of high-span running long jumps for humanoids[END_REF] present a simulated humanoid robot that runs and jumps on a horizontal platform. The takeoff leg angle and intensity are computed to cross the large gap. [START_REF] Peng | Terrain-adaptive locomotion skills using deep reinforcement learning[END_REF] and [START_REF] Liu | Guided learning of control graphs for physics-based characters[END_REF] produce near optimal hopping motions online for quadrupeds from reinforcement based learning techniques. However, as they simplify the location of the contacts, the method cannot deal with arbitrary 3D environments. [START_REF] Pollard | Force-based motion editing for locomotion tasks[END_REF] and [START_REF] Mccann | Physics-based motion retiming[END_REF] consider how existing motions may be edited of re-timed to consider friction. Motion planning and obstacle avoidance are considered in [START_REF] Yamane | Planning and synthesizing superhero motions[END_REF]. The method computes a sequence of parabolas. It consists of tuning the parabola heights in order to reach different levels while avoiding obstacles. This paper does not consider the full dynamics of articulated avatars, but is restricted to point-robots. With respect to the state of the art, the contribution is to account for slipping prevention as well as takeoff and landing velocity limitations. Furthermore, the proposed approach applies on 3D environments and rough terrains without any restriction.

We formally state our problem in Section II. In Section III, we detail the unconstrained parabola trajectory equations. Then, we present and solve the non-sliding constraints as well as the velocity limitations in Section IV. Finally, this resolution is integrated into a motion planner (Section V) whose probabilistic completeness is proven. Simulation results are provided in Section VI.

II. PROBLEM STATEMENT

Let us consider a point-robot moving in a 3D environment. The robot begins from a starting position c s and wants to reach a goal position c g , only by performing jumps from one contact to another. Both c s and c g are assumed to be in contact with the environment. There is no distinction between ground and obstacles. The purpose of this paper is to determine a sequence of jumps, under the following assumptions:

• The robot is modeled by a point mass m of position c with respect to the origin. • The only force that applies to the robot during a jump is mg. . Three sequences of parabolas between cs and cg positions for different constraints. In the case illustrated on the right, friction cones are narrower than those on the left, so that the parabola on top is not admissible anymore, and a waypoint has to be used. In the bottommost case, the initial velocity has been limited compared to the left case, resulting in a sequence with numerous jumps.

landing to takeoff results from an impulsion. • The non-sliding constraint is modeled by a friction cone.

According to the contact model, the robot is not sliding as soon as its impulsion vector belongs to the friction cone. The direction of the impulsion vector is the same as the difference between the takeoff and the landing velocity vectors. Then, if both velocity vectors belong to the convex friction cone, so does the impulsion direction. We detail the benefit of this sufficient condition in the motion planning section. Moreover, the surface material is uniform in the environment, i.e. the non sliding constraints can be modeled everywhere by a friction cone with a constant coefficient. We denote by µ the tangent of the cone half-angle. • Takeoff and landing velocity magnitudes are bounded by the same value, so that an admissible jump path can be followed in a reversed direction. • There is no constraint on the energy balance between one jump and the next. • The robot cannot collide with the obstacles. Fig. 1 illustrates the effects of the friction and velocity constraints on the existence of parabola sequences. The following section reminds the basics of ballistic motion and details the equations of parabolas linking two points.

III. UNCONSTRAINED BALLISTIC MOTION

A. Accessible space of ballistic motion

We denote the global frame basis by (e x , e y , e z ). When Newton's second law of motion is integrated with respect to time for a ballistic shot from the c s position with a ċs initial velocity, the following robot trajectory is obtained: Let (x, y, z) T be the coordinates of c. The ballistic motion belongs to a vertical plane denoted by π θ . The orientation of the plane is given by the initial velocity components as follows:

c(t) = - g 2 t 2 e z + ċs t + c s (1)
θ = atan2( ẏs , ẋs ) ∈ [-π; π]
Considering Θ = [cos(θ) sin(θ) 0] T , we introduce the following variable changes involving the scalar product:

x θ = c.Θ, x θs = c s .Θ x θg = c g .Θ, ẋθs = ċs .Θ
Thus from (1), one can rewrite the main equations of motion determining the robot coordinates (x θ , z) T in π θ (see Fig. 2):

z = - g 2 (x θ -x θs ) 2 ẋ2 θs + żs ẋθs (x θ -x θs ) + z s (2)
ż ẋθs = -g x θ -x θs ẋ2 θs + żs ẋθs (3)
Let us denote the takeoff angle by α s = atan2( żs , ẋθs ) and the velocity value ||ċ s || by v s . Equations ( 2)-(3) highlight the two parameters α s and ẋθs that determine a parabola in π θ . For instance, Fig. 3 presents the parabola beams when v s (resp. α s ) is fixed. This can also be viewed as the accessible space of the robot performing ballistic motions.

B. Goal-oriented ballistic motion

Now we want our robot to reach the goal position c g with a jump starting from c s . Therefore, the value θ = atan2(y gy s , x gx s ) is now known. Let X θ equal x θgx θs and Z equal z gz s . Since Z is fixed, it appears that from (2), α s is the only remaining variable to compute the parabola beam leading to c g . In fact, the initial velocity ẋθs can be obtained with the following equation:

ẋθs = gX 2 θ 2(X θ tan(α s ) -Z) (4)
Equation ( 4) implies that ẋθs is only defined for top-curved parabolas, which is consistent with gravity. Non-physicallyfeasible parabolas such as down-curved ones are not considered. Therefore we impose:

atan2(Z, X θ ) < α s < π 2 (5)
An example of a goal-oriented parabola beam is presented Fig. 4. Finally, we denote a parabola starting from c s and its parameters by P s (θ, α, v).

IV. BALLISTIC MOTION WITH CONSTRAINTS

So far we have defined a beam of feasible parabolas to connect two positions. In this section, the non-sliding and velocity constraints are introduced, and the resulting reduction of the space of admissible parabola beams is detailed.

A. Non-sliding constraints 1) 2D reduction: Let us consider two points c s and c g at the contact of environment surfaces. Non-sliding constraints impose the robot to land and take off along velocity vectors that belong to 3D friction cones of apexes based on s and c g .

Since the motion has to lie in a vertical plane π θ , the problem of computing a parabola between the two 3D friction cones is reduced to a 2D problem. Corresponding 2D cones result from the intersections of the 3D cones with the plane π θ (see Fig. 5 c s and c g . Otherwise, let us denote their half-apex angles1 respectively by δ s and δ g , and their directions projected in π θ respectively by n s and n g . Note that δ s and δ g may be smaller that arctan(µ). For the 2D start cone of direction n s = (n xs , n ys , n zs ) T , let us denote by γ s the angle between the cone direction and the horizontal line:

γ s = atan2(n zs , n xs cos(θ) + n ys sin(θ))
γ g is similarly defined, respectively to the 2D goal cone. Thus the problem of slippage avoidance is reduced to the problem of finding a parabola going through the 2D cones (see Fig. 5 bottom).

2) Constraint formulation: Since the equation of a parabola starting at c s and ending at c g only depends on α s , the four constraints are just formulated relatively to α s .

For the non-sliding takeoff constraint, the inequalities on α s are immediate:

α - 1 ≤ α s ≤ α + 1 with α - 1 = γ s -δ s α + 1 = γ s + δ s
To express the three remaining constraints according to α s , (2)-( 3) are brought back to the parabola origin c s . Thus constraints are still expressed as inequalities:

α - i ≤ α s ≤ α + i , i ∈ {2..4}
For the landing cone constraint, different cases appear, depending on the accessibility of the cone. They are tackled by Algorithm 1 Resolution of the landing cone constraint.

Output: Defined constraint bounds α - 2 , α + 2 if γ g > 0 then α - g = γ g -π -δ g α + g = γ g -π + δ g if α + g < -π 2 then No solution else α - 2 = arctan( 2Z X θ -tan(α + g )) if α - g > -π 2 then α + 2 = arctan( 2Z X θ -tan(α - g )) else α + 2 not defined else α - g = γ g + π -δ g α + g = γ g + π + δ g if α + g > π 2 then No solution else α + 2 = arctan( 2Z X θ -tan(α - g )) if α + g < π 2 then α - 2 = arctan( 2Z X θ -tan(α + g )) else α - 2 not defined
Algorithm 1, which returns the constraint bounds (α - 2 , α + 2 ). Note that one of the bounds may not exist, and that the constraint may also not be satisfied.

B. Velocity constraints

Takeoff velocity limitation is expressed as v s ≤ V max . Equation (2) leads to:

gX 2 θ tan(α s ) 2 -2X θ V 2 max tan(α s ) + gX 2 θ + 2ZV 2 ≤ 0 (6) ∆ = V 4 max -2gZV 2 max -g 2 X 2 θ If ∆ < 0, (6)
has no solution. In other words, it means that the goal position is not reachable with an initial velocity satisfying the limitation. In the case where the constraint is solvable, we write:

α - 3 = (V 2 max - √ ∆)/gX θ α + 3 = (V 2 max + √ ∆)/gX θ
The same argument can be applied for the landing velocity limitation (see Fig. 6). Using (3)-(4), we can rewrite the constraint equation v f ≤ V max as:

gX 2 θ tan(α s ) 2 -(4X θ Zg + 2X θ V 2 max ) tan(α s ) + gX 2 θ + 2ZV 2 max + 4gZ 2 ≤ 0 (7) Λ = V 4 max + 2gZV 2 max -g 2 X 2 θ c s c s ċg c g ċg c g
Fig. 6. The landing velocity limitation allows to reject parabolas that have too important an impact velocity magnitude vg (right).

If Λ < 0, (7) has no solution. Otherwise, we write:

α - 4 = (V 2 max + 2gZ - √ Λ)/gX θ α + 4 = (V 2 max + 2gZ + √ Λ)/gX θ
A symmetry property of the parabola implies that, given one parabola from c s to c g determined by ċs , the same parabola can be obtained from c g to c s with -ċ g as initial velocity. In the latter case, the contact velocity becomes -ċ s . We use this property to apply the same bound V max for the takeoff and landing velocities. Thus the parabola can be traveled both ways without violating the velocity limitation constraints.

C. Constraints collection and solution existence

The domains where constraints are satisfied are convex. Thus, we intersect these domains to determine if an interval ]α - s ; α + s [ of α s values complying with all the constraints exists. The interval bounds are given by: [START_REF] Zucker | CHOMP: covariant hamiltonian optimization for motion planning[END_REF] has to be simultaneously satisfied to consider an admissible parabola. Fig. 7 presents an illustration of this constraint intersection. Constraint bounds (α - i , α + i ) i∈{1..4} are used to plot parabolas, representing the domains where constraints are satisfied. The intersection of these domains leads to the set of possible solutions.

α - s = max(α - 1 , α - 2 , α - 3 , α - 4 ) α + s = min(α + 1 , α + 2 , α + 3 , α + 4 ) Note that
Finally, the existence of an admissible jump between two points is guaranteed as soon as:

• Neither of the intersections between both friction cone and π θ is reduced to a point. • (α - s , α + s ) are defined and α - s ≤ α + s . The two conditions are necessary and sufficient. The interval ]α - s ; α + s [ gives a simple parametrization of the solution beam. Choosing α s as the average 0.5(α - s + α + s ) allows to optimize the distance to the constraints, e.g. to be far from the limits of the friction cones, and so far from sliding. Fig. 8 illustrates the constraint effects on a simple example. Topological Property: Let us consider an admissible parabola P s (θ, α, v) starting at c s and ending at c g . There exists a neighborhood N s (resp. N g ) of c s (resp. c g ) such that any pair of points (c * s ,c * g ) belonging to N s × N g can be linked by an admissible parabola.

3.

1.

2.

Fig. 7. Illustration of the constraints on a practical example: each constraint bound is used as αs and represents a bold parabola. Between these bounds, the constraint is satisfied, out of them not. The constraint intersection is given by the bounds (α - s , α + s ) and illustrated by the gray zone: blue parabolas belonging to it are admissible solutions to the problem.

Proof: Let us consider the parabola family {P s (θ + e 1 , α + e 2 , v + e 3 ), e i ∈] -, [} starting at c s . The function giving the three parabola parameters from the three coordinates of c g is an homeomorphism. Therefore such a family spans a neighborhood of c g . Let c * g be a point of this neighborhood and P s (θ+e * 1 , α+e * 2 , v+e * 3 ) the parabola from c s to c * g . c * g may be chosen close enough from c g to guarantee that e * is small enough, and then P s (θ+e * 1 , α+e * 2 , v+e * 3 ) is admissible. Because the construction is symmetric, let us consider the same parabola as starting at c * g and ending at We a new parametrization of the same parabola, i.e. P g (θ * , α * , v * ). By using the same argument as above, the parabola family {P g (θ * + e 1 , α * + e 2 , v * + e 3 ), e ∈] -, [} starting at c * g spans a neighborhood of c s . The property holds for any point c * g sufficiently close to c g . Therefore, there exists a neighborhood N s (resp. N g ) of c s (resp. c g ) such that any pair of points (c * s ,c * g ) belonging to N s × N g can be linked by an admissible parabola.

V. MOTION PLANNING

To find a sequence of parabola arcs between an initial position c s and a final one c g , we use a simple PRM-based probabilistic roadmap planner [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF] (see Algorithm 2). Note that the roadmap may contain cycles. The planner builds a roadmap in the 3D space by randomly sampling contact positions similarly to [START_REF] Amato | A randomized roadmap method for path and manipulation planning[END_REF] (RANDOMSAMPLE), and by linking them (STEER) with admissible collision-free parabola arcs. The roadmap construction is over as soon as either a path linking c s and c g is found (ARECONNECTED), or computation time is over. Then, the function FINDSHORTESTPATH explores the roadmap to return the shortest path sequence, in terms of sum of parabola lengths.

Note that the sufficient non-slipping condition reduces the dimensionality of the motion planning problem, because it removes the relationship between the entering velocity and the exiting velocity of a node. With a classical kynodynamic planner [START_REF] Kunz | Probabilistically complete kinodynamic planning for robot manipulators with acceleration limits[END_REF], to verify whether a trajectory can be connected with another one, it is required to extend the state space with the velocities and so it doubles the dimensionality of the problem. In our case, this is only required to verify whether there exists a velocity vector belonging to the cone each time we want to add a new path.

The function BEAM is described in Algorithm 3. It computes the interval of takeoff angles that generate constrained parabolas to link c s and c g . The algorithm starts by calculating each cone and plane π θ intersection, and continues only if both intersections are not reduced to the cone apexes. Then, takeoff angle bounds related to constraints are computed as in Section IV. A boolean f ail conveys the feasibility of constraints, i.e. if one constraint cannot be satisfied, f ail is set to true. At this stage, an admissible parabola exists if the global constraint bounds verify α - s ≤ α + s . Then the steering method STEER detailed in Algorithm 4 selects a takeoff angle α s and tests the corresponding parabola for collisions. If the parabola is not collisionfree (HASCOLLISIONS), then we select a new parabola α s by dichotomy on the interval ]α - s ; α + s [ until the resolution Algorithm 2 Probabilistic roadmap planner for ballistic motion planning.

Input: environment, c s , c g , µ, V max Output: Collision-free solution sequence to problem path ←STEER(c s , c g ) f inished ← ARECONNECTED(c s , c g ) while not(f inished) do c random ← RANDOMSAMPLE() ADDTOROADMAP(c random ) for c node ∈ Roadmap do path ←STEER(c node , c random ) ADDTOROADMAP(path) end for f inished ← ARECONNECTED(c s , c g ) return sequence ← FINDSHORTESTPATH() Algorithm 3 BEAM(c s , c g ): Computes the parabola beam represented by the takeoff angle interval ]α - s ; α + s [. Input: c s , c g , µ, V max Output: Interval of takeoff angles I beam cone 2D s ← COMPUTEINTERSECTION(cone 3D s , π θ ) cone 2D g ← COMPUTEINTERSECTION(cone 3D g , π θ ) if ISREDUCED(cone 2D s ) or ISREDUCED(cone 2D g ) then return I beam ← ∅ (α - i α + i , f ail) i∈{1..4} ← COMPUTECONSTRAINTS() if f ail = true then return I beam ← ∅ α - s ← max(α - 1 , α - 2 , α - 3 , α - 4 ) α + s ← min(α + 1 , α + 2 , α + 3 , α + 4 ) return I beam ←]α - s ; α + s [
Algorithm 4 STEER(c s , c g ): Steering method based on a constrained parabola. Returns a collision-free path linking c s and c g . Otherwise, returns an empty path. Input: c s , c g , µ, V max , n limit Output:

Collision-free parabola path path ]α - s ; α + s [← I beam n ← 1 I beam ← BEAM(c s , c g ) if ISEMPTY(I beam ) then return path ← emptyP ath else α s ← 0.5(α - s + α + s ) path ← COMPUTEPARABOLA(c s , c g , α s ) while HASCOLLISIONS(path) and n < n limit do α s ← DICHOTOMY(]α - s ; α + s [, n) path ← COMPUTEPARABOLA(c s , c g , α s ) n ← n + 1
if HASCOLLISIONS(path) then path ← emptyP ath return path threshold n limit is reached. In the worst case, the DI-CHOTOMY function allows to span the almost entire parabola beam. Doing so, the algorithm is probabilistically complete as proven by the following property. Convergence Property: Let us consider a sequence of collision-free ballistic jumps between two points c s and c g in a given environment. Let us assume that the entire path is at a distance of about from the obstacles. Then the probability for Algorithm 2 to find a sequence of collision-free ballistic jumps between c s and c g converges to 1 when running time tends to infinity.

Proof: The property is a direct consequence of the topological property exposed in Section IV. Indeed, let us consider a sequence of collision-free ballistic jumps between two points c s and c g . Let c i and c i+1 two consecutive points in the sequence. c i and c i+1 are linked by a collision-free parabola P i . From the topological property, there are two neighborhoods N i (resp. N i+1 ) of c i (resp. c i+1 ) such that any pair of points (c * i ,c * i+1 ) belonging to N i × N i+1 can be linked by an admissible parabola P * i . Because Algorithm 2 tends to sample the environment uniformly, the probability of sampling two points in N i and N i+1 respectively tends to 1 when time tends to infinity. N i and N i+1 can be arbitrarily small. As a consequence, P * i can be arbitrarily close to P i . Because P i is away about from the obstacles, P * i is guaranteed to be collision-free.

VI. RESULTS

The ballistic motion planner was tested in 3D environments containing slippery surfaces, using the software Humanoid Path Planner2 . Graphical renderings were done using Blender 2.7. In all described examples, the parameter n limit from Algorithm 4 was set to 6.

We planned sequences of parabolas for a point-robot in three environments. For each example, we considered weak and strong constraints. The results are shown in Fig. 9, 10 and 11. Movies of the trajectories are available in the companion video 3 . Solutions under strong constraints tend to increase the number of waypoints. It is not only a consequence of the velocity limitation that forces to reach closer positions (see also Fig. 8 bottom), but it is also a result of the cone narrowness. In fact, as it is shown in Fig. 8 top, narrow cones provide parabolas with greater heights, more likely to produce collisions or to exceed the environment bounds.

Table I presents the average performance results of the ballistic motion planner run on the Fig. 10 benchmark. The velocity limitation is less restrictive in terms of computation time than the cone coefficient. However, the velocity limitation cannot be reduced without endangering the existence of a solution. In fact, the robot has to reach other platforms in order to find a solution path sequence. Benchmarking was done on a PC with 15.8 GB of main memory and using one core of an Intel Xeon E3-1240 processor running at 3.4 GHz

VII. CONCLUSION

We presented a method that analytically computes a nonsliding jump for a point-robot, resulting in a parabola going from one friction cone to another. The method has been implemented as a steering method in a probabilistic-roadmap motion planner in order to determine a sequence of jumps between given start and goal positions.

We can easily extend the parabola-based steering method to devise a diffusing type of probabilistic planner, such as RRT [START_REF] Lavalle | Algorithmic and Computational Robotics: New Directions[END_REF]. Besides, our algorithm is the first stage of a more ambitious challenge. Our final purpose is to address dynamic motion planning for digital artifacts. The solution which we provide can be used to compute the center of mass path when the artifact is jumping. Now, it remains to consider more realistic models of contacts (e.g. multiple contacts involving feet and hands) and impacts (e.g. including energy balance). Moreover, the steering method we consider in the motion planner is assumed to be symmetric. This assumption is not realistic. Indeed, for a given parabola, the energy required to overcome the gravity effect from a position is greater than the energy to dissipate landing at the same position. The extension of the motion planner to more realistic energetic models is the purpose of future developments.

c s robot c g c s c g c s c g Fig. 1

 g1 Fig.1. Three sequences of parabolas between cs and cg positions for different constraints. In the case illustrated on the right, friction cones are narrower than those on the left, so that the parabola on top is not admissible anymore, and a waypoint has to be used. In the bottommost case, the initial velocity has been limited compared to the left case, resulting in a sequence with numerous jumps.

Fig. 2 .Fig. 3 .

 23 Fig.2.The parabola always belongs to the plane π θ defined by (cs; ex θ ; ez), where ex θ = cos(θ)ex + sin(θ)ey.

  Fig. 4. Physically-feasible parabolas linking cs and cg, for multiple values of αs in [0.91; 1.27] rad.

Fig. 5 .

 5 Fig. 5. (Top) Representation of the intersection between π θ and two 3D cones. (Bottom) 2D cones resulting of the intersection and an example of parabola belonging to both cones.

Fig. 8 .

 8 Fig. 8. Three parabola examples linking cs to cg with different constraints. Large (blue) and narrow (violet) friction cones are considered, forcing the solution parabola to be adapted. With a large velocity limitation, cg can be directly reached (blue). Otherwise, an intermediate position has to be considered (red).

Fig. 9 .

 9 Fig. 9.Full path planning results in an environment containing two windows to cross from right to left. The red solution is more constrained, so it results in a longer sequence of parabolas. Number of triangles: 47 733.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Full path planning results in an environment containing platforms and a chimney. The blue path is constrained by large cones, the red path by narrow cones. Reducing µ prevents the creation of a parabola linking two low platforms with the same inclination. Number of triangles: 696.

Detailed computation of δs and δg is presented in the appendix file.

http://humanoid-path-planner.github.io/hpp-doc/index.html

https://youtu.be/vv K7HqANmk