Enrico Natalizio
email: enrico.natalizio@hds.utc.fr

Rosario Surace
email: rsurace@deis.unical.it

Valeria Loscrí
email: vloscri@deis.unical.it

Francesca Guerriero
email: guerriero@deis.unical.it

Tommaso Melodia
email: tmelodia@eng.buffalo.edu

Filming Sport Events with Mobile Camera Drones: Mathematical Modeling and Algorithms

Keywords: Sport Event Filming (SEF) problem, Mobile Camera Drones, UAV Routing Problem, VRP with Soft Time Windows

We introduce and formulate the Sport Event Filming (SEF) problem. We are interested in controlling the movement of a set of camera drones that are filming the event by moving over the field where the event takes place. The objective of the problem is to maximize the satisfaction of event viewers while minimizing the distance traveled by the camera-drones. We model the static version of the SEF problem as a Vehicle Routing Problem with Soft Time Window (VRP-STW), where the whole sequence of actions in the event are known a priori. Since this assumption is unrealistic for real sport events, we propose two families of heuristics to solve the dynamic version of the problem, where the camera-drones do not have any knowledge of the input sequence and move in reaction to the movements of the protagonists of the event. The first family (Nearest Neighbor) is based on a technique used in robotic systems, whereas the second family (Ball Movement Interception) is designed based on specific characteristics of the SEF problem. We present extensive simulation results for both families in terms of average viewer satisfaction and traveled distance for the camera-drones, when several parameters vary.

I. INTRODUCTION

Most popular sport events are played by two teams that confront each other over a field of limited size. The game typically consists of a sequence of actions where usually one team attacks and the other defends. Typically, the objective of each team is to achieve a certain goal while preventing the opposite team from achieving the same goal. Usually the objective is accomplished by carrying, kicking, shooting or dropping a single object (the ball in the rest of the text), such as a ball, a football, a disk etc., in a specific area that is defended by the opposite team. The main actors of the game are the two teams, the ball and the referees, i.e., one or more people that look after player safety and make sure they obey the rules of the game.

In many sport events, a small fraction of the spectators enjoy the emotion of a close contact with the main actors and the game by surrounding the game field. All other spectators (viewers in the following) watch the game on TV (or on the Internet) where the event is broadcasted (or streamed) along with statistics, replays and comments. In recent years, several techniques and devices have been developed by event broadcasting companies to make the spectator feel inside the game field. Hence, new types of cameras such as automatic cameras and spider cameras have been deployed to cooperate with or replace traditional human-centric filming techniques. This work copes with the organization of a fleet of drones able to fly over a limited field to film a sport event with the objective of maximizing the satisfaction experienced by viewers who watch the game on TV. We refer to this problem as the Sport Event Filming (SEF) problem.

The problem is to develop strategies to coordinate the movement of a group of mobile robots in the presence of highly varying time-space constraints to film/monitor a sequence of actions while optimizing some specific objective. A solution to this problem is of interest for several application domains. Besides TV filming, it would be beneficial for environmental monitoring, disaster recovery, site inspection and exploration, etc. and would pave the way for the design of mission-oriented devices and the definition of their coordination/cooperation schemes.

The family of problems we deal with are usually referred to as Dynamic Vehicle Routing (DVR) problem, and the static variants taken into consideration in this work are all NP-hard problems. Specifically for the event filming problem some solutions have been proposed [START_REF] Daniyal | Multi-camera scheduling for video production[END_REF], [START_REF] Qureshi | Surveillance in virtual reality: system design and multi-camera control[END_REF], [START_REF] Zhou | A master-slave system to acquire biometric imagery of humans at distance[END_REF]. The main disadvantage of these solutions is that cameras are fixed. Thus, they cannot provide the same level of accuracy or entertainment given by mobile devices. To the best of our knowledge, no schemes using mobile devices have been proposed to solve this problem.

Our solution is based on controlling the movement of mobile cameras mounted on a fleet of Unmanned Aerial Vehicles (UAV). UAVs are usually equipped with a positioning system, storage memory, and a wireless transceiver. They can fly at considerable speed, 60 km/h for commercial drones and 220 km/h for military aircrafts. These devices can be controlled in a distributed fashion through the proposed algorithm to film a sport event while maximizing viewers' satisfaction and minimizing the travelled path.

The core contributions of our work can be outlined as follows:

• we describe and formulate an interesting and unexplored problem in the framework of self-organization of mobile video sensing devices;

• we model the problem as a centralized mathematical program by assuming that the whole sequence of actions in the event is known a priori;

• we propose two families of algorithms to solve the dynamic version of the problem in a distributed way and without any knowledge of the sequence of actions. The rest of this paper is organized as follows. Section II presents the Vehicle Routing Problem. The mathematical model is discussed in Section III, while in Section IV we propose two families of distributed techniques for the optimal placement of UAV camera-drones. These schemes are validated in comparison with the mathematical model, tested and analyzed through several simulation campaigns in Section V. Finally, Section VI concludes this paper.

II. VEHICLE ROUTING PROBLEM AND ITS EXTENSIONS

The Vehicle Routing Problem (VRP) can be described as the problem of defining an optimal delivery from one or more depots to a number of geographically scattered cities or customers. This planning aims at determining the best route that vehicles starting from their depots must travel to reach all customers in a certain period of time. Each customer must be visited exactly by one vehicle.

In the classic version of the VRP the goal is to minimize the total transportation cost. It is well known that VRP is an NP-hard (Nondetermistic Polynomial-Time Hard) problem [START_REF] Lenstra | Complexity of vehicle routing and scheduling problems[END_REF]. A special case of a Vehicle Routing Problem is the famous Traveling Salesman Problem (TSP), in which one is restricted to only one vehicle. Similar to VRP, TSP is an NP-hard problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

The basic version of the VRP is the Capacitated Vehicle Routing Problem (CVRP). In this version, all vehicles are initially located at the starting point, have a limited capacity equal for all and the only constraint is not to exceed vehicle capacity. CVRP is also known to be NP-hard [START_REF] Toth | SIAM monographs on discrete mathematics and applications[END_REF].

The VRP, TSP and CVRP cannot describe completely the Sport Event Filming (SEF) problem because they do not include time constraints. A possible extension of the CVRP is the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW introduces two new concepts with respect to the classical CVRP: a time window is assigned to each customer and a vehicle must remain in proximity of the customer for the entire duration of the time window. These time windows can be essentially of two types [START_REF] Golden | The vehicle routing problem: latest advances and new challenges[END_REF]: Hard and Soft Time Windows. In the first case none of the time windows may be violated, i.e., vehicle(s) must arrive at the customer location in time to serve the customer. In the case of Soft Time Windows, instead, these time windows can be violated at the price of paying a penalty. VRPTW is also an NP-hard problem [START_REF] Lenstra | Complexity of vehicle routing and scheduling problems[END_REF], and NP-complete when we fix the number of vehicles [START_REF] Savelsbergh | Local search in routing problems with time windows[END_REF].

The problem of determining the movement pattern for a certain number of UAV camera-drones when they have to film an event while maximizing viewer satisfaction and minimizing the total transportation costs can be considered as a special case of the VRPTW. Specifically, it can be classified as a Vehicle Routing Problem with Soft Time Windows (VRP-STW), where the sequence of points in the field to be filmed represent the customer to be served. If a specific point is not timely filmed, this affects only the satisfaction of the viewers without invalidating the overall solution.

Both VRP and its extensions assume that the cities to be visited (actions in the SEF problem) are known a priori and will not change during the execution of the solution. However, in real applications this assumption may be too strict. In reality, we have locations to be served that can be highly variable [START_REF] Kilby | Dynamic vrps: A study of scenarios[END_REF]: they can be born and die at any moment, their demands can change over time even when the solution has already been calculated. Also in the SEF problem, the position to film and the time to film that location change action by action.

The problem of planning routes through service demands that arrive during a mission execution is known as the Dynamic Vehicle Routing Problem (DVRP) [START_REF] Pavone | Dynamic Vehicle Routing for Robotic Networks[END_REF], because part or all the locations to reach are not known a priori.

In [START_REF] Pavone | Dynamic Vehicle Routing for Robotic Networks[END_REF], the authors identify three main approaches to address DVR problems. The first approach is to simply reoptimize every time a new event takes place; in the second approach, routing policies are designed to minimize the worstcase ratio between their performance and the performance of an optimal offline algorithm that has a priori knowledge of the entire input sequence; in the third approach, the routing problem is embedded within the framework of queueing theory and routing policies are designed to minimize typical queueingtheoretical cost functions such as the expected waiting time in the system for the demands.

