Just-In-Time compilation of OCaml byte-code

This paper presents various improvements that were applied to OCamlJIT2, a Just-In-Time compiler for the OCaml byte-code virtual machine. OCamlJIT2 currently runs on various Unix-like systems with x86 or x86-64 processors. The improvements, including the new x86 port, are described in detail, and performance measures are given, including a direct comparison of OCamlJIT2 to OCamlJIT.

Introduction
The OCaml system [11,16] is the main implementation of the Caml language [6], featuring a powerful module system combined with a full-fledged object-oriented layer. It comes with an optimizing native code compiler ocamlopt, a byte-code compiler ocamlc with an associated runtime ocamlrun, and an interactive top-level ocaml. OCamlJit [18] and OCamlJit2 [15] provide Just-In-Time compilers for the byte-code used by ocamlrun and ocaml.
We describe a set of improvements that were applied to OCamlJit2, including a new port to the x86 architecture 1 and some interesting optimizations to further improve the execution speed of the JIT engine. OCamlJit2 is open-source 2 and is verified to work with Linux/amd64, Linux/i386 and Mac OS X (64-bit Intel Macs only), but should also run on other Unix-like systems with x86 or x86-64 processors.
The paper is organized as follows: Section 2 mentions existing systems and relevant sources of information. Section 3 describes the improvements applied to OCamlJit2, in particular the new x86 port and various floating-point optimizations. Detailed performance measures are given in section 4, including a direct comparison with OCamlJit. Section 5 concludes with possible directions for further work.

Existing systems
The implementation of OCamlJit2 described below is based on a previous prototype of OCamlJit2 [15], and earlier work on OCamlJit [18] and OCaml [10,11,12,16]. We assume that the reader is familiar with the internals of the OCaml byte-code and runtime, and the structure of the OCamlJit and OCamlJit2 Just-In-Time compilers. An overview of the relevant parts of the OCaml virtual machine is given in both [15] and [18], while [16] provides the necessary insights on the OCaml language.

Improvements
This section describes the improvements that were applied to the OCamlJit2 prototype described in [15]. This includes the new x86 port (section 3.1), a simple native code managment strategy (section 3.2), as well as improvements in the implementation of floating-point primitives (section 3.3), which reduced the execution time of floating-point benchmarks by up to 30%. Readers only interested in the performance results may skip straight to section 4.

32-bit support
OCamlJit2 now supports both x86-64 processors (operating in long mode) as well as x86 processors (operating in protected mode). This section provides a brief overview of the mapping of the OCaml virtual machine to the x86 architecture, especially the mapping of the virtual machine registers to the available physical registers. See [15] for a description of the implementation details of the x86-64 port.
The x86 architecture [9] provides 8 general purpose 32-bit registers %eax, %ebx, %ecx, %edx, %ebp, %esp, %edi and %esi, as well as 8 80-bit floating-point registers organized into a so-called FPU stack (and also used as 64-bit MMX registers). Recent incarnations also include a set of 8 SSE2 registers %xmm0, . . ., %xmm7. The System V ABI for the x86 architecture [17], implemented by almost all operating systems running on x86 processors, except Win32 which uses a different ABI, mandates that registers %ebp, %ebx, %edi, %esi and %esp belong to the caller and the callee is required to preserve their values across function calls. The remaining registers belong to the callee.
To share as much code as possible with the x86-64 port, we use a similar register assignment for the x86 architecture. This includes making good use of callee-save registers to avoid saving and restoring too many aspects of the machine state whenever a C function is invoked. Our register assignment therefore looks as follows: The virtual register accu is mapped to %eax. extra args goes into %ebx, whichjust like on x86-64 -contains the number of extra arguments as tagged integer. The environment pointer env goes into %ebp, and the stack pointer sp goes into %esi. %edi contains the cached value of the minor heap allocation pointer caml young ptr to speed up allocations of blocks in the minor heap; this is different from ocamlopt on x86, where caml young ptr is not cached in a register (unlike x86-64 where ocamlopt caches its value in %r15).
The setup and helper routines that form the runtime of the JIT engine are located in the file byterun/jit rt i386.S. These are mostly copies of their x86-64 counterparts in the file byterun/jit rt amd64.S, adapted to the x86 architecture. The adaption was mostly straight-forward, replacing the x86-64 registers with their x86 counterparts and the 64-bit opcodes with their 32-bit counterparts.

Address mapping and on-demand compilation
We use the existing scheme [15] to map byte-code to native machine code address, which replaces the instruction opcode word within the byte-code sequence with the offset of the generated native code relative to the base address caml jit code end. Whenever jumping to a byte-code address -i.e. during closure application or return -this offset is read from the instruction opcode, caml jit code end is added to it, and a jump to the resulting address is performed. The trampoline code for x86 -shown in Figure 1 -is therefore quite similar to the trampoline code for x86-64 (%ecx contains the address of the byte-code to execute and %edx is a temporary register). movl (%ecx), %edx addl caml_jit_code_end, %edx jmpl *%edx Adapting the on-demand compilation driver was also straight-forward, due to the similarities of the x86 and x86-64 architectures. It was merely a matter of adding a x86 byte-code compile trampoline -shown in Figure 2 -which is slightly longer than its x86-64 counterpart, because the C calling convention [17] requires all parameters to be passed on the C stack.
pushl %eax pushl %ecx call caml_jit_compile movl %eax, %edx popl %ecx popl %eax jmpl *%edx Whenever the byte-code compile trampoline is invoked, %eax contains the current accu value, %ecx contains the byte-code address and the remainder of the OCaml virtual machine state is located in global memory locations and callee-save registers. Therefore %eax has to be preserved on the C stack and %ecx must be passed as parameter to the caml jit compile function. Upon return %eax contains the address of the generated native code, which is saved to %edx. Afterwards the stack frame is removed, restoring %eax, and execution continues at the native code address.
The remaining porting effort was mostly related to generalizing the code emitter preprocessor macros to conditionally emit x86 or x86-64 code, and fiddling with some nasty details of the different addressing modes. The core of the code generator is almost free of #ifdef's, because the structure of the generated code for the two targets is pretty much equivalent. This is especially true for floating-point operations, which use SSE2 registers and instructions on both x86 and x86-64. OCamlJit2 therefore requires a processor with support for the SSE2 extension [1,9]; if OCamlJit2 detects a processor without SSE2, it disables the JIT engine and falls back to the byte-code interpreter 3 .

Native code management
With our earlier prototype, memory allocated to a chunk of generated native machine code was never freed by OCamlJit2, even if the byte-code segment, for which this native machine code was generated, was released (using the Meta.static release bytecode OCaml function). This may cause trouble for MetaOCaml [19] and long-lived interactive top-level session, where the life-time of most byte-code segments is limited. This was mostly due to the fact that all generated native machine code was stored incrementally in one large memory region, with no way to figure out which part of the memory region contains code for a certain byte-code segment. We have addressed this problem with a solution quite similar to that used in OCamlJit [18]. Instead of generating native machine code incrementally into one large region of memory, we divide the region into smaller parts, called native code chunks, and generate code to these chunks. Every byte-code segment has an associated list of chunks, allocated from the large memory region, now called chunk pool, which contain the generated code for the given byte-code segment, as shown in Figure 3.
Every segment starts out with an empty list of chunks. As soon as on-demand compilation triggers for the segment, a new chunk is allocated from the chunk pool and native machine code is generated into this chunk until it is filled up; when this happens, the code generator allocates another chunk for this segment, and emits a jmp instruction from the previous chunk to the new chunk if necessary. Once a byte-code segment is freed using Meta.static release bytecode, all associated native code chunks are also released. This way OCamlJit2 no longer leaks native code generated for previously released byte-code segments.
While this technique is both simple and effective, there are also several drawbacks. The speed of both the JIT compiler and the generated code is somewhat dependent on the size of the native code chunks. A small chunk size helps to reduce the size of the working set and the amount of memory wasted in long-lived interactive top-level sessions, but on the other hand decreases the throughput of the JIT compilation driver and leads to somewhat less efficient execution for common byte-code programs which use only a single byte-code segment. We have settled on a chunk size of 256 KiB for now, which seems to provide a good compromise.
A possible way to reduce the amount of wasted memory with the interactive top-level would be to store code generated for small byte-code segments to some special, shared code chunks, and manage the life-time of these shared chunks using a reference counting scheme.

