Sébastien Lengagne
email: sebastien.lengagne@lirmm.fr

Nacim Ramdani
email: nacim.ramdani@lirmm.fr

Philippe Fraisse Demar

Guaranteed computation of constraints for safe path planning

Path planning issues are often solved via constrained optimization methods but with constraints which must be satisfied over a whole interval of time or space. The use of fast numerical toolboxes implementing state-of-the-art constrained needs to discretize the continous constraints over a time grid. Thus, the obtained solution, in this way, will satisfy the constraints only for time values corresponding to the time grid. Obviously, some constraints could be violated with catastrophic consequences when dealing with, for instance, the balance of humanoid robots. In this paper we introduce a guaranteed discretization method which uses interval analysis to ensure that the constraints are satisfied over the whole time interval. We analyze numerically this method by performing a trajectory generation under constraints dedicated to the motion of the HOAP-3 humanoid robot.

INTRODUCTION

Path planning is an important topic in the humanoid robotics research field. Robot motion generation is usually achieved by solving a path planning problem which boils down to a constrained optimization one. This problem is solved by [START_REF] Pettré | A 2-stages locomotion planner for digital actors[END_REF] for the planning of digital actors' locomotion ; by [START_REF] Miossec | Development of a software for motion optimization of robots -application to the kick motion of the hrp-2 robot[END_REF] for the optimization of motions such as a kick motion on HRP-2 robot or by [START_REF] Piazzi | Global minimum-jerk trajectory planning of robot manipulators[END_REF] for the planning of a manipulator robot's trajectory.

The validity of the constraints during the whole motion is of prime importance. However, the optimization algorithms used need only the assessment of the constraints over a time or space grid. The continuous constraints must then be discretized to be taken into account in the optimization process. [START_REF] Miossec | Development of a software for motion optimization of robots -application to the kick motion of the hrp-2 robot[END_REF] and [START_REF] Hardt | Optimal biped walking with a complete dynamical model[END_REF] use such a time-grid discretization, so they consider only discrete values of the continuous constraints. Therefore, these constraints are satisfied over the time-grid but can be violated elsewhere. This is the reason why we introduce a timeintervals dicretization method which guarantees the validity of the constraints for the whole motion.

This paper is structured as follows. First, we recall the path planning problem under constraints for generating optimal motions. Then, we present two simplified dynamic models considered to assess the proposed method : a double pendulum and the legs of the HOAP-3 humanoid robot expressed in the sagital plane. The next section will address the time discretization issue : we remind the classical discretization method usually used in robotics and then introduce our developments. In the last part, we compare the two discretization methods 1 Author Nacim Ramdani is on leave from CERTES EA 3481 Université Paris 12 Val de Marne for the generation of a double pendulum motion. Finally, we apply the time-intervals method to the generation of a one-step motion with the HOAP-3 humanoid robot.

I. PATH PLANNING UNDER CONSTRAINTS

To generate a motion, the usual solution is to solve a constrained optimization problem which takes into account several constraints, and an objective function which depends on the application.

The constrained optimization problem is to find out the best parameters vector x which minimizes an objective function F(x,t) and satisfies some constraints g j (x,t), ∀ j ∈ {1, ..., ng}. Therefore, the problem can be expressed as : min

R T 0 F(x,t)dt subject to : ∀ j, ∀t ∈ [0, T ] g j (x,t) ≤ 0 (1)
There can be some constraints on the vector parameters :

x min i ≤ x i ≤ x max i (2)
A. The constraints : g j (x,t)

The constraint functions allow to take into account the limitations of the system such as the mechanical constraints (joint limits : angle, velocity, torque . . . ). They can also describe the desired behaviour. In this case the constraints are the position of some bodies of the robot at several time instants to define the motion. Specifically dedicated to humanoid robots, we add a function which describes the equilibrium of the robot (ZMP : Zero Moment Point).

We consider n g constraint functions such as :

• the limit value for joint angle :

q min i ≤ q i(t) ≤ q max i ( 3
)
• the limit value for joint velocity :

qmin i ≤ qi(t) ≤ qmax i ( 4
)
• the limit of the ZMP position (cf. II-A)

zmp min ≤ zmp (t) ≤ zmp max (5)
All these constraints can be expressed as :

∀t ∈ [0, T ]min j ≤ g j (t) ≤ max j ∀ j ∈ {1, ..., n g } (6)
To fit with the optimization problem (cf. 1), we need to modify the bounded contraints (eq:6) into two inequality constraints :

∀t ∈ [0, T ] -g j(t) + min j ≤ 0 g j(t)max j ≤ 0 ∀ j ∈ {1, ..., n g } (7)

B. The objective function : F(x,t)

