Towards Sneaking as a Playful Input Modality for Virtual Environments

Using virtual reality setups, users can fade out of their surroundings and dive fully into a thrilling and appealing virtual environment. The success of such immersive experiences depends heavily on natural and engaging interactions with the virtual world. As developers tend to focus on intuitive hand controls, other aspects of the broad range of full-body capabilities are easily left vacant. One repeatedly overlooked input modality is the user's gait. Even though users may walk physically to explore the environment, it usually does not matter how they move. However, gait-based interactions, using the variety of information contained in human gait, could offer interesting benefits for immersive experiences. For instance, stealth VR-games could profit from this additional range of interaction fidelity in the form of a sneaking-based input modality. In our work, we explore the potential of sneaking as a playful input modality for virtual environments. Therefore, we discuss possible sneaking-based gameplay mechanisms and develop three technical approaches, including precise foot-tracking and two abstraction levels. Our evaluation reveals the potential of sneaking-based interactions in IVEs, offering unique challenges and thrilling gameplay. For these interactions, precise tracking of individual footsteps is unnecessary, as a more abstract approach focusing on the players' intention offers the same experience while providing better comprehensible feedback. Based on these findings, we discuss the broader potential and individual strengths of our gait-centered interactions.

INTRODUCTION
Imagine being a spy infiltrating a secret base, sneaking past patrolling guards, stealing the confidential information, and leavingunseen. This plot reads like a typical mission of any stealth game. While such games already deliver an intense experience when consumed on a flat-screen, virtual reality (VR) setups provide the unique potential of boosting tension and involvement even further. Players may fully dive into the character's role and experience the plot themselves. Nevertheless, existing stealth VR-games often fail to reach this enormous potential. Most of the available titles, such as Espire 1: VR Operative [12], do not offer a fully fetched sneaking mechanism. Instead, players have to use virtual locomotion techniques and activate a binary sneak mode using hardware buttons. While enemies may visually detect the players, one of the central aspects of sneaking is left vacant: being quiet.
In the real world, every step we take emits noise. Apart from revealing our position and speed, these walking sounds also expose a broad range of personal information, including gender [36], emo-1 arXiv:2102.02024v2 [cs.HC] 10 Feb 2021 To appear in 2021 IEEE Conference on Virtual Reality and 3D User Interfaces (VR). tional state [15], or posture [43]. Still, we usually tend to ignore them in our everyday life. Things change when the situation requires secrecy and discretion. Sneaking needs both -staying out of sight and adopting the own gait to minimize walking sounds. On the other hand, one can also attract attention by producing sounds intentionally, i.e., through stomping. This range of interaction fidelity, which is still missing in today's VR games, could greatly benefit immersive VR experiences.
Our research closes this gap by assessing the potential of sneaking as a novel input modality for immersive virtual environments (IVEs). Therefore, we split our work into three consecutive parts: We start by developing the technical basis for capturing the users' sneaking behavior. In this process, we provide insights into our exploratory design process that covered a range of different technical approaches, e.g., using microphones or marker-based tracking, as well as various abstraction levels. We also discuss the reasoning behind our final selection of three fundamentally different implementations.
In the second part of this work, we develop possible interactions and gameplay elements utilizing our stealth mechanisms. Combining sneaking with other time-or body-based tasks allows us to modify the overall task difficulty and provide varied challenges. In the final step, we compare our three sneaking mechanisms in a betweensubject study, using the developed interaction concepts. Our context is an immersive stealth VR-game, where the subjects take the role of a secret agent, stealing confidential information (see Figure 1).
Our results reveal the great potential of sneaking as an input modality for IVEs, providing high presence and enjoyment levels. The body-based mechanisms offer unique challenges and thrilling gameplay. Comparing the different technical approaches, we found that precise tracking of individual footsteps is unnecessary for the particular use-case. Instead, a more abstract approach focusing on the players' intention offers the same experience while providing better comprehensible feedback. In turn, accurate footstep tracking could be used for a variety of other use-cases, e.g., for training simulations providing individual gait-related feedback. These findings form the basis for further research on other gait-related interaction concepts.

RELATED WORK
In this section, we cover the related research relevant to this work. We start by briefly covering the basic concepts linked to playing games in VR -immersion, presence, and cybersickness. Next, we provide a concise summary of VR locomotion research, as our topic is closely linked to this area. Lastly, we discuss the latest advancements enriching IVEs with novel sensations or a greater input fidelity, focusing primarily on gait-related approaches.
Modern head-mounted displays (HMDs), such as the Oculus Quest 2 [13], replace the users' real surroundings with a realistic representation of the virtual world. In this context, researchers usually call the technical quality of the used hardware immersion [5,8,50] and the perceptual effect of being in the IVE presence [18,51]. The latter is of particular interest for this work and can be measured using various approaches [10,24,37]. Apart from the positive experience of diving into a fully immersive environment, VR also bears the risk of causing cybersickness [19,35]. In this case, a mismatch between the human vision and the vestibular system causes symptoms ranging from headaches to vomiting.
Especially poorly suited locomotion techniques bear the risk of quickly inducing high levels of discomfort [16]. Thus, recent work has mostly focused on using natural locomotion approaches, such as real walking [47], to counter this threat. These efforts center around the concept of extending the walking range by augmenting real movements [4,7,26], changing perspectives [2,9,32], or subconsciously avoiding real obstacles [46]. Among these approaches, the walking-in-place concept is of particular interest as it derives the users' anticipated motion from in-place steps [52]. While being superior to gamepad locomotion, early implementations did not feel as natural as real walking [61]. Thus, later research [14,56,68] has focused on improving the matching, e.g., by using the biomechanics of human gait [65]. Since our work connects only loosely to VR locomotion research, we point to Boletsis et al. [6] and Krekhov et al. [34] for a more detailed overview of the current state of the art.
Recently, a particular focus in VR research has been placed on enhancing the users' perception of the virtual world. These efforts mostly focus on adding additional sensations exceeding the visual and audio components of currently available headsets. Examples include haptic surface feedback [66], weight-shifting controllers [69], or olfactory systems [40]. Instead of adding novel sensations, other projects used the existing capabilities to manipulate the users' impression of the virtual world. In this context, a special focus was placed on the effects of displaying virtual avatars in various shapes and appearances [38]. For instance, altering the users' avatar can not only evoke the impression of changing age [3], race [30,44], or even species [33] but also impact mental health, like in the case of eating disorders [45]. Specifically related to our particular research interest, Pan and Steed [42] focused on the influence of virtual legs and feet on presence and embodiment.
Apart from enriching the users' interactions and sensations in general, a growing body of research has focused on improving the movement through virtual scenarios. A compelling and realistic walking experience requires a profound knowledge of the biomechanical fundamentals of human gait. The upright bipedal progression characterizing human locomotion is commonly defined as a periodic movement of the two lower limbs. The underlying pattern, i.e., the gait cycle [25], consists of two phases: the swing phase, where the foot is in the air, and the stance phase, where the foot has contact with the ground [29]. The latter phase is subdivided into four stages [23,39]: heel strike, forefoot contact, midstance, and heel off. The interplay of alternating swing and stance phases leads to forward propulsion. Individual differences, such as gender, age, posture, or walking speed, significantly influence the particular gait [31,58], and it was shown that listeners could deduce these characteristics solely from the emitted walking sounds [63]. Also, research mainly differentiates between two primary types of gait: walking and running [11,21]. Apart from the velocity, the main difference is the flight phase while running, i.e., no foot is touching the ground. Thus, we consider sneaking a subtype of walking, characterized by a more careful foot placement.
In the last decades, foot-based interactions have been of ongoing interest to the research community [62]. For virtual scenarios, most of the work has focused on more realistic walking experiences. The Real-Walk approach by Son et al. [53] simulates various surfaces by altering the viscosity of a shoe-like apparatus. Similarly, King et al. [57] combined visual with tactile vibrations to improve the realism of walking in VR. Strohmeier et al. [54] presented their bARefoot prototype capable of generating virtual walking surfaces through motion-coupled vibrations. Our work -exploring sneaking as an input modality -adds to the research dealing with the auditive aspect of walking. This research area is mostly centered around synthesizing or modifying the users' footstep sounds as part of the overall soundscape. For instance, Tajadura et al. [55] showed that modified walking sounds alter the self-perception. Also, Kern et al. [28] reported the positive effects of synchronized step sounds on presence and realism. For a broader view on the interplay between synthesized footstep sounds and immersive soundscapes, we point to the extensive work by the Medialogy Department at Aalborg University Copenhagen [41,49,59]. The closest related work in this field is the VRSneaky approach by Hoppe et al. [20]. The authors use shoe-attached trackers to play gait-aware walking sounds in a stealthy IVE to provoke a gait-change and achieve an increased presence. While these works underline the importance of plausible soundscapes, including synchronized walking sounds, our work concentrates on the potential of the users' sneaking behavior as a novel input modality.

