Gang Chen

Thierry Fraichard

A Real-Time Navigation Architecture for Automated Vehicles in Urban Environments

This paper presents a novel navigation architecture for automated car-like vehicles in urban environments. Motion safety is a critical issue in such environments given that they are partially known and highly dynamic with moving objects (other vehicles, pedestrians. . . ). The main feature of the navigation architecture proposed is its ability to make safe motion decision in real-time, thus taking into account the harsh constraints imposed by the type of environments considered. The architecture is based upon an efficient publish/subscribebased middleware system that allows modularity in design and the easy integration of the key functional components required for autonomous navigation: perception, localisation, mapping, real-time motion planning and motion tracking. After an overall presentation of the architecture and its main modules, the paper focuses on the "motion" components of the architecture. Experimental results carried out on both a simulation platform and a Cycab vehicle in a parking environment are presented.

I. INTRODUCTION

Intelligent Transport Systems (ITS) have been considered in the past ten years or so as a possible response to a number of problems related to the increased usage of private vehicles worldwide, namely pollution, congestion and safety problems [START_REF] Parent | A dual mode personal rapid transport system[END_REF]. One of the long-term goals is to reduce the use of the private car in downtown areas by offering novel modern and convenient public transportation systems. The Cybercar concept is a vivid example of such innovative transport systems. Cybercars are road vehicles with fully automated driving capabilities. A fleet of such vehicles would form a managed transportation system, for passengers or goods, on a network of roads with on-demand and doorto-door capability (http://www.cybercars.org). This concept emerged in Europe in the early 1990's and was demonstrated for the first time in the Netherlands in December 1997 for passenger transport at Schipol airport. As of today, Cybercars operate on dedicated and protected road-networks only. The next step is to take them to open environments featuring other vehicles, pedestrians, etc.

Autonomous navigation requires to solve a number of challenging problems in domains as different as perception, localization, environment modelling, reasoning and decisionmaking, control, etc. The problem of designing and integrating these functionalities within a single navigation architecture is of a fundamental importance. Since Shakey's pioneering attempts at navigating around autonomously in the late sixties [START_REF] Nilsson | Shakey the robot[END_REF], the number and variety of autonomous navigation architectures that have been proposed is large (see [START_REF] Nourbaskhsh | Introduction to Autonomous Mobile Robots[END_REF]). From the motion determination perspective, these navigation architectures can be broadly classified into deliberative (aka motion planning-based) versus reactive approaches: deliberative approaches aim at computing a complete motion all the way to the goal using motion planning techniques, whereas reactive approaches determine the motion to be executed during the next time-step only. Deliberative approaches have to solve a motion planning problem [START_REF] Lavalle | Planning Algorithms[END_REF]. They require a model of the environment as complete as possible and their intrinsic complexity is such that it may preclude their application in dynamic environments: indeed, the vehicle has a limited time only to determine its future course of action (by standing still for too long, it might be collided by one of the moving objects). Reactive approaches on the other hand can operate on-line using local sensor information: they can be used in any kind of environment whether unknown, changing or dynamic. This accounts for the large number of reactive approaches that have been developed over the years, eg [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF], [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF], [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF], [START_REF] Minguez | Nearness diagram (ND) navigation: collision avoidance in troublesome scenarios[END_REF], etc. Most of today's reactive approaches however face a major challenge: as shown in [START_REF] Fraichard | A short paper about safety[END_REF], motion safety in dynamic environments is not guaranteed (in the sense that the vehicle may end up in a situation where a collision inevitably occurs at some point in the future).

The primary contribution of this paper is a motion planning module that takes into account these two constraints, namely the real-time and safety constraints. It is achieved thanks to the two concepts of Partial Motion Planning (PMP) [START_REF] Benenson | Toward urban driverless vehicles[END_REF] and Inevitable Collision States (ICS) [START_REF] Fraichard | Inevitable collision states -a step towards safer robots?[END_REF]. PMP is a planning scheme that take into account the real-time constraint explicitly. PMP has an anytime flavor: when the time available is over, PMP is interrupted and it returns a partial motion, ie a motion that may not necessarily reach the goal. This partial motion is then passed along to the navigation system of the vehicle for execution. Of course, since only a partial motion is computed, it is necessary to iterate the partial motion planning process until the goal is reached. Like reactive decision scheme, PMP faces the safety issue. ICS are called upon to address this issue. An ICS is a state for which, no matter what the future trajectory followed by the vehicle is, a collision with an object eventually occurs. For obvious safety reasons, a vehicle should never ever end up in an ICS. By computing ICS-free partial motion at each time-step, the vehicle's safety can be guaranteed in real-time.

The secondary contribution of this paper is a presentation of the navigation architecture hosting the PMP-ICS motion planner. It is based upon an efficient publish/subscribe-based middleware system named DDX [START_REF] Corke | DDX: A distributed software architecture for robotic systems[END_REF] that allows modularity in design and the easy integration of the key functional components required for autonomous navigation: perception, The architecture presented in this paper is a DDX-based real-time modular architecture. DDX is a publish/subscribebased middleware [START_REF] Corke | DDX: A distributed software architecture for robotic systems[END_REF] that is used to provide the navigation modules with an abstract view of the Cycab, its sensors and its environment. Fig. 1 depicts the overall architecture. Below the DDX layer is the Cycab layer: it features the Cycab, its sensors and the environment either in simulation or for real. Above the DDX layer is the Navigation layer: it features the different key modules required for autonomous navigation: localization, world modelling, motion planning and motion tracking (these modules are detailed in section V). To complete the architecture, a Geographic Information System (GIS) is used to provide static information about the environment (road geometry and topology, traffic signs and traffic rules. . . ), as opposed to the dynamic information about the environment (other vehicles, pedestrians. . . ) which is computed by the Cycab layer through sensor-data processing (or directly by the simulator). The following sections describe the DDX, the Cycab and the Navigation layers respectively.

III. DDX LAYER

DDX provides an efficient communication mechanism to allow multiple processes to share data. It is implemented as a store, ie a block of shared memory (possibly distributed over several computers), that is used to store shared information. The Catalog function is used to ensure the coherence of the information contained in the different stores (using the UDP/IP communication protocol). As far as the navigation architecture proposed is concerned, the data contained in the DDX store comprises four main data structures concerning either the Cycab or its environment:

• Cycab: information concerning the Cycab:

-CycabState: encoder values, wheel velocities. . . .

-CycabCommand: actuator commands (speed, steering angle). -CycabPose: position and orientation of the Cycab.

• Landmarks: position of the observed landmarks, ie the salient features of the environment used for absolute localization (see section V-B).

• Trajectory: trajectory that is to be executed by the vehicle (see section V-C). It is a sequence of (state, time) couples.

• Moving objects: list of the moving objects observed in the environment. Each moving object is characterized by it shape, position, orientation and velocity. Table I summarizes how these data structures are used by the different navigation modules. The GIS data used by Localization is the list of the landmarks' position. World Modelling on the other hand gets the road geometry from GIS. Future Model is a description of the current state of the environment (fixed and moving objects) plus a prediction of the future motion of the moving objects (see section V-A).

IV. CYCAB LAYER

A. Cycab Vehicle

The Cycab vehicle is a lightweight urban electric vehicle which is specifically designed for downtown areas (Fig. 5). It can be driven using a joystick (manual mode) but is also equipped to be fully computer-controlled (automatic mode). Its maximum speed is 30 km/h and it can accommodate two people along with their luggage. It is used by the different Inria research centers as an experimental platform for research on Intelligent Transport Systems. Its mechanical structure is similar to that of a small golf cart. It integrates four motor wheels and a motorized mechanical jack for steering. Micro-controllers are used to control of the motorwheels and the steering mechanism. An embedded PC under Linux RTAI is used for the overall control of the vehicle. Two CAN (Controller Area Network) buses are used for communication between the different hardware components of the vehicle. It can be equipped with various sensors such as GPS, IMU, video cameras and range sensors (more details at http://www-lara.inria.fr/cycaba).

B. Cycab Simulator

The Cycab Simulator has been designed to facilitate the design and test of the algorithms for automated driving in dynamic urban environments that will be implemented on the real Cycab. It is based upon the MGengine simulation engine (http://mgengine.sourceforge.net) and permits the simulation of the Cycab vehicle, its sensors and its environment. Figs. 7(a) and 8(a) depict snapshot of the simulator GUI (more details at http://cycabtk.gforge.inria.fr).

V. NAVIGATION LAYER This section presents the main modules used for autonomous navigation. There are four of them: World Modelling and Localization that deals with building a model of the vehicle's environment and localizing the vehicle inside this model. Motion Planning and Motion Tracking respectively deals with computing and executing a trajectory. These modules are described in the next four sections with a particular emphasis on the "motion" modules.

A. World modelling

The primary purpose of the World Modelling module is to build a model of the environment of the vehicle that can be used for autonomous navigation purposes. Road-like environments feature both fixed objects (such as building) and moving objects (such as other vehicles and pedestrians) and the World Model must represent them both. In the roaddriving context, static information about the environment can be obtained from a GIS and it is up to the on-board sensors to provide the dynamic information. In addition to that, the Motion Planning module requires additional information about the topology of the road network and a model of the future, ie information about the future behaviour of the moving objects (see section V-C). The next three sections respectively overview how are obtained the static and dynamic information and the model of the future.

1) Static Information: Static information about the environment, eg limits of the roadway, geometry of the obstacles, etc. are assumed to be a priori known and made available in a Geographic Information System (GIS). For the purpose of navigation in urban environments, a two-dimensional map of the environment (ie a set of polygonal obstacles) suffices (Fig. 2). In addition to this two-dimensional map, the GIS contains information about the landmarks of the environment that are used for localization purposes (see section V-B). The structure of the roadway is also included in the GIS: it is represented as oriented lanes connected together in a network. This structure is exploited by the Motion Planning module to determine the route that is to be followed in order to reach a given goal (see section V-C).

2) Dynamic Information: The dynamic information includes all the environmental objects that are not represented in the GIS. It concerns the moving objects of the environment mostly, eg other vehicles, pedestrians, etc. It is up to the different exteroceptive sensors to detect these moving objects on-line. The Motion Planning module requires not only the position and shape of these moving objects but also information about their dynamics (linear and/or angular velocity, acceleration, etc.) and whatever information that can be used to predict their future behaviour (if it is signaling a turn for instance). For the time being, only the linear velocity information is determined. In the architecture proposed, it is assumed that the information about the moving objects is a direct output of a sensorprocessing step corresponding to the different sensors used. In other words, the detection and tracking of the moving objects is performed in the Cycab layer, not the Navigation layer (Fig. 1). Detecting and tracking moving objects is one of the key challenge in perception. A wide range of techniques are now available for different sensors, eg video cameras, laser or radar, (see [START_REF] Blackman | Design and Analysis of Modern Tracking Systems[END_REF]). Experiments have been carried out using video cameras and laser range sensor and the tracking techniques presented in [START_REF] Vasquez | A novel self organizing network to perform fast moving object extraction from video streams[END_REF] and [START_REF] Benenson | Toward urban driverless vehicles[END_REF] (Fig. 3).

3) Future Prediction: Decision-making in general and motion planning in particular involves a certain degree of reasoning about the future: you decide now what you will do next: knowledge about the future is therefore necessary. When it comes to motion planning, long-term knowledge about the future motion of the moving objects is required. This knowledge is usually not available a priori and one has to resort to prediction. In the architecture proposed, motion prediction relies upon the assumption that pedestrians and vehicles do not move randomly but follow typical "motion patterns" which may be learned and then used in a prediction phase. Fig. 4 illustrates the motion prediction process: the left image depicts the networks of motion patterns that have been learned from a set of observed moving object's motions. The center image shows a moving object being tracked by the vision system. The right image plots the different goals that this moving object is likely to reach with their associated probabilities. The trajectory leading to these goals is also computed. The reader is referred to [START_REF] Vasquez | Intentional motion on-line learning and prediction[END_REF] for more details.