Floating-point optimizations
OCaml uses a boxed representation for floating-point values. It does this for various reasons, i.e. to simplify the interface to the garbage collector and the garbage collector itself. While this is an elegant and portable solution, it decreases the performance of OCaml programs using floating-point calculations, especially when executed with the byte-code interpreter.
The optimizing native code compiler ocamlopt applies various optimizations to avoid generating a boxed floating-point object in the heap for each and every floating-point value during the execution of the program. The byte-code interpreter ocamlrun however has to box every floating-point value, which is certainly slower than using the available floating-point registers, and also causes a non-negligible load on the garbage collector. Both OCamlJit and OCamlJit2 (as described in [15]) used the same strategy as the byte-code interpreter, namely allocating a heap object for every floating-point value during the execution, but both JIT engines applied various peephole optimizations to avoid the overhead of calling the floating-point C primitives.
We have implemented a new technique for OCamlJit2, which avoids the heap allocation for temporary floating-point values that appear as result of a byte-code instruction and are used as argument in the subsequent byte-code instruction. Figure 4 shows an example taken from the byte-code of the almabench.ml OCaml program. ccall caml_array_unsafe_get_float, 2 ccall caml_mul_float, 2 ccall caml_add_float, 2 ccall caml_add_float, 2 ccall caml_sqrt_float, 1 push Executing this piece of byte-code with the byte-code interpreter allocates five floatingpoint objects in the minor heap, one for each ccall. The first four objects will die immediately once the garbage collector is run, since they are only used as temporary results, while the result of the caml sqrt float call may indeed survive for a longer period of time. Furthermore, accessing the actual floating-point values of the temporary results requires at least four additional load instructions. If the temporary results would be kept in registers, there would be no need for the heap allocation and this would also eliminate the additional load instructions. While the heap allocations can seriously decrease performance, the additional load instructions are a minor issue, since the store-to-load forwarding techniques [3,14] implemented in modern processors will usually eliminate the load from memory.
We have implemented a clever optimization in OCamlJit2, which translates various floating-point primitives using SSE2 instructions and functions from the standard C math library, in a way that the result of each primitive is not stored in a heap-allocated object, but is left in the %xmm0 register. Subsequent floating-point primitives then take the value from the %xmm0 register instead of the memory location pointed to by %rax (or %eax). This process is repeated for all floating-point primitives in a row. The last floating-point instruction -the call to caml sqrt float in our example -then allocates a heap block for its result. Our optimization is particularly beneficial for the x86 port, where we were able to beat the optimizing native code compiler in the almabench.unsafe benchmark, but it also pays off for the x86-64 port, where we could reduce the execution time of floating-point benchmarks by up to 30% (compared to the earlier OCamlJit2 prototype).