DEVELOPING THE SNEAKING MECHANISMS
While past research has already dealt with capturing the users' walking behavior and using this information in virtual environments, these approaches mainly aimed to achieve a realistic soundscape.
In contrast, our mechanism should translate the users' gait into a discrete state, i.e., differentiating between walking and sneaking. This processed information would form the basis for our novel input modality. From the very start of our design process, we decided to start from scratch and refrain from using any auditory walking feedback with our mechanism. Existing research, such as VRSneaky [20], have already demonstrated the benefits of precisely synchronized footstep sounds for presence and gait awareness. We wanted to focus entirely on the interactional aspect and determine the necessary tracking fidelity needed for a plausible sneaking mechanism.
Based on this goal, we determined three main requirements for the target implementation. Firstly, the mechanism must be able to differentiate between the two states walking and sneaking. We do not distinguish between walking and stomping, as both share the same source, i.e., stepping with normal force, and the same effect, i.e., attracting attention. Secondly, the used tracking mechanism must deliver robust signals to determine the active state independent of the users' physiologies, walking behavior, and other environmental factors, i.e., ground, footwear, or noise. Finally, the chosen tracking method must not impede the users' movement in the real world in any way. This constraint also applies to hardware that might alter or diminish the fine-graded foot movement necessary for sneaking.
Considering these prerequisites, we started by capturing the real step sounds emitted by the users. Therefore, we attached Bluetooth microphones to the users' ankles and used the transmitted audio volume to extract the users' gait. This approach is the exact realization of the abstract idea behind our work. The lightweight microphones guarantee an easy setup that is not intervening with the actual gameplay. However, external interferences and individual differences between users are only partially removable by filtering. Eager to find a better alternative, we experimented with various other approaches. In particular, we shifted our focus from measuring the exact sounds to detecting the foot motions during sneaking.
Compared to other alternatives, such as force-sensing resistors, our final implementation uses the existent precise VR tracking environment and only requires a pair of HTC Vive trackers attached to the users' feet. This setup does not influence the individual sneaking movement and provides seamless and quick integration with the overall VR system. As with every sensor device, minor tracking errors and inaccuracies might occur from time to time. Also, using the trackers' exact positions to determine the foot's touchdown would require precise calibration as every users' feet are different. However, we found that these issues are avoidable by rethinking the definition of silent footsteps. When a foot is placed on the floor, the ground slows its speed to zero. The faster a foot is slammed down, the more noise is produced. Thus, the step sounds are directly dependent on the decrease in velocity.
Plotting the decrease in velocity over time reveals the users' gait. Note that we isolate the deceleration alone: The resulting peaks correspond to when the users place their foot on the floor. These measured values vary only minimally across different users, making it possible to determine global thresholds for different types of gait (see Figure 2). While this approach is immune to typical noise sources, such as random foot movements or physiological differences, we noticed that minor tracking errors might still trigger an unexpected peak. We solved this impediment by adding a small sliding window to eliminate single erroneous frames. After all, this tracker-based approach has a minimal impact on the movement and provides a reliable and precise tracking of the users' gait.
During the design process of our first implementation, we learned that it might be beneficial to use a more abstract approach instead of measuring walking sounds directly. The result stays the same: we can detect whether users are walking or sneaking. Next, we asked ourselves: Do we even need to track individual steps? When testing our early prototypes, all test users shared one similarity when sneaking: they walked slowly. While it would certainly be possible to sneak quietly without sacrificing much of the original walking speed, we usually measured a significant decrease in general velocity during our trials. It seems that this observation is tightly associated with the users' expectations. Thus, we designed our second approach to measure the overall walking speed using the horizontal velocity of the HMD. The threshold, determining whether users sneak or walk, was chosen based on the tracking data of our pre-tests. Like the first tracker-based mechanism, we added a sliding window to account for tracking issues and the head's micro-movements. Apart from that, both approaches work almost identical.
The main difference between our two implementations is the loss of tracking fidelity. Only the first technique can detect the actual gait, whereas the second mechanism relies on an implicit observation. Nonetheless, both approaches are body-based interactions and are compatible with natural walking, which is generally seen as the best locomotion technique for virtual environments [61]. In contrast, existing stealth VR-games are geared to sneaking mechanisms of established non-VR games. These games tend to use a binary stealth mode that is triggered using a hardware button. Players are slowed down and become harder to detect by the NPCs. Of course, this approach requires a virtual locomotion technique to control the player's position and movement. While not entirely comparable to our walking-oriented mechanisms, we decided to add gamepadbased sneaking as a third baseline implementation. This approach uses a continuous joystick movement and introduces a dedicated button triggering the sneaking mode. While sneaking, users are limited to a lower velocity that does not attract attention. It is worth noting that this mode is optional, as users might use the joystick carefully enough to achieve the same effect.
Altogether, our design and implementation phase leaves us with three different approaches to detect sneaking: • Tracker: ankle-attached trackers measure the foot's deceleration • HMD: HMD's movement is used as a proxy for the users' speed • Gamepad: joystick locomotion and button-controlled sneak mode

DESIGNING SNEAKING-BASED INTERACTIONS
Apart from developing the technical basis for measuring the users' gait, it is crucial to design gameplay elements and interactions that utilize the novel input channel. On the surface, our sneaking mechanism appears to be a simple binary differentiation: If the players walk carefully enough, everything is fine. Otherwise, they are detected.
In this regard, sneaking is very similar to hiding visually from enemies. Both mechanisms build on top of the normal locomotion in the virtual scenario. However, they differ in the underlying challenge. Hiding behind obstacles and avoiding a direct line of sight is a complex body-based task. Players must pay attention to the positioning of all body parts, i.e., not letting a limb peek out of the coverage. On the other hand, sneaking does not constrain the players' position but requires careful movement. Thus, hiding is challenging the where to move and sneaking the how to move. Both mechanisms are often used in conjunction to increase the overall difficulty.
Besides this famous coalescence, sneaking might be combined with other interaction patterns to obtain interesting challenges and vary the degree of difficulty. We subdivide these patterns into two groups: reinforcing and contradicting elements. A task is called reinforcing if it intensifies the players' attention on their movement. Typical examples include stepping over obstacles or crouching behind barriers. These tasks add an additional movement challenge forcing the players to focus even more on every step. Conversely, contradicting gameplay elements split the players' attention between the newly emerged challenge and the active sneaking task. For instance, getting past patrolling guards requires spatial understanding and precise timing, while players still must avoid getting heard.
Finally, the switch between quiet sneaking and loud walking itself is another potential gameplay element. A common feature found in almost every stealth game is the capability of producing sound on purpose. Whistling or stomping may attract attention and lure enemies to desired spots. In essence, this interaction combines the known gameplay elements. Stomping is another type of reinforcing action, as it requires stopping sneaking for one single step. Next follows a typical contradicting time-based task, e.g., guards investigating the noise's source. Thus, we consider such composite features to be more complex than their primary counterparts.