The choice of the objective function for motion optimization must take into account the features of the robot and the desired motion. For example, [START_REF] Miossec | Development of a software for motion optimization of robots -application to the kick motion of the hrp-2 robot[END_REF] defines the objective function as the electrical energy consumption while taking into account the parameter (friction, etc.) of the actuators; whereas [START_REF] Piazzi | Global minimum-jerk trajectory planning of robot manipulators[END_REF] chooses to minimize the jerk.

This paper focuses on the computation of the constraints, so we will not deal with the objective function. The optimization parameters define the motion function. The next part describes how to compute the joint trajectories (q (t) ) from the vector x.

C. Computation of joint values : q (t)

The vector x is comprised of :

• the motion duration t max , • the initial joint value q i , • the final joint value q f , • a parameter vector P which modifies the trajectory between the initial and final joint values. We have chosen to compute the joint value q (t) thanks to two functions which depend on the value of t max , q i and q f :

• s (t) links q i and q f with initial and final velocity and acceleration equal to zero, • b (t) are Bspline-functions. 1) the function s (t) : .

s (t) = at 5 + bt 4 + ct 3 + d ( 8
)
with :

a = 6 × (q f -q i )/t 5 max b = -5 2 × a × t max c = 5 3 × a × t 2 max d = q i (9) 2) the functions b (t) : b (t) is a set of n b B-splines functions b n(t) as shown in figure:1.
3) joint value: The joint value q i(t) is computed by adding s (t) with a ponderation of b j(t) . This ponderation is contained in the vector : P (n j ×n b ) , where n j is the number of joints and n b the number of splines for each joint :

q i(t) = s i(t) + n b ∑ n=1 P (i,n) b n(t) ( 10
)
The joint velocity qi(t) and acceleration qi(t) are computed by derivating q i(t) . So, we are in position to compute the joint angle (q (t) ), velocity ( q(t) ) and acceleration ( q(t) ). These results are useful for the next section to calculate the constraints and objective functions.

II. MODELING

In this section, we present the dynamic model of a planar robot. Starting from the joint position, velocity and acceleration (q(t), q(t), q(t)), we compute the torque Γ(t) and ZMP value zmp(t).

A. Computation of the dynamic model

The dynamic model equation allows to compute the joint torques Γ (t) knowing the joint angle, velocity and acceleration :

Γ (t) = NE(q (t) , q(t) , q(t) ,t) (11)
In [START_REF] Khalil | Modeling, Identification & Control of Robots[END_REF], the Newton-Euler method is used for computing the dynamic model of a 3-D robot thanks to a two-recursionsalgorithm. This paper deals with optimization applied to 2-D robot, therefore we adapt the Newton-Euler method for computing the joint torques of a 2-D robots.

For humanoid robots, the computation of the Zero Moment point (ZMP) give information about the balance. [START_REF] Vukobratović | Zero-moment point : Thirty five years of its life[END_REF] defines ZMP as the point zmp, on the contact surface, where the moment is equal to zero M zmp = 0 (cf. fig 2). If this point stays in the base of support, the robot maintains its equilibrium. The zmp location depends on the joint angle q (t) , velocity q(t) and acceleration q(t) .

B. Double pendulum

The double pendulum (cf. fig. 3) is used, in section IV, as a simple model. We define the initial value q i = [0, 0] to get the foot position : (x = 0, y = 0). The final joints value is computed to do a step lenght of d :

q f = Acos d 2L , 2 × Acos d 2L (12)
Let us consider one parameter per joint. So, in the case of Fig. 3, we get 2 parameters : P = [p 1 ; p 2 ]. The goal is to determine the best value of P, which minimizes the energy consumption and guarantees the contraints shown in I-A, thanks to the constrained optimization algorithm. We define the objective function as :

F(x) = t f ∑ t=0 ∑ i Γ 2 i(t) (13)
Where Γ i(t) is the torque of joint i at the instant t:

C. HOAP-3 's leg in the sagittal plane

To validate the method proposed in section V, we will use a more complicated model : HOAP-3's legs. We consider only the lower limbs, so the upper parts of the body are equivalent to a mass on the chest (cf. fig: 4). The legs of the humanoid robot HOAP-3 are modeled as a 6-links robot in the sagittal plane (hips, knees and ankles).

To apply the Newton Euler Algorithm (cf. II-A), we consider a fixed contact between one foot and the ground, whereas the other foot moves from its initial position to its final position.

D. Why discretization is needed ?

Starting from the parameter vector x we are able to compute the continuous functions : (q(x,t), q(x,t), q(x,t), Γ(x,t), zmp(x,t)). Nevertheless, the constrained optimization software needs the evaluation of the constraints over a time grid t i , i = {1, 2, ..., k}. Consequently, these constraints must be discretized. First we describe the method usually used in robotics for discretizing continuous functions (section : III-A), then we will introduce a new way of discretization which uses interval arithmetics (section : III-B).