B. Localization

The primary purpose of the localization module is to determine where the vehicle is in its environment (position and orientation). The Localization module combines odometric relative positioning and landmark-based absolute positioning in order to achieve the required robustness and accuracy of localization. Odometric localization is achieved by using encoder data (wheels, steering angle) and standard Extended Kalman Filters (EKF). Landmark-based localization is achieved by matching observed landmarks, ie specific features of the environment, with a priori known information about the landmarks present in the environment (obtained from the GIS). A laser range-sensor is used to detect the artificial landmarks located in the surroundings of the vehicle. The vehicle's pose is calculated by triangulation thanks to the range-bearing data associated to the observed landmarks and their GIS coordinates. The fusion of odometric with landmark-based localization results is also made by means of an EKF. The reader is referred to [START_REF] Pradalier | Simultaneous localization and mapping using the geometric projection filter and correspondence graph matching[END_REF] for more details.

C. Motion Planning

The Motion Planning module is the key component of the solution proposed for motion autonomy in dynamic environments. Its purpose is to compute the trajectory that is to be executed by the vehicle in order to reach its goal. As mentioned in the section I, the Motion Planning module takes into account the two constraints imposed by dynamic environments, namely the real-time and safety constraints. It is achieved thanks to the two concept of Partial Motion Planning (PMP) [START_REF] Benenson | Toward urban driverless vehicles[END_REF] and Inevitable Collision States (ICS) [START_REF] Fraichard | Inevitable collision states -a step towards safer robots?[END_REF] Let A denote the Cycab vehicle. A state of A is defined as a 5-tuple (x, y, θ, v, ξ) where (x, y) are the coordinates of the middle point R of the rear axle, θ is the main orientation of A, v is the linear velocity of the rear wheel, and ξ is the orientation of the front wheels (Fig. 5). A control of A is defined by the couple (α, γ) where α is the rear wheel linear acceleration. and γ the steering velocity. The motion of A is governed by the following motion equation:

      ẋ ẏ θ v ξ      =       v cos θ v sin θ tan ξv L 0 0       +       0 0 0 1 0       α +       0 0 0 0 1       γ (1)
with α ∈ [α min , α max ] (acceleration bounds), γ ∈ [γ min , γ max ] (steering velocity bounds), and |ξ| ≤ ξ max (steering angle bounds). L is the wheelbase of A.

2) Partial Motion Planning:

t t i t i+1 (1)
(2)

(3) When placed in a dynamic environment, a vehicle cannot stand still since it might be collided by one of the moving objects. In a situation like this, a real-time constraint is imposed to the vehicle: it has a limited time only to determine its future course of action. The time available is a function of what is called the dynamicity of the environment which is directly related to the dynamics of both the moving objects and the robotic system.

PMP(i) PMP(i + 1) Π(i) Π(i + 1) . . . . . .
As mentioned earlier, Partial Motion Planning (PMP) is a planning scheme that takes into account the real-time constraint explicitly: when the time available is over, PMP is interrupted and it returns a partial motion, ie a motion that may not necessarily reach the goal. Of course, since only a partial motion is computed, it is necessary to iterate the partial motion planning process until the goal is reached. The iterative nature of PMP is doubly required since the model of the future is based upon predictions whose validity duration is limited in most cases. An iterative planning scheme permits to take into account the unexpected changes of the environment by updating the predictions at a given frequency (which is also determined by the environment dynamicity). Fig. 6 depicts the PMP iterative cycle. Let us focus on the planning iteration starting at time ti, it comprises three steps:

(1) An updated model of the future is acquired (provided by the World Modelling module). (2) The state-time space of A is searched using an incremental exploration method that builds a tree rooted at the state s(t i+1 ) with t i+1 = t i + δ p where δ p is the planning time available.

(3) At time t i+1 , the current cycle is over, the best partial trajectory Π(i) of the tree is selected according to a given criterion (safety, length, etc.). It is discretized and placed into the DDX store. PMP cycles until the last state of the planned trajectory reaches a neighbourhood of the goal state. An incremental search method is used to explore the state-space. It is based upon the Rapidly-Exploring Random Tree (RRT) technique [START_REF] Lavalle | Planning Algorithms[END_REF] that incrementally expands a tree rooted at the start state. This method being incremental in nature, it can interrupted at any time. Classically, RRT computes collision-free trajectories. In the approach proposed, the usual geometric collision-checker is replaced by an Inevitable Collision State-checker [START_REF] Parthasarathi | An inevitable collision statechecker for a car-like vehicle[END_REF] that ensures that A will never end up in a situation eventually yielding a collision later in the future.

D. Motion Tracking

Motion tracking control deals with the execution of the planned trajectory. The Motion Tracking module is essentially a feedback controller that seeks to minimize the error between the current state of the vehicle and the desired state. Both states are obtained from the DDX store, they are respectively computed by the Localization and the Motion Planning modules.

For tracking purposes, a motion model simpler than ( 1) is used instead. A state is now defined as a 3-tuple (x, y, θ). and a control by the couple (v, ξ). The motion of A is thus governed by the following motion equation:

   ẋ = v cos (θ) ẏ = v sin (θ) θ = v tan ξ L (2)
The tracking problem is considered as tracking a moving reference frame which is moving along a given trajectory. The trajectory tracking error e = (e x , e y ) is the difference between the current position and the desired position of the robot. The error in the orientation between the current and the reference frames is e θ . A linearized 5th-order dynamic model is used for the controller design [START_REF] Rives | Vision-based control for car platooning using homography decomposition[END_REF]. This model is decoupled into a longitudinal model and a lateral model. Let (v * , ξ * ) denote the velocity and steering angle of the reference frame, the expected velocity v c and steering angle ξ c are obtained as:

v c = v * -k v e x v -v * ; ξ c = ξ * -k ξ   e y e θ ξ -ξ *   (3)
where k v = (k v1 , k v2 ) and k ξ = (k ξ1 , k ξ2 , k ξ3 ). The k vi (i = 1, 2) and k ξj (j = 1, 2, 3) are positive scalar gains (they will determine the tracking performance).

VI. EXPERIMENTS

The different modules of the navigation architecture are implemented in C++ under Linux. The DDX framework allows the different navigation functionalities/modules to be distributed over different computers. when the real Cycab is used, its embedded core software communicates with the rest of the application through wireless Ethernet. Experiments on autonomous navigation has been carried out in simulation. So far, only the localization and tracking modules have been tested on the real Cycab. Autonomous navigation experiments with the real Cycab are underway.

A. Simulation Results

As mentioned earlier, PMP plays an key role for safe navigation in dynamic environments. Simulations for two different scenarios are first studied to test the real-time planning performance of PMP.

1) Test Environment: The first experiment is done in a dynamic two-dimensional environment (size 60×30m), featuring two static rectangular objects and two moving disk objects (Fig. 7(a)). The start and the goal pose of the Cycab are (5, 15, 0) and (50, 5, 0) respectively. The moving objects are programmed to move with a constant velocity (moving upwards). Fig. 7(b) shows the setup of this experiment and the output of the motion planning process. The safe motion planned for the Cycab is the red line passing the two rectangular objects. In comparison, the green line passing below the two rectangular objects is the trajectory obtained when the moving objects are not present. Figs 7(c) and 7(d) depicts the velocity and steering angle profile along both trajectories. The difference between the two trajectories is clearly due to the presence of the moving objects. Notice how the vehicle modify its course (Fig. 7(d)) and slows down twice in order to give way to the moving objects (Fig. 7(c)).