EVALUATION
We conducted a study to evaluate our three proposed sneaking techniques using a between-subject design. We were primarily interested in the general acceptance of our mechanisms and the differences in enjoyment, presence, tension, difficulty, and necessary effort. Therefore, we designed a VR stealth game that consisted of multiple short levels, each focusing on one of the introduced interactions.

Research Questions and Hypotheses
The study's main goal is to explore the differences between the three implementations Tracker, HMD, and Gamepad. In this context, we refer to both of our two proposed approaches, HMD and Tracker, as full-body movement-based interactions. We hypothesize that these techniques, resembling real sneaking, benefit the perceived presence. Additionally, such gait-based interactions force the players to pay attention to every step they take. Consequently, we expect a significantly higher physical effort compared to the Gamepad controls. Also, we assume an overall increase in task complexity. Despite these difficulties, we do not expect a lower success rate. Instead, the novel challenges are likely to increase the players' tension and enjoyment. All in all, our hypotheses are as following: Apart from these four hypotheses, we are also interested in how the players perceive the different sneaking techniques: Are the controls easy to learn and usable? How do the techniques compare to real sneaking? Finally, we want to use the insights from the hypotheses, logged gameplay data, and participants' feedback to compare our two proposed approaches against each other. We summarize both aspects into two additional research questions: • RQ1: How do players assess their particular sneaking technique regarding usability, learnability, and realism? • RQ2: Are there notable differences between the two proposed walking-based approaches HMD and Tracker?

Scenario
We realized the stealth game, used for comparing the different sneaking techniques, with the Unity game engine [60]. The setting is futuristic and highly technological, including teleports and patrolling robots (see Figure 3). The players take the role of a spy who must steal a tablet with confidential information hidden somewhere in the level. Since two of our sneaking mechanisms rely on natural walking, we restricted the virtual environment's size to match our real play area's boundaries, i.e., 16 m 2 . Each of the ten consecutive levels is structured similarly: The players enter the room using a teleporter, which serves as a loading screen. While obstacles, e.g., crates, walls, or laser barriers, differ each time, at least two elements are found in every level: the target tablet and a sentinel robot. This guard is the main antagonist in the game. If players fail to sneak while walking through the level, they attract attention to their position, causing the robot to investigate the noise's source. If the robot detects the players visually, a bar indicating the alertness level begins to fill. Similar to other games, only the HMD's position is used to determine visibility. Players who fail to interrupt the robot's line of sight will be caught and must restart the level. Therefore, players must do their best to stay unseen and unheard. In the case of detection, the environment offers various corners and blinds that help the players hide and wait for the guard to stop searching. Additionally, we provide a holographic noise indicator attached to the hand, informing the players whether they are sneaking quietly enough. As only one condition involves positional foot tracking, we refrain from visualizing feet or body to assure comparability. Also, prior research already covered the effects of displaying virtual limbs [42].
While walking through the level and locating the tablet, the players have to overcome various challenges and obstacles. These are designed carefully to introduce new gameplay concepts one at a time. In the beginning, players only need to sneak to avoid the guard, who is looking out of a window. Subsequently, we add the guard's lookout, time-based patrols, dynamic obstacles, and crouching activities. A complete list of the mechanisms used in each of the ten levels is depicted in Table 1. After retrieving the tablet, the players must return quietly to their starting point. They are then teleported back to a waiting room where they start the next level.

Procedure and Applied Measures
We conducted a between-subject study splitting the participants randomly into three groups, each using one of the proposed sneaking techniques. In the beginning, we considered a within-subject design to collect qualitative feedback comparing the different implementations. However, the necessary repetition of gameplay elements paired with the general similarity between the sneaking approaches would have led to unwanted sequence effects.
We executed the study in our VR lab using an HTC Vive Pro Wireless setup [22]. On average, the study took 45 minutes. At first, the participants were informed about the overall process and completed a general questionnaire assessing gender, age, gaming behavior, and prior VR experience. We also administered the Immersive Tendencies Questionnaire (ITQ) [67] to determine the ability to get immersed in fiction. At last, we introduced the participants to the VR hardware and assisted them in putting on the hardware.
The participants started the game in a waiting room, where they were introduced to the controls needed to complete the levels. While there was no guard present in the waiting room, the subjects could use their holographic noise indicator to test the particular sneaking technique. We did not limit this introductory phase, which usually only took one to two minutes. After getting used to the controls, the subjects entered the first level by stepping on the teleporting device and returned to the waiting room between every level. We logged the relevant statistics, such as the overall playtime or the number of detections, to analyze the players' performance.
After completing the final level, the subjects removed the HMD and filled out a series of questionnaires regarding their experience. For administering the feeling of presence, we used the Presence Questionnaire (PQ) [10,67] focussing on interaction-related presence. It contains five subdimensions, each rated on a 7-point Likert scale (coded 0 -6): realism, possibility to act, quality of interface, possibility to examine, and self-evaluation of performance. We also included the challenge construct of the Player Experience Inventory (PXI) [1] and two subscales of the Intrinsic Motivation Inventory (IMI) [48]: interest/enjoyment and pressure/tension (coded 0 -6).
For assessing the mental and physical effort, we used the NASA Task Load Index (NASA-TLX) questionnaire [17]. The two chosen subscales mental demand and physical demand are rated on a 100point scale with 5-point steps (coded 0-99). Finally, we also included the Simulator Sickness Questionnaire (SSQ) [27] with its three subscales nausea, oculumotor, and disorientation. While we expected to find certain differences in cybersickness, these should relate to the different locomotion techniques, i.e., walking and gamepad, and not to the sneaking mechanism itself. The questionnaires were accompanied by a set of custom questions (coded 0 -6) to gain further insights into the participants' experiences with the sneaking mechanisms (see Table 3). We finished the study by allowing the subjects to share their opinions in a semi-structured interview.

RESULTS
In total, 45 persons (19 female, 26 male) participated in our study with a mean age of 24.64 (SD=3.13). Most of the subjects played digital games a few times a month (93%) and had already used VR systems before (78%). However, only a minority of 11% reported using VR regularly. All participants were randomly split into three study conditions. We did not find any significant discrepancies between these groups regarding age, gender, prior VR experience, or immersive tendencies (all p > .05). As we searched for differences between the three independent groups, we performed one-way analyses of variances (ANOVA) for all measures. Therefore, we ensured normal distribution with Kolmogorov-Smirnov and homogeneity of variances using Levene's tests. In cases where the data did not meet the latter requirement, we used Welch's ANOVA instead. Depending on Levene's test results, we chose either Tukey's or Games-Howell tests for posthoc comparisons. For legibility reasons, we only report significant differences between the conditions, including all necessary information to ensure reproducibility [64].