Performance
With the x86 port in place we were finally able to compare the performance of OCamlJit [18] and OCamlJit2 running on the same machine. We measured the performance on three different systems, one x86 box for comparison with OCamlJit, and two x86-64 machines with different processors and operating systems to test-drive the recent improvements with our primary 64-bit targets: • A MacBook with an Intel Core 2 Duo "Penryn" 2.4 GHz CPU ( The benchmark programs used to measure the performance are the following test programs from the testsuite/tests folder of the OCaml 3.12.0 distribution: • almabench is a number-crunching benchmark designed for cross-language comparisons. almabench.unsafe is the same program compiled with the -unsafe compiler switch.
• bdd is an implementation of binary decision diagrams, and therefore a good test for the symbolic computation performance.
• boyer is a term manipulation benchmark.
• fft is an implementation of the Fast Fourier Transformation.
• nucleic is another floating-point benchmark.
• quicksort is an implementation of the well-known QuickSort algorithm on arrays and serves as a good test for loops.
• soli is a simple solitaire solver, well suited for testing the performance of non-trivial, short running programs.
• sorts is a test bench for various sorting algorithms.
For our tests we measured the total execution time of the benchmarks, given as combined system and user CPU time, in seconds.     values are better. The times were collected by executing each benchmark 5 times with every engine, and using the timings of the fastest run. Figure 5 highlights the speedup of the JIT engines relative to the byte-code interpreter on the three test systems. The x86-64 port received another nice speedup in the floating point benchmarks compared to the earlier prototype due to the improvements described in section 3.3. On x86 OCamlJit2 provides a performance boost of 2.2 to 9.6 compared to the byte-code interpreter, and is 1.1 to 2.0 times faster than OCamlJit. This is especially noticable with short running programs like soli.unsafe, where OCamlJit2 benefits from the reduced compilation overhead, and in floating-point programs, where OCamlJit wins because of clever floating point optimizations and its use of the SSE2 extension. Figure 6 shows the performance of the byte-code interpreter and the JIT engines relative to the optimizing native code compiler ocamlopt. One rather surprising result was the bad performance of the generated x86 native code for the almabench.unsafe benchmark, where OCamlJit2 was able to beat the native code compiler by a factor of 1.2. This may be related to the use of SSE2 instead of x87 instructions, which are generally faster, but it also seems that we have spotted a problem within the x86 port of ocamlopt here (unfortunately, we were unable to track down the issue). On a related note, we have also spotted some issues with the x86-64 floating-point code generated by ocamlopt and already submitted an appropriate patch 4 , which will be available in OCaml 3.12.1, yielding performance improvements of 6 − 13% with floating-point programs.
In general, floating-point benchmarks benefit a lot when used with OCamlJit2, which was somewhat expected, in particular with the optimizations implemented in the latest prototype. OCamlJit does a respectable job, but is unable to compete with OCamlJit2 performance-wise. This is probably caused by the better compilation scheme used by OCamlJit2 and also related to the use of Gnu Lightning within OCamlJit. Nevertheless, it is this use of Gnu Lightning which makes OCamlJit slightly more portable than OCamlJit2 (three supported platforms in case of OCamlJit, compared to only two with OCamlJit2).

Conclusions and further work
Our results show that Just-In-Time compilation of OCaml byte-code can lead to some significant speedup (at least twice as fast the byte-code interpreter in all benchmarks). Starting out with a simple compilation scheme and applying some clever optimizations led to impressive performance gains. But we have also noticed that our approach is somewhat limited, which is mostly related to the nature of the OCaml byte-code and the design choices made for the interpreter runtime. The OCaml byte-code and runtime were certainly designed with "fast interpretation" in mind [10] and perform quite well in this area, but this same fact also limits the possibilities for effective Just-In-Time compilation if one wants to avoid touching too many aspects of the runtime. Using a register machine as used by Dalvik [5] or Parrot [7] instead of the stack machine for the byte-code virtual machine would make it easier to apply JIT techniques -it would in fact make Just-In-Time compilation the natural implementation choice for the virtual machine.
Implementations of other runtimes, like the various JVMs [13] or the Common Language Runtime [8], show that it is indeed possible to perform efficient JIT compilation with stack virtual machines, but these runtimes use expensive compilation techniques for instruction selection, register allocation and instruction scheduling, whose applicability is questionable within the scope of the OCaml byte-code runtime. For example, in order to effectively reduce the overhead of closure application and return in OCaml byte-code execution, one would most likely need to perform interprocedural register allocation, which mandates the availability of global control and data flow information, both of which are difficult to collect efficiently. It may indeed be possible to design a Just-In-Time compiler for the OCaml byte-code, which generates code as fast as the code generated by ocamlopt, using standard compilation techniques [2], but such a JIT engine comes at a high cost with respect to maintainability and execution speed of the JIT compiler, and it is questionable whether it is worth this cost, especially since there is already an optimizing native code compiler, which limits the possible use cases for the Just-In-Time compiler.
The main application of OCamlJit2 is the interactive top-level and other dynamic code generation environments like MetaOCaml [19]. The OCaml repository already contains an experimental "native top-level" ocamlnat for this purpose, which uses the functionality of ocamlopt to generate efficient native code at runtime and execute it via the native code runtime. Improving ocamlnat may provide a better way to gain an efficient top-level, and we are currently evaluating what would need to be done in this area.


s2fieldsofstudy:
Computer Science
Business

text:
A Genetic Algorithm for the Multi-Pickup and Delivery Problem with time windows

In This paper we present a genetic algorithm for the multi-pickup and delivery problem with time windows (m-PDPTW). The m-PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. This paper purposes a brief literature review of the PDPTW, present our approach based on genetic algorithms to minimizing the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.

Introduction
With the time and economic constraints implications of the transport goods problem, its resolution becomes very difficult, requiring the use of tools from different disciplines (manufacturing, information technology, combinatorial optimization, etc.)... Indeed, the process from transport systems and scheduling are becoming more complex by their large size, by the nature of their relationship dynamics, and by the multiplicity of which they are subjected.
Many studies have been directed mainly towards solving the vehicle routing problem (VRP). It's an optimization vehicle routing problem to meet travel demands. Other researchers became interested on an important variant of VRP which is the PDPTW (Pickup and Delivery Problem with Time Windows) with capacity constraints on vehicle.
Our object is to design a tool for m-PDPTW resolution based on genetic algorithms and Pareto dominance method to give a set of satisfying solutions to this problem minimizing the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.

Vehicle routing problem
The Vehicle Routing Problem (VRP) represents a multi-goal combinatorial optimization problem which has been the subject of much work and many variations in the literature. It belongs to the NP-hard class. . [Christofides, N and al., 1979] [Lenstra, J and al., 1981] Heuristic methods have been used by Matsinen, T and al to solve the general problem in this area as the Travelling Salesman Problems [Matsinen, T and al., 1992]. The Meta heuristics were as well applied to solving the vehicle routing problem. Among these methods, we can include ant colony algorithms, which were used by Montamenni, R and al for the resolution of DVRP and used also by Sorin C, N and al to solving the multiple constraints problem: vehicle route allocation. [Montamenni, R and al., 2002] [Sorin C, N and al., 2008] The VRP principle is: given a depot D and a set of customers orders C = (c1, ... , Cn), to build a package routing, for a finite number of vehicles, beginning and ending at a depot. In these routing, a customer must be served only once by a single vehicle and vehicle capacity transport for a routing should not be exceeded. [Nabaa, M and al., 2007] Savelsbergh shown that the VRP is a NP-hard problem [Savelsbergh, M.P.W and al., 1995]. Since the m-PDPTW is a generalization of the VRP it's a NP-hard problem.

The PDPTW: Pickup and Delivery Problem with Time Windows
The PDPTW is a variant of VRPTW where in addition to the existence of time constraints, this problem implies a set of customers and a set of suppliers geographically located. Every routing must also satisfy the precedence constraints to ensure that a customer should not be visited before his supplier. [Psaraftis, H.N., 1983] A dynamic approach for resolve the 1-PDP without and with time windows was developed by Psaraftis, H.N considering objective function as a minimization weighting of the total travel time and the non-customer satisfaction. [Psaraftis, H.N., 1980] Jih, W and al have developed an approach based on the hybrid genetic algorithms to solve the 1-PDPTW, aiming to minimize combination of the total cost and total waiting time. [Jih, W and al., 1999] Another genetic algorithm was developed by Velasco, N and al to solve the 1-PDP bi-objective in which the total travel time must be minimized while satisfy in prioritise the most urgent requests. In this literature, the method proposed to resolve this problem is based on a No dominated Sorting Algorithm (NSGA-II). [Velasco, N and al., 2006] Kammarti, R and al deal the 1-PDPTW, minimizing the compromise between the total travel distance, total waiting time and total tardiness time, using an evolutionary algorithm with Special genetic operators, tabu search to provide a set of viable solutions. About the m-PDPTW, Sol, M and al have proposed a branch and price algorithm to solve the m-PDPTW, minimizing the vehicles number required to satisfy all travel demands and the total travel distance. [Sol, M and al., 1994] Quan, L and al have presented a construction heuristic based on the integration principle with the objective function, minimizing the total cost, including the vehicles fixed costs and travel expenses that are proportional to the travel distance. [Quan, L and al., 2003] A new metaheuristic based on a tabu algorithm, was developed by Li, H and al to solve the m-PDPTW. [Li, H and al., 2001] Li, H and al have developed a "Squeaky wheel" method to solve the m-PDPTW with a local search. [Li, H and al., 2002] A genetic algorithm was developed by Harbaoui Dridi, I and al dealing the m-PDPTW to minimize the total travel distance and the total transport cost. [Harbaoui Dridi, I and al., 2008]

Mathematical formulation
Our problem is characterized by the following parameters: • N : Set of customers, supplier and depot vertices, The function to minimize is given as follows: Subject to: The constraint (2) and (3) ensure that each vertex is visited only once by a single vehicle. The constraint (4) and (5) ensure that the vehicle route beginning and finishing is the depot. The constraint (6) ensures the routing continuity by a vehicle. (7), (8) and (9) are the capacity constraints. The precedence constraints are guaranteed by (10) and (11). The constraints (12), (13) and (14) ensure compliance time windows.

Genetic algorithm for minimizing the total travel cost
In this part, we present our approach based on genetic algorithms to minimize the total travel cost.

Solution coding
A chromosome is a succession (permutation) vertex, which indicates the order in which a vehicle is to visit all the vertices. Fig.1 represents the solutions under form of chromosomes.

Decoding the vehicles passage
The decoding allows, from every chromosome of the population to obtain an initial solution sign the passage of each vehicle on the corresponding vertex. (Fig.2) 1

Crossover operator
Following the generation of the initial population, we proceed to crossover phase which ensures the recombination of parental genes for train new descendants. To do this, we choose the one point crossover. (Fig.3) 1 2 3 4 5 6 7 8 9 10

Mutation operator
Mutation operator (Fig.4) is to choose two positions at random, within a chromosome and exchange their respective values.

Fig.4 : Mutation operator
Note here that we must respect the constraint precedence, to ensure that a customer is not visited before his supplier, and capacity to ensure the non-overload of each vehicle.

Generation of initial population
The choice of the initial population is important because it can make a genetic algorithm more or less fast to converge towards the global optimum.
In our case, we will generate two types of populations. A first population noted P node , which represents all nodes to visit with all vehicles, according to the permutation list coding (Fig.1). The second population noted P vehicle indicates nodes number visited by each vehicle. Knowing that k varies between 1 and

N' 2
vehicles. Fig.5 shows an individual example of P vehicle with

Correction procedure
The principle of correction precedence and capacity is to ensure that a customer is not visited before his supplier while respecting the vehicles capacity.

Generation of population P node/vehicle
Considering the population P node given by Fig.1, correction procedures and P vehicle population, given by Fig.5, we illustrated in Fig.8 an individual of the population P node/vehicle .

Calculation procedure
Each vehicle will serve vertices in the assignment order. Once returned to the depot, we calculate the transport cost corresponding to the travel distance, and we repeat this until all the vertices are served. We reproduce this work for each individual to the population P vehicle , taking into account the different possible combinations between P vehicle and P node , to obtain thereafter the correspondent individual of the population P node/vehicle that minimizes our objective function. The algorithm of this procedure is shown by the Fig.9. Fig.10 indicates how to minimizing the total cost of transport.

Begin
Step 1 : Create the initial population, (size n).
Step 2 : Fill the intermediate population P node (size 2n) with individuals' crossover, mutation or copy.
Step 3 : Correction procedure of Precedence and capacity. Step

Simulation
We present in Table 1, the simulation results given by our approach. We observe that our approach reduces the vehicles number (2 vehicles to serve up to 50 vertices and 4 vehicles to serve 100 vertices). Knowing that a vehicle will cause an augmentation travel cost on the addition of a driver, the travel fixed costs, to depreciation of the vehicle used. Hence the interest of our approach that aims to minimize the total travel cost.

Conclusion
In this paper we have proposed, following a study of the different approaches proposed for the resolution of 1-PDPTW and m-PDPTW, a genetic algorithm for minimizing the total travel cost. To do this, we presented the mathematical formulation of our problem, and we have detailed the calculation procedure for determine the optimal solution, that minimizes our objective function


Combination of Subtractive Clustering and Radial Basis Function in Speaker Identification

Speaker identification is the process of determining which registered speaker provides a given utterance. Speaker identification required to make a claim on the identity of speaker from the Ns trained speaker in its user database. In this study, we propose the combination of clustering algorithm and the classification technique - subtractive and Radial Basis Function (RBF). The proposed technique is chosen because RBF is a simpler network structures and faster learning algorithm. RBF finds the input to output map using the local approximators which will combine the linear of the approximators and cause the linear combiner have few weights. Besides that, RBF neural network model using subtractive clustering algorithm for selecting the hidden node centers, which can achieve faster training speed. In the meantime, the RBF network was trained with a regularization term so as to minimize the variances of the nodes in the hidden layer and perform more accu-rate prediction.

INTRODUCTION
Pattern recognition is the scientific discipline whose goal is the classification of objects into a number of categories or classes [1]. Pattern recognition in speech can be divided into speaker recognition and speech recognition. The different between speaker recognition and speech recognition are speaker recognition is recognizing who is speaking but speech recognition is recognizing what is being said.
Speaker recognition technologies have two major applications that are speaker identification and speaker verification. The goal of speaker identification is to recognize the unknown speaker from a set of N known speakers. On the other hand, the goal of speaker verification is evaluate whether the claimed identity is correct or not when the unknown speaker presents a speech sample. The performance of the speaker recognition system is dependent on few factors. Speech variations are hard to distinguish even the same particular effect is observed on the speech signal. The speech variation can divided into six categories -intra-speaker variations, inter-speaker variations, model size, robustness, modeling and accuracy.
One of the factors that will influence the performance of the speaker recognition system is amount of data. The population of data complexity increase the of degradation rate inter-speaker variation. Beside this, the ways to build speaker models using statistical methods in data training might influence system decision biased the verification environment is different from the enrollment [2].
A static model is proposed which employed as an input pattern of Multilayer Perceptron (MLP) network [24]. A MLP network consisting input layers, hidden layers and output layer. The network has a simple interpretation as a form of input-output model, with the weights and thresholds (biases) the free parameters of the model. Such networks can model functions of almost arbitrary complexity, with the number of layers, and the number of units in each layer, determining the function complexity [23]. However, MLP network has some disadvantages. First, MLP needs input pattern of fixed length [24] which will cause the difficulties when dealing with the speech data. Another disadvantage are MLP increasing the number of connections in the network. The increasing of the number of connection will increases the training time and make it more probable fall into a poor local minima.

IDENTIFICATION TAXONOMY
Speaker recognition can be divided into speaker verification and speaker identification. Speaker verification is speaker claims to be of a certain identity and the voice is used to verify this claim. On the other hand, identification is the task of determining an unknown speaker's identity. The figure 2.2 is the figure of the identification taxonomy. Speaker identification can be divided into closed-set iden-tification and open-set identification. For the closed-set identification, the task can divided into text-independent identification and text dependent identification, depend on the algorithm used for the identification. The goal of speaker recognition is to identify the speaker, independently of what the speaker is saying.

Speaker verification
Speaker verification is the process of accepting or rejecting the identity claim of a speaker. For the speaker verification, a speaker's recording is matched to previous recording, which was made during the voice registration period to produce the result. The result either is accepting or refusing the match between the speaker's recording and the previous recording.

Speaker Identification
Speaker identification is the process of determining which registered speaker provides a given utterance. Speaker identification required to make a claim on the identity of speaker from the Ns trained speaker in its user database. So, the role of automatic speaker identification (ASI) is more complex and the error of the system will increased if the Ns increased.

Close-set and Open set
Closed-set speaker identification occurs if all possible test utterances belong to one of the speakers that have been learned by the system. If a test utterance may be originating by a person that has not been shown to the system before, this is open-set speaker identification.

Text-dependent and Text Independent
Speaker recognition methods can be divided into two methods. There are text-dependent and text-independent. During the enrollment phase, the speaker's voice is recorded and typically a number of features are extracted. If the utterances used in the operational phase must be same with the utterances during the enrollment phase, this is text-dependent. On the other hand, for the textindependent, the utterances use in the operational phase is different with the utterances during the enrollment phase.

SPEAKER IDENTIFICATION SYSTEM
There are two phases in the speaker identification: enrollment phase and identification phase.

Figure 2 Enrollment Phase
During the enrollment phase, speech samples are collected from the speaker and convert the speech signal into set of feature vectors, which characterize the properties of speech that can separate different speakers. The collections of the enrollment

Figure 3 Identification Phase
In the identification phase, the test sample of unknown speakers is analyse and compared with all models from the speaker database. Both enrollment and identification phase has the same first step, feature extraction which converts the sampled speech signal into set of feature vectors, which characterize the properties of speech that can separate different speakers. The main purpose of this step is to reduce the amount of test data while retaining speaker discriminative information.

Speaker Identification Based on Subtractive Clustering Algorithm with Estimating Number of Clusters
Subtractive clustering algorithm which does the clustering without the initial guesses of location of the cluster centers and priori information about the number of clusters. The number of clusters is obtained by investigating the mutual relationship between clusters. This algorithm will solve the problems that contain in the K-means and fuzzy c-means (FCM). The major problems are the improper initial guesses of cluster centers may degrade the performance and the number of clusters cannot always be defined a priori. The new algorithm is based on subtractive clustering algorithm [11,12] and mutual relationship of clusters [13]. First, cluster centers are obtained incrementally from adding one cluster center at a time through the subtractive clustering algorithm. Second, investigate the mutual rela-tionship of a cluster with respect to all the other clusters, to obtain the estimation of the number of cluster. Two clusters are statistically dependent is decide by the mutual relationship.

Speaker Identification Using Reduce RBF Networks Array
The purpose of speaker identification is to determine a speaker's identity from the speech utterances. Essentially, speaker identification is a pattern recognition problem of a speech signal [16]. Both of the training and recognition processes are important for the speaker identification. Those processes are include the identification of discriminating features representing the specific characteristics of the speakers and the choice of the classifier. Radial basis function (RBF) networks choose because it successful use of GMM in speaker identification. The RBF network is a three-layer NN, which has the same underlying structure as the Gaussian Mixture Models (GMM) when Gaussian function is selected as the type of basis function in the RBF network [17]. Another reason for choose the RBF is RBF network easy to use. The key point in design of radial basis function networks is to specify the number and the locations of the centers. Input training data (IC) and both the input and output data (IOC) are the ways to obtained the vectors from the clustering algorithm. In this paper, IOC is choose because the structure of centers designed in the IOC is more effective. To select the suitable number or network centers, this method use the recursive orthogonal least-squares (ROLS) algorithm after the training process. Mel's frequency cepstral coefficients (MFCC) are extracted as the features for speaker characteristics. The system is composed of some binary classifiers, while the binary partitioned approach has been shown as an efficient solution for reducing training time [18].

OPERATION FRAMEWORK
In this paper, we focus on the performance of the speaker identification system using the clustering algorithm. In this case, we have applied the subtractive clustering as the clustering algorithm and RBF as the classification in speaker identification.

DC offset Removal
Speech data are discrete-time speech signal, it often carry some redundant constant offset called DC offset [20]. These DC offset will effect quality of the information extracted from the speech signal. Consequently, we calculating the average value of the speech signal and subtracting this from itself [2].

Silence Removal
This process is to remove the silence periods from the speech containing silence frames to make the signal becomes more compact. The figure 3.4 is the example of the before and after the silence removal process. Silence frames are audio frames of background noise with a low energy level with respect to voice segments [2]. The signal energy in each speech frame is evaluated by equation (1).

(1)
Where M is the number of samples in a speech frame and N is the total number of speech frames. Threshold is successively performed to detect silence frames with a threshold level determined by equation. Threshold = Emin + 0.1 (Emax -Emin) Emax -Emin are the lowest and greatest values of the N segment respectively.

Frame Blocking
The analysis of the speech signal is based on short-term spectral analysis. So, in order to analyze the speech signal, the speech signal is require to divided into fixed-length short frames. Figure 3.5 show that the speech signal is divided into overlapping frames with N analysis frame length and the frame is shifted with M samples from the adjacent frame. If the shifting is small, then the MFCC spectral estimated from frame to frame will be very smooth. If there is no overlapping between adjacent frames, the speech signals will be totally lost and correlation between the result LPC spectral estimates of adjacent frames will contain a noisy component [9].

Pre-emphasizing
Pre-emphasis is a technique used in speech processing to enhance high frequencies of the signal [2]. The main purpose of pre-emphasizing is to spectrally flatten the speech signal that is to increase the relative energy of its highfrequency spectrum. Pre-emphasis is important because: i. The speech signal generally contains more speaker specific information in the higher frequencies [21]. ii. When the speech signal energy decreases, the frequency increases. This allows the feature extraction process to focus on all aspects of the speech signal [2].

Windowing
In this process, the frames will be applied a window function to minimize the signal discontinuities at the beginning and the end of the each frame. A windowing function is used on each frame to smooth the signal and make it more amendable for spectral analysis [2]. A windowing function is used on each frame to smooth the signal and make it more amendable for spectral analysis. Usually for the speech processing, the smoother functions, Hamming Window is used.

Feature Extraction using Mel Frequency Cepstral Coefficients (MFCC)
A speech parameterization must be performed to convert the raw speech waveform into features vectors. After the windowing function is apply to the frames, the transformation technique, Fourier transform will be applied to the frames. The propose of the Fourier transform is to performed the transformation between time domain and frequency domain. Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) are efficient implementation of Fourier transform for discrete time signals sampled at regular intervals [2]. Mel-frequency warping is used to reduced the large number or the channel for the FFT. This process is called "binning". This step gives the linear-spectral domain feature vector, O_b^I (t), for bin b of the sample waveform at time t. Following that, logarithm transformation is applied to obtain the log-spectral values [2]: MFCCs can be obtained from the log-spectral values using inverse FFT[7]:

Obtain feature vector by applied the Subtractive-RBF
This process is to generate the speaker model for each of the sample speech in the training phase and store into the database. First, we used the subtractive clustering to choose the network centers. The RBF network is a threelayer NN, which has the same underlying structure as the Gaussian Mixture Models (GMM) when Gaussian function is selected as the type of basis function in the RBF network [17]. Each hidden unit is a Gaussian kernel function with output related to the distance between the input vectors and the centroid of the basis function. The output layer forms a linear combiner which calculates the weighted sum of the outputs of the hidden units, and is given by, where is the input vector, is the output node, is the weight from the ith RBF center, b is the output bias, and the Gaussian kernel functions are Where is the ith center, and are the function widths. Once the centers have been fixed, the optimal linear weights can be determined straightforwardly by using a linear least squares algorithm, or taking the pseudo inverse.

Identify the unknown speaker
An unknown speaker's voice is represented by a sequence of feature vector {x1, x2 ….xi), and compared with the speaker model from the database. To identify the unknown speaker, we measure the distortion distance of two vector sets based on minimizing the Euclidean distance. The equation for measuring the distortion distance is The more lower the value, that two vector sets is more similar and the lowest distortion distance of the speaker is chosen to be identified as the unknown person.

DISCUSSION
There are many techniques in speaker recognition system. The most common and widely use technique in speaker recognition are Hidden Markov models, Gaussian mixture models, pattern models, pattern matching algorithm, neural network and so on. But there are still need improved for the pattern recognition. By improved statistical modeling may produce better performance for the speaker recognition system. A better performance of the speaker recognition for the aspect speed and accuracy will attracted more people choose to use speaker recognition as the input method and replace the old input method.