Both families of distributed algorithms we present in this work follow the first approach. In the second family, we additionally consider specific characteristics of the problem to forecast the next locations to be covered.

III. MATHEMATICAL MODEL FOR STATIC SEF PROBLEM

In this Section we introduce the mathematical formulation of the sport event filming problem, aimed at determining the routes followed by a set of camera-drones which simultaneously maximize the satisfaction of viewers and minimize the total traveled distance of the camera-drones. The problem is modeled as a Vehicle Routing Problem with Soft Time Windows (VRP-STW). In the formulation, we assume knowledge of the entire sequence of actions. Since this assumption is not realistic, we will use the results obtained by solving to optimality the mathematical model only as a comparative benchmark against the distributed solutions proposed in this work. Nevertheless, the effort of modeling the whole problem is very useful when the approach used to tackle the dynamic version of the problem is to re-optimize every time a new event takes place with no knowledge of the sequence of actions.

A. Definitions and initial assumptions 1) Definitions: Action

An action consists of a sequence of simultaneous movements performed by the main actors of the event: the ball (or football, disk, etc.), the players and the referees. The complete characterization of an action is composed of a quadruple (x, y, z, t) for each actor, where (x, y, z) are the coordinates of the actor's position in a tri-dimensional spatial reference system and t is the time instant when the actor is in that position. We assume that the camera-drones move on a plane that is fixed, parallel to the plane where the actions take place and high enough so as not to interfere with the actions. To correctly film the game, cameras will have to match the players (x, y) -coordinates exactly by moving over their heads and filming them from a perpendicular perspective. It is worth noting that in reality a perfect matching of the (x, y) -coordinates is not necessary, because the camera aperture diameter can compensate for moderate errors in camera positioning. Nevertheless, this assumption remarkably simplifies the mathematical modeling and, to obtain a fair comparison, it will be used also for evaluating the proposed distributed algorithms. From the camera perspective the images will be flattened on the game field plane. Hence, the z -coordinate for both the players and the drones can be neglected in the definition of the problem and its solution.

Our future work will also consider movement of the camera over the z -axis or, equivalently, its zooming capabilities. A transversal (rather than perpendicular) perspective of filming, which is possible by considering the rotational capabilities of the cameras, would lead to a totally different problem and mathematical formulation that we do not consider in this work.

An action is defined within a time window, which consists of the following time instants and intervals:

• t birth : is the moment when the possession of the ball is gained by another player;

• t start : is the moment when the player who has possession of the ball starts moving with it;

• t stop : is the moment when the player in possession of the ball loses it;

• T f ly : is the time interval between the loss of the ball by one player (t stop ) and the gain of it by another (t birth ).

We are not interested in T f ly because we assume that a typical camera can follow the movement of the ball from one player to another for the whole event. Therefore, we will not use T f ly in optimizing the viewer satisfaction. Instead, we want to offer the viewers the possibility of enjoying the performance of the individual players involved in the event by "personalized" shots when they get possession of the ball. The duration of an action is the time interval between t birth and t stop . As discussed in Section III-A2, drones can recognize when a player is in possession of the ball. Hence, the time interval between t start and t stop involves all the movements of the player in possession of the ball as well as the consequent movements of the drone that is filming the current action, even when the player moves away from the ball reception position. Event An event is a sequence of actions that takes place in a sizelimited field and in a predefined time span. In the following, we will use a subscript for t birth , t start and t stop that indicates the action within the whole event.

Viewer satisfaction

The satisfaction S k i of the viewer by watching the i th action of the event, filmed by the k th drone is modeled as

       S max t k arr,i < t start,i -S max • t k arr,i -tstart,i tstop,i-tstart,i + S max t start,i ≤ t k arr,i ≤ t stop,i 0 t k arr,i > t stop,i (1)
where t k arr,i is the arrival time of drone k at the position of action i. It is worth observing that the no-linear piecewise function ( 1) can be linearized by using binary variables. The related linearized function has been used when testing the proposed model. The total satisfaction of the viewer is obtained by averaging the sum of the satisfaction experienced from each action on the whole event. The satisfaction of the viewer is represented graphically in Fig. 1. It is maximized if the drone arrives at the action location before t start and it decreases linearly until becoming 0 when t = t stop . Hence, the definition of viewer satisfaction matches with the definition of Soft Time Window, because the only effect of a drone not arriving before t start at the action location is to reduce the overall satisfaction of the viewer without invalidating the solution of the problem. 2) Relevant assumptions related to the drones: With regards to the drones movement, we refer to UAV camera-drones as any aircraft that has a limited energy E provided by its battery and capable of moving autonomously at constant speed v. We assume that our UAV camera-drones are equipped with a positioning system (GPS or indoor positioning system), a camera, storage memory and a wireless transceiver to send the filmed images to a base station and to allow communication and cooperation with other UAV camera-drones. These drones are capable of identifying and localizing a target by some radio frequency identification tag applied to it or by using a sensor network [START_REF] Melodia | Cross-layer QoS-Aware Communication for Ultra Wide Band Wireless Multimedia Sensor Networks[END_REF], [START_REF] Pudlewski | Compressive Distortion-Minimizing Rate Control for Wireless Multimedia Sensor Networks[END_REF], [START_REF] Rullán-Lara | Uav real-time location using a wireless sensor network[END_REF] deployed on the side of the field and capable of locating the target and communicating with the drones. Therefore, drones are able to recognize when a player is in possession of the ball because player and ball tags will be overlapping. When this occurs, the drone that is filming the action "sticks" to the player and follows him until the ball is released, and the current action terminates. Further extension of this work will consider in detail the communication aspects of filming and transmitting the images to a base station.

In the mathematical model we refer to the total traveled distance as the objective to be minimized (rather than the consumed energy) since this is the limiting factor for the drone [START_REF] De Filippis | A minimum risk approach for path planning of uavs[END_REF], [START_REF] Hammouri | Voronoi path planning technique for recovering communication in uavs[END_REF].

B. Variables and model assumptions

In this section we introduce all the variables, constraints and assumptions used to formulate the proposed mathematical model. At the end of this subsection, we will illustrate the constraints of the model.

1) Variables:

• F = L × W size-limited field;

• 0 → T event time duration;

• M = {1...m} drones able to move in 2 dimensions with constant speed v. Initially they have the same energy E;

• N = {1...n} with 0 < m < n actions spatially distributed in F and time-distributed in 0 → T ;

• N 1 = N 2 = ... = N m-1 = N m initial
positions of the drones, before they start moving to film the actions;

• N n final position of the drones, after they filmed the whole event.

• t birth,i birth time of action i, ∀i

∈ N \ {N 1 ...N m }; • t start,i start time of action i, ∀i ∈ N \ {N 1 ...N m }; • t stop,i stop time of action i, ∀i ∈ N \ {N 1 ...N m }; • t birth,i < t start,i < t stop,i ∀i ∈ N \ {N 1 ...N m }; • t stop,i < t birth,j ∀i, j ∈ N \ {N 1 ...N m } with i < j
ensures that actions are sequential and non-simultaneous;

• t stop,n = T ensures that all actions terminate within the given time frame.

• d k max maximum distance that drone k is able to travel; • d ij Euclidean distance between the location of action i and action j, ∀i, j ∈ N ;

• d ik ≤ d ij + d jk triangle inequality for the distances among actions locations ∀i, j, k ∈ N ;

• t k arr,i arrival time of drone k to the location of action i ∀i ∈ N \ {N 1 ...N m } and ∀k ∈ M ;

• t k dep,i departure time of drone k from the location of action i ∀i ∈ N \ {N n } and ∀k ∈ M ;

• t k i→j = dij v
time required by drone k to move from action i to action j ∀i, j ∈ N and ∀k ∈ M ;

• x k ij on/off variable with the following meaning:

x k ij = 1 if arc i -j is crossed by drone k 0 else
• y k i on/off variable with the following meaning:

y k i =
1 if drone k was on game action i 0 else

• S k i viewer's satisfaction due to the drone k that filmed action i ∀i ∈ N \ {N 1 ...N m and N n } and ∀k ∈ M . We already defined this in (1);

• S max = 1 maximum satisfaction obtainable by the viewer in a single action;

• Ψ = m k=1 n-1 i=m+1 S k i n-m-1
average viewer satisfaction;

