Martin Schoeberl

Benjamin Rouxel
email: benjamin.rouxel@irisa.fr

Isabelle Puaut
email: isabelle.puaut@irisa.fr

A Time-predictable Branch Predictor

Keywords: •Computer systems organization → Embedded systems, Embedded systems, real-time systems, worst-case execution time

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

is then considered just a performance reduction. However, this is not appropriate for real-time systems for which we need to model processor features for their worst-case behavior.

In a branch predictor that is optimized for the average case, two branches might map to the same entry in the branch prediction table and con ict with each other at run-time. In the average case this is just annoying and a possible reduction of performance. For real-time systems, con icts are a considerable issue as the aim is to have safe and tight WCET bounds.

is paper presents a branch predictor especially designed to enable tight WCET analysis.

e predictor consists of a fullyassociative prediction table that includes the full address of the branch as tag memory. erefore, no two branches can share one entry. With that fully-associative table we can use a simple scopebased WCET analysis to determine if all branches at some program scope t into the branch prediction table. When all branches t into the branch prediction table, we can model each loop exit branch individually for this scope. Basically, a er the rst iteration of a loop, the loop exit branch will be predicted correctly for the remaining iterations of the loop (except the loop exit at the last iteration).

We have implemented the branch predictor in hardware in an FPGA to explore the feasibility of using a fully-associative table. Besides storing the branch address as tag memory, the table also contains the branch target address. erefore, a correctly predicted branch is executed in a single cycle independent of being taken or not. We have integrated the model of this branch predictor and the scope-based analysis in the WCET analysis tool Heptane [START_REF] Hardy | e Heptane Static Worst-Case Execution Time Estimation Tool[END_REF]. We consider this as one example of co-design of time-predictable hardware with WCET analysis.

e hardware implementation shows that a fully-associative table is feasible for up to 64 entries. In that case, the hardware consumption is about 20 % of a Patmos RISC style processor. When connecting the branch predictor to the Patmos processor it is, not even with 128 entries, dominating the (hardware) critical path.

Results from this WCET analysis on Mälardalen and Polybench benchmarks show that the proposed predictor never results in worse WCET bounds than the initial Patmos static branch predictor. Results also show that depending on the loop shapes generated by the compiler, the gap between the two predictors di er a lot (much higher for do-while loops than for for loops, for which the gain is negligible). Results also show that so ware-emulated oating point operations introduce a lot of spurious branches that call for a larger branch prediction table than hardware-supported integer operations.

A number of WCET-oriented analyses of branch predictors have been designed in the past [START_REF] Bate | Worst-Case Execution Time Analysis for Dynamic Branch Predictors[END_REF][START_REF] Burguiere | A contribution to branch prediction modeling in WCET analysis[END_REF][START_REF] Colin | Worst Case Execution Time Analysis for a Processor with Branch Prediction[END_REF][START_REF] Grund | Branch target bu ers: WCET analysis framework and timing predictability[END_REF][START_REF] Maiza | A framework for the timing analysis of dynamic branch predictors[END_REF][START_REF] Mitra | A Framework to Model Branch Prediction for Worst Case Execution Time Analysis[END_REF][START_REF] Pu | E cient Worst-Case Execution Time Analysis of Dynamic Branch Prediction[END_REF]. ese works aim at analyzing existing predictors, designed for the average-case. In contrast to these works, the proposed predictor is designed with predictability in mind, and is co-designed with the associated analysis.

e main contributions of this paper are:

• the design of a time-predictable branch predictor,

• the co-designed static scope-based analysis, by cooperation between di erent research domains, • experimental evaluation of the hardware cost of the proposed predictor, • experimental evaluation of the reduction of WCET bounds using the proposed predictor compared to basic static branch prediction, and analysis of the impact of loop shapes on the reduction.

is paper is organized as follows. Section 2 surveys related work. Section 3 describes the proposed time-predictable branch predictor and its di erent variations. Section 4 presents the associated scopebased static WCET analysis technique. Section 5 analyzes the worstcase behavior of the proposed branch predictor. Finally, Section 6 concludes and gives directions for future work.

BACKGROUND AND RELATED WORK

Branch prediction techniques help performing control ow speculation by predicting the outcome of branch instructions. If the prediction is correct, then execution proceeds without interruption, whereas for incorrect predictions, the speculatively executed instructions have to be cancelled, incurring a time penalty. If branch prediction is not modeled, WCET estimation tools must conservatively assume that all branches are mispredicted, resulting in overestimations.

Branch prediction can be either static or dynamic. Static scheme associate a xed prediction for every branch (e.g. backward edges always assumed taken, or compiler-guided). Dynamic predictors predict the branch outcome dynamically based on the past execution history. e rst dynamic technique proposed is called local branch prediction. is scheme uses a branch prediction table indexed by the lower bits of the program counter. Each entry contains a k-bit saturated counter representing the last predictions. Global schemes exploit correlation between branches. Global schemes use a single shi register, called branch history register to record the outcomes of n most recent branches. As in local schemes, there is a global branch prediction table in which the predictions are stored.

e various global schemes di er from each other in the way the prediction table is looked up when a branch is encountered.

Static branch predictors are easy to analyze. However, for compilerdirected static prediction, the compiler has to statically determine the direction of the branch to be predicted to minimize WCET estimates (see [START_REF] Franc ¸ois Bodin | A WCET-Oriented Static Branch Prediction Scheme for Real Time Systems[END_REF][START_REF] Burguiere | A Case for Static Branch Prediction in Real-Time Systems[END_REF]). In addition, the performance of static predictors like backward taken, forward not taken are highly in uenced by the compiler code generation, raising the issue of code generation, in particular basic block re-ordering, for obtaining as low as possible WCET estimates [START_REF] Plazar | WCETdriven branch prediction aware code positioning[END_REF].

Dynamic branch predictors are less predictable and harder to analyze than static branch predictors, as observed in [START_REF] Engblom | Analysis of the execution time unpredictability caused by dynamic branch prediction[END_REF] and [START_REF] Colin | Experimental evaluation of code properties for wcet analysis[END_REF]. For dynamic cases, the analysis has to determine both if there is a hit in the prediction table and the actual contents of the prediction table.

e rst work was on local dynamic branch predictors [START_REF] Colin | Worst Case Execution Time Analysis for a Processor with Branch Prediction[END_REF]. Static analysis of dynamic branch predictors were proposed in [START_REF] Bate | Worst-Case Execution Time Analysis for Dynamic Branch Predictors[END_REF][START_REF] Mitra | A Framework to Model Branch Prediction for Worst Case Execution Time Analysis[END_REF], with some restrictions to keep the analysis tractable: absence of con icts in the prediction table for [START_REF] Bate | Worst-Case Execution Time Analysis for Dynamic Branch Predictors[END_REF], consideration of con icts in [START_REF] Mitra | A Framework to Model Branch Prediction for Worst Case Execution Time Analysis[END_REF], but only one bit counters to keep the analysis complexity low. Compared to the above-mentioned studies, the main contribution of the work presented in [START_REF] Burguiere | A contribution to branch prediction modeling in WCET analysis[END_REF] is a precise modeling of misprediction penalties, that depend on the direction of the branches. e work presented in [START_REF] Maiza | A framework for the timing analysis of dynamic branch predictors[END_REF] releases these restrictions through the provision of a framework for the analysis of a large set of global branch predictors used in embedded processors. Experimental results using this framework however show that the complexity of models can be signi cant, in particular when increasing the number of bits in the prediction table or the branch history length. A framework for the static analyses of branch target bu ers was presented in [START_REF] Grund | Branch target bu ers: WCET analysis framework and timing predictability[END_REF].

eir analyses are based on abstract interpretation, and are shown to be able to successfully analyze a panel of non trivial branch target bu ers. More recently, a technique to support longer branch history length was proposed in [START_REF] Pu | E cient Worst-Case Execution Time Analysis of Dynamic Branch Prediction[END_REF] at the price of reasonable loss of precision.