III. GUARANTEED CONSTRAINTS COMPUTATION A. The classical time-grid discretization

Discretization addresses the process of transferring continuous models and equations into discrete counterparts. Usually discretization consists on picking up several time points of the functions to be discretized. The constraints are computed as shown : for i = {1, 2, .., k}

min j ≤ g j (t i ) ≤ max j ∀ j ∈ {1, ..., n g } (14)
Once the optimization is finished with optimal results, the motion satisfies all the constraints over the time grid but this does not ensure that the constraints are satisfied elsewhere (cf. Fig: 5). Figure 5 shows the discretization of a constraint function. If the maximum value of the constraint is 0.5, the constrained optimization program does not detect any constraint violation even though the constraint is not satisfied for t ∈ [START_REF] Piazzi | Global minimum-jerk trajectory planning of robot manipulators[END_REF][START_REF] Hardt | Optimal biped walking with a complete dynamical model[END_REF], and even though there is a computed value at t = 3 and at t = 4. In spite of time points discretization process, a solution which violates the continuous constraints may exist.

This drawback can be solved by increasing the number of time-points, but this will also increase the computation time [START_REF] Hardt | Optimal biped walking with a complete dynamical model[END_REF]. Another solution may be to consider a time-interval instead of a time-point. This is the topic of the next part.

B. Time-interval discretization via interval analysis

The main idea of the time-interval discretization is to bound a function g j (t) with a minimum and maximum value during a time interval [t] = [t min ,t max ] instead of computing a single value.

The issue is to compute min t∈[t min ,t max ] g j (t) and max t∈[t min ,t max ] g j (t). This operation is easily done thanks to interval analysis.

Interval analysis was initially developed to account for the quantification errors introduced by the floating point representation of real numbers with computers and was extended to validated numerics [START_REF] Sunaga | Theory of interval algebra and its application to numerical analysis[END_REF], [START_REF] Moore | Interval Analysis[END_REF], [START_REF] Neumaier | Interval methods for systems of equations[END_REF]. A real interval [a] = [a, ā] is a connected and closed subset of R. The set of all real intervals of R is denoted by IR. Real arithmetic operations are extended to intervals. Consider an operator • ∈ {+, -, * , ÷} and [a] and [b] two intervals. Then:

[a] • [b] = [in f u∈[a],v∈[b] u • v, sup u∈[a],v∈[b] u • v] ( 15
)
Consider g : R n -→ R m ; the range of this function over an interval vector [a] is given by:

g([a]) = {g(u) | u ∈ [a]} (16)
The interval function [g] :

IR n -→ IR m is an inclusion function for g if ∀[a] ∈ IR n , g([a]) ⊆ [g]([a]) (17)
An inclusion function of g can be obtained by replacing each occurrence of a real variable by the corresponding interval and each standard function by its interval counterpart. The resulting function is called the natural inclusion function. The performances of this inclusion function depend on the formal expression for g. Interval analysis has been used in several fields. In robotics, it has been used to solve off-line the constrained optimization problem which furnishes the best trajectory for manipulator robots [START_REF] Piazzi | Global minimum-jerk trajectory planning of robot manipulators[END_REF]. Figure 6 shows the time-interval discretization of the function of figure 5. A drawback of interval arithmetics is the existence of pessimism (cf. [START_REF] Jaulin | Applied interval analysis[END_REF]). The pessimism is the difference between the actual maximum, or minimum value of the function and the computed one. To deal with this problem, time intervals can be sub-divided into n d subdivisions, and determine the minimum (or maximum) value for each subdivision. The minimum (or maximum) for the whole interval is the minimum (maximum) of all the minimum (maximum) of the subdivisions.

C. Computation of the constraints

IV. PERFORMANCE ASSESSMENT

The programs are developped using C/C++ language. The constrained optimization is done thanks to FSQP program [START_REF] Craig Lawrence | User's Guide for CFSQP Version 2.5: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems[END_REF]. The interval arithmetic is done by PROFIL/BIAS [START_REF] Knppel | PROFIL/BIAS V2.0[END_REF].

We proposed to compare the two methods with a simple example : the double pendulum (cf. fig. II-B). We define the initial value q i = [0, 0] to get the foot position : (x = 0, y = 0). The final joints value is computed to do a step of size d :

A. Number of contraints

We take into account the constraints :

• the joint position,velocity : 2 constraints, • the zmp location : 1 constraint. Starting from the interval t = [0,t max ], we define k time instants and time-intervals, to be used in the constrained optimization. The algorithm considers only one inequality per computation.

n c = 2k × (2 + 1) (18)

