Thibault Louis
email: thibault.louis@univ-grenoble-alpes.fr

Jocelyne Troccaz
email: jocelyne.troccaz@univ-grenoble-alpes.fr

Amélie Rochet-Capellan
email: amelie.rochet-capellan@gipsa-lab.grenoble-inp.fr

François Bérard
email: francois.berard@univ-grenoble-alpes.fr

Is it Real? Measuring the Effect of Resolution, Latency, Frame rate and Jitter on the Presence of Virtual Entities

Keywords: Presence, HPCD, User Study, Spatial Augmented Reality

The feeling of presence of virtual entities is an important ob-jective in virtual reality, teleconferencing, augmented reality, exposure therapy and video games. Presence creates emotional involvement and supports intuitive and efficient interactions. As a feeling, presence is mostly measured via subjective ques-tionnaire, but its validity is disputed. We introduce a new method to measure the contribution of several technical pa-rameters toward presence. Its robustness stems from asking participant to rank contrasts rather than asking absolute val-ues, and from the statistical analysis of repeated answers. We implemented this method in a user study where virtual entities were created with a handheld perspective corrected display. We evaluated the impact on two virtual entities' presence of four important parameters of digital visual stimuli: resolu-tion, latency, frame rate and jitter. Results suggest that jitter and frame rate are critical for presence but not latency, and resolution depends on the explored entity.

INTRODUCTION

Presence is the sensation felt when exposed to immersive reali-ties using high fidelity devices. It is sought in many application fields like Virtual Reality (VR), teleconferencing, Augmented Reality (AR), exposure therapy and video games as it allows intuitive and efficient interaction and emotional involvement. In this paper, we refer to reality (either physical or virtual) as a complete autonomous environment governed by physicallaws, as well as all the objects, living and social creatures that evolves and interact with one another in the environment. We use the term entities to regroup all kind of actors evolving in a reality (i.e. objects, creatures or peoples). As human beings, we evolve in the physical reality. In order to interact with other physical entities, our brain analyzes the data perceived by our sensory system using previous knowledge of the real-ity's physical laws. Our lifetime interacting experiences allow us to apprehend new entities that we never saw before. From the texture, reflections and shape of an object, we can deduce its matter, weight and purpose.

More than fifty years ago [START_REF] Sutherland | The Ultimate Display[END_REF], research on virtual reality began to address the creation of other realities with their own entities, rules and interaction metaphors. Within VRs, people can interact with entities, stories and environments that do not or cannot exist in the physical reality. With high fidelity VR systems that reproduces the laws, visual stimuli and interactive potentialities of the physical reality, users can be immersed into other realities and interact with virtual entities intuitively, benefiting of their own lifetime experiences. When most of the physical reality is adequate, however, it may seem wasteful to reproduce it in a virtual reality only to add a nonphysical entity. A more sensible approach is to create an augmented reality were only the virtual entity is immersed in the physical world. Both VRs and ARs share the same objective of offering intuitive interaction with the transfer of skills and knowledge acquired in the physical reality.

Ultimately, with either high fidelity VR or AR, users will not be able to tell if the entity they interact with is physical or virtual. When this happens, we qualify the virtual entity as entirely present for the user. The more present an entity is, the more difficult it is for the user to identify whether the entity is a virtual or a physical one. Various definitions of presence are found in the literature, each one being specific to a given context of use.

Presence is considered beneficial and sought after in several domains from video games to professional immersive train-ing through curing phobia with exposure therapy. Interacting with a very present object is usually intuitive; which reduces learning time and enhances training acceptability. When using virtual simulations to train for physical skills (e.g. flight simuators), it is crucial that the virtual reproduction of the physical reality is as faithful as possible, i.e. very present, in order to maximize the transfer of learning from virtual to physical. In VR games, players want to be immersed into the game's world; which requires a strong presence of its entities.

Rendering a scene with a high level of presence require to produce credible sensory feedbacks coupled with natural in-teraction. To date, hardware capable of such feedbacks are emerging but expensive, and are still struggling with techni-cal barriers. As presence is a subjective feeling, researchers struggle to find a direct way to measure it, and many studies rely on questionnaires to do so. Empirical works that study the impact of devices input and output performances on presence are scarce and hard to compare given the lack of objective measurement.

Enhancing an entity's presence can be achieved by acting at several abstraction levels, from devices input/output perfor-mances to the scenario of use. In this study, we focus on the lowest abstraction level: the device technical performances. A pixelated rendering, for instance, should yield less presence than a high-resolution rendering that saturate human's visual acuity. All technical parameters do not have the same impact on presence, and literature is lacking in experimental work on the topic.

In this paper, we propose a new method to measure the contri-bution of various parameters towards the perceived presence of a scene. Our method relies on a statistical repetition of comparisons between 2 conditions rather than on a direct questionnaire on the feeling of presence. We argue that the method yields a more objective measurement of presence than questionnaires. Our method might enhance comparison of future studies and help to understand the factors impacting the presence of virtual scenes.

The method was implemented in a user study that questions the impact of 4 major parameters influencing the visual percep-tion of a scene: the display's pixel Resolution, the end-to-end Latency, the display Frame rate and the motion capture Jitter (RLFJ). The interactive system tested was a handheld per-spective corrected display (HPCD). This study provided first insights about the impact of these parameters on presence.

RELATED WORK

We organize this review of the related work around four topics: the various definitions of the concept of presence, its appli-cations, the means to increase presence, and how to measure it.

Literature definitions of presence

Virtual Reality

Presence was first introduced in the VR domain as a psy-chological sense of "being there" in the virtual environment (Slater et al. [29]). It described the human psychological state when exposed to an immersive VR system. Immersive VR systems aim at entirely replacing users' physical environment with a virtual environment. To do so, VR systems must, for as many of users' sensory receptor as possible, either provide high-resolution stimuli that saturate the receptors, or silent the receptors.

Remote collaboration

In teleconferencing and telecooperation, the term telepres-ence refer to the feeling of being physically there in a remote workspace [START_REF] Thomas B Sheridan | Musings on telepresence and virtual presence[END_REF]. In this case, users want to feel as if they were present in a remote physical reality. As the focus is essentially on collaboration, the environment becomes superfluous: only the copresence of users with their remote coworkers is essen-tial [START_REF] Schroeder | Social interaction in virtual environments: Key issues, common themes, and a framework for research[END_REF]. Here, the focus is on presence as a feeling of relation to social individuals, not to an entire reality. The realism of the coworkers' avatars has been shown to positively impact the feeling of copresence as well as the understanding of non-verbal communication. Bailenson et al. tested participants feeling of copresence, verbal and nonverbal disclosure, and emotion recognition of their interlocutor in a teleconferencing communication depending on the realism of the interlocu-tor avatar [START_REF] Bailenson | The effect of behavioral realism and form realism of real-time avatar faces on verbal disclosure, nonverbal disclosure, emotion recognition, and copresence in dyadic interaction[END_REF]. They tested three conditions: no avatar, an impersonal polygonal avatar that reproduces the interlocutor facial expressions, and a videoconference (i.e. a high quality photo-realistic avatar). They reported a negative impact of the polygonal avatar on copresence and a reduction of nonverbal disclosure with both avatar representations.

Augmented Reality

AR transports virtual objects into the user physical reality, in opposition to VR that aims to transport the user out of the physical reality. One important advantage of AR is that appli-cations do not have to reproduce the surrounding environment. However, the realism of the virtual object has to be very high for the illusion that it actually exists in the physical environ-ment to work. To date, realism is limited by several technical issues listed and categorized by Kruijff et al. [START_REF] Ernst Kruijff | Perceptual issues in augmented reality revisited[END_REF], including: occlusion handling, place stability, lightning and shadowing, accommodation and limited field of view. Chen et al. extended the notion of presence defined in VR to apply it in AR. They considered the presence of the virtual entities in the physical reality instead of the user's presence in the virtual reality [START_REF] Chen | Exploring the Effect of Presence in an ARbased Learning Environment[END_REF]. They measured AR presence by adapting the common Witmer and Singer's Presence Questionnaire [START_REF] Witmer | Measuring presence in virtual environments: A presence questionnaire[END_REF] to the AR context. Here, the concept of presence relates to the feeling, for users, that the virtual object is with them in their physical reality.

Applications of presence

HCI performances