An Overview of IEEE 802.15.6 Standard

Wireless Body Area Networks (WBAN) has emerged as a key technology to provide real-time health monitoring of a patient and diagnose many life threatening diseases. WBAN operates in close vicinity to, on, or inside a human body and supports a variety of medical and non-medical applications. IEEE 802 has established a Task Group called IEEE 802.15.6 for the standardization of WBAN. The purpose of the group is to establish a communication standard optimized for low-power in-body/on-body nodes to serve a variety of medical and non-medical applications. This paper explains the most important features of the new IEEE 802.15.6 standard. The standard defines a Medium Access Control (MAC) layer supporting several Physical (PHY) layers. We briefly overview the PHY and MAC layers specifications together with the bandwidth efficiency of IEEE 802.15.6 standard. We also discuss the security paradigm of the standard.

I. INTRODUCTION
Wireless Body Area Network (WBAN) has great potential to revolutionize the future of healthcare technology. It has attracted a number of researchers both from the academia and industry in the past few years. WBAN supports a wide range of medical and Consumer Electronics (CE) applications. For example, WBAN provides remote health monitoring of a patient's state for a long period of time without any restriction on his/her normal activities [1]- [2]. For a successful implementation of WBAN, a standard model was required which would be able to address both medical and CE applications. IEEE 802 established a Task Group called IEEE 802.15.6 1 for the standardization of WBAN [3]. Earlier, IEEE 802 had many success stories in developing international standards on wireless communication. Examples include IEEE 802.11 [4], IEEE 802.15.1 [5] and IEEE 802.15.4 [6] standards. The purpose of the IEEE 802.15.6 was to define new Physical (PHY) and Medium Access Control (MAC) layers for WBAN. The selection of the PHYs (frequency bands) were one of the most important issues. Generally, the available frequencies for WBANs are regulated by communication authorities in different countries. Fig. 1 shows a short summary of some of the frequency bands available for WBAN in different countries [7]. Medical Implant Communications Service (MICS) band is a licensed band used for implant communication and has the same frequency range (402-405 MHz) in most of the countries. Wireless Medical Telemetry Services (WMTS) is a licensed band used for medical telemetry system. Both  [7] MICS and WMTS bandwidths do not support high data rate applications. The Industrial, Scientific and Medical (ISM) band supports high data rate applications and is available worldwide. However, there are high chances of interference as many wireless devices including IEEE 802.1 and IEEE 802.15.4 operate at ISM band.
The current IEEE 802.15.6 standard defines three PHY layers, i.e., Narrowband (NB), Ultra wideband (UWB), and Human Body Communications (HBC) layers. The selection of each PHY depends on the application requirements. On the top of it, the standard defines a sophisticated MAC protocol that controls access to the channel. For time referenced resource allocations, the hub (or the coordinator) divides the time axis (or the channel) into a series of superframes. The superframes are bounded by beacon periods of equal length. To ensure high level security [8], the standard defines three levels: 1) level 0 -unsecured communication, 2) level 1 -authentication only, 3) level 2 -both authentication and encryption. In this paper, we briefly overview the PHY and MAC layers specifications together with the bandwidth efficiency of IEEE 802.15.6 standard for different frequency bands and data rates. We also discuss the security paradigm of the standard.
The rest of the paper is organized into three sections. Section I discusses WBAN applications targeted by the standard. Section II presents the PHY and MAC layers specifications. This section also presents the bandwidth efficiency and the security paradigm of the standard. The final section concludes our work with useful remarks.

II. TARGET APPLICATIONS
The WBAN applications targeted by the IEEE 802.15.6 standard are divided into medical and non-medical applications as given in Fig. 2. Medical applications include collecting vital information of a patient continuously and forward it to a remote monitoring station for further analysis. This huge amount of data can be used to prevent the occurrence of myocardial infarction and treat various diseases such as gastrointestinal tract, cancer, asthma, and neurological disorder. WBAN can also be used to help people with disabilities. For example, retina prosthesis chips can be implanted in the human eye to see at an adequate level. Non-medical applications include monitoring forgotten things, data file transfer, gaming, and social networking applications. In gaming, sensors in WBAN can collect coordinates movements of different parts of the body and subsequently make the movement of a character in the game, e.g., moving soccer player or capturing the intensity of a ball in

A. PHY Layer Specification
As mentioned earlier, the IEEE 802.15.6 supports three different PHYs, i.e., NB, UWB, and HBC. preamble helps the receiver in the timing synchronization and carrier-offset recovery. It is the first component being transmitted. The PLCP header conveys information necessary for a successful decoding of a packet to the receiver. The PLCP header is transmitted after PLCP preamble using the given header data rate in the operating frequency band. The last component of PPDU is PSDU which consists of a MAC header, MAC frame body, Frame Check Sequence (FCS) and is transmitted after PLCP header using any of the available data rates in the operating frequency band. A WBAN device should be able to support transmission and reception in one of the frequency bands summarized in Table I. The table  further shows the data-rate dependent modulations parameters  Fig. 4 shows the UWB PPDU that contains a Synchronization Header (SHR), a PHY Header (PHR), and PSDU. The SHR is composed of a preamble and a Start Frame Delimiter (SFD). The PHR conveys information about the data rate of the PSDU, length of the payload and scrambler seed. The information in the PHR is used by the receiver in order to decode the PSDU. The SHR is formed of repetitions of Kasami sequences of length 63. Typical data rates range from 0.5 Mbps up to 10 Mbps with 0.4882 Mbps as the mandatory one.

3) Human Body Communications PHY (HBC): HBC PHY operates in two frequency bands centered at 16 MHz and 27
MHz with the bandwidth of 4 MHz. Both operating bands are valid for the United States, Japan, and Korea, and the operating band at 27MHz is valid for Europe. HBC is the Electrostatic Field Communication (EFC) specification of PHY, which covers the entire protocol for WBAN such as packet structure, modulation, preamble/SFD, etc. Fig. 5 describes the PPDU structure of EFC that is composed of a preamble, SFD, PHY header and PSDU. The preamble and SFD are fixed data patterns. They are pre-generated and sent ahead of the packet header and payload. The preamble sequence is transmitted four times in order to ensure packet synchronization while the SFD is transmitted only once. When the packet is received by