B. Time-points discretization

Table I shows the results for different number (k) of discretization time points. n e is the number of evaluation of the constraint value by the optimization program. p 1 and p 2 are the final value of the optimized parameters. The number (n e ) of constraints evaluations increases with the number (k) of time points. The final value (p 1 , p 2 ) depends on the value of k. Therefore we cannot say which value (p 1 , p 2 ) is the optimal one. Moreover, when the optimization program finishes with the optimal solution (result = OK), the constraints are not satisfied for the whole motion.

C. Interval discretization

Table II shows the results for different number (k) of intervals and different number of sub-division (n d ). The number n e is also linked to the number of interval (k). Nevertheless the the final solution (p 1 , p 2 ) is almost the same for several value of k.

An important result is that, with only four intervals ( or subdivisions), the optimization will find the best solution (p 1 = 0, p 2 = 0) and the constraints are always satisfied.

D. Assessment

This simple example shows that the time-point discretization carried out for motion optimization, can generate some solutions which violate the constraints. Whereas the time-interval discretization ensures the constraints validity. Moreover, the iteration number of the constraints computation is lower than for the time-instant discretisation (942 << 19644).

V. EXPERIMENTAL RESULTS

The guaranteed computation of the constraints is applied to the generation of joints trajectories for a one-step-motion of the humanoid robot : HOAP-3 (cf. II-C).

The optimization vector x is composed of :

• the initial and final value (q i , q f ) for all joints : 2 × 6 parameters, • one B-splines parameter for all joints : 1 × 6 parameters,

• the motion duration : 1 parameter. Therefore the constrained optimization program deals with 19 parameters.

To avoid any convergence problem in this study, we do not take into account any objective function. We consider only the following constraints :

• the initial and final positions of the moving foot (position (x, y) of the toes and position (y) of the heel) : 2 × 3; • the minimum and maximum limit of joint values and velocities for all the intervals: 2 × 6 × k; • the minimum and maximum values of the ZMP location : zmp (t) , for all the intervals : 2 × k. For this constrained optimization, we focus on 5 intervals of discretization : k = 5. Thus, we get n c = 6 + (12 + 2) × k = 76 constraints to validate. We also use n d = 5 sub-divisions.

On figure 7, we compare the values of the zmp (t) , computed from the obtained solution, and the value given by the time intervals computation for several number nd of sud-divisions.

When n d = 1 (fig. 7(a)), the minimum and maximum values of the function : zmp (t) are computed with an important pessimism and we know that the constrained optimization program will reject acceptable solutions. Whereas for n d = 100 (fig. 7(e)), the pessimism effect is very small. Nevertheless we know that the computation time increases with the value of n d . A good compromise between large computation time and small pessimism effect is to choose a value of n d between 5 and 20.

CONCLUSION

In this paper we have presented a new method that ensures the validity of continous constraints for trajectories optimization. We have shown that the commonly used time-point discretization method is fast but do not ensure the validity of the constraints. Therefore the constrained optimization algorithm will accept some solutions which violate the contraints. However, the time-interval method proprosed ensures constraints validity over the whole motion. We have compared the two methods for the contrained optimization of a double pendulum motion, and applied the time interval discretization to motion optimization of the humanoid robot HOAP-3.

We have planned to implement our method to address the contrained optimization of a whole step motion and to merge the two methods to decrease computation time.

Fig. 1 .

 1 Fig. 1. Representation of B-splines functions b n(t) with n b = 2.

Fig. 2 .

 2 Fig. 2. Representation of zmp

Fig. 3 .

 3 Fig. 3. Double pendulum used for the comparaison of the discretization method

Fig. 4 .

 4 Fig. 4. 2-D model of HOAP-3

Fig. 5 .

 5 Fig. 5. Example of a function discretization. (The discrete values satisfy the constraint, whereas the continuous function violates it.)

Fig. 6 .

 6 Fig. 6. Example of time-interval discretization of a function. (The minimum and maximum value are computed for each interval. The continuous value is always between those two values.)

3 (e) n d = 100 Fig. 7 .Figure 8

 310078 Fig. 7. Comparaison of interval computation of the ZMP for several n d values

Fig. 8 .

 8 Fig. 8. One step motion obtained with guaranteed discretization

TABLE I RESULTS

 I FOR DOUBLE PENDULUM OPTIMIZATION MOTION WITH INSTANT DISCRETIZATION.


Julien Pettré
email: julien.pettre@inria.fr

Populate Your Game Scene