2) Parking Lot of Inria Rhône-Alpes :

The second experiment is done in a two-dimensional model of the parking lot of Inria Rhône-Alpes (Fig. 8(a)). This environment is cluttered with twenty-six fixed objects and two pedestrians. From the motion planning point of view, this environment imposes more collision-avoidance constraints than the first scenario. The starting pose and the goal pose of the Cycab is (5, 7, 0) and (43, 7, 0.1) respectively. The pedestrians move upwards on the roadway. Fig. 8(b) shows the setup of this experiment and the output of the motion planning process. It also features the trajectory obtained when the moving objects are not present. Figs 8(c) and 8(d) depicts the velocity and steering angle profile along both trajectories. In this scenario, because of the extra constraint imposed by the fixed objects,, the two trajectories are geometrically close (there is little room for manoeuvring). Most of the differences occur in the velocity profile. Preliminary experiments with the real Cycab vehicle have been done in the parking lot of Inria Rhône-Alpes in order to evaluate the performance of the Motion Tracking module. As per (3), five parameters (k v1 , k v2 , k ξ1 , k ξ2 , k ξ3 ) are used to obtain the desired control velocity and steering angle for accurate trajectory tracking. Although this designed controller algorithm shows that the control system is theoretically stable for any combination of parameter values of , an optimal parameter set needs to be chosen for the stable and accurate execution of the desired trajectories in realtime environment. The chosen parameter values are: k v1 = 0.1; k v2 = 0.1; k ξ1 = 0.2; k ξ2 = 0.2; k ξ3 = 0.1.

B. Real Experiments