With a high level of presence, a virtual entity is perceived as a physical entity, favoring the transfer of skills that were learnt in the physical reality to the virtual environment. In-deed, Bérard et al. used the observation of a transfer of skill between physical and virtual realities as a definition of a "natural" human-computer user interaction [START_REF] Bérard | The Transfer of Learning as HCI Similarity: Towards an Objective Assessment of the Sensory-Motor Basis of Naturalness[END_REF]. This transfer of skill makes the interaction more intuitive (i.e. reducing learning time) and more efficient. Jacob et al. proposed a framework to regroup recent interaction systems that tend to reduce the gap between a user's intention and the means to execute the cor-responding interaction by getting closer to user's habits [START_REF] Robert | Reality-based interaction: a framework for post-WIMP interfaces[END_REF]. They called this framework Reality-Based Interaction, and claim that such emerging systems get their inspirations from the physical reality.

Emotional responses

Enhancing presence fosters user's involvement with a virtual experience; which, in turn, can lead to similar emotional re-actions that they would have in a physical context. In a 2001 review, Schuemie et al. pointed at several studies in VR that show a correlation between self-reported presence and emo-tional responses such as fear of heights and public speaking anxiety [START_REF] Martijn | Research on presence in virtual reality: A survey[END_REF]. More recently, Diemer et al. highlighted a rela-tion between presence and arousal emotions such as fear and excitement [START_REF] Diemer | The impact of perception and presence on emotional reactions: a review of research in virtual reality[END_REF]: they reviewing more than 30 studies of the past twenty years; which consistently reported correlations between presence and emotional experience. This literature shows that high presence in immersive VR environment tends to increase emotional responses.

Generating emotions from VR experience has an important health application: exposure therapy to cure phobias. Parsons et al. reported a meta-review of numerous VR exposure ther-apy studies [START_REF] Parsons | Affective outcomes of virtual reality exposure therapy for anxiety and specific phobias: A meta-analysis[END_REF]. They quoted that in vivo exposure therapy has shown greater efficacy than imaginary exposure, such as hypnosis therapy, in the treatment of specific phobias. This meta-analysis suggests that VR exposure therapy is effective in reducing patient anxiety. Price et al. analyzed clinical VR exposure therapy followed by 36 patients suffering from agoraphobia or fear of flying [START_REF] Price | The role of presence in virtual reality exposure therapy[END_REF]. They found correlations between reported presence and phobic anxiety. They conclude that feeling present in the VR environment seems necessary for the success of the exposure therapy but may not be sufficient. Those findings suggests that patients experiencing a high level of presence during VR exposure therapies are able to feel physically exposed to their phobia, which is a crucial factor for the therapy to succeed. Exposure therapy was also implemented in AR in cases related to the phobia of small animals. According to Wrzesien et al. the proximity of the patient with the stimuli, and especially the hands, is of prime importance in the therapy [START_REF] Wrzesien | How technology influences the therapeutic process: a comparative field evaluation of augmented reality and in vivo exposure therapy for phobia of small animals[END_REF]. Creating a motion-tracked avatar of the user's hands that is realistic enough to allow great presence is a very difficult challenge in VR. The AR approach eliminates this difficulty, as users perceive their actual arms and hands. In their study, Wrzesien et al. tested the response of 12 patients suffering from small animal phobia to either an AR or an in vivo exposure therapy. Results indicated compa-rable reduction of phobia anxiety for patients of both groups after the treatment, supporting the efficiency of Augmented Reality as a treatment.

Learning environment

Chen et al. studied the effect of presence experienced in two kind of AR-based learning environment (head-mounted dis-play versus webcam display) [START_REF] Chen | Exploring the Effect of Presence in an ARbased Learning Environment[END_REF]. In a lesson introducing the concept of protein structure, they tested a class of 58 university students enrolled in organic chemistry class in a between sub-jects design. Results suggested that students that experienced a high level of presence endured lower cognitive load when interacting with the AR system. Furthermore, the authors reported a correlation between presence and involvement in the course.

Video games

Traditional HCI performance metrics do not apply to video games as players look for different rewards: traditional HCI usually aim at improving task accomplishment performance while games aim at creating emotions and challenges for users. The flow-channel model is frequently used to evaluate the quality of video games. This concept was first introduced by Csikszentmihalyi in 1975 [START_REF] Csikszentmihalyi | Beyond boredom and anxiety: Experiencing flow in work and play[END_REF]. An optimal state of flow occurs in a situation were skills and challenges are balanced. The theory provides a 70-items questionnaire to analyze players' subjective feedbacks. Takatalo et al. applied the model to evaluate two popular first-person shooter video games based on the answer from more than a hundred expert gamers. They supported the importance of presence as a prerequisite that fosters an optimal state of flow [START_REF] Takatalo | Presence, Involvement, and Flow in Digital Games[END_REF].

How to achieve presence

High quality sensory feedbacks

In the VR research field, presence is the human response to an immersive virtual environment: the more the system is immersive, the more its users feel presence. Rendering high quality sensory feedbacks provides better immersion; which, in turn, is likely to enhance presence. However, the quality of a sensory feedback depends on many factors that are not com-parable. It is thus difficult to predict which factor improvement will have the largest effect on immersion, and thus presence. The visual feedback quality, for example, depends on many factors as listed by Slater [START_REF] Slater | A note on presence terminology[END_REF]: display resolution, field of view, frame rate, implementation of stereo, mesh resolution of the displayed entity, system latency and motion tracking precision and stability. In addition, Slater mentioned that the consistency between the various sensory feedbacks is mandatory to allow presence. For instance presence is hindered if a big metallic cube has a perfect visual feedback but users feel no weight for the cube. This, incidentally, provides evidence that presence is task-dependent: if this same cube were only to be observed at a distance, its presence would not be reduced by its lack of weight. Aiming to perfect presence for complex scenes may require very high quality visual feedbacks, imperceptible latency, full body interaction with haptic feedbacks, and so on. All these challenges have a cost and are constrained by the available technology. In practice, in it important to inform about the effect on presence of each of these parameters in order to chose the best trade-off.

Preeminence of the visual feedback

Cummings et al. reported a large meta-analysis on the effect of various parameters on presence. [START_REF] Cummings | How immersive is enough? A meta-analysis of the effect of immersive technology on user presence[END_REF]. To perform the analysis, they normalized the effect size for all the parameters tested in the reviewed studies. The main parameters were the update rate, the "tracking level" defined as the number of tracked degrees of freedom, the field of view, the image quality, the stereoscopy, and the use of sound. They reported a strong effect on presence of the update rate and the tracking level. The lack of sound and "image quality" was found to have a lower impact on presence. While this survey is quite extensive, its results are based on disparate studies involving tasks and experimental contexts that differ across studies. As such, it is not as detailed as in a single controlled user study focused on comparing the effect of each parameter. The low impact of sound is consistent with the visual capture effect: a tendency of the human brain to trust visual information when multimodal information conflicts [START_REF] Mateeff | Dynamic visual capture: apparent auditory motion induced by a moving visual target[END_REF]. A well-known example of visual capture is the ventriloquism effect: it produces the illusion to ear the dummy's voice because its mouth is moving, although the sound actually comes from the ventriloquist. The visual capture effect stresses the importance of the visual feedback and motivated our choice of tested parameters in the present study.

Plausibility

At a higher level of abstraction, one must consider the plau-sibility of the scenario presented to the user. Slater defined the plausibility illusion as "the illusion that what is apparently happening is really happening" [START_REF] Slater | Place illusion and plausibility can lead to realistic behaviour in immersive virtual environments[END_REF]. In VR, the situation in which the users are immersed must be credible for them to feel totally present. I.e. immersing participants into a room that looks alike the physical room that are in is more likely to favor great presence than immersing them into a wild jungle scene. In AR, a virtual dragon is less likely to be perceived as present than a virtual butterfly. When interacting with virtual humans, the way the virtual entity will look at the user and answer questions is crucial to avoid breaking the presence. In addition, according to Diemer et al., VR scenarios that engage emotions tend to increase presence [START_REF] Diemer | The impact of perception and presence on emotional reactions: a review of research in virtual reality[END_REF].

HPCD: a promising approach

Introduced by Stavness et al. [START_REF] Stavness | pCubee: a perspective-corrected handheld cubic display[END_REF] and recently improved by Berard et al. [START_REF] Bérard | The Object Inside: Assessing 3D Examination with a Spherical Handheld Perspective-Corrected Display[END_REF], the Handheld Perspective Corrected Display (HPCD) approach seems to be particularly suitable to create a strong feeling of presence. HPCDs render 3D content with a perspective projection that depends on the viewpoint of a user. This can creates the illusion that the virtual entity is inside the manipulable display, as if the user was holding a physical transparent object with a physical entity inside. HPCDs are closer to AR than to VR in the sense that they create the illusion of presence of a virtual entity in the surrounding of the user rather than immersing the user in a virtual environment. They may not be called AR displays, however, in the sense that the virtual entity appears to reside in the display rather than in the general surrounding of the user. HPCD present several benefits to foster presence: as in AR, users are not cut from their physical environment; which does not have to be reproduced digitally. The display itself has a credible meaning in the physical reality as a transparent container. The display being physical, it has natural passive haptic feedback making users understand that they cannot reach inside to touch the virtual entities. Finally, as long as the weight of the display matches that of the virtual entity, the sense of touch is credibly rendered without any implementation effort.

