Mireilla Martinez

Anna I Esparcia
email: aesparcia@pros.upv.es

Urko Rueda
email: urueda@pros.upv.es

Tanja E J Vos
email: tvos@pros.upv.es

Carlos Ortega
email: cortega@indenova.com

Automated localisation testing in industry with Test *

Keywords: Automated testing, localisation, technology transfer

Test * is a testing tool that automatically and dynamically generates, executes and verifies test sequences based on a tree model that is derived from the software User Interface through assistive technologies. Test * is an academic prototype that we continuosly try to transfer to companies to get feedback about its applicability. In this paper we report on one of these short experiences of using Test * in industry at the Valencian company Indenova. We applied the tool to check the localisation quality of a secure web platform that encapsulates a set of applications as services.

Introduction

In previous work [START_REF] Rueda | TESTAR: from academic prototype towards an industry-ready tool for automated testing at the user interface level[END_REF] we have presented an approach to automated testing of software applications from their User Interface (UI). Test *1 automatically and dynamically generates test sequences which are executed and verified to reveal quality issues of the software under test. The tool is based on a tree model that is derived from the UI through the Operating System' Accessibility API 2 . From that API we can get access to the set of widgets that compose the UI of the target application (e.g. buttons, text-fields, menu bars) and the properties of each widget that characterise their appearance in the screen (e.g. screen position, size, whether it is enabled or not). From the UI model Test * is able to compute a set of feasible actions (user events like left clicks and typing texts) to automate the interaction, so do the testing, with the software interface. No test cases are recorded and the tree model is dynamically inferred for every state 3 , this implies that tests will run even when the GUI changes. This reduces the maintenance problem that threatens other GUI testing techniques like Capture and Replay [START_REF] Nguyen | Guitar: an innovative tool for automated testing of gui-driven software[END_REF] or Visual testing [START_REF] Alegroth | Jautomate: A tool for system-and acceptance-test automation[END_REF].

The Test * tool has been developed in the context of the EU FITTEST project that finished in 2014. First, it was evaluated in experimental conditions using different real and complex software applications like MS Office suite (running it 48 hours we detected 14 crash sequences). Subsequently, and with the purpose of getting a better understanding about the applicability of the tool in an industrial environment, we continuosly try to apply Test * in companies to get feedback about its applicability and help companies to obtain solutions to the problems they face. In [START_REF] Tanja | Testar: Tool support for test automation at the user interface level[END_REF] results are described of transferring and evaluating the tool within 3 different companies on 2 desktop applications and one web application. In this paper we report on yet another short experience of using Test * in industry at the Valencian company Indenova4 .

Test *

To automate test generation, execution and verification, Test * performs the steps as is shown in Fig. 1: (1) start the SUT (System Under Test); (2) obtain the GUI's State (a widget tree5 ); (3) derive a set of sensible actions that a user could execute in a specific SUT's state (i.e. clicks, text inputs, mouse gestures); (4) select one of these actions (random or using some search-based optimisation criteria); (5) execute the selected action (through Java Robot6 class); (6) apply the available oracles to check (in)validness of the new UI state. If a fault is found, stop the SUT (7) and save a re-playable sequence of the test that found the fault. If not, keep on testing if more actions are desired within the test sequence.

Using Test * , you can start testing immediately from the UI without the traditional requirement of specifying test cases, which are commonly provided manually with some degree of tool support. Based on the information gathered from the Accessibility API tests are generated by selecting an action to execute in the UI (e.g. left click a button with the title "Ok"). The action selection mechanism mainly drives how the test cases are generated, which can be performed randomly (select any suitable action for the current UI) or using a more advanced approach to increase the effectiveness of tests like the work in [START_REF] Bauersfeld | A reinforcement learning approach to automated gui robustness testing[END_REF]. Without specifying anything, Test * can detect the violation of generalpurpose system requirements through implicit oracles like those stating that the SUT should not crash, the SUT should not find itself in an unresponsive state (freeze) and the GUI state should not contain any widget with suspicious words like error, problem, exception, etc. This is a very attractive feature for companies because it enables them to start testing immediately and refine the tests as we go.

Indenova and the SUT eSigna

Indenova is a Valencian ICT company that provides ERP (Enterprise Resource Planning) solutions for companies. Their initial clients are based in Spain. But throughout the years, Indenova has gained new clients in Latin America. Testing at Indenova is mainly manual and basically done at the system acceptance test level. Written requirements are used for the design of system test suites. They would like to have more tests automated, but currently in the company there is a lack of time and people with knowledge about test automation.

Becoming aware of Test * Indenova is very interested to see how they can start test automation, so they provided access to their eSigna product. It is a web platform that securely integrates and provides access to applications as services enabling users to perform specific processes inside their organisations. Thus, eSigna is a base component in which concrete services can be plugged-in as required by each particular project. Those services are independent from each other, but they are interconnected to share information in real time.

The industrial experience

During the investigation we have measured the following effectiveness and efficiency aspects of Test * for testing the localisation quality of eSigna:

Planning the testing: what do we want to test

One of the immediate problems that Indenova faces with eSigna, localisation to Latin America community, fits perfectly with Test * capabilities. The tool enables not only to detect stability problems for free, like crashes and exceptions, but it also allows to systematically analyse the UI in the search of wrongly translated texts.

As previously indicated, the initial clients from Indenova were from Spain, but gradually they have expanded to Spanish speaking South American countries. One of the problem encountered is that there are differences between the Castilian Spanish spoken in Spain and the different Latin American Spanish. Although it is not a problem of not being able to understand what is meant, some of the clients from Columbia and Peru just have complained about the usage of Castilian words. For example:

English

Castilian Spanish Latin American Spanish Mobile phone Móvil Celular Holiday Festivo Feriado Computer Ordenador Computadora Since the implementation is not based on dictionaries and the Castilian Spanish is hard-coded, there is no other way than test the application to find the words that need to be changed for the other countries. This is a tedious and boring job.

Implementing the Test * protocol