A U-shaped trajectory was precomputed and placed in the DDX store to be used as a reference trajectory for the Motion Tracking module. The localization module was operational (including the landmark-based positioning) and used to determine the position of Cycab in the parking lot. Fig. 9(a) shows the desired trajectory and executed trajectory with this parameter set. It can be seen that the designed controller has desired performance for executing the planned trajectories. To ensure smooth driving, a first-order low-pass filter is applied to the velocity commands that are sent to the low-level vehicle control module. Fig. 9(c) shows the effects of the filter on the velocity commands (a close-up of the velocity profile is shown in Fig. 9(b).

VII. CONCLUSIONS AND FUTURE WORKS

This paper has presented a novel navigation architecture for automated car-like vehicles in urban environments. Experimental results carried out on a simulation platform in a parking environment has demonstrated the ability to navigate safely in dynamic environments. Preliminary results with a real vehicle were also presented. Future works will include further experiments with a real vehicle.

Fig. 2 .

 2 Fig. 2. View of the parking lot (left) and the corresponding map (right).

Fig. 3 .

 3 Fig. 3. Detecting and tracking moving objects using an off-board video camera (left) and an on-board laser range sensor (right).

Fig. 4 .

 4 Fig. 4. Predicting the future motion of a moving object in a parking lot.

Fig. 5 .

 5 Fig. 5. The Cycab vehicle and its kinematics.

Fig. 6 .

 6 Fig. 6. Partial Motion Planning iterative cycle.

Fig. 7 .

 7 Fig. 7. Experiment in a test environment.

Fig. 8 .

 8 Fig. 8. Experiment in the parking lot of Inria Rhône-Alpes.

Fig. 9 .

 9 Fig. 9. Tracking of a U-shaped trajectory.


Morten Mossige
email: morten.mossige@no.abb.com

Arnaud Gotlieb
email: arnaud@simula.no

Hein Meling
email: hein.meling@uis.no

Testing Robotized Paint System using Constraint Programming: An Industrial Case Study

Advanced industrial robots are composed of several independent control systems. Particularly, robots that perform process-intensive tasks such as painting, gluing, and sealing have dedicated process control systems that are more or less loosely coupled with the motion control system. Validating software for such robotic systems is challenging. A major reason for this is that testing the software for such systems requires access to physical systems to test many of their characteristics. In this paper, we present a method, developed at ABB Robotics in collaboration with SIMULA, for automated testing of such process control systems. Our approach draws on previous work from continuous integration and the use of well-established constraint-based testing and optimization techniques. We present a constraint-based model for automatically generating test sequences where we both generate and execute the tests as part of a continuous integration process. We also present results from a pilot installation at ABB Robotic where ABB's Integrated Process Control system has been tested. The results show that the model is both able to discover completely new errors and to detect old reintroduced errors. From this experience, we report on lessons learned from implementing an automatic test generation and execution process for a distributed control system for industrial robots.

Introduction

Developing reliable software for Complex Industrial Robots (CIRs) is a complex task, because typical robots are comprised of numerous components, including computers, field-programmable gate arrays (FPGAs), and sensor devices. These components typically interact through a range of different interconnection technologies, e.g. Ethernet and dual port RAM, depending on delay and latency requirements on their communication. As the complexity of robot control systems continuous to grow, developing and validating software for CIRs is becoming increasingly difficult. For robots performing process-intensive tasks such as painting, gluing, or sealing, the problem is even worse as their dedicated process control systems is loosely coupled with the robot motion control system. A key feature of robotized painting is the ability to perform precise activation of the process equipment along a robot's programmed path. At ABB Robotics, Norway, they develop and validate Integrated Painting control Systems (IPS) for CIRs and are constantly improving the processes to deliver products that are more reliable to their customers.

Current practices for validating the IPS software involve designing and executing manual test scenarios. In order to reduce the testing costs and to improve quality assurance, there is a growing trend to automate the generation of test scenarios and multiplying them in the context of continuous testing. To facilitate this automation, we abandon the use of physical robots and instead run our tests on the IPS controllers with outputs connected to actuators. We monitor these outputs and compare with the expected results for the different tests.

In this paper, we report on our work using Constraint Programming (CP) over finite domains to generate automatically timed-event sequences (i.e., test scenarios) for the IPS and execute them within a Continuous Integration (CI) process [START_REF] Fowler | Continuous integration[END_REF]. Building on initial ideas sketched in a poster [START_REF] Mossige | Poster: Test generation for robotized paint systems using constraint programming in a continuous integration environment[END_REF] one year ago, we have developed a constrained optimization model in SICStus Prolog clpfd [START_REF] Carlsson | An open-ended finite domain constraint solver[END_REF] to help test the IPS under operational conditions. Due to online configurability of the IPS, test scenarios must be reproduced every day, meaning that indispensable trade-offs between optimality and efficiency must be found, to increase the capabilities of the CI process to reveal software defects as early as possible. While using CP to generate model-based test scenarios is not a completely new idea [START_REF] Di Alesio | Stress testing of task deadlines: A constraint programming approach[END_REF][START_REF] Balck | Model-based protocol log generation for testing a telecommunication test harness using clp[END_REF], it is to our knowledge, the first time that a CP model and its solving process been integrated into a CI environment for testing complex distributed systems. Organization. The rest of the paper is organized as follows: Section 2 presents some background on robotized painting, with an example serving as a basis for describing the mathematical relations involved ; Section 3 describes ABB Robotics' current testing practices of the IPS and the rationale behind our validation choices ; Section 4 presents test objectives and scenarios ; Section 5 explains how the model is implemented and how it is integrated in in the CI process ; Section 6 discuss the errors found using the new model and compare our new approach with existing testing methods. Finally, Section 7 present the lessons learned from using the new testing approach and outlines ideas for further work, before we conclude the paper. Notation. Throughout this paper the following notations is used: A symbol prefixed with a * , as in * SeqLen, is to be regarded as a constant integer value given as input to the CP-model. An underlined symbol, as D + , is to be regarded as an integer generated by the CP-model, i.e. a result of the solving process.

Robotized Painting

This section briefly introduces robotized painting. A robot system dedicated to painting typically consists of two main parts: the robot controller, responsible for moving the mechanical arm, and the IPS, responsible for controlling the paint process. That is, to control the activation and deactivation of several physical processes such as paint pumps, air flows, air pressures, and to synchronize these with the motion of the robot arm.

A spray pattern is defined as the combination of the different physical processes. Typically, the physical processes involved in a spray pattern will have different response times. For instance, a pump may have a response time in the range 40-50 ms, while the airflow response time is in the range 100-150 ms. The IPS can adjust for these differences using sophisticated algorithms that have been analyzed and tuned over the years to serve different needs. In this paper, we focus on validating the timing aspects of the IPS.

Example of Robotized Painting

We now give a concrete example of how a robot controller communicates with the IPS in order to generate a spray pattern along the robot's path. A schematic overview of the example is shown in Figure 1, where the node marked robot controller is the CPU interpreting a user program and controlling the servo motors of the robot in order to move it. The example is realistic, but simplified, in order to keep the explanations as simple as possible.

Robot Controller

IPS master P reT ime P ostT ime

C2 D + 2 ,D - 2 ,K2 C1 D + 1 ,D - 1 ,K1 C3 D + 3 ,D - 3 ,K3
MoveL p1; SetBrush 1 \x := 200; SetBrush 2 \x := 300; PaintL p2, v800;

User program L1,1 L1,2 L1,3 L2,1 L2,2 L2,3 L3,1 L3,2 L3,3 L = (Bi, ti) ( L B ,1 , ti ,1 ) (LB,2, ti,2) ( L B ,3 , t i, 3 )

Lookup(Bi)

(LB,1, LB,2, LB,3) LB,1@to,1 LB,2@to,2 LB,3@to,3

Fig. 1: Logical overview of a robot controller and the IPS.

The program listing of Figure 1 shows an example of a user program. The first instruction MoveL p1 moves the robot to the Cartesian point p1. The next two SetBrush instructions tells the robot to apply spray pattern number 1 when the robot reaches x = 200 on the x-plane, and to apply spray pattern number 2 when it reaches x = 300. Both SetBrush instructions tell the IPS to apply a specific behavior when the physical robot arm is at a given position. The last instruction (PaintL) starts the movement of the robot from the current position p1 to p2. The v800 argument of PaintL gives the speed of the movement (i.e., 800 mm/s).

We now assume that the path from p1 to p2 results in a movement from x = 0 to x = 500. The robot controller interprets the user program ahead of the actual physical movement of the robot, and can therefore estimate when the robot will be at a specific position. Assuming that the movement starts at time t = 0, the robot can compute based on speed and length of path that the two SetBrush activations should be triggered at t 1 = 250 ms and t 2 = 375 ms.

The robot controller now sends the following messages (a.k.a. events) to the IPS master: (B 1 = 1, t 1 = 250), (B 2 = 2, t 2 = 375), which means apply spray pattern 1 at 250 ms, and spray pattern 2 at 375 ms. The messages are sent around 200 ms before the actual activation time, or at ≈ 50 ms for spray pattern 1, and at ≈ 175 ms for spray pattern 2. These messages simply converts position into an absolute global activation time. Note also that the IPS receives the second message before the first spray pattern is bound for execution, which means that the IPS must handle a queue of scheduled spray patterns.

IPS master: When the IPS receives a message from the robot controller, it first determines the physical outputs associated with the logical spray pattern number. Many different spray patterns can be generated based on factors like paint type or equipment in use. In the IPS, each spray pattern is translated into 3 to 6 different physical actuator outputs that must be activated at appropriate times, possibly different from each other. In this example, we use three different physical actuator outputs.

Figure 1 shows the three different actuator outputs (C1, C2, C3). The output value of each actuator output for a given spray pattern is resolved by using a brush table (L) (simply a lookup table). In this example, L(B 1 = 1) returns (L 1,1 , L 1,2 , L 1,3 ), while L(B 2 = 2) results in (L 2,1 , L 2,2 , L 2,3 ). The IPS master will now pass these values to each actuator output along with its activation time, which may be different from the original time received from the robot controller (t i ). This possible modification can be formalized as follows:

t i = t i -P reT ime if L 1,Bi-1 = 0 ∧ L 1,Bi = 0 t i -P ostT ime if L 1,Bi-1 = 0 ∧ L 1,Bi = 0 (1)
What equation [START_REF] Fowler | Continuous integration[END_REF] shows is that the activation time of each actuator output may be adjusted by a constant factor (P reT ime, P ostT ime), depending on changes from other actuator outputs. This is done because small adjustments may be necessary when there is a direct link between the timing of different actuator outputs. In our example, the timing on C2 is influenced by changes on C1.

A practical example of such compensation is to change the timing on an air actuator output when a paint-pump is turned on or off. Activation of actuator outputs: By still referring to Figure 1, we now present how a message sent from the IPS master to a single actuator output is handled. Let us assume that message (L, t i ) is sent, and that the current actuator output is L . Since painting involves many slow physical processes, the actuator output compensates for this by computing an adjusted activation time t o , that accounts for the time it takes the physical process to apply the change.

The IPS can adopt two different strategies to compute this time compensation. The first consists of adjusting the time with a constant factor: D + for positive change, and D -for negative change. The second one consists in using a linear timing function to adjust the time linear to the change of the physical output.

Equation ( 2) combines these strategies into a single compensation function, where * M in (resp. * M ax) is the physical minimum (resp. maximum) value possibly handled4 by some actuator output.

t o = t i -      D -• ( L-L * M ax- * M in ) K if L < L D + • ( L -L * M ax- * M in ) K if L > L 0 otherwise (2)
Physical layout of the IPS: Figure 1 only shows the logical connections in a possible IPS configuration. In real applications, each component (IPS master, C1, C2, C3) may be located on different embedded controllers, interconnected through an industrial-grade network. As such, the different components may be located at different physical locations on the robot, depending on which of physical process it is responsible for.

Testing IPS

In this section, we summarize some of the testing approaches that have been used to test the IPS, focusing on validating the accuracy of time-based activation. We discuss the benefits and drawbacks of these legacy-testing approaches, before we introduce our automated testing approach.

A major challenge that we are confronted with, when testing a robot system, is that it involves a physically moving part (the robot arm), which must be accurately synchronized with several external process systems. This quickly turns into labor-intensive procedures to set up the tests and execute them. Moreover, strict regulations with regard to safety must also be followed due to moving machinery and use of hazardous fluids like paint.

Painting on Paper

To simulate a realistic application of spray painting with a robot, we can configure a paint system to spray paint on a piece of paper. An example of this is shown in Figure 2 5 . This test includes both realistic movement of the robot while running a complete and realistic setup on the IPS. However, there are many drawbacks to using this method, where one is high cost of much manual labor to set up, and hazardous environment due paint fluid exposure. It is also more or less impossible to automate this test, even after the initial setup is done.

A typical test execution will be to perform a single paint-stroke as shown in Figure 2, followed by manual inspection of the result. This inspection will typically require both a software engineer and a paint process engineer to interpret the results. Because of this manual inspection that need to be done between each paint-stroke, the possibility of automating this test method is limited. Such a test is typically performed during the final verification phase for a new product running the IPS software, such as the air controller of a paint controller. The test is also executed as part of major revisions of the IPS. Based on our experience at ABB Robotics, it is extremely rare that errors related to timing are found when running such a test.

Spraypattern 1

Spraypattern 2

Fig. 2: Painting on paper.

Activation Testing with an Oscilloscope

By reducing the IPS setup to include only a single digital actuator output, without any fluid or air, it is possible to perform some of the basic synchronization tests on the IPS. This can be done by connecting the digital output to an input channel on an oscilloscope, and the output from a proximity sensor to another input channel. The robot is then programmed to perform a linear movement passing over a proximity sensor, with the paint program set up to do an activation at exactly that point. Thus generating a signal which should be in sync with the signal from the proximity sensor. By comparing the signal from the digital output with the signal from proximity sensor, it is possible to test much of the timing behaviors of the IPS 6 .

At ABB Robotics, this is one of the most frequently executed tests aimed at uncovering synchronization problems. However, also this test require manual labor to set up and to execute the test runs, and since it also involves physical movement of the robot arm, a hazard zone must be established for this test. However, different from the test described in Section 3.1, it can be executed without supervision, and the test results can be inspected after test completion.

Running in a Simulated Environment

The IPS is designed to be portable to many microprocessor platforms and operating systems. It is even possible to run the IPS on a desktop system such as Windows. This has the advantage that much of the functional testing can be performed in a simulated environment. This has reduced some of the need for time consuming manual testing on actual hardware. However, testing against performance requirements is impossible in a simulated environment, due to lack of real-time behavior in the simulator.

Summary of Existing Test Methods

There are several drawbacks with the test methods described above. The methods that use real robots gives very realistic results, but require costly and slow manual labor to set up the test, and to interpret the results. For the method described in Section 3.3 it is clearly possible to automate both setup and result analysis. However, it cannot be used to execute tests related to real-time and synchronization between several embedded controllers.

A New Test Strategy

In the following, we outline some of the requirements for our new test strategy. The rationale behind the new requirements are mainly to reduce manual labor, and to be able to detect errors earlier in the development process: 1) Automated: It should be possible to set up the test, execute the test, and analyze the results without human intervention. 2) Systematic: Tests should be generated automatically by a model, rather than being contrived by a test engineer. 3) Adaptive: Generated tests should automatically adapt to changes in the software and/or configurations, and should not require any manual updates to the testing framework. This implies that tests should be generated immediately prior to their execution, using as input, information obtained from the system under test.

Constraints and Scenario

With the mathematical relations described in Section 2 as background, we now describe the constraints used to generate test sequences. The constraints can be divided into two main categories. The first category expresses how a complete IPS behaves in a normal situation. That is, the IPS is not forced into any erroneous state, or other corner cases. The second category represents constraints where the model generates specially selected error scenarios, where the IPS is either pushed into an erroneous state, or where performance limitations are being tested. These constraints are summarized in Figure 3, and discussed in detail in the following sections.

Normal Scenario

During normal, non-erroneous behavior, the robot controller sends commands to the IPS according to the constraint given in (3), and the IPS generates output activations according to (4). These two constraints correspond to Figure 3a.

Input sequence: ∀i ∈ 1 . . . * SeqLen, (3)
t i -t i-1 ≥ * M inBrushSep, t i > t i-1 , t i ≥ 0, B i = B i-1 , B i ∈ 0 . . . * BT abSize
Each single actuator output:

∀j ∈ 1 . . . * C, ∀i ∈ 1 . . . * SeqLen (4)
t j,i -t j,i-1 ≥ * M inT rigSep, t j,i > t j,i-1 , t j,i ≥ 0

Where * C refers to the number of actuator output in the setup.

The Overlap Scenario

Figure 3b shows two overlapping event activations. This overlap can be generated using the constraint in [START_REF] Balck | Model-based protocol log generation for testing a telecommunication test harness using clp[END_REF]. This scenario is used to test how well the IPS is able to handle that an activation time for one actuator output gets out of order with respect to time. For real robot applications, there are many possible sources for this particular problem scenario. The most common one being that a user increase the robot's speed by changing the speed parameter in a PaintL instruction. For the IPS, this behavior should be reported as an error message to the user, and resolve any conflicts with the actuator output.