In this study, in contrast to existing works whose objective is to analyze increasingly complex dynamic branch predictors, originally designed for the average-case, our focus is on the design of a simple and easy to analyze branch predictor, optimized for the worst-case.

BRANCH PREDICTION DESIGN 3.1 Hardware Assumptions

For the rest of the paper we assume a classic RISC style processor with 5 pipeline stages: fetch, decode, execute, memory, and writeback. Figure 1 shows such a pipeline organization, already with a branch prediction unit a ached. In that pipeline each instruction has a total latency of 5 clock cycles, but due to pipelining (if there are no stalls) each instruction takes e ectively one clock cycle. e added branch predictor is shown as BP1, BP2, and BP3, as it spans the rst three pipeline stages.

We consider conditional branches, simply called branches for the rest of the paper, where the condition is a comparison between two register values. It is also common to encode branch targets as o sets from the current address, which is held in the program counter (PC).

A branch instruction may be split into three di erent steps: (1) evaluate the condition, (2) compute the branch target, and (3) change the program ow to the branch target if the branch is taken. A branch instruction is fetched in the rst stage. In the decode stage, besides decoding the branch instruction, the two register values used to evaluate the branch condition are loaded from the register le and the branch target address is computed. In the execution stage, the branch condition is computed. If evaluated to true, the target address is loaded into the PC. If the condition evaluates to false, the pipeline continues to execute in program order.

While the branch instruction moves through the pipeline, the following sequential instructions are fetched and decoded. If the branch is taken, the following instructions are replaced by a bubble (nop instructions). is behavior results in di erent execution times for a branch if taken or not. If not taken, it is only one clock cycle; if taken, it is three clock cycles in our example pipeline. is behavior is also called statically predict not-taken. When the branch instruction reaches the execution stage, the branch outcome is compared with the prediction. When it is di erent from the prediction, branch predictor ushes the two instructions in the pipeline, sets the PC to the correct target, and updates the branch history table. Using more than one bit for prediction can add some hysteresis to the predictor to avoid changing the prediction back and forth when executing an inner loop several times. Besides estimating if a branch is taken or not, the branch target address needs to be computed as well. In a standard 5-stage RISC pipeline this can be performed in the decode or execution stage.

erefore, even on a correctly predicted branch a taken branch takes two clock cycles. erefore, a branch history table can be extended to also include the target address of a taken branch. 1 Again, if two di erent branches map to the same entry in the table, a branch might branch to a wrong destination. is can be detected in the execution stage and corrected. is results also in "just" a performance penalty.

A Time-predictable Branch Predictor

In contrast to the classic predictor presented above, the base idea here is to build a branch predictor that is an easy target for WCET analysis. Existing predictors use a prediction table without tags, thus di erent branches can alias to the same entry. In case of aliasing, the predicted outcome of the branch is wrong, but this only hurts performance. For WCET analysis, aliasing is a source of pessimism when estimating the worst-case outcome of branches (if two branches map to the same entry, the analysis has to consider the worst-case situation). Moreover, detecting the presence of aliasing is a complex and time consuming task. erefore, our predictor will tag each entry in the prediction table. Furthermore, to avoid 1 All target addresses of every branch are known at compile time con ict misses we aim at a high associativity (for the scope of this paper the prediction table will be fully-associative).

In its default con guration, the proposed branch predictor will use a branch target bu er (BTB) that is fully-associative, and stores in each entry:

• the address of the branch instruction in the tag memory, to avoid aliasing; • the branch target address; and • the branch outcome estimation (as one bit or as a two-bit saturating counter).

e BTB stores all conditional branches, and the replacement policy for the BTB is FIFO2 (First-In First-Out). As the BTB contains a tag entry for the branch, aliasing of two di erent branches is completely avoided. Unconditional branches are not stored in the BTB. In the following, the term branch refers to conditional branches only.

Branch prediction is performed at the fetch stage, by looking for the current PC in the BTB. In case of a miss in the BTB (meaning the instruction is not a branch or the branch is not yet in the BTB), the pipeline proceeds normally (i.e. the pipeline proceeds with the next instructions in sequence). In case of a hit, the branch history bits and the branch target address are used to determine if and where to branch. In case the prediction bits outcome is taken, then the pipeline is lled at the fetch stage with the branch target address, else the pipeline proceeds normally.

On a miss in the BTB, the BTB is updated for a branch instruction in the execution stage. e execution stage also checks if the prediction was correct, updates the BTB accordingly, and triggers a fetch from the correct address if the prediction was wrong.

Variations

3.4.1 1-bit history. In this variation, the BTB stores a history of one bit used to predict the direction of a branch when found in the BTB (predict not taken (NT) if zero, predict taken (T) if one). e prediction bit is ipped in case of wrong prediction, as depicted below.

Predict NT 0

Predict T 1

Taken (T)

Not Taken (NT) NT T 3.4.2 2-bits history. is second variation uses a 2-bits history to predict the outcome of every branch, as depicted below. When the history bits are 00 or 01 (respectively 10 and 11) the branch is predicted not taken (respectively taken).

TIMING ANALYSIS

e proposed branch predictor allows a scope-based WCET analysis. Assuming properly nested loops, the analysis for each loop determines if all branches belonging to the loop scope are guaranteed to stay in the BTB, in order to determine the number of correctly predicted loop exit instructions.

e analysis is aware of loop nesting to provide tight estimates, and supports elaborate models of misprediction penalties.

Assumptions and Notations

Our analysis applies to programs amenable to static WCET analysis (see Section 5.1 for the exact restrictions imposed by the static WCET estimation tool used in the experimental evaluation). e branch prediction analysis needs properly nested loops. Di erent shapes of loops are supported, according to the following three criteria on the conditional test to exit the loop:

• test executed before or a er the loop body;

• test branches outside or inside the loop;

• test located at an address immediately before or not immediately before the start of the loop body.

e analysis is detailed for the following two loop shapes, described below and depicted in Figure 2. ese two loop shapes are representative of the most common cases found in compiled code.

e analysis implementation supports all loop shapes corresponding to any combination of loop shape criteria. e following notations are used in the analysis description:

• f req exec l is the loop bound of loop l (maximum number of times the body is executed). e conditional branch is thus executed f req exec l times for loop shape 1 (Figure 2a), and f req exec l + 1 for loop shape 2 (Figure 2b). e bound is local (it counts the maximum number of iterations for each entry in the loop, not the cumulated value for all entries). • e scope of a loop, scope(l), is de ned as the number of distinct branches inside the loop, plus the loop conditional branch itself. By de nition it includes all branches contained in functions called (directly or indirectly) from the loop body.

• antecedents(l) refers to all loops including l until the outermost one (all direct and indirect parents, considering function calls). • Maximum total number of times loop l is entered/exited:

η l = Π p ∈ant ecedent s(l ) f req exec p
• Maximum total number of entries into the loop l guaranteed to t in the BTB:

δ l = (Π p ∈ant ecedent s(l )|scope(p)≤BT B f req exec p )
ese de nitions hold for all considered loop shapes. e analysis provides for the conditional branch of every loop l the total number of times the branch falls into the categories listed in Table 1. In the text of the analysis, the categorization of a branch is a pair (X,Y), with X the prediction (miss, good, bad) and Y the actual branch direction (T,NT ). e corresponding number of occurrences in each category is denoted n Y X . For example, n T ood denotes the number of times a branch is predicted taken and is actually taken at runtime. is categorization of branches is ne grain, to allow precise modeling of misprediction penalties such as in [START_REF] Burguiere | A contribution to branch prediction modeling in WCET analysis[END_REF]. Note that our analysis currently focuses on loop exit branches, leaving the analysis of the other conditional branches for future work. We herea er detail the analysis for loop shape 1 and 2. For space considerations, we only give detailed description of the analysis for loop shape 1 (Figure 2a) and do not describe all the details for the other loop shape.

Analysis for Loop Shape from Figure 2a