In summary, the HPCD approach solves important issues of consistency between sensory feedbacks with no particular effort while avoiding the VR struggle to create a faithful avatar of users' body. Displaying virtual entities with a high level of presence seems feasible, and mainly depends on the quality of the visual stimuli created by the device. This motivated the choice of this approach in the current study.

Measuring presence

In a survey of VR literature related to presence, Schuemie et al. analyzed the various methods used to measure pres-ence [START_REF] Martijn | Research on presence in virtual reality: A survey[END_REF]. In an overwhelming majority of studies, presence was evaluated with subjective questionnaires. As presence is a subjective notion by definition, a self-evaluation makes sense. Echoing the diversity of definitions, a lot of questionnaires have been used to measure presence. The most commonly used are the Slater-Usoh-Steed Questionnaire [START_REF] Slater | Depth of presence in virtual environments[END_REF], the Wit-mer and Singer's Presence Questionnaire [START_REF] Witmer | Measuring presence in virtual environments: A presence questionnaire[END_REF], and the ITC Sense of Presence Inventory [START_REF] Lessiter | A cross-media presence questionnaire: The ITC-Sense of Presence Inventory[END_REF].

Objective measurement methods for presence were only ex-plored in a few studies. Slater et al. proposed to measure how the users prioritize cues when virtual and real cues are conflicting [START_REF] Slater | Taking steps: the influence of a walking technique on presence in virtual reality[END_REF]. They implemented this method by immersing participants in a virtual replication of the experimental room where a radio was present. When immersed, the physical ra-dio was turned on and secretly moved while the virtual radio stayed still. Participants were then asked to point at the ra-dio. The results suggested a correlation between self-reported presence using the Slater-Usoh-Steed questionnaire and the objective measurement. Another approach is to record skin conductance as several studies noticed a correlation between presence and skin conductance when dealing with arousal emotions (like phobias) [START_REF] Diemer | The impact of perception and presence on emotional reactions: a review of research in virtual reality[END_REF]. However, skin conductance is known to be a direct measure of stress, not presence. Hence it can only be applied as an indirect metric for presence in specific contexts where an induced stress depends on a high level of presence, and such method is quite intrusive.

Given the subjective nature of presence and the lack of a re-liable objective metric for presence, the consensus is to use self-reported questionnaire. A recent survey provided an evi-dence of this consensus: Cummings et al. reviewed more than 80 studies that analyzed the effect of immersive technology on presence [START_REF] Cummings | How immersive is enough? A meta-analysis of the effect of immersive technology on user presence[END_REF]. In a concern for results comparisons, they chose to reject studies that did not evaluate presence through questionnaires. However, self-reported presence does not achieve unanimity. Slater advanced an important argument against the validity of questionnaires on presence. In everyday life, presence is a fact. It is where we are, and we do not question whereas our surrounding environment is coherent in response to our actions as it indubitably is. As we never get to evaluate presence, it is hard to believe that we could grade the level of presence of any virtual situation in an absolute but yet undefined scale [START_REF] Slater | How colorful was your day? Why questionnaires cannot assess presence in virtual environments[END_REF]. In their recent survey of presence, Skarbez et al. [START_REF] Skarbez | A survey of presence and related concepts[END_REF] inves-tigated methods to measure presence that did not implicate subjective questionnaires that "add complexity to presence research". They presented "behavioral methods" which analyze how participant behave when confronted to a given scenario. As objective measures, these methods address the major shortcomings of questionnaires. However, they usually require additional specific elements to trigger the evaluated behavior that depends on the scenario. As such, they are unsuited for generalization.

Skarbez et al. also presented "psychophysical methods" as methods meant to evaluate the relative importance of different aspects of a virtual experience on presence. Those novels methods have been used in VR to evaluate the impact of some immersion and scenario coherence parameters on participant's self-reported presence. Bergstrom et al. implemented such a method to evaluate the contribution of four parameters of a virtual string quartet performance on the reported plausi-bility [START_REF] Bergström | The plausibility of a string quartet performance in virtual reality[END_REF]. After experiencing the performance with optimal parameters, participants were exposed to a low level of fidelity and were asked to change parameters to maximize plausibility while minimizing the number of parameter change. Partici-pants enhanced the gaze and the environmental sound first, suggesting the importance of these two features to enhance the performance plausibility. Psychophysical methods seems promising for studying different factors of virtual experience and their relative effects on presence.

A NEW METHOD TO EVALUATE PRESENCE

On the one hand, self-reported questionnaire are commonly used but the difficulty to rate presence on an absolute scale yields large inter-participant variability that hides small ef-fects. Even for a single participant, it is difficult to estimate the absolute distance between two experiences on the scale of presence. In addition, questions are usually asked only once in subjective questionnaire. This does not support the com-putation of basic statistics (i.e. means, spread) that improve the precision of the measure and inform about its robustness. On the other hand, a direct measurement of the presence felt by participants, such as using bio-signals, seems illusory, as presence is a subjective feeling of high level of abstraction. We introduce a new approach founded on the following observation: while grading presence on an absolute scale is difficult, ranking two immediate experiences in terms of the presence felt is much easier. As a parallel, recognizing the pitch of a single note requires a rare absolute ear, but given two music notes most people are able to identify the higher one.

Our approach has been inspired by the just noticeable dif-ference (JND) protocol used in recent HCI research to mea-sure the smallest perceivable system's latency [START_REF] Ng | Designing for low-latency direct-touch input[END_REF]. The JND protocol consists in presenting pairs of stimulus and asking participants to rank them, for example by choosing the best one, or the lowest one. For each correct answer, the difference between the stimuli is slightly reduced. It is greatly enlarged in case of wrong answer. This occurs when the two stimuli are too closed and the participant cannot perceive the difference. Changes in the stimuli and order of presentation are hidden from participants so that their answers are not influenced by the evolution of the parameters. This protocol robustly con-verges to the smallest perceivable difference for the participant. Ng et al. always used the lowest possible latency, i.e. 1ms, as one of the stimulus in the pair. Assuming that 1ms was below the absolute threshold or perception for all participants, they changed the purpose of the JND protocol from measur-ing a smallest perceivable difference between two latencies to measuring an absolute threshold of perception. The JND protocol can be seen as a way to make an objective measure of a subjective question, e.g. "what is the smallest system latency that you can perceive?".

The JND protocol as implemented by Ng et al. is not directly applicable to our aim. We are interested by the relative effect of various heterogeneous parameters on presence, but the JND is used to accurately find a threshold on a single parameter. Another main obstacle is that a system that creates the perfect presence does not exist. The physical world is not a candidate as its parameters such as latency or resolution cannot be re-duced in a way that is unnoticeable to participants. However, we keep the principles of a repetition of many comparisons between pairs of stimulus; which parameters are unknown to the participants.

The main principles of our approach is thus to expose par-ticipants to two variant of a virtual experience, that we call representations. We ask them which of the two representations generates the strongest feeling of presence. To facilitate such comparison, participants can switch at will between the two representations before giving their answer. A single compari-son only yields a binary measure. However, we arrange for a comparison to be quick: in the order of 10s. This way, we can ask for many comparisons where we control which parameter is altered in each representation, and to which level, yielding a finer measure of the relative effect of pairs of parameters. The differences between representations are not explained so that participants can only rely on their feelings to make the choice. In addition, the same comparison is requested several times during a participant's experimental session. This improves the precision of the measure by allowing the computation of a mean. It also provides an estimate of the robustness of the measure by exposing the variability of a participant's answers to the same comparisons.

Every representation corresponds to one of the experimental condition: each representation is rendered by optimizing every parameter except for one that is altered in a negative way. Experimental conditions differ by the level of alteration for one particular parameter, such as latency or resolution, or by the parameters themselves. The approach allow testing very different parameters, such as interaction possibilities, or the use of a stereoscopic rendering, as long as participant can quickly and repeatedly switch between representations. In a concern for generalization, this method is repeated on various virtual scenes.

Similarly to the psychophysical methods, our method relies on the participants' sense of presence to evaluate the influence of several parameters. But unlike methods such as in Bergstrom et al. [START_REF] Bergström | The plausibility of a string quartet performance in virtual reality[END_REF], participants are not familiarized with the parame-ters and they cannot manipulate them freely. By hiding the information and the control on the parameters, we insure that participant are not influenced by their own expectations about the parameters.

