Interactive path planning and real-time motion synthesis for articulated humanoid characters in virtual environments

Table of contents

1 Introduction

2 Virtual Environments
2.1 Virtual Humanoids
2.2 Path Planning
2.3 Motion Synthesis
2.4 Summary

3 Path Planning
3.1 World Description
3.1.1 Wavefront Planner
3.1.2 Quadtree
3.1.3 Cell Decomposition
3.1.4 Visibility Graph
3.1.5 Global Roadmap
3.1.6 World Description Overview
3.2 Path Adjustment
3.2.1 Rubber Banding
3.2.2 Path Smoothing
3.3 Summary

4 Motion Synthesis
4.1 Motion Description
4.2 Organization of Motion Data
4.2.1 Motion Graphs
4.2.2 Motion Generation from Examples
4.2.3 Annotations
4.2.4 Data Organization Overview
4.3 Motion Modification
4.3.1 Motion Warping
4.3.2 Spacetime
4.3.3 Retargetting Motion
4.3.4 Motion Modification Overview
4.4 Motion Transition Detection
4.4.1 Similarity Metric
4.4.2 Window of Frames Approach
4.4.3 Transition Detection Overview
4.5 Summary

5 Framework
5.1 Framework Layers
5.2 Network Distribution
5.3 Path Planning module
5.3.1 Wavefront
5.3.2 Quadtree
5.3.3 Global Roadmap
5.4 Motion Synthesis Module
5.4.1 Motion data reader
5.4.2 Motion transition detection
5.4.3 Motion modification and blending .

6 Results
6.1 Path Planning Module Analysis
6.1.1 Wavefront analysis
6.1.2 Quadtree analysis
6.1.3 Global Roadmap analysis
6.1.4 Comparative analysis
6.2 Motion Synthesis Module Analysis

7 Conclusion

A Tools
A.1 FXMotionViewer
A.2 FXSplineEditor
A.3 FXMotionMerge
A.4 FXNavigator

Bibliography

Statement

Hiermit versichere ich, dass ich die vorliegende Arbeit selbständig im Rahmen der an der RWTH Aachen üblichen Betreuung angefertigt und keine anderen als die angegebenen Quellen und Hilfsmittel benutzt habe

I guarantee that this thesis is done independently, with support of the Virtual Reality Group at RWTH Aachen University and no other unmentioned helping resources are used

Aachen, October 5,

1 Introduction

Virtual Environments are becoming more realistic and more functional with today’s constant technological advances. These advances allow for virtual worlds to closely resemble reality. Therefore, new areas of usage and application of virtual environments are found every day. The interiors of submarines, cargo ships, power plants, oil platforms, airports and many other environments can today be replicated and used in various training applications, pre-construction simulations and many more.

Young doctors, for example, can perform numerous complex operations on virtual patients. Once they are finished or have made a mistake, they can simply, with one press of a button, reset the patient and the entire operation hall, and prepare them for a new operation. Same can be applied in any other training environment where the mistakes during practical education have a great potential of occurring and more importantly, have an enormous cost.

Furthermore, beside eliminating costly repercussions, the availability of on-demand training environments provides the ability to perform almost unlimited repetitions of training exercises. This significantly increases the number of trainees as well as their individual expertise.

On a more technical note, rendering and processing are increasingly get- ting faster. This allows for the introduction of more complex shapes and a higher number of these shapes into a virtual environment which makes the virtual world more detailed and thus more realistic. In addition, fast rendering and high processor power bring higher resolution, better lighting and shading, and all other aspects that increase the realism of an artificial environment and allow for greater believability in users of these systems.

However, high resemblance to the real world is not sufficient for great acceptance and believability. Imagine a perfect virtual copy of a factory, a mall, or an airport and a user placed in this environment. Without the pres- ence of virtual characters, the user will soon start to reject this simulation.

Therefore, human characters present an inevitable part of almost any environment. One cannot construct a virtual city, a museum, or a factory, without placing humans, their pets, birds, and many other beings in it. These characters bring life to an environment and, since the goal of a virtual world is to closely resemble the real world, then life, as its unavoidable part, must be replicated as well.