For this loop shape, the branching behavior for each execution of loop l is T … T (repeated f req exec l -1 times) NT. is pa ern T … T NT is repeated several times when l is included in other loops.

For a given loop l, the number of times the branch is correctly predicted or mispredicted depends on how many branches in the loop scope are guaranteed to t in the BTB, as de ned by scope(l).

4.2.1 Case 1: branches are not guaranteed to fit inside the BTB. If scope(l) > BT B, branches executed in the scope of loop l are not guaranteed to stay in the BTB once loaded. However, we can guarantee a BTB miss only for loop l once. is is because there may exist conditional branches that are not loop branches (i.e. conditional constructs) whose execution depends on input data, making it hard to ensure that a loop branch is always evicted from the BTB.

With the loop shape we are focusing on (see Figure 2a), the very rst entry of the loop conditional branch is taken, and results in a BTB miss. It is thus categorized as (miss,T). e following iterations, last iterations excluded, are also taken. Since it cannot be guaranteed that the loop branch for these iterations is evicted from the BTB, the most pessimistic situation has to be considered. Assuming that a misprediction is the worst-case, the following iterations are then conservatively considered mispredicted (category (bad,T)).

en each last iteration of the loop are not-taken and thus predicted correctly (category (good,NT)).

e number of occurrences in each category is then as follows (only non zero counts are listed from now on):

• n T miss = 1 • n N T ood = η l • n T bad = (f req exec l -1) * η l -1 4.2.
2 Case 2: branches are guaranteed to fit in the BTB. When scope(l) ≤ BT B, it means that all branches in the scope of the loop stay in the BTB a er rst loaded. In the following, we give for the two branch predictor con gurations:

•

e categorization for all rst executions of the loop (the rst iteration of a loop might be executed several times in the presence of loop nesting), • e categorization of the next iterations of the loop (last iteration excluded), • e categorization of the last iterations of the loop.

e analysis is detailed for the two variations of the predictor (1-bit history and 2-bit history).

Con guration with 1-bit history.

• First iterations. Apart from the very rst entry in the loop, which is a BTB miss, all entries are mispredictions (category (bad,T)). For the δ l entries that, by de nition of δ l , stay in the BTB once loaded, the prediction bit is 0, because the last prediction for the branch (last iteration) was T and the actual outcome was NT. us the prediction bit was ipped to 0 and the entry is mispredicted (category (bad,T)). For the η l -δ l that are not guaranteed to stay in the BTB, the branches are conservatively classi ed as mispredicted, resulting in a the category (bad,T) (it cannot be guaranteed they stay in the BTB, and cannot be guaranteed to be evicted from the BTB).

• Next (f req exec l -2) * η l iterations. For these branches, the prediction bit is 1 (predicted T) and the branch is T. us they are predicted correctly (category (good,T)). • Last iterations (executed η l times). e prediction bit is 1 (T) and the branch is not taken, thus a misprediction and a change of the prediction bit to 0 (category (bad,NT)).

• Total:

-

n T miss = 1 -n T bad = η l -1 -n N T bad = η l -n T ood = (f req exec l -2) * η l
Con guration with 2-bit history.

• First iterations. Similarly to the 1-bit history predictor, the η l -δ l that are not guaranteed to stay in the BTB are conservatively classi ed as mispredicted (category (bad,T)).

Regarding the δ l executions that stay in the BTB across executions of the loop, the 2-bit history now allows all of them to be correctly predicted (category (good,T)), because the previous branch to exit the loop changed the prediction bits from 11 to 10. When re-entering the loop again, the prediction is T and the branch is T . • Next (f req exec l -2) * η l iterations. e prediction bits are 11 (predict T) and the branch is T, the prediction is therefore correct (category (good,T)). • Last iterations (executed η l times). e prediction bits are 11 (predict T) and the branch is NT, thus the branches are mispredicted (category (bad,NT)).

• Total:

-

n T miss = 1 -n N T bad = η l -n T bad = η l -δ l -1 -n T ood = δ l + (f req exec l -2) * η l

Analysis for Loop Shape from Figure 2b

For this loop shape, the branching behavior for each entry of loop l is NT … NT (repeated f req exec l times) T. is pa ern NT … NT T is repeated when l is included in outer loops. Similarly to the other loop shape, the result of the analysis depends on whether or not the BTB is big enough to store the loops branches.

4.

3.1 Case 1: branches are not guaranteed to fit inside the BTB. If the scope is larger that the BTB, for all the two variations (1-bit history and 2-bit history) we have:

• n N T miss = 1 • n T bad = η l • n N T bad = (f req exec l ) * η l -1 4.3.
2 Case 2: branches are guaranteed to fit in BTB. In case the scope ts in the BTB, we have, for 1-bit history (details omi ed for space consideration):

• n N T miss = 1 • n T bad = 2 * η l -1 • n N T ood = (f req exec l -1
) * η l en, for a 2-bits history we have:

• n N T miss = 1 • n T bad = η l • n N T bad = η l -δ l -1 • n N T ood = δ l + (f req exec l -1) * η l

WCET Calculation with IPET

e classical IPET (Implicit Path Enumeration Technique [START_REF] Li | Performance analysis of embedded so ware using implicit path enumeration[END_REF]) formulation computes WCET estimates using an Integer Linear Programming (ILP). IPET re ects the program structure and the possible execution ows using a set of linear constraints. An upper bound of the program's WCET is obtained by maximizing the objective function i ∈Basic Blocks T i * f i . T i is the timing information of basic block i, that integrates the e ects of micro-architecture. Frequency f i , a variable in the ILP system, to be instantiated by the ILP solver, corresponds to the number of times basic block i is executed along (one of) the longest path(s). A value of 0 means that the block is not on the critical path.

We have extended IPET to include the timing penalties of branch prediction (gains if the penalty is negative) by adding a binary variable isex l to the basic block l containing the loop branch. isex l is set to 0 if the node is not on the critical path (if f l = 0), and 1 if it is (if f l 0).

To model this if-then-else scenario in ILP (isex l = 0 if f l = 0), there exist several ways depending on the used solver. For example, with IBM CPLEX we can use indicator constraints (see equation ( 1)) whereas in the open-source LPSolve solver we can use a Big-M notation (see equation [START_REF] Bate | Worst-Case Execution Time Analysis for Dynamic Branch Predictors[END_REF]). e choice of a BigM value might be di cult as this value must be bigger than any other integer in the system to solve. One could choose the maximum integer the solving computer can deal with. In our experiments (see details in Section 5.1), we use CPLEX with the indicator constraints.

∀l ∈ loopbranches; isex l = 0 → f l = 0 (1) ∀l ∈ loopbranches; 0 × isnotex l + 1 × isex l ≤ f l ≤ 1 × isnotex l + Bi M × isex l (2)
A new term is then added to the objective function, representing the penalty for each loop branch l, according to the branch classication from Table 1. Let us denote by t Y X the penalty corresponding to the branch category (X,Y), with X the prediction (miss, good, bad) and the actual branch direction (T, NT ). e new term added is:

n Y X × t Y X × isex l Logic cells

EXPERIMENTAL EVALUATION

is paper has presented a co-designed solution for time-predictable branch prediction with (a) a hardware design optimized for WCET analysis and (b) a WCET analysis speci c for this hardware design.

is section includes an evaluation of our design through a comparison of WCETs for the proposed branch predictors with other hardware designs (a static backward taken forward not taken predictor and the static predictor of the Patmos processor [START_REF] Schoeberl | Patmos Reference Handbook[END_REF][START_REF] Schoeberl | Towards a Timepredictable Dual-Issue Microprocessor: e Patmos Approach[END_REF]). We voluntarily do not include any more complex branch predictor, because state-of-the-art branch predictors are not designed for predictability and therefore are hard to analyze statically. Experiments were performed on standard WCET benchmarks from the Mälardalen benchmark suite [START_REF]WCET Benchmarks[END_REF] and Polybench benchmark suite.

Experimental Setup