• Ψ min minimum guaranteed satisfaction for the viewer;

2) Assumptions:

• The time and spatial sequences of actions are known;

• All actions (except the last) must be filmed by 1 drone;

• Since the last game action is not an action to film but only a dummy location where the drones come together so that maintenance operations can be performed, the distance traveled to reach this final position is not considered in the cost for the drones.

• All actions ∈ N \ {N 1 ...N m } have their own Soft Time Window already presented in Fig. 1;

C. Problem Formulation

The objective function is given by the total distance traveled by the drones involved in the sport event filming (to be minimized). This can be expressed as

minimize m k=1 n-1 i=1 n-1 j=1 d ij • x k ij (2)
This objective has to be accomplished by satisfying the following constraints:

m k=1 y k i = 1 ∀i ∈ N \ {N n } (3)
m k=1 y k n = m (4)
y k i ≥ x k ji ∀i, j ∈ N and ∀k ∈ M (5)
y k i ≥ x k ij ∀i, j ∈ N and ∀k ∈ M (6)
m i=1 n j=m+1 x k ij = 1 ∀k ∈ M (7) n-1 i=1 x k in = 1 ∀k ∈ M (8) n-1 j=1 m k=1 x k ji = 1 ∀i ∈ N \ {N 1 ...N m and N n } (9) n j=1 m k=1 x k ij = 1 ∀i ∈ N \ {N n } (10) n i=1 x k iz - n j=1 x k zj = 0 (11) ∀z ∈ N \ {N 1 ...N m and N n } and ∀k ∈ M i j=1 x k ij = 0 ∀i ∈ N and ∀k ∈ M ( 12
) m i=1 m j=1 x k ij = 0 ∀k ∈ M (13) n-1 i=1 n-1 j=m+1 d ij • x k ij ≤ d k max ∀k ∈ M (14)
t k arr,i = 0 ∀i ∈ {N 1 ...N m } and ∀k ∈ M (15)
t k arr,j = n i=1 (t k dep,i + t k i→j ) • x k ij ( 16
)
∀j ∈ N \ {N 1 ...N m } and ∀k ∈ M t k dep,i ≥ 0 ∀i ∈ N and ∀k ∈ M (17) t k dep,i ≥ t stop,i • y k i (18) ∀i ∈ N \ {N 1 ...N m and N n } and ∀k ∈ M t k dep,i ≤ t stop,n • y k i ∀i ∈ N and ∀k ∈ M (19) t k dep,n = t stop,n ∀k ∈ M (20) t k arr,n ≤ t stop,n ∀k ∈ M (21) Ψ = m k=1 n-1 i=m+1 S k i n -m -1 ≥ Ψ min ( 22
)
where S k i is defined as in [START_REF] Bullo | Dynamic vehicle routing for robotic systems[END_REF]. Each action (except the final one) must be filmed exactly by one drone (3), whereas the last dummy action will make all the drones move together (4). The action j must be filmed by the drone that moved from a previous action i for that purpose [START_REF] Hammouri | Voronoi path planning technique for recovering communication in uavs[END_REF][START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Drones must start from different initial positions and terminate in the same final position, respectively [START_REF] Kilby | Dynamic vrps: A study of scenarios[END_REF][START_REF] Lenstra | Complexity of vehicle routing and scheduling problems[END_REF].

Exactly one entering and one outgoing arc for each action can be crossed and must be present in the final solution [START_REF] Melodia | Cross-layer QoS-Aware Communication for Ultra Wide Band Wireless Multimedia Sensor Networks[END_REF][START_REF] Pavone | Dynamic Vehicle Routing for Robotic Networks[END_REF][START_REF] Pudlewski | Compressive Distortion-Minimizing Rate Control for Wireless Multimedia Sensor Networks[END_REF]. Actions are sequential, therefore drones cannot reach an action occurred earlier in time than the current one and can not produce loops, i.e. they cannot move away from the action and then return onto the same action [START_REF] Qureshi | Surveillance in virtual reality: system design and multi-camera control[END_REF]. The drones cannot travel towards the initial positions of other drones [START_REF] Rullán-Lara | Uav real-time location using a wireless sensor network[END_REF], and the whole route of each drone should not exceed the maximum allowed traveled distance [START_REF] Savelsbergh | Local search in routing problems with time windows[END_REF]. The arrival time of the drones at the locations of the initial action is the starting time of the whole event [START_REF] Toth | SIAM monographs on discrete mathematics and applications[END_REF], instead, the arrival time at the location of action j (excluded the initial actions) by the drone k must be equal to the sum of the departure time from the previous location i and the time needed to move from i to j, [START_REF] Zhou | A master-slave system to acquire biometric imagery of humans at distance[END_REF]. A drone cannot move before the event started (17), it can leave the location of the filmed action only after the action terminated (18), and cannot move after the event is over (19). A drone must never leave the location of the last action, which is used to collect all the drones in the same location for maintenance operations (20), and this location must be reached before the end of the event (21). The average satisfaction experienced by the viewer must never be less than a certain minimum value (22).

IV. DISTRIBUTED ALGORITHMS FOR DYNAMIC VRP-STW

When no knowledge of the event sequence of actions is available a priori, the static vehicle routing problem with soft time windows of Section III becomes a dynamic vehicle routing problem that requires different optimization techniques.

In Section II we mentioned that three different approaches have been identified to tackle the dynamic version of the problem. The first of these approaches simply proposes to reoptimize every time a new event takes place. This approach is the most suited for the specific communication and movement capabilities of the drones to offer a feasible and practical solution to the event filming problem. In fact, the sub-optimal solution will be computed action-by-action by the drones that cooperate by exploiting their communication capabilities in a distributed and self-organized fashion. For this purpose, we introduce in the distributed strategies the coordination time, T coord , which is the time needed by the drones to communicate with each other and determine which of them will move to follow the newly generated action.

In the following we present two families: Nearest Neighbor (NN) and Ball Movement Interception (BMI), each of them consisting of four different distributed techniques to solve the event filming problem.

A. Nearest Neighbor

The Nearest Neighbor technique for DVR problems in robotic system is presented in [START_REF] Bullo | Dynamic vehicle routing for robotic systems[END_REF]. The core idea is that viewer satisfaction increases when a drone is able to reach the location of the current action as quickly as possible, and that the minimum traveled distance is achieved by the closest drone. Thus, the drone that is the closest to the location of the action is the one chosen to move and film the action. The following three techniques are extensions of the basic NN technique.

B. Nearest Neighbor-Division Field

A disadvantage of the NN technique is that when a sequence of actions occurs in a limited area, the same drones will be chosen to film it. If the duration of this sequence extends over time, it would cause one drone to reach its maximum feasible traveled distance much earlier than the others.

Based on these considerations, we introduce the Nearest Neighbor-Division Field (NN-DF). In the NN-DF technique, each drone is assigned to a portion of the field, and it will film the actions that are located inside that portion.

This technique has the disadvantage of not choosing the drone that is the nearest to the current action, which can result in a reduced satisfaction for the viewer. We will see in Section V the effects of this with respect to the reduced area for each drone to monitor.

C. Nearest Neighbor with Specular Repositioning

In the previous two techniques only one drone moves when a new action is born. The Nearest Neighbor with Specular Repositioning (NN-SR) technique considers drones as belonging to a pair. When one of them, k, is chosen to move to film an action for which it is the nearest neighbor, the drone that is closest to the position specular to the action position, k, moves as well to mirror the movement of the first. More precisely, let L and W be the length and the width of the field. When drone k moves to the position of the new action (x a , y a ), k will move to (L -x a , W -y a ). It is worth noting that drones are not coupled at the beginning of the event, instead k is chosen action-by-action depending on the proximity to the action specular position. We expect that this technique, which results in drones traveling more than the previous techniques, will be more reactive and timely in filming the actions so as to offer a higher satisfaction to the viewer.

D. Nearest Neighbor with Quasi-Specular Repositioning

A generalization of the NN-SR technique is the Nearest Neighbor with Quasi-Specular Repositioning (NN-QSR). The NN-SR technique makes pairs of drones move specularly. As we have already highlighted, this behavior can lead to a quick depletion of the maximum allowed traveled distance, due to the specular movements of the drone ( k) that is not filming any action. Thus, the idea behind the NN-QSR is to make the center of the field be an attractor for k while it is repositioning in the direction of k's specular position.

The attraction strength on the movement can be modulated through an appropriate detour factor, 0 ≤ β ≤ 1. When β = 0, no detour is applied on the movement of k, which moves to the specular position in respect of the current action position, and NN-QSR coincides with NN-SR. When β = 1, k is completely detoured towards the center of the field. For intermediate values between 0 and 1, k move on a point on the straight line between these two extreme points. More precisely, if (x a , y a ), L, W are the positions of the new action, the length and the width of the field, respectively, then k will move to

(L • (1 -β 2 ) -x a • (1 -β), W • (1 -β 2 ) -y a • (1 -β))
. By detouring the movement of k, we expect a higher satisfaction of the viewer as compared to the NN and NN-DF techniques, without introducing a high traveled distance expenditure as in the NN-SR technique.

E. Ball Movement Interception

All the previous techniques work well if t birth and t start are sufficiently far in time to allow a drone to reach the action location before t start . In fact, these techniques try to solve the dynamic version of the proposed problem simply by adapting as quick as possible the position of one (or one pair of) drones. None of them try to forecast the location to film for next action before its t birth . As we described in Section III-A, our static model introduces the time of "flight" of the ball when the ball is not possessed by any player, T f ly . This interval of time between t stopi and t birthi+1 could be used to forecast the location of next action.

We can realistically assume that drones, which are able to constantly detect the ball and its location, are also able to easily compute their trajectory. For the sake of simplicity, in this work, we consider only that the ball moves along straight lines. We consider the parabolic trajectory of the ball as flatted on the straight line lying on the game field plane, and we do not take into consideration special effects that can be given to the ball.

By assuming that drones know the trajectory of the ball, they can estimate the next player who will hold the ball. Through this estimation, before the ball reaches the next player they can start moving towards the straight line between the position of the previous action and that of the player expected to receive the ball. Thus, we introduce a new family of techniques, called Ball Movement Interception (BMI), which includes all the previous techniques augmented by this knowledge: Ball Movement Interception (BMI), Ball Movement Interception with Division Field (BMI-DF), Ball Movement Interception with Specular Repositioning (BMI-SR) and Ball Movement Interception with Quasi-Specular Repositioning (BMI-QSR). It is important to note that we do not assume that unexepected interceptions of the ball destined to a specific player are neglected. In fact, such events would simply cause a degradation in the performance of this family of techniques.

V. PERFORMANCE RESULTS

In this Section we will show three simulation campaigns illustrating selected results obtained for both the model and the algorithms when several parameters vary. We consider the average viewer satisfaction as the output parameter for assessing the quality of the route chosen for the drones, and the total traveled distance as the output parameter representing the cost of the route. The first simulation campaign is used to validate the distributed techniques and tune the main parameters. In the second campaign we study the impact of the detour factor, β, on the performance of the Specular Repositioning techniques. The third simulation campaign is a more general comparison among the different distributed techniques. The results have been achieved by using LINGO 9.0 for the mathematical model and MATLAB 7.9.0.529 (R2009b) for the algorithms, and they have been averaged over 1000 runs with a confidence interval of 95%. The parameters presented in Table I are used in all the simulation campaigns, specific differences will be highlighted in each campaign subsection. In Table II

TABLE II: algorithms and their acronyms

We simulate the behavior of the algorithms when the number of actions in the event and the duration of each action vary, respectively. The number of actions is useful to characterize the time-space variability of the actions in the event, whereas the duration of an action represents the dynamicity of the event. Both these input parameters depend on the kind of sport that has to be filmed and their characterization is left as a future work. In our simulations we also used a variable number of drones (2 ÷ 6), but for matter of space we will be able to show few results of scenarios with 2 and 4 drones.

A. Validation of the distributed algorithms

A a priori knowledge of the whole event actions gives a significant advantage to the mathematical model with respect to our algorithms. Therefore, in this section we verify that the mathematical model achieves results that are an upper bound for the viewer satisfaction and a lower bound for the total traveled distance with respect to the basic heuristics of the NN and the BMI families.

In this campaign, we performed simulations when both the number of actions and the action maximum duration vary. In the interest of space we report only the diagrams of the maximum duration of an action varying between 6 and 12 s, with a step of 2 s. All parameters for this simulation campaign are reported in Table III. As previously stated, the actual duration of each is randomly chosen in the interval between the fixed minimum and the maximum. The number of actions in the event is set to 20. From Fig. 2, we can see that the action maximum duration does not affect the total traveled distance and that the NN technique is very close to the centralized optimum obtained through the mathematical model, whereas the BMI needs 40% more movements than NN. This extra movement is compensated by an increased performance in terms of viewer satisfaction. The BMI performance is between 10% and 25% better than NN. The highest difference among NN and BMI is for short actions, that is the case when the ball moves frequently among the players, while both the techniques tend to reach the mathematical model when the maximum duration of the action increases.

B. Performance evaluation varying detour factor

In this simulation campaign we want to investigate the impact of the detour factor on the performance of the QSR techniques. Hence, we compare the results of NN-QSR and BMI-QSR, when the detour factor, β, varies in the range {0 ÷ 1}. As we did for the first simulation campaign, we let the number of actions in the event and the duration of an action vary, as shown in Table IV for former parameter has been increased to match the time duration of a real event. The performance of the two techniques in terms of average viewer satisfaction for different number of actions is reported in Fig. 4, and traveled distance for different maximum durations of the actions in Fig. 5.

From Fig. 4 we observe that use of the ball movement interception does limit the need to reposition the drone specular to the drone that is filming the action. The BMI technique leads to a high viewer's satisfaction when the attraction strength towards the center of the field increases, whereas the NN-QSR technique presents a maximum when the detour factor is between 0.5 and 0.6. This also means that different detour strengths should be applied depending on the used technique. As expected, the viewer satisfaction experienced with the BMI technique is higher on average.

The same behavior for the NN-QSR technique is presented 5, where we can appreciate the existence of a minimum in the distance traveled by the drones when the detour factor is around 0.6. The BMI-QSR improves its performance when the detour factor grows until values very close to 1. It is interesting to remark that for both the techniques, a decrease in the distance traveled by the drones corresponds to an increase in the satisfaction experienced by the viewer. Comparatively, the NN-QSR technique leads the drones to travel about 1.3km on average less than the BMI-QSR technique, with a corresponding about 18% on average of decrease in the viewer's satisfaction. For both the output parameters, the number of actions and the action maximum duration do not significantly impact the performance of the different techniques, therefore the three simulated algorithms produce overlapping curves.

C. Comparison of Positioning Techniques

This last simulation campaign, whose main parameters are in Table V, shows the results when all the distributed techniques are applied to a scenario with a variable number of actions and a fixed action maximum duration (Fig. 6,7) and a fixed number of actions and a variable action maximum duration (Fig. 8,9).

In Fig. 6 we show that the distance traveled by the drones grows linearly with respect to the number of actions for all the algorithms. Thus, it is easy to predict the distance that each technique will make drones travel through an estimate of the number of actions a real event will consist of. As expected, the NN technique is the best in terms of traveled distance, both when the Division Field is used and when it is not. The basic technique of the BMI family performs as the third best for this metric, which is a very encouraging result because of the consideration we will make about the average viewer satisfaction. On average the BMI technique makes drones travel about 73 km more than NN in the considered interval. The techniques with Specular Repositioning are the worst for this metric because of the distance traveled by the drone that does not film the action.

The situation is reversed in Fig. 7, which shows the average viewer satisfaction. All techniques in the BMI family achieve a higher satisfaction than the corresponding techniques in the NN family. The distance between the best techniques of the two families for this parameter, which are the basic technique and the SR technique, is 14% on average. When the upper limit on the feasible traveled distance is reached, both the satisfaction achieved by BMI-SR and BMI-QSR start decreasing, since drones are not allowed to move anymore. Thus, the instantaneous satisfaction goes to zero and the average satisfaction decreases. Until the feasible distance limit is reached, the two techniques of the BMI family perform very similarly, the only main difference is that the QSR let drones travel more efficiently. Instead, we can appreciate some difference in the performance of the same techniques for the NN family, the SR technique performs 2% better on average than the QSR technique.

In Fig. 8 we can appreciate the traveled distance when the maximum duration of the actions varies. We can see that all the proposed algorithms are scalable with respect to this input parameter, and the heuristics ranking is the same of that in Fig. 6. 9 shows a logarithmic growth of the average viewer's satisfaction when the actions maximum duration increases. Very quick and short actions create troubles to all the algorithms, which do not achieve more than 30% of viewer's satisfaction, whereas they perform much better and reach 90% of satisfaction when the maximum duration is the upper value. On average, the BMI techniques have a gain of 15% over the corresponding NN techniques.

VI. CONCLUSION

We have introduced the Sport Event Filming problem, whose objective is to maximize the average satisfaction of a sport event viewer while minimizing the distance traveled by the camera-drones that film the event. First, we modeled the problem as a Vehicle Routing Problem with Soft Time Window. We then considered the dynamic version of the problem where knowledge of the entire sequence of actions is not assumed to be known a priori. The dynamic version of the Sport Event Filming can be treated as a Dynamic Vehicle Routing problem. We solved it by re-optimizing the position

Fig. 1 :

 1 Fig. 1: Game action's soft time window.2) Relevant assumptions related to the drones: With regards to the drones movement, we refer to UAV camera-drones as any aircraft that has a limited energy E provided by its battery and capable of moving autonomously at constant speed v. We assume that our UAV camera-drones are equipped with a positioning system (GPS or indoor positioning system), a camera, storage memory and a wireless transceiver to send the filmed images to a base station and to allow communication and cooperation with other UAV camera-drones. These drones are capable of identifying and localizing a target by some radio frequency identification tag applied to it or by using a sensor network[START_REF] Melodia | Cross-layer QoS-Aware Communication for Ultra Wide Band Wireless Multimedia Sensor Networks[END_REF],[START_REF] Pudlewski | Compressive Distortion-Minimizing Rate Control for Wireless Multimedia Sensor Networks[END_REF],[START_REF] Rullán-Lara | Uav real-time location using a wireless sensor network[END_REF] deployed on the side of the field and capable of locating the target and communicating with the drones. Therefore, drones are able to recognize when a player is in possession of the ball because player and ball tags will be overlapping. When this occurs, the drone that is filming the action "sticks" to the player and follows him until the ball is released, and the current action terminates. Further extension of this work will consider in detail the communication aspects of filming and transmitting the images to a base station.In the mathematical model we refer to the total traveled distance as the objective to be minimized (rather than the consumed energy) since this is the limiting factor for the drone

Fig. 2 :Fig. 3 :

 23 Fig. 2: Distributed algorithms validation: total traveled distance when the maximum duration of the actions varies

Fig. 4 :Fig. 5 :

 45 Fig. 4: QSR techniques: average viewer's satisfaction when the detour factor and the number of actions vary

Fig. 6 :Fig. 7 :

 67 Fig. 6: Distributed algorithms comparison: total traveled distance for fixed actions maximum duration (6 [s])

Fig. 8 :

 8 Fig. 8: Distributed algorithms comparison: total traveled distance for a fixed number of actions (1000)

Fig. 9 :

 9 Fig. 9: Distributed algorithms: average viewer's satisfaction for a fixed number of actions (1000)

  , we list the distributed algorithms names and the corresponding acronyms.

	Parameter	Value
	Size of the game field (L × W )	110 × 80 [m 2 ]
	Max Distance Feasible by Drones	65 [km]
	Speed of Drones	15 [m/s]
	Action Min Duration (t birth → tstop)	0.2 [s]
	Ball Min and Max Speed	{1 ÷ 40} [m/s]
	Coordination Time (T coord )	0.2 [s]
	Threshold Satisfaction (Ψmin)	95%
	Max Satisfaction (Smax)	1
	Actions Spatial and Temporal Distribution	random
	Number of run for each scenario	1000

TABLE I :

 I Fixed parameters used for all simulations

	Name	Acronym
	Mathematical Model	MM
	Nearest Neighbor	NN
	Nearest Neighbor with Division Field	NN-DF
	Nearest Neighbor with Specular Repositioning	NN-SR
	Nearest Neighbor with Quasi-Specular Repositioning	NN-QSR β
	Movement Interception	BMI
	Movement Interception with Division Field	BMI-DF
	Movement Interception with Specular Repositioning	BMI-SR
	Movement Interception with Quasi-Specular Repositioning	BMI-QSR β

  . The range considered

	Number of Drones	2
	Drone k Position Action Max Duration (t birth → tstop)	{(-1) k L 4 + L 2 , W 2 } {6 ÷ 12}[s]
	Number of Actions	20

TABLE III :

 III Simulation parameters used for distributed algorithms validation

TABLE IV :

 IV Simulation parameters used for simulating NN-QSR and BMI-QSR

TABLE V :

 V Simulation parameters used for distributed algorithms comparison


Fabien Danieau

Julien Fleureau

Philippe Guillotel

Nicolas Mollet

Marc Christie

Anatole Lécuyer

HapSeat: Producing Motion Sensation with Multiple Force-feedback Devices Embedded in a Seat

Keywords: H5.2 [Information interfaces and presentation]: User Interfaces. -Haptic I/O Design, Experimentation sensation of motion, force-feedback, haptic seat, audiovisual experience

We introduce a novel way of simulating sensations of motion which does not require an expensive and cumbersome motion platform. Multiple force-feedbacks are applied to the seated user's body to generate a sensation of motion experiencing passive navigation. A set of force-feedback devices such as mobile armrests or headrests are arranged around a seat so that they can apply forces to the user. We have dubbed this new approach HapSeat. A proof of concept has been designed which uses three low-cost force-feedback devices, and two control models have been implemented. Results from the first user study suggest that subjective sensations of motion are reliably generated using either model. Our results pave the way to a novel device to generate consumer motion effects based on our prototype.

INTRODUCTION

Motion simulation is usually provided by a motion platform [START_REF] Laycock | Recent developments and applications of haptic devices[END_REF]. Typically the user's whole body is moved to generate various sensations such as accelerating, falling or passing * email: fabien.danieau@technicolor.com over bumps. While these devices generate a realistic sensation of motion with 6DoF, they are not designed for domestic settings and they are too expensive for the mass consumer market. Immersive experiences with motion effects are thus currently limited to amusement parks or "4D Cinemas". In this article we present the HapSeat, a novel approach for producing motion sensations in a consumer settings using multiple force-feedback devices embedded in a seat. Three low-cost actuators which simulate 6DoF effects of motion are used. The motion effect is generated by adjuncts to the structure of the chair rather than moving the whole chair. A proof-of-concept prototype has been designed and constructed, which uses actuators held by an armchair-shaped structure (see figure 1). Two models to control the device has been implemented: a Physical Model which computes forces supposed to be felt during a movement, and a Geometrical Model which modifies the structure to match the position and posture that characterize a movement. A user study was conducted to assess this approach. Participants reported a sensation of motion. When applied to a passive navigation simulation in a real or virtual environment, our results show that the HapSeat increases the quality of the user experience. We considered four factors in the measurement of the QoE: realism (of the simulation), sensory (involvement of the sense of touch), comfort and satisfaction. In this paper we first review the literature on human motion perception and motion simulators (section 2). Then the HapSeat is introduced in section 3 while section 4 details the proof of concept. The user study is discussed in section 5. Finally a conclusion and perspectives are provided in section 6.

RELATED WORK

Human motion perception

The perception of motion is a complex sensation resulting from the integration of multiple perceptive inputs from different systems: visual, auditory, vestibular and kinesthetic [START_REF] Berthoz | The brain's sense of movement[END_REF][START_REF] Harris | Simulating self-motion I: cues for the perception of motion[END_REF]. The visual system contributes to this perception by providing an estimation of distances between the body and landmarks. A displacement of the body will modify these distances and add the perception of self-motion. Moving visual cues can often trigger a sensation of selfmotion even though the viewer is stationary [START_REF] Riecke | Using the perceptually oriented approach to optimize spatial presence & ego-motion simulation[END_REF]. This illusion is called vection. The auditory system may also contribute to this perception by locating the body relative to "acoustic" landmarks [START_REF] Valjamae | Travelling without moving: auditory scene cues for translational self-motion[END_REF]. But the main contributor to the perception of motion is the vestibular system. Located in the inner ear, this organ is composed of three orthogonally-oriented semi-circular canals and two otolith organs. The canals allow rotational movements to be detected while otolith organs contribute to the perception of linear accelerations. Finally, it is interesting to note that haptic cues provided by the kinesthetic system also influence the sensation of motion. The kinesthetic system provides information about limb positions. When an elevator goes up, one feels the motion thanks to the proprioreceptive receptors in joints and muscles of the legs. The tactile sense also provides information about motion: internal receptors detect movements of visceral organs and act as accelerometers. These visceral graviceptors are especially to be be found in the region of the kidney. The somatosensory system indicates the direction of gravity through pressure patterns all over and inside the body [START_REF] Trousselard | Contribution of tactile and interoceptive cues to the perception of the direction of gravity[END_REF].

Motion simulators

Motion simulators are well-known devices designed to make the user feel motion. They are intensively used in driving or flight simulators for training purposes. Most are based on a Stewart's platform [START_REF] Dasgupta | The Stewart platform manipulator: a review[END_REF], a 6 Degrees of Freedom (DoF) platform driven by 6 hydraulic cylinders. A motion simulator is basically a seat attached to this kind of platform. While the user navigates the virtual environment, the seat moves to generate a sensation of motion. These systems are often used in virtual reality rooms or 4D cinemas but few are designed for the end-user consumer. To the best of our knowledge, the D-Box company 1 is one of the few actors in this market, having developed an armchair placed on four actuators that is suitable for an enduser's living-rooms. This seat generates 3DoF motion effects (pitch, roll and heave) for movie viewing and consumer applications. Despite this attempt to succeed in the consumer 1 http://www.d-box.com environment, this chair remains expensive and limited to 3DoF motion effects. The sensation of motion can also be induced in a less invasive way by force-feedback devices that simulate the kinesthetic system. Ouarti et al. applied a force to users' hands as they watched an optic flow stimulus [START_REF] Ouarti | Method for simulating specific movements by haptic feedback, and device implementing the method[END_REF]. The system was expected to generate an illusion of motion with force-feedback: when the interface pulled the user's hand, the user experienced a sensation of forward motion. Similarly, Danieau et al. used a 3DoF force-feedback device to induce the sensation of global movement in a video [START_REF] Danieau | A framework for enhancing video viewing experience with haptic effects of motion[END_REF]. This system was designed to enhance audiovisual content as a cheaper alternative to motion platforms, but the movement simulated was limited to 3DoF (translations only). The use of haptic illusions to enhance the audiovisual experience has also been explored by Israr et al., who designed a chair with several vibration devices embedded at different locations [START_REF] Israr | Tactile brush: drawing on skin with a tactile grid display[END_REF]. Actuators in the chair were activated in such a way that the user felt a continuous stimulus. Though no effect of motion was claimed in this study, Riecke et al. have showed that vibrotactile feedback may generate a vection effect by improving the realism of the simulation [START_REF] Riecke | Towards lean and elegant self-motion simulation in virtual reality[END_REF]. To sum up, there remains an important gap between haptic devices which do not, or only partially simulate, a sensation of motion, and complex simulators which are efficient in conveying motion but remain expensive and not well adapted to the consumer environment. We propose our HapSeat as a solution to fill this gap.

HAPSEAT: A NOVEL APPROACH FOR SIMULATING 6DOF MOTION

We propose to enhance the experience of passive navigation in virtual or cinematic content using 6DoF motion effects generated by multiple force-feedback devices. Instead of moving the whole user's body as on motion platforms, only some parts of the body are stimulated. As described in section 2.1, the perception of motion results from the stimulation of various parts of the body (vestibular system, visceral organs, kinesthetic system). Our approach is built on the hypothesis that local haptic cues suffice to trigger a sensation of self-motion. Previous work has shown that a 3DoF force-feedback applied to a user's hand may simulate a 3DoF motion effect in a video viewing context [START_REF] Danieau | A framework for enhancing video viewing experience with haptic effects of motion[END_REF]. But the simulated motion is limited to 3DoF (translations). Using only one or two 3DoF force-feedback devices is not sufficient to invoke a 6DoF sensation of motion [START_REF] Shah | How to build an inexpensive 5-dof haptic device using two novint falcons[END_REF] (translations and rotations). Extending the approach to three 3DoF devices in order to apply three force-feedback stimulus to the user's body offers the possibility of simulating a global 6DoF effect of motion. A plane looping sensation could be simulated by pulling the head backward and lifting both arms simultaneously, while a car braking could be simulated by pushing both the head and hands forward. This concept can be extended by stimulating other regions of the body, using 5x3DoF devices for instance.

PROOF OF CONCEPT

The prototype developed as a proof of concept relies on three actuators. Two stimulate the user's hands, while a third stimulates the head. As the vestibular system is located in the head, stimulating this part of the body should heighten the illusion of simulated motion. Figure 2 shows a schematic representation of the concept and offers an introduction to our notation. The motion description associated with a simulation is transmitted to a model at each instant t which computes the ideal position G A for each local actuator A. This position is then rendered by the haptic rendering algorithm as a force FA. Each step of this workflow is detailed in this section.

Prototype of the HapSeat

An aluminum structure was designed to allow the positioning of the three actuators around an ordinary chair. The user passively rests his or her head and hands on each of the 3DoF actuators while watching a projection on a screen positioned in front of the chair (see figure 4). The head actuator is equipped with a block of foam for the user's comfort. At rest (no rendered motions), the three actuators (H), (LA) and (RA) maintain the head, right arm and left arm of the user at the central positions GH , GLA and GRA respectively. When the simulation starts, each actuator generates 3DoF forces on its respective body part within the limits of the cubic workspaces in figure 2. Our current prototype uses three Novint Falcons2 actuators. These devices are robust, relatively cheap and the forces generated are appropriate for safe movement of the user's head and hands.

Motion data

We focus on the case of a first person point-of-view simulation, whose intention is to mimic for the user the sensation of motion that the principal actor would have felt at the time of its recording. The audiovisual content is augmented with extra data describing the motion in terms of the linear acceleration a(t) and the angular velocity w(t). Let us define FN as the navigation frame of the actor and FB the frame associated with his body, centered on a point C (his chest for instance). The actor's motion is modeled as a rigid body motion described by two quantities a(t) = [a(C ∈ FB|FN )]F B = {ax(t), ay(t), az(t)} t (the gravity being removed [START_REF] Sabatini | Quaternion-based extended kalman filter for determining orientation by inertial and magnetic sensing[END_REF]) and

w(t) = [w F B /F N (t)]F B = {wx(t)
, wy(t), wz(t)} t (where the [x]F notation designates the vector x expressed in the frame F ). This kind of content can be easily produced by a video camera equipped with an inertial measurement unit. Danieau et al. used this setup to capture first-person point of view videos [START_REF] Danieau | A framework for enhancing video viewing experience with haptic effects of motion[END_REF]. The capture device was attached to an actor's torso to record both his movement and a video of his field of view. Therefore a(t) and w(t) describe the motion of the actor.

Models for motion simulation

Each actuator (H, LA, RA) moves to create the feeling of 6DoF global motion modeled by the quantities a(t) and w(t) as if the motion of the main actor was mapped onto them. Two models to control the device were devised. The first model is based on a Physical Model. The related acceleration applied to some parts of the body of the actor (here the head, left hand and right hand) are derived from the parameters of the global motion, a(t) and w(t) and then reproduced on the user by the corresponding actuators. The second model, referred to as Geometrical Model, aims at reproducing the position and attitude of the main actor on the basis of a more metaphorical paradigm.

Physical Model

In this model the accelerations felt by the main actor at his head, PH , and at his left and right shoulders, PLS and PRS, are computed through a rigid body approach, where the motions of the hands are considered equivalent to the movements of the shoulders. Knowing a(t) and w(t) at the origin of his body frame FB, the accelerations of a new point P of the rigid body may be computed by the following mechanical relation (time derivation of the kinematic torsor):

[a(P ∈ FB|FN )]F B = a(t) + dw dt ∧ --→ GP + w ∧ (w ∧ --→ GP ) (1)
The new position G A for an actuator A is the formulated in terms of displacement from its initial and central position GA by:

----→ GAG A =   sx 0 0 0 sy 0 0 0 sz   (2a) (a(t) + dw dt (t) ∧ --→ GPA + w(t) ∧ (w(t) ∧ --→ GPA)) (2b)
where G A is the new application point at time t, and sx, sy, sz are scaling factors which map the actual motions of the three actuators in their workspaces. Those scaling factors are computed so as to use the workspace of the actuator in an optimal way. This involves compromises between the use of the largest possible space, so as to have a larger amplitude in the final rendering, while avoiding any saturation. These scaling factors are computed is a preprocessing step that consists of finding the maximal amplitude of the acceleration rendered by the actuator.

In this context the new application points G H , G LA and G RA are computed from the intial points GH , GLA and GRA, and sx = sy = sz.

Geometrical Model

This second model aims to make the chair reproduce the position and posture of the moving actor during the simulation. Two kinds of motion will be rendered: linear accelerations and orientation changes. The linear acceleration rendering is simply performed by a simultaneous translation of each of the different local actuators along the 3D vector given by a(t). The scene pose changes rendering is trickier. It makes the assumption that the rotation speed of the current scene, modeled by w(t), may be rendered by rotating the position of the three actuators around the center modeled by a point G located near the user's sternum (see figure 2) and with a 3D angle modeled by w. Then the faster the object is turning, the bigger the angle of rotation. Moreover, if the rotation stops (i.e. w(t) = 0), the actuators are at rest. The new position G A of the actuator A for a rotation around G can be expressed:

---→ GG A = (Rx(wx(t))Ry(wy(t))Rz(wz(t))) ---→ GGA (3)
i.e.:

----→

GAG A = ---→ GG A - ---→ GGA (4a) = (Rx(wx(t))Ry(wy(t))Rz(wz(t))) -I3) ---→ GGA (4b)
where Rx, Ry and Rz are the 3D rotation matrices around their respective X, Y and Z axes and I3 is the identity matrix of R 3 .

