N94- 34026 A STUDY OF NAVIGATION IN VIRTUAL SPACE Rudy Darken & John L. Sibert The George Washington University Department of Electrical Engineering and Computer Science 801 22nd St. NW Washington, D.C. 20052 darkenlsibert@ seas.gwu.edu Randy Shumaker The U.S. Naval Research Laboratory Information Technology Division Code 5500, 4555 Overlook Ave. SW Washington, D.C. 20375 [email protected] ABSTRACT In the physical world, man has developed efficient methods for navigation and orientation. These methods are dependent on the high-fidelity stimuli presented by the environment. When placed ina virtual world which cannot offer stimuli of the same quality due to computing constraints and immature technology, tasks requiring the maintenance of position and orientation knowledge become laborious. In thispaper, we presentarepresentative set of techniques based on principles of navigation derived from real world analogs including human and avian navigation behavior and cartography. A preliminary classification of virtual worlds is presented based on the size of the world, the density of objects in the world, and the level ofactivity taking place in the world. We also summarize aninformal study we performed to determine how the tools influenced the subjects' navigation strategies and behavior. We conclude that principles extracted from real world navigation aids such as maps can be seen to apply in virtual environments. INTRODUCTION Orientation and navigation are fundamental components ofmovement inanyspace. This isparticularly true invirtual spaces where tasks involving movement of any kind become difficult due to the low-fidelity stimuli presented by the virtual environment. Our focus in this exploratory research has been on navigation tasks and human behaviors associated with these tasks in differing worlds with various cues and tools. The approach taken begins with a classification of virtual worlds based on their spatial attributes and an enumeration of navigation tasks performed in these worlds. Considering human abilities, both innate and artificially enhanced, we have built a set of tools designed to aid in performance of navigation tasks. Results of an informal empirical study are presented suggesting that a relationship exists between cues and tools available in an environment and navigational behaviors exhibited by the USed'. A PRELIMINARY CLASSIFICATION OF VIRTUAL SPACES We have chosen to classify virtual worlds basedon three auributes: size, density, andactivity. We donot claim that this classification is precise or complete. A complete classification scheme codd in fact be a useful metric for the evaluation of virtual worlds and interaction techniques associated with them. 51 Size A small world is described asany world inwhich the entire world canbe viewed in detail from asingle vantage point. Small worlds tend to focus the user's attention on a single object or group of related objects. An example of such a world is the virtual windtunnel (Bryson & Levit, 1991; Bryson & Gerald-Yamasaki, 1992). A large world isdefined by Kuipers and Levitt (1988) asa"space whose structure isat a significantly larger scale than the observations available at an instant." We modify this, making it more geometric, by stating: there is no vantage point from which the entire world can be seen in detail. This keeps usconsistent with our definition of asmall world. A large world may or may not be of finite size. An infinite world is defined as one in which we can travel along a dimension forever without encountering the "edge of the world." Density A sparse world has large open spaces in which there are few objects orcues to help in navigation. An example of this is anaval simulation which is populated by only afew objects of interest. Experience has shown that subjects in such aspace easily become disoriented (Darken & Bergen, 1992). Contrarily, adense world is characterized by arelatively large number of objects and cues inthe space. An example of this would be the simulation of an urban area with many closelyspacedbuildings. Another aspect of density is the distribution of objects in the space. As the distribution approaches uniformity, the positions of objects become much more predictable. On the other hand, if objects are found clustered around a relatively small number of locations, aspace with arelative number of objects sufficient to be dense can actually be Activity The level of activity of objects within a world can be static or dynamic. In a static world, the positions of objects do not change over time. This represents the simple end of the activity scale. Dynamic worlds are worlds in which objects move about, thereby increasing the complexity of the navigational task. This movement can be deterministic or nondeterministic in nature. Worlds can be characterized along a continuum from fully determined, where all of the objects move deterministically, to fully nondetermined, where all objects move randomly. NAVIGATION We use the term "navigation" to describe any process of determining apath to be traveled by any object through any environment. For this study, that object is always the user's viewpoint in the virtual world. The ideas and tools for navigation presented here have been developed for application to the real world, or at least adapted for application to virtual worlds with similar dimensionality and properties to the real world. However, virtual environment technology enables the ability to create environments where we radically alter physical scale, time scale, sensor modality (e.g. feeling electromagnetic forces, seeing sound, hearing texture, etc.) and sensor sensitivity. This provides the potential toconsider creating entirely synthetic environments that map various phenomenon of interest into modalities to permit "direct" sensory exploration of phenomenon. This capability may become valuable in the "visualizing" and understanding of otherwise difficult to understand abstract feature_ and interactions. Many of the concepts, and even some of the actual tools of real world navigation are directly applicable to virtual worlds representing both possible and entirely synthetic phenomena. 52 Human Navigation Humans are thought to form cognitive maps of their environments for use in navigation (Stevens & Coupe, 1978; Howard & Kerst, 1981; Goldin &Thomdyke, 1982). These maps encode spatial information such as landmarks and distances. Itisbelieved that aviancognitive maps utilize asophisticated multisensory landmarking technique inwhich nodistinction ismade between visual, acoustic, orolfactory landmarks (Baker, 1984). Also, the ability tofly greatly alters the cognitive map's range,detail, and complexity. Lynch (1960, 1965, 1959, 1958) developed a set of generic components which he hypothesized areused toconsract cognitive maps of urbanenvironments. They include: • Paths: linearseparators, examples include walkways and passages. • Edges: linearseparators, such aswalls orfences. • Landmarks:..objects which areinshaq3contrast totheir immediate surroundings, such asa churchspire. • Nodes:.sections oftheenvironment withsimilarcharacteristics. Forexample, agroupof streets withthe same type of fightposts. • District_ Logically and physically distinct sections. InWashington, D.C., they might be Foggy Bottom, Capitol Hill, etc. Through the ages, humans havedeveloped techniques for navigation and piloting tocompensate for their perceptual system's limited ability to effectively utilize the physical cues available in nature.The primitive technique of dead reckoning is used today as a simple yet effective navigation method. The navigator marks the present position and orientation. This information is used, along withthedistance raveled in asraight fine, todetermine afutureposition (Bowditch, 1966). Trailblazing isperformed inasimilarfashion. Typically, physical marketsareleftbehind toencode pastpositions orinformation concerning those positions forfutureretrieval. Amore modern tool isthe global position indicator which utilizes two satellite signals toaccurately determine latitude andlongitude. This information can be used witha local map foraccurate navigation. One of the most effective tools for navigation is,of course, the map. Physical map organization and display and the relationship between the physical map and itsassociated cognitive mapare also at issue. Boff and Lincoln (1988) present threefundamental design principles formaps: • The two-point theorem states thatamapreadermust beable torelate two points onthe maptothe corresponding two points inthe environment. This will orient the space properly tofacilitate the map's use fornavigation. • The alignment principle states thatthe map should be aligned with the terrain. That is, a line between any two points in space should be parallel totheline between those two points on themap. • The forward-upequivalence principle. The upwarddirection onamapalways shows whatisinfrontofthe viewer. In addition to traditional maps, Simutis and Barsam (1980) describe the use of contour maps for navigation and orientation. Theten-aincontour itself isused as acue tomaintaindirection. An Informal Study of Navigation For our initial study, we chose a virtaal environment that is both simple and relatively similar to a physical environment. The world consists of alargerectangular planewhich can be randomly filled with avarying numberof typical objects.* We also focused on three different navigation tasks: exploration, where the primary goal isgaining familiarity with the environment; naive search, where the subject issearching for an object when its appearance but not itslocation, isknown; and informed search, when the subject has some knowledge about the location of the object. °"We used ships since the closest physical analog isalarge tract of open sea. 53 The study included nine subjects, seven male and two female t all of whom have a technical background and are experienced computer users. Only three of the subjects had any experience using the apparatus and none had any lxevions knowledge of the subject matter of the study. A Fake Space Labs, Inc. BOOM2C display was used for high resolution, monochromatic display and mechanical tracking. The Audio Cube by Visual Synthesis Inc._was used for spatialaudio. For each trial, alarge world was randomly configured based on the number of objects required (sparse or dense world) and the tools to be made available. The initial viewpoint location was marked with a fiat square on the ground plane and the target was placed randomly at some minimal distance f_romthe initial viewpoint location. The ground plane was reil_sented as asquare grid. The objects were identical ships. The target was asmall pyramid. One button on the BOOM2C was used for forward movement in the view direction and the other for backward movement. Movement speed was not variable and movement through the ground plane was not allowed. Due to the use of primarily distant viewing, stereoscopy was notutilized. Before their initial participation, subjects were informed as to the natm'e of the study and what they would be seeing in the worlds. Before each treatunent' subjects were given information about the suucture or representation of the tool(s) to be used but were never prompted with suggested strategies. For example, the components of the mapview and the orientation of the coordinate systems were described but subjects were not told how to use the tools. The task was descn'bed as having three primary parts: 1. Move through the space at will trying to view as much space as possible. 2. Search for the target object. 3. On cue, return to the start position. Each subject was instructed to browse the space in an investigative fashion. Spatial knowledge gathered inlhis step is useful in the subsequent search tasks. At some random time before the target was visible to the subject, each was told to search for the target object. After moving sufficiently close to the target, an audible bell would sound signalling the subject to return to the initial position (marked by asquare). During each trial, subjects were asked to freely describe choices being made, strategies, and general actions. Subject behavior was recorded in written notes documenting observations made by the evaluator and comments made by the subjects during and after each trial. Of particular interest was data on positional or orientational information being gleaned from the environment orthe tools and swategies used to accomplish any part of the task. Each scenario of tool(s) and world type was lried by different subjects until a generalization could be made on behavior in that scenario. Typically, five to six trials per scenario were used. Tool Descriptions and Observations of Use We have implemented atoolset which consists of a subset of the navigation techniques used in the physical world. Table 1lists the techniques and, for each of them, the real world analog which we used as our guide in developing each technique. t. Although some studies have indicated gender variance in navigational behavior, we did not observe any gender based diffexences. t. The Audio Cube uses acube of eight external speakers rather than headphones to position the sound sample. 54 Landmark Scenario Synthetic landmarks can be placed in the world. These landmarks are distinct fromother objects in the space and are placed randomly when the environment iscreated. The landmarks we used were simple rectangular columns, but they were considerably larger than the ships (figure 1). Subjects began by scanning the space from the starting location. They attempted to locate easily identifiable configurations of landmarks orclusters of ships. If they were able to locate a configuration of landmarks which also provided directional information, such as an "L" shape, their homing performance was improved. Technique Real World Analog flying avtan navigation spatial audio avian landmarking breadcrumb markers trailblazing coordinate feedback global position indicator districting urban environmental cues landmarks urban environmental cues grid navigation contour map orientation mapview map organization &presentation methodologies Table 1:Navigation techniques in the toolset. When subjects began moving through the space they attempted to use landmarks to separate the space into segments. Ifthe landmarks were configured in such away as to make itdifficult to use them as separators, subjects had atendency to become disoriented and repeatedly search the same space. During this searching phase, subjects were also trying to maintain a direction for home. Figure 1: Landmarks hips. During the homing phase, all subjects initially moved in aninaccurate direction indicating that their ability to maintain an accurate home direction was poor. Furthermore, those subjects who were unable to glean any directional information from landmark configuration were forced to perform the same kind of exhaustive search to find their way home that they had performed to find the target in the first place. When asynthetic sun was added, all subjects' performance in both phases of the search improved. The landmarks were still used to separate the search space and make the search forthe target more efficient but the sun provided much better directional information. This seems to result from two characteristics of the sun; its relative immobility and its 55 visibility throughout the space make itan absolute directional marker. Incontrast the most distinctive configurations of landmarks canonly provide directional information relative toa local region. Coordinate Tools Scenario A coordinate feedback system displays acontinuous textual readout of either Cartesian or polar coordinates of the subject's current position. Thisis similartothe type of information available from the global position indicator. Subjects determined their orientation by making exploratory movements and observing how their coordinates • • .... with one of the axes of theworld changed. With Cartesian coordinates, the subjects tended toalign thetr view direction grid and move back and forth while observing changes inthe coordinates. They would then turn ninety degrees and repeat the back and forth movement. With polar coordinates, subjects tended to combine small back and forth movements with sweeping from side toside. The coordinate tools proved most useful forthe homing task. Subjects were able toremember the coordinates of their starting place and quickly recognized the relationship between their current and startingpositions. In both eases the subjects tended to treat homing as a separable task (Jacob & Sibert, 1992) where movement and searching were performed disjointedly. We feel that thistask separation isan artifact ofthe tools rather than something that isinherent in the task. With the polar tool, subjects would fast adjust the bearing and then the range or vice versa. With the Cartesian tool subjects treated movement in x and y separately. The Cartesian coordinate tool was also somewhat useful in the target search since itcould be used easily topartitionthe space into quadrants. Breadcrumbs (or Hansel and Gretel Scenario) A system of marking the space with a visual marker (a simple unmarkedcube which we call a breadcrumb) was implemented. This mechanism canbe used manually, requiring the usertospecify where markers should be dropped, or automatically, dropping markers ata constant frequency along the user's path. This method was originally intended to be used as a trail making mechanism but was found to be used more as a manual landmarking technique where subjects would mark positions inspace with semantic information. Subjects typically would mark the start position to simplify their return later inthe trial. This was done insuch a way astobe directional (See Landmarks Scenario). The criteria for dropping a marker depended onthe strategy being employed. If an exhaustive search was required, markers were dropped at a regular frequency in space tomark places as searched. If dead reckoning was being performed, markers were dropped along a straight line between two positions. Subjects also attempted to create a directional indicator with the markers showing a direction change ifpossible. Subjects exhibited behavior similar to that in the landmark treatment. Since the markers were nondirectional, maintaining orientation was a problem. Only relative information was available from the markers. Breadcrumbs were also used inan automatic mode in which markers were dropped at some set frequency in time• This technique was useful only for leaving a trail or as a method of marking searched spaces because itwas not directly inthe subject's control. Flying Scenario When we allow flying as ameans of movement, we are effectively adding the third spatial dimension as atool ifwe keep the navigation task two-dimensional. This isreflected in the initial action taken by subjects, flying up to get a bird's-eye view of their surroundings. They then maintained their altitude while searching for the target. The "fly where you look" style of movement made thisdifficult but a relatively steady altitude could be maintained with slight up and down fluctuations. This has the effect of changing the scale at which they view the world and is somewhat analogous tousing a map. A map is, after all, a small scale representation of important characteristics of a space• The 56 major difference is that, when flying in this way, asubject is combining map reading, navigation and movement into a unified task. A further indication that the subjects are integrating these tasks is the nature of their flight path. Subjects tended to simultaneously move the BOOM and depress a movement button yielding parabolic changes in direction. Simultaneous movement and change of direction was almost never observed in any of the other treatments. Mapview Scenario The mapview is adynamic map linked to the viewpoint which can be either aligned with the world oraligned with the viewpoint. The distinction isrelated to the map organization and presentation methodologies previously described by Boff and Lincoln (1988). The map in our mapview tool appears to float within the lower part of the field of view so that the subject cam consult it at will by glancing down, yet it does not obscure the environment when the subject is looking around. The map shows the locations of; the starting point, ships, landmarks (if present), and tile subject (figure 2). The two treatments of mapview differ in their roles for orientation. In the view-aligned treatment, the map r /; p L. ,I; • mill j Fi F I i Figure 2: Schematic illustrating the map for mapview. X repre- sents the start point and the diamond isthe "you are here" mark- er. Other symbols represent ships; no landmarks are shown. isalways oriented with its top in the direction of the subject's view (figure 3a). This is analogous to navigating inacar with the map on your lap and its top oriented towards the dashboard regardless of the direction in which the car is moving. This behavior is characteristic of travel between cities. Our other treatment, world-aligned, keeps the map in constant alignment with the coordinate system of the world (figure 3b). This is somewhat analogous, in the cat navigation example, to twisting the map so that the street you are driving along is aligned with its representation on the map. People tend to exhibit this behavior when they want to make sure they are turning in the correct direction at the next corner. Only this treatment satisfies the alignment and forward-up principles. Because the map includes the starting point, it was unnecessary for the subjects to remember its location. Each version of mapview had both advantages and disadvantages. The view-aligned version was more useful for exhaustively searching the space. Subjects appear to have formed a more complete cognitive map of the environment since their view of the map did not vary as they moved. On the other hand, it was necessary for them to move and watch this motion reflected by the "you are here" indicator on the map in order to determine their orientation. With the world- aligned version, subjects had no difficulty determining their orientation from the map since it conforms to the alignment principle. However, maintaining world alignment causes the map to appear to rotate when the subject changes direction. This makes itharder to maintain a consistent cognitive map of the environment and hence decreases the usefulness of the map as an aid for exhaustive search. 57 / Figure 3a: View aligned version of mapview. Figure 3b: World aligned version of mapview. Other Methods Other treatments implemented and studied include districting, spatial audio, and grid navigation. Districting was implemented asavisual subdivision of the world into four quadrants and isbased on Lynch's (1960, 1965, 1959, 1958) districts described earlier (See Human Navigation). The districts allowed subjects to "chunk" spatial information necessary for learning and searching tasks into pieces. Searching was performed sequentially by district. Districts could be combined together to form an image of the world as awhole. A spatial audio cue, asteady positional tone generated using the Audio Cube (by Visual Synthesis Inc.) is used as an acoustic landmark. This is currently our only non-visual modality. The audio signal was added to the start location as acue forthe homing task. The cue was notaudible throughout the world and thus offered no information when outside its range. When it became audible, it was used for rough direction finding. The spatial audio cue had the effect of enlarging the target object. Lastly, when no other cues were available, subjects resorted to using the ground plane grid itself as a cue. The grid cannot offer assistance in position (unless an edge is used in a finite world). The orientation information available is cognitively demanding to maintain because it is purely relative information and requires attention to the grid at all times. If the grid included contour information (Simutis & Barsam, 1980), orientation would become easier and even positional information might be available. CONCLUSIONS The complexity of navigation tasks invirtual environments requires special attention inthe development of interaction techniques pertaining to navigation aids. Our intention has been to investigate design principles and study their 58 relationship to user behaviors in virtual spaces. Considering the innate use of environmental cues by humans and the principles of cognitive map formation and map design developed by cartographers and planners, we developed a toolset of navigation aids for use in virtual spaces. An informal empirical study of the tools for a small set of searching tasks supports the following general conclusions: • People tend to take advantage of environmental cues in predictable ways. They use them to partition spaces as an aid to exhaustive search. They use them to maintain direction relations performing best when the cue is statically positioned or highly predictable in its motion and when itis visible from the entire environment. • The tools they use have sarong influences on people's behavior. Our subjects showed very different behavior when they used different tools. The variation among tool treatments was much larger than the variation among subjects. • Because the navigation tasks were constrained to be two-dimensional and were performed on atwo-dimensional surface, cartographic design principles could be extended from the real world to the virtual world. Had we included a three-dimensional task, such as a hunt for a spacecraft in an asteroid belt, we doubt that our mapview would have been of much use. These conclusions, although far from definitive, are suggestive and encourage us to consider extending our research. We must form more specific hypotheses about how design principles relate to environmental characteristics and test them with more formal studies. We also intend to extend the research to virtual environments which have less in common with the real world. We hope that by doing this in a careful and gradual way, we will be able both to extend existing principles into new domains and to develop new principles for tool building in virtual environments. ACKNOWLEDGMENTS This research was supported by funding from NRL (NAVY N00014-91-K-2031). Special thanks go to Allen Duckworth, the late Donald Grady, and John Montgomery of the Tactical Electronic Warfare Division for their support of our work at the Naval Research Laboratory. We would also like to thank the Computer Graphics and User Interface Group at the George Washington University for their assistance. REFERENCES Baker, R.R. (1984). Bird Navigation: The Solution of aMystery? London: Hodder and Stoughton. Boff, K.R., & Lincoln, J.E. (1988). Engineering Data Compendium: Human Perception and Performance. Wright- Patterson AFB, Ohio. Bowditch, N. (1966). American Practical Navigator An Epitome of Navigation. Washington: U.S. Naval Oceanographic Office. Bryson, S. & Levit, C. (1991). The Virtual Windtunnel: An Environment for the Exploration of Three-Dimensional Unsteady Flows (Tech. Rep. RNR-92-013). Moffet Field, California: National Aeronautics and Space Administration Ames Research Center. Bryson, S. & Gerald-Yamasaki, M. (1992). The Distributed Virtual Windtunnel (Tech. Rep. RNR-92-010). Moffet Field, California: National Aeronautics and Space Administration Ames Research Center. Darken, R., & Bergen, D.E. (1992). A Virtual Environment System Architecture for Large Scale Simulations. Proceedings of Virtual Reality 1992.38-58. Goldin, S.E., & Thorndyke, P.W. (1982). Simulating Navigation for Spatial Knowledge Acquisition. Human Factors, 24(4), 457-471. 59 Howard, J.H. Jr., & Kerst, S.M. (1981). Memory and Perception of Cartographic Information for Familiar and Unfamiliar Environment. Human Factors, 23(4), 495-504. Jacob, R.K.J. & Sibert L.E. (1992). The Perceptual Structure of Multidimensional Input Device Selection. Proceedings of SIGCIM 1992. 211-218. Kuipers, BJ. & Leviu, T.S. (1988). Navigation and Mapping in Large-Scale Space. AI Magazine. 9(2), 25-43. Lynch, K. (1960). The Image of the city. Cambridge: M.I.T. Press. Lynch, IC (1965). The City as Environment. Scientific American. 213, 209-219. Lynch, K., & Rivkin, M. (1959). A Walk Around the Block. Landscape. 8, 24-34. Lynch, K., &Rodwin, L. (1958), A Theory of Urban Form. Journfil of the American Institute of Planners. 24,201 _214. Simutis, Z.M., & Barsam, H.F. (1980). Terrain Visualization and Map Reading. In Pick, H.L., & Aeredole, L. ('Eds.), Spatial Orientation: Theory, Research, & Application (pp. 161-193). New York: Plenum Press. Stevens, A. & Coupe, P. (1978). Distortions in Judged Spatial Relations. Cognitive Psychology. 10, 422-437. I= 60