Hardware Implementation. We have implemented the proposed branch predictor targeting the Patmos processor [START_REF] Schoeberl | Patmos Reference Handbook[END_REF][START_REF] Schoeberl | Patmos: A Time-predictable Microprocessor[END_REF]. For the implementation, we use the hardware construction language Chisel [START_REF] Bachrach | Chisel: constructing hardware in a Scala embedded language[END_REF]. Chisel allows to generate a C++ based tester and Verilog code for synthesis. Besides the branch predictor we implemented a simulation of the rst three stages of RISC style processor pipeline (fetch, decode, and execute) to drive the branch predictor. e simpli ed processor simulation serves as a testbed for functional veri cation of the branch predictor. e simpli ed pipeline is also synthesizable and we report on resource consumption and maximum clock frequency when targeting an FPGA.

We are interested in how expensive the fully-associative, single cycle lookup is. When an entry matching the current PC is found, the result may update the PC, depending on the branch prediction.

erefore, the critical path starts from the PC register output, is fanned out to n comperators for an associativity of n, the comperator outputs are then encoded to nd one possible match, and an n port multiplexer gives the result, which may update the PC register. As we aim for a single cycle branch predictor, this operation cannot be pipelined. Furthermore, as we aim for a fully-associative table, the table needs to be implemented in dedicated registers instead of an on-chip memory.

We have synthesized the branch predictor for an Altera/Intel Cyclon IV FPGA with the artus Prime 16.1 Light edition. Table 2 shows the result of the resource consumption (logic cells, registers) and the maximum clocking frequency, for di erent con gurations.

e last row shows for a comparison the resource consumption 3: Gain in % over a "pessimistic predictor" with Mälardalen benchmark suite and a 16 entries BTB (loop shape 1) Table 3: Modi cation of branch timing as compared to predict not taken Branch taken Branch not taken BTB miss 2 0 BTB hit, predict taken -2 2 BTB hit, predict not taken 2 0

and maximum frequency of a Patmos processor. e results show that single cycle lookup BTB with up to 128 entries can be implemented. However the larger the BTB, the higher the branch prediction hardware cost comparatively to the base Patmos processor. A fully-associative BTB with 16 entries is used by default in the experimental evaluation. Patmos implements the classic 5-stages pipeline and includes by default the static branch predictor (statically predict not-taken) described in Section 3.1. According to the structure of the Patmos pipeline, the timing penalties of branches for the proposed branch predictor as compared to the Patmos static predictor are given in Table 3. Compilation and WCET Analysis. e analyzed programs were compiled with LLVM for the Patmos processor [START_REF] Puschner | Compiling for Time Predictability[END_REF]. the programs were compiled with no optimization (compiler option -O0), except the -loop-rotate ag for half of the experiments, that allow to have, when the optimization is applicable, the exit test of loops executed a er the loop body. A default optimization level of -O0 is used for two main reasons. First, optimizing code is not current practice in safety critical domain, because compilers have to be certi ed, and compiler optimizations make certi cation complex if the compiler implements aggressive optimization passes [START_REF] Leroy | Formal veri cation of a realistic compiler[END_REF]. Second, WCET estimation requires loop bounds to be known, and loop bounds are easier to estimate at source code level (either using static analysis or provided through annotations). Many optimizations change loop bounds, requiring traceability of loop bounds within the compiler when bounds are given at the source code level [START_REF] Li | Traceability of Flow Information: Reconciling Compiler Optimizations and WCET Estimation[END_REF]. Optimizationloop-rotate has impact on the shape of loops, transforming almost all loops of shape 1 (Figure 2a) to shape 2 (Figure 2b) without changing the loop bound (except the -1 required in a do-while construct).

We have implemented the scope-based analysis in the Heptane static WCET estimation tool [START_REF] Hardy | e Heptane Static Worst-Case Execution Time Estimation Tool[END_REF]. Heptane, like most static WCET analysis tools, imposes a set of constraints on code: no function pointers, no indirect jumps through jump tables, a single entry per loop.

Heptane was modi ed to support the Patmos instruction set. e analysis of the micro-architecture of Patmos in Heptane being incomplete at the time this paper is wri en, it is assumed that the Patmos pipeline and memory hierarchy is e cient enough to execute an instruction every clock cycle. Loop bounds are given through annotations.

Experimental Results

Results

for loop shape 1 from Figure 2a. Figures 3 and4 present the gain in percentage on the WCET when using the two variations of the proposed branch predictor, as compared with a pessimistic predictor for which all branches are systematically assumed mispredicted (penalty of 2 cycles per branch). e higher the gain, the be er the predictor. ree baselines are used to evaluate the quality of our design:

(1) Perfect branch prediction (noted perfect in the gure) (2) e Patmos original static branch predictor described in Section 3.1 (statically predict not-taken) [START_REF] Franc ¸ois Bodin | A WCET-Oriented Static Branch Prediction Scheme for Real Time Systems[END_REF] e simple backward taken, forward not taken static branch predictor (BTFNT in the gures). For this predictor, we added a delay of 1 clock cycle per conditional branch, required to know if the instruction is a branch, to compute the branch address, and to detect the branch direction. is knowledge is available at the decode stage only.

Results show that in general WCETs estimates when using the proposed branch predictors are smaller than with the default Patmos predictor. Compared to BTFNT, the proposed predictors are sometimes be er, sometimes worse; our predictors have a more regular behavior than BTFNT.

One can notice that in some benchmarks from the Mälardalen benchmark suite, branch prediction does result in any improvement. e cause of this behavior is the small number of iterations in many of these benchmarks (for example 3 in minver). In this situation, the cost of the initial BTB miss (or misprediction when re-entering the same loop several times) outweights the gains when re-executing the branch again a too small number of times.

e proposed branch predictor performs be er on the Polybench benchmarks than on the Mädardalen benchmarks. is comes from the Polybench benchmarks have loops with a much larger number of iterations than in the Mälardalen benchmarks. Having loops with large loop bounds makes the prediction close to perfect branch prediction, since misses and mispredictions are paid only at startup and when entering a loop several times in the application lifetime; all the branches in the large number of iterations are predicted correctly.

e 2-bit history con guration results in almost all situations in smaller WCET estimates than when using 1-bit history. is is because when exiting a loop inside a loop nest, the prediction is correct when re-entering the loop again (provided that all branches t in the BTB). ere are however some exceptions, when the 1-bit history outperforms the 2-bit history (Mälardalen benchmark bcall). In this benchmark, there is no loop nest (one single loop in the code, iterating 30 times). ere is one extra misprediction for the 2-bit counter con guration, because the counter needs two iterations to reach state "predict taken" (one more than the 1-bit history con guration). In other terms, the 2-bit predictor takes longer to warm-up than the 1-bit predictor. e number of loop iterations being moderate, and the cost of a misprediction being larger than the gain for a correct prediction, the impact on the WCET is noticeable.

Figures 5 and6 give a di erent view of the same set of experiments, by showing now the absolute number of mispredictions (the lower the be er). Since the percentage of mispredicted branches is low as compared to the pessimistic baseline, the gures are presented using a logarithmic scale. One can notice that some benchmarks from the Mälardalen benchmark suite have a low estimated Figure 8: Gain in % over a "pessimistic predictor" with Polybench benchmark suite and a 16 entries BTB (loop shape 2) number of mispredictions (minmax, insertsort). is comes from two factors: (i) these benchmarks do not contain nested loops, thus once the predictor is warmed-up, it will always issue correct predictions; (ii) BTB misses are not depicted in the gure, only branch mispredictions.

e results show that, although the number of mispredictions from Figure 4 looked low, there are actually a non negligible number of mispredictions for the Polybench benchmarks. However, since these benchmarks are compute-intensive (the WCET is dominated by calculations, not by branches) the impact of misprediction on WCETs is limited.

Results