A complete 6DoF motion is a combination of linear accelerations and rotations. A function f is proposed to model the incorporation of both these types of information in our system. The proposed system has intentionally decoupled the linear motions from the rotational ones. This assumption is somewhat unrealistic from a mechanical point of view, but nevertheless makes sense in the context of passive navigation. If the motion to be rendered is a pure translation or a pure rotation, this decoupling is not a restriction. The difficulty arises when the motion to be rendered is a combination of translation and rotation. We make the assumption that a user would unconsciously expect to feel the dominant motion in the scene more strongly. Then, if GA represents the new position of the actuator A at time t and GA its initial position, we have:

----→ GAG A = f (   sx 0 0 0 sy 0 0 0 sz   a(t), (5a)
(Rx(mxwx(t))Ry(mywy(t))Rz(mzwz(t)

) -I3) ---→ GGA) (5b) with f (B, C) = B B + C C B + C (6)
From this equation, the new application points G H , G LA and G RA are computed from the initial points GH , GLA and GRA.

In addition, sx, sy, sz on one hand and mx, my, mz on the other hand represent different scaling factors to map the actual motion represented by the couple (a(t), w(t)) in the workspace of the different actuators. As previously described, those scaling factors are computed so as to use the workspace of each actuator in an optimal way. More precisely, computing the scaling factors mx, my and mz is one using a preprocessing step that consists of in finding the maximal amplitude f with respects to the values of a(t) and w(t) over the whole time interval. An exhaustive numerical analysis is thus performed to find the joint optimal discretized values mx, my and mz. Several solutions may be admissible in the parametric space and the one that offers the best isotropic behavior is selected.