B. MAC Layer Specification
In IEEE 802.15.6, the entire channel is divided into superframe structures. Each superframe is bounded by a beacon period of equal length. The hub selects the boundaries of the beacon period and thereby selects the allocation slots. The hub may also shift the offsets of the beacon period. Generally, the beacons are transmitted in each beacon period except in inactive superframes or unless prohibited by regulations such as in MICS band. The IEEE 802.15.6 network operates in one of the following modes.
1) Beacon mode with beacon period superframe boundaries: In this mode, the beacons are transmitted by the hub in each beacon period except in inactive superframes or unless prohibited by regulations. Fig. 6 shows the superframe strucutre of IEEE 802.15.6, which is divided into Exclusive Access Phase 1 (EAP1), Random Access Phase 1 (RAP1), Type I/II phase, Exclusive Access Phase 2 (EAP 2), Random Access Phase 2 (RAP 2), Type I/II phase, and a Contention Access Phase (CAP). In EAP, RAP and CAP periods, nodes contend for the resource allocation using either CSMA/CA or a slotted Aloha access procedure. The EAP1 and EAP2 are used for highest priority traffic such as reporting emergency events. The RAP1, RAP2, and CAP are used for regular traffic only. The Type I/II phases are used for uplink allocation intervals, downlink allocation intervals, bilink allocation intervals, and delay bilink allocation intervals. In Type I/II phases, polling is used for resource allocation. Depending on the application requirements, the coordinator can disable any of these periods by setting the duration length to zero.
2) Non-beacon mode with superframe boundaries: In this mode, the entire superframe duration is covered either by a type I or a type II access phase but not by both phases.
3) Non-beacon mode without superframe boundaries: In this mode, the coordinator provides unscheduled Type II polled allocation only.
The access mechanisms used in each period of the superframe are divided into three categories: 1) Random access mechanism, which uses either CSMA/CA or a slotted Aloha procedure for resource allocation, 2) Improvised and unscheduled access (connectionless contention-free access), which uses unscheduled polling/posting for resource allocation, and 3) Scheduled access and variants (connectionoriented contention-free access), which schedules the allocation of slots in one or multiple upcoming superframes, also called 1-periodic or m-periodic allocations. These mechanisms are comprehensively discussed in the standard. Here we explain the basic procedures of the CSMA/CA protocol defined in the standard. In CSMA/CA, a node sets its backoff counter to a random integer number uniformly distributed over the interval [1,CW ] where CW ∈ (CW min , CW max ). The values of of CW min and CW max vary depending on the user priorities. The node starts decrementing the backoff counter by one for each idle CSMA slot of duration equal to pCSM ASlotLength. The data is transmitted when the backoff counter reaches zero. If the channel is busy because of a frame transmission, the node locks its backoff counter until the channel is idle. The CW is doubled for even number of failures (when the node fails to receive an acknowledgement or group acknowledgement) until it reaches CW max . Fig. 7 shows the CSMA/CA procedure defined in the IEEE 802.15.6 standard. In RAP1, the node first waits for SIF S = pSIF S duration and then unlocks the backoff counter until it reaches zero where the data transmission starts. But the node fails to receive an acknowledgement and the contention fails. According to the standard, the CW is not doubled for odd number of failures and therefore it remains unchanged. In CAP, the node sets the backoff counter to 5 and locks it at 2 since the time between the end of the slot and the end of the CAP is not enough for completing the data transmission and the Nominal Guard Time, represented by GT n . The backoff counter is unlocked in the RAP2 period. Again the node fails to receive an acknowledgement and the contention fails. The CW gets doubled (for even number of failures) and the backoff counter is set to 8. Once the data transmission is successful, the CW is set to CW min . Further details about the CSMA/CA procedure can be found in the standard [3].
To measure the spectral utilization of IEEE 802.15.6 when using CSMA/CA procedure, we analyze the bandwidth efficiency for different frequency bands and data rates. The bandwidth efficiency is inversely proportional to the basic data rate. The following assumptions are considered during the calculations. 1) Bit Error Rate (BER) is zero, 2) The channel is perfect with no losses due to collisions, 3) The node always has a packet to send, 4) There are no packet losses due to buffer overflow. Fig. 8 presents the bandwidth efficiency as a function of payload size. It can be seen that the efficiency increases as we increase the payload size, i.e., it is 83.6% for 187.5 Kbps and 69.4% for 971 Kbps, respectively. These results can help the application protocol designer to see the effects of the payload size on the bandwidth efficiency and can be used to minimize jitter in multimedia applications. Detailed analysis can be found in [9].

C. Security Paradigm
The standard defines the following three levels of security. Each security level has different security properties, protection levels and frame formats.
1) Level 0 -unsecured communication: This is the lowest security level where data is transmitted in unsecured frames. There is no mechanism for data authentication and integrity, confidentiality and privacy protection, and replay defense.
2) Level 1 -authentication only: This is the medium security level where data is transmitted in secured authentication but is not encrypted. The confidentially and privacy is not supported by this mode.
3) Level 3 -authentication and encryption: This is the highest security level where data is transmitted in secured authentication and encryption frames. It provides solutions to all of the problems not covered by the level 0 and level 1.
The required security level is selected during the association process, i.e., when a node is joining the network. For unicast communication, a pre-shared Master Key (MK) or a new key (established via unauthenticated association) is activated. Then a Pairwise Temporal Key (PTK) is established, which is used once per session. For multicast communication, a Group Temporal Key (GTK) is shared with the corresponding multicast group. The whole security structure is given in Fig.  9.

IV. CONCLUSION
This paper presented a brief overview of the new IEEE 802.15.6 standard. We studied the PHY and MAC layers specifications and identified their key points. In addition, we analyzed the bandwidth efficiency of the standard for CSMA/CA procedure. The efficiency results were presented for different frequency bands and data rates. We observed that increase in the payload size improves the bandwidth efficiency. We also highlighted different security modes of the standard. This paper can be used to quickly understand the key concepts of IEEE 802.15.6 without reading the whole standard.


extfieldsofstudy:
Engineering
Computer Science

text:
Threat-aware path planning in uncertain urban environments

This paper considers the path planning problem for an autonomous vehicle in an urban environment populated with static obstacles and moving vehicles with uncertain intents. We propose a novel threat assessment module, consisting of an intention predictor and a threat assessor, which augments the host vehicle's path planner with a real-time threat value representing the risks posed by the estimated intentions of other vehicles. This new threat-aware planning approach is applied to the CL-RRT path planning framework, used by the MIT team in the 2007 DARPA Grand Challenge. The strengths of this approach are demonstrated through simulation and experiments performed in the RAVEN testbed facilities.

I. INTRODUCTION
Whether driving on highways or navigating in the middle of a battlefield, intelligent vehicles must be able to quickly and robustly compute motion plans in very uncertain worlds. The sources of this uncertainty may be internal, i.e., incomplete or imperfect knowledge of the vehicle model, or external, i.e., incomplete or imperfect knowledge of the environment, and may be present either in sensing or in predictability [1]. This paper addresses problems involving uncertainty in predictability, and in particular the intentions of the other vehicles within our vehicle's world.
To make meaningful predictions of other vehicles' intentions, a smart vehicle should be able to gather information from the environment to build models approximating those intentions. It is not safe to assume that all drivers obey all "rules of the road," as many collisions occur when this is not the case, but classifying all other vehicles as hostile would be overly conservative. The information gathered by our vehicle might include onboard camera images, radarbased measurements of surrounding objects, or messages intercepted or shared on some communication channels.
The vehicle planner must be able to address the uncertainty in each vehicle's future state and actions, or at a higher level, the behavior / intent governing those actions. Existing path planners typically rely on a priori information to generate trajectories, applying reactive maneuvers or replanning as needed to correct the path online and maintain feasibility. However, uncertainty in object predictability is typically not considered explicitly in the global path planner. Instead, moving vehicles are often assumed to follow known trajectories or policies, which the planner reacts to locally. While full probabilistic representation of the environment is possible, such as with POMDPs [2], [3], the corresponding solution techniques are computationally intractible for real-time path planning problems of even modest complexity or dimension. Recently, sampling-based techniques such as rapidlyexploring random trees (RRTs) [4] have been extended to incorporate motion patterns for moving obstacles learned offline via Gaussian processes [5]. However, these patterns may not be sufficient to capture all possible unexpected behaviors, which are usually the main reason behind collisions.
The main motivation of this work is the set of challenges faced by autonomous vehicles in the 2007 DARPA Grand Challenge (DGC) [6], which involved navigating an outdoor urban environment in the presence of other vehicles while obeying all traffic regulations. One of the main challenges of this race was negotiating traffic intersections, where several vehicles were involved in collisions or near-collisions. Several explanations have been offered for these occurrences, but the one that motivated this work is the inability of the autonomous vehicles to anticipate the intent of other vehicles [7]. With some knowledge of those intentions, the motion planner could incorporate the risk posed by those vehicles when considering potential trajectories, improving safety. This paper introduces a new framework for autonomous vehicles which enables path planning algorithms to explicitly incorporate both obstacle uncertainty and the corresponding risk posed to the vehicle. A threat assessment module, consisting of an intention predictor and a threat assessor, augments the host vehicle's path planner with a real-time threat value for each potential trajectory, reflecting the risks posed by the estimated intentions of other vehicles. The strengths of this approach are demonstrated through simulation and experiments performed in the MIT RAVEN facility [8].
II. PROBLEM STATEMENT Consider the autonomous system denoted by HV, where s is the state and u is the control input; we have that s is constrained to the state space S, s ∈ S, while u is contstrained to the control space U, u ∈ U. Our objective for safe motion planning is to minimize some desired cost functional over the duration of the motion, Of the many constraints C might include, we are interested in those necessitating collision avoidance with N other vehicles, denoted here as OV i , i = 1 . . . N . These can typically be written in the form where r i (t) is the state of vehicle i at time t, p s (t) is the position vector corresponding to s(t), p ri (t) is the position vector corresponding to r i (t), is the minimum allowed distance between the HV and the OVs, and t f = t 0 + T h where T h is the time horizon of interest. We say that HV is in collision with OV i if the tuple (p s (t), p ri (t)) enters the closed "collision" set Ω i , In uncertain and/or non-cooperative environments, r i (t) is typically not available for the HV. For HV to maintain guaranteed safety, some mechanism must be able to identify the input sequence u(t) which yields a feasible path for all possible realizations of r i (t), i = 1 . . . N . In the event that no such path exists, the same mechanism should select u(t) in order to minimize some threat level. Here we define the threat level T i for vehicle i as inversely proportional to t ci , the earliest possible time of collision between HV and OV i : Equation (4) thus cannot typically be guaranteed at all times, so this constraint is instead converted to a penalty in the objective function. We define the new cost functional where L is defined in (2), T i is the threat level defined in (6), and w is a user-selected weighting factor representing the tradeoff between safety and optimality. The constraints (4) are then removed from (3), yieldinḡ Problem Definition (Threat-Aware Dynamic Motion Planning): Given a state space S, a control space U, an initial state s 0 ∈ S and a final state s f ∈ S, compute the control input sequence u(t), t ∈ [0, t f ], t f ∈ [0, ∞) that minimizes (7) subject to the constraints (1) and (8).
III. THREAT-AWARE PATH PLANNING Several global path planners, including sampling-based planners, use the philosophy that collision detection should be done in a "black box" which decouples the host vehicle's path planning from any specific geometric or kinematic obstacle models [9]. This paper proposes that threat assessment should be done in a similar "black box" framework, providing planners with a quantitative threat metric to identify safer paths during trajectory generation. This threat assessment considers the unknown intentions of moving OVs, which may present a collision risk for the HV.