Test * has the flexibility to adapt its default behaviour for specific needs. We will describe next how did we setup the tool to automatically verify localisation problems on eSigna product. We refer to the steps in the testing flow (Fig. 1 approaches to stop a test, including a fixed time for execution, a fixed length for the number of UI actions to be executed or a self-made stopping criteria through a Java based protocol class (check next point). We made use of the last option to establish that we have tested enough when no more new UI is being exercised by our tests. 6. Advanced setup editing the tool' test protocol: Test * provides a Java class composed of a method for each task in the testing cycle presented in figure 1. Concretely, we implemented the automated login inside the task START SUT, non-interesting actions filtering inside the task DERIVE SET OF USER ACTIONS and the stopping criteria in the more actions? check point.

Once Test * was setup for automated localisation verification we just had to wait for the tool test reports. Following the testing flow of Test * it would first activate eSigna, perform an automated login and repeat a cycle of <select and execute action, verify localisation problems, check stopping criteria>.

Testing and Evaluation

Our context multilingual scenario consisted of one target language, Latin American Spanish, as this was the first concern on eSigna testing with Test * . We account in table 1 (LOC = Lines Of Code; time in minutes) for metrics that measure the effort required for our solution on automated verification of localisation issues.

Setting up Test * for eSigna is an easy process that consists on providing the command line that would activate the product. Actions configuration would require some effort though as we would like Test * to perform automated tests without user intervention. Thus, we first need to analyse eSigna authentication process to provide the proper actions once the product has been activated. Additionally, we wanted to maintain our tests in relevant UI parts of eSigna, for example disabling/filtering non interesting actions like closing the browser, logout of eSigna, etc. Yet, 35 lines of code and 10 minutes were enough for Test * to perform automated tests over eSigna. We acknowledge that future enhancements on Test * would enable a more efficient configuration of actions (we used version 1.1a of the tool). Oracles did not require any lines of code, but just a regular expression with the full list of unwanted localised product words (e.g. Móvil, Festivo, Ordenador). From Indenova, we acquired a full list of more than 30 words that the Latin American community had issued to the company in the past. This list contained wrongly used Spanish words (e.g. Móvil instead of Celular). Thus, we defined the regular expression for the words in the list that would enable Test * to check the quality of eSigna with respect to its localisation.

The stopping criteria was easily implemented taking into account how much of the UI was being exercised (user events) by the test. We named this UI space exploration, where the full UI space is composed of every particular and different7 screen window that the application might show to the user. We forced to stop the tests when no more UI space was being explored by the last 100 executed actions. In other words, when there was no new UI window already exercised by the test.

Finally, using the configuration just described we let Test * run a test for almost an hour. The tool was able to report localisation issues on 2 words from the list in the first 5 minutes of execution. Both words were confirmed by the company as they were already aware that they were incorrectly localised. Other words were not reported, but Indenova indicated that such words were not part of the product. We also observed that new UI space was explored after an hour of execution, which could reveal additional issues in the localised product. We expect a direct relation between the UI space exploration (coverage) and the effectiveness achieved on localisation verification of software products, but this should be analysed in a further study.

We would like to make some final considerations. We acknowledge that the verification of localisation issues has been traditionally performed using other alternatives, for example through text finding utilities like grep command on Linux hosts or a general purpose text editor with file searching features. A main efficiency problem of these approaches is that we cannot safely distinguish between texts used in the source code, and text that is mainly appearing in the UI: users will never complain on texts that they do not see in the User Interface.

Moreover, more complex products like eSigna might make more difficult to check localisation issues when the source code is spread over several (virtual) machines (perhaps targeting different operative systems), databases, or even legacy systems. In this sense, Test * provides a central setup place from which products localisation can be verified.

Additionally, we decided to stop our tests after an hour of execution tough we could have allowed it to run for longer. If checking localisation issues is performed manually by a human (interacting with the UI) then Test * is helpful once it is setup correctly, as it can operate without human supervision. Although Test * is a general purpose testing tool, we have presented how it can be used to verify that a software product has the quality levels expected by a company like inDenova.

Conclusions and further work

We have presented a short experience of transferring an academic prototype from the university to the industry, for testing software applications at the UI level. Indenova is a Valencian ICT company that provides ERP solutions to other companies. We applied the prototype Test * for testing localisation issues in eSigna product, which targets the Latin American countries. eSigna is a secure web platform composed of integrated web services.

The automation level achieved by the prototype and its potential for testing software products made Indenova consider the integration of Test * into their testing processes. They used the prototype for performing smoke testing, which would provide early feedback of the quality of developed product versions.

As further work, we will improve localisation testing in the prototype by including dictionaries. We would also like to further investigate the effectiveness of the presented localisation testing solution, concretely its relation to the test' UI space coverage.

Fig. 1 .

 1 Fig. 1. Test * testing flow

1 .

 1 Number of failures (wrongly translated words) observed after executing Test * on eSigna 2. Time needed to set-up the test environment and get everything running 3. Lines Of Code (LOC) and time needed for UI actions definition, oracles design and stopping criteria setup. 4. Time for running Test * to reveal localisation issues on eSigna. The project has been carried out in a fashion that allowed us to perform iterative development of Test * . The process included the following steps which were repeated several times to yield the final setup: 1. Planning: Implementation of Test Environment, consisting of planning and implementing the technical details of the test environment for Test * , as well as the anticipating and identifying potential fault patterns in the Error Definition. 2. Implementation: Consisting of implementing the Test * protocol consisting of: Oracles to implement the detection of the errors defined in the previous step; Action Definition to define the action set from which Test * selects; and the Implementation of stopping criteria that determine when sufficient testing has been done by Test * . 3. Testing and Evaluation: Run the tests.

	Test

*

  ):1. START SUT -Set eSigna activation: it will tell Test * how to start/run the application. Being a web application, it consists of a command line BROWSER URL where BROWSER is the path and executable of an available web browser (i.e. Internet Explorer) and URL the entry point for the eSigna web application. 2. DERIVE SET OF USER ACTIONS -Set suitable actions: from the space of candidate actions that the user could perform over the product UI we are interested in 1) actions that will enable an automatic login to eSigna and 2) actions which are not interesting for our localisation verifying objective (i.e. web browser actions, a logout button, an administration panel in eSigna, etc.) 3. SELECT ACTION -Set test algorithm: the tool provides several strategies to generate a test (e.g. picking a random action each time). We are interested in exercising as much of the UI as possible to verify any potential localisation issues. We selected the Q-Learning algorithm from previous work[START_REF] Bauersfeld | A reinforcement learning approach to automated gui robustness testing[END_REF]. 4. ORACLE -Set localisation oracles: verifying the localisation correctness of eSigna for a target language can be straightforward performed by defining a list of taboo words that should not appear in the UI. This list can be easily defined in Test

* UI through Java regular expressions (i.e. .*[mM][óo]vil.*|.*[fF]estivo.*|.*[oO]rdenador.*). 5. FAULT?/more actions? -Set the stopping criteria: the tool offers different

Table 1 .

 1 Efficiency

	Setup environment Actions Oracles Stop criteria Test run
	time	LOC time LOC time LOC time	time
	1	35 10	0	5	9	2	>60

Previously known as TESTAR or Testar, and available as open source at http://www.testar.org

https://msdn.microsoft.com/en-us/library/windows/desktop/ff486375(v=vs.85).aspx

The Graphical User Interface at a particular time

www.indenova.com/

Test * uses the Operating System's Accessibility API, which has the capability to detect and expose a GUI's widgets, and their corresponding properties like: display position, widget size, title, description, etc.

https://docs.oracle.com/javase/8/docs/api/java/awt/Robot.html

two windows are considered different if there is almost a) one widget not present in both windows or b) a widget with different properties (e.g. text or size)) in each window

Acknowledgement

This work was partly funded by the SHIP project (EACEA/A2/UHB/CL 554187) and the PERTEST project (TIN2013-46928-C3-1-R). Test * was funded by the EC within the context of the FITTEST project, ICT-2009ICT- .1.2 no 257574 (2012ICT- -2015)).


Ludwig Kampel
email: lkampel@sba-research.org

Dimitris E Simos
email: dsimos@sba-research.org

Set-based Algorithms for Combinatorial Test Set Generation

Keywords: Combinatorial testing, independent families of sets, setbased algorithms

Testing is an important and expensive part of software and hardware development. Over the recent years, the construction of combinatorial interaction tests rose to play an important role towards making the cost of testing more efficient. Covering arrays are the key element of combinatorial interaction testing and a means to provide abstract test sets. In this paper, we present a family of set-based algorithms for generating covering arrays and thus combinatorial test sets. Our algorithms build upon an existing mathematical method for constructing independent families of sets, which we extend sufficiently in terms of algorithmic design in this paper. We compare our algorithms against commonly used greedy methods for producing 3-way combinatorial test sets, and these initial evaluation results favor our approach in terms of generating smaller test sets.

Introduction

In modern software development testing plays an important role and therefore requires a large amount of time and resources. According to a report of the National Institute of Standards in Technology (NIST) [START_REF]The economic impacts of inadequate infrastructure for software testing[END_REF], faults in software costs the U.S. economy up to $59.5 billion per year, where these costs could be reduced by $22.2 billion, provided better software testing infrastructure. Another report from NIST [START_REF] Kuhn | Practical combinatorial testing[END_REF] shows that failures appear to be caused by the interaction of only few input parameters of the system under test (SUT). Combinatorial testing guarantees good input-space coverage, while reducing the resources needed for testing. In particular, it is a t-wise testing strategy whose key ingredient is a Covering Array (CA), a abstract mathematical object that provides coverage of all t-way interactions of a certain amount of input parameters, reducing the amount of tests that need to be executed. For their use in practice, the columns of CAs are identified with the input parameters of the SUT, where each entry in a certain column is mapped to a value of the corresponding parameter [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF]. This way each row of the CA translates to a certain parameter value setting of the input model of the SUT which can be used as a test. Translating each row of a CA in this way, one obtains a concrete test set hence a CA can be regarded as an abstract combinatorial test set. To reduce further the amount of resources needed for testing, one is interested to construct optimal CAs (e.g. arrays of a minimal size that provide maximal coverage). This software testing problem is tightly coupled with hard combinatorial optimization problems for CAs (shown to be NP-hard [START_REF] Seroussi | Vector sets for exhaustive testing of logic circuits[END_REF]).

Contribution. In this paper, we use a set-based method for constructing CAs based on independent families of sets (IFS) from [START_REF] Freiman | A polynomial algorithm for constructing families of k-independent sets[END_REF]. There exists an equivalence between these two combinatorial objects which allowed us to use the two discrete structures interchangeably in terms of algorithmic design. In particular, we extend this set-based method with balancing properties that can impose restrictions on the cardinality of the appearing intersections. This (among other concepts) enabled us to define different building blocks that give rise to a family of algorithms based on IFSs (and consequently also for CAs). Furthermore, as a proof of concept we compared our algorithms against a widely used combinatorial strategy (the so-called IPO-strategy [START_REF] Lei | In-parameter-order: A test generation strategy for pairwise testing[END_REF]) which bares similarities with our approach for constructing and extending CAs. Our initial results outperform this strategy for 3-way testing, generating better sized covering arrays.

Structure of the paper. In Section 2 we give some preliminaries for CAs, where we also review related algorithms and problems for the former objects. Afterwards, in Section 3 we describe a set-based method for constructing CAs and extend it with concepts necessary for devising an algorithmic concept later on Section 4, in which we also propose a variety of algorithms for generating CAs. Subsequently, in Section 5 we compare our algorithms against IPO-strategy greedy techniques for constructing CAs and comment on the evaluated results. Finally, 6 concludes the work and discusses future directions of work.

Problems and Algorithms for Covering Arrays

In this section we give a short overview of the needed definitions, as well as of related problems, related algorithms and work in general. In the following we frequently use the abbreviation [N ] for a set {1, . . . , N } ⊆ N and also

A C denotes the complement [N ] \ A of A in [N ].
The definitions given below are slightly different phrased as those given in [START_REF] Colbourn | Handbook of combinatorial designs[END_REF], and can also be found in [START_REF] Lawrence | A survey of binary covering arrays[END_REF].

Preliminaries for Covering Arrays