Output of the models

A comparison of the outputs of the models is described in this section to highlight their main differences. The outputs of simple translations and then rotations are compared together. A linear forward acceleration on the Z axis can be described by a(t) = {ax(t) = 0, ay(t) = 0, az(t) = t} t and w(t) = {wx(t) = 0, wy(t) = 0, wz(t) = 0} t . Such a movement is rendered in the same way by both models. All actuators are moving simultaneously along the Z-axis as if the user were being pushed forward. The same behavior is observed for the other translations on Y and X axes. In these cases, the user is pushed upward or pulled toward the left side. Secondly self-rotations are tested. For instance a left rotation around the Y-axis can be described by a(t) = {ax(t) = 0, ay(t) = 0, az(t) = 0} t and w(t) = {wx(t) = 0, wy(t) = t 2 2 , wz(t) = 0} t (the angular acceleration w (t) is linear). In this case (see figure 3), the outputs of the models are different. With the Physical Model the user's hands are moving along the X-axis toward the center while the head is not moving. With the Geometrical Model, the right hand is going forward (Z-axis) and the left hand is going backward (Z-axis) while the head slightly moves to the right side (Xaxis). The same behavior is observed for rotations on other axes: the Physical Model renders self-rotation by an attraction of each part of the body toward the center G and the Geometrical Model renders them with desynchronized movements. A 6DoF movement that combines translations and rotations is thus managed differently by each model depending on the amount of rotations.