t c,e -t c,e+1 ≥ * M inOverlapT ime, t c,e+1 -t c,e-1 ≥ * M inT rigSep, (5)
t c,e+2 -t c,e ≥ * M inOverlapT ime Above, t c,e represents the activation time for a specific actuator output c and e indicates where in the sequence the overlap should be enforced.

The Illegal Value Scenario

The illegal value constraint is important for checking that the IPS is able to shut down safely in case of an error. By forcing one of the output channels to fail, the internal structure of the IPS should initiate a controlled shutdown. This shutdown procedure must be performed in a special sequence, taking care to avoid pressure build up in hoses, which could otherwise lead to rapturing hoses. This constraint is visualized in Figure 3c, and specified in Equation [START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF].

P c,e = * IllegalV al (6)
Where P c,e is the output value of actuator output c for the e th event.

Implementation

This section explains how the model is implemented and used in ABB's production grade test facility. We will also discuss some of the design choices that we made during the deployment of the model.

Continuous Integration

CI [START_REF] Fowler | Continuous integration[END_REF] is a software engineering practice aimed at uncovering software errors at an early stage of development, to avoid problems during integration testing. One of the key ideas in CI is to build, integrate, and test the software frequently.

For developers working in a CI environment, this means that even small source code changes should be submitted to the source-control system server frequently, rather than submitting large sets of changes occasionally. Typically, a CI infrastructure includes tools for source control system, automated build servers, and testing engines.

Testing in a CI Environment

Our goal in this work has been to develop an automated testing framework for the IPS as an integrated part of a CI environment. Compared to traditional software testing, a test running in a CI environment will have some additional requirements. In particular, Fowler [START_REF] Fowler | Continuous integration[END_REF] points out that the total round-trip time is crucial for a successful CI deployment. Here, round-trip time refers to the time it takes from a developer submits a change to the source repository, until feedback from the build and test processes can be collected. Thus, to keep the round-trip time to a minimum, we have identified a few areas that we have given special attention to in our design.

Test complexity: Testing based on CI will never replace all other kinds of testing. In CI, a less accurate but faster test will always be preferred over a slow but accurate test. In practice, a test must satisfy the good enough criteria, frequently used in industry.

Solving time: Many constraint-based optimization problems are time consuming to solve, especially if an optimal solution is sought. For our purposes, an optimal solution is unnecessary. Simply finding a good solution after running the solver for a limited period is considered good enough for our purpose.

Execution time: The most important factor for controlling the execution time for a generated test sequence is to control the length of the test sequence. By balancing the length of the test sequence between a reasonable, realistic enough but still small enough, the execution time of the test is kept under control. Clearly, it will require some experience, to determine what is good enough.

Model Implementation

We choose to use Constraint Programming (CP) over finite domains to solve the model. CP is a well-known paradigm introduced twenty years ago to solve combinatorial problems in an efficient and flexible way [START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF]. Typically, a CP model is composed of a set of variables V , a set of domains D, and a set of constraints C. The goal of constraint resolution is to find a solution, i.e., an assignment of variables to values that belong to the domains and that satisfy all the constraints. Finding solutions is the role of the underlying constraint solver, which applies several filtering techniques to prune the search space formed by all the possible combinations. In practice, the constraint models that are developed to solve concrete and realistic testing problems usually contain complex control conditions (conditionals, disjunctions, recursions) and integrate dedicated and optimized search procedures [START_REF] Gotlieb | TCAS Software Verification using Constraint Programming[END_REF].

We have chosen to implement the constraint model using the finite domains library in Sicstus Prolog [START_REF] Carlsson | An open-ended finite domain constraint solver[END_REF], and have thus written the actual model in Prolog. To integrate the model with ABB's existing testing framework, we have also built a front-end layer in Python. This front-end layer can be used by test engineers with no prior knowledge of CP or Prolog, and allows us to integrate with our existing build and test servers based on Microsoft Team Foundation Server. A schematic overview of the architecture is shown in Figure 4.

While referring to Figure 1, we now assume that the number of actuator outputs is a constant input parameter * C, instead of 3. The variables for our problem can be divided into three groups: the input sequence ((B 1 , t 1 ), . . . , (B N , t N )), where N = * SeqLen (the length of the test sequence). The configuration variables: (P reT ime, P ostT ime, D + 1 , D - 1 , K 1 , . . . , D + * C , D - * C , K * C ), and the variables in the brush table (L 1,1 , . . . , L * BT abSize, * C ) where * BT abSize is the size of the brush table. By selecting one of the previously mentioned scenarios, a solution to the CP model is constructed by an instantiation of these variables. Thus, the expected output on each actuator output along with its activation time, represents the test oracle.

Test Setup

An overview of our test setup is shown in Figure 4. With reference to the numbers in Figure 4 a test sequence execution is typically triggered by a build server upon a successful build of the IPS software, [START_REF] Fowler | Continuous integration[END_REF]. Building the software is scheduled to run every night, but can also be triggered manually by a developer. The first task the test server does is to upgrade all connected embedded controllers with the newly built software, [START_REF] Mossige | Poster: Test generation for robotized paint systems using constraint programming in a continuous integration environment[END_REF]. Then the IPS is configured with test specifications retrieved from the source control repository, (3). This is followed by executing a set of basic smoke tests, before the constraint model is launched for test cases generation. By feeding the constraint model with data retrieved from the new configuration and properties from the IPS (4), we ensure that the generated tests are synchronized with the current software and configuration. Further details on just-in-time test generation (JITTG) is discussed in Section 5.5. Finally, the actual test is executed by applying the generated test sequence, and comparing the actuator outputs with the model generated oracle, [START_REF] Balck | Model-based protocol log generation for testing a telecommunication test harness using clp[END_REF].

In the production test facility at ABB, each generated test sequence is executed on a total of 11 different configurations. The different configurations include execution on different hardware and software generations of the IPS, and execution on both VxWorks and Linux as the base operating system for the IPS. The test framework is written in Python and supports parallel execution of tests when there are no shared resources. Thus, the time to run the test sequence on many different configuration is very low, compared to running them in a sequence, one at a time.

Just-in-Time Test Generation

As shown earlier in this paper, there are many parameters in the model that must be specified before the model can be solved. Some of these parameters come from configuration files used to configure the IPS, and some of the parameters can be extracted by querying a newly built IPS. Common for both sets of parameters is that the resulting model will be different if the parameters have changed. This means that the model is closely linked to what is fetched from the source control system. Because of this, we decided to generate and solve the model at testing time, as opposite to solving the model once, and adding the resulting model to source control. There are several advantages to using JITTG, but there are also some drawbacks. The most important advantage of using JITTG is that there is a lower probability of falsely reporting an error due to mismatch between the generated model and the running system. The main drawback is that the time needed for solving the model becomes an important factor. If the model is solved once and used many times, a solving time of several hours is reasonable. However, with JITTG the solving time becomes a crucial. The models that we have solved so far have had a solving time of less than a few minutes.

Evaluation

This section presents the errors that were found after having used the new model in ABB Robotics production test facility for about four months. We also compare our new model-based testing approach with some of the other testing practices.

New Errors Found

This section describes the errors found immediately after we introduced the new model. We found three previously unknown errors in the IPS. These errors have been in the IPS for some time, and were only found through the use of the new model. Two of the errors was directly related to the behavior of the IPS, while the third was related to how a PC tool present online diagnostics from a live, running system. It is important to emphasize that tests executed in a CI framework is primarily designed to detect errors caused by source code changes committed to the source control repository. Consequently, when a test framework like this is first introduced, it will not necessarily find many new errors in a mature, well-designed system. During normal operation, the test framework should only rarely find any errors. PreTime/PostTime Calculation Error: If an actuator output was assigned a value 0, while at the same time another actuator output was set up to slave the timing of the first actuator output, using the logic specified in Equation [START_REF] Fowler | Continuous integration[END_REF], this could lead to an erroneous calculation of the timing of the slaved actuator output. This error was found by running the normal behavior scenario as described in Section 4.1. Event Queuing Blocks Shutdown: If a shutdown of the IPS occurred at the same time as a queue of actuator output events was scheduled for execution, the shutdown could be delayed. This could happen because the shutdown message was treated with the same priority as a normal output message, when placed in the scheduling queue. Shift in Clock: There exist several online monitoring tools like RobView and Robot Studio. These tools can be used for online monitoring of the process data from the IPS. To be able to present very accurate timing on the presented signals, the clock on the PC running the tool, and the clock on the IPS is synchronized through a proprietary light weight version of the IEEE 1588 clock synchronization protocol. Our test framework found an error in this synchronization protocol, which could cause the reported time of a signal change to deviate by as much as 10 ms compared to the actual time of the change. The error could even cause changes in the causal ordering of events.

Detection of Old Errors

To further validate the robustness of the model, a collection of old, previously detected errors were reintroduced into source control repository with the intention to verify that the model was able to detect the errors. The selected errors were chosen by searching in ABB's bug tracking system, by interviewing ABB's test engineers, and through discussions with the main architect of the IPS. Most of the errors were originally discovered at customer sites during staging of a production line, or after the production line was set into production. The chosen errors are mainly related to timing errors of painting events, and several of the errors can be classified as errors that appear when the IPS is put into a large configuration with many components. The chosen errors are summarized in Table 1. The table shows historical data on how long it original took to detect the error, how long it took to fix the error, and how long it took to validate that the error had in fact been fixed. Finally, the table shows if our new model was able to detect the re-injected bug. Note that some of these numbers cannot be accurately specified; they represent reasonable estimates. Especially errors related to how long a bug has been in the system is difficult to estimate. However, by interviewing the main architect of the IPS and the lead test engineer, we feel that the numbers presented has high confidence.