DESIGN OF THE USER STUDY

Selecting a definition of presence

The goal of our study is to measure the effect of the main technical parameters of a visual stimulus on presence. How-ever, a universal definition of presence is hard to find in the literature, as the various studies tend to subdivide the concept to fit their specific needs: physical presence, social presence, co-presence, and telepresence. All these definitions, however, describe a psychological sense of sharing a reality with one or several entities. Lee [START_REF] Kwan Min | Presence, explicated[END_REF] proposed a definition of presence that unifies the VR and AR approaches: they define presence as "a psychological state in which virtual (para-authentic or artificial) objects/social actors/selves are experienced as actual objects in either sensory or nonsensory ways". We use this definition, and use the term "entity" to denote all possible ac-tors from unanimated objects to the self. We also acknowledge that presence is a continuous metric rather than a binary value, as evaluated in many studies [START_REF] Slater | Taking steps: the influence of a walking technique on presence in virtual reality[END_REF][START_REF] Price | The role of presence in virtual reality exposure therapy[END_REF][START_REF] Chen | Exploring the Effect of Presence in an ARbased Learning Environment[END_REF], and that presence depends on the task (e.g. a weightless metallic virtual object may seem present, as long as users don't interact with it). In summary, our study aims at measuring presence defined as "a continuous metric for the psychological state corresponding to the degree to which virtual entities are experienced as actual entities in either sensory or nonsensory ways for a specific task".

Acknowledging the lack of consensus on the definition of pres-ence and its associated concepts, we note that our experiment can also be seen as measuring the plausibility of the virtual entity.

Choice of parameters

In order to isolate the effect of technical parameters, we imple-mented an HPCD technique where parameter's values could be independently altered from a reference optimal value. The optimal value corresponds to our best implementation effort. We chose to implement an HPCD device, as it allowed us to surpass commercialized Head-Mounted Display (HMD) hard-ware in term of jitter and resolution, and to equalize the bests HMD in term of latency.

According to Cummings et al. [START_REF] Cummings | How immersive is enough? A meta-analysis of the effect of immersive technology on user presence[END_REF], the most studied and impactful technical parameters when dealing with presence are display resolution, frame rate, tracking jitter, the field of view, and stereoscopy. We altered this set of parameters with the following rationales. We created virtual entities that appeared to reside inside a Handheld Perspective Corrected Display (HPCD); hence the field of view was not relevant and was left out of this study. We found in a pilot study that the absence of stereoscopy when using a HPCD would break the feeling of presence in a strong way. We thus considered that stereoscopy is an essential requirement for presence and removed this parameter from the study. The effect of the system's latency on presence has not been studied in depth, however several studies have shown its strong negative impact of the quality of the interaction [START_REF] Cattan | Reducing latency with a continuous prediction: Effects on users' performance in direct-touch target acquisitions[END_REF][START_REF] Ng | Designing for low-latency direct-touch input[END_REF][START_REF] Pavlovych | The tradeoff between spatial jitter and latency in pointing tasks[END_REF]. We suspected a similar negative impact on presence and chose to include it in the study. We thus tested the effect on presence of display resolution, latency, frame rate and tracking jitter (RLFJ).

Alteration levels

All parameters were tested at two or more levels in the study. For each parameter, one level was our best effort, i.e. the best level we could achieve with our experimental system. We reproduced the HPCD system described in Berard et al. [START_REF] Bérard | The Object Inside: Assessing 3D Examination with a Spherical Handheld Perspective-Corrected Display[END_REF]: for all representations, the entity was displayed in a 30cm diameter polystyrene sphere used as a wireless HPCD. Motion capture was implemented with an Optitrack optical tracking system (8 Prime 13 cameras at 240Hz). We recorded the re-ported position of a static marker to evaluate tracking jitter and observed a Gaussian white noise. Images were created by a Barco F-50 projector (2560x1600@120Hz pixels). Stere-oscopy was implemented using shutter glasses and time multi-plexing the left and right images. We evaluated the system's end-toend latency using the approach from Cattan et al. [START_REF] Cattan | Reducing latency with a continuous prediction: Effects on users' performance in direct-touch target acquisitions[END_REF]. This system achieved to following best-effort levels for the 4 parameters: resolution at 90dpi in the focus area (resolution lowers on the side of the projection on the sphere), latency at 27ms, frequency at 60Hz per eye, and jitter at 0.022mm of standard error.

To determine relevant alteration levels according to the state of the art, we first diagnose popular VR and AR devices for their RLFJ values. We evaluated two VR HMD (HTC Vive and Vive pro), two AR HMDs (Metavision Meta 2, Microsoft Hololens) and an AR tablet (Tango).

Software alteration was chosen as follow.

• Resolution. The majority of AR ready tablets, as well as the Hololens, have a resolution in the order of 100dpi; which is superior to the 90dpi of our HPCD implementation. Most current HMDs have a much lower resolution, in the order of 50dpi, although high resolution VR HMDs are becoming available. We chose a first alteration level at 50 dpi. We also tested a second alteration level, recognizing that it is common practice to lower the rendering resolution in software to keep an acceptable frame rate with virtual scenes of high complexity. We chose 35pdi ( √2 * 50d pi = 35d pi) as the resolution reduction needed to halve the number of pixels from the first alteration level. • Latency. The end-to-end latency of systems used to create virtual entities is generally not published. Sometimes, a soft-ware prediction is used to compensate for part of the latency. However, predictions have the drawback of increasing the jitter in position. We chose to avoid predictions in this study to concentrate on the fundamental impact of latency and jitter. Nevertheless, the prediction used in the Hololens prevented us to estimate its baseline latency. We measured a latency of 28ms for the vive pro (nearly identical to our optimal value), and around 60ms for the Meta 2. Ng et al. report that the latency of commercial touch devices is in the range 50-200ms [START_REF] Ng | Designing for low-latency direct-touch input[END_REF]. We chose to use a single alteration level for latency at 60ms. • Frame rate. Frame rates are easy to evaluate, as they are negotiated with the graphic card; which report it to the system. We observed a native frame rate (i.e. optimal) of 60Hz for the Hololens, 72Hz for the Meta 2, 90Hz for the Vive and Vive pro. The frame rate of most tablets is 60Hz. Current hardware thus affords 60Hz stereoscopic display, but rendering complex scenes often result in frame rate drop. We chose a single frame rate altered level at 30Hz to illustrate rendering limitations. This frame rate level also represents what time multiplexed stereo would provide on 60Hz tablet computers. • Jitter. We measured a standard error of the jitter at 0.13mm, 0.20mm and 1.7mm for the Vive pro, the Hololens, and the Meta 2, respectively. We first intended to use these as 3 alteration levels from our baseline (0.022mm). However, we determined in pilot studies that 0.13mm was unnoticeable and that 1.7mm was conversely breaking presence when used with the HPCD. We chose not to include 0.13mm, to halve 1.7mm, and to include a value inbetween the two remaining alteration levels. We thus tested 0.2mm, 0.5mm and 0.8mm.

Entities and task

In a concern for generalization, we chose two entities with different complexity in their behavior and interaction possibil-ities. The first entity was a femur. Participants could explore the bone by rotating and moving the sphere but the bone was static in the sphere coordinate system. The second one was a butterfly that acted like it was encaged in the sphere: it could walk on the surface of the sphere or fly inside it. When on the surface, participants could force it to fly if they shook the sphere. The animation was randomized to appear realistic. Both entities are illustrated in figure 1. The task that we asked participant to perform was to freely explore the presented enti-ties by means of changing their viewpoint and manipulating the sphere (including shaking it).

Protocol

We implemented the method introduced above. At the begin-ning of the session, we explained the definition of presence to participants. Every representation was associated with a single level of alteration of a single RLFJ parameter. In other words, each representation was our best effort, except for one parameter that was altered. The table 1 summarize all the representations used in the experiment. Each representation is named after its altered parameter and level. It should be noted that the best effort was not presented as a representation.

The set of comparison presented to participant was made of all possible pairs of representations, except that we did not present pairs of representations of the same parameter at different levels.

The same comparison was presented 8 times to each participant (4 times per entity). This resulted in 17×8 = 136 comparisons per participant. As the experimental session was quite long, in the order to 90 minutes, we split it on two days to limit a tiredness effects. Comparisons were presented in a randomized order in a total of 8 blocks (4 peray). The entity displayed was the same within a block and was switched between each block. Participants could take a short break between each block.

At the end of the first day of experiment, participants filled a short questionnaire with three questions designed to highlight the subjective differences between the two entities presented. For the two entities, they had to report: the variability of presence levels experienced (on a strait line without scale), how easy it was for them to answer the comparisons, and how much they enjoyed to explore the scene (on a 5 level scale for the two last questions).

Participants

We welcomed 16 participants: 8 women, 28.2 mean age (23 to 37). All had correct stereoscopic vision (tested with the Stereo Optical RANDDOT stereopsis test), and none was afraid of butterflies.

Figure 2 shows a participant exploring two representations: one for each entity. While exploring, she can tap her right foot at any time to switch between the two representations. She identifies the one generating the most presence by tapping with her left foot while it is active.

RESULTS

Methodology

We recorded participants' preference in terms of presence felt when presented a comparison of two representations. To com-pute mean and confidence intervals, we associated numeral values to participants' answers. Given a comparison A vs. B, we associate a value of 1 whenever A has been preferred, and a value of -1 whenever B has been preferred. In Figure 3, Figure 4, and Figure 5, each cell represents a A vs. B comparison where A and B are defined by a cell's row title and column title, respectively. In a concern for readability we did not present redundant information: resolution conditions are only presented on the left and jitter conditions only on top.

We acknowledge the current concerns on the use of statistical significance categorization in various research fields [START_REF] Valentin Amrhein | Scientists rise up against statistical significance[END_REF][START_REF] Besançon | The Continued Prevalence of Dichotomous Inferences at CHI[END_REF]. Hence, we report the exact values of the probability of the NULL hypothesis and we avoid the use of the significance vocabulary.

We computed the probability of results being explained by ran-dom sampling and measurement errors (p-value of the NULL hypothesis) with logistic regressions for every comparison. We used R glmer, anova and glht methods from packages lme4 and multcomp.

Effect of the entity

We performed an analysis of deviance, with single-step correc-tion, to test the effect of the entity on participants' preferences. Results are shown in Figure 4. They indicate that participants' feeling of presence differed depending on the entity mostly when resolution was involved, although it also differed in the frame rate 30Hz vs. jitter 0.8mm comparison. Conversely, results appear to be similar with both entities when resolution is not involved.

Participants' preferences

For each participant, we computed the mean answer for the 4 repetitions per entity of each comparison. We then computed the mean and standard deviation across participants for each comparison, per entity. This is shown on Figure 3. We com-puted the p-value for each comparison by testing the linear hypothesis of the logistic regressions. The p-values are shown in Figure 5.

An alteration that is often preferred indicates that the parameter has not a strong negative impact on presence. However, this does not mean that this parameter has a positive impact on presence as presence is resulting from the combination of all the parameters. Conversely, an alteration that is rarely preferred indicates that the parameter has a strong negative impact on presence. We thus focus in the latter.

Jitter. We observed that jitter 0.8mm was never preferred, which indicate that jitter was a critical parameter for presence and that a high jitter has a strong negative impact. This effect is robust (with low p-values) and the effect size is large, with mean preferences against this condition at 0.78 or more, except when compared with frame rate 30Hz with the bone.

Even with the lesser alteration at 0.5mm, jitter was rated more detrimental than resolution and latency for both entities. The effect sizes observed are lower than with the highest jitter level but the effect remains robust. This level of jitter, however, appears to have an effect that is close to the effect of the 30Hz frame rate: in these comparisons, preferences are closer to 0, answers are more variable, and the p-value indicates a fragile effect (e.g. p=0.26 for the bone).

The smallest jitter level that we tested (0.2mm) is far less detrimental for presence. It was preferred to the frame rate alteration for both entities and to the resolution alterations for the butterfly. The other comparisons were less clear; which indicate an effect similar to those of the resolution alteration for the bone and the latency alteration for both entities.

Frame rate. Frame rate 30Hz is more detrimental than latency 60ms for both entities, and more detrimental than the two resolution alterations for the bone. Frame rate 30Hz appears to be more detrimental than resolution 50dpi with the butterfly entity, even though this last result has a smaller effect size and is less robust (mean preference of 0.34, p=0.038). Finally, frame rate 30Hz seems equivalent to resolution 35dpi with the butterfly entity (mean preference of 0.22, p=0.236).

Latency. Latency is less detrimental with the butterfly than both resolution alterations, even if the results are not so clear with the Resolution 50dpi (mean preference of -0.25, p=0.11). With the bone entity, latency appears to be slightly more detrimental than resolution (mean preference values of 0.34 and 0.38 for the 50dpi and the 35dpi condition respectively, p<0.043).

Effect size -task duration correlation

For both entities, we computed the Spearman correlation factor between the effect size for every comparison and the mean time spent by the participants to answer to the comparison. We obtain a correlation factor of -0.78 for the bone and of -0.12 for the butterfly. We assumed that large effect size corresponded to an easy comparison, i.e. a comparison where the best representation for presence was obvious. Hence, we observed that time spent in each comparison was highly related to the difficulty of the task with the bone entity but not with the butterfly.

Subjective results

Participants expressed a range of presence that delimited all representations of the same entity that they explored, i.e. from the less present representation to the most present one. The range was expressed on continuous scale with no graduation from no presence to perfect presence. The results are reported in figure 6.

The range expressed by participant is quite large: over 50% of the entire scale. This indicates that the loss of presence in the worst conditions was clearly felt by the participants. For both entities, results are extremely similar.

For the two questions: 'I liked to explore the scene' (explo-ration enjoyment) and 'In average, I could easily identify the most present representation within each comparison' (ease for identification), participants answered on 5-levels scale from 1 (not at all) to 5 (totally). Results are illustrated on Figure 7. Participants slightly preferred to explore the scene with the butterfly but they found the choice task easier with the bone.

DISCUSSION

Effect of the entity

We observed that results are similar with both entities except when resolution is involved. The two studied entities are quite different: the bone is a simple non-textured mesh whereas the butterfly is made of highly detailed mesh with colorful textured wings. This could explain why alterations of resolutions were more detrimental to presence in the case of the butterfly. This result reveals how the nature of the entity may put specific technical requirements to create a good presence. In our study, the two entities did not have a tightly coupled interaction with the participant, which may explain why the alteration of latency did not have a strong detrimental effect on presence. A virtual pen, however, may have a stronger requirement in terms of latency.

General analysis of the comparisons

Jitter 0.8mm was the worst condition for presence, whereas Jitter 0.2mm was one of the conditions with the weaker effect, alongside Latency 60ms. Frame rate 30Hz and jitter 0.5mm belongs to the same class in their impact on presence with both entities, along with the 35dpi resolution condition with the butterfly.

Figure 8 summarizes the results of the comparisons. Alter-ations are either separated per entity or regrouped when the results do not depend on the entity. Rectangles regroup condi-tions in same class.

Performance trade-offs

Resolution vs. frame rate

Displaying complex scenes can reduce the frame rate when the computing time for each frame is greater than the refresh period. Our study indicates that reducing the display resolution to keep the optimal frame rate is a good strategy in terms of presence, although caution is required when displaying highly detailed entities. Still, with the highly detailed butterfly, going from 90dpi to 50dpi was less detrimental to presence than going from 60Hz to 30Hz. This could be explained by degree of physicality of the two phenomena. There are many physical explanations for seeing things in low details: air mist, dirty glasses or window, eye moisture, etc. This is not the case for jerky motion.

Latency vs. jitter

The study revealed that tracking jitter could have a large detri-mental effect on presence. One way to reduce jitter is to smooth the tracking data over several capture frames at the cost of additional latency. Our study indicates that this could be a good strategy in terms of presence, as the latency alter-ation had a smaller negative effect to presence than the two largest jitter alteration, and a similar effect to the smallest jitter alteration. In our experiment, participants explored the virtual entities residing inside a sphere. The vibration of the entities due to jitter did not seem to have a physical interpretation; while the lag of the motion of the entities created the illusion that the entities were immersed in a viscous fluid. However, this trade-off may be task dependent. It may only be beneficial when there is no tightly coupled interaction with the entities, as the opposite trade-off is more suitable in terms of pointing performance [START_REF] Pavlovych | The tradeoff between spatial jitter and latency in pointing tasks[END_REF]. In addition, we only tested a latency alter-ation from 27ms to 60ms. It would be interesting to investigate how far the trade-off holds when going beyond 60ms.

Informal feedback from participants

Some participants reported that the butterfly appeared more present than the bone because it moved by itself. They took some times to play with it and explore its movements, like they would have done with real butterflies. Three participants also gave it a name. These comment partly explain the weaker correlation between the effect size and the answering time: even when a comparison was easy to rank, some participant did not answer immediately as they were compelled to play with the butterfly. However, some participants where disturbed by the wings animation: they found that it was not plausible, reducing the presence felt. One participant found the bone extremely convincing as a 3D-printed plastic bone, resulting in total presence with the best representations. Two participants reported that latency, especially with the bone, produced an immersion effect, as if the sphere was full of formalin. This is another illustration on how the human brain manages to produce rational explanation to a strange stimulus, as with the ventriloquism effect. Another participant reported that the "vibrations" of the bone when it was supposed to be static (i.e. with high jitter) was strongly breaking the presence because static object that lay in stable equilibrium never move in "real life". Here, the lack of a credible physical explanation appears to have broken the presence.

Several participants reported that the movements of the butter-fly made it hard to compare the representations, whereas they could easily reproduce a similar viewpoint in the two represen-tations with the static bone. This probably explains why the task was rated more difficult with the butterfly than with the bone. Finally, the fact that participants also liked to explore the static bone without getting bored (enjoyment score superior to 3.5 over 5) is in line with a high involvement in the task when presence is concerned, as previous work suggested [START_REF] Chen | Exploring the Effect of Presence in an ARbased Learning Environment[END_REF].

Presence comparison method

We observed that the presence comparison method that we introduced had a high level of acceptance: all participants declared that they clearly understood the task. In the subjective questionnaire, the question about the ease to answer the task had a score of 3.2 or more (for a maximum of 5) for both entities. The method yielded several large effect sizes (e.g. score of 0.81 for jitter 0.2mm when opposed to frame rate 30Hz) that appear to be robust (p=1e-05 for this comparison for both entities).

Although we used the method in a study focused on a small set of technical parameters, we think that its utility is quite general. For example, the method could be used to thoroughly test a single parameter with many alteration levels; which would bring it closer to the JND protocol. Also, it could be used to test the effect on presence of non-technical parameters such as the complexity of the task or the plausibility of the entity.

Limits of the study

As in any user study, participants' time and endurance are bounded. We thus had to limit the number of tested conditions. The results should be interpreted with these limits in mind. In particular, we only tested each parameter individually. Yet, some parameters may interact with others. In addition, for now, we have confidence in the results only for one particular task, two entities, and one particular interactive device. Further studies are required to test for the generality of these results. More conventional VR and AR HMDs could be used, although a lesser baseline may prevent a direct comparison of the results with the spherical HPCD. In addition, it would be particularly interesting to test other tasks involving more tightly coupled interaction between the participants and the entity, in order to interrogate the latency-jitter trade-off. Finally, more complex entities should be tested, such as human avatars, although the main bottlenecks on presence may stem from the quality of the human model rather than the technical parameters of the visual stimulus.

This first study based on the proposed method shows the vi-ability of the method. However, further studies on the effect of these parameters on presence will be required to test the coherence of the results and thus to test the external validity of the method.

CONCLUSION

Recent improvements in AR and VR hardware have resulted in virtual experiences that come close to creating the perfect subjective feeling of presence. However, the final step may require a methodological analysis of the factors coming into play to create this feeling. One way to foster this methodolog-ical analysis is to unify the concept of presence across the various research fields involved, so that studies' results can be more easily consolidated. The method that we introduced is not tied to any particular system, interactive setup, or research field. The user study implementing this method serves two purposes. It provides evidences of the viability and utility of the method. It also provides a first measurement of the relative effect on presence of 4 important parameters of the virtual visual stimulus in the context of a spherical Handheld Perspective Corrected Display. These measurements inform about important design guidelines: avoiding a perceivable mo-tion jitter and a loss in frame rate were the most important requirement in our setup. Reducing the resolution does not reduce the feeling of presence for entities that do not have fine details. And contrary to our expectations, a perceivable latency of the system did not have a strong negative effect on presence.

Figure 1 .

 1 Figure 1. The two entities displayed. On the left, the static bone. On the right, the animated butterfly while it is flying inside the sphere. For illustration purpose, stereo has been disabled in this picture.

Figure 2 .

 2 Figure 2. A participant exploring a representation of the bone entity (left) and of the butterfly entity (right). Daylight was covered during the experiment to maximize the projector contrast.

Figure 4 .

 4 Figure 4. Effect of the entity: probability of the NULL hypothesis for the difference of mean preferences between entities, for each comparison.

Figure 5 .

 5 Figure 5. Robustness of the comparisons: probabilities of the NULL hypothesis (p-values) for the preferences reported in Figure 3.

Figure 6 .

 6 Figure 6. Self reported range of presence of all explored representations, per entity. The left and right sides of the boxes are the mean of the min-imum and maximum limits of the range, respectively. 95% confidence intervals are represented by the colored segments.

Figure 7 .

 7 Figure 7. Mean subjective enjoyment and task difficulty, per entity, with 95% confidence intervals.

Figure 8 .

 8 Figure 8. Alterations ordered by the strength of their detrimental effect on presence, from the most detrimental (top) to the less detrimental (bot-tom). The rectangles group alterations that are in the same class. The effect of the resolution alterations depends on the entity.

ACKNOWLEDGEMENTS

This work was supported by the An@tomy2020 project ANR-16-CE38-0011.


L Ta Eb

M Schoenauer

Optimization of direction nders by Genetic Algorithms

1 The relative positions of the antennas of a direction nder are critical regarding the e ciency and the robustness of the indications of the apparatus. The state of the art in direction nder optimization is limited with classical methods to the case of direction nders with 3 antennas, with naive trialand-error methods for more complex cases. The use of Genetic Algorithms brings a tremendous increase to that domain, allowing the optimization of direction nders with up to 10 antennas in a reasonable computing time. Moreover, as GAs provide multiple optimal solutions on multi-modal problems, a thorough numerical investigation of all possible optima provides a new insight in the underlying optimization problem, nally leading to the derivation of a formula for the optimal direction nders.

Introduction

A direction nder is a measuring apparatus used to determine the bearing angle (or site angle) of the direction of an electromagnetic source from the differences in phase measured between couples of antennas. It is used by airplanes or ships for the determination of the position of radars or radio beacons. Direction nders used for radar detection and localization, with high frequency signals, are studied and built by the division "Radars et Contre-Mesures" (RCM) of the French rm THOMSON. Even in the simplest case of aligned antennas, in which a single direction is sought, the exact positions of the antennas is a critical factor of the efciency and accuracy of the direction nder [START_REF] Schwefel | Numerical Optimization of Computer Models[END_REF]). This e ciency is quanti ed by a maximum allowable error, the amount of noise that a given direction nder can a ord while still giving a correct answer regarding the direction of the incoming signal. The case of 3 antennas has been well studied ( 15]), and analytical formulas can be derived for such an error, allowing brute optimization: both extremal antennas are xed to the prescribed total length of the apparatus, and every possible placement of the third antenna on a xed grid between the two others can be investigated. But such a method does not scale up: even in the case of four antennas, the classical method is to start from the optimal solution of the corresponding 3antennas problem, and to add the fourth one by trials and errors, eventually moving step by step the third antenna. And of course the global optimization of more than 4 antennas is unconceivable with such methods. The reasons for that are both: First, the function to optimize is not analytically known, and is accessible only through numerical computation. Second, it presents a very large number of local optima, and the standard deterministic optimization methods are known to generally fall into one of these local optima, unless some good starting points can be guessed. The use of stochastic optimization methods in such situations seems quite natural. First introduced by Holland 4], then popularized by Goldberg 2], Genetic Algorithms (GAs) are evolutionary algorithms crudely mimicking natural evolution. They are based on the Darwinian principle of the Survival of the ttest: a population of chromosomes (points of the search space) undergoes a succession of generations, and each chromosome is applied successively the genetic operators of selection, cross-over and mutation. GAs, though they are not function optimizers [START_REF] Holland | Adaptation in natural and articial systems[END_REF]) have demonstrated they can be used as trustworthy optimization methods, particularly in cases where other classical methods fail. The price to pay for that is a fairly high computational cost. This paper presents results obtained by GAs on the problem of optimizing a direction nder, problem which is introduced in Section 2. The main di culties come from the noise in the measures made by the antennas, which cannot be avoided in real world applications. The mathematical optimization problem, taking these errors into account, is posed, but all the technical details are omitted. Three annexes at the end of the paper give the most important calculation details, and all detailed demonstrations can be found in 15]. Section 3 gives a brief overview of the genetic algorithm used on the direction nder problem, while section 4 presents the results obtained in the case of aligned antennas. Direction nders up to 10 antennas can be optimized by this method. Moreover, multiple optimal solutions can be found by GAs, either in multiple runs, or using niching schemes like the well-known sharing scheme ( 3]). And a careful look at all solutions found by the GAs in the case of 3 antennas for di erent values of the total length D of the direction nder surprisingly lead to a relation linking the optima for lengths D and D=2, thus completely solving the 3 antennas case. Section 5 presents this unusual approach, where numerical computation through evolutionary computation happened to be the necessary step toward the theoretical comprehension of the underlying phenomenon. The nal section presents some preliminary results obtained in the more general case of coplanar antennas (not aligned). The extension of the method to that case is conceptually straightforward, though many technical di culties, not presented here, arise during the derivation of the tness function. Finally, some future directions of research are sketched, in the area of electromagnetic engineering using GA optimization.