for loop shape 2 from Figure 2b. is second set of experiments is again for a BTB with 16 entries, but now operates on loops with mostly the second loop shape. Figures 7 and8 depict the WCETs for the Mälardalen and Polybench benchmarks respectively. e results show that for this loop shape the di erence of gain of the proposed predictors as compared to the Patmos default prediction exists but is small. is comes from the conjunction of two factors: (i) the shape of loops in the benchmarks (mostly for loops, almost no do while loop); (ii) the code generated by default by the compiler, that makes Patmos original predictor perform well in the worst-case.

5.2.3

Experiments for floating point values. In the above experiments, the Polybench benchmarks were con gured to operate on integer values. We performed the same set of experiments when con guring them with precision oating point values. Since in Patmos oating point operations are emulated in so ware, we observed an increase of the number of branches per loop, caused by the oating point emulation functions. e loop scopes were signi cantly increased, requiring a larger BTB to bene t from the branch predictor. I.e., 64 entries in the BTB are required to reach similar gains than using integer values.

CONCLUSION

is paper has presented a time-predictable branch predictor codesigned with the associated worst-case execution time analysis.

e branch predictor uses a fully-associative cache to track conditional branch outcomes and destination addresses. e prediction table entries are tagged with the branch address to avoid false sharing of entries between branches. e design of the branch predictor allows the de nition of a simple scope-based static analysis of the branch predictor. Experimental results show that although the design of the predictor and analysis are simple in order to be predictable, the impact of the branch predictor on worst-case execution time bounds is positive, specially for the predictor with a 2-bit history. However, we noticed that the bene t brought by the predictor highly depends on the code generated by the compiler.

As future work, one direction is to make our analysis more precise by identifying the branches that are guaranteed to be evicted from the branch predictor in a loop. Another extension of the work is to study the impact of di erent structures for the branch predictor table (set-associative instead of fully-associative) on misprediction rates and worst-case execution time bounds.

Figure 4 :

 4 Figure 4: Gain in % over a "pessimistic predictor" with Polybench benchmark suite and a 16 entries BTB (loop shape 1)

Figure 5 :

 5 Figure 5: Number of mispredictions with Mälardalen benchmark suite and a 16 entries BTB -logarithmic scale (loop shape 1)

Figure 6 :

 6 Figure 6: Number of mispredictions Polybench benchmark suite and a 16 entries BTB -logarithmic scale (loop shape 1)

Figure 7 :

 7 Figure 7: Gain in % over a "pessimistic predictor" with Mälardalen benchmark suite and a 16 entries BTB (loop shape 2)

•

  Figure 2a: conditional test executed a er the loop body, branching inside the loop, conditional test not immediately before the loop body; • Figure 2b: conditional test executed before the loop body, branching outside the loop, conditional test immediately before the loop body.

Table 1 :

 1 Notations for prediction outcome categories

	(a) Loop shape 1: test a er body,	(b) Loop shape 2: test before
	branch inside, test not immedi-	body, branch outside, test not im-
	ately before body	mediately before body
	Figure 2: Considered loop shapes
	Branch taken Branch not taken
	BTB miss BTB hit, predict taken BTB hit, predict not taken	n T miss n T ood n T bad	n N T miss n N T bad n N T ood

Table 2 :

 2 Resource consumption and maximum frequency for di erent branch predictor con gurations.

	Registers	Fmax

e analysis presented in this paper is not limited to a BTB using FIFO replacement. It applies to any replacement policy for which the following property holds: if the BTB contains X ≤ N values, with N the BTB size, no access to one of the X values will evict any of them (all values will stay in the BTB).

Acknowledgment

e work presented in this paper was partially funded by the Danish Council for Independent Research | Technology and Production Sciences under the project PREDICT 3 contract no. 4184-00127A.


Kerstin Dautenhahn
email: k.dautenhahn@herts.ac.uk

Michael Walters

Sarah Woods

Kheng Lee Koay

Emrah Christopher L Nehaniv

Akin Sisbot
email: emrah.akin.sisbot@laas.fr

Rachid Alami

Thierry Simeon

E A Sisbot

T Siméon

How May I Serve You? A Robot Companion Approaching a Seated Person in a Helping Context

Keywords: A.m [Miscellaneous]: Human Robot Interaction -Social Robots I.2.9 [Artificial Intelligence]: Robotics -Mobile robots Human Factors, Human-robot interaction, social robot, social spaces, personal spaces, user trials, live interactions

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

INTRODUCTION

If robots are to be used in office and domestic environments, they will have to encounter and interact with people. They must survive and carry out tasks in a disordered and unpredictable environment, safely and effectively. This paper presents the results from Human Robot Interaction (HRI) trials carried out at the University of Hertfordshire (UH). These results have then been used to inform and guide work carried out at the Laboratory for Analysis and

Architecture of Systems at the Centre National de la Recherche Scientifique (LAAS-CNRS), to develop a task planning, motion planning, and control system that incorporates human social factors and preferences.

The work presented in this paper contributes to the COGNIRON Project [2005]. Part of this research into a cognitive robot companion investigates socially interactive robots [START_REF] Fong | A survey of socially interactive robots[END_REF] from a human-centred perspective, i.e. how robots could be useful in domestic environments; in particular the roles, tasks, and social behaviour(s) that will be necessary for robots to exhibit in order to integrate into everyday domestic situations. In order to study human-robot relationships, HRI trials using carefully devised test scenarios are conducted [START_REF] Walters | Practical and methodological challenges in designing and conducting interaction studies with human subjects[END_REF], where human responses and opinions can be collected using a variety of methods. A number of previous live HRI trials with human scaled PeopleBot TM robots have been carried out [START_REF] Dautenhahn | What is a robot companion -Friend, assistant or butler?[END_REF][START_REF] Boekhorst | A study of a single robot interacting with groups of children in a rotation game scenario[END_REF][START_REF] Walters | The influence of subjects' personality traits on personal spatial zones in a human-robot interaction experiment[END_REF][START_REF] Walters | Close encounters: Spatial distances between people and a robot of mechanistic appearance[END_REF]. Other researchers have also investigated similar HRI trials with human sized robots including Dario et al. [START_REF] Dario | Humanoids and personal robots: Design and experiments[END_REF], Severinson-Eklundh et al. [START_REF] Severinson-Eklundh | Social and collaborative aspects of interaction with a service robot[END_REF], Kanda et al. [START_REF] Kanda | Interactive robots as social partners and peer tutors for children: A field trial[END_REF] and Hinds et al. [START_REF] Hinds | Whose job is it A study of human-robot interaction in a collaborative task[END_REF].

Once the desired behaviour(s) for sociable robots capable of competent human-robot interactions are known, the challenge is then to incorporate the results into mobile robot path planning algorithms and control systems. At LAAS-CNRS progress has been made towards a motion planning framework that will allow the implementation of key criteria and parameters that can incorporate these results into the control system of a mobile robot that can be applied to human-centred environments. The presence of humans raises new issues for motion planning and control since the human's safety and comfort must be taken into account. The claim here is that a human-aware motion planner must not only consider safe robot paths, but also plan good, socially acceptable and legible paths.

There are a number of contributions in the literature where humans and robots co-exist in the same environment. These studies have frequently focussed only on the safety of the human [START_REF] Bicci | Fast and soft arm tactics: Dealing with the safety-performance trade-off in robot arms design and control[END_REF][START_REF] Kulic | Safe Planning for Human-Robot Interaction[END_REF][START_REF] Kulic | Strategies for safety in humanrobot interaction[END_REF][START_REF] Zim | Playing it safe (human friendly robots)[END_REF] and have failed to take human comfort into account. The planner presented here explicitly takes into account the human partners' safety and comfort by reasoning about accessibility, visual field, posture, gaze direction, relative distance to the robot and potential shared motions. Although several authors have proposed motion planning or reactive schemes with a consideration for humans, there is no contribution that has tackled this whole problem.

2.

The Live HRI Trials

This section presents results from two live HRI trials. First, a human-robot interaction demonstration trial event, which was run as part of an informal evening event at the AISB'05 Convention held at University of Hertfordshire in April 2005, and secondly, follow-up trials carried out in a controlled laboratory set-up, to retest the results gained from the demonstration trial.