Questionnaires
We assumed that the walking-based implementations lead to higher enjoyment and tension levels. Table 2  Moreover, we compared the perceived presence between the three study conditions using the PQ questionnaire. As shown in Table 2, only the measure for experienced realism and the total presence score indicate a significant difference. Further, we wanted to assure that potential cybersickness induced by locomotion would not impede our study. The results of the SSQ are listed in Table 2. The values for the Gamepad condition are significantly higher than for the HMD condition (nausea: p = .018; 95% CI[4.882, 59.990], disorientation: p = .023; 95% CI[4.999, 69.241]). We presume that this difference is related to the used locomotion technique rather than the sneaking mechanism. Most importantly, the values across all groups are low compared to Kennedy et al.'s reference values [27], thus not indicating significant problems with cybersickness in any of the three conditions.
To test our hypotheses, we also assessed individual subscales of the NASA-TLX and PXI. The resulting means and standard deviations are listed in Table 2

Custom Questions and Logging Data
To better understand the participants' expectations and experiences, we also assessed several custom questions. These questions covered three aspects: realism, usability, and liking. Table 3 lists the means, standard deviations, and ANOVA results. In particular, the performed one-way ANOVA reveals notable disparities for five of the ten custom questions. For CQ1, posthoc tests indicate that the Tracker mechanism felt more realistic than the Gamepad approach  Finally, we also analyzed the data logged during the play sessions: the total playtime, the number of detections by the guard, and the number of level restarts (see Figure 4). Among those, only the playtime differs significantly across the groups. Compared to the Gamepad condition, subjects in the HMD group played 23% longer (F(2, 26.33) = 9.410; p = .014; η 2 = 0.327; 95% CI[29.808, 293.276]), and participants using the Tracker approach played even 50% longer (F(2, 26.33) = 9.410; p = .002; η 2 = 0.327; 95% CI[129.543, 580.650]). However, this discrepancy was not caused by substantial differences in detections or level restarts.

DISCUSSION
Regardless of the used sneaking technique, the majority of players enjoyed participating in our study. Subjects explicitly mentioned the potential of sneaking-based interactions for immersive experiences. According to their feedback, this type of gameplay conforms to the key advantage of VR by allowing to "become someone completely different -like a master spy"(P29). Most subjects wanted to play more levels (CQ8) and were interested in other sneaking-based VR games (CQ9). But how do the different implementations compare? Where are the individual strengths and weaknesses? Our four hypotheses and two research questions cover the various aspects of player experience and usability necessary to answer these questions.
H1: In comparison to the Gamepad condition, the Tracker and HMD approaches significantly increase the perceived presence. The results from the PQ indicate that the subjects experienced high levels of presence across all three conditions. However, the two movement-based techniques both scored higher regarding experienced realism. This finding supports our primary research goal of creating a natural and realistic sneaking experience for IVEs. Interestingly, the HMD condition got even minimal higher values for realism and total presence than the precise tracker-based approach. Players in the HMD group even reported having the feeling that "the guard would hear every loud step immediately"(P5). It seems that most participants did not notice the inferior tracking fidelity.
H2: The full-body conditions require a significantly higher physical effort compared to the Gamepad controls. One potential difficulty introduced by our proposed mechanisms is the additional physical demand. The requirement of cautiously placing every foot increases the necessary physical effort for the Tracker condition significantly. While the values for the HMD condition were also higher than for the Gamepad group, this difference was not significant. Also, VR experiences do not necessarily suffer from demanding full-body interactions. In contrast, several participants appreciated the novel challenge as it forced them "to be fully aware of the own body"(P34). Especially the tracker-based approach caused the subjects to feel very active (CQ6) and was sometimes as demanding as an "exergame"(P1).
H3: The Tracker and HMD conditions significantly increase task difficulty but not the success rate. The result from the assessed PXI subscale indicates that our two proposed approaches increased the game's challenge significantly. Since both mechanisms are movement-based, players had to stay cautious and canny even in stressful situations. This conflict was especially noticeable when players got detected and had to outsmart the guard to avoid failing the level. Several participants reacted hectically, which sabotaged their goal and usually forced them to restart the level. As a consequence, the players progressed more slowly and carefully. While the subjects' cautious behavior increased the overall playtime, it had no notable effects on the success rate or enjoyment. Since developers typically seek this kind of behavior in stealth games, we consider our approaches' increased challenge to benefit the intended genre.
H4: Movement-based sneaking significantly boosts players' enjoyment and tension compared to the Gamepad approach. The study's results confirmed our fourth hypothesis only partially. Regarding the participants' enjoyment, we did not find any notable difference between the three groups. Nevertheless, the high scores of the IMI subscale indicate an overall pleasant experience. Especially in the groups using real walking, players sometimes described the gameplay as "if you were a secret agent in a blockbuster movie"(P9). Additionally, the tension subscale revealed that our two proposed techniques elicited a significantly higher tension than the gamepad controls. While there is no considerable difference between the more accurate tracker-based mechanism and the more abstracted HMD approach, the results still underline the general advantage of body-based sneaking. These outcomes are also reflected in the oral feedback: "it is extremely thrilling to play hide-and-seek with the guard after already being detected"(P22).
RQ1: How do players assess their particular sneaking technique regarding usability, learnability, and realism? In general, most participants learned to use the particular sneaking technique very quickly. The concepts behind each mechanism were understood intuitively (CQ3) and did not require additional assistance from the study coordinators. Especially the visual noise indicator, attached to the players' hand, was mentioned as a major aid as it helped to "gain a feeling for the own loudness"(P14). After the first levels, the participants mostly "learned the acceptable threshold by heart"(P10) and reduced their use of the display.
Since all three sneaking techniques work differently, the players' difficulties and problems varied as well. Some of the subjects using the gamepad approach reported being challenged by pressing multiple buttons simultaneously, e.g., taking the tablet while sneaking. In particular, participants with no prior VR experience tended to utter this concern. In the other groups, players had to pay more attention to their movement. Later levels increased this challenge by adding obstacles requiring precise timing or crouching. As this hurdle is primarily relevant for the tracker-based approach, subjects in this group had significantly more problems (CQ5). However, it is worth noting that only very few players reported being overstrained (CQ5) or preferring a different technique (CQ7).
Apart from usability and learnability, we were also interested in the realism of our proposed techniques. How do they compare to real sneaking? In general, players tend to adapt to simplifications and abstractions in gameplay elements and usually ignore implausibilities for the sake of a coherent game experience. Therefore, it does not surprise that the participants mostly rejected CQ2. However, asking them personally, subjects articulated more diversified feedback. Especially the binary sneak mode of the Gamepad condition "did not feel like sneaking but cheating. I stopped using it and controlled my speed manually"(P3). For the tracker-based sneaking, players liked that "every step is relevant. I could even stomp to attract attention on purpose"(P28). This feedback is reflected in the significant difference regarding the realism of the sneaking technique (CQ1).
RQ2: Are there notable differences between the two proposed walking-based approaches HMD and Tracker? Our proposed implementations fit their intended purpose and provide valuable benefits. Compared to established controls, these approaches can increase the perceived presence, tension, and challenge without causing frustration or exhaustion. However, generally speaking, both proposed techniques performed very similarly, despite the differences in tracking precision. While the accurate tracker-based approach offers some advantages over the HMD abstraction, e.g., more realism and physical activity, these did not significantly impact the player experience. In contrast, the feedback for the Tracker condition was more ambiguous than the overall positive HMD feedback.
The oral feedback points towards the most likely reason: with the hardware trackers, players must pay attention to every single step they take. In contrast, the HMD approach focuses on the players' intentions. Precisely speaking, the mechanism is based on the assumption that sneaking players walk slowly. Despite being unaware of the actual implementations, players intuitively understood this concept. The HMD approach delivers a comparable experience to precise tracking while requiring less attention and being more forgiving. Therefore, it might fit the players' expectations better.
Furthermore, the HMD implementation relies only on standard hardware and does not require any additional tracking devices. Considering both properties, we conclude that the HMD-based approach is most suited for consumer-oriented experiences, i.e., VR stealth games. In contrast, the hardware trackers can guarantee far more precise footstep tracking necessary for enhanced realism and additional gait-based interactions that are not possible with the HMD abstraction, e.g., stomping. The technique also builds upon Vive's marker-based tracking and is therefore easily applicable to every VR scenario. These benefits make our approach valuable for other use-cases as well. For instance, accurate footstep tracking is useful for a variety of physical activities such as dancing or in specific simulation or training applications.