Background

A direction nder is made of several antennas, recording electromagnetic signals coming from a xed source. The dephasings between the antennas are used to determine the direction from which the signal is coming. This section is devoted to the derivation of the theoretical equations governing a direction nder, when all antennas are aligned. The di culties encountered in a real world situation are emphasized. The number k is termed the number of turns between the antennas. This number has to be determined before the angle can be extracted: the information given by the two antennas is not sucient to actually nd out the direction from which the signal is coming.

Theoretical approach

Consider now a three antennas direction nder, as described by Figure 2. The antennas 1 and 2 (resp. 2 and 3) are separated by a distance d 1 (resp. d 2 ), and 1m (resp, 2m ) are the measured dephasing between antennas 1 and 2 (resp. 2 and 3). Applying equation (3) twice for both couples of antennas gives

2m = d 2 d 1 1m + 2 ( d 2 d 1 k 1 k 2 ) (4)
for some couple of integers (k 1 ; k 2 ). Figure 3 shows a plot, in the 1m 2m plane, of the solutions of (4), made of several parallel lines, one for each couple

(k 1 ; k 2 ).
From a couple of measures ( 1m ; 2m ) it is then possible to identify all couples (k 1 ; k 2 ):

d 2 d 1 k 1 k 2 = 2m d2 d1 1m 2 ; j im j (5)
The only one case of non-uniqueness is the case where two di erent couples (k a

1 ; k a 2 ); (k b 1 ; k b 2 ) satisfy d 2 d 1 k a 1 k a 2 = d 2 d 1 k b 1 k b 2 ; a 6 = b (6)
i.e.