Haptic Rendering

Whatever the model selected to control the chair, for each instant t of the simulation, each actuator A (namely H, LA and RA) has to be in its targeted position G A (namely G H , G LA and G RA ). Most force-feedback devices (such as Novint Falcons) are impedance haptic devices, and the position of the actuator is thus not directly controllable. Indeed this kind of device is designed to sense the current position of the actuator and to provide a reaction force to the user. A classical spring-damper model may be used to control these devices in pseudo-position. The force FA applied to an actuator A is computed by:

FA = k(G A -PA) -dVA (7)
where G A is the targeted position, PA the current position of the actuator, VA its velocity, k the spring constant and d the damping constant.

Provisional Conclusion

The models and the rendering algorithm were integrated to a home-made multimedia player that allowed the haptic rendering on three force-feedback devices to be synchronized with the audiovisual playback. The haptic loop runs at 1KHz and the value of the force FA is updated at each instant t. The control software is written in C++ and runs on an ordinary personal computer. Our initial tests showed that the force capabilities and workspaces of the Novint Falcons were sufficient to move the user's head and hands. Our system enables the experience of novel motion sensations when viewing virtual navigation (see figure 4).

USER STUDY

A user study was conducted to evaluate the quality of the simulated motion and to quantify its impact on the user's perceived quality of experience (QoE). 17 participants took part in the study, aged from 21 to 54 (x=36.11 σx=11.11). Five were female, two participants were left-handed and one already used a Novint Falcon device. The pilot study was presented as a single experiment lasting 20 to 30 minutes. Each participant was first introduced to the Novint Falcon and given a demonstration of its force capabilities. This step aimed to reduce the "surprise effect" for novice users. Participant was asked to passively experience each stimulus (see figure 4 and section 5.1) and then answer a questionnaire (see section 5.3).