The HRI Trial Method

The trials were both carried out in converted seminar rooms where the scenario involved a robot using three different approach directions (front, left and right) to bring a seated subject an object (a TV remote control). The main aim of both trials was to establish subjects' preferences for the different robot approach directions. The demonstration event was conducted as part of an evening of entertainment for convention delegates, and involved different robot demonstrations. Spectators were present during the trials which were performed under non-laboratory conditions using 38 volunteers from the convention. The follow up study was carried out under controlled conditions with 15 subjects, and one of the main aims of this trial was to re-test the results obtained from the informal study.

The Trial Areas

The trial set-up was virtually identical for both trials and resembled a simulated living room with a chair and two tables. The subject was seated in the chair, which was positioned halfway along the rear wall (point (9), Fig. 1), throughout the trial. To the left front, and right front of the chair, two tables were arranged (with room for the robot to pass by) in front of the chair. One of the tables had a television placed upon it; the other had a CD Radio unit. The robot was driven under direct remote control to the appropriate start position by an operator, but the robot's approaches to the subject were fully autonomous. The operator was seated at a table in the far corner of the room. Subjects were told that the robot would be controlled by the operator while it was driven to the three start positions, but would be approaching them autonomously to bring them the TV remote control. This was reinforced as the operator made notes and did not press any of the robot control keys (on the robot control laptop) while it approached the subject (Figure 1). The robot carried the remote control in a small basket suspended between the fingers of the lifting gripper. The remote control was placed in the basket prior to each experimental run. For each approach trial, the subject took the remote from the basket then replaced it ready for the next approach.

The HRI Trial Scenario

The same scenario was used for both HRI trials, introduced by the experiment supervisor. The context explained to the subjects was as follows: the subject had arrived home, tired after a long day at work and rested in an armchair (point (9), Fig. 1). After looking around for the TV remote control, the subject then asked the robot to fetch it for them as they were too tired to get up. The robot then brought the remote control to the subject. It was explained to the subject that the robot was new to the household and it was necessary to find out which approach direction the subject preferred; either from the front (2), the left (1) or the right (3). The three possible paths taken by the robot are shown in Fig. 1. In order to justify the scenario of the robot fetching the remote control, one of the tables had a (switched off) TV set upon it. The other table had a CD-Radio unit. Our expectations prior to the trials were that subjects would prefer the approach from the front, since the robot was then fully visible at all times. Since many subjects, in particular in the demonstration trial, had never seen the robot before we assumed that they would feel most secure, comfortable, and 'in control' when the robot was fully visible so that its behaviour could be monitored easily.

Experimental Conditions

We were aware that the TV might be a natural focus of subjects' attention and may have influenced the choice of preferred robot approach direction. Therefore, for the controlled lab condition, half the trials were carried out with the TV on the left hand table, and the other half with the TV on the right hand table. Each subject experienced the robot approaching from three directions: front, left and right. To avoid any order effects, a counterbalanced order sequence covering all six possible permutations of the three robot approach directions was used. For the demonstration event, subjects experienced each approach direction only once, and for the controlled follow-up trials, each subject experienced the three robot approach directions twice, in a counterbalanced order.

Subject Sample Sets:

For the demonstration trial, 21 males (54%) and No subjects had previous exposure to the robots used in the trial. In the demonstration trial, some subjects had not sat straight in the chair (see Fig. 2). In the follow-up study subjects were made to sit straight with their feet to the front of the chair.

Procedure

For both trials, subjects completed a short introductory questionnaire to gain the necessary consent, and demographic details. At the end of each trial a semi-structured questionnaire was used to assess subject attitudes and preferences for the different robot approach directions and approach speed, as well as practicality issues. The questionnaires used for the follow-up trials were more extensive and included questions about the robot stopping distances, comfort levels and practicality for the different approach directions, rated according to a 5-point Likert scale. Subjects also participated in a semi-structured interview after the follow-up trial. The interview was carefully designed to eliminate leading questions. The main purpose of the structured interview was to assess subjects' views about the trial procedures and methodology, and find out how the trial could be improved from the participants' point of view. The subjects' reactions to both HRI trials were recorded by a single tripod mounted camera placed at an appropriate point at either ( 5) or [START_REF] Dautenhahn | What is a robot companion -Friend, assistant or butler?[END_REF] in Fig. 1. Figure 4 illustrates that 60% (N: 23) of subjects stated that they preferred the right robot approach direction, followed by 24% (N: 9) preferring the left approach and just 16% (N: 6) preferring the front approach. An overriding majority of subjects stated that they least preferred the frontal robot approach direction (N: 31, 80%). Very few subjects least preferred the left and right approach directions.

Demonstration Trial Results

Overall Approach Direction Preferences:

Gender Differences & Approach Direction Preferences

Figure 5. Male and female approach direction preferences

Chi-square cross-tabulations revealed a significant trend between gender and the preferred robot approach direction (X 2 (2, 38) = 3.77, p = 0.1). More females stated that they preferred the front robot approach direction compared to males, and more males preferred the right robot approach direction compared to females (see Figure 5). A significant relationship was found between gender and least preferred robot approach direction (X 2 (2, 39) = 7.09, p = 0.03). Significantly more males stated that they least preferred the front robot approach direction compared to females (males: 95%, females: 61%). More females stated that they least preferred the right robot approach direction compared to males (males: 0%, females: 11%).

Age, Handedness, and Approach Direction Preferences

Chi-square cross-tabulations revealed no significant relationships between age, handedness and approach directions preferred and least preferred.

Approach Distance

76% (N: 28) of subjects stated that the distance between them and the robot (0.5m ±0.1m) was 'about right', followed by 19% (N: 7) who felt that the robot was to 'too far' from them. Only 5% (N: 2) of subjects stated that the robot approached them too closely.

Practicality of Approach Directions

In addition to subjects rating which robot approach direction they preferred, ratings were given for how 'practical' they thought each approach direction was for the given task of delivering a TV remote control, according to a 5-point Likert scale (1 = not practical at all to 5 = very practical). A Friedman test for ordinal data illustrated that the rankings for approach direction practicality were significantly different from each other (X 2 (39, 2) = 12.11, p < 0.01). The mean rankings indicated that the front approach direction (mean ranking = 1.63) was rated as the least practical, and the right approach the most practical (mean ranking = 2.33), followed by the left (mean ranking = 2.04) approach direction.

Comfort Ratings of Approach Directions

Subjects were asked to rate how comfortable they felt with the different robot approach directions trials according to a 5-point Likert scale (1 = very uncomfortable, 5 = very comfortable). A Friedman test showed that the comfort level rankings for approach directions were significantly different from each other (X 2 (39, 2) = 29.38, p < 0.001). The mean rankings highlighted that subjects were the least comfortable with the front (mean ranking = 1.37) robot approach direction, and the most comfortable with the right approach direction (mean ranking = 2.49), followed by the left (mean ranking = 2.14).

2.3

Follow-Up Trial Results Results of the follow-up approach direction robot trials under laboratory conditions clearly demonstrated that the least preferred approach direction was the front approach. The right approach direction was the most preferred. These results are highly consistent, with the demonstration trial results (Figure 6).

Approach directions most and least preferred

Robot Distance from the Subject

For the robot's front approach direction stopping distance, 53% (N = 8) of subjects rated that the robot's stopping distance was too close. 27% (N = 4) of subjects rated that the robot's stopping distance was about right, and 20% rated that robot's stopping distance was too far. These results seem to indicate that a near majority of subjects rated that the front approach stopping distance was too close. In the case of subjects who rated the stopping distance as being too far for the front approach, we observed that these subjects usually had their legs stretched out in front of them causing the robot to stop when it reached the subject's feet rather than their arm for them to reach the TV remote control (due to the robot's stopping safety mechanism which had to be operational due to safety considerations). During the robot's approach from the left direction, 80% (N = 12) stated that the stopping distance was about right and 20% (N = 3) rated the stopping distance as being too far. During the robot's approach from the right of the subject 60% (N = 9) of subjects rated the stopping distance as about right, 40% (N = 6) rated it as too far. It is interesting to note that no subjects thought the robot approached too closely from either left or right approach directions.