d 2 d 1 = k b 2 k a 2 k b 1 k a 1 ( 7
) (k1,k2) (k1,k2) (k1,k2) (k1,k2) (k1,k2) (k1,k2) (k1,k2) (0,0) (k1,k2) 2 φ φ 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 m m Figure 3 : 2m =f( 1m ; k a 1 ; k a 2 )
So, if the distances (d 1 ; d 2 ) are chosen such that d2 d1 6 2 Q, equation ( 5) has a unique solution (k 1 ; k 2 ), which in turn allows the derivation of the angle from one of the equation:

= arcsin( 2 D ( 1m + 2k 1 + 2m + 2k 2 )) (8)

Real world is noisy

But in practice, errors are made on the measures ( 1m ; 2m ). If i is the error made on im , equation (3) becomes: im = 2 d i sin 2k i + i ; 1 i 2 [START_REF] Radcli | Equivalence class analysis of genetic algorithms[END_REF] The relation between 1m and 2m is then:

2m = d 2 d 1 ( 1m 1 ) + 2 ( d 2 d 1 k 1 k 2 ) + 2 (10)
The measured points are generally not on one of the lines of Figure 3, but somewhere between two lines, depending on the errors. Such a situation is presented in Figure 4. The error cube corresponds to the maximum possible error of the measurement process.