A. High-level TAM Architecture
The proposed architecture features a threat assessment module (TAM, Figure 1), consisting of an intention predictor (IP) and a threat assessor (TA). The IP uses observations taken by the HV of the OVs to make predictions of their intentions. Instead of using low-level reasoning to predict future trajectories, the IP uses higher-level logic and learning to provide the planner with predicted future intentions, key to earlier and more accurate prediction of future collisions. The TA then converts this prediction into a set of potential paths for the OV, and returns a threat value that a candidate trajectory u(t) (or equivalently, s(t)), t ∈ [t 0 , t f ] for HV incurs in the vicinity of these potential paths. As a result, the planner generates paths that are threat-aware by construction, thus improving the vehicle's reactive behavior.
Several distinct representations have been proposed to model intentions for humans and autonomous systems; here we adopt the Ecological Recogniser architecture introduced by [10]. Using the language of [10], the HV is the recognising agent, while each OV is an intending agent. We follow the abstract definition that these intentions are directly responsible for the actions executed by the intending agents. Intentions may be desired plans (e.g., following a straight path) or other high level intentional states (e.g., not following the rules of the road). Let the M -vector b i denote the intention vector of OV i ; the j th entry b j i corresponds to the belief OV i is operating under the jth intention. The cost functional (7) is then modified to embed the intention information, where T ij is the threat value of the trajectories followed by OV i as a realization of its j th intention; note that i ∈ {1 . . . N } and j ∈ {1 . . . M }.

B. Agent Model
Each agent is modeled using the standard bicycle model where (x, y) is the rear axle position, v is the forward speed, θ is the heading, L is the wheelbase, a is the forward acceleration, and δ is the steering angle (positive counterclockwise). The state of the vehicle is s = (x, y, θ, v) ∈ S, while the input is u = (δ, a) ∈ U, including the constraints a min ≤ a ≤ a max and |δ| ≤ δ max . Each admissible control sequence u : [0, t f ] → U is piecewise constant.
In the work that follows, we make several assumptions to constrain the focus on the uncertainty in the prediction of obstacles or other agents. We assume that the current states and models of the HV and the OVs are perfectly known by the HV within a detection radius (Section V-C), and that all sensor measurements are noise-free. Additionally, the path planner is provided with a complete map of the environment a priori, excluding any dynamic obstacles or agents.
IV. DEVELOPED ALGORITHMS This section describes the implementation of the IP and TA components of the TAM and the resulting threat-aware path planner, using closed-loop rapidly exploring random trees (CL-RRT), into which they are embedded.

A. Intention Predictor (IP)
The Ecological Recognizer architecture [10] that the IP adopts has two key components: a pattern matcher and a reasoning module. The pattern matcher is a classifier that is trained offline to recognise different possible intentions by observing agent states, and operates online by giving a continuous estimate of the intentions over time. The reasoning module filters these estimates of intentions, along with knowledge of previous encounters with the agent, to give a final estimate of the intention vector b.
Here we are interested in estimating the intentions of human vehicles in urban environments, specifically near intersections. This Ecological Recognizer implementation is based on an approach previously developed and demonstrated by the authors in simulation [11] for classifying agent intentions using support vector machines (SVM) and Bayesian filtering (BF). The human driver intention classification problem is very complex, due to the various nuances of human behaviors. SVM is suitable for the IP because it has been shown to be both robust and efficient for classification problems [12], such as lane-change detection [13].
The IP design consists of an SVM combined with a Bayesian filter that uses the SVM outputs over a specific time period to compute the intention vector b. SVM-BF also includes a threshold detector, such that the final vector b is a unit basis vector specifying the most likely intention according to the threshold value [11]. Based on experimenting with different combinations of kernel functions and features, the best results were obtained using the Gaussian radial basis function and combining the following three features: 1) the relative distance between the OV i and the entrance of the intersection it is approaching, 2) the speed of the OV i , and 3) the longitudinal acceleration of the OV i . Note that the SVM-BF algorithm is only activated when the distance between the OV i and the HV is within some detection radius, and both vehicles are approaching the same intersection.

B. Threat Assessor (TA)
The threat-aware CL-RRT algorithm (Section IV-C) incorporates the computation of a threat value for each candidate trajectory it generates, given knowledge of the current Algorithm 1 Intention-based Threat Assessment 1: T i ← 0 ∀i 2: for each agent OV i do 3: Reach-Set ← Compute-Intention-Reachability (b i ) 4: for each intention e j with probability b j i do 5: T i ← T i + b j i · Compute-Threat(Reach-Set,OV i , e j ) 6: end for 7: end for 8: return max i=1...N T i Algorithm 2 Compute-Threat (Reach-Set, OV, e) 1: for each path path k in Reach-Set ending in region of intention e do 2: t k ← compute earliest time of collision of path k with HV within time horizon T h 3: T k ← 1 t k 4: end for 5: return max k T k OV states. We propose an approach, detailed in Algorithm 1, that combines a fast sampling-based reachability method with intention prediction information provided by the IP (Section IV-A) to efficiently estimate the threat level.
The threat assessor has a finite time horizon, limiting the HV lookahead horizon for possible future OV paths, in order to focus computation on imminent threats. The choice of horizon length is domain-specific, but should allow the HV sufficient time to react in a dynamic environment. The Threat-Assessor algorithm (Algorithm 1) begins by calling the Compute-Intention-Reachability (CIR) subroutine, discussed below, to create the reachability set for each OV i . The resulting sets are biased based on the perceived intentions of the OVs. For each intention e j of each OV i , Algorithm 2 is called to compute the threat incurred by the HV trajectory in the region reached by the paths corresponding to e j . Note that the earliest time to collision is converted into a threat value using (6) (line 3 of Algorithm 2). This value is weighted by the probability b j i provided by the IP. Finally, the threat is computed as the maximum value of all threats created by each OV i (line 8 of Algorithm 1).
The CIR algorithm (detailed in [14]) is also based on the CL-RRT algorithm, but uses the resulting tree only for simulation of the different possible paths of a OV (which is not controlled by the operator). No best path is selected, but rather the entire tree is biased towards regions corresponding to the learned intentions of the OVs. This biasing is achieved by devoting a portion of the tree samples to regions corresponding to the intention e j , with remaining samples being taken uniformly throughout the environment. The algorithm also includes time-parametrization extensions (introduced in [15]) that tailor the RRT algorithm to the efficient computation of intented paths by the OVs.

C. Threat-Aware CL-RRT Planner
In this section, we present a global threat-aware planner which builds on the CL-RRT implementation developed for MIT's Talos vehicle in the 2007 DGC competition [16]. The CL-RRT algorithm extends the rapidly-exploring random tree (RRT) algorithm [4], [9], which grows a tree of dynamically feasible trajectories by randomly sampling points toward which the tree is extended. The CL-RRT algorithm adds a path-tracking control loop in the vehicle prediction model, such that sampling takes place in the reference input space rather than in the vehicle input space. The algorithm thus maintains the exploration bias of traditional RRT algorithms, while allowing for generation of smooth trajectories more efficiently. Furthermore, because the RRT algorithm is sampling-based, the quality of the planning tree and resulting paths are scalable with the available computational resources. Please refer to [16] for a detailed description of the CL-RRT planner, and [6] for an explanation of the planner integration in the Talos system architecture.
The proposed threat-aware planner is shown in Algorithm 3. The main addition is the threat computation in lines 6 and 10. This computation calls Algorithm 1 to efficiently calculate the threat of colliding with the possible paths of the other OVs (Section IV-B). Whereas the original CL-RRT heuristic identifies nearest nodes based on path duration (in the Dubins sense), we extend this heuristic to also include the threat value (line 6). In line 10, the threat along the edge to a new node is computed and stored at the new node. The best path is then chosen in accordance with the cost defined in (9) (line 15 of Algorithm 3), which includes both the total time to the goal and the threat along the trajectory. These modifications embed the threat computation in the CL-RRT trajectory generation, leading to the selection of safer paths which are threat-aware by construction.
Another related addition is the use of threat propagation logic. First, the root node is initialized to have zero threat. When adding a new node, if the path from the selected node (initially the root) to the new node incurs a non-zero threat (computed using Algorithm 1), then an intermediate node is created at the location of the earliest collision, and both the intermediate node and the new node inherit the computed threat value. Note that if a node with a non-zero threat value is chosen to be expanded, the new node inherits that value and no new threat computation is required. The rationale is that the threat value does not decrease along an edge connecting a node with non-zero threat to its child (recall (6)). A useful property of the threat heuristic is that it is admissible: it underestimates the "true" cost. This is due to the sampling-based nature of the CIR algorithm, which underapproximates the earliest time of collision, as well as the assumption that children nodes inherit the threat value of their parent if the value is non-zero. Before choosing a best path, the threat values of the tree are updated from the bottom up (i.e., starting from the leafs) by reassigning each parent's threat value to be the minimum of the threat of its children, and so on, until the root is reached.