We describe a method for populating large virtual environments with crowds of virtual pedestrians. Pedestrians are distributed in the environment by giving them goal destinations to reach. In order to facilitate this population setup, we assign identical destinations to batch of pedestrians, resulting in navigation flows. In order to preserve individuality of pedestrians, navigation is planned with variety and each pedestrians follows its own unique trajectory. This specific navigation planning technique answers user's queries very rapidly. As a result, impact of the insertion of a new navigation flow in the environment is directly observable, and interactive design is achieved. Once the problem of design solved, we address the problem of simulating the virtual population navigation. A level-of-details strategy is used to achieve on-line real-time simulation of large crowds, formed by up to tens of thousands of pedestrians. We illustrate our method on the typical example of a virtual city, and discuss our approach.

Introduction

Motivations

Many video games action take place in large virtual environments such as buildings, districts, entire cities or outer landscape. Players and virtual opponents are present in these environments, however, if the environment remains only populated with players, real or virtual, the scene may still look empty. Scene liveliness can be improved by filling up the place with a population of virtual inhabitants. A large number of them may be required to achieve this goal, even more when scenes are large. As a result, some aspects of this problem are close to the one of crowd simulation. However, video games applications have specific needs: among them, the need for a eye-believable population simulation (that can be opposed to the need for realistic results, and that also eliminate some classes of crowd simulation techniques such as cell-automata); the need for interactivity between the player and the population, which induces the need for on-line simulation; and finally, the need for giving control on the population activity to game designers.

Our objective is to provide tools for creating and animating large virtual populations, in order to make large environments alive. Some questions need addressing: how to setup a crowd and get control on its activity? how to simulate efficiently a crowd on the performances point of view? In the next section, we give a very brief overview of existing techniques for crowd design, visualization, simulation and motion planning. However, in this article, we will specifically focus on populations of pedestrians with behavior restricted to navigation. We will give key-ideas for designing large navigating crowds from simple and few high-level directives, and describe a crowd simulator exploiting a level-of-details strategy in order to reach high performances.

Related Work

Crowd Visualization and Design. Crowd Visualization is a specific problem with various solutions [START_REF] Aubel | Real-time display of virtual humans: Levels of details and impostors[END_REF], [START_REF] Tecchia | Visualizing crowds in real-time[END_REF], [START_REF] Dobbyn | Geopostors: A real-time geometry/impostor crowd rendering system[END_REF]. Briefly, these solutions rely on two major concepts. The first one is the level-of-details concept which consists in representing entities on the screen with a varying complexity, depending on its visibility and distance to the spectator's point of view; the more the entity is viewable (close and centered in the screen), the more its representation is accurate, and inversely. The second one is the use of impostors. Impostors are 2D images of entities which are used in place of 3D models when displaying the entity on the screen, allowing important computation time saves. It is possible to use such simple representations while preserving variety for visual aspect of individuals. CrowdBrush is a user-friendly tool for Crowd Design [START_REF] Ulicny | Crowdbrush: Interactive authoring of realtime crowd scenes[END_REF]. This tool is mainly dedicated to give visual aspects to many individuals in an easy manner, but also allows the distribution in space of the crowd and the definition of the inhabitants activity. Using CrowdBrush, goal destinations can be assigned to individuals, however, the user is in charge of providing a collision free path. Compared to this useful tool, we provide a solution to compute automatically collision-free paths for batches of pedestrians.

Crowd Simulation. Simulating crowds first consists in computing trajectories for several entities while taking into account their interactions and presence of obstacles in the environment. We briefly present 3 general methods to address crowd simulation among others: rule-based systems, particle systems and cellautomaton methods. Reynolds' rule-based model is a popular approach, allowing to compute motions for coherent groups [START_REF] Reynolds | Flocks, herds, and schools: A distributed behavioral model[END_REF]. Each entity's motion is influenced by other entities in its vicinity resulting in a global motion that can be compared to flock of birds or fishes. Reynolds declined later his approach in [START_REF] Reynolds | Steering behaviors for autonomous characters[END_REF] to propose a complete set of steering behaviors such as seeking, fleeing, pursuing, etc. Using Particles Systems is another popular manner to simulate crowds [START_REF] Bouvier | Crowd simulation in immersive space management[END_REF], interactions between particles may be modeled by forces such as in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF], or by using potential fields [START_REF] Treuille | Continuum crowds[END_REF]. Finally cell-automaton techniques relies on a floor-field structure, a regular discretization of the navigable space looking like a grid. Each cell of this floor field may be occupied or free. Each time-step, the content of occupied cells has a probability to be transferred toward a neighbor cell, modeling people's motion.