Sequences: Haptic-Audiovisual Contents

Two driving sequences were created to test our device, and evaluate the sensation of motion and quality of experience (see figure 5). We generated two 1-minute videos and the associated descriptions of the global motion in terms of a(t) and w(t). Our first sequence was a video of a real car driving session. Data was first captured using a front passenger equipped with a camera and an inertial measurement unit that sampled data at 30Hz. The second sequence was a video of a virtual car racing video game. The main camera of the 3D simulation was placed inside the car in order to have a passenger point of view of the race. The visual output of the simulation was recorded while the accelerations and turn-rates of the car were extracted at 50Hz from the physics engine.

Variables

To evaluate the quality of the simulated motion (and of the models) and the impact of this haptic feedback on the QoE, we defined four types of haptic feedback to be rendered with each sequence. Physical Feedback, computed from the physical model; Geometrical Feedback derived from the geometrical model; No Haptic Feedback in which only the audiovisual content was displayed, serving as a control to show how the other conditions impact on the QoE; and lastly Random Haptic feedback was provided. This random feedback was derived from low-pass filtered white noise (cutoff frequency Fc = 0.5Hz) played throughout the video. The amplitude of the signal was limited to the capabilities of the actuators. This last feedback was not synchronized to the video and was used to evaluate the effect of providing a continued haptic feedback. All height conditions (two videos sequences x four types of haptic feedback) were presented in random order to the participants.

Measurement of QoE: questionnaire

A questionnaire was designed to evaluate the QoE of passive navigation enriched with haptic feedback. QoE relates to the subjective user experience with a service or an application [START_REF] Kilkki | Quality of experience in communications ecosystem[END_REF]. This questionnaire was based on the four factors we wanted to evaluate [START_REF] Danieau | A framework for enhancing video viewing experience with haptic effects of motion[END_REF]: realism, comfort, sensory and satisfaction. "Sensory" characterized how the haptic feedback contributed to the immersion. "Realism" describes the de-gree to which the simulation is realistic and consistent with the user's representation of the real world. This factor is particularly helpful in evaluating the quality of the simulated motion. "Comfort" measures how comfortable is the system. "Satisfaction" determines measures user enjoyment. Each factor was evaluated by questions rated on a 5-point scale. A mean was calculated for each factor. The sum of the scores gave a global QoE score. Table 1 presents the questions used to evaluate the QoE.

Factor Question

Realism

How much did this experience seem consistent with your real-world experiences? How strong was your feeling of self-motion?

Sensory

How much did the haptic feedback contribute to the immersion? Were the haptic and visual feedback synchronized together?

Comfort

Was the system comfortable? How distracting was the control mechanism? Satisfaction How much did you enjoy using the system? Table 1: QoE Qestionnaire. Each question is rated on a 5-point scale from 1 (Not at all) to 5 (Totally)

Results

Two hypothesis are tested: the HapSeat enhances the quality of experience and generates a sensation of motion. Shapiro-Wilk and Bartlett tests were performed on our data and the normality and homoscedasticity for most distributions could not be assumed. Hence non-parametric tests were used to analyze the results presented in this section. As described above, a score for the four factors, realism, sensory, comfort and satisfaction were obtained using a questionnaire (see figure 6 and table 2). The main result confirms our first hypothesis. Our device significantly enhances the quality of experience (Friedman Anova: p = 8.44e -08 < 0.05). The Wilcoxon test with the Holm-Bonferroni correction has been used for the post-hoc analysis (see table 3). With the haptic feedback computed from the Physical or Geometrical model, the QoE is significantly higher than without haptic feedback (p < 0.05). However the QoE of the Geometrical Model is not significantly different from the QoE of the Physical Model (QoEG = 15 ≈ QoEP = 14.20, p = 0.5575 > 0.05). It seems that haptic feedback consistent with the video is necessary to improve the QoE: user scores for random feedback are not statistically different to the no feedback condition (QoEN = 8.36 ≈ QoER = 9.45, p = 0.4816 > 0.05). This tendency is observable for three factors. Presenting users with haptic feedback computed from our models resulted in significant increases in their reporting of Realism (Friedman Anova, p = 3.80e -08 < 0.05), Sensory (Friedman Anova, p = 7.02e -08 < 0.05) and Satisfaction (Friedman Anova, p = 3.86e -07 < 0.05) scores. However Comfort remained equal for all conditions: the Friedman Anova is significant, p = 1.27e -03 < 0.05, but Wilcoxon tests cannot confirm this hypothesis, p > 0.05 (see table 3). Finally no significant differences are found for the QoE of each model between the two sequences Real Car and Virtual Car (Wilcoxon test, pGeo = 0.3933 and p P hy = 0.4173 > 0.05). In order to evaluate the second hypothesis, the answers to the two questions of the Realism factor were analyzed (see figure 7, Q1 on top and Q2 on bottom and table 4). The results from Q1 suggest that the simulated motion was perceived as realistic (Friedman Anova p = 3.60e -05 < 0.05). A Wilcoxon test with the Holm-Bonferroni correction was also performed on our data (see table 5). Again, no statistical difference between the Physical and Geometrical models is observed (Q1P = 3.6 ≈ Q1G = 3.8, p = 0.6356 > 0.05) but they are significantly different from the Random and None conditions (p < 0.05). The results from Q2 follow the same pattern. Both models provided a strong sensation of motion, significantly higher than Random and None conditions (Friedman Anova p < 0.05, Wilcoxon tests p < 0.05).

Discussion

Our results suggest that the HapSeat does enhance the user experience during passive navigation simulation. Both rendering models significantly increased the QoE compared to the Random and None feedback conditions. Our results also suggest that the synchronization of the haptic effect with the visual content is important.

In this study, no statistical differences are found between the models. This is probably due to the nature of the simulation (car driving) which does not fully exploit the 6DoF. Only translation (car acceleration) and rotation (turns) were included in the two sequence tested. More complex content, such as a plane or spaceship flight or a rollercoaster ride, might produce results that highlight differences between the models. In addition, the parameters of the models could be tuned to increase their differences. Each one is composed of several factors which impact the use of the workspace.

The Physical Model could be also improved by modeling the segments and joints of the user's skeleton instead of treating the user as a single rigid body. We observed that the simulated motion was not perceived in the same way by all participants. Some of them found that the haptic feedback computed from our models was reversed.

For instance, they expected to be pushed backward instead of being pulled forward when the car (real or virtual) was moving straight forward. However this observation was not consistent among all users. Some participants expected to feel the reaction force instead of the acceleration only during turns, but found the feedback acceptable for linear transla- How much did this experience seem consistent with your real-world experiences? How strong was your feeling of self-motion? tions, i.e. when the car was going straight forward. Though some participants seem to prefer a reversed force feedback in specific cases, this does not mean that the output of the models should necessarily be reversed. One might posit two user profiles "direct" and "reversed" to address this, it can certainly be said that the design of the associated haptic feedback is not straightforward. The perception of motion simulated by force-feedback devices require further evaluation. Studies are also needed to understand the influence of a haptic stimulus on the perception of a visual stimulus.

Our the device was reported as comfortable and user friendly. The perception of comfort was similar with and without haptic feedback, suggesting that no extra discomfort is introduced by the system. Nevertheless comfort could be improved, especially for the headrest. Some participants reported that the haptic feedback for the real car sequence contained too much vibration. This may be explained by the greater sensitivity of proximal joints to movement than distal joints [START_REF] Jones | Kinesthetic sensing. Human and Machine Haptics[END_REF]. Similar displacements are perceived more strongly on the head than on the hands. If this vibration that contribute to realism when perceived by the user's hand, might be too intense for the head. So far the haptic rendering for all actuators is the same. But dedicated algorithms could be implemented for each device. As a minimum, a low-pass filter could be applied on the output of the actuator H to reduce vibration.

CONCLUSION & PERSPECTIVES

We have presented the HapSeat, a novel approach to the simulation of 6DoF effect of motion. Instead of moving the whole user's body as it is traditionally done with motion platforms, we stimulate only parts of the body. Our hypothesis was that, coupled with a visual stimulus, these local stimulations could trigger a sensation of motion and thus improve the quality of experience. Results of a user study show that the two control models, Physical and Geometrical, succeed at enhancing the quality of experience during passive navigation. Furthermore participants reported having experienced a realistic sensation of self-motion. Future work to improve of the models and study of the user's perception of the simulated motion is planned. The prototype could be extended by adding more points of stimulation, for instance, for the legs. The input capabilities of the devices could be used to allow the user to interact with the simulation, offering the prospect of extending applications of the HapSeat to flight or driving simulators, teleoperation, etc. To conclude, this original approach yields a new way to simulate a sensation of motion in a consumer environment and allows the creation of more immersive applications.

Figure 1 :

 1 Figure 1: Prototype of the HapSeat. Left: seat structure with 3 force-feedback devices. Right: the system in use.

Figure 2 :

 2 Figure 2: Simulating 6DoF motion with 3x3DoF force-feedback devices. While the three local devices are moving, the user is expected to feel a sensation of motion in relation to the visual content.

Figure 3 :

 3 Figure 3: Output of the models (Physical on the left, Geometrical on the right) for a left rotation around Y-axis of 15 seconds. The position in meters is plotted for each actuator LA, RA and H, and for each axis.

Figure 4 :

 4 Figure 4: The user, comfortably installed on our device, is experiencing passive navigation enhanced by a haptic effect of motion.

Figure 5 :

 5 Figure 5: Haptic-Audiovisual contents. Left -Real video sequence of a car driving. Right -virtual car race.

Figure 6 :

 6 Figure 6: Quality of experience. The haptic feedback provided by the Physical and Geometrical models significantly improves the QoE.

Figure 7 :

 7 Figure 7: Realism factor details. Users found the simulation realistic (top) and experienced a stronger sensation of self-motion (bottom).

Table 2

 2

	: Means (x) and Standard deviations (σx) for
	each model with respects to each factor. A Friedman
	Anova (χ 2 , df, p.value) has been performed on each
	factor.

Table 3 :

 3 Pairwise comparison of each model for each factor using Wilcoxon test with Holm-Bonferroni correction.

	Question	Q1	Q2
	Model
	None	1.2647 0.5338	1.2059 0.3976	x σx
	Random	2.1563 0.9259	2.7813 1.0483	x σx
	Physical	3.5588 0.7045	3.7353 0.8860	x σx
	Geometrical	3.8 0.5606	4.0333 0.6935	x σx
		20.4615	12.86	χ 2
	F. Anova	2 3.60 -05	2 1.61e -03	df p
		***	*	sig.

Table 4 :

 4 Means (x) and Standard deviations (σx) for each model with respects to Q1 and Q2. A Friedman Anova (χ 2 , df, p.value) has been performed on each question.

Table 5 :

 5 Pairwise comparison of each model for both question using Wilcoxon tests with the Holm-Bonferroni correction.

http://www.novint.com