Comparison of Test Methods

While our new model-based test strategy cannot entirely replace the current testing methods, it represents an excellent supplement to identify bugs at a much earlier stage in the development process. Nonetheless, we can still compare the different methods quantitatively. Table 2 gives the results of our comparison. As we can see from this table, our new test strategy gives a huge improvement in number of activations that can be tested within a reasonable timeframe, which is not possible with existing testing methods. If we also include the automation in all aspects of testing, our strategy performs much better than our current test methods. However, it is important to note that our new method does not involve a mechanical robot, and this must be regarded as a weakness. 1 Time to upgrade software, configure IPS, and loading test. 2 The number of physical outputs that are verified with respect to time in one test.

3 Time needed to repeat two identical tests. 4 Time needed to inspect and interpret the result. 5 Manual task performed by a test engineer. 6 Automated task performed by a computer.

Conclusion

This section concludes the paper by presenting some lessons learned from our experience at ABB Robotics of introducing CP in our CI process. We also outline some ideas for further work.

Lessons Learned

Based on experience from about one year of live production in ABB Robotics software development environment, we report on lessons learned. The lessons learned presented here are based on experience gathered through development and deployment of the test framework, and on discussion with test engineers. We summarize lessons learned in the following: Higher confidence when changing critical parts: Based on feedback from developers, there are now less 'fear' of applying changes in critical parts of the code. Previously such changes involved significant planning efforts and had to be synchronized with test engineers responsible for executing tests. With the new testing framework in place, it is easy to apply a change, deploy a new build with the corresponding execution of tests and inspect the result. If the change has caused unwanted side effects, the change is rolled back to keep the build 'green'. Simple front-end, complex back-end: By using Python [START_REF] Rossum | Python reference manual[END_REF] as the front-end interface to the constraint solver and keeping the interface that a test engineer is exposed to as simple as possible, we are able to utilize personnel with minimal computer science background. It has been recognized by both [START_REF] Francis | Optimisation modelling for software developers[END_REF] and [START_REF] De La Banda | The future of optimization technology[END_REF] that CP has a high threshold for usage. By limiting the training to introduction of the famous classical problems like 'SEND+MORE=MONEY' and the N-Queens problem [START_REF] Marriott | Programming with constraints: an introduction[END_REF], the test engineers have received enough training to use the constraint solver from Python without major problems. Less focus on legacy, manual tests: A positive side effect of introducing model-based testing is that the focus in the organization has shifted from lots of manual testing towards more automatic testing. Even for products beyond the scope of this paper, the introduction of a fully automatic test suite has inspired other departments to focus more on automatic testing.

Putting everything in source control repository: In our work, we never perform any installation on any build server. After a build server is installed with its CI software, absolutely everything is extracted from the source control repository. This is also a clear recommendation in CI [START_REF] Fowler | Continuous integration[END_REF]. By being 100 % strict to this philosophy, it is possible to utilize big farms of build servers without any prior installation of special build tools. This is also the case for the new CP based tool presented in this paper. We consider that the effort taken to do a 100 % integration of the tools is quite demanding, but in the long run very efficient.

Keeping tests in sync with source code and hardware: The combination of adding 'everything' to the source control repository and JITTG is that we experience less problems with tests generating false errors due to a mismatch. We still have other test suites where we do not have this tight integration, and thus these tests may occasionally produce false errors.

Further work

The very promising results we got from use of the model inside the CI environment, has inspired us to also make use of the model outside the CI environment. This will enable us to use the model to generate tests where there is a focus on tests with longer duration. When using the model inside the CI environment, the focus is always on short duration tests, where each test never exceeds 3 minutes.

Conclusions

This paper introduced a new testing strategy for validating timing aspects of complex distributed control systems for robotics systems. A constraint-based mathematical model was introduced to automatically generate test cases through constraint solving and continuous integration techniques. The model, designed through a collaboration with SIMULA, has been implemented and a pilot installation has been set up at ABB Robotics. Using the model, both previously discovered bugs, as well as new bugs were found in a period that has been dramatically reduced with respect to other current testing practices.

Fig. 3 :

 3 Fig.3: Test scenarios considered as test objectives. The horizontal axis represent time, and the black dots correspond to output activations. A specific spray pattern is a collection of output activations, and is visualized by a line connecting the black dots.

Fig. 4 :

 4 Fig. 4: Integration of CP-model with physical setup.

Table 1 :

 1 Historical data on old bugs that were reintroduced. Time in system 2 Time to solve 3 Time to validate4 Detected by model

	Bug# 1 44432	5-10 years	1-2 hours	1 day	Yes
	44835	5-10 years	2-4 days	1 day	Yes
	27675	6-12 months	1-2 months	1-2 weeks	Yes
	28859	6-12 months	2-3 months	2-3 weeks	Yes
	28638	4-6 months	1-2 weeks	2-3 weeks	Yes

Table 2 :

 2 Comparison of test methods.

		Activation w/oscilloscope	Paint on paper	Constraint-based test
	Setup time 1	1-2 hours 5	3-4 hours 5	1-2 min 6
	Activations per test 2	1	5-10	>100
	Repetition time 3	5 sec	10 min	< 1 sec
	Interpretation time 4	< 1 min 5	2-4 min 5	< 1 sec 6
	Synch. with mechanical robot	Yes	Yes	No
	Run stand alone after initial setup	Yes	No	Yes

These values are determined by the physical equipment involved in the paint process (pumps, valves, air, etc.).

This video http://youtu.be/oq524vuO5N8 also shows painting on paper.

Two videos showing activation testing using a proximity sensor and oscilloscope: http://youtu.be/I1Ce37_SUwc and http://youtu.be/LgxXd_DN2Kg.

Refer to bug-number in ABB's bug tracking system.

How long the bug was present in the IPS before it was discovered.

How long it took from the bug was discovered until the bug was fixed.

How long it took to validate that the bug had actually been fixed. For many bugs, this involved testing time spent at customer facilities.

Acknowledgements This work is funded by the Norwegian Research Council under the frame of the Industrial PhD program, the Certus SFI grant and ABB Robotics.


Theophanis Tsandilas
email: theophanis.tsandilas@inria.frpierre.dragicevic@inria.fr

Pierre Dragicevic

Accounting for Chance Agreement in Gesture Elicitation Studies

Keywords: Gesture elicitation, agreement rate, agreement coefficient, chance agreement, kappa coefficients, confidence intervals ACM Classification H.5.m. Information Interfaces and Presentation (HCI)

The level of agreement among participants is a key aspect of gesture elicitation studies, and it is typically quantified by means of agreement rates (AR). We show that this measure is problematic, as it does not account for chance agreement. The problem of chance agreement has been extensively discussed in a range of scientific fields in the context of inter-rater reliability studies. We review chance-corrected agreement coefficients that are routinely used in inter-reliability studies and show how to apply them to gesture elicitation studies. We also discuss how to compute interval estimates for these coefficients and how to use them for statistical inference.

INTRODUCTION

Gesture elicitation is widely used in HCI as a method for designing better gesture-based interfaces by involving end users [START_REF] Wobbrock | User-defined gestures for surface computing[END_REF]. This method seeks to identify gesture vocabularies that are self-discoverable or easy to learn. Participants are typically shown the outcome of user interface actions or commands, and asked to propose gestures that would trigger these actions. The hope is that consistent gesture/command associations will emerge, but participants can also be very inconsistent in their proposals. Thus analyzing agreement between participants is a key aspect of the method [START_REF] Wobbrock | User-defined gestures for surface computing[END_REF][START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF]. Agreement can help assess whether the use of gestures is appropriate for a certain situation, can guide the design and evaluation of gesture vocabularies, and can help understand why some commands naturally map to gestures while others do not.

The most widely used index for quantifying agreement in gesture elicitation studies is Wobbrock et al's coefficient A [START_REF] Wobbrock | Maximizing the guessability of symbolic input[END_REF], recently superseded by Vatavu and Wobbrock's agreement rate AR [START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF]. The authors convincingly argue for the use of AR rather than A, derive a significance test for making comparisons between AR values, and suggest conventional ranges of values (low, medium, high) to help researchers interpret levels of agreement and compare them across studies.