When a point ( 1m ; 2m ) is measured, in order to derive , the couple (k 1 ; k 2 ) of equations ( 8) must be determined without ambiguity. And the simple procedure "take the nearest beam line in Figure 3" does give the correct answer if the error square of gure 4 does not intersect with the dotted line which is the median between the lines (k a [START_REF] Schwefel | Numerical Optimization of Computer Models[END_REF], 2 The distance considered here is the Euclidean distance. But any distance on IR 2 gives the same qualitative results.

1 ; k a 2 ) and (k b 1 ; k b 2 ) 2 . So, for any (k a 1 ; k a 2 ), (k b 1 ; k b 2 ) both satisfying
there exists a maximum allowable error denoted ab such that, if the maximum errors 1 and 2 on the measures of the dephasing are less than ab , the error cube induced by these errors will not intersect. The value for ab is given by ab

= j d2 d1 (k b 1 k a 1 ) (k b 2 k a 2 )j 1 + d2 d1 (11)
See Annex 1 for more details. Let = min a6 =b ab , where the minimum is taken over all (k 1 ; k 2 ) satisfying relation [START_REF] Radcli | Equivalence class analysis of genetic algorithms[END_REF].

Assuming that 1 and 2 are less than , ensures that the determination of the couple (k 1 ; k 2 ) of equation ( 8) is unambiguous (by choosing the nearest line of the theoretical beam). Thus, the determination of is possible, without ambiguity as well.

Remark: The distance D between the two extremal antennas plays a leading role. Actually, it has an in uence on the precision of the calculus of the researched angle. If is the angle calculated with errors on the measures and the theoretical angle:

= arcsin( 2 ( P n 1 i=1 ( im + 2k i ) D + P n 1 i=1 i D )) = arcsin( 2 ( P n 1 i=1 ( im + 2k i ) D ))
and when D ! 1 !

The in uence of the errors on measures becomes insigni cant, that's why it is desirable to take this distance as long as possible. On the other hand, technological (and military) reasons generally impose strict restrictions on the maximum total length D of the direction nder.

The optimization problem

Consider now the general case of N aligned antennas. The antennas i and i + 1 are separated by a distance d i . The di erence of phases im between antennas i and i + 1 are measured with some error.

Equation ( 12) gives the maximum allowable error still enabling to actually solve the direction nder problem: nd the direction of the coming signal. And this term depends on the distances (d i ) separating the antennas. The aim of direction nder design is to nd out these distances (d i ) such that the allowable error , is maximum, thus allowing the unambiguous determination of even in the worst noisy possible case. The data of this optimization problem are N the number of antennas 3 , D, the total length of the direction nder, F the frequency of the signal, max the wanted range of visibility of incoming signals, and d min , the minimum distance between antennas (imposed by the physical dimensions of the antennas).

The useful variables here are b i = d1 di+1 ; i 2 1; N 2] (with notation b 0 = 1). The optimization problem can be mathematically written as Find (b 1 ; :::; b N 2 ); 2 IR N 2 + such that:

= inf 6 = sup 1 i n 2 i<j n 1 j bi 1 bj 1 (k i k i ) (k j k j )j 1 + bi 1 bj 1 (12) d i = D (1 + P n 2 j=1 (1=b j ))b i 1 d min (13)
Some details about these formula can be found in Annex 2.

A simple plot in the case of 3 antennas for a small value of D (Figure 5) gives an idea of the landscape of in terms of b = d1 d2 . Such a landscape, in this very simple case, explains why deterministic optimization algorithms fail, and why Genetic Algorithms have greater chances of success in solving this problem. 3 which could actually be unknown, to be minimized 3 The Genetic Algorithm

The Genetic Algorithm used for the optimization problem presented in section 2.3 is a home brew GA. The general outline of the algorithm is the usual GA scheme:

Randomly initialize the population. Iterate until either a prescribed number G of generations is run, or G flat generations are run without any increase of the maximum tness in the population:

{ Select individuals according to their relative tness.

{ Recombine couples of selected individuals with probability p cross .

{ Mutate o springs with probability p mut .

The di erent genetic operations are based on what is now becoming the standards in many real world applications of GAs dealing with real numbers: roulette wheel selection, with linear tness scaling (see 2]); real encoding, as demonstrated powerful by 8, 7]; The genetic operators are adapted to that representation:

The crossover operator is achieved by a linear combination of both parents (this operator is termed the intermediate recombination operator in Evolution Strategies, see 9, 1]).

The o spring of the two parents (x 1 ; : : : ; x N ) and (y 1 ; : : : ; y N ) is ( x 1 +(1 )y 1 ; : : : ; x N + (1 )y N ) for some randomly chosen uniformly in 0:5; 1:5].

The mutation operator is performed by adding some Gaussian noise to the some randomly chosen coordinate(s) of the chromosome. The main di erences with the mutation scheme of Evolution Strategies 9, 1] is that each coordinate has a probability of being changed, and the evolution scheme for the standard deviations of the Gaussian noise is a geometric decrease instead of an adaptative evolution.

When some niching scheme is needed, the sharing scheme as described in 3] is used. For all runs, the stopping criterion is either a maximum number of generations, or a prescribed number of generations without any improvement, whichever comes rst.