Robot's Speed during the Trial

The robots final approach speed to the subject was approximately 0.4 to 0.25 m/s, but was not finely controlled due to the inbuilt safety speed limiting mechanism. When subjects were asked to rate the robot's approach speed, 60% (N: 7) of participants rated that the speed was about right, and 40% (N: 6) of subjects rated that the robot's speed was too slow. None of the subjects rated that the robot's speed was too fast during the trials.

Practicality and Comfort of the different Robot Approach Directions

The front approach direction received the lowest practicality ratings for both the live and video trials. The right approach direction received the highest ratings of practicality followed by the left approach. The lowest mean comfort levels were found for the front robot approach direction. The highest comfort level rating was found for the right approach direction followed by the left approach direction. No significant differences were found between most preferred approach direction and least preferred approach direction for gender, subject handedness (whether subject was left or right handed), and occupation.

Combined Results of Demonstration & Follow-Up Trials

In light of the comparable HRI trial methodologies and the high degree of agreement between the results from the informal demonstration trials and formal follow-up trials, the results from both trials were combined to form one dataset from the 55 subjects who participated in both trials. Thirty males (56%) and 24 females (44%) in total participated in the robot approach direction trials. The mean age of subjects was 36 years (range: 21-58, SD: 11.54). Forty nine subjects (94%) were right handed, and 3 subjects (6%) were left handed. Figure 7 illustrates that 59% (N: 31) of subjects stated preferring the right robot approach direction, followed by 28% (N: 15) who preferred the left approach, and just 13% (N: 7) preferred the front approach. An overriding majority of subjects stated least preferring the front robot approach direction (N: 43, 80%). Few subjects least preferred the left and right approach directions.

Trial Preferences:

Practicality of Approach Directions

A Friedman test for ordinal data illustrated that the rankings for approach direction practicality were significantly different from each other (X 2 (54, 2) = 21.87, p < 0.001). The mean rankings indicate that the front approach direction (mean ranking = 1.55) was rated as the least practical, and that the right approach was the most practical (mean ranking = 2.34), followed by the left (mean ranking = 2.11) approach direction.

Comfort Ratings of the Approach Directions

Results from a Friedman test showed that the comfort level rankings for approach directions were significantly different from each other (X 2 (54, 2) = 47.78, p < 0.001). The mean rankings highlight that subjects were the least comfortable with the front (mean ranking = 2.43) robot approach direction, and the most comfortable with the right approach direction (mean ranking = 4.15), followed by the left (mean ranking = 3.76).

Gender Differences

Chi-square cross-tabulations revealed a significant association between gender and the robot approach direction preferred (X 2 (2, 53) = 5.83, p = 0.05). More females stated preferring the robot front approach direction compared to males, and more males preferred the right robot approach direction compared to females (See Figure 8). A small significant relationship was found between gender and least preferred robot approach direction (X 2 (2, 54) = 5.72, p = 0.06). More males stated least preferring the front robot approach direction compared to females (males: 90%, females: 67%). More females stated least preferring the left (males: 10%, females: 21%) and right robot approach direction compared to males (males: 0%, females: 13%). Independent measures t-tests revealed a trend for males (M = 4.37) to rate the right robot approach direction as more comfortable compared to females (M = 3.88) (t (52) = 1.74, p = 0.08). No further significant gender differences were revealed for comfort ratings of the front and left robot approach directions. Independent measures t-tests were calculated to examine gender differences and ratings of the practicality of the robot approach directions. Significant differences were found for the practicality of the front approach direction (t (52) = -2.46, p = 0.02). Females rated the front approach direction as significantly more practical compared to males (males M = 2.60, females M = 3.38). No further significant differences were found between gender and practicality ratings for the left and right approach directions.

Age, Handedness, and Approach Direction Preferences

Chi-square cross-tabulations revealed no significant relationships between age, handedness, approach directions most and least preferred, comfort ratings of the approach directions, and practicality ratings of the approach directions.

Comments made by Subjects about the Three Robot Approach Directions.

Subjects were asked to provide details about the reasons for preferring and least preferring particular robot approach directions. The most frequently cited comments are provided in tables 1 and 2.1

Table 1. Reasons why subjects preferred a particular approach direction.

Preferred Front Approach Direction Front approach direction was easy to reach for the TV remote control The effort needed to reach for the remote control was the least, but this was still not close enough Preferred Left Approach Direction I felt the most relaxed and comfortable during this approach Preferred this approach as I am left handed This approach was the quickest and most direct This approach felt the most natural It was the most convenient for the robot to approach this way.

Preferred Right Approach Direction I felt the most comfortable with this approach This approach seemed the most natural I am right handed, so it was the easiest way to take the remote control This approach seemed to be the quickest This approach because it was always in my field of vision Table 2. Reasons why subjects least preferred a particular approach direction.

Least Preferred Front Approach Direction I had to move forward to reach for the remote control, the robot was too far away from me This approach was slightly threatening This approach was just a little bit too close for comfort Seemed too aggressive The robot was always looking a me I was concerned about the robot running into me during this approach This approach was intimidating Least Preferred Left Approach Direction Didn't like left approach as I am right handed It was difficult for me to reach for the remote control I felt awkward reaching across with me left hand It felt like I had to reach further for the left approach The robot was not in my line of vision during the left approach Least Preferred Right Approach Direction Least preferred this approach because I am left handed The robot felt like it was behind my back during this approach

Implications of User Studies for Robot Motion Planning

Today, classical motion planning methods [START_REF] Latombe | Robot motion planning[END_REF] are quite efficient at locating feasible paths. However, the presence of humans in the environment drastically changes the notion of acceptable paths. In a human-robot interaction context, the computed paths do not only need to be collision-free but must also take into account human comfort. This is illustrated in figure 9, which shows two paths produced by a classical motion planner. Both paths are inconvenient since one path passes too close to the wall, causing the human to be surprised, and the other passes behind the human resulting in discomfort. The HRI studies reported in the previous section, and others [1, 13, and 19] highlight a number of properties that must be taken into account when dealing with humans. Only limited studies have considered comfort and legibility issues, often in an ad hoc manner. A new technique is described that integrates additional constraints in a more generic way. In these steps of our work, we assume that the final positions of the paths are already calculated.

Figure 9. Two paths found by classical motion planning systems

We introduce three criteria to the motion planning stage to ensure safety and comfort. The robot must take into account these three criteria at the planning stage along with the more common aspects of path planning such as obstacle avoidance. Each criterion is represented by human-centred costs stored in a 2D grid:

Safety Criterion: This focuses on ensuring safety by controlling the distance between the robot and human. The robot, if possible, must avoid approaching the human too closely, and in some cases (i.e. no physical interaction) the robot must not be able to pass through a certain perimeter around the human. However, the robot must be able to approach the human to allow interactions to occur (for example to pass an object to a human). Hence, this distance between the robot and the human is not uniform and fixed, but depends on the type of human-robot interaction, in addition to the human preferences, and physical abilities. For instance, the user studies presented above are reflected by a configuration of costs that favours approach motions by the side ( Fig 10).

Visibility Criterion: Human comfort is a key issue when dealing with HRI scenarios, and some properties can be extracted from this issue. In particular, humans generally feel more comfortable when the robot is within their field of vision. Therefore, a "visibility criterion", is used to help the robot to stay, during its motions, in the human's field of view. The visibility grid is constructed according to costs reflecting the effort required by the human to get the robot in his field of view. Grid points located in a direction for which the human has only to move his eyes have a lower cost than positions requiring head turning in order to get the robot in the field of view. Also, when the robot is far away from the human, the effect of visibility must decrease, and beyond a certain distance it must be negligible.