However, it has long been recognized in other disciplines that AR is problematic because it does not account for chance agreement [START_REF] Cohen | A Coefficient of Agreement for Nominal Scales[END_REF][START_REF] Fleiss | Measuring nominal scale agreement among many raters[END_REF][START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. In this article we explain the issue of chance agreement and how it can affect AR. We review previous work on inter-rater reliability assessment, where these issues have been extensively studied. Several chance-corrected agreement coefficients have been proposed [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF] and are routinely used in a range of areas including psychometrics, medical research, computational linguistics, as well as in HCI for video and user log analysis [START_REF] Hailpern | A3: Hci coding guideline for research using video annotation to assess behavior of nonverbal subjects with computer-based intervention[END_REF]. We discuss how to use chance-corrected agreement coefficients in gesture elicitation studies, how to compute and interpret interval estimates, and conclude with pending challenges and limitations.

AGREEMENT MEASURES IN ELICITATION STUDIES

Wobbrock et al. [START_REF] Wobbrock | User-defined gestures for surface computing[END_REF] refer to presented commands as referents, and assume that all user-elicited gestures can be categorized into classes of equivalence they call signs. To quantify agreement for a given referent i, a great number of elicitation studies have used the formula initially proposed by Wobbrock et al. [START_REF] Wobbrock | Maximizing the guessability of symbolic input[END_REF] in their early 2005 paper on gesture elicitation:

A i = q k=1 n ik n i 2 (1)
where q is the total number of signs produced in the study, n ik is the number of participants who proposed sign k for the referent i, and n i is the total number of gestures proposed for the referent i. In the common situation where all participants are presented with all referents, n i is the number of participants in the study. To obtain the overall agreement A, Wobbrock et al. [START_REF] Wobbrock | Maximizing the guessability of symbolic input[END_REF] then average A i across all referents.

Later on, Vatavu and Wobbrock refine this index of agreement A i and propose to replace it with a slightly different index AR i they call the agreement rate, defined as follows:

AR i = q k=1 n ik (n ik -1) n i (n i -1) (2)
Vatavu and Wobbrock point out that in contrast to the A i index, AR i takes values in the entire interval [0..1] and has a clear interpretation whereby AR i is the proportion of participant pairs who are in agreement. It can be further observed that AR i reduces to A i for large samples. Both AR i and its approximation A i have been used in a range of disciplines as an index of homogeneity for nominal data, and are most commonly referred to as the Simpson's index [START_REF] Lieberson | Measuring population diversity[END_REF][START_REF] Ellerman | History of the logical entropy formula[END_REF]. As before, Vatavu and Wobbrock average AR i across all referents to obtain an overall agreement rate AR. This index also has a long history in science, and is commonly referred to as the percent agreement [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. However, it is also widely known to be problematic [START_REF] Fleiss | Measuring nominal scale agreement among many raters[END_REF][START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF], as we will now illustrate.

R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 total A 0 1 0 1 1 1 0 0 0 1 5 B

THE PROBLEM OF CHANCE AGREEMENT

Suppose a researcher is interested in a new ten-inch tablet that can sense user grasps, and wants to see if previously proposed techniques [START_REF] Wagner | Bitouch and bipad: Designing bimanual interaction for hand-held tablets[END_REF] can be improved through gesture elicitation. She recruits 20 participants to whom she shows 10 different document navigation operations in the form of animations on the tablet, and asks them to choose among five different grasps [START_REF] Wagner | Bitouch and bipad: Designing bimanual interaction for hand-held tablets[END_REF]. Table 1 summarizes the results.

A visual inspection of this table reveals a mix of disagreement and agreement. The researcher is initially worried, but is then relieved to see that her agreement analysis yields a quite respectable AR = .265. This value can be considered respectable because it is slightly higher than the average AR reported by Vatavu and Wobbrock [START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF] from 18 previous elicitation studies, and because it can be interpreted as a medium level of agreement according to their recommendations.

The researcher was right to be worried, however. Suppose that the study is replicated, but participants are blindfolded and cannot see any of the referents presented to them -they are simply asked to guess. Their choice of grasp will thus be random. Suppose all grasps are equally preferred. Shockingly, this study will yield an expected overall agreement rate of AR = .200, not far from the previously observed AR.

Since all grasps are equally likely, the probability that a given participant proposes a specific grasp for a given referent is 1/5 = 0.2, and the probability that a given pair of participants proposes it is 0.2 × 0.2. Since two participants can agree on any of the five grasps, the probability of agreement for a pair of participants on a referent is

5 × 0.2 × 0.2 = 0.2.
Therefore, the expected proportion of participant pairs who are in agreement -that is, the expected AR -is 0.2.

Given that there could not have been any intrinsic agreement between participants, one would rather expect an agreement index to give a result close to zero. Furthermore, one would certainly not label such a result as a "medium" agreement.

Arguably, the blindfolded study is purely fictional, and no gesture elicitation study involves participants who make completely random decisions. Nevertheless, gesture elicitation involves subjective judgments, where randomness can play a role. A participant may be uncertain about which gesture is the best, and in some situations, may even respond randomly. Such situations can include highly abstract referents for which there is no intuitive gesture, poor experimental instructions, gesture options that are too similar, or a lack of user familiarity with the specific domain or context of use.

Due to sources of randomness in participants' choice of signs, any value of AR reflects both intrinsic and spurious agreement. How much spurious agreement AR reflect depends on the likelihood of chance agreement, which in turn depends on the number of signs. The vocabulary of five signs used in our example is rather small, but not implausible for a study. Even for large vocabularies, participants often show a strong preference for a few signs (e.g., [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF]). Such biases can greatly increase chance agreement and inflate agreement rates. Therefore, it seems safer to always correct for chance agreement.

CORRECTING FOR CHANCE AGREEMENT

A large volume of research has examined the problem of chance agreement in the context of inter-rater reliability studies, i.e., studies that involve subjective human assessments [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. In this section, we explain how results from this research can be applied to gesture elicitation studies.

Inter-rater reliability studies employ a different terminology from gesture elicitation studies, but the mapping between the two is straightforward. Study participants become raters (also called judges or coders), referents become items (often confusingly called subjects), signs become categories, and gestures become ratings (or judgments) [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF].

Kappa Coefficients

Work on chance-corrected indices of agreement dates back to at least the 50-60's. Early on, Cohen proposed the Kappa coefficient to measure the agreement between two raters:

κ = p a -p e 1 -p e (3)
where p a is the proportion of items on which both raters agree, and p e is chance agreement. According to Cohen [START_REF] Cohen | A Coefficient of Agreement for Nominal Scales[END_REF], Kappa measures "the proportion of agreement after chance agreement is removed from consideration." The nominator captures "the percent of units in which beyond-chance agreement occurred", while the denominator is a normalizing term that captures maximum beyond-chance agreement.

The p e term does not assume equiprobable categories as in our blindfolded study but instead considers the distribution of categories assigned by each rater across all items. Scott's π coefficent [START_REF] Scott | Reliability of content analysis: The case of nominal scale coding[END_REF] makes the additional assumption that all raters share the same distribution of categories.

Most chance-corrected agreement indices known today are based on Equation 3. Each index makes different assumptions and has different limitations [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. More than forty years ago, Fleiss [START_REF] Fleiss | Measuring nominal scale agreement among many raters[END_REF] proposed to extend Cohen's Kappa (but actually extended Scott's π) to multiple raters. For p a he uses the "proportion of agreeing pairs out of all the possible pairs of assignments" [START_REF] Fleiss | Measuring nominal scale agreement among many raters[END_REF], also called percent agreement. This formulation for p a is used in many other indices, and is the same as Vatavu and Wobbrock's [START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF] agreement rate AR.

For the chance agreement term p e , Fleiss uses:

p e = q k=1 π 2 k , π k = 1 m m i=1 n ik n i ( 4
)
where m is the total number of items, n ik is the number of ratings for item i having category k, and n i is the total number of ratings for item i. The value π k estimates the probability that a rater classifies an item into category k, based on how many times this category has been used across the entire study.

In Table 1, Fleiss' chance agreement is p e = .251. Fleiss' Kappa is thus κ F = .265-.251 1-.251 = .018, reflecting a close-tochance overall agreement. Note that κ F is allowed to be negative, which would suggest a beyond-chance disagreement.

A large volume of research has been devoted on how to best estimate p e . The Brennan-Prediger coefficient [START_REF] Brennan | Coefficient kappa: Some uses, misuses, and alternatives[END_REF] uses the simplest estimate p e = 1/q, where q is the total number of categories. It assumes equiprobable selection of categories, as in our blindfolded example. The chance agreement for Table 1 becomes p e = .200, and the Brennan-Prediger agreement coefficient yields κ q = .081. However, Table 1 suggests that equiprobable categories is not a realistic assumption, as in most gesture elicitation studies. The coefficient has also been criticized for giving researchers incentive to increase the number of categories to artificially inflate agreement.

Another measure of agrement, widely used in content analysis, is Krippendorff's α [START_REF] Krippendorff | Content analysis: An introduction to its methodology[END_REF]. Krippendorff's α uses a different formulation for both p a and p e and can be used for studies with any number of raters, incomplete data (i.e., not all raters rate all items), and different scales including nominal, ordinal and ratio. For simple designs, its results are generally very close to Fleiss' Kappa, especially when there is no missing data and the number of raters is greater than five [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF].

Applying Agreement Coefficients to Elicitation Studies

Any chance-corrected agreement coefficient can be used to analyze agreement in gesture elicitation studies. Gesture elicitation studies, however, have unique features. For example, in contrast to typical inter-rater reliability studies where raters choose among a pre-assigned set of categories, many gestures elicitation studies do not enforce a fixed set of categories. Participants can be creative and propose gestures that are not foreseen by the investigators. In these cases, categories are defined a posteriori by the investigators, after inspecting the data. In the simplest cases where gestures can still be categorized objectively, the validity of agreement rates should not be affected. More complex cases are outside the scope of this note and will be briefly discussed in the conclusion.

Research on inter-rater agreement has also mostly focused on the use of overall agreement scores for validation purposes. In contrast, gesture elicitation studies are mainly used to inform design. Researchers are interested in finer details concerning agreement, i.e., situations in which agreement is high and situations which exhibit little consensus. To this end, the analysis and graphing of agreement scores for all individual items (referents) is a useful and commonly employed method. When examining agreement on individual referents or groups of referents, chance-corrected agreement can be assessed by computing p a for each referent or group of referent, and using a common p e estimated across all items. Agreement indices also exist that are computed on an item-per-item basis [START_REF] O'connell | General observer-agreement measures on individual subjects and groups of subjects[END_REF].

Since chance correction typically only scales and offsets all per-referent agreements, relative differences are preserved. Thus, if only relative differences are of interest (e.g., which are the most consensual and the least consensual referents?), the use of percent agreements is acceptable. Correction for chance agreement is more strongly recommended when overall chance agreements are reported, or when comparing agreements across different gesture sets or different studies.

Statistical Inference

Statistical inference is the process of drawing conclusions about populations by observing random samples. When doing so, it is crucial to determine what is randomly sampled and what is not. In many inter-rater reliability studies, items are assumed to be sampled from a larger population of items [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. In gesture elicitation studies, items (i.e., referents) are fixed: any conclusion typically only applies to these items. Raters, in contrast, are chosen arbitrarily, and an investigator may need to generalize her conclusions to the entire population of potential raters. Rater recruitment is a source of variability in the calculation of agreement coefficients, and this variability should ideally be acknowledged when presenting results, and when comparing results across studies.

The sampling distribution of agreement coefficients is often hard to approximate, but resampling methods such as jackknifing [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF] and bootstrapping [START_REF] Hayes | Answering the call for a standard reliability measure for coding data[END_REF][START_REF] Wood | Bootstrapped confidence intervals as an approach to statistical inference[END_REF] can be used to produce variance estimates, standard errors and confidence intervals for almost any agreement coefficient. Confidence intervals can be used both for communicating uncertainty and for testing hypotheses [START_REF] Dragicevic | HCI Statistics without p-values[END_REF]. To compare two agreement scores obtained from the same set of participants (e.g., to compare agreement across referents or groups of referents), a jackknife or bootstrap confidence interval can be computed on their difference. This generally yields higher statistical precision than inspecting how individual confidence intervals overlap [START_REF] Cumming | Inference by eye: confidence intervals and how to read pictures of data[END_REF].

Interpreting the Magnitude of Agreement

Gwet [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF] dedicates a full chapter on how to interpret the magnitude of an agreement. Several authors suggested conventional thresholds to help researchers in this task -Fleiss, for example, labels κ < .400 as "poor" and κ > .750 as "excellent" [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. Krippendorff suggested α > .667 and then later α > .800 as thresholds below which data must be rejected as unreliable [START_REF] Krippendorff | Reliability in content analysis: Some common misconceptions and recommendations[END_REF]. However, he and many others recognized that such thresholds are largely arbitrary and should be chosen depending on the application domain and on the "costs of drawing invalid conclusions from these data" [START_REF] Krippendorff | Reliability in content analysis: Some common misconceptions and recommendations[END_REF]. It has also been emphasized that the magnitude of an agreement cannot be interpreted if confidence intervals are not provided [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF][START_REF] Krippendorff | Reliability in content analysis: Some common misconceptions and recommendations[END_REF].

In gesture elicitation studies, the bar for an agreement score to be considered acceptable is way lower, even when ignoring chance agreement by considering AR only. Vatavu and Wobbrock [START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF] They suggest to refer to AR < .100 as a low agreement, .100 < AR < .300 as medium, .300 < AR < .500 as high, and to AR > .500 as a very high agreement.

However, Vatavu and Wobbrock's probabilistic reasoning is based on a null distribution assuming a 50% chance of agreement between participant pairs, so it is not clear to what extent it can answer a question about effect sizes. Setting standards based on results from past studies seems more sensible, but can also discourage efforts to raise our standards. Indeed, there does not seem to be any valid reason to be satisfied with a gesture agreement rate of .2 or .5. As much as we would like to have objective rules to help us distinguish between acceptable and unacceptable agreement scores, it is wise to refrain from using any such rule until these can be grounded in more solid cost-benefit analyses that integrate usability metrics.

CASE STUDY

We demonstrate the use of chance-corrected agreement coefficientsby re-analyzing a gesture elicitation study by Bailly et al. [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF]. The study was also re-analyzed by Vatavu and Wobbrock [START_REF] Vatavu | Formalizing agreement analysis for elicitation studies: New measures, significance test, and toolkit[END_REF], thus it provides a good basis for comparison. Bailly et al introduce Métamorphe, a keyboard with actuated keys that sense user gestures (e.g., pull, twist, or push sideways). In their study, 20 users suggested a keyboard shortcut for 42 referents on a Métamorphe mockup. Choosing a keyboard shortcut required choosing i) a key and ii) the gesture applied to the key. Bailly et al. treat shortcuts as a whole, but also analyze keys and gestures separately. Here, we focus on analyzing keys and gestures separately. Participants produced a total of 71 different signs for keys and 27 different signs for gestures (compound gestures were counted as separate signs).

Table 2 shows overall agreement scores for keys and for gestures, computed using A, AR and Fleiss' Kappa1 . An investigator who uses the index A or AR may infer that participants' consensus was higher for gestures than for keys. However, Fleiss' Kappa values reveal that this difference is most likely due to chance agreement. As the number of signs was lower for gestures than for keys and participants exhibited a strong bias for the "top push" sign [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF], agreement was more likely to occur by chance. Fleiss' Kappa corrects for this and allows the investigator to reason about intrinsic agreement.

In addition to point estimates of agreement values, Table 2 reports 95% CIs calculated using the jackknife method [START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. Researchers attached to null hypothesis significance testing can observe that none of the intervals contains zero, thus the existence of agreement (both chance-corrected and uncorrected) can be presented as statistically significant at the α=.05 level [START_REF] Dragicevic | HCI Statistics without p-values[END_REF]. However, showing that an agreement is greater than zero is not very informative [START_REF] Krippendorff | Reliability in content analysis: Some common misconceptions and recommendations[END_REF][START_REF] Gwet | Handbook of Inter-Rater Reliability, 4th Edition: The Definitive Guide to Measuring The Extent of Agreement Among Raters[END_REF]. CIs allow for more useful statements, e.g., we can be reasonably confident that across all users similar to the ones recruited for the study, the average Fleiss' Kappa is between .15 and .37 for keys, and between .19 and .29 for gestures. We can further test whether the difference we noticed between the ARs for keys and gestures is reliable: the difference is 0.05, 95% CI = [-0.05, 0.16], thus we cannot confidently conclude that there is a difference. Finally, we can back up claims on the effect of referents such as "highly directional commands [...] tended to have a high gesture agreement" [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF]. The difference in Fleiss' Kappa between the 8 referents containing the terms top, bottom, left, right, previous or next and all other referents is 0.41, 95% CI [0.24, 0.58], so the evidence is overwhelming.

DISCUSSION AND CONCLUSION

We discussed the problem of chance agreement in gesture elicitation studies, and how it can bias results. This issue most strongly affects studies with small sign vocabularies, and studies exhibiting a strong user bias for some signs. Since user bias cannot be controlled for, it is safer to always use indices that correct for chance agreement. We also motivated the use of confidence intervals, especially when making claims about overall agreement scores.

There are many issues this note does not address. For example, indices of agreement between user-elicited gestures and UI gesture sets such as the "guessability" metric proposed by Wobbrock et al. [START_REF] Wobbrock | Maximizing the guessability of symbolic input[END_REF] are important but not addressed here. Furthermore, gesture elicitation studies can employ complex designs features that are not well supported by existing interrater agreement methods or may violate their model assumptions. These include the use of non-overlapping gestures sets and semantic grouping [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF], hierarchically-structured sign sets [START_REF] Bailly | Métamorphe: Augmenting hotkey usage with actuated keys[END_REF], and multiple gesture proposals per referent [START_REF] Morris | Web on the wall: Insights from a multimodal interaction elicitation study[END_REF].

Another pending issue is how to account for the subjectivity often inherent in the process of classifying user-elicited gestures into signs, especially in open coding settings [START_REF] Grijincu | User-defined interface gestures: dataset and analysis[END_REF]. This subjectivity poses a threat to validity and can possibly render all data and analyses meaningless, agreement indices included. Content analysis has developed methods to ensure reliability in similar situations [START_REF] Krippendorff | Content analysis: An introduction to its methodology[END_REF], but these have been largely ignored in elicitation studies. Since content analysis also uses agreement indices, gesture elicitation studies would need to consider agreement at two very different levels.

Gesture elicitation studies are extremely useful but can be very complex to set up and analyze. The proper methodology that can ensure reliability and scientific rigor largely remains to be developed. HCI can gain a lot by considering the lessons learned in other disciplines where similar issues have been discussed, instead of (re-)developing methods in isolation. HCI also has the opportunity to contribute to the interdisciplinary debate on how to assess and use agreement, given that its complex study designs can pose interesting methodological challenges that have never been studied before.

Table 2 .

 2 offer guidelines for interpreting AR based on a probabilistic reasoning and a survey of past studies. [.213, .427] .284 [.172, .397] .260 [.148, .371] Gestures .370 [.323, .417] .336 [.287, .386] .240 [.192, .289] Values of different indices of agreement (A, AR and Fleiss' κ) for Bailly et al.'s study [1]. Brackets indicate 95% jackknife CIs.

		A	AR	Fleiss' Kappa
	Keys	.320

The content of this paper was finalized on September 22, 2015. It was registered as research report on February 2016: Research Report No 1584, Laboratoire de Recherche en Informatique (LRI), CNRS and Université Paris-Sud, Feb 2016.

Bailly et al only considered 15 signs for gestures by grouping uncommon signs into "combo" and "other". We kept

all 27 signs to be consistent with Vatavu and Wobbrock's analysis, but the results are very similar. Vatavu and Wobbrock report AR = .336 but A = .406 for gestures, which is likely an error since it violates the linear relationship between A and AR expressed in their Equation (3).