LIMITATIONS
In our study, we compared our two movement-based approaches against the commonly used gamepad controls. This decision was motivated by the observation that current stealth VR-games tend to rely on button-controlled sneak modes and joystick locomotion. Nevertheless, the chosen study setup raises the question of whether our findings may instead originate from this difference in locomotion techniques. While we indeed attribute a notable influence to the particular navigation method, the overall low levels of cybersickness paired with the similar enjoyment levels indicate a comparable user experience across the groups.
Further, we focussed entirely on the fundamental sneaking mechanism, comprising a simple binary differentiation between walking and sneaking. Consequently, more complex interaction patterns, such as the introduced stomping concept, were not included in the study scenario. Especially stomping is an interesting concept, as it introduces an additional degree of input fidelity, namely exceeding the sneaking-threshold deliberately. However, such interactions are not easily realizable for the Gamepad and HMD approaches without adding additional buttons. Since this step would have introduced an additional variable for our study, we decided to test the basic sneaking concept in isolation.
Finally, we decided against any avatar visualization except for the players' hands. This decision was mainly motivated by the differences in tracked devices: Only one condition featured positional feet tracking. Therefore, displaying virtual feet would have introduced an additional variable to our study. Instead, we point to the existing work on virtual avatars as the underlying effects were already extensively covered. Similarly, we decided to base our detection algorithms solely on the visibility of the HMD. Thereby, we assured comparability and avoided frustration caused by peeking limbs. Nevertheless, using the players' fully tracked and visualized bodies for the detection mechanism might significantly influence the players' behavior and the measured effects.

CONCLUSION AND FUTURE WORK
Virtual reality games provide the unique opportunity to slip into the role of the own favorite character and experience a thrilling adventure first-handed. One of these stories may involve a top-secret agent on his almost impossible mission to save the world. Therefore, the agent must infiltrate a restricted area and secure confidential files. While players can already encounter similar plots in available VR games, these often lack to convey a satisfying stealth experience. In most cases, players only need to stay out of sight of the probably deaf guards. Stepsounds rarely have any influence on the gameplay. This simplification does not use the full interaction fidelity of sneaking activities and limits the achievable scope of realism.
With our work, we have explored the potential of sneaking as a novel input modality for such IVEs. Therefore, we developed two gait-oriented mechanisms to capture the users' gait. The first measured the feet's deceleration, while the second used the average HMD speed as a proxy. We then compared the two approaches against the established gamepad controls. Our study's results revealed three interesting takeaways: 1. The experiments confirmed that players generally appreciated sneaking-based gameplay elements.
2. Our proposed implementations increased the perceived presence, tension, challenge, and physical activities without overcharging or exhausting the players.
3. Both approaches performed very similarly, despite the differences in tracking fidelity and degree of abstraction. In most cases, it is not necessary to capture exact foot movements, as the HMD-based implementation provides a similar experience.
In our future research, we will concentrate on further use-cases of the proposed interaction concepts. In particular, our tracker-based mechanism opens interesting research directions. It enables precise detection of the users' steps, which could be used for other movement-intense activities, such as dancing. While we mainly focused on differentiating walking and sneaking, our tracking mechanism was also capable of detecting stomping and jumping movements. In the future, we want to extend this concept to identify more types of gait. Especially training simulations could profit from this capability to provide individual gait-understanding feedback. Finally, we aim to combine the proposed gait-based sneaking with additional channels, namely synchronized audio feedback, voice detection, haptic feedback, and full-body tracking, to achieve a fully lifelike sneaking experience.


extfieldsofstudy:
Computer Science
Medicine

text:
A Modified Sparrow Search Algorithm with Application in 3d Route Planning for UAV

The unmanned aerial vehicle (UAV) route planning problem mainly centralizes on the process of calculating the best route between the departure point and target point as well as avoiding obstructions on route to avoid collisions within a given flight area. A highly efficient route planning approach is required for this complex high dimensional optimization problem. However, many algorithms are infeasible or have low efficiency, particularly in the complex three-dimensional (3d) flight environment. In this paper, a modified sparrow search algorithm named CASSA has been presented to deal with this problem. Firstly, the 3d task space model and the UAV route planning cost functions are established, and the problem of route planning is transformed into a multi-dimensional function optimization problem. Secondly, the chaotic strategy is introduced to enhance the diversity of the population of the algorithm, and an adaptive inertia weight is used to balance the convergence rate and exploration capabilities of the algorithm. Finally, the Cauchy–Gaussian mutation strategy is adopted to enhance the capability of the algorithm to get rid of stagnation. The results of simulation demonstrate that the routes generated by CASSA are preferable to the sparrow search algorithm (SSA), particle swarm optimization (PSO), artificial bee colony (ABC), and whale optimization algorithm (WOA) under the identical environment, which means that CASSA is more efficient for solving UAV route planning problem when taking all kinds of constraints into consideration.

Research Background
The three-dimensional (3d) route planning for unmanned aerial vehicle (UAV) can be considered as a multi-constraint global optimization problem [1], and the main purpose of this problem is to search for the optimal route from the departure point to the target point autonomously according to the task requirements and the flight constraints. In recent years, with the broad use of different kinds of UAV, this problem has drawn widespread attention from researchers.
In recent years, various approaches have been put forward for solving this complex optimization problem, such as A* algorithm [2], rapidly exploring random trees [3], potential field based method (PFM) [4], genetic algorithm (GA) [5], linear programming [6], and artificial intelligence guidance [7]. These methods can be classified as deterministic algorithms and non-deterministic algorithms. Obviously, most of the practical engineering problems have many local optimal solutions [8,9]. Although deterministic algorithms are quite mature in mathematical theory, there also exists the problem that they are less effective in dealing with discontinuous and non-derivative functions, and they are easily trapped into local optimal solutions when solving the UAV route planning problem with multiple constraints [10]. Due to those problems that deterministic algorithms have, researchers have begun to pay more attention to heuristic algorithms. The most important feature of the heuristic algorithm is that it introduces a stochastic approach, which provides the opportunity to get rid of the local optimal solutions. Compared with classical methods, the heuristic algorithms require less computation due to their independence of initial conditions. In general, it is significant to use heuristic algorithms to obtain the optimal solution for global optimization problems.

Related Work
With the development of computer science, some heuristic algorithms have been widely applied to deal with UAV route planning problems. In Table 1, the recent relevant studies are shown as below. Table 1. Heuristic algorithms for UAV route planning.