Definition 1 (t-Independent Family of Sets). A t-independent family of sets, IFS (N ; t, k), is a family (A 1 , . . . , A k ) of k subsets of [N ], with the property that for each choice {i 1 , . . . , i t } ⊆ [k] of t different indices, for all j ∈ [t] and for all Āij ∈ {A ij , A C ij } it holds that t j=1 Āij = ∅. The parameters t and k are called, respectively, the strength and the size of the IFS.

We say that a family of sets is t-independent if it is an IFS (N ; t, k) for some value of N and k. Without loss of generality we only consider IFS over a underlying set [N ] with N ∈ N. A1 = {6, 7, 8, 9, 10, 11} ↔ (0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0) T = a1 A2 = {1, 2, 3, 6, 7, 8} ↔ (1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0) T = a2 A3 = {1, 2, 4, 6, 9, 10} ↔ (1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0) T = a3 A4 = {1, 2, 5, 7, 9, 11} ↔ (1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0) T = a4 B = {1, 2, 5, 8, 9, 10} ↔ (1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0) T = b Table 1. The sets A1, A2, A3, A4 and B are considered as subsets of [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF]. We identify them with their binary indicator vectors, i.e. vectors in {0, 1} 12 that have 1 in position i if, and only if i is element of the corresponding set, and 0 otherwise.

Example 1. From Table 1 the family A = (A 1 , A 2 , A 3 , B) is an IFS (12; 3, 4), i.e. if we choose 3 sets of A or independently their complements, their intersection is nonempty. For example,

A 1 ∩ A C 3 ∩ B = {8} = ∅ and A 1 ∩ A 2 ∩ A C 3 = {7, 8} = ∅.
(m i 1 , . . . , m i t ).
In some cases M is also called a binary covering array of strength t.

Remark 1. Covering arrays of fixed non-binary alphabet with size u are denoted with CA(N ; t, k, u) in the literature (e.g. see [START_REF] Colbourn | Handbook of combinatorial designs[END_REF]). When u = 2 is clear from the context we simply use the notation introduced as above.

As the similarity of the former definitions of these combinatorial objects implies, there is a close relation between the two of them. For example, it is known that every CA(N ; t, k) is equivalent to an IFS (N ; t, k) (see for example [START_REF] Lawrence | A survey of binary covering arrays[END_REF] and [START_REF] Colbourn | Handbook of combinatorial designs[END_REF], Remark 10.5).

Example 2. From Table 1 we take the vectors a 1 , a 2 , a 3 and b to form the array

A = (a 1 , a 2 , a 3 , b) =     0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0     T ,
which is equivalent to the IFS given in Example 1. The defining property of an IFS translates to the defining property of a binary CA. In this case, within each three selected columns of (a 1 , a 2 , a 3 , b), each binary 3-tuple appears at least once. Therefore the given array A is a CA (12; 3, 4). On the other hand, the IFS in Example 1 can be uniquely reconstructed from the array A, interpreting its columns as indicator vectors of subsets of [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF]. Definition 3. The smallest number of rows N such that a binary CA(N ; t, k) exists is defined as CAN (t, k) := min{N : ∃ CA(N ; t, k)}. Definition 4. The largest number k such that a IFS (N ; t, k) exists is defined as CAK (N ; t) := max{k : ∃ IFS (N ; t, k)}.

For an overview of the vast amount of theoretical and computational problems that arise in the theory of CAs we refer to [START_REF] Colbourn | Combinatorial aspects of covering arrays[END_REF], [START_REF] Hartman | Problems and algorithms for covering arrays[END_REF]. Especially the problem of determining binary CAs with minimum amount of rows turns out to be NP-hard (see [START_REF] Seroussi | Vector sets for exhaustive testing of logic circuits[END_REF]).

Algorithms for Covering Arrays

The notorious difficulty of constructing optimal CAs has been the subject of many algorithmic approaches. The most related ones to our work are greedy methods such as AETG [START_REF] Cohen | The aetg system: An approach to testing based on combinatorial design[END_REF] and IPO [START_REF] Lei | In-parameter-order: A test generation strategy for pairwise testing[END_REF]. AETG employs a randomized, greedy, one row at a time extension strategy. The IPO-strategy is to grow the covering array in both dimensions. Horizontal growth adds one column to the current array by its cells with entries in a greedy manner. Vertical extension is performed, by adding rows until the array is once again a CA. Adjusting the parameters of the IPO-strategy has been the subject of [START_REF] Gao | Balancing frequencies and fault detection in the in-parameter-order algorithm[END_REF]. Finally, in [START_REF] Freiman | A polynomial algorithm for constructing families of k-independent sets[END_REF] a method is proposed that produces exponentially sized IFS one set at a time. In terms of CAs this comes down to a one column at a time construction of a binary CA. As this method plays a pivotal role in our work, we further describe it in Section 3.

Due to space limitations, for other related works we refer the interested reader to a recent survey [START_REF] Torres-Jimenez | Survey of covering arrays[END_REF].

A Set-Based Method for Constructing CAs

In this section we elaborate on a set-based method for constructing CAs and extend it with concepts necessary for devising an algorithmic concept later on in Section 4.

Before the description of the method, we have to define some terms needed. It is well known that Orthogonal Arrays of index one are optimal CAs [START_REF] Colbourn | Handbook of combinatorial designs[END_REF], i.e. within each selection of t columns each binary t-tuple appears exactly once.

Also when constructing a CA with as few rows as possible, one tends to not cover certain t-tuples multiple times; rather the target would be to cover as few t-tuples as possible more than once. Lets consider the case of a CA (a 1 , . . . , a r ), where only few t-tuples appear more than once within a certain choice c = (a i 1 , . . . , a i t ) of t columns of that array. Since for each (t-1)-tuple (u 1 , . . . , u t-1 ) there are exactly two binary t-tuples, that start with (u 1 , . . . , u t-1 ), namely (u 1 , . . . , u t-1 , 0) and (u 1 , . . . , u t-1 , 1). We know that within (a i1 , . . . , a it-1 ) each (t -1)-tuple appears at least twice, and only few of them appear more than twice. Of course, this argument holds for each choice of (t -1) columns of c. Remark 2. Note as well that this argumentation can be iterated. From these thoughts we design a necessary condition when a column is allowed to be added to the current array. In particular, we want to ensure a minimum amount of balance among the columns of the array in the regard just described.

In light of the previous remark, we introduce the notion of α-balance.

Definition 5. Let A = (A 1 , . . . , A k ) be a family of sets A i ⊆ [N ] ∀i ∈ [k] and α = (α 1 , . . . , α s ) ∈ N s , s ≤ k. We say that A is α-balanced, if ∀i ∈ [s] ∀{j 1 , . . . , j i } ⊆ [k] ∀ Ājr ∈ {A jr , A C jr } : i r=1 Ājr ≥ α i . (1)
Note that if a family of sets is (α 1 , . . . , α s )-balanced and α s ≥ 1 then it is also s-independent.

Definition 6. Let B ⊆ [N ], A = (A 1 , . . . , A k ) be a family of sets A i ⊆ [N ] ∀i ∈
[k] and α = (α 1 , . . . , α s ) ∈ N s . We say that B α-balanced with respect to A, if the family (A 1 , . . . , A k , B) of sets is α-balanced.

Example 3. Consider the family F = (A 1 , A 2 , A 3 , A 4 ), constructed from the sets of Table 1. This family is a (6, 3)-balanced family of sets, i.e. each set, as well as its complement, has at least cardinality 6, and all intersections of any two sets of F (complements might be involved) have at least cardinality 3 (e.g.

A 1 ∩ A C 3 = {7, 8, 11} ≥ 3). B is an example for a set that is not (6, 3)-balanced w.r.t. F, since A C 3 ∩ B = |{5, 8}| = 2 < 3.

A New Family of IFS Algorithms

In this section, we propose a variety of algorithms, IFS-origin, IFS-greedy and IFS-score, based on independent families of sets. We call this class of algorithms collectively a family of IFS-Algorithms. In particular, we formalized and extended in terms of a combinatorial algorithmic design the method described earlier. Our design is comprised of the following five building blocks: store, select, admissible, extend and update which we state below.

-Store: The store is a data structure that serves as a resource, from which the sets to build the target IFS are chosen. It may be static, or dynamic. -Select: A procedure that returns one element of the store, e.g. randomly or via a scoring function.

-Admissible: This procedure decides whether a certain element is allowed to be added to the current IFS or not under certain admissible criteria which can be based for example on the concept of α-balance. -Extend: A procedure that extends the IFS at hand. -Update: The procedure which updates the store in case latter is dynamic.

In the following we frequently use

F 2 (N ) := {A ⊆ [N ]|N / ∈ A ∧ |A| = N/2 }
, which is a 2-independent family of sets of maximal size (cf. [START_REF] Kleitman | Families of k-independent sets[END_REF]). A comprehensive overview of the proposed algorithms via their building blocks, is given below in Table 4.

IFS-Origin

Firstly we give a short algorithmic description of the method proposed in [START_REF] Freiman | A polynomial algorithm for constructing families of k-independent sets[END_REF] and extended in Section 3. We refer to it and its implementation as IFS-origin.