Crowd Control. We intend to populate environments with crowds of pedestrians with goal-directed navigation; this problem is thus reduced to a navigation planning problem. An exhaustive description of existing motion planning algorithms can be found in [START_REF] Lavalle | Planning Algorithms[END_REF]. Briefly, three major classes of solutions can be distinguished. Firsts are reactive methods: the key-principle of these techniques is to model goals as attractive and obstacles as repulsive potentials [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF]; the moving entity follows the gradient of the resulting potential field in order to reach its goal. This kind of techniques suffers some local minimum deadlocks, however, they are simple to implement and practical to use. Sampling-based motion planning is the second major class of approaches. These methods explore partially the navigable space in order to capture interconnected collision-free positions and paths into a graph structure (commonly called a roadmap). The well-known PRM (Probabilistic Roadmaps Methods, [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF]) and RRT (Rapidly-Exploring Random Tree [START_REF] Kuffner | Rrt-connect: An efficient approach to single-query path planning[END_REF]) methods explore the free space in a random manner. A the opposite, deterministic approaches are based on a complete exploration of the free space, however, they can use discrete representation or complete representation of this space, resulting respectively in partial or complete solutions. Deterministic approaches result in a data structure, generally a graph, capturing both the geometry and the topology of the free environment. Navigation planning queries are solved using graph search algorithms. Deterministic approaches were recently used to adress the crowd navigation problem in [START_REF] Sud | Real-time path planning in dynamic virtual environments using multiagent navigation graphs[END_REF].

Overview

Our approach allows a designer to populate a scene by adding progressively navigation flows in the environment. Navigation flows are subsets of pedestrians navigating back and forth endlessly between two given locations. The designer controls the distribution of the population in the environment only by selecting these destinations, and the pedestrians groups size (i.e., the number of individuals composing the group). By answering very rapidly designers' queries, they can immediately see the impact of the insertion of a new navigation flow, and compose a population by trial and error. There is no theoretical limitation on the number of flows, as the simulation complexity is mainly dependent on the total number of pedestrians composing the whole population.

These objectives are reached by combining 3 major ingredients:

1. Navigation Graphs: they result from a specific environment analysis which is similar to a cell-decomposition technique. Navigation Graphs are computed at a preprocessing stage, and support future navigation planning queries. 2. Navigation Flows: as defined above, they are sets of navigating pedestrians with common destinations. However, we want to preserve individuality in trajectories followed by each pedestrian. For this reason, we developed a specific navigation planning technique which computes a variety of solution paths. Doing so, from a unique navigation planning query, we can generate a variety of solution paths. 3. Crowd Simulator : it exploits a Level-of-Detail strategy, which allows to dispatch the available computation resources at the best. As for crowd visualization techniques, the key-idea is to get high-quality simulation in front of the user's point of view whereas the quality is progressively lowered in far and invisible areas.

Next sections detail each of these three ingredients. We demonstrate the efficiency of our approach in the Results section. Navigation Graphs (N G) is a graph structure capturing the topology and the geometry of the navigable space of a given environment. Navigable space is the flat part of an environment (flat enough to allow human walk, according to a user-defined threshold slope) free of any obstacle.

Navigation Graphs

A N G vertex captures a portion of the navigable space with a vertical cylindrical shape, high enough to include a human (typical height is 2 meters). A N G edge models a connection between two navigable cylinders, meaning they have a common portion of navigable space. Geometrically, passages between navigable cylinders are rectangular gates (with size as great as possible) included in the intersection of the two connected cylinders.

An example of Navigation Graph is displayed in Fig. 1 N G are computed automatically from the environment geometry and few user-defined parameters, as described in [START_REF] Pettré | A navigation graph for real-time crowd animation on multilayered and uneven terrain[END_REF], in 5 successive steps:

1. environment geometry sampling: we create a regular grid of points matching the environment surfaces. As multi-layered environments may be considered, a simple elevation is insufficient since several elevations may correspond to given horizontal coordinates. 2. grid mesh: two neighboring grid points are interconnected when the slope of the in-between space is beneath the user-defined maximum slope angle and free of obstacle. With this stage, we provide a mesh capturing the navigable space in a discrete manner.

3. clearance map: we compute the clearance for each grid point, i.e. the distance to the nearest obstacle or high-slope. Given the the grid mesh computation method, this distance is approximated by the distance to the nearest grid point not connected to all of its direct neighbors. Indeed, The lack of connection reveals the presence of an obstacle or a high-slope. 4. N G deduction: we then use a subset of grid points to compute the N G vertices. A graph vertex (cylinder) is created from a grid point by using it as centre and its corresponding clearance as radius. The grid point with maximum clearance is selected to create the graph vertex and all the grid points covered by the vertex are disabled for selection. The process is then reiterated until no more grid points remain for selection. Doing so, a majority of cylinders are centered on the Voronoï diagram corresponding to the environment. 5. visibility pre-computation: for each N G vertex, we compute the visibility of all other vertices according to the four main cardinal points. We can then use this information for visibility queries between moving entities.