Authors Algorithms Modified Strategy
Shin, J. et al. [11] Improved particle swarm optimization (PSO) algorithm Proposed the multiple balance strategy Cekmez, U. et al. [12] Multi ant colony optimization (MACO) algorithm Proposed the new information exchange strategy Li, B. et al. [13] Improved artificial bee colony (ABC) Algorithm Proposed the balanced evolution strategy Pan, J. et al. [14] Chaotic cuckoo search (CCS) algorithm Integrated the chaotic strategy into CS Pandey, P. et al. [15] Improved glowworm swarm optimization (GSO) algorithm Introduced the genetic operators of mutation and crossover into GSO YongBo, C. et al. [16] Modified wolf pack search (WPS) algorithm Introduced the mutation operators into WPS GaiGe, W. et al. [17] Improved bat algorithm (IBA) Combined the BA with Differential Evolution (DE) Wu, J. et al. [18] Improved whale optimization algorithm (IWOA) Proposed an adaptive chaos-Gaussian switching strategy ChenZhi, Q. et al. [19] Hybrid grey wolf optimizer (GWO) (HSGWO-MSOS) Combined the simplified GWO and modified symbiotic organisms search (MSOS) Jize, L. et al. [20] Modified PSO algorithm Introduced the genetic algorithm and chaos theory into PSO Inspired by the predatory behavior of sparrows, the sparrow search algorithm (SSA) is firstly proposed in Ref. [27]. As a heuristic algorithm, the SSA imitates the predatory activity and the escape activity of a sparrow group, which has better convergence performance than some other swarm-intelligence algorithms. Because of its few controlling parameters as well as easy implementation, SSA has been successfully used in various practical engineering applications. For example, Ref. [28] proposed a power flow management of a hybrid renewable energy source (HRES) with SSA. Ref. [29] used an improved SSA to solve the renewable energy system optimization problem. In Ref. [30], the authors combined the neural networks with the SSA for the obstacle avoidance. In Ref. [31], the authors proposed an adaptive SSA to identify the optimal parameter of proton exchange membrane fuel cell stacks.

Contributions
In this paper, a novel modified sparrow search algorithm called CASSA is proposed for solving this complex optimization problem. The modified method includes the following steps: (1) The chaotic strategy is used to enhance the randomness of the positions of the initial population; (2) an adaptive inertia weight is applied to balance the convergence rate and exploration capabilities of the algorithm; (3) the Cauchy-Gaussian mutation strategy is adopted to improve the capability to get rid of stagnation. The effectiveness of the proposed modified algorithm is verified through the comparison among it and other algorithms, including original SSA, PSO, ABC, and WOA. Finally, the modified SSA is successfully applied to search the best route in the complicated 3d environment for UAV. The final experimental results evidenced that CASSA has the most excellent capability among all the algorithms tested in this paper.
The structure of this paper is shown as below. In Section 2, the original sparrow search algorithm is described in detail; Section 3 shows the motivation of improving CASSA and its details, including the chaotic strategy, the adaptive weight parameters, and the Cauchy-Gaussian mutation; Section 4 conducts comparison experiments on some classical benchmark functions and evaluates the effectiveness of each part of the proposed CASSA; Section 5 introduces the mathematical model of UAV route planning in detail and shows the experimental results of this problem; finally, Section 6 concludes with an integrated summary of this paper.

Overview of Sparrow Search Algorithm
The original SSA is a heuristic algorithm motivated by the foraging and anti-predation behaviors of sparrow colony. This algorithm was put forward by Ref. [27] in 2020 and has drawn great attention recently. During the foraging process of sparrows, the colony is divided into finders and entrants. The finders have better fitness values and provide foraging areas and directions for the entire sparrow colony, while the entrants use the position of finders to get food. When the sparrow colony detects the danger and the alarm value exceeds the safety value, the sparrows will act against predation. The framework of original SSA is composed of the following three main parts.

Updating Finder Location
In the search process, the finders with better fitness values are given priority for getting food. As the finders have the responsibility to search for food and direct the movement of the whole population, they can find food in a broader range compared with other sparrows. During each iteration, the location of the finder is updated as below: where t represents the current iteration; n is the number of sparrows; d denotes the dimension of the variables; T max is the largest number of the iteration; X t i represents the position of the ith individual at iteration t; α ∈ (0, 1] denotes a random number; R 2 ∈ (0, 1] represents the alarm value and ST ∈ [0.5, 1) represents the safety threshold; L is a 1 × d matrix that each factor inside is 1; Q is a random number that obeys the normal distribution with mean 0 and variance 1; if R 2 < ST, it denotes that the foraging environment is safe, while R 2 ≥ ST signifies that some individuals have already encountered predators and therefore all sparrows need to fly quickly to other safe areas.
According to Equation (1), it can be seen that when R 2 < ST, the next generation of finder will move around the current position. Equation (2) reveals the variation in the range of values of the finder's position.
where x represents the iteration times, and y represents the range of value variation for finder's position. Figure 1 shows the distribution of a random value between 0 and y, which represents the change of the updated range of the finder's position when the foraging environment is safe. As x becomes larger, y gradually narrows slowly from (0,1) to approximately (0,0.3). When x is smaller, the probability of y taking on a value close to 1 is higher, and as x increases, the distribution of the values of y becomes more even. Therefore, when R 2 < ST, the range of value variation of each dimension of the sparrow is getting smaller. This search strategy makes the SSA extremely capable of local search, but it also leads to a tendency to fall into the local optimal solutions in the late iterations.

Updating Entrant Location
The rest of the sparrow colony are entrants, which monitor the finders frequently. As soon as they notice that the finder has found better food, they will quit their current position and fly to better foraging areas. The location of the entrants is updated as below: where X best denotes the elite individual position, i.e., the current best position; X worst is the current global worst position; A denotes a d × d matrix for which each factor inside is assigned 1 or −1 in random. When i ≤ n/2, it suggests that the ith entrant is foraging near the best location, if i > n/2, it means that the ith entrant with the worse fitness is needed to fly to another place for food.

Detection and Early Warning Behavior
In the colony, all sparrows have a scouting and early warning mechanism. Generally, the sparrows that are aware of the predator account for 15% to 30% of the colony. The mathematical model can be described as below: where β represents the random step length control coefficient, which obeys the normal distribution with variance of 1 and mean value of 0; K ∈ [−1, 1] is a random number; f i denotes the fitness value of the ith individual; f b denotes the current global best fitness; f w denotes the current global worst fitness; ε represents a smallest parameter to avoid the zero-division-error. When f i > f b , it means that the individual is at the edge of the colony.
If f i = f b , this indicates that the sparrows in the middle of the colony are aware of the danger and need to fly closer to the safe place.

Proposed Modified Sparrow Search Algorithm (CASSA)
According to the results of previous research, the original SSA has better robustness and rapid convergence speed [27][28][29][30][31]. However, some shortcomings still exist in SSA, such as being easily trapped into local optimal solutions and lower solution precision. The initialization strategy of SSA is a simple random method, which makes the performance of the algorithm largely depend on the diversity of the initialized populations. Additionally, in the late iterations of the algorithm, the sparrow group gradually clusters around the found optimal position, making it easily get trapped into local optimal solutions. Therefore, in order to further enhance the SSA's capability, some specialized strategies are adopted. The detailed definitions of CASSA are shown as the followings.