The algorithm takes as input the N of the underlying set and the strength t of the to be constructed IFS. The initial Store, S 0 , is set to be equal to F 2 (N ) and the initial IFS, A 1 , is set to be a random element of the Store. This random initialization is justified because picking a different initial element boils down to permuting the first [N -1] elements of [N ], which also respects Definition 1, and keeps F 2 (N ) invariant under such permutations. From now on in each step i the IFS-origin traverses through the whole Store S i-1 given at that time, updating it by removing all non-Admissible α (Admissible α checks for α-balance and t-independence) elements from it, which yields S i . For the admissibility check the algorithm requires a vector α 1×(t-1) , which encodes the desired balance of i-tuples for i = 1, . . . , t-1. Thereafter, now that S i is left with only Admissible α elements, a random element is chosen and added to the IFS at hand, yielding A i+1 . The algorithm terminates when the Store is empty.

IFS-Greedy

When being familiar with IFS-origin described above, one will realize, that this version, as was originally given in [START_REF] Freiman | A polynomial algorithm for constructing families of k-independent sets[END_REF] lacks of a method to decide which of the elements in the remaining Store should be added to the current array. In particular, this is done via a random pick, which in retrospect makes the Update of the Store, which leaves the Store with only Admissible α elements inside, unnecessary. The newly proposed IFS-greedy version bypass this decision problem by simply taking the next found Admissible α element of the Store, having the advantage that the Store has never to be updated. The initialization stays the same as in IFS-origin. After that IFS-greedy traverses the Store only once, adding the first element that is Admissible with respect to the already chosen ones and α (recall Definition 6). The Store never gets updated.

IFS-Score

The overall structure of IFS-score is the same as that of IFS-origin, but different building blocks SelectScore and Admissible are defined. To circumvent the problem of IFS-origin of picking a random element from the updated Store, we calculated a score for each element of the Store, that reflects αbalance, and add the one (or one of those, since ties may occur) with the least score. Each element is initialized with a score of zero and in the i-th step of the algorithm we calculate again a score for each element of the current Store, S i-1 , as before. This has also the advantage that IFS-score does not require α. Since we compute a score for each element, we already encounter the tuple balance of (A i , b) to our selection and we do not need to previously dictate via α how often certain i-tuples have to appear. Therefore IFS-score is the only algorithm in the proposed IFS-family that does not require an input of α. Consequently, in an element of the Store passes the decision criterion of Admissible, if and only if (A, b) is t-independent.

Results

As a proof of concept of our algorithmic design (cf. Section 4) we compared our implementations of the IFS-family of algorithms for t = 3 to two of the most commonly used greedy algorithms of the IPO-family, namely IPOG [START_REF] Lei | IPOG-IPOG-D: Efficient test generation for multi-way combinatorial testing[END_REF] and IPOG-F [START_REF] Forbes | Refining the inparameter-order strategy for constructing covering arrays[END_REF]. In addition, we evaluate our results versus the current best known upper bounds for CAK (N ; 3) (retrieved from [START_REF] Colbourn | Table for CAN(3,k,2) for k up to 10000[END_REF], via CAK (N ; t) = max{k|CAN (k, t) ≤ N }, cf. [START_REF] Lawrence | A survey of binary covering arrays[END_REF]), that are combined results of algorithms and methods that are partly described in [START_REF] Torres-Jimenez | Survey of covering arrays[END_REF]. To the best of our knowledge the algorithms of the IPO-family are the only ones that generate CAs using a horizontal extension step similar to the one proposed in the IFS-family of algorithms. Table 5 shows the amount of columns a binary CA of strength 3 can attain by either the respective algorithm compared or according to [START_REF] Colbourn | Table for CAN(3,k,2) for k up to 10000[END_REF]. Table 5 starts with N = 8, since there are at least eight rows needed to cover all eight binary 3-tuples. It shows that the IFS-family of algorithms improves significantly over IPOG and IPOG-F in almost every case presented, as well that IFS-greedy and IFS-score improve over IFS-origin. It is also worth pointing out that during our computations we obtained larger families, when running IFS-origin and IFS-greedy on more restrictive α-vectors than running them on less restrictive α-vectors. We believe the concept of admissibility via α-balance (and its requirement per different IFS algorithms) makes the difference versus IPOG and IPOG-F, since these algorithms lack of a balancing strategy during horizontal extension. Regarding our results, we want to highlight that IFS-score is able to deliver almost the same size of output IFS as IFS-greedy without the need of an α-vector as input. On the other hand, IFS-score is more complex than IFS-greedy and even IFS-origin due to score computations.