Of course, rendering and processor power assist in the appearance of vir- tual characters in the same way they do with appearance of non-live objects. Thus, if we have realistic walls, pieces of furniture and other objects in the virtual world, it is safe to assume that the features of the virtual humanoids like their skin, clothes and other visual aspects, will also appear as realistic. But with virtual characters that is not sufficient. Virtual humanoids can not just stand in the environment like buildings or trees or pieces of furniture, and by looking good satisfy users’ expectations. These characters must also move, walk, act, and most importantly react to the surrounding environment.

It is the way the virtual characters act that is their most important fea- ture. Their movements and reactions to the stimuli within the environment and from the user are what actually makes them appear realistic and be- lievable. If we examine animated cartoon characters, it is clear that most of them do not appear realistic at all. A 4-foot tall talking rabbit, arguing with a slightly shorter but also talking duck is not realistic, we all know that. But viewers recognize familiar reactions and movements that these cartoon characters exhibit. Thus, if Bugs Bunny reacts in the same manner as an actual human would react, the viewers will accept him regardless of his ap- pearance. In the same way, even if rendering is not sufficiently advanced to create absolutely believable appearances, the virtual character’s movements, actions and reactions will be sufficient for his believability and acceptance.

This feature of virtual characters can be split into two large parts: how they act and how they move. The first one refers to the execution of motions, for example reaching for an item, jumping for a ball or taking a seat in the waiting room. The second part deals with spacial transitions, for example going from one point in the world to another while avoiding obstacles and other characters. These two parts belong to the areas of Motion Synthesis and Path Planning respectively.

The problem of Motion Synthesis is to recreate realistic motions as they are performed by real characters. There are several issues involved with this problem and they will be examined in greater detail in chapter 4. The Path Planning problem is to determine the most appropriate and realistic path in a virtual world while, naturally, avoiding solid objects. This and many other issues associated with Path Planning will be detailed in chapter 3.

The two fields, namely, Path Planning and Motion Synthesis, are the main aspects of this master thesis. The goal of the thesis is, therefore, to research and implement State of the Art algorithms from the areas of Path Plan- ning and Motion Synthesis and to compare the results of those algorithms. During implementation, the focus will be kept on the principal factors influ- encing the acceptance of virtual humanoids, namely real-time responses and interactivity. These methods are to be integrated into the ViSTA VR-toolkit [TvRB00, SGvR+03] for the manipulation and control of the VRZula¹ char- acter.

The rest of the thesis is structured as follows. In chapter 2, the funda- mentals of virtual worlds are explained and the problems of Path Planning and Motion Synthesis are presented. Chapters 3 and 4 explain areas of Path Planning and Motion Synthesis in greater detail and offer the analysis of several State of the Art algorithms from these areas. Chapter 5 will outline the framework design and the implementation of the system that includes the Path Planning and Motion Synthesis engines. Evaluation of the results of the implemented algorithms is in chapter 6. Chapter 7 contains conclu- sions and suggestions for future work. Detailed descriptions of all the tools created for testing and analysis of the implemented algorithms can be found in appendix A.

2 Virtual Environments

Virtual Reality (abbreviated VR) describes an environment that is simulated by a computer. The goal of virtual reality is to make this simulated environment appear as realistic as possible. This may be a replica of some existing real environment or it may simulate an environment that is planned to be created. It may also fall under the category of science fiction. In either way, realism, or in other words realistic appearance and user believability, is the main goal of virtual reality. The users must feel as if they are not in a lab surrounded by huge projectors and other gadgets, but rather as if they were actually immersed in an existing real environment.

illustration not visible in this excerpt

Figure 1: Virtual Environment (image from www.hhi.fraunhofer.de)

As an inevitable part of virtual worlds, humanoid characters are affecting the overall appearance and realism of the environment they reside in. In this chapter, the virtual humanoids and the requirements that follow their presence in the virtual worlds are analyzed. Following the analysis of virtual humanoids the problems of Path Planning, section 2.2, and Motion Synthesis, section 2.3, will be presented and analyzed.

2.1 Virtual Humanoids

Virtual humanoids are an inevitable part of virtual environments [Tha01, Hod98]. Their realism and believability directly affects that of the environment they reside in. Thus, it is of equal importance that they too resemble their real counterparts as closely as possible.