The actual parameters used are: p cross = 0:65; p mut = 0:075

Numerical results

This section is devoted to the numerical results obtained using the GA brie y presented in section 3 on the direction nder optimization problem of section 2.3. Fortunately, these results con rm some points that direction nder experts have known for long: when D increases, the maximum allowable error decreases, and the only way to increase is to use more antennas. The only di erence is that now, the optima with up to 10 antennas can be computed. Moreover, the results of Figure 6 also demonstrate that the incremental method is de nitely useless when the number of antennas increases, as the optimum solution for N + 1 antennas is not a simple addition of one antenna to any optimum for N antennas.

But even more insight in the problem of direction nder can be gained from a careful look at the numerical results obtained by the GAs, as is demonstrated in the next section.

New theoretical insight

One of the main advantages of GAs, apart from being able to solve di cult optimization problems untractable with standard optimization methods, is the ability to nd out multiple quasi-optimal solutions to a given problem. This can be achieved either incidently, by running the same algorithm with di erent random initializations of the population, of more systematically by adding some niching technique to the basic GA. The sharing scheme (see 3]) is used in the GA presented in section 3.

From the equations giving (see section 2.3 and Annex 2), it seems clear that some kind of regularity exists in the problem. However, no direction nder expert has been able to precisely identify any theoretical relations between di erent optima.

But a close look at many results obtained for the 3 antennas problem, where is a function of 1 variable ( d1 d2 ) gave hints that nally lead to an answer. The following relations give all the maxima in term of the data:

Let D sin max 2 IN: 8 k 1max 2 IN; 0 k 1max < D sin max b = 2k 1max + 1 2( D sin max k 1max ) (14) = 1 + 2 D sin max ( 15
)
The number of maxima M is:

M(D; ; max ) = 2 D sin max (16)
The technical details can be found in Annex 3.

Remark: The component of the maxima for D sin max 2 IR can be found at the end of the An-nex3.

Let's apply the relations ( 14),( 15),( 16) for the case D=100mm, F=18 Ghz ( = 16:667mm), max = 2 ; d min = 0 D sin max = 6 can be immediately derivated : = 13 13:846154 this maximal value is obtained for the following b i , extracted for 0 k1max 5 We can also notice that maxima for a given distance D = 2 12:5 can also be found by addicting an integer, or dividing the decimal part by 2 of the maxima D = 2 1 12:5 ( gure 6). This is in fact the observation of these links which lead us to study a theoretical approach, and make us found out the expression of b and in function of the given informations.

k 1max = 0 ) b 0 = 1 12 0:0833333 k 1max = 1 ) b 1 = 3 10 = 0:3 k 1max = 2 ) b 2 = 5 8 = 0:625 k 1max = 3 ) b 3 = 7
The derivation of the same kind of results for any number of antennas is part of ongoing work, and the technical di culties are almost overwhelmed (see 15]).

Conclusion and future work

An application of GA optimization to direction nder optimization has been presented. The state of the art of electromagnetism engineering was limited by the use of classical optimization methods to 3 or 4 aligned antennas. The evolutionary optimization is able to handle the case of up to 10 aligned antennas. Moreover, the ability of GAs to nd multiple optima lead to the derivation of a theoretical analysis of the problem, through a careful look at all optima. Though this theoretical analysis has no a posteriori relation with GAs, it had not been found out before numerical optimization gave hints that nally lead to the solution.

Regarding the numerical optimization of direction nders, ongoing work is concerned with more general con gurations of the antennas.

The rst results on coplanar antennas is a strict extension of the aligned case, though the technical details of the derivation of the tness function are awkward looking (see 15] for all the details). The rst results obtained with the same method are presented in Figure 8, in the case where the antennas must lie on a given half-circle. The more general case of 3-dimensional direction nders, where both the bearing angle and the site angle are to be determined by the direction nder is currently under investigation.

Moreover, the same kind of theoretical result then the one presented in section (5) has been obtained for the general case of N aligned antennas. But the extension of these results to more general situations seems more di cult.

Finally, electromagnetism engineering o ers many optimization problems whose characteristics appeal for evolutionary computation, e.g. diagram synthesis, partitioning of networks of antennas. The basic relations relations of the problem are: b i = d1 di+1 , b 0 = 1 im = 2 di sin 2k i + i 1 i n 1; k i 2 N; j i j jm = B(i; j)( im + 2 k i i ) 2 k j + j B(i; j) = bi 1 bj 1 1 i n 2; i < j n 1 im The preceeding relations imply that for each measured dephasing im , there is a nite number of turns which allow to nd out the theoretical dephasing i : jk i j E di sin max + 1 2 (1 + )] , k i 2 N with:

= j d 2 d 1 (k a 1 k b 1 ) (k a 2 k b 2 )j 1+ d 2 d 1 2 ( d 2 d 1 k a 1 k a 2 ) = 2m a 2 d 2 d 1 ( 1m a 1 ) 2 ( d 2 d 1 k b 1 k b 2 ) = 2m
d i = D (1+ P n 2 j=1 (1=bj ))bi 1 = c F
The previous relations show that among all the possibilities of turns, we only consider those which respect the condition :

sup 1 i n 2 i<j n 1 j bi 1 bj 1 k i k j j 1 + bi 1 bj 1 1 2 (1 + )
Generalizing what have been done for 4 antennas in the Annex1 , gives equations ( 12) and (13).

= inf 6 = sup 1 i n 2 i<j n 1 j bi 1 bj 1 (k i k i ) (k j k j )j 1 + bi 1

Figure 1 :

 1 Figure 1 : Two antennas direction nder Consider a system of two antennas separated by a distance D, as represented in Figure 1. If both antennas receive an electromagnetic signal of wavelength from a direction being in the interval ] max ; max , the dephasing between the signals they respectively receive is given by = 2 D sin ; j j max 2

Figure 2 :

 2 Figure 2 : Three antennas direction nder

Figure 4 :

 4 Figure 4 : Error cube .

Figure 5 :

 5 Figure 5 : Three antennas problem: Maximum allowable error vs position of the third antenna.

Figure 6 :

 6 Figure 6 : Optimal placements for antennas found by GAs. N is the number of antennas, and D the total length of the apparatus.

Figure 7 :

 7 Figure 7 : GA results for D = 2 12:5; N = 3

  inverse values (if b is a solution, obviously 1 b is too) M(100; 16:6667; 2 ) = 12:

References 1 ]Figure 8 :

 18 Figure 8 : Five antennas direction nder on a semicircular form

  these two relations it is possible in eliminating the measures to express the di erences of turns

  Analytic relations for 3 antennas.The problem studied is the one modelized in Annex2 for N=3 with last condition replaced by j of (k 1 ; k 2 ) satisfying jk i j k imax are considered (this does not change any result).The aim is to nd out the couple (b; ) such that is maximal. The data are the distance D between the two extremal antennas, the wavelength , the maximal angle for incoming signals max , and the minimal distance between two antennas set here to 0 (d min = 0).If k 1max and k 2max are the maximum numbers of turns that can generate ambiguities, the maximum allowable error is given by: sin max ! 1 + 2 D sin max Case 2: general case with D sin max 2 IN Lets nd out b such as b = a 1 R b , a 1 2 N, R b 2 Q and verifying for a 2 k 1max + k 2max + 1) a 2 To maximize , a 2 has to be maximize but respecting k 1max and k 2max used before. when a 2 increases, b increases too, and then k 1max , a 2 has to verify: bD sin max (b + 1) + 1 2 (1 + ) < k 1max + sin max k 1max ) = 1 + 2 D sin max With k 1max = 0, we nd back the inverse value of the Case 1 of this Annex. If b is an optimum 1 b = d2 d1 is an optimum too. Then the total number of maxima M is: M(D; ; max ) = 2 D sin max The component of the maxima for D i sin max 2 IR seams to respect the following rules: Let D such as D sin max 2 IN 9 D 1 > D; D 1 sin max 2 IR such as from D + to D 1 b i D 1 = b i D , for all i; i 6 = 0; i 6 = D sin max = 1+2 D sin max M = 2( D sin max 1)The two values of b given by the Case 1 of this Annex are lost.

  9 D 2 > D 1 ; D 2 sin max 2 IR such as from D 1 + to D 2 b i D 2 = b i D , for some i = 1+2 D sin max M < 2( D sin max 1) 9 D 3 > D 2 D 3 sin max 2 IR such as from D 2 + to D 3 b 2 IR; M = 1 In this case the previous relations that give (b; ) can not be used because b has been supposed belong to Q.

Submitted to GALESIA'95, First IEE/IEEE International Conference on Genetic ALgorithms in Engineering Systems: Innovations and Applications.