On one hand, the use of an intermediate grid during computation makes the solution incomplete: navigable space is partially captured. But on the other hand, this discretization makes our method robust to complex and various environments.

Navigation Flows

A designer populates a virtual scene by creating as many Navigation Flows as desired. A Navigation Flow is a subset of pedestrians navigating endlessly between two locations of the environment. By choosing the number of pedestrians composing the flow as well as the locations to be joined, the designer is able to control the dispatching pedestrians in the scene. For example, the distribution of pedestrians into a virtual city is done according to the importance of some specific centers of interest, such as public buildings in a virtual city, shops, attractions, etc. Collision free paths joining two locations can be computed easily using navigation graphs by simple graph search algorithms, such as A* or Dijkstra's. The search results in a Navigation Path. A solution path is composed by a sequence of connected edges to follow, i.e., a sequence of rectangular passages to cross. This sequence of passages delimits a solution corridor joining the two desired locations. The width of this corridor allow to: dispatch people, individualize their trajectories and let them avoid each other.

The individualization of navigation trajectories is important in order to preserve the believability of the obtained crowd motion. Indeed, if all pedestrians follow exactly the same path when navigating, strange queue formations appear as well as jams at some places in the scene with a negative impact on the resulting crowd motion. Following this idea, a single Navigation Path is even insufficient to drive a navigation flow. For that, we search for alternative paths that will finally compose Navigation Flows: a second level of variety in trajectories is thus obtained.

This search for alternative paths is illustrated in Fig. 1. A navigation flow is created between locations 1 and 2 as indicated on the right image of the figure . A first navigation path (the shortest) is found. As mentioned before, this navigation path is geometrically similar to a corridor joining the two locations. But, still in Fig. 1, one can see that paths 2 and 3 also compose the navigation flow. These two alternative paths will allow pedestrians to join their destinations passing by one side or another of obstacles in the environment.

The existence of several navigation paths in a navigation flow is useful when jams appear during the simulation. The way pedestrians -belonging to an identical navigation flow -are dispatched inside a given solution path, and the way they are dispatched among the alternative navigation path is detailed in next Section. An extensive description of the Navigation Flows computation technique is given in [START_REF] Pettré | Crowds of moving objects: Navigation planning and simulation[END_REF]. Once a navigation flow is created, simulation starts. During simulation, pedestrians' position is updated according to the path they are following and their position relatively to spectator's point of view. In this Section we describe:

Scalable Pedestrian Simulation

1. How an individual trajectory is computed from the characteristics of the flow they belong to? 2. How the position-update accuracy is tuned according to the centrality and visibility of the corresponding pedestrian into the screen.

From Navigation Flow to Navigation Path A pedestrian belonging to a navigation flow first chooses a navigation path among the available ones (i.e., one of the corridor as displayed in Fig. 1). This choice is made each time the pedestrian is at one of the extremity of the flow and have to go back (i.e., when at location 1 going to location 2 or inversely in Fig. 1). This choice is irrevocable until he reaches his destination. Choice is based on the estimated travel time for each path belonging to the flow. Estimation takes into account the total length and density of population along the path, as described in [START_REF] Pettré | Real-time navigating crowds: scalable simulation and rendering: Research articles[END_REF]. Using a velocity /density statistical law v = f (density), we can estimate the required time for crossing each area. By summing these crossing times, we compute the estimated travel time for each path. For example, a path composed by n edges has a travel time estimated to:

ET T path = n i=0 ET T edgei with ET T edgei = lengthi v=f (density)
. The local densities of population are not varying rapidly, as a result, the estimated travel times are updated at low frequencies. Finally, pedestrians choose the path currently having the lowest estimated travel time.

From Navigation Path to Individual Path The distribution of pedestrians following a same navigation path is simply done according to an individual parameter p. This individual parameters (ranging from 0 to 1) determines a tendency of the pedestrian to walk on the left or the right of the followed corridor. More precisely, pedestrians follow way-points placed at each gate to cross. The position of the way-point W P within the gate AB is done as follow: W P = A + pAB.

Levels of Simulation

Main objective of the simulation is to get believable results with high performances. High performances can be obtained by applying a strategy of levels-of-detail to the simulation. The principle is to focus the dedicated computation resources where it is the most needed, i.e., in the most visible parts of the environment. In areas at a far distance of the user point-of-view, or in the invisible parts of the environment, the simulation can be progressively simplified in order to save precious computation-time. Two major components in simulations allow to diminish the complexity of the simulation:

1. update-rates: Updating each individual at each simulation step results in a complexity which is linear with the number of simulated pedestrians. However, the spectator is able to see only a few part of pedestrians at a given instant with respect to his field of vision and the presence of obstacles occluding parts of the environment. We first improve the simulation performances by updating at high-frequencies positions of the most visible pedestrians while the other ones benefit from less frequent updates. 2. reactive collision avoidance: reactive collision avoidance between pedestrians moving in the same area is probably the most time consuming task in the simulation, with quadratic complexity. Collisions between pedestrians is required where the attention of the spectator is focused, however, elsewhere, collisions are not checked. Note that pedestrians are already dispatched in the environment using our specific Navigation Flow technique (both on several paths and inside each navigation path). As a result, at far distances (and obviously in invisible areas), the lack of collision-checks between pedestrians is not easily detectable.

Figure 2 illustrates our Level-of-Simulation (LOS) strategy. On the left image, the distribution of LOS is displayed: most visible pedestrians are in red. For them, collision avoidance is enabled and their situation is updated at each simulation step. Obtained performances are plotted on the right (LOS4 plot). For pedestrians who are far from the user point of view, the collision avoidance is first disabled (pedestrians in green on the left image, corresponding to LOS3 on the plot). Then, situation update rate is progressively lowered (LOS2, 1 and 0, pedestrians in blue in the image). In conclusion, Level-of-Simulations is a key principle in order to focus available computation resources where they are the most needed, and to improve drastically simulation performances: with low update rates and no collision avoidance, 10 000 pedestrians can be simulated at 100Hz. In order to illustrate our method, we consider the following example of a virtual city displayed in Figure 3. This environment is large, 640 × 420 meters, and composed by approximately 100'000 triangles. A Navigation Graph is computed for this scene in 20 minutes approximately, composed by 5017 vertices and 8003 edges. Four visual output of the crowd simulation, we use the YAQ crowd visualization system developed at EPFL-VRlab.

Example and Discussion

In order to populate this environment, 7 navigations flows are sufficient. They join some main centers of interest into the city, such as an hotel, a train station, a circus, the old center of the city, etc. Each of the 7 Navigation Flow is composed by 5000 pedestrians, resulting in a virtual population made of 35'000 pedestrians. During Population Setup, each Navigation Flow is computed in less than a second, and as the simulation and visualization runs during this stage, we can evaluate immediately the impact of the insertion of new flows. Despite the small number of flows to populate this scene, all the places of this environment are occupied with pedestrians. This results from our specific dispatch method in Navigation Flow computations.

Conclusion

We presented a Navigation Graph based approach for populating scenes with crowds of pedestrians. The principle is to populate semi-automatically environments by planning the navigation of large crowds of pedestrians. Few high-level directives allow to populate large scenes with numerous pedestrians. We proposed efficient techniques in order to allow: first, interactive design of the population by answering quickly to user's navigation queries, and second, on-line simulation with real-time rates.

For efficient Navigation Planning, the key-idea is to search for varieties of solution. This allow to derive solution paths in order to individualize pedestrians' trajectories with no supplementary computation cost.

For efficient simulation of pedestrians, the key-idea is to use a level-of-details strategy in order to maintain a high simulation quality where it is the most needed, i.e., in front of the spectator, whereas the simulation quality is lowered elsewhere.

Our method fits the video-games field, and is applicable to the problem of populating large game scenes with large virtual population of pedestrians with low computation costs and believable results.

Fig. 1 .

 1 Fig. 1. Left Image: 2-D representation of a Navigation Graph. Right Image: Result of a Navigation Flow query: 3 Navigation Paths are found, each being a sequence of gates delimiting a corridor joining the 2 locations given as input of the query

  for a simple 2-D environment: obstacles are the blue regions of the figure, while the navigable area is left blank. The Voronoï diagram of the navigable area is displayed as well. N G vertices are represented as green circles centered on the Voronoï diagram. Edges are represented as red gates between overlapping vertices.

Fig. 2 .

 2 Fig. 2. Left Image: Distribution of different levels-of-details in scene. Most visible pedestrians (red) avoid each other, whereas far pedestrians (green and blue) do not avoid themselves and are updated at lower rates. Right plot: Performances obtained for each Level of Simulation LoS according to the number of pedestrians. LoS4, the most accurate, has quadratic complexity due to collision avoidance between pedestrians.

Fig. 3 .

 3 Fig. 3. Top images: Views of a virtual city, with 8 centers of interests corresponding to most important buildings (hotel, train station, church, circus, etc.). Bottom images: Views of the virtual population generated by creating several navigation flows between the centers of interest.

Acknowledgments

This work was realized in 2005-06 at EPFL-VRlab, directed by Pr. Daniel Thalmann. The project was funded by the European Research Community, by a Marie-Curie Action EIF 2005-mobility. The author would like to thank B. Yersin and J. Maïm who developed the crowd visualization system used in our examples, and M. Clavien and R. Krummenacher for environment design.