Virtual character’s clothes, skin, hair, as well as movements and actions affect their acceptance in users. Therefore, character’s behavior, as well as their appearance, is an important aspect of their believability. A virtual humanoid endowed with realistic behavior models can evoke better levels of presence and believability in a user than a humanoid with no innate behavior [Vin02]. However, there is a great distinction between what appears to be realistic and what appears believable [PG96].

Figure 2: Virtual Humanoids (image from http://vrlab.epfl.ch)

illustration not visible in this excerpt

The problem of appearance of virtual characters depends on the rendering and processor power, same as the rest of the virtual world. Their behavior, however, is a separate and more complicated issue. In the example of cinema, any human character is perfectly realistic simply because we actually see the real human being. But, believability does not require this absolute realism because millions of people relate to Bugs Bunny and Daffy Duck as if they actually exist. The cartoon characters are absolutely not realistic, and yet, they are quite believable to the viewers. The secret to their believability lies in the interactivity they exhibit among each other and their reactions to the environment. As long as their movements and reactions are similar to what viewers expect, the believability will exist regardless of realism.

This rule equally applies to virtual characters. No matter how realistic we make the virtual humanoids, this alone will not make them believable to the users. They need to act and react in accordance to user’s expectations. This means that they must, for example, fall when they are tripped, jump when they are scared, and much more. But, it all must be done exactly like an actual human would do under the same circumstances.

The actions of the virtual humanoids can be split into two categories, one that deals with the aspect of moving through the environment or, in other words, the path along which they move from one point to another and the other that deals with the motions that they perform during various actions. This division is resembled in the two areas that this thesis deals with, namely Path Planning and Motion Synthesis. The next two sections will examine the problems of these two fields. First, the problems of Path Planning will be presented, followed in section 2.3 by the presentation of issues associated with the area of Motion Synthesis.

2.2 Path Planning

With the increased development of virtual environments, the ability of virtual characters to find their way around the terrain becomes a more important feature of their behavior [Cha01]. Naturally, simply selecting a straight line as a shortest path between the starting point and the goal position is not sufficient because there might be an obstacle in the way like a chair, a table, a wall, or even another character. In addition, in a 3D environment, the goal position might be on another floor in a building and is, thus, only reachable via stairs or elevator. All these aspects of complex virtual environments af- fect the selection of the path that a character needs to follow in order to reach his goal.

illustration not visible in this excerpt

Figure 3: Path Planning

Therefore, obviously, the path determination greatly depends on the vir- tual world and the items in it. In order to suggest an appropriate path, the algorithm needs explicit knowledge of the positions, shapes and sizes of potential obstacles that exist in the environment as well as the overall knowledge of the entire environment. Of course, with static environments it is possible to have a complete knowledge of all elements of the virtual world. On the other hand, dynamic environments only allow partial knowledge to be extracted initially, while, an exact description must be obtained at run-time which increases the time complexity. In either case, when the information about the virtual environment is available, the algorithm can proceed and attempt to create a path that connects the character’s current position with its goal destination, if such a path exists.

Therefore, the problem of Path Planning can be separated as follows: first, the virtual world is analyzed and properly described, then, using this descrip- tion, a path is determined between any two given locations. In addition, fur- ther sub-categorization includes different approaches for static and dynamic environments accordingly. Also, path determination is complemented with some path adjustment in order to achieve more natural path outlines.

An important feature of the world analysis step is that, regardless of the type of the environment, most, if not all Path Planning algorithms rely on a graph representation of the virtual world. Various types of analysis are used in different algorithms in order to obtain a graph structure which will, in some way, represent the world’s properties and determine the area in which a virtual humanoid can move freely. This particular area is properly called the free space.

A common approach to analyzing the virtual environment is to spatially decompose the world into a number of individual areas. Following this de- composition, a graph representation can be extracted using information that is gathered in the first step. The area of spatial decomposition includes al- gorithms like Quadtree, Visibility Graph and many others. Naturally, even though decomposition algorithms differ greatly, their end result is always some graph representation. Therefore, the step of path finding is reduced to a simple graph search using any of the famous graph theory search al- gorithms. This leads to the conclusion that any Path Planning algorithm can be structured in four separate steps: spatial decomposition of the virtual world, graph extraction, path finding and finally path adjustment.

In chapter 3 the problem of Path Planning will be discussed in greater detail, together with descriptions of particular State of the Art algorithms in this field of research.

2.3 Motion Synthesis

Subtle details in the motion of humanlike characters affect the believability and aesthetic of a virtual environment [ZH99]. How the characters act and react affects their acceptability and thus, the acceptability and believability of the entire virtual world. When users interact with these characters, they expect realistic behavior which implies realistic movement. Without realis- tic movement users would quickly notice that something is out of place and would, thus, loose their belief in the reality of the entire environment.

Figure 4: Motion Synthesis (image from [FP03])

illustration not visible in this excerpt

In order to instruct a virtual character to perform a particular motion, that motion must be described in a way that the computer will understand it. Only then will the machine be able to convert given information into an an- imated motion. Trying to instruct the machine to animate the jumping-jack motion for a virtual character will not succeed unless there is an appropriate computer-readable description of this motion available. Therefore, a more machine oriented description than ”jumping-jack” is required.

To obtain a suitable description, the virtual character is first described as a set of bones and joints. With this reduction any motion can easily be described as a set of rotations for each individual bone independently and a single translation for the entire character. These rotations and a translation are nothing more than just one number each. And when they are reproduced in a synchronous way, a motion is correctly animated. This procedure seems rather simple and in reality it actually is, but the problem of motion anima- tion begins much earlier. In other words, motion descriptions must first be created or collected.

There are several methods that lead to relatively realistic motion data. These methods include key framing, physically based modelling and others [PB00]. However, most reliable and most realistic looking motion is obtained via motion capture [TH00]. In this approach, a human actor dressed in a special suit, performs various actions while the computer records the bone rotation data. This data is later used for the reproduction of the recorded motion.

However, while motion capture is a reliable way of acquiring realistic hu- man motion, it is only a technique for reproducing motion. This data is difficult to modify, and editing techniques are reliable only for small changes to a motion [PB02]. This problem of inability to modify captured data par- ticularly arises in interactive systems where certain motions may be required for which there is no captured data. At this point the system’s only solution would be to reproduce some similar motion, however, this most often will not lead to a satisfactory result. Therefore, an important part of Motion Synthesis is modification of existing motion data and creating new ones.

Further, in an interactive system a virtual character will need to perform various motions one after another consecutively. Simply concatenating any two motions is not a very good idea. If the first motion does not end exactly as the second motion starts, there will be a noticeable ”jump” at the inter- section point. Thus, motion modification must also cover motion blending where two motions are both modified partially on their corresponding ends in order to create a smooth transition. Obviously, for different pairs of motion, different parameters for blending must be used and therefore, a transition detection is required to obtain the parameters for a satisfactory blend.

In addition, given a large set of motions and tools for creating new mo- tions and blending existing ones, the system which is intended to use them must have some mechanism for extracting the specific motion at an appropri- ate time. Therefore, some organization of the existing motion is also needed.

Thus, the area Motion Synthesis can be categorized in four separate parts. The first part is motion description. The second part is organization of de- scribed motions. Existing motions require modification and blending which is the third part. Finally, the fourth part is a transition detection which is required for a proper motion blending as well as for a good motion organi- zation. In chapter 4 these four areas of Motion Synthesis are discussed in detail and various State of the Art algorithms from these fields are explained.

2.4 Summary

Virtual Environment’s goal is to mimic the real world closely. Their realism strongly depends on the characters in it. Virtual humanoids’ realistic appear- ance, accompanied with realistic behavior, fully supports the believability of the entire virtual world. While the appearance of virtual characters mostly relies on the hardware of the system, their behavior is handled by the various algorithms from the two areas of Path Planning and Motion Synthesis.

Both Path Planning and Motion Synthesis are relatively large areas defined by several distinct problems. This allows for a clear breakdown of these areas into a series of separate steps. Each of these steps can be viewed and analyzed as a distinct area of research. These two areas will be discussed in detail in the next two chapters together with a presentation of various State of the Art algorithms for their respective parts.

3 Path Planning

As the technology advances, so do the virtual environments and their com- plexities. This increases the requirement for faster and more precise Path Planning solutions and many algorithms have, therefore, been designed and constructed in the attempts to solve this problem. They vary significantly in their approaches, their end results as well as in their time complexities.

Figure 5: Virtual Humanoids Walking (image from http://vrlab.epfl.ch)

illustration not visible in this excerpt

Due to the increase in complexity of the virtual environments, today’s State of the Art algorithms are mostly concentrated on world representation. Describing the world appropriately is the most important aspect of Path Planning. Without a proper description, path finding becomes extremely difficult, if not impossible.

Almost all Path Planning algorithms use graphs as a data structure for describing the virtual environment. An advantage of this approach is that after this type of representation is extracted, a path finding step is reduced to a simple graph search using algorithm like:

- Dijkstra’s algorithm, which solves the shortest path problem for a directed graph with nonnegative edge weights; [CGR94]
- A* search, which employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node; [GH05]
- Kruskal’s algorithm which finds a subset of edges that form a tree which includes every vertex, while total weight of the edges is minimized.

There are several ways in which Path Planning algorithms can be cate- gorized based on their differences. First, there are algorithms that deal with dynamic virtual environments and those that rely on the assumption that the virtual world is static. Further, based on the way in which these algorithms decompose the world, they are categorized into those based on uniform and those based on random decomposition of the virtual environment.

As for the static versus dynamic worlds categorization, these two cate- gories of path planners are called one-shot and many-shot, respectively. One- shot planners do not make assumptions about the environment and simply take the world description at run time. However, it might take a few seconds in the worst case for these planners to come up with a collision-free path. On the other hand, many-shot spend a reasonable amount of time in preprocess- ing the configuration space for future path-planning queries.

The planning times for many-shot planners are better bounded since the planning problem can be reduced to only a graph search problem at run time. This comes from the assumption that the environment doesn’t change, otherwise it would be needed to redo the preprocessing step whenever the environment changes which is very inefficient. Many-shot planners are more suitable for real-time user interactions than one-shot planners due to the fact that at runtime, only graph search is performed [LT00].

The second categorization separates algorithms that are based on random sampling from those that decompose the world in some uniform way. The uniform decomposition is usually based on some type of a grid representation of the virtual world. Random decomposition algorithms, on the other hand, rely on repetitive random sampling of the environment in order to obtain an overall description of the world at hand. In addition, there are algorithms that fall in between these two categories. These are algorithms are mostly oriented towards the obstacles in the world and do not rely on either uniform or random approaches.

In the next section, Path Planning algorithms with regard to the categorization of random versus uniform decomposition will be described. Since the most important aspect of this master thesis is interactivity and real-time responses only many-shot algorithms will be considered and analyzed. In addition, an overview and comparison of these algorithms will also be presented. Then, motivation for path adjustment and possible solutions for this problem will be presented in section 3.2.

3.1 World Description

Describing the virtual world for Path Planning is a challenging task. First, the obtained description must be computer understandable. Further, even though it must distinctively describe all the obstacles and the entire free space, it must be as compact as possible in order to allow fast path extraction. On the other hand, the more detailed the description of the world is, the more accurate path will be obtained from it.

In this section, several State of the Art algorithms that attempt to provide such a description of the virtual world will be described. First, algorithms that rely on uniform decomposition of the virtual environment will be dis- cussed followed by algorithms that fall somewhere in between uniform and random approaches. Finally, random approach algorithms will be presented at the end of this section.

3.1.1 Wavefront Planner

The first algorithm in the list is the Wavefront [LS01] algorithm. In this approach, the world is decomposed using a two-dimensional grid representa- tion. In this grid, each cell is assigned a value which later helps in the path finding step. This way, the path finding is reduced to a breadth first search of the grid.

Figure 6: Wavefront Planner setup

illustration not visible in this excerpt

Initially, cells that belong to the free space are labelled with 0, the goal position with 2 and cells that belong to the obstacles with 1. Optionally, the entire world can be surrounded with 1’s as well to tell the virtual characters to avoid those squares. Then, starting from the goal position, for a cell with value i, all cells adjacent to it that have not already been labelled are labelled with i + 1. This step is repeated until there are no reachable cells labelled with 0. This way, a wave of values is created, which is where the name for this algorithm comes from. Figure 6 shows an illustration of Wavefront Planner setup of a simple virtual world.

After the labelling is complete, the path finding step is simply a breadth first search of the grid representation of the virtual world. The shortest path is found from any cell in the world simply by always moving to the adjacent cell that has the lowest value. Of course, during this search, cells with value 1 are avoided as they represent obstacles in the world. Obviously, many paths can be used to reach the goal, and any path that follows the descending val- ues correctly is acceptable. However, the search is limited to only one goal position. If the goal position changes, all the values of cells in the free space must be recalculated.

Unfortunately, this drawback is a rather serious one. Since virtual worlds are increasingly becoming larger, the number of cells required for their representations will be increasing as well. For example, a world with 256 × 256 cells can never be considered a large one, yet, in the worst case, 65536 cells need to be searched through for a path, and, after every change of the goal position, 65536 cells, in the worst case, must be recalculated.

3.1.2 Quadtree

Since existence of too many cells creates a significant problem, obeying the following rule becomes quite sensible:

The Bigger Is Better Law of Spatial Decomposition for Path Planning (BIBLOSD): Use the largest convex regions you can as the basis for search-based path planning [Dav00].

The bigger the regions, the fewer there are. Thus, the number of regions becomes significantly smaller and so it is easier to search through them. As- suming that there is some predefined minimum obstacle size, there will be some minimal acceptable cell size, therefore simply making the uniform cells bigger doesn’t achieve all of the goals of Path Planning, namely fast planning and good paths.

There is a vast number of different convex decompositions that can be used. However, a Quadtree structure provides a good combination of fast pre-computation and recomputation and a great decrease in the number of cells from a uniform grid [Dav00]. There is also a nice bonus of a fairly straightforward implementation compared to many other convex decompo- sitions. Figure 7 shows an illustration of a Quadtree Representation of a simple virtual world.

Figure 7: Quadtree representation of a simple virtual world

illustration not visible in this excerpt

After the virtual world is decomposed using a Quadtree, a graph repre- sentation is extracted in a fairly straightforward way. Each cell is observed as one node, and so, a graph node is placed at the center of that cell. Edges are then created between nodes in the neighboring cells. A graph constructed in this way has a very good connectivity and a relatively low number of edges. Both aspects increase the speed of the run-time path finding step.

The Quadtree algorithm, together with its predecessor, the Wavefront approach, relies on a uniform sampling of the virtual environment. Next, algorithms that do not depend on uniform sampling will be presented.

3.1.3 Cell Decomposition

Cell Decomposition algorithm [LS01] is a way of dividing the virtual world into a number of convex regions. The idea behind Cell Decomposition is that a vertical line is drawn from each vertex of all obstacles in any two directions, either up-down or left-right, until it hits an obstacle or the edge of the world. One thing to note here is that the lines are not drawn both horizontally and vertically but rather only one of these directions is chosen, it is irrelevant which one.

This way, the world is reduced into a union of trapezoid-shaped cells. After the division, each region’s center is taken as a node in the graph representation of the virtual environment. Similarly to the quadtree approach, edges are created only between neighboring cells. Figure 8 shows an illustration of a Cell Decomposition setup.

Figure 8: Cell Decomposition of a simple virtual world

illustration not visible in this excerpt

A great disadvantage of this approach is immediately noticeable from this figure. Namely, some edges actually pass through obstacles which is unac- ceptable. A possible extension would be to intentionally extend lines both vertically and horizontally in order to create a slightly better decomposition to solve this problem.

3.1.4 Visibility Graph

Visibility Graph is formed by connecting all visible obstacle vertices to each other, including corners of the world. Two vertices are considered to be visible to each other if no obstacle exists between them. After this, the drawn lines are edges in the graph representation of the virtual environment and vertices that they connect are nodes. Lines along obstacle edges are also lines of sight and thus are represented as edges in the graph.

Figure 9: Visibility Graph representation of a simple virtual world

illustration not visible in this excerpt

A path using this setup is found in the following way: first, lines of sight are drawn from the start and goal positions to all other nodes in the graph, not cutting through any obstacles. Then, the new graph is searched using any standard graph search algorithm. Figure 9 shows an illustration of a Visibility Graph setup of the virtual environment.

3.1.5 Global Roadmap

A few years back, a path-planning scheme called random sampling scheme for path planning was proposed. Experimental and theoretical results show that it is effective in solving practical problems in various applications with high dimensionalities. Many random approaches have been developed over the years and [BKL+97] provides a good overview of different random sam- pling schemes. However, the most promising scheme, called Global Roadmap is presented in [SGLM03].

The Global Roadmap is a graph that captures the connectivity of the por- tions of the model that are accessible to the virtual characters. This graph is created via successive repetitions of random selection of a point in the free space of the virtual environment. Following a set of rules, a random selection is either added to the graph or discarded and this process is repeated until a certain predefined coverage of the free space is obtained. The created graph is called a Roadmap and it is later used to generate walkable paths that let the user navigate between arbitrary locations in the environment. The fact that it is computed during a preprocessing phase implies significant increase in the speed of the runtime algorithm.

The roadmap graph is a bipartite graph containing two different types of nodes: guard nodes and connector nodes.

- Guard Nodes: Given a fixed radius rg , called the guard reachability radius, each guard node g has the property that no other guard node g′ is in the reachability domain Reach(g, rg ). Intuitively this means that all of the guards are mutually unreachable for this given radius.
- Connector Nodes: For a given distance, rc, called the connector reachability radius, a connector node represents a configuration, c, such that there are two or more guard nodes in the reachability domain of c, Reach(c, rc). For each connector node, edges are added in the graph to all guard nodes in its reachability domain.

Figure 10: Global Roadmap setup of the vertices (image from [SGLM03])

illustration not visible in this excerpt

The nodes in the graph are added in the following way. Given any random point in the free space, the first step is to check if this point can be added as a connector node. This check consists of counting the existing guard nodes within the predefined connector radius of this location. If there are at least two guard nodes within this radius, than a new connector node is added to the graph at this location and edges are added between this node and all guard nodes within the connector radius. If there is less than two guard nodes, the second check is performed to see if this position can be added as a guard node. This requires a count of guard nodes within the guard radius of this location. If there are no guard nodes in this radius, than this location can be safely added as a guard node. Otherwise the location is discarded and the whole process is repeated.

The guard nodes define a set of reachability domain that, once complete, should cover as much of the free space in the virtual environment as possi- ble. Connector nodes act as links between two or more guards to produce a well-connected graph that is used for Path Planning. Two parameters con- trol the characteristics of the reachability roadmap. The guard reachability radius, rg , controls the density of guards in the roadmap. As rg decreases, more guards are needed to cover the domain. The second parameter, the connector reachability radius, rc, influences the connectivity of the roadmap by defining the maximum edge length in the graph. If rc = rg it will take many samples to connect two guards with approximate separation distance rg. For this reason rc = 2rg is recommended [SGLM03].

Figure 11: Global Roadmap representation of a simple virtual world

illustration not visible in this excerpt

The second part of the Global Roadmap algorithm includes the runtime algorithm. This algorithm searches the roadmap graph using a variation of the IDA* search algorithm, which uses iterative depth first searches with an increasing distance cutoff, and performs connected component analysis to improve its performance.

After the Roadmap graph that provides the desired amount of coverage is generated, it is used to construct paths between some given start and goal locations. The start and goal configurations are first added to the graph as query nodes. Then, edges between these nodes and all other nodes reachable from them in less than the connector link distance are created. Once the algorithm finds a path between two nodes, it checks whether any nodes in the path ahead are reachable from the current position. If so, the path is cut to this node from the current position to shorten the path.

The Global Roadmap algorithm presents a graph structure representation of the virtual world that is extremely good. Due to the nature of random sampling, there is no bias towards any areas which means that the nodes in the graph are equally distributed throughout the free space. This is accom- panied with high connectivity as well as with user defined coverage or the free space. An equally distributed graph with high connectivity is exactly the goal of the World Decomposition step in Path Planning. In the next section, the Global Roadmap algorithm will be compared to the other algorithms described in this chapter.

[...]

---

¹ www.vrzula.org