Hidden Zones: In the grids presented above, the costs are calculated without taking into account obstacles in the environment. However, obstacles in close vicinity to the human can have various effects on safety and visibility issues. If the robot is behind an obstacle, the human might feel comfortable because the obstacle would block the direct path between the human and the robot. Therefore, the safety criterion must be cancelled in zones located behind the obstacles. In contrast, as the robot passes behind an obstacle and becomes hidden, and the human cannot see the robot, the visibility costs no longer correspond to physical realities.

To handle this issue, we introduce a further criterion termed, "hidden zones criterion". This criterion helps to determine better costs for positions hidden from the human by obstacles. An important effect of obstacles for human comfort is the "surprise factor". When the robot is hidden by an obstacle close to the human, and suddenly appears in the human field of vision, it can cause surprise and possibly fear. To avoid this effect, we must discourage the robot to pass behind an obstacle too closely, and must allow it to get into the human's field of view when sufficiently far from the human. This can be done by adding costs to the zones hidden from the subject's view by the obstacles. The costs in the hidden zone grid are inversely proportional to the distance between the human and the robot so that the robot chooses to keep a distance from back sides of the obstacles that are close to humans.

Once the safety, visibility, and hidden zones grids have been computed (Fig. 10), they are merged into one single grid where the robot will search for a minimum cost path. Different ways, depending on the task and on the balance between criteria, can be used to aggregate the grid costs. For example, for an urgent task, the importance of the visibility grid is less than the safety grid so that the robot does not take visibility largely into account. Once the final grid is computed, the cells corresponding to the obstacles in the environment are labelled as forbidden and an A* search is performed to find minimum-cost path between two given positions of the robot. Since only crossing the obstacles and humans are forbidden, with this algorithm we guarantee to find a path if it exists. The computed paths shown in Figures 11 and12 are collision-free and also take into account the human's comfort and safety.

Conclusions

Results from the two HRI trials indicate that a large majority of human subjects, when seated, preferred a robot to approach from either the left or right side. The frontal approach was seen as uncomfortable, impractical, in some cases even threatening or confrontational, and should thus be avoided. This result is in line with human-human situations where standing or sitting at an angle of 45 degrees to each other can reduce feelings of aggression and confrontation [START_REF] Pease | The definitive book of body language[END_REF]. However, the side that an individual human will actually prefer, left or right, depends to a large extent on the preferences of the individual concerned. The results do show that there is a bias towards the right hand side. This may be related to the fact that most of the trial subjects were right handed (in common with most of the population in general). Therefore, for a robot which is bringing an object to a seated human whose preferences are not known, it should always avoid a frontal approach and if (physically) convenient and consistent with the particular task then approach from the right. If the seated humans' approach direction preferences are known, then the robot should approach from the preferred direction whenever convenient 2 . It should be noted here that a human subject will not be unduly disturbed if their approach preference with regard to which side are not followed.

There were some perceived gender differences with regard to approach direction, with some females actually preferring a frontal approach direction, whereas slightly more males than females preferred a right side approach over other directions. From psychological studies [START_REF] Pease | The definitive book of body language[END_REF] it has been found that women tend to stand slightly closer to one another, face each other more, and touch each other more, compared to men interacting with other men. That women tend to face each other more could possibly account for the fact that women in our studies more frequently preferred the robot to approach from the frontal direction compared to men, although this issue needs further investigation.

In the follow-up trials, no subjects thought that the robot came too close from either the right or left side directions, though a majority thought the front approach distance was too close. In all cases the robot approached to no closer than 50cm, which was the inbuilt safety collision avoidance distance of the robot. It has been noted that there are cultural differences in personal spatial zones [START_REF] Pease | The definitive book of body language[END_REF] 3 . However, although some subjects in the HRI trials may have originated from other countries and cultures, all the subjects had been resident in the UK and therefore could be presumed to adopt human-human social distances similar to those of the average UK population. Therefore, regional, cultural or ethnic origin information was not asked (or controlled) for in the studies 4 .

Most subjects stated that the robot moved too slowly or about right at 0.4m/s, while nobody rated that the robot moved too fast. This suggests that (especially after a longer habituation period), most subjects would prefer the robot to move at a faster speed. It would therefore be reasonable to set the default robot speed at a relatively slow 0.4m/s and then perhaps increase the approach speed over time or in response to the user's wishes or preferences.

The robot used in the trials only had a simple short reach gripper, so the object was presented to the subject in a simple lifting tray. If a longer manipulator or arm was fitted, the results obtained may well be very different. It is desirable to perform further trials with various robots fitted with various types of arms or manipulators to see what effect they may have on user preferences. Also, long term trials are needed to investigate the effect on people of longer periods of exposure to robots. It would also be interesting to perform human-human studies to complement the work presented here. However, the primary focus of this paper is on robot to human approach direction preferences.

The human-aware motion planner is in its first steps of development and implementation. It requires further experiments to customize and validate the planner for live HRI situations. We are planning to implement this motion planner along with task reasoning capabilities [START_REF] Clodic | A decisional framework for autonomous robots[END_REF] into a real robot that must have sufficient human perception capabilities such as determination and tracking of various features like human-body posture, head orientation, hand configuration and gaze direction. In the execution stage of the plan, the robot must be highly reactive to changes in the environment. Using path deformation approaches can ensure this reactivity.

Joint work as described in this paper will ultimately contribute to the development of interaction-aware robots [START_REF] Dautenhahn | From embodied to socially embedded agents -Implications for interactionaware robots[END_REF], i.e. robots that are sensitive to the social context they are embedded in. This is a vital requirement for all those robotics applications where human contact and acceptability plays a vital part, as it is the case in domestic, healthcare and other applications. The challenge to develop robots that are not only 'doing the right thing', but 'doing the thing right' [START_REF] Sengers | Do the right thing: An architecture for action expression[END_REF] can only be tackled in a interdisciplinary endeavour involving psychologist as well as roboticists and HRI experts.

4.

Figure 1 .Figure 2 .Figure 3 .

 123 Figure 1. Live Trial Area

Figure 4 .

 4 Figure 4. Demonstration trial: Robot to human approach direction preferences.

Figure 6 .

 6 Figure 6. Follow-up trial: Least preferred and most preferred robot to human approach directions.

Figure 7 .

 7 Figure 7. Combined trial results: Overall robot to human approach direction preferences

Figure 8 .

 8 Figure 8. Combined results: Male and female preferences

Figure 10 .

 10 Figure 10.The "safety", the "visibility" and the hidden zones" grids. The height of a point corresponds to the cost of that point. The grids were modified to correspond to the results of the user studies.

Figure 11 .

 11 Figure 11.A human friendly path calculated automatically by the planner. Note the robot does not choose the shortest path and prefers a path that avoids it "to burst" near the human.

Figure 12 .

 12 Figure 12.A Hallway scenario. The planner automatically plans a trajectory that allows the robot to pass next to the human without causing any discomfort. Note that as the robot does not immediately take a position behind the human, it avoids causing any discomfort when it is invisible to him.

Due to space limitations, only the most frequently cited comments are shown.

For example, many southern Europeans and Japanese have an intimate distance (reserved for close friends and family) of only 20-30cm compared to

46-122cm of the Americans and northern Europeans. Europeans might refer to Asians as 'pushy' and 'familiar' and Asians might refer to Europeans and Americans as 'cold' and 'stand-offish'. There are also differences in rural vs. urban spatial zones. People raised in more rural, less populated areas need more personal space, than those raised in densely populated cities.[START_REF] Dario | Humanoids and personal robots: Design and experiments[END_REF] A specific study which investigates in more detail human robot approach distances using PeopleBot TM robots is given in Walters et al.[START_REF] Walters | Close encounters: Spatial distances between people and a robot of mechanistic appearance[END_REF].

ACKNOWLEDGMENTS

The work described in this paper was conducted within the EU Integrated Project COGNIRON ("The Cognitive Robot Companion") and was funded by the European Commission Division FP6-IST Future and Emerging Technologies under Contract FP6-002020.

Many thanks go to Mike Blow for his help in creating the videos.

5.