The values for IPOG-F in Table 5 are taken from [START_REF]NIST: Table for CA(3,k,2[END_REF]. For the experimental evaluation we run IPOG locally as it is implemented in ACTS, a CA generation tool provided by NIST [START_REF] Yu | Acts: A combinatorial test generation tool[END_REF]. For the input values of N in Table 5, IPOG and IPOG-F were considerably faster than all three of our algorithms. We think that the extra computations are fully justified, since the IFS-family of algorithms outperforms IPOG and IPOG-F, in 14 out of the 18 documented cases in terms of output size of produced IFS (or columns of produced CAs respectively) and achieves the same size values in the other four. Especially, if we consider that in our experiments the main objective was to compare to the best bounds provided by greedy algorithms.

Table 3. Comparison of the amount of columns attained on N rows by different CA algorithms (larger is better). Information for the best lower bound for CAK (N ; t) where t = 3 is provided by Colbourn Tables [START_REF] Colbourn | Table for CAN(3,k,2) for k up to 10000[END_REF]. The superscripts denote the α-vector that was used as input for the computation that yields the output IFS, where a=(4,2), b= [START_REF] Forbes | Refining the inparameter-order strategy for constructing covering arrays[END_REF][START_REF] Colbourn | Table for CAN(3,k,2) for k up to 10000[END_REF], c= [START_REF] Gao | Balancing frequencies and fault detection in the in-parameter-order algorithm[END_REF][START_REF] Colbourn | Combinatorial aspects of covering arrays[END_REF], d= [START_REF] Kleitman | Families of k-independent sets[END_REF][START_REF] Colbourn | Handbook of combinatorial designs[END_REF]

Conclusion and Future Work

In this paper, we present a family of set-based algorithms for covering arrays, which can be regarded as abstract combinatorial test sets, based on independent families of sets. Our algorithmic design is modular thanks to a variety of building blocks which can give rise to even more algorithms than the ones presented. As a proof of concept of our approach we compared the implementations of the proposed family against state of the art greedy algorithms that are also used in practice for 3-way testing. This initial evaluation shows, that our approach improves significantly, in terms of size, over the existing greedy algorithm, which translates to smaller test sets. As future work, we plan to enhance the functionality of our algorithms via extending it to produce combinatorial test sets over non-binary alphabets as well as conduct more experiments for test sets that can be used for higher strength interaction testing.

Table 2 .

 2 Composition of the IFS-family algorithms.

	``````````B uilding blocks	Algorithm	IFS-origin	IFS-greedy IFS-score
	Store		F2	F2	F2
	Select		SelectRandom SelectNext SelectScore
	Admissible	Admissibleα Admissibleα Admissible
	Extend	Extend	Extend	Extend
	Update	Updateα	-	Update

Acknowledgments. This work has been funded by the Austrian Research Promotion Agency (FFG) under grant 851205 and the Austrian COMET Program (FFG).


David Leake

Case-Based Reasoning Tomorrow: Provenance, the Web, and Cases in the Future of Intelligent Information Processing

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

France;

  Chair for the 2003 International Conference on Intelligent User Interfaces (IUI 2003), Miami Beach, FL, U.S.A.; Short Paper and Demonstration Chair for the 2002 International Conference on Intelligent User Interfaces (IUI 2002), San Francisco, CA, U.S.A. Chair of the 1998 and 1999 Workshop Program of the AAAI National Conference on Artificial Intelligence and co-chair of the Second International Conference on Case-Based Reasoning (ICCBR-97). Program committee member for numerous international and national conferences.


Shusaku Tsumoto
email: tsumoto@med.shimane-u.ac.jp

Shoji Hirano
email: hirano@med.shimane-u.ac.jp

Hidenao Abe
email: abe@med.shimane-u.ac.jp

Automated Empirical Selection of Rule Induction Methods based on Recursive Iteration of Resampling Methods

One of the most important problems in rule induction methods is how to estimate which method is the best to use in an applied domain. While some methods are useful in some domains, they are not useful in other domains. Therefore it is very difficult to choose one of these methods. For this purpose, we introduce multiple testing based on recursive iteration of resampling methods for rule-induction (MULT-RECITE-R). We applied this MULT-RECITE-R method to monk datasets in UCI data repository. The results show that this method gives the best selection of estimation methods in almost the all cases.

Introduction

One of the most important problems in rule induction methods [START_REF] Clark | The CN2 Induction Algorithm[END_REF][START_REF] Michalski | A Theory and Methodology of Machine Learning[END_REF][START_REF] Michalski | The Multi-Purpose Incremental Learning System AQ15 and its Testing Application to Three Medical Domains[END_REF][START_REF] Quinlan | 5 -Programs for Machine Learning[END_REF] is how to estimate which method is the best to use in an applied domain. While some methods are useful in some domains, they are not useful in other domains. Therefore it is very difficult to choose one of these methods.

In order to solve this problem, we introduce multiple testing based on recursive iteration of resampling methods for rule induction methods (MULT-RECITE-R). MULT-RECITE-R consists of the following four procedures: First, it randomly splits training samples(S 0 ) into two parts, one for new training samples(S 1 ) and the other for new test samples(T 1 ) using a given resampling method(R). Second, S 1 are recursively split into training samples(S 2 ) and test samples(T 2 ) using the same resampling strategy(R). Then rule induction methods are applied to S 2 , results are tested and given metrics(S 2 metrics) are calculated by T 2 for each rule induction methods. This second procedure, as the inner loop, is repeated for finite times estimated from precision set by users and the statistics of metrics are obtained. Third, in the same way, rules are induced from S 1 and metrics(S 1 metrics) are calculated by T 1 for each rule induction methods. Then S 1 metrics are compared with S 2 metrics. If the difference between both results are not statistically significant, then it is counted as a success. The second and the third procedure, as the outer loop, are iterated for certain times estimated from precision preset by users, which gives a total success rate which shows how many times of total repetitions S 2 metrics predict S 1 metrics. Finally, fourth, the above results are interpreted in the following way. If a success rate is high, then this estimation method is expected to be well-performed, and the induction method which gives the best metric is selected as the most suitable induction method. If a success rate is low, then this estimation is expected not to be a good evaluation method. So a list of machine learning methods ordered by S 1 metrics is returned as an output.

We applied this MULT-RECITE-R method to monk datasets in UCI repository [START_REF] Murphy | UCI Repository of machine learning databases[END_REF]. The results show that this method gives the best selection of methods in almost the all cases.

The paper is organized as follows: Section 2 and 3 present the strategy of MULT-RECITE-R and its algorithm. Section 4 gives experimental results. Finally, we conclude this paper in Section 5.

Strategy of MULT-RECITE-R

There are many reports on rule induction methods and their performance in the community of machine learning [START_REF] Thrun | The Monk's Problems-A performance Comparison of Different Learning algorithms[END_REF]. However, since each performance is different in each paper, it is very difficult to determine which method should be selected.

Each of these methods has interesting characteristics of induced rules. For example, CN2 induces a decision list subsection, while ID3 calculate a decision tree. Strangely, comparison of these features of induced rules are used as secondary, because of the difficulties in evaluation, although classification accuracy or error rate are as the primary comparison index. However, as to classification accuracy, it is pointed out that these performances may depend on applied domains [START_REF] Schaffer | Overfitting Avoidance as Bias[END_REF][START_REF] Schaffer | Selecting a Classification Method by Cross-Validation[END_REF], although it is easy to apply statistical methods to testing significance. Actually, it is hard and controversial to determine what factor should be applied to evaluation of rule induction methods, which remains to be an open question in machine learning.

Since our objective is to develop a method which empirically selects rule induction methods, we use accuracy as a metric for statistical evaluation in this paper 1 .

The next important thing is that one may want to evaluate these rule induction methods without domain knowledge in case when domain-specific knowledge may not be applicable.

Therefore, since one of the most characteristics of resampling methods is that they are domain-independent [START_REF] Efron | An Introduction to the Bootstrap[END_REF][START_REF] Mclachlan | Discriminant Analysis and Statistical Pattern Recognition[END_REF][START_REF] Schaffer | Selecting a Classification Method by Cross-Validation[END_REF], one way for evaluation is to select one method from considerable resampling methods, that is to say, to select the best rule induction method by using subsets of training samples. For example, let us consider when we have training samples, say {1,2,3,4,5,6,7,8,9,10}. Then, first, they are split it into new training samples, say {1,3,5,7,9}, and new test samples, {2,4,6,8,10}. Using new training samples, rule induction methods are applied and the results are compared with the result by the new test samples.

Then the method which gives the best metric, such as the best classification rate, will be selected. For example, let the accuracy of the induced decision tree be equal to 0.97, and the accuracy of the rule to be equal to 0.82. Then induction of decision tree is selected as the best method. It may depend on splitting, so these procedures should be repeated for certain times, say 100 times. several statistics of the given metrics are calculated over these 100 trials, such as average, variance, and t-statistics.

In this method, we implicitly assume that the "matryoshka" principle should be true. That is, the best method for total population can be selected from original training samples, and the best method for original training samples can be estimated from training samples generated by resampling plans. Therefore, in terms of Section 2 and 3, a domain of both R 1 and R 2 is the best select method (R 1 (F 0 , F 1 ) R 2 (F 1 , F 2 ) = (the best method).)

An Algorithm for MULT-RECITE-R

An algorithm for MULT-RECITE-R can be described by embedding a rule induction method into the following algorithm based on a resampling scheme. ) and the other for new test samples(T 2 ) using the same resampling plan(R). Then perform the following subprocedures. 3-a) Induce rules from S 2 for each member of L.

INPUTS: S

3-b) Test induced results using T 2 and Calculate given metrics (S 2 metrics).

3-c) Repeat 3-b) and 3-c) for B in times. 3-d) Calculate statistics of S 2 metrics. 4) Apply all the rule induction methods to S 1 . Then execute the following procedures.

4-a) Test induced results by using T 1 and Calculate given metrics(S 1 metrics). 4-b) Compare S 1 metrics with S 2 metrics. If the best induction method j for S 1 metrics is the same as that of S 2 metrics, then Count this trial as a success on evaluation (succ j := succ j + 1). Otherwise, then Count it as a failure.

4-c) Test statistical significance between the best statistics of S 2 metrics and S 1 metrics using student t-test. If not significant, goto 5). Otherwise, Count this trial as a failure (p calc j := p calc j + 1). 5) Increment the counter (i := i + 1). If the counter is less than the upper bound(i < B out ), goto 2). If not, goto 6). 6) Calculate the overall success rate (SR := succ j /B out ). And calculate an ordered list of evaluation M 1 with the success rate succ j /B out of each member in L. 7) Calculate the overall adjusted p-value (p := p calc j /B out ). And calculate an ordered list of evaluation M 1 with the success rate p calc j /B out of each member in L. 8) Interpret the above results by the overall success rates. If a success rate is high, then this estimation method is expected to well-performed, and output the induction method j which gives the best metric is selected as the most suitable induction method (BI := j) and an ordered list M 1 . If a success rate is low, then this estimation is expected to be not a good evaluation method. Thus, only a list of machine learning methods ordered by S 1 metrics is returned as an output (BI := nil). 9) Interpret the above results by the overall adjusted-p values. If p < α, then this estimation method is expected to well-performed, and output the induction method j which gives the best metric is selected as the most suitable induction method (BI p := j) and an ordered list M 1 p. If p ≥ α, then this estimation is expected to be not a good evaluation method. Thus, only a list of machine learning methods ordered by S 1 metrics is returned as an output (BI p := nil).

Experimental Results

We applied this MULT-RECITE-R method to monk datasets in UCI repository [START_REF] Murphy | UCI Repository of machine learning databases[END_REF]. In these experiments, we set L r , L m α, α in and α out be equal to the same values as the above Monk's problems and set R to {2-fold cross-validation, the Bootstrap method}.

Unfortunately, in these databases, test samples are not given independently. So we first have to generate test samples from the original training samples. to evaluate our MULT-RECITE-R methods in the same way as evaluation shown in Section 3 . First, given samples are randomly split into training samples(S 0 ) and test samples(T 0 ). This T 0 correspond to test samples of Monk's problems, and S 0 correspond to training samples of Monks problems. Then MULT-RECITE-R method is applied to new training samples. This splitting procedure is repeated for 100 times in order for the effect of random sampling to be small. The above experimental results give us three interesting results, although all of the applied databases are of small size.

First, 2-fold repeated cross validation performs slightly better than the Bootstrap method, which corresponds to the characteristics derived by [START_REF] Efron | How biased is the apparent error rate of a prediction rule ?[END_REF][START_REF] Efron | An Introduction to the Bootstrap[END_REF]. Therefore, for predictive use, evaluation by cross-validation would be better, although the variance of estimation will be larger.

Second, the best selected method does not always perform better than other two methods. That is, in some generated samples, other methods will perform better. Finally, in the cases when MULT-RECITE-R does not go well, the differences of three rule induction methods in accuracy are not so significant. That is, we can select any of three methods, although the accuracy of each method is not so high.

Conclusion

One of the most important problems in rule induction methods is how to estimate which method is the best to used in an applied domain. For this purpose, we introduce multiple testing based on recursive iteration of resampling methods for rule-induction (MULT-RECITE-R). We apply this MULT-RECITE-R method to three original medical databases and seven UCI databases. The results show that this method gives the best selection of estimation methods in almost the all cases.

  Precision for statistical test α in : Precision for the Inner Loop α out : Precision for the Outer Loop L

	given resampling
	plan(R).
	3) Randomly split training samples(S 1 ) into two parts, one for new training
	samples(S 2

0 : Training Samples α: r : a List and Subprocedures of Rule Induction Methods L m : a List of Metrics R: Resampling Scheme OUTPUTS: BI: the Best Induction method selected by success rate M 1 : a List of Induction Methods ordered by success rates SR: Overall Success Rate BI p : the Best Induction method selected by adjusted-p Value M 1p : a List of Induction Methods ordered by adjusted-p Values SR p : Overall (Adjusted-)p Value 1) Set Counter to 0 (i := 0, succ := 0, p calc := 0). And set B in and B out to [10 -αin ] and [10 -αout ], respectively 2 . 2) Randomly split training samples(S 0 ) into two parts, one for new training samples(S 1 ) and the other for new test samples(T 1 ) using a

Table 1 .

 1 Results of S2 and S1 Metrics(Accuracy)

				S2 Metric
	Domain Samples C4.5	AQR	CN2
	Monk-1	62	84.3±1.5 90.2±0.9 92.0±1.8
	Monk-2	86	62.6±2.4 74.8±1.9 59.1±1.7
	Monk-3	62	87.7±1.4 82.5±1.3 84.8±0.9
				S1 Metric
	Domain Samples C4.5	AQR	CN2
	Monk-1 124	85.3±0.9 91.2±0.5 93.0±0.2
	Monk-2 169	66.7±1.3 75.8±0.7 60.1±0.8
	Monk-3 122 89.7±0.2 83.5±0.4 83.8±0.5

Table 2 .

 2 Success Rate (100 Trials)

		Overall
		Success Success Rate
	Domain Rate C4.5 AQR CN2
	Monk-1	94	9	12 73
	Monk-2	74	19 31 24
	Monk-3	90	79	6	5

Table 3 .

 3 Adjusted-p Value (100 Trials)

	Overall
	p-	Adjusted-p Value
	Domain Value C4.5 AQR CN2
	Monk-1 0.02 0.01 0.01 0.00
	Monk-2 0.10 0.04 0.02 0.04
	Monk-3 0.05 0.01 0.02 0.02

It is notable that our MULT-RECITE-R can be applied to any numeric metrics.

x denotes a maximum integer which do not exceed x. For example, 4.6 is equal to 4.


Thibaut Munzer

Marc Toussaint

Manuel Lopes

Preference Learning on the Execution of Collaborative Human-Robot Tasks

We present a novel method to learn human preferences during, and for, the execution of concurrent joint humanrobot tasks. We consider tasks realized by a team of a human operator and a robot helper that should adapt to the human's task execution preferences. Different human operators can have different abilities, experiences, and personal preferences, so that a particular allocation of activities in the team is preferred over another.

We cast the behavior of concurrent multi-agent cooperation as a semi Markov Decision Process and show how to model and learn human preferences over the team behavior. After proposing two different interactive learning algorithms, we evaluate them and show that the system can effectively learn and adapt to human preferences.

I. INTRODUCTION

Robotic technology is improving to the level that now we can have a close human-robot collaboration. This opens many new cobotic applications where people and robots work together in teams. In this context, robots can have simple repetitive behaviors and allow the user to adapt to them, or having reasoning capabilities that makes them true team members. A true collaboration involves shared decision making, mutual support, and easy ways to interact and express preferences.

In this work we want to explore such intuitive collaborations where the robot models the concurrent aspects of the shared task, and not just executes the task jointly with the user but also executes it in the way the user prefers. Such preferences are learned in an intuitive interaction loop.

We take this approach because to improve comfort, efficiency, acceptance, and reducing physical fatigue it should be the robot to learn and adapt to human preferences rather than the other way around. Such preferences are learned during task realization to avoid periods of task programming facilitating task switching.

Recent works have considered preference learning and learning from imitation, but mostly in the context of singleagent tasks. In this paper we propose different ways to learn the preferences over the execution of a collaborative task with concurrent actions. Our contributions include the following: i) a formalism to model team behavior using Relational Activity Processes (RAPs) [START_REF] Toussaint | Relational activity processes for modeling concurrent cooperation[END_REF]; ii) a formalism to represent preferences with standard MDP tools and iii) two different algorithms to learn preferences interactively. We show results in simulation and with a real robot. 1 Thibaut Munzer is with Inria, France 2 Marc Toussaint is with USTT, Germany 3 Manuel Lopes is with INESC-ID, Instituto Superior Técnico, Portugal manuel.lopes@tecnico.ulisboa.pt Fig. 1. The toolbox domain. A box can be assembled in a easier and efficient way if a collaborator robot helps by providing the new parts and by holding parts in place to make screwing easier for the user.

II. RELATED WORK

Research on learning from demonstration has included: i) low-level learning, where the goal is to learn a mapping from sensor output to motor command, e.g. learning motor policies [START_REF] Chernova | Interactive policy learning through confidence-based autonomy[END_REF] or navigation [START_REF] Bradley | Training a robot via human feedback: A case study[END_REF], [START_REF] Jain | Learning trajectory preferences for manipulators via iterative improvement[END_REF]; ii) symbolic learning, where the goal being is to learn a policy, a mapping from a symbolic space state to the space of actions [START_REF] Sriraam Natarajan | Imitation learning in relational domains: A functional-gradient boosting approach[END_REF] or learning rewards [START_REF] Munzer | Inverse reinforcement learning in relational domains[END_REF] from demonstration.

In most of those examples, there is a clear separation between the learning and the execution phase. This has several drawbacks as the number of demonstrations might be larger than needed, and might not even cover critical aspects of the task. To address such problems interactive scenarios where both phases are merged have been proposed. In [START_REF] Chernova | Interactive policy learning through confidence-based autonomy[END_REF], the robot only makes queries when, in a given state, the confidence on the actions passes a given threshold. Alternatively, in [START_REF] Lopes | Active learning for reward estimation in inverse reinforcement learning[END_REF], the system requests information about relevant states to learn a good reward representing the task. Other approaches provide a smooth transition between the phases, a first phase of teleoperation where the policy [START_REF] Daniel | Dogged learning for robots[END_REF], or the preference [START_REF] Mason | Robot self-initiative and personalization by learning through repeated interactions[END_REF], is learned and, at any time, the user can resume teleoperating to provide corrections.

A new trend of interactive learning systems is to rely on weak feedback to handle situations where optimal feedback is impossible or costly to produce by the human teacher. In particular, [START_REF] Shivaswamy | Online structured prediction via coactive learning[END_REF], [START_REF] Jain | Learning trajectory preferences for manipulators via iterative improvement[END_REF] relies on local improvements of the current policy while [START_REF] Akrour | Preference-based policy learning[END_REF] asks for ranking between two or more policies.

Another line of research considers not just learning individual tasks but also how to learn collaborative tasks. In [START_REF] Peternel | Teaching robots to cooperate with humans in dynamic manipulation tasks based on multi-modal human-in-the-loop approach[END_REF], the robot learn by demonstration how to collaborate with a human at a trajectory level. Several works have shown that learning the preferences of the human teammate has a positive impact on both cooperation and engagement of the user [START_REF] Kyung | Personalization in hri: A longitudinal field experiment[END_REF], [START_REF] Mitsunaga | Adapting robot behavior for human-robot interaction[END_REF].

If the preferences of the user are known then planning methods can be used to anticipate the needs of the user [START_REF] Hema | Anticipatory planning for human-robot teams[END_REF]. [START_REF] Nikolaidis | Efficient model learning for human-robot collaborative tasks[END_REF] show how to learn different profiles of user's preferences by clustering trajectories containing multiple types of execution. The preferences of the user are modeled as a hidden state of a POMDP allowing to adjust to the particular type of user in real time.

The concept of cross-training is explored in [START_REF] Nikolaidis | Human-robot cross-training: Computational formulation, modeling and evaluation of a human team training strategy[END_REF] where robot and the user simultaneously adapt to each other by switching roles. The robot learns directly a policy that better adapts to the user preferences. This improves team efficiency and acceptance metrics.

Our work is different from the previous research because we consider: i) how to learn interactively preferences in a collaborative setting; and ii) we learn preferences in a highlevel relational formalism with concurrent actions.

III. TEAM BEHAVIOR MODELING WITH RAPS

In this section we present the underlying formalism to model team behavior. We rely on a recently introduced general formalism for relational MDPs with concurrent actions [START_REF] Toussaint | Relational activity processes for modeling concurrent cooperation[END_REF], and show how to apply it to team behavior.

A. Relational MDPs

Markov Decision Processes (MDPs) are widely used to represent the decision process of an agent that can act in an environment. An MDP is a quadruplet (S, A, R, T ) with S the space of states, A the set of actions, R some reward function that the agent aims to maximize, and T the transition probability function that describes the dynamics of the world.

Relational MDPs generalize MDPs for high-level representations [START_REF] Džeroski | Relational reinforcement learning[END_REF]. Solutions to the planning and learning problems can be found in the literature [START_REF] Kersting | Bellman goes relational[END_REF], [START_REF] Lang | Planning with noisy probabilistic relational rules[END_REF]. Under this representation, the state of the environment is defined as the set of predicates (logical formulas) that are true. Actions, and the transition function, are represented as a set of rules that contain 3 parts, i) the action and its argument (action are predicates); ii) the states where such action can be applied, aka the context; and iii) the outcome or the final state.

Fig. 2 depicts how a Relational MDP may represent a domain where one can move blocks over each other.

B. Relational Activity Processes

For most formalisms for MDPs, only one action can be chosen at a given time. But in most cooperative tasks two agents perform actions at the same time. Other formalisms allow such flexibility but are not Markovian and so all the already known algorithms for task learning cannot be used.

A Relational Activity Processes (RAP), introduced in [START_REF] Toussaint | Relational activity processes for modeling concurrent cooperation[END_REF], is a way to model concurrent cooperation of multiple agents while being at the same time a Markovian process. Roughly, RAPs define a sequential MDP where decisions are about the initiation or termination of activities, and activities run concurrently with random durations.

Under the RAP formalism we consider a relational domain with a set of predicates. For a given set of objects or agents, the state is the conjunction of all true grounded predicates. Under RAP we augment the state with some predicates representing running activities. These predicates include a special real argument which parameterizes the expected timeto-go of the activity. The decision set contains the initiations of all activities that can be started in the current state and a special Wait decision after which the real time advances until the next activity ends and applies its termination effects change the state. In contrast, for the initiation and termination of activities real time does not advance.

C. Decentralized Team Decision Making

Using the RAP formalism we can model teams of cooperating agents, where all agents are embedded in the same semi-MDP and the decision space is the joint space of human decisions and robot decisions, D. Given a reward and using planning methods, for example Value Iteration, we can compute an optimal Q-function over the next decision d ∈ D in a given RAP state s. It provides values for decisions across agents. If there was a single central decision maker, it could read out the arg max d Q(d, s) and transmit the decision d to the agent it concerns. However, in real human-robot collaboration, without such a central decision maker, the readout and interpretation of this Q-function is non-trivial. With two decision makers, both might want to start an activity at the same time.

At team level, we transform this concurrent decision making into a sequential process. If both agents decide not to start a new activity the RAP wait decision is chosen. On the other hand, if the robot agent decides to engage an activity this is picked and transitions are applied. Human decisions can only be taken into account by the model when the robot decides not to start a new activity. This might come as a limitation but because all decisions except wait are instantaneous (as it is equivalent to start an activity), in practice, the human agent can engage a new activity at any time.

In the human-robot cooperation case we assume that the joint decision space decomposes as D = D R ∪D H and D R ∩ D H = {wait}, with D R the robot's and D H the human's decision space.

Given the robot has a representation of the shared task as a Q-function, we propose the following procedure for the robot to decide on its own activities. If max d∈D R Q(d, s) < max d∈D H Q(d, s), that is robot decisions have strictly less value than human decisions, the robot does not start an activity and lets the human act. Otherwise, the robot samples uniformly from the set of optimal robot decisions ⊆ D R .

IV. INTERACTIVE PREFERENCE LEARNING

In the previous section we showed a general formalism to describe cooperative concurrent tasks. Now we present our interactive preference learning formalism. We show how we can model preferences in a cooperative MDP and then how can we learn them from a database in a batch function and then how to learn them interactively.

For the batch process, we assume having access to a dataset of state-action pairs D = [(state i , decision i )] N i=0 of behavior from the team that reveals the human preferences.

A. Modeling Preferences

Given a task with different ways to solve it, i.e. different optimal paths in the RAP, preferences are defined as the preferred subset of these paths. The task can be seen as prior knowledge whereas preference is the learned behavior. In the extreme case where no prior knowledge is available this problem is reduced to learning from demonstration in an interactive setting.

More formally, under an MDP the task is defined by the reward, R task . Using Value Iteration, we can compute the optimal quality function Q * task . We can then represent the behavior of the team taking into account human preferences as another quality function

Q * f ull = Q * task +Q p ,
where Q p is a shaping function of the task optimal quality function such that Q * f ull maximizes task and human preference. In the following we will present two different methods to learn preferences.

B. Regression Based Preference Learning (RBPL)

The first method follows a typical approach of policy matching where we learn a function that directly represents the policy. We can see Q f ull as the policy because we can directly compute a policy from a quality function either by argmax or using some soft version like a Boltzmann policy.

With the decomposition we performed between task and preferences we can match the observed policy using the following process. For every state in D we want to reduce the quality of decisions not taken by the expert human-robot team, and increase the quality of decision taken.

For this we augment the dataset D and create a dataset D f where for every couple (state, decision) in D, for every decision e in D we add ((state, e), 0) if e = decision or ((state, e), -1) otherwise to D f .

We have now cast the learning problem as a regression problem. We can then rely on a relational regression tree such as the ones presented in [START_REF] Blockeel | Top-down induction of first-order logical decision trees[END_REF] to learn the function Q p from D f . Such method have been shown to be successful in the context of learning individual policies in relational domains [START_REF] Munzer | Inverse reinforcement learning in relational domains[END_REF].

A relational tree follows a similar idea of typical decision trees but each node is a logical query on a given predicate. Several regularization methods can be used, a simple one is to limit the depth of the tree.

Algorithm 1 RBPL 1: procedure RBPL(Q * task , D) 2: D f ← build regression dataset(D) 3: Q p ← learn regression tree(D f ) 4: return Q * task + Q p C. Gradient Based Preference Learning (GBPL)
The second idea follows a gradient based approach. In this case we do not have a set of parameters to optimize, and we rely on relational trees to learn functions. As such, we can not use classical gradient methods that work on parameters, but instead rely on functional gradient boosting where the gradient is computed on the space of functions. By defining a smooth mapping between policies and quality functions (we use a Boltzman mapping), it is possible to compute the values of functional gradient of the log-likelihood of the dataset D with respect to Q * task for every data point in D. Using relational regression tree, we can learn the functional gradient, Q i , that generalize gradient value to unseen data. By iterating this process, as presented in Alg. 2, we can learn the function Q * f ull such that it maximizes the log-likelihood of the dataset D. This algorithm is analog to using the TBRIL algorithm [START_REF] Sriraam Natarajan | Imitation learning in relational domains: A functional-gradient boosting approach[END_REF] initialized with Q * task .

Algorithm 2

GBPL 1: procedure GBPL(Q * task , D, nb iter) 2: Q * f ull ← Q * task 3:
for i ∈ [0, ..., nb iter] do 4:

D g ← compute gradient(Q * f ull , D) 5:
Q i ← learn regression tree(D g ) 6:

Q * f ull ← Q * f ull + Q i 7: return Q * f ull

D. Interactive setting

In the interactive setting, we use a similar approach. We initialize Q p to Q p (s, d) = 0. The robot takes decisions following the procedure describe above. So, in practice, the robot follow Q * task during the first task realization. After each decision taken (start human activity, start robot activity or wait) we update D. Two cases are possible:

• The decision is correct, we add (state, decision) to the dataset, with decision the robot decision • the decision is incorrect, we add (state, decision) to the dataset, with decision a correct decision (given by the human as feedback). Once the task is completed, we relearn Q * f ull by one of the two ways above and the interactions continue to solve the task again, starting from a new state.

Because we modify the policy it can happen that the robot starts an activity that doesn't respect the preferences of the user or even that are not optimal with respect to the task. In some contexts, it might not be possible to recover from such error. This is the reason for another approach where we allow the robot to ask before doing an activity. We call this setup ask-before-act. Because this changes the MDP trajectories, it impacts the trajectory of learning. Both scenarios are shown in Fig. 3.

V. SIMULATIONS

A. Domains

We test our system in two domains: the blocksworld because it allows to easily change its dimension, and a more realistic cooperative human-robot assembling task for which we have a real robotic setup.

1) Concurrent blocksworld: This domain extends the standard blocksworld by allowing two activities to be executed at the same time. Blocks can be put on top of each other or on a surface (called floor) by a robot and by a human. Unless otherwise specified we use 5 blocks (2 red and 3 blue blocks).

The domain is represented with the predicates: on/2, clear/1, busy/1, in hand/2, blue/1 and red/1. The activities are pick(agent, block) and put(agent, block, block), both of them last one unit of time and both of them can be realized by either the robot or the human.

The goal of the task is to stack all blocks in one tower. Starting states are generated by first sampling the number of initial towers between 4 and 5 and then uniformly select one state that respects the total number of towers. We enforce that no activities are active in the start state.

Even in such a simple domain we can imagine different user preferences. For instance one user might have a preference for a color, or for building the tower by alternating the actions with the robot. We first consider that the user dislikes picking blue blocks. Under such preference the task must be solved in a way that minimizes the number of blue blocks picked by the human while keeping an optimal policy with respect to the task.

2) Cooperative toolbox: The cooperative toolbox domain is inspired by industrial tasks. In this domain, represented in Fig. 1, a robot must support a human in the assembly of a toolbox. The toolbox is constituted by five pieces: handle, side left, side right, side front and side back. The toolbox can be built in different ways, the side left and side right are interchangeable as well as side front and side back.

At the beginning of the task, all pieces are set on a location not accessible by the human. The robot has to realize consecutively two activities to put them in the human workspace : pick(piece) and give(piece). Once the human has the pieces in his workspace he can start a positioning activity to put them in a correct disposition for screwing. Simultaneously, the robot should hold one of the pieces in order to allow the human to screw them together. Hold activity is done with the right arm of the robot whereas pick and give are done with the left arm so the robot can do different activities at the same time (which can be naturally represented with the RAP formalism). Because the box have different possible combinations, this domain has 240, 000 states.

In this domain, the task is to build the toolbox. Again we can imagine different ways to assembly the box that can be preferred by different people. For instance positioning everything and then screw, or positioning and screw one piece at a time. For the simulations we consider that the user likes to have an uncluttered workspace and so be given new parts as late as possible.

B. Results

To evaluate the proposed methods, we use three metrics. First, the accumulated preference reward gathered that measures if the robot found a policy that allows the users to execute the task in their preferred way. Second we count the number of errors: an error is made when a non optimal activity with respect to the task and preferences is realized, to evaluate the cost of learning the policy interactively. And third the number of human feedback needed to learn the preferences. We use this measure a a proxy-measure for the cognitive cost of teaching the preferences on the task. These metrics are divided by the number of times the task has been solved to obtain regret-like metrics. We could evaluate the learning offline (run a number of simulation after each learning episodes) but as we are interested in designing an online system we focus our efforts on online performance. These measures allow us to study the compromise between the number of instruction and the number of errors.

1) Comparison of RBPL and GBPL: In Fig. 4 we compare the results of the RBPL and GBPL approaches on both domains. We can see that both approaches perform well on the toolbox domain. After 10 episodes the mean number of errors is close to zero and the accumulated preferences reward is close to the optimal. In the blocksworld domain the GBPL approach performs better in the long term.

We explain the difference of performance on the two domains by the complexity of the function to be learned. In the blockworlds, the function must be more generic because of the different possible starting states. The Q p function has to generalize in order for the agent to perform well. In that Both methods are able to learn to fulfill the task while respecting the user preferences. In this case, the number of feedback is equivalent to the number of error and is not displayed. Shaded area represent standard error of the mean. case, the gradient approach is more adapted as it can learn more complex model. On the toolbox domain, however, the starting state is always the same, and only local modifications of Q * task are needed in order learn correctly the preferences. 2) Ask-before-act: Fig. 5 presents the number of feedback needed by the system to learn the user's preferences in the toolbox and blocksworld domains. We can see that for both domains ask-before-act leads to better results as the number of feedback decrease earlier. The system makes no mistakes and therefore the dataset D contain only states on the optimal RAP trajectories. This makes the learning task easier as Q p must be learned for a smaller part of its input space. For the blocksworld, as the learned function must generalize, the impact is less significant.

For the toolbox domain, the number of feedback is inferior at the beginning in the ask-before-act condition whereas it is the opposite for the blocksworld domain. In the first domain making a mistake with respect to preferences will lead to states where more mistakes can be made. In the second Fig. 5. Number of feedback for blocks domain (top) and toolbox domain (bottom). For ask-before-act the number of errors and the preference reward is equivalent to the optimal and is not displayed. Shaded area represent standard error of the mean. domain, it is the opposite, if the robot picks a red block, most of the time, no more mistakes can be made.

3) Noise robustness: We now evaluate the impact of noise in the human feedback. We imagine that the human does not correct the robot every time. This creates a noisy learning scenario as wrong decisions will sometimes not be corrected by the human. It results in a dataset D where suboptimal decisions are present.

As Fig. 6 shows, even with noise equal to 0.4 (40% of wrong robot decisions that are not corrected) both approaches still manage to learn the human preferences. We observe that the number of feedback given in noisy setup becomes higher after only five episodes indicating that not always giving feedback is not a good strategy if one goal is to minimize the number of feedback given.

4) Transfer: We also evaluate the transfer capabilities of the learn policy. In the blocks world domain, a red block is added to the domain after 50 episodes.

Results reported in Fig. 7 indicate that when learned preferences are transfered, the learning is faster than when preferences are relearned from scratch. After only 10 episodes asymptotic performances are reached. We conclude that preferences can indeed be transfered from one domain to another.

VI. ROBOTIC EXPERIMENT : COOPERATIVE TOOLBOX

ASSEMBLY

We now present an experiment of a joint human robot task realized with a user and the Baxter robot. This experiment uses the toolbox domain (Fig. 8) and consist in building the toolbox following a specific plan. In particular the user prefers having an uncluttered workspace while following this order for assembly: Fig. 6. Impact of the noise on the feedback in learning the task in the blocks domain. With noise up to 40% it is possible to learn the task. The standard error of the mean is not displayed for readability reasons. Fig. 7. Evaluation of the impact of changing the number of blocks during the task (at step 50). We can see that both approaches allow to transfer between domain sizes and learn faster than starting from scratch. In this case, the number of feedback is equivalent to the number of error and is not displayed. Shaded area represent standard error of the mean. 1) attach handle and side right 2) attach handle and side left 3) attach side right and side front 4) attach side left and side front 5) attach side left and side back 6) attach side right and side back During the first three episodes the starting state stays the same with all the pieces not in the human workspace. For the fourth episode the side front starts already in the human workspace.

The perception system relies on Optitrack cameras for object tracking. Based on this information, we compute the truth values of the domain predicates for any objects. The system is also programmed to recognize the different activities.

Using an algorithm on a real robot is always more challenging than in simulation. The list of additional difficulties includes: an imperfect perception system and a model not conform with the reality. The imperfect perception system leads to predicates wrongly detected as true as well as the other way around (for example, because of occlusion). Having an algorithm robust to noise helps coping with that. The mismatch of the model from the reality leads to making decision on states that are not predicted by the model. The presented algorithms allow learning what to do in those cases.

In this experiment, we use a hybrid strategy mixing the ask-before-act and the normal strategies. By applying the learning algorithm on different subsets of the dataset we can estimate the potential error (or confidence) of the predicted optimal decision. If the potential error is over a threshold, we use ask-before-act, otherwise the robot directly acts.

To compute the potential error, we learn 25 times on random subsets composed of 75% of the dataset. For every possible decision we compute the potential error as the mean over every learner of the difference between the predicted quality and the maximum predicted quality (by this learner). The predicted decision is the one with the lower associated potential error. Based on the previous results, we use the GBPL algorithm as it has shown better performances. The results are presented in Fig. 9. We can see that the algorithm allows the system to significantly reduce the number of feedback after only one assembly. A feedback is given when the robot suggest a non preferred activity. So, a decrease in the number of feedback shows the robot correctly learned the user preferences. We also observe that the system is able to generalize to the new starting state in the forth assembly with a number of feedback of 5 as opposed to 19 for the first assembly. The bottom graph displays that the number of use of the interface decrease with the number of assembly. Which means that the robot is capable of correctly estimating its confidence. The video of the whole learning process can be found at https://vimeo.com/182913540. In this experiment the decision to stop the holding activity is hardcoded based on the screwdriver position. Because the system fail to detect correctly the screwdriver at around 2 minutes in the video, the robot stops holing prematurely.

VII. CONCLUSION

In this work we present an approach to learn preferences interactively during concurrent human-robot collaboration. In our setting the robot simultaneously executes the task and learns how the user prefers to execute it. Our main contribution is to consider such preference learning in an interactive and concurrent multi-agent action setting.

Our first contribution is to show how preferences can be efficiently encoded at the team behavior level using concurrent relational actions processes.

We then compared two preference learning methods where the team solves a shared task. These methods are prone to be used either in a batch or interactive setting. We showed results in a large dimensional domain, and a real robotic scenario, showing that these methods are able to execute the task while simultaneously learning which different ways of execution is preferred by the user.

We also showed how robust our approach is for intradomain transfer and noise. We showed that we could change the dimension of the problem and still reuse parts of the information to learn fast. And, we showed that even is there is some noise in the feedback the system is able to learn.

Fig. 2 .

 2 Fig. 2.Sketch of a Relational MDP representation of a blocksworld domain. The state is defined as a set of predicates, upon performing a relational action, the state, i.e. the true predicates change.

Fig. 3 .

 3 Fig. 3. Representation of the interactive process used by the robot to learn the preferences of its human teammate.

Fig. 4 .

 4 Fig. 4. Comparison of RBPL and GBPL on blocks domain (top) and toolbox domain (bottom).Both methods are able to learn to fulfill the task while respecting the user preferences. In this case, the number of feedback is equivalent to the number of error and is not displayed. Shaded area represent standard error of the mean.

Fig. 8 .

 8 Fig. 8. Execution of a joint human robot task while learning the user preferences.

Fig. 9 .

 9 Fig. 9. Number of feedbacks (top) and number of uses of the interface (bottom) during four consecutive assemblies of the toolbox with a real robot. For the forth assembly, a different starting state is used. A decrease in the number of feedbacks shows the robot correctly learned the user preferences

ACKNOWLEDGMENT

This work was supported by national funds through Fundac ¸ão para a Ciência e a Tecnologia (FCT) with reference UID/CEC/50021/2013 and by the EU FP7-ICT project 3rdHand under grant agreement no 610878