V. EXPERIMENTAL RESULTS
This section presents experimental results which validate the effectiveness of the threat-aware CL-RRT algorithm, augmented with the TAM, in enabling an autonomous vehicle to successfully identify and avoid an errant human-driven vehicle under real-world uncertainty. These results focus on Algorithm 3 Threat-Aware CL-RRT 1: repeat 2: Measure current vehicle states and environment 3: Propagate states by computation time limit 4: repeat 5: Generate sample for the input to controller 6: Sort nodes in tree using threat and time heuristics 7: for each sorted node do 8: Form controller input by drawing line from node to sample, then propagate 9: if propagated portion is collision free then 10: Compute threat of propagated portion (Algorithm 2) 11: Add sample to tree break 12: end if 13: end for 14: until time limit is reached 15: Choose best path and repropagate from current states 16: if repropagated trajectory is infeasible then 17: Remove infeasible portion from tree and go to line 15 18: end if 19: Send best path to controller 20: until vehicle reaches target the challenging task of avoiding collisions at intersections, in particular with errant drivers who do not observe a stop sign and enter the intersection out of turn.
First, a brief overview of the experimental infrastructure is provided. Next, we present a subset of hardware results showing the interaction between an errant human driver and an autonomous vehicle at intersections; additional experiments can be viewed in the video attachment or at http://acl.mit.edu/IROS10TAM.mp4. Further experiments and infrastructure details are given in [14].

A. Hardware
Hardware demonstrations were performed in the Real-time indoor Autonomous Vehicle test ENvironment (RAVEN) [8], a testbed which uses motion-capture cameras to provide high-fidelity vehicle state data. We have constructed a representative road network within the RAVEN testbed, including many intersection types and road signs, to emulate a realistic driving environment ( Figure 2).
All vehicles in this experiment use the iRobot Create platform [17], a skid-steered vehicle, modified with a software wrapper to emulate traditional automotive steering (10). Each experiment consists of 1 or 2 autonomous vehicles and 1 human-driven vehicle. The autonomous vehicles are controlled through an off-board wrapper which receives waypoints from the threat-aware CL-RRT software (Section V-B) and steers using pure pursuit [18]. The human-driven vehicle is controlled through a wireless steering wheel [19], including acceleration and brake pedals. A human driver may steer their vehicle through simple visual inspection, or via an onboard dual-camera ( Figure 2) interface which emulates the first-person driving perspective (Figure 3). This interface includes a real-time "GPS" display, which guides the driver through an intended sequence of waypoints (Section V-B).

B. Software
The planning software consists of two primary modules, discussed below. The navigator module accesses an abstract  representation of the road network and selects sequences of waypoints, yielding the current goal location for the vehicle. The CL-RRT motion planning module then uses local knowledge of the environment (e.g., obstacles, terrain, and other agents), including the TAM, to plan dynamically feasible paths to this goal.
The navigator module leverages a sparse representation of the RAVEN road network (Figure 4), constructed using the Route Network Data File (RNDF) specification from the 2007 DGC [20]. As the RNDF represents the traversability graph, an A * implementation is used to select the shortestdistance waypoint path in the graph between the current and desired waypoints, respecting lane directionality constraints [6]. As the vehicle (whether human or autonomous) approaches each intermediate or desired waypoint, the navigator selects the next waypoint on the list as the new target. An arbitrary list of desired waypoints is provided for each vehicle; the ultimate objective is to observe the vehicles' interactions at intersections.
The threat-aware CL-RRT algorithm (Algorithm 3) is implemented as an offboard, multi-threaded Java application, designed to support arbitrary vehicle and environment models in both simulation and hardware. The CIR algorithm [14] is embedded in this offboard planner as a separate thread which runs asynchronously for each OV. Over fixed time intervals (2s), the algorithm grows a new reachability tree based on the current OV position in RAVEN. At the end of each time interval, the reachability tree is relayed to the host RRT thread, which then relays it to the TA algorithm (Section IV-B). Figure 4 shows the display representation generated by the application. Fig. 4. Display view of the RAVEN road network for the host vehicle (blue chevron, path history in blue). The host uses the CL-RRT tree (brown edges, green nodes) to identify the best known path (red edges, black nodes) to the current waypoint (purple). This path should avoid all obstacles (black boxes), the human-driven vehicle (green circled chevron) and, if active, their reachability tree (yellow edges, orange nodes). The other autonomous vehicle is represented as the car-sized rectangle at bottom-center.

C. Results
The results below demonstrate the threat-aware closedloop RRT algorithm in the context of stopping at intersections. In each experiment, one human-driven vehicle and one or two autonomous vehicles are navigating through the RAVEN road network simultaneously. The human driver may choose to not stop at an intersection and instead enter it out of turn, violating the rules of the road. The human driver's intent is classified as either good or errant, based on whether or not they correctly approach the intersections. The objective of the autonomous vehicle(s) is then to not only avoid all collisions, but also minimize the risk of collision with an errant human driver in intersections.
The human-driven vehicle is perceived to be a threat if three conditions are satisfied: (1) the IP module has classified the drivers' behavior as errant; (2) the errant driver is within the host vehicle's detection radius ( Figure 4); and (3) both vehicles are approaching the same intersection. In this case, the autonomous vehicle is to avoid that vehicle's reachability tree constructed by the CIR algorithm; otherwise the reachability tree is not an active constraint.
Over the course of this experiment set, 20 intersection encounters occurred: 10 with one autonomous vehicle in the network, and 10 with two autonomous vehicles in the world. Of these encounters, only one resulted in a collision; in this case, the human-driven vehicle aggressively approached the autonomous vehicle, which had already stopped to avoid it. Figure 5 demonstrates two particular scenarios in which the human-driven vehicle interacts with an autonomous vehicle at an intersection. In Scenario 1 (Figure 5(a)-(c)), both vehicles are attempting to enter the same lane, with the human-driven vehicle approaching from the left and making a right turn, and the autonomous vehicle approaching from the right and making a left turn. The autonomous vehicle arrives first and, observing (through the IP) that the human driver is decelerating, plans a path through the intersection ( Figure 5(a)). After entering the intersection, however, the IP module detects the human driver accelerating, as if it will enter the intersection out of turn. The IP module classifies this behavior as errant, and thus the TA module seeks to minimize the corresponding threat level T . Though the autonomous vehicle cannot avoid the reachability tree's outer reaches, it does avoid the inner nodes (where the time to collision is lower) by quickly coming to a stop ( Figure 5(b)).
Once the errant driver is no longer a threat, the autonomous agent finishes crossing the intersection ( Figure 5(c)). In Scenario 2 ( Figure 5(d)), the autonomous driver is making a left turn, while the human-driven vehicle is crossing the intersection (from left to right in the figure). Here, the human-driven vehicle has correctly come to a stop at the intersection, and the IP module has classified it as a good driver. Unlike Figure 5(b), the autonomous driver then proceeds through the intersection, perceiving that the human driver is likely to obey the rules.

VI. CONCLUSION
This paper has introduced a new approach for path planning in urban environments subject to uncertainty in the intentions of other vehicles. This work combines an intention predictor (IP) and a threat assessor (TA) to create a threat assessment module (TAM), embeddable in path planning algorithms, which runs efficiently and is suitable for realtime implementation. The IP uses high-level logic based on the Ecological Recogniser, while the TA uses sampling-based techniques to efficiently compute reachable future paths for surrounding vehicles. Using TAM applied to the CL-RRT planner, an autonomous vehicle can successfully identify and avoid an errant driver in realistic intersection scenarios, as demonstrated through hardware results.