Chaotic Strategy
In solving complex optimization problems, SSA has the disadvantage of poor population diversity in the late iterations. Recently, chaotic sequences [32] have been applied to the intelligence algorithms in many optimization applications. For instance, in Ref. [33], chaotic sequences are applied to dynamically improve population size to avoid immature convergence; in Ref. [34], chaotic sequences are used in the generation of the initial population and the performance of the mutation operators. In this paper, chaotic sequences are used to improve the population diversity of SSA. Chaotic sequences can map by different chaotic models such as the Tent map, Logistic map, Kent map, and Cubic map. Ref. [35] demonstrates that the Cubic map has better uniformity than others. Therefore, the cubic mapping chaos sequences are adopted for the generation of CASSA population. The diversity of the CASSA's population is improved by the ergodicity and the initial sensitivity of the chaotic maps. The mathematical formula is described as below: where X i represents the individual variable values of sparrows; X lb and X ub correspond to the upper and lower bounds in the solution space, respectively; N represents the population size. Firstly, let D denote the dimension, and a D-dimensional vector with values of [−1,1] in each dimension is randomly generated as the first operator. Then Equation (5) is used to iterate over each dimension of the first operator to obtain the remaining (N−1) operators. Finally, Equation (6) is used to map the values of the operators generated by the cubic mapping onto individual of sparrows.

Adaptive Inertia Weight Strategy
Whether the SSA can find the optimal solution is largely determined by the search ability of the finder. The locations of individuals in the searching range are distributed at random. When there are no adjacent sparrows near the current finder, a random search strategy will be conducted. It should be noticed that this mode not only slows down the convergence speed, but also decreases the convergence accuracy under the limited number of iterations. For further improvement of the finder's performance, an adaptive inertia weight is introduced to Equation (7). The mathematical formula is described as below: where t is the current iteration times; T max represents the maximum iteration times; w is an inertia weight that adaptively decreases as the number of iterations increases. By introducing this inertia weight, the range of values taken by α is adaptively controlled. As is shown in Figure 2, at the beginning of the iterations, a larger value of w gives the algorithm a larger range of optimization. At the end of the iterations, a smaller value of w is conducive to enhancing the convergence accuracy of the algorithm.

Cauchy-Gaussian Mutation Strategy
In the late iterations of SSA, sparrows gradually move closer to the optimal individuals, which leads to a lack of population diversity and a tendency for the algorithm to converge prematurely. For solving this problem, the Cauchy-Gaussian mutation strategy [36] is introduced in this paper. The individual with the best current fitness is selected for mutation. Then, its positions before and after mutation are compared, after which the better position is chosen to enter the next iteration. The mathematical definition of the Cauchy-Gaussian mutation strategy is described as below: where X best is the elite individual position, U t+1 i represents the position of the elite individual after mutation, σ 2 represents the standard deviation of the Cauchy-Gaussian mutation strategy. cauchy(0, σ 2 ) is a random variate satisfying Cauchy distribution, and Gauss(0, σ 2 ) is a random variate satisfying Gaussian distribution. λ 1 = 1 − t 2 /T 2 max and λ 2 = t 2 /T 2 max are the dynamic parameters that are adaptively adjusted with the times of iteration. In Equation (9), λ 1 is larger at the initial stage so that the algorithm can explore the optimal solution in a larger range with a larger mutation step. λ 2 has a small mutation step, which facilitates the algorithm to search near the optimal solution. During the search process, λ 1 decreases gradually, while λ 2 keeps increasing. The flowchart is shown in Figure 3, and the detailed implementation procedure of CASSA is illustrated in Algorithm 1. Update the finder's position using Equation (7); 12. end for 13. for i = (F d + 1) : n 14.
Update the threatened sparrow's position using Equation (4)

Experiment for Benchmark Functions
In this section, there are four tested functions shown in Table 2, and the trajectories of individuals of CASSA in these test functions are presented in Figure 4. It shows that most individuals move towards the global optimum in unimodal functions. However, in the more complex multi-modal functions, although many individuals stagnate at the local minimums, some individuals can still avoid them and aggregate towards the global optimum. To verify whether it is feasible and highly efficient, the proposed CASSA is compared with four algorithms in the experiments, including original SSA, PSO, ABC, and WOA. There are twelve classical benchmark functions [37] shown in Table 3, which consists of the information of their formula, initialization range, and global optimum. Among these benchmark functions, f1∼f6 are unimodal functions, and f7∼f12 are multi-modal functions. In all cases, we conducted the independent trials 30 times on each benchmark function. The maximum number of iterations is 500, and the population size is 50 in each experiment. Finally, we obtained the best value, mean value, and the standard deviation (Std.) of the objective function values. With the same benchmark function, the best value and average value denote the exploration ability and convergence accuracy, respectively, and the standard deviation denotes the stability of the algorithm. The experimental results are shown in Figure 5 and Table 4.
As is shown in Figure 5, in the experiments on unimodal functions, CASSA can quickly find the optimal values of f1, f2, f5, and f6. Although the optimal values of f3 and f4 are not found, CASSA still has the fastest convergence speed and accuracy among all the tested algorithms. In the experiments on the multi-modal functions, only CASSA and SSA can find the optimal values of f7. For f8, f9, f10, and f12, CASSA, SSA, and WOA can find the optimal values, but CASSA requires the smallest iteration times. For f11, all algorithms fail to find the optimal value, but CASSA still finds the near-optimal solution with the highest accuracy.

Name Definition Domain Optimum/Minimum
Ackley

Name Definition Domain Optimum/Minimum
Sphere      In terms of convergence value and convergence speed, CASSA is better than the other four test algorithms. As is shown in Table 4, the test results of unimodal functions and multi-modal functions show that the mean and variance of CASSA are much smaller than those of the other four algorithms, which shows that the optimal values obtained by the algorithm are highly stable and robust and can be effectively implemented to avoid premature convergence.
With the purpose of further assessing the performance of these heuristic algorithms and proving a significant improvement of CASSA compared with the other four algorithms, a non-parametric statistical test is performed with the Wilcoxon [38] rank sum test set at a significance level of α = 5%. It is generally considered that when p < 5%, it is significantly different, while when p ≥ 5%, it is not significantly different. As is shown in Table 5, p of CASSA are all less than 5%, which means that compared with the search ability of SSA, that of CASSA has been greatly improved. Additionally, the optimization accuracy and robustness of CASSA are better than other popular intelligent algorithms.

UAV Route Planning Strategy
In this section, the application of CASSA to 3d UAV route planning will be discussed in detail. The UAV route planning aims to minimize the cost function in the task space, which can be defined as an optimization problem with multi-constraint. Generally, the UAV route generated by meta-heuristic algorithms is composed of the line segments, which is unsuitable for exact flight. To solve this problem, some methods are used to further optimize the route generated, such as the B-spline curve [39], the Bezier curve [40], and the simple circular arcs [41]. The B-spline curve has the unique superiority in many ways, such as locality, geometrical invariability, symmetry, recursion, continuity, convex hull characters, and convexity-preservation. It is highly appropriate to use the B-Spline curves in the process of optimization, because merely a few variables are required to define the complex curved routes. Therefore, in this paper, the B-Spline curves smoothing strategy is used to smooth the generated route. With the given departure point and target point, some control points in the map space are set and applied to generate the B-Spline curve. The points on the B-Spline curve serve as the waypoints, of which the coordinates can evaluate the cost of the UAV route.

B-Spline Curve
The construction of B-Spline curve is made up of blending functions, which denotes that B-Spline curve is a parametrized curve. In a whole route, the number of waypoints is n, the number of control points of the corresponding curve is n + 1, with the coordinates (x 0 , y 0 , z 0 ), . . . , (x p , y p , z p ), . . . , (x n , y n , z n ); then, the coordinates (x e , y e , z e ) of the B-Spline curve can be defined as follows: where p represents the order of the curve, which influences the smoothness of the B-Spline curve; the free parameter e varies from 0 to n − p + 1, which generates a series of discrete points. The blending functions are designed by a knot vector E = {e 0 , . . . , e m } recursively as follows: The B-Spline curve is used to determine the flight route, and it has the advantage of illustrating a complex non-monotonic 3d curve with controlled smoothness through a few designed parameters. Figure 6 shows a 3d cubic B-Spline curve (k = 3) with its control points and the corresponding control polygon (the green line). After this procedure, the original route (the blue line) could be replaced by the new smooth route (the red curve).

Cost Function
The problem of UAV route planning is defined by a series of optimization criteria and constraints, which consist of the minimization of the threats of damage of the UAV, the constraints imposed by the UAV's dynamic property and the flight environment. The cost function is described as the total of three functions, given as follows: where J cos t represents the total cost function; J path denotes the length cost of the route of UAV; J height denotes the height cost of UAV; J turn denotes the smoothness cost of the planning route; w i is the weights of the above functions, which are given as follows: In the process of UAV route planning, it is obvious that the shorter route needs less time and less fuel consumption for flight. In the meanwhile, it is less likely to encounter an unknown danger. The route length is calculated with the following expressions: where (x i , y i , z i ) denotes the i th waypoint within the whole UAV route. If the line segment between every two waypoints passes the obstacles, the cost of the route needs to be processed by the penalty function. However, it is hard to express the infinite function in the practical experiment. Therefore, a large value, like 10 7 , can be added to solve this problem in the simulation.
In the meantime, the suitable flying height also has an important impact on the UAV route planning process. For most kinds of UAV, the flying height should not be changed too frequently and drastically. The stable flying height can save more fuel and ensure more security. Additionally, when UAV flies at a low height, it can benefit from the terrain mask effect, which can help to avoid unknown threats [42]. Therefore, the cost function of height is described as below: The stability and maneuverability of UAV are constrained by the maximum turning angle at each waypoint. In the process of UAV route planning, the maximum turning angle should not be bigger than the maximum preset angle. Furthermore, when the UAV flight efficiency is considered, it is obvious that the UAV work condition will be inefficient when UAV does the turning maneuvers. The cost function of the turning angle can be defined as below: where ϕ denotes the maximum angle; θ denotes the current angle; and a i represents a vector of the ith part of the whole route.

CASSA for 3d UAV Route Planning
After the above discussion, the detailed implementation procedure of CASSA for UAV three-dimensional route planning is illustrated in Algorithm 2, and the flowchart is shown in Figure 7. Algorithm 2 CASSA for 3d UAV route planning /*Initialization*/ 1. Set the parameters of CASSA same as Algorithm 1; 2. Set the start point (x S , y S ), target point (x T , y T ), the boundaries of the map space, and the number of control points n; 3. Set the position(x threat , y threat ) and the range of threats; /*Iterative search*/ 4. while (t < T max ) 5. Each sparrow represents a route; sort the population of sparrows from best to worst by order of cost function Equation (10) for each sparrow 6. G = rand(1); 7. for i = 1 : F d 8.
Update the threatened sparrow's position using Equation (4); 15. end for 16. Evaluate the cost for each route by Equation (13), then select the top S elite sparrows with the best fitness value and implement adaptive mutation for them by Equation (9)

Simulation Experiment
In this section, the capability of CASSA in solving the 3d UAV route planning problem will be assessed by a series of computational simulations. To conduct a fair comparison, all the experiments are performed on the PC with Intel (R) Core (TM) i5-9400 @2.40 GHz CPU and 16 GB RAM, and the simulations are compiled using Matlab-2016b under Win-10 platform.

Experimental Parameters
The UAV mission region is [0, 150] km long, [0, 100] km wide, and [0, 8] km high, and UAV knows the terrain and threat's position. The terrain is modeled by a processing elevation map of real terrain, while the threats are modeled as black columns. The coordinates value of the start point is (10.0,90.0,2.3 km), the coordinates value of the target point is (140.0,10.0,2.9 km). The 3d UAV route planning environment is shown in Figure 8. There are five algorithms in the experiments, including CASSA, SSA, PSO, ABC, and WOA. In all experiments, the parameters of those algorithms are set according to their references respectively. To make a fair comparison, the maximum iterations of those algorithms is set as 200, while the population size is set as 50. For CASSA and SSA, using the same parameters setting is necessary, which are the number of the finders (Fd = 0.2), the number of the threatened sparrows (Sd = 0.15), and the alarm value (G = 0.8). In consideration of the randomness nature of heuristic algorithms, each tested algorithm is executed 30 times independently, and the experimental results are used for the evaluation and comparison of their performance.

Analysis of Experimental Results
For the objective of comparison, the best UAV routes generated by CASSA, SSA, PSO, ABC, and WOA during 30 independent runs are displayed in Figure 9, and the statistic results are showed in Figure 10. To show the difference between the tested algorithms intuitively, the best cost curves for each algorithm are displayed in Figure 11.   As the test results reveal, all the five tested algorithms found the safe flight route for UAV, but they have different performance on route length, flight altitude, and route smoothness. As experimental results display in Figure 9, it is apparent that among all the five algorithms, CASSA can find the best route for the UAV. The route generated by CASSA has a more suitable altitude, which can help UAV to benefit more from the terrain mask, and its length and smooth criteria are also better than other four algorithms. In Figure 10, it can be seen that CASSA has the best performance on the best cost value, mean cost value, and worst cost value, which shows that CASSA is superior to other four algorithms with regard to searching ability and stability. Among all the five algorithms, PSO takes the shortest running time and WOA takes the longest running time. The running time of CASSA is a little longer than SSA, mainly due to the variation operations added during the iteration of the algorithm. For offline route planning problems, the accuracy of the algorithm is more important than the running time, so the time taken to run CASSA is acceptable. In Figure 11, it should be noticed that CASSA not only has the best convergence value, but also has a good initial solution and the fastest convergence speed.
The 3d UAV route planning problem has many local solutions, making it challenging to solve by classical optimization algorithms. The reason why CASSA performed excellently on this complex optimization problem is due to the integration of the adaptive inertia weight and the Cauchy-Gaussian mutation operator. In the searching process, the adaptive inertial weight can control the search ability and convergence speed of CASSA, and the integration of the Cauchy-Gaussian mutation operator can avoid the local optimal solutions by suddenly changing the location of the elite sparrows in the search space. Therefore, the excellent exploration ability and local minimums avoidance of the proposed CASSA helps it to improve the drawbacks and surpass the original SSA.

Conclusion and Future Work
This paper proposed a modified sparrow search algorithm called CASSA and successfully applied it for solving the 3d UAV route planning problem in complex task space. In the proposed CASSA, the chaotic strategy is used to enhance the stability of the algorithm, and an adaptive inertia weight is used to balance the convergence speed and exploration ability. The original SSA usually suffers from local optimal stagnation, but the Cauchy-Gaussian mutation operator integrated is able to help CASSA avoid this drawback by suddenly changing the position of the elite sparrows in the search space. Those modified strategies lead to the better performance of CASSA on the 3d UAV route planning problem. In order to make the route more viable for practical UAV flight mission, the B-Spline curve is used for smoothing the route generated by CASSA. The experimental results demonstrate that CASSA is an efficient and viable method in the field of UAV route planning.
There are many challenges for future work. For example, more constraints can be introduced, such as flight speed constraint, different types of obstacles, and dynamic threats. Moreover, it would be meaningful to apply CASSA for solving other optimization problems in the field of UAV, such as task assignment and formation control.