Michel Buffa
email: michel.buffa@univ-cotedazur.fr

Laurent Pottier
email: laurent.pottier@univ-st-etienne.fr

Shihong Ren
email: shihong.ren@univ-st-etienne.fr

Yang Yu
email: yuyang@shcmusic.edu.cn

Yang Yu Making

Making Computer Music on the Web with JSPatcher

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

INTRODUCTION

JSPatcher is a web-based visual programming language (VPL) originally designed for providing a user interface (UI) for Web Audio API. 1 Since the API describes the audio processing flow as a graph of DSP nodes, it is convenient to have a patcher editing system [START_REF] Puckette | ªThe patcher,º in Proceedings of the International Computer Music Conference. San Fran-15 The[END_REF] to manipulate the audio graph. JSPatcher is initially a WebAudio patcher editor that runs in a browser, where users can create boxes representing the DSP nodes and cables representing the connections in a canvas.

Since the whole JSPatcher platform is mainly developed in TypeScript and compiled to JavaScript which is the scripting language for the Web API, we have the possibility to fully import the language it self to the patcher system. Thus, in addition to the audio connection layer, in order to control DSP parameters with non-audio data, we added a dataflow layer that can distribute events between functions in real time. In this layer, various functions imported from the web environment, including JavaScript language built-ins and Web APIs, are available. These can be used to access the browser's high-level APIs, such as those for managing mouse and keyboard events, battery life or computer peripherals.

With these two layers in a single imperative patcher, the usage becomes similar to some VPLs available on native platforms like Max or PureData, while offering more flexible computational possibilities, taking advantages from the web community, as most of the JavaScript packages can be imported and used as functional boxes in a patcher. An additional patcher interpretation mode, FAUST compiled patcher, has also been developed to facilitate DSP design under the WebAudio AudioWorklet specification [START_REF] Choi | ªAudioworklet: the future of web audio[END_REF].

The FAUST [START_REF] Orlarey | ªFAUST : an Efficient Functional Approach to DSP Programming[END_REF] language ecosystem is used to transform patchers under a specific mode into FAUST code which can be compiled to a customized DSP. This kind of can be used in imperative patchers as a special WebAudio node called AudioWorkletNode that can be connected with other WebAudio nodes. With this interpreter, some Max's Gen patchers can also be interpreted to FAUST code and be compiled in the same way in JSPatcher.

These new features make JSPatcher not only a utility to interface graphs from the Web Audio API, but also an integrated development environment (IDE) for data computation and audio processing on the web. Various possibilities related to music composition and performance are thus open for exploration on the platform.

The following sections will present the improvements made to JSPatcher that contain important features for modern computer music practices, including a file manager, audio buffer manipulation, audio plugin support and computer-assisted composition functions.

FILE MANAGER

Concept

One major limitation of the web environment is the access to the device's local files due to security reasons. According to the current web standards, web applications do not have permissions by default to read local files unless users explicitly allow them. The lack of a proper file manager API makes any web application difficult to maintain the structure of a file-based project.

To support sub-patchers and audio file manipulation in Figure 1. JSPatcher with a file manager JSPatcher, we had to design a virtual file system in the browser that allows the following operations:

1. Make the file system persistent after closing the application, 2. Upload files from the user's machine, 3. Create new files, 4. Delete files, 5. Copy or move files, 6. Access file data using its path. Designing and implementing a persistent file storage system is a challenge in this work as there are few ways to keep reusable data in the browser. Our solution relies on IndexedDB,2 a technology for client-side storage of significant amounts of structured data. Normally, in 2022 and on a desktop browser, up to two gigabytes of storage quota are available in the IndexedDB per site group, 3 . It is sufficient for any lightweight project. We also use BrowserFS, a JavaScript module that can store persistently a whole structured file system into the IndexedDB and provide a JavaScript API for file management [START_REF] Vilk | ªDoppio: Breaking the Browser Language Barrier[END_REF][START_REF] Powers | ªBrowsix: Bridging the Gap Between Unix and the Browser,º in Proceedings of the Twenty-Second International Confer[END_REF].

To accelerate file reading and writing in runtime, we also built a higher-level file system that caches the file tree structure and data in memory. It acts as a bridge between the BrowserFS and the UI, when a change is made by the user to the file system, it calls the BrowserFS to store new change in IndexedDB; meanwhile, all event subscribers to the changed file, such as the file manager UI (Figure 1), file editors or audio players will be alerted and they can react in real time.

Temporary File System

Along with the persistent file system in IndexedDB, we also implemented another memory-only file system for temporary entries. It is internally a label and file content map with event emitters and an observation mechanism.

The purpose of the temporary file system is to allow users to create memory spaces and use them with an associated name just like a persistent project file. A similar behavior exists in Max. For example, when a user defines an audio buffer using a name that doesn't refer to a file from the hard disk, the system will allocate a part of the memory that is temporarily accessible with this name. Any object that uses the same name will then refer to the same part of the memory. When every object associated with this name is removed, the memory will be freed and erased.

In JSPatcher, this behavior is implemented by the temporary file system in which every file is under the root directory. We have provided an API for objects to create temporary files when a name cannot be resolved as a persistent file. Meanwhile, the object becomes an observer of the temporary file. When the last observer gets removed, the temporary file will automatically free the memory space and remove itself.

File Structure of a Project

In JSPatcher, a project is a folder that contains subfolders or files in any format as in native operating systems. When a session is started, the project folder will automatically be initialized with a hidden file named .jspatproj under the root folder. This file contains metadata related to the project such as its name, its author, its dependencies and will be saved with the whole project.

Typically, a project will have one or multiple patchers with some asset files. To distinguish patchers under different modes, we use .jspat as the extension for regular imperative patcher, and .dsppat for FAUST compiled patcher. Patcher files can be uploaded to the file system or downloaded (exported) from it. Users can also upload or download the whole project for further exchange under the .zip format with every file compressed inside.

Usage in Patchers

Some types of project files can be recognized by JSPatcher and can be loaded into patchers. Typically, they will be used in a JavaScript patcher (using imperative and WebAudio layers) by different box objects. To load a specific file, the user should put the file path in Unix format (using slash for sub-directory) relative to the project root folder.

Table 1 shows a list of file types that can be loaded by box objects in a patcher. Figure 2 shows a sub-patcher file, an audio file, a text file and an image file in a patcher.

AUDIO EDITING

Concept

Different kinds of web-based audio editors or digital audio workstations (DAW) have been developed by the community in recent years to bring desktop audio production experience on the web platform. However, for a long period, due to the inconsistent implementation of the Web Audio API between different web browsers, it has been hard to maintain related projects and ensure the same user experience across browsers and devices. Support for the AudioWorklet API on Safari Desktop and iOS browsers was added in April 2021, which as the final step in providing full Web Audio API coverage on all major browsers. Also, the Web Audio API version 1.0 became, after ten years of maturation, a W3C recommendation (a frozen standard) in June 2021. These two events mark a milestone of the standard and its implementation process. It motivated developers to adapt Web Audio applications to the recommended standard without worrying about compatibility issues. The AudioWorklet API is important for audio editors or DAWs as buffer recording, looping, editing regions require sample-accurate controls over the input signal and can be done in a customized DSP through the API.

In JSPatcher, using the recent API, two features related to audio files were added. Audio files can now be edited in non-real time from a single-track audio editor and can be manipulated as an audio buffer in real time in a patcher.

Audio Editor

In the workflow for some genres of electronic music, especially musique concrète or interactive electroacoustic music, raw audio materials need to be cut and ªcleaned upº before being put into a DAW project or a program. This process requires a tool that can directly modify the audio file with the following features:

1. Visualize any part of the waveform with rulers, 2. Play any part of the audio clip, 3. Select on the waveform with sample-accuracy, 4. Record audio in-place or after the clip, 5. Cut, copy and paste any part of the clip, 6. Adjust the volume of the selected section, 7. Silent the selected section or insert silence of any length, 8. Perform a phase inversion or reverse the selected section, 9. Fade-in and fade-out of any length with a flexible curve, 10. Resample the audio to any sample rate, 11. Create, delete, reorder channels, up-mix and downmix (i.e., mix a stereo audio to a mono one), 12. Apply audio effects, 13. Export the audio in some formats. Its implementation in JSPatcher is a dedicated window that can be opened by double-clicking an audio file listed in the file manager. (Figure 1) When the user needs to open the editor, the system will firstly decode the given file to raw PCM data. Then, the data will be grouped into different levels of zoom that contain minimum and maximum values of each 16, 256, 4096 samples, etc. to optimize the waveform display for long audio files.

The layout of the editor's UI is similar to some desktop audio editors. A navigation bar with the waveform of the whole file is shown at the top of the window with a range of currently displayed and selected sections. Below the bar, a larger waveform viewer shows a section of the audio. Conventional features were implemented such as the cursor, the auto-scalable timing grid (vertical), energy (in dB) grid (horizontal), buttons to enable or disable channels for replay, fade-in and fade-out handlers, and an additional popup handler to adjust the gain when a section is selected.

Below the main viewer, a playback toolbar is presented. Users can play, pause or stop the playback from the cursor's position. Loop can also be enabled or disabled here. To record audio, users can choose an input device from a menu, enable the monitoring, and start recording using the red button.

At the bottom, a meter shows the current volume of the playing or the monitoring audio. A table with adjustable numbers shows the current displayed and selected section, and allows users to change it manually.

In the menu, a set of options are available to perform simple processing like silence, reverse, phase inversion, insert silence, resample, remix channels and export. To perform more complex processing using third-party DSPs, it is possible to load WebAudioModule (WAM) plugins [START_REF] Kleimola | ªWeb audio modules[END_REF][START_REF] Buffa | ªTowards an open web audio plugin standard[END_REF] into a plugin rack. Users can choose to process the whole audio file or only the selected part. We will present the WAM support in the next sections of the paper.

In the ªRemix channelsº option, users have access in a popup window to an I/O matrix to decide the number of outputs and how much volume of signals coming from original channels for the resulting audio. (Figure 3) Figure 3. ªRemix channelsº and ªBounceº options

The audio export (ªBounceº option) supports .wav, .mp3 and .aac formats with different sample rates or bit-rates thanks to a web implementation of ffmpeg4 through Emscripten5 compilation and WebAssembly. 6 7 (Figure 3)

Audio Buffer Manipulation in a Patcher

Audio buffer manipulation is a key feature for any audio programming environment like Max or JSPatcher, as real time audio projects like some interactive music pieces often need to record and replay audio clips during the performance.

In the previous section, we mentioned that the bufferõ bject can refer to any audio file in the project or can create any temporary audio clip in the memory. The audio editor is also available when the user double-clicks the object. In addition, the editor can be ªdockedº beside the patcher.

The buffer~object accepts 4 possible arguments. The first argument is the identifier of the audio file or a temporary audio clip. If it is temporary, users can initialize it by specifying the buffer's number of channels, length in samples and its sample rate.

In fact, the object is associated with a PatcherAudio API in which the audio buffer is stored with its waveform data, with a set of methods related to the buffer editing. A Bang (a triggering event) from the first inlet of the buffer~object will trigger output of the PatcherAudio API.

Users can connect the buffer~object to some other objects to use the PatcherAudio API. For example, the wave-form~object can display the waveform of the audio clip, bufferSource~object is a player that wraps the Buffer-SourceNode from the Web Audio API that accepts the PatcherAudio as the input and can play the audio with loop and different playback speed.

The PatcherAudio API provides necessary information getters like its number of channels, length and sample rate; and manipulation methods like split, concatenate, pick, paste, remove, insert, etc. Figure 4 shows an example of picking a section (from sample 24000 to 25000) of the existing buffer with 48000 samples. Due to the limitation of the web platform, native audio plugins such as VSTs cannot be used in a web application without installing additional native software. Thus, for web-based DAWs, the need arose for a new standard of WebAudio plugins, offering similar functionality to their native counterparts.

In 2015, the first version of the Web Audio Modules (WAM) [START_REF] Kleimola | ªWeb audio modules[END_REF] standard is created, primarily for native plugins developers to port their existing plugins to the web. In 2018, they joined forces with other groups of people working on interoperable Web Audio plugins and plugin hosts to synchronize their efforts toward the beginnings of an open standard called Web Audio Plugins (WAP) [START_REF] Buffa | ªTowards an open web audio plugin standard[END_REF][START_REF] Buffa | ªEmerging w3c apis opened up commercial opportunities for computer music applications[END_REF], covering a wider range of use cases. Recently, taking into account previous developments and the feedback received from developers over the past few years, a new version of the WAM standard has been created by emerging recent technological developments. Now, a WAM plugin can be fetched from the web using a URI, and be initialized using the current WebAudio context. The plugin comes with a standardized API that can create a UI, get or adjust parameters, schedule events like parameter automation or MIDI messages, and connect with other WAMs or native WebAudio nodes.

WAMs in the Audio Editor

The Audio Editor in JSPatcher has a dedicated effect ªrackº for WAMs. When the audio is loaded, the ªrackº is empty so that users can add WAMs from their URIs. The audio will be played and processed through a pre-gain, then through the ordered WAM effects, finally through a post-gain. Users can use the rack UI to add or delete WAMs or display the WAM's own UI. (Figure 5) Web Audio's OfflineAudioContext is an audio context that, instead of process audio in real time, generates audio data from a WebAudio graph as fast as it can. When a user needs to export the entire audio file rendered with effects, or to apply the effects in-place, we will use a copy of the current ªrackº in a new OfflineAudioContext to render the audio.

WAMs in Patchers

It is also important to be able to create interactive audio programs with WAMs in JSPatcher. Using the pluginõ bject, users can load WAMs via a URI into a patcher. When the plugin~receives a text string (as URI), it will remotely download the code from the URI and initialize it as a WAM. Then, it will automatically wrap the WAM and load its UI. Its inlets and outlets will be connectable with other WebAudio node objects. Additional inlets will be created to accept real time parameter change messages.

As WAMs support MIDI messages as input, the first inlet of the object accepts numbered arrays as MIDI event messages to the WAM inside. In addition, as WAMs have the ability to transmit non-audio events between each other, the patcher connection between two WAMs will be treated as a special one and make the necessary connection. Figure 6 is an example of a WAM loaded in a patcher with an audio player. Figure 6. WAM with an audio player in a patcher

COMPUTER-AIDED COMPOSITION

Context

Algorithmic composition often needs computer programs to calculate its musical representation. To design such a computer-aided composition (CAC) system for composers, visual programming and musical score display are two key features. OpenMusic, developed at IRCAM, shows the power of such a VPL in algorithmic composition with its composer-oriented design. The web environment, with its strong accessibility from device to device and flexibility from the UI perspective, is already a common platform for the low-code development system. It is likely to be highly suitable for a CAC system.

High-quality digital musical scores can be dynamically rendered and displayed on a computer using the SVG (Scalable Vector Graphics) format. Libraries like VexFlow, 8 Guido, 9 Verovio10 or abcjs 11 can render music scores on the web. However, not all of them provide an API to interactively deal with the musical structure (model) behind the score.

The challenge we are facing is a need for a JavaScriptcompatible musical model system that is able to:

1. Calculate and compose abstract music (like a MIDI file), 2. Play via WAM synthesizers, 3. Be displayed as a musical score. Therefore, we created a JavaScript library called Sol for the calculation of different musical concepts. 12 It aims to deal with the musical model issue in the web-based CAC system. Then, a WebAssembly version of Guido 13 is used to render the score as it provides the AR (Abstract Representation) API to easily convert the musical model to the score. Finally, these feature are integrated as a package 14into JSPatcher.

Musical Model

Musical notation is basically a representation of the musical structure based on a set of different musical concepts and a composition of instances of these concepts. To facilitate the CAC, the modeling of these concepts, or generally music theory, should be implemented in a digital way to allow the calculation between the musical concepts.

Yet, modern music theory is so complex and diverse that its modeling cannot be all-inclusive. The Sol library is only a proof of concept with a covering of very basic but necessary concepts in a common CAC workflow.

Pitch and Note

The difference between a pitch and a note can be ambiguous. In our library, ªnoteº means different ªpitch classesº in an octave. A note can be A, B, C, D, E, F and G with any number of sharp or flat accidentals.

Text strings can be used to construct a Note object. For example, ªC###º ªDbº or ªBxº are recognizable as ªnote C with 3 sharpsº ªnote D with 1 flatº and ªnote B with double sharps.º Internally, the note name and the accidentals will be preserved and can be used for further calculation. Integer numbers can also be used to construct a note as the offset in semitones from note C, in this case, the note name and the accidentals will be determined automatically.

Pitch is an extended Note object with additional octave information. It is then a more concrete concept as the frequency can be calculated. It is also possible to get a pitch from a frequency with an approximation of a semitone. The pitch's offset follows the C4 = 60 standard.

Both Note and Pitch object supports some kinds of mathematical calculations. Adding or subtracting a number from a Pitch will change by semitones its offset. The offset difference can also be calculated between two Pitches For example, the following code creates a C4 pitch, by adding 12 to get a C5 pitch, then by subtracting a C4 pitch to get 12.

const pitch = new Pitch("C4"); pitch.add [START_REF] Buffa | ªEmerging w3c apis opened up commercial opportunities for computer music applications[END_REF].toString(); // => "C5" // Now pitch is C5 pitch.sub(new Pitch("C4")); // => 12

The multiplication between a pitch and a number is supported to calculate an approximated pitch based on the current pitch as the fundamental frequency and a multiplication ratio. The division is also possible between the pitch and a number or another pitch to calculate a new pitch or the frequency ratio between them. For example, the following code creates a C3 pitch, by multiplying 4 (to its frequency) to get a 2 octaves higher pitch C5, then by multiplying 1.5 to get a perfect fifth higher. const pitch = new Pitch("C3"); pitch.mul(4).toString(); // => "C5" // Now pitch is C5 pitch.mul(1.5).toString(); // => "G5"

Interval

Interval is the distance between two pitches, but it is more complex than just the number of semitones. With different note names and accidentals, the same distance, in equal temperament, can have different intervals such as diminished fourth and major third. Its calculation involves three properties: quality, degree and octave.

In Sol, an interval can be created with a text string, a frequency ratio, or from these properties. ªA4º ªd5-1º ªP5º ªM9º ªm10+1º are usable strings for ªaugmented fourthº ªdiminished fifth with one octave lowerº ªperfect fifthº ªmajor ninth (internally will be transformed to a major second with one octave higher)º ªmajor tenth with one octave higher (internally a major third with two octaves higher).º

Here, the distance between two pitches can be ªnegative.º In one octave, the interval between note F and note B is augmented fourth, and the interval between note B and note F will be ªdiminished fifth with one octave lower.º The operation can be executed using the following code: const b = new Note("B"); const f = new Note("F"); const i1 = f.getInterval(b); i1.toString(); // => "A4" const i2 = b.getInterval(f); i2.toString(); // => "d5-1" i1 and i2 from the code above are two intervals. They can be used for addition and subtraction from notes and pitches.

Chord

A chord is basically a set of pitches aligned vertically and executed at the same time. In our library, the Chord interface includes a base note or pitch and an array of intervals. It has methods such as inverse up and down, move up and down, etc. This model is chosen to easily move the chords, and also to solve the following question more easily: "How to find the missing fundamental frequency of a given chord, if any?" CAC is often used for spectral music composition algorithms, which involves the calculation of harmonics or the fundamental frequency. The missing fundamental of a sound [START_REF] Seebeck | ªBeobachtungen È uber einige bedingungen der entstehung von tÈ onen[END_REF] is an interesting topic in the scope. It has been demonstrated that the frequency of the pitch heard in response to a set of two or more successive harmonics corresponds to the greatest common divisor (GCD) of the harmonic set, even when there is no spectral energy at that frequency [START_REF] Schwartz | ªPitch is determined by naturally occurring periodic sounds[END_REF]. From a signal perspective, the autocorrelation algorithm can be used to find the periodicity of a sound and to determine the missing fundamental frequency. As we already have the frequencies from every pitch of the given chord, we can simply calculate the GCD of the frequencies.

However, the missing fundamental frequency should be an approximated value, as we are under the equal temperament, and human ears has a limited frequency discrimination capacity [START_REF] Moore | ªFrequency difference limens for shortduration tones[END_REF].

Therefore, we calculate a commonly approximated ratio between pitches from multiple ratios given by the intervals, we choose 1 3 of a semitone, which is nearly a 2% difference, as a threshold of the frequency discrimination and the temperament compensation.

As a result, the algorithm is able to recognize that a dominant seventh chord has a ratio of 4 : 5 : 6 : 7 and a missing fundamental on the two octaves lower dominant degree. const chord = new Chord( new Pitch("C4"), new Pitch("E4"), new Pitch("G4"), new Pitch("Bb4") ); chord.ratio; // => [START_REF] Bresson | ªOpenmusic: Visual programming environment for music composition, analysis and research[END_REF][START_REF] Puckette | ªThe patcher,º in Proceedings of the International Computer Music Conference. San Fran-15 The[END_REF][START_REF] Choi | ªAudioworklet: the future of web audio[END_REF][START_REF] Orlarey | ªFAUST : an Efficient Functional Approach to DSP Programming[END_REF] chord.phantomBase.toString(); // => "C2"

The code above calculates a dominant seventh chord on C4, it returns that its missing fundamental (phantomBase) is C2.

Duration

A musical value (duration) in fractions of beats can be expressed using the Duration object. Its constructor accepts a fraction (numerator and denominator) or a text string such as ª4nº ª8ndº or ª16ntº for ªa quarterº ªa dotted 8thº and ªa triplet 16th.º Mathematical operations like compare, add, subtract, multiply and division are also available. For example, we create in the following code the length of a quarter note (one beat), then multiply it by 1.5 to get a dotted quarter, divide it by 9 to get a triplet 16th, finally add a quarter to it to get a length of 7 24 beat. const dur = new Duration(1, 4); // 1 beat dur.mul(1.5); // 3/8 beat dur.div(9); // 1/24 beat dur.add(new Duration(1, 4)); // 7/24 beat

Sequence

Combining the presented models, a sequence can be formed with an array of chords or null values for a rest, and their duration. The sequence interface contains minimum data to render a score segment. It can also be compiled to a MIDI file with a time signature and BPM (beats per minute) information.

Others

Other musical concepts such as Velocity, Scale, Tonality, Track, Instrument, Genre, etc. are added to the library as well. However, these concepts are more complex and still need to be improved in future works.

Score Rendering

The Guido engine [START_REF] Hoos | ªThe GUIDO notation format: A novel approach for adequately representing score-level music,º in Proceedings of the 1998[END_REF] is originally a C++ library aimed to compile plain text as GMN (Guido Music Notation) and to an SVG format file for the score. But it also has two intermediate steps, AR (Abstract Representation) and GR (Graphical Representation) that allow rendering a score from its API [START_REF] Fober | ªScores level composition based on the GUIDO music notation[END_REF].

Through an Emscripten toolchain, the engine has been compiled to WebAssembly with most of its API and released as a JavaScript library at NPM (Node Packages Manager) online. To use the Sol library with the Guido API, we added a method toGuidoAR to the Note, Pitch, Chord and Sequence to perform function calls, construct the musical structure in the Guido AR.

In JSPatcher, the Guido engine runs in a separate thread using the Web Worker API. A guido.view object is available to accept a Guido AR instance and shows directly the compiled SVG score in the object UI.

Other CAC-related Objects

Manipulations of arrays (lists) of pitches, durations, velocities are common tasks in a CAC work. Like the numerous array-related functions in OpenMusic, we also need to provide them in JSPatcher.

Array versions of JavaScript operators are available as objects with the prefix ª[]º like []+, []*, []&&, which are array versions of ªaddº ªmultiplyº and ªlogical and.º They accept an array as the first input. When the second input is an array, values in two arrays will be applied to the function respectively according to their index; otherwise, every value in the first array will be applied to the functions with the second value. We also added some functions existing in OpenMusic like x2dx (calculate the difference between values in an array), dx2x (integrate an array), permute, combinations, arithmSer (create an arithmetic series), fiboSer (create a Fibonacci series), etc.

EXAMPLE

The following patcher (Figure 7) shows a CAC project combining the presented features. The first part of the patcher starts with a button that will create a Bang on click. The Bang generates an arithmetic series between 60 and 71, then randomly permutes the array to get the prime form of a dodecaphonic series. Its inversion is then calculated using the first value and the intervals between each value .The reversions of the two forms are calculated using a copy of the arrays. Using the Sequence and the Sequences functions, we now have a four-voice music segment. The score is displayed using the cac2guido object, and its MIDI file is generated and passed to a sequencer. Below the sequencer, a WAM synthesizer is loaded and waiting for real time MIDI messages. It produces audio data that is connected to the physical output. With the toggle, users can play or stop the sequence.

CONCLUSIONS

The scope of sound and music computing becomes wider today due to various possibilities to create music rapidly or even in real time. The development of machine learning and AI makes automatic composition possible and continuously inspires musicians to cooperate with the computer in the composition process. The accessibility offered by modern web technology with its highly active ecosystem is an opportunity for us to bring music programming and CAC systems to a new stage. For instance, an artwork created on JSPatcher can be easily shared with people by designing a presentation mode of the patcher in which only selected boxes is showing with specific position and size, and specifying in the URI the location of the project file and the patcher filename, with additional options such as hiding the editor UI or make the patcher read-only. 15 In addition, UI components in patchers can also be interacted using touch devices which could make the design workflow simpler than existing VPLs on native platforms.

Today, audio processing in the web do have some limitations, especially the performance cost and the reliability compared to native C/C++ programs due to the implementation of different browsers, i.e. lack of optimization for multi-core CPUs. Even though, the web platform is still attractive to both developers and users. It has minimized the barrier for the deployment and use of any computer program from any device.

The described additions and improvements on JSPatcher are just the first steps towards a complete online IDE for sound and music computing. Feedbacks given by musicians from the community shows high interest in the future possibilities of JSPatcher such as supports for INScore, 16 collaborative editing and messaging via the network. As the project is open-sourced 17 with the examples and SDK (Software development kit) provided, contributions from third-party are feasible and welcome.

Figure 2 .

 2 Figure 2. Files in a patcher

Figure 4 .

 4 Figure 4. Audio buffer manipulation

Figure 5 .

 5 Figure 5. WAM plugins in the audio editor

Figure 7 .

 7 Figure 7. An example of CAC with a MIDI player

Proceedings of the 19th Sound and Music Computing Conference,June 5-12th, 2022, Saint-Étienne (France)

https://www.w3.org/TR/IndexedDB/

https://tinyurl.com/muc8cmyx

https://www.ffmpeg.org/

https://emscripten.org/

https://webassembly.org/

https://github.com/ffmpegwasm/ffmpeg.wasm

https://www.vexflow.com/

https://guido.grame.fr/

https://www.verovio.org/

https://www.abcjs.net/

Open-sourced on https://github.com/fr0stbyter/sol

https://github.com/grame-cncm/guidolib

https://github.com/jspatcher/package-cac Proceedings of the 19th Sound and Music Computing Conference, June 5-12th, 2022, Saint-Étienne (France)


Alberto Serafim Luiz

Guardini

Anne Spalanzani

Philippe Martinet

Christian Laugier

Thomas Genevois

Anh-Lam Do

Minimal Injury Risk Motion Planning using Active Mitigation and Sampling Model Predictive Control

Collision mitigation is an important element in motion planning. Although Advanced Driver-Assistance Systems (ADAS) have a rich number of functionalities, they lack interchangeability. There is still a gap on finding a way to evaluate the best decision globally. This paper presents a novel motion planning framework to generate emergency maneuvers in complex and risky scenarios using active mitigation. The classical Model Predictive Path Integral (MPPI) algorithm is improved to be used in a probabilistic dynamic cost map under limited perception range. A cost map with global probability of injury to all road users is used as a constraint to the problem in order to compute target selection based on the global minimum risk considering all road users. Real experiments introduce the use of augmented sensor data by merging simulation and real sensor data to safely produce collision and mitigation experiments. Results show that the proposed algorithm can perform correctly in real time on board of the vehicle, by finding collision-free trajectories in complex scenarios and compute viable target selection that minimizes global injury risk when collision is inevitable.

I. INTRODUCTION

Advanced Driver-Assistance Systems (ADAS) have been developed to raise safety and driving comfort. Primary safety has been addressed over the years with the advancement of safety technologies such as Autonomous Emergency Braking (AEB) and Advanced Evasive Steering (AES) systems.

NCAP-2025 Roadmap contemplates the development of Autonomous Emergency Braking and Steering Systems (AEBSS), which integrate steering and/or differential braking by taking action autonomously, shifting from a system based assessment to a scenario-based assessment. Its aim is to deliver improved passenger car safety but also on how it might assist other road users. The main objective is to make use of new technologies to minimize human error, which are responsible for over 90% of road accidents [START_REF]Euro ncap launches road map 2025 -in pursuit of vision zero[END_REF].

Many works in the literature propose motion planning for emergency scenarios considering collision avoidance, vehicle stability and path tracking supposing collision-free scenarios. However, few works consider AEBSS application for complex scenarios mitigation, such is the case in [START_REF] Wang | Crash mitigation in motion planning for autonomous vehicles[END_REF], [START_REF] Lee | Collision avoidance/mitigation system: Motion planning of autonomous vehicle via predictive occupancy map[END_REF]. These works however, limit the scope of the risk assessment to the ego-vehicle occupants, disregarding the related risk to all other road users. 1 Univ. Grenoble Alpes, INRIA, Chroma Team, 38000 Grenoble, France, name.surname@inria.fr 2 Centre INRIA d'Université Côte d'Azur, ACENTAURI Team, 2004 Route des Lucioles, 06902 Valbonne, name.surmane@inria.fr 3 Renault S.A.S, 1 av. du Golf, 78288 Guyancourt, France.

name.surmane@renault.com On the other hand, works based in accidentology propose a framework to quantify the benefits and efficiency of AEB [START_REF] Schachner | Development and evaluation of potential accident scenarios involving pedestrians and aeb-equipped vehicles to demonstrate the efficiency of an enhanced open-source simulation framework[END_REF] and AEBSS [START_REF] Kovaceva | Safety benefit assessment of autonomous emergency braking and steering systems for the protection of cyclists and pedestrians based on a combination of computer simulation and real-world test results[END_REF] towards vulnerable road users. Yet, these studies comprise a posterior analysis of the probability of injury in the event of a collision.

To develop our AEBSS framework we rely on the MPPI technique developed by Williams [START_REF] Williams | Aggressive driving with model predictive path integral control[END_REF]. It derives from Path Integral Control [START_REF] Kappen | Linear theory for control of nonlinear stochastic systems[END_REF] which transforms the value function of the Optimal Control Problem (OCP) into an expectation over all possible trajectories. It is a method that allows Stochastic Optimal Control (SOC) problems to be solved with a Monte Carlo approximation using forward sampling of stochastic diffusion processes [START_REF] Williams | Model predictive path integral control: From theory to parallel computation[END_REF]. Thus, MPPI uses a path integral method to find a control sequence by minimizing the running cost, which corresponds to the integral of each individual cost in each step where solution to the Hamilton-Jacobi-Bellman equation is approximated by importance sampling of these paths using Feynman-Kac theorem and KL divergence [START_REF] Williams | Aggressive driving with model predictive path integral control[END_REF].

The use of MPPI is appealing because it is a derivative-free optimization method, which allows the use of non-linear and non-convex models and cost functions. As MPPI has shown good performance in aggressive driving situations, it seems therefore particularly well adapted to emergency trajectories in the ADAS context.

The original version of the MPPI algorithm [START_REF] Williams | Aggressive driving with model predictive path integral control[END_REF] considers an offline static cost map with previous knowledge of the track configuration. It has been extended to environments with dynamic obstacles in [START_REF] Buyval | Model predictive path integral control for car driving with dynamic cost map[END_REF]. Also, a study on partially observable scenarios for Quadrotors was introduced in [START_REF] Mohamed | Model predictive path integral control framework for partially observable navigation: A quadrotor case study[END_REF].

The main contribution of this work is the development of a novel motion planning technique for vehicle navigation in a risky environment considering Active Mitigation, i.e, real time target selection based on accidentology data.

In technological requirements, our methodology fulfills Euro NCAP 2025+ specs for an AEBSS motion planning, going beyond scenario-based assessment, since it can be considered a generic assessment method. Therefore, our work's emergency trajectories planning considers the global injury risk for all binary collisions between the ego vehicle and a given object in the scene by using the Probability of Collision with Injury Risk (PCIR) [START_REF] Guardini | Employing Severity of Injury to Contextualize Complex Risk Mitigation Scenarios[END_REF] as a constraint to the problem.

To the best of our knowledge, this is the first time PCIR is integrated into motion planning, as well as the use of MPPI considering a probabilistic dynamic cost map with limited perception range. In other words, from a classical navigation algorithm, our work presents a novel AEBSS general framework that integrates Active Mitigation (by the use of PCIR) to compute either collision-free trajectories when available, or a mitigation trajectory that comprises a real-time target selection based on the global probability of injury concerning all road users.

Real testing validation was conducted by using Virtual Objects and Augmented Reality. It is possible then to overcome the adversity of real testing collisions with pedestrians and/or other vehicles, making it possible to conduct real experiments in safety while considering a virtual collision with objects in the scene.

The remainder of the paper is organized as follows. Section II introduces the system's architecture. Section III explains the Emergency Trajectory MPPI (ET-MPPI) methodology. Section IV presents testing results and discussions. Section V provides conclusion remarks.

II. SYSTEM ARCHITECTURE

Our proposed system for the motion planning framework is depicted in Figure 1. Inputs are: the Dynamic Environment Representation, given by Conditional Monte Carlo Dense Occupancy Tracker (CMCDOT) [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF], a generic spatial occupancy tracker that infers dynamics of the scene through a hybrid representation of the environment; PCIR, which provides the probability of collision between the ego-vehicle and an object while also considering the probability of injury as a function of the type of object (pedestrian, cyclist, another vehicle etc.) and the impact speed between the ego-vehicle and the corresponding object [START_REF] Guardini | Employing Severity of Injury to Contextualize Complex Risk Mitigation Scenarios[END_REF]; Vehicle Status and Localization, which refers to ego vehicle information such as position, velocity, acceleration and steering angle. In practice, the odometry information is obtained by combining information from an Xsens GPS and an Inertial Measurement Unit (IMU) present in the prototype. The odometry estimator is based on an Extended Kalman Filter (EKF) in order to infer the pose of the ego vehicle.

The output of the system is an optimal trajectory that considers either a collision-free trajectory when possible or a mitigation trajectory that minimizes the global risk of injury considering all binary collisions between the ego-vehicle and each object in the scene.

III. EMERGENCY TRAJECTORY MPPI (ET-MPPI)

The original MPPI algorithm was developed to perform aggressive maneuvers while maintaining the ego vehicle speed as constant as possible. In emergency trajectories, besides steering angle, one also needs to change the velocity. To deal with emergency situations, our work makes use of a large range of control inputs and due to the characteristics of the MPPI approach, a significant number of trajectories would be necessary to contain all the input variation needed.

It becomes too expensive to compose the two-dimensional set comprising the desired extent for both the steering angle and the velocity for each cell in the grid. For instance, let us imagine a pedestrian and the reachability set of the vehicle. A vast number of trajectories would be needed in order to contain all possible (combinations of steering angle and velocity variations within the desired scope for each cell representing an object.

A. ET-MPPI

The Emergency Trajectory MPPI (ET-MPPI) framework for emergency scenarios is presented in Algorithm 1. The improvements to the original MPPI algorithm [START_REF] Williams | Aggressive driving with model predictive path integral control[END_REF] that allows the use of MPPI in emergency scenarios are highlighted in red and further explanation on the definition of the cost function is given later in this section.

Algorithm 1: ET-MPPI Algorithm 1 Procedure computeMppiControl(x init ,u init ,∆t) 2 for k ← 0 to K -1 do // For all sampled trajectories 3 Sample ε k t ∈ N (0, νΣ) // Generate Gaussian noise 4 for t ← 0 to T -1 do // For prediction horizon 5 v t = u t + ε k t // Adding
S k = S k + q(x t,k , u t,k ) // Trajectory Cost 12 S k = S k + φ (x) // State dependent terminal cost 13 ρ ← min k ( S k ) // Find minimum cost 14 η ← K-1 ∑ k=0 exp -1 λ (S k -ρ) // Normalizer 15 for k ← 0 to K -1 do 16 w k ← 1 η exp -1 λ (S k -ρ) // Probability Weight 17 for k ← 0 to K -1 do 18 U ← U + K-1 ∑ k=0 w k ε k // Weighted sum control update 19 return etmppiTrajectory(x init ,U) // Return trajectory
To start, the algorithm requires the status and localization of the ego vehicle at instant t init , here defined as (x init ,u init ). In our case, it comes from the Vehicle Status and Localization block. Then, KxT random control variations are generated using CUDA's random number generation library (line 3). The variance ν of the noise N can be increased to avoid local minima by shifting the range of the trajectory cost, which leads to even more chattered control solutions.

Perturbation is added to the initial control sequence (line 5). The Gaussian noise generated for the acceleration in the original algorithm is replaced by the maximum deceleration in ε brake (line 6), whereas the Gaussian noise for the steering angle remains the same.

The next state is found for each sampled trajectory (line 7) and updated according to each timestep t. The Same is valid for K conservative trajectories x brake (line 8), which always consider the maximal braking and the corresponding random noise for the steering angle. F(•) represents the vehicle model, in our case, a kinematic bicycle model and g(•) the clamping function for actuators saturation.

Every trajectory x k is checked for collisions. If the k th trajectory collides against one of the objects of the scene, it is replaced by the conservative trajectory x k brake (line 10).

A running cost for each sample trajectory k at a given timestep t is then computed and added to the final cost (lines 11:12). The cost of each sampled trajectory k is converted to a probability weight w k (line 16), taking into account the minimum weight trajectory (line 13). The optimal control law is then defined via the probability weight w k averaged over all the perturbation sequences (line 18).

The final trajectory is obtained by passing the final control sequence trough a vehicle model (line 19), a kinematic bicycle model in our case. Since the final optimal trajectory depends on the probability weight of each k trajectory, it is possible to compute compute pure evasive steering trajectories (or a composition of braking and steering), otherwise, the ET-MPPI algorithm guarantees that the worstcase scenario will always have the maximal braking (same as in AEB), although with the advantage of all possible range of steering for the collision trajectories, which allows some maneuverability.

For the latter, since we apply PCIR as a constraint to the system, it is possible to have a better contextualization of the scene when dealing with mitigation scenarios and compute a target selection considering the global minimal risk. So, if the evaluation considers that no collision-free trajectories can be computed, we need to compute the minimal global risk associated with all K possible trajectories. Those criteria are addressed by defining and tuning the cost function S k coefficients as presented in the next subsection.

B. ET-MPPI Cost Functions

Our cost map takes into consideration both static and dynamic objects given by a probabilistic grid. Furthermore, the Probability of Collision with Injury Risk (PCIR) is used as a novel constraint to the problem. The elements taken into consideration in order to develop our cost map are the vehicle's actuators and dynamics constraints, objects and PCIR, perception limits and the ego-vehicle predicted trajectory.

The actuator and dynamic constraints and variance cost are already taken into consideration in the original algorithm presented in [START_REF] Williams | Robust sampling based model predictive control with sparse objective information[END_REF] in the form of a convex cost function.

Our path cost q(x) is defined as:

q(x) = c pcir + c whiteline + c limits + c re f erence (1)
c pcir penalizes collision while considering injury risk:

c pcir = w pcir (PCIR) (2)
where w pcir is the weight and PCIR is computed according to the impact speed and the type of object in the scene [START_REF] Guardini | Employing Severity of Injury to Contextualize Complex Risk Mitigation Scenarios[END_REF].

To avoid collisions as much as possible, w pcir gets a high value, and if mitigation is needed, the value of PCIR will become predominant over all other costs, which sets the target selection. c whiteline assigns for ego-vehicle trajectory to remain on the right side of the road. Trajectories surpassing the boundaries are penalized as defined in equation [START_REF] Lee | Collision avoidance/mitigation system: Motion planning of autonomous vehicle via predictive occupancy map[END_REF].

c whiteline = w whiteline (3)
Where w whiteline corresponds to the correct road lane cost. It is set as a soft constraint to appease an emergency eviction maneuver that requires crossing the middle lane to avoid a collision. This is achieved by setting the corresponding weight to a value that is between Reference and PCIR costs. c limits , defined in Equation ( 4) is used to ensure that the ego-vehicle will not cross undesired areas, such as sidewalks, which can lead to loss of control. In cases where a behavior planning is used, this constraint can be replaced by the ones issued by the behavior planner.

c limits = w limits (4)
Where w limits corresponds to the road limit cost and its value shall surpass w PCIR to assure that even in mitigation cases the constraint will be respected.

Figure 2 shows a diagram to exemplify c whiteline and c limits . Trajectories which are generated and which remain in the green zone (trajectory 3) are not penalized by either costs. Trajectories that go beyond the green zone to the yellow zone (trajectory 2) are penalized with c whiteline . Trajectories which are in the red zone (trajectories 1 and 4) are penalized with c limits . c re f erence is used for having the evasive trajectory closer to the projected real trajectory of the vehicle. It is defined as:

c re f erence = (x -x re f ) T w re f (x -x re f ) (5)
Where w re f corresponds to a positive define weight matrix and x re f are the reference states in a three seconds horizon trajectory prediction from a kinematic bicycle model and the initial states provided by an odometry estimator based on an Extended Kalman Filter (EKF).

IV. EXPERIMENTS AND TESTING The ET-MPPI algorithm has been tested both in simulation and real experiments. Table I presents the corresponding parameters for the testing.

A. Experimentation Scenarios

We propose a pedestrian crossing scenario, shown in The ego vehicle (white), has its field of view occluded by the truck on its right. Therefore, the pedestrian (coming from the right of the ego vehicle) perception happens for Time-to-Collision (TTC) between 0.5 and 2 seconds.

B. Metrics

Two metrics are considered. The first is related to vehicle controllability. Two different control constraints based on the definition of controllability given by ISO 26262 standard [START_REF]Road vehicles -functional safety[END_REF] had been chosen. C x (simply controllable) and C y (difficult to control or uncontrollable), whose parameters for the steering angle δ , the steering rate δ and the acceleration a are presented in Table II. These parameters are inserted in line 3 of Algorithm 1 in order to generate the noise ε k t that will be added to the control input and thus influence the variance importance sampling. The control input perturbation along with the clamping function g(•) compose the vehicle reachable set.

Constraint δ [degrees] δ [degrees/s] a [m/s 2 ] C x [-3 3] [-3 3] [-3 3] C y [-30 30] [-30 30] [-9 3]
The second metric is a performance comparison between AEB systems, C x and C y in terms of collision eviction and/or mitigation.

Each scenario was simulated twenty times for each control constraint. A small offset was added to each of the objects' initial position to observe the robustness of the method with respect to avoidance/mitigation and provide a comparison with the full longitudinal braking AEB system.

C. Simulation Experiments

Simulations take into consideration noisy localization sensors, such as GPS and IMU. Besides, the uncertainty in the perception is also taken into consideration. All simulation results were obtained with the following specs: Intel® Core™ i9-9880H CPU @ 2.30GHz x 16 with NVIDIA Quadro RTX 3000/PCIe/SSE2 GPU under Ubuntu 18.04 ROS Melodic [START_REF] Quigley | Ros: an open-source robot operating system[END_REF] and Gazebo 9 [START_REF] Koenig | Design and use paradigms for gazebo, an open-source multi-robot simulator[END_REF].

1) Simulation Results: The graph in Figure 4 presents the percentage of collision-free (blue) and mitigation trajectories (red) for the AEB case and control constraints C x and C y , considering an ego-vehicle longitudinal velocity of 50 km/h . Control constraint C y showed a better performance in avoiding objects in the scene when compared to the other control constraint C x and the AEB system. This is due to the fact that C y presents a larger reachability set and an eviction maneuver is possible in many more cases. In most of the cases, configuration C x does as good as the AEB system, since its output usually corresponds to braking, since its reachable set is much more limited.

Another outcome is that an increase in scenario complexity will lead to situations where collision might become inevitable, and consequently, mitigation is needed.

Next, we discuss and present the output of the ET-MPPI algorithm compared to the AEB for a collision-free trajectory for scenario (a), and a mitigation case for scenario (c), both considering the control constraint C y at 50 km/h ego-vehicle speed. Scenario (b) will not be discussed since its outcomes tend to one of the presented results.

Scenario (a) is shown in Figure 5 on the left. The system perception and output for the ET-MPPI generated trajectory for Scenario (a) is shown in Figure 5 on the right. The AEB trajectory is represented by the black band and the ET-MPPI trajectory by the yellow band.

Although the given scenario is not complex, it is possible to observe that the AEB system will only be able to mitigate the collision, whereas an eviction trajectory (yellow band with footprint of the ego-vehicle) was generated by the ET-MPPI algorithm. Besides the point of avoiding the obstacle, the ET-MPPI trajectory might also avoid a rear collision to a tailing vehicle, increasing the road safety. For the simulation we consider that the pedestrian will cross the road at constant speed. However, if the pedestrian reacts to the incoming vehicle, the emergency trajectory is replanned (iteration time of 0.05 seconds) and a new emergency trajectory is computed in order to cope with the new changes.

Scenario (c) is depicted in Figure 6, where the scene is shown on the left and the output with the elements of the scene are displayed on the right. The truck on the right, which is occluding the field of perception is pushed closer to the pedestrian passing to decrease even further the reaction time. The goal is to analyse a mitigation scenario by observing how the algorithm generates the ET-MPPI trajectory according to the injury risk associated with each of the objects. The ET-MPPI trajectory for this case is displayed in red, since a mitigation trajectory is considered for the scene. Both AEB and ET-MPPI trajectories will result in a collision, however, for the latter, a target is selected through the cost function parameter c pcir , resulting in a trajectory that minimizes the global injury risk.

Figure 7 displays the corresponding PCIR cost map based on the type of object and the prediction. This cost map gives us an indication of the global probability of injury with respect to the highest probability of injury in the scene. For instance, the pedestrian presents the reference PCIR of 1 (or 100%), meaning that it is the most vulnerable road user. The vehicles on the top (blue vehicle) present a very low probability of collision with injury risk (close to white) if compared to the pedestrian. The stationary vehicle on the bottom presents a PCIR close to 40%. It takes precedence over the blue vehicle but does not take precedence over the pedestrian, but since the path to the blue vehicle is blocked by the pedestrian prediction, target selection goes towards the parked truck on the right.

In short, AEB trajectory will result in an ego-to-pedestrian collision, which to the corresponding impact speed and assumptions brings a higher probability of injury (around 80% probability of slight and 20% severe injury) to the pedestrian. ET-MPPI algorithm had a better performance in mitigating the collision due to the target selection based on PCIR. For the given scenario, instead of colliding with the pedestrian our algorithm selects the truck on the right, which brings a less than 2% probability of injury to the occupants of the vehicles.

D. Real Experiments

Experiments have been conducted on a dedicated test vehicle, a Renault Zoe equipped with a Velodyne HDL64 LiDAR on the top, 3 Ibeo Lux on the front and 1 on the back, which provides dense 3D point clouds of threshold measurement. Besides, a Xsens GPS, an IMU and a SP90 RTK GPS system provide accurate position and orientation. Same as in simulation, perception relies on the CMCDOT spatial occupancy tracker [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF]. The localization is based on the fusion of the odometry and the RTK GPS to obtain a coherent position, orientation and speed estimation.

The experimental validation of this work demands complex test scenarios, where collision with pedestrians and vehicles must be contemplated. For safety reasons, such tests cannot be realized in real conditions and a new augmented reality framework [START_REF] Genevois | Augmented Reality on LiDAR data: Going beyond Vehicle-in-the-Loop for Automotive Software Validation[END_REF] has been used.

The results for real experiments are shown in Figure 8. On the left, the augmented reality provides augmented sensor data to the vehicle camera and on the right the virtual and real objects perception and PCIR. The red band represents the ET-MPPI mitigation trajectory. As in simulation, target selection presents the pedestrian as the most vulnerable road user and a collision with the parked truck on the right brings the least global injury risk. The augmented reality setup allowed real testing considering collision while keeping driver security and prototype integrity. Terrain noise affected the result due to falsepositive detection. However, due to replanning we noticed that once the perception grid filters the noise a new trajectory is promptly generated.

Another remark is related to object prediction. We have noticed a small delay that might be the result of GPU usage for perception, virtual object simulation and MPPI algorithm combined.

Considering all challenges of real time experiments, the ET-MPPI algorithm has produced results consistent with simulation for generating collision-free trajectories when possible or mitigating the global probability of injury for a collision in mitigation scenarios.

V. CONCLUSIONS The present work presents a novel motion planning technique for vehicle navigation on risky environments considering active mitigation. Trajectory planning is based on the classical MPPI framework, which is significantly improved to contemplate a probabilistic dynamic cost map and global probability of injury constraints.

Results show that trajectory generation complies with Euro NCAP 2025+ requirements by providing an AEBSS scenario based framework which generates collision-free trajectories when possible or computes active mitigation target selection based on preexisting accidentology data.

Virtual objects are introduced in our work as an alternative to conduct safe real experiments. By merging virtual sensor data to actual real data to virtually present objects in the scene, which allowed us to carry out real experiments without putting in risk the driver or menacing prototype integrity.

One limitation of the study is the use of constant velocity objects in simulation. A suggestion for improvement includes a more liable simulation scenario with non-constant velocities objects and pedestrians with random trajectories. Also, for prototype experiments, false-positives on detection interfered with the algorithm output, although the replanning made it possible to correct it once filtering removed the noise.

Future development includes dealing with the mentioned limitation on object tracking to improve object prediction, and noise filtering to improve trajectory planning output stability. It also includes the use of the generated trajectories as set points for a motion controller to be used in a feedback loop in order to observe its feasibility in prototype applications.

Fig. 1 :

 1 Fig. 1: System Architecture.

Fig. 2 :

 2 Fig. 2: Road Boundaries and Limits.

Fig. 3 :

 3 Fig. 3: Pedestrian Crossing Scenarios

Fig. 4 :

 4 Fig. 4: Percentage of collision-free or mitigation cases for 20 simulation runs for the given scenarios for AEB system and ET-MPPI control constraints C x and C y .

Fig. 5 :

 5 Fig. 5: Scenario (a): On the left the gazebo simulation, on the right, perception, object prediction and ET-MPPI generated trajectory

Fig. 6 :

 6 Fig. 6: Scenario (c): On the left the gazebo simulation, on the right, perception, object prediction and ET-MPPI mitigation trajectory

Fig. 7 :

 7 Fig. 7: Scenario (c): PCIR cost map generated from ET-MPPI trajectory cost

Fig. 8 :

 8 Fig. 8: Scenario (c) real testing. On the left, camera view with objects in Augmented Reality. on the right, perception, PCIR for object prediction and ET-MPPI mitigation trajectory

TABLE I :

 I ET-MPPI Parameters Values

	K	4000	T	45
	λ	0.004	α	0.7
	w whiteline	5000	w PCIR	1.6E5
	ν	Diag(1.0, 1.2)	w re f	Diag(0, 400, 0, 0)
	Σ Cx	Diag(1.0, 2.0)	Σ Cy	Diag(1.0, 22.0)
	R terminal	Diag(0, 2.5, 0, 400)

TABLE II :

 II Control Constraints C x and C y

VI. ACKNOWLEDGMENT

This work is supported by a CIFRE PhD fellowship with Renault. We thank the Chroma Inria team and IRT Nanoelec (founded by the French program "Investissement d'Avenirs" ANR-10-AIRT-05).


Hassan Harb
email: hassan.harb.1@ul.edu.lb

Diana Abi Nader

Kassem Sabeh

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Real-Time Approach for Decision Making in IoT-Based Applications

Keywords: IoT, wireless sensor networks, real-time applications, energy saving, data reduction techniques, score system, K-means algorithm

Nowadays, the IoT applications benefit widely many sectors including healthcare, environment, military, surveillance, etc. While the potential benefits of IoT are real and significant, two major challenges remain in front of fully realizing this potential: limited sensor energy and decision making in real-time applications.

To overcome these problems, data reduction techniques over data routed to the sink should be used in such a way that they do not discard useful information. In this paper, we propose a new energy efficient and real-time based algorithm to improve the decision making in IoT. At first data reduction is applied at the sensor nodes to reduce their raw data based on a predefined scoring system. Then, a second data reduction phase is applied at intermediate nodes, called grid leaders. It uses K-means as a clustering algorithm in order to eliminate data redundancy collected by the neighbor nodes. Finally, decision is taken at the sink level based on a scoring risk system and a risk-decision table. The evaluation of our technique is made based on a simulation from data collected on sensors at Intel Berkeley research lab. The obtained results show the relevance of our technique, in terms of data reduction and energy consumption.

INTRODUCTION

Wireless sensor network (WSN) is an indispensible part of Internet of Things (IoT). It allows monitoring, data collection, processing and transmission in several IoT based applications [START_REF] Kadiravan | Metaheuristic clustering protocol for healthcare data collection in mobile wireless multimedia sensor networks[END_REF] [START_REF] Mostafa | An energy-efficient mul-tiobjective scheduling model for monitoring in internet of things[END_REF], such as smart cities and smart farms, health care, agriculture, business innovation, environmental monitoring, and so on [START_REF] Atzori | Understanding the internet of things: definition, potentials, and societal role of a fast evolving paradigm[END_REF]. In a typical scenario, data collected by sensor nodes are transmitted to a middleware for processing before being forwarded to a specific access point (sink) for further analyses and decision making [START_REF] Kaur | An energy-efficient architecture for the internet of things (iot)[END_REF].

Following the increasing number of IoT users, the quantity of data generated and collected is continuously increasing. For that, differentiating between what data to keep and what data to dismiss is crucial for data accuracy and decision making optimization especially in real-time cases. However, data transmission is the most expensive in terms of sensor energy consumption. Additionally, IoT devices, especially sensor nodes, are limited in their lifetime ena https://orcid.org/0000-0003-3066-9189 b https://orcid.org/0000-0003-0485-097X ergy due to the battery power limitation which affects the device's longevity [START_REF] Ruan | A life cycle framework of green iot-based agriculture and its finance, operation, and management issues[END_REF]Harb and Makhoul, 2018). Thus, many data reduction techniques have been introduced in order to solve this problem. It aims at removing similar routed data in such a way of minimizing the amount of data transmitted and thus, saving energy (Harb et al., 2018) [START_REF] Harb | An energy-efficient data prediction and processing approach for the internet of things and sensing based applications[END_REF].

In this paper, we propose a novel approach for energy saving and decision making in real-time IoTbased applications. Its purpose resides in reducing the quantity of transmitted data to the sink without loosing information and guaranteeing data integrity. By this mean, data transmission rate will be reduced, leading to the optimization of the network resources. Our technique is composed of two data reduction levels and one decision level. The first data reduction technique is applied at the sensor level where raw data are reduced by mean aggregation based on a predefined score system. The second data reduction technique is applied at intermediate nodes, called grid leaders. Each grid leader works on removing data redundancy collected by neighboring nodes based on Kmeans clustering algorithm. The final decision phase is achieved at the sink level. The dataset obtained will be used to calculate the risk ratio based on the score system, then it will determine the right decision according to a predefined risk-decision table. To evaluate our approach several simulations have been conducted while using real dataset collected at the Intel Berkeley research lab. The obtained results show the relevance of our technique in terms of data reduction and energy consumption.

The rest of the paper is organized as follows. Section 2 overviews various existing data reduction techniques for IoT. Section 3 describes the real-time grid architecture used in our scenario. In Section 4, we present the first layer of our data reduction technique applied at the sensor nodes level. Section 5 describes the second layer of data reduction applied at the grid leaders level. In Section 6 we detail the decision making algorithm at the sin level. Simulation results are presented in Section 7. Finally, Section 8 concludes our paper and gives some perspectives.

Related Work

Many approaches have been suggested for data reduction in WSNs. The importance of reducing data collected in IoT based sensors relies in avoiding packets loss in network or delay in packets delivery which will affect decision making.

Many energy efficiency techniques based on machine learning techniques have been proposed for effective routing decisions in WSN and IoT. For instance, in [START_REF] Thangaramya | Energy aware cluster and neuro-fuzzy based routing algorithm for wireless sensor networks in iot[END_REF], neuro-fuzzy based cluster formation protocol (FBCFP) was proposed. The network is trained with convolutional neural network with fuzzy rules for weight adjustment, learning four components: current energy level of the CH (Cluster Head), distance of the CH from the sink node, change in area between the nodes present in the cluster and the CH due to mobility and the degree of the CH. Then using Mamdani Inference System for adjusting new CHs depending on energy. In [START_REF] Preeth | An adaptive fuzzy rule based energy efficient clustering and immuneinspired routing protocol for wsn-assisted iot system[END_REF], another fuzzy energy efficient scheme is proposed called adaptive fuzzy multi criteria decision making (AF-MCDM) approach, where fuzzy Analytic Hierarchy Process (FAHP) and TOP-SIS methods are combined together for selection of cluster head.

In [START_REF] Santiago | Ealba: energy aware load balancing algorithm for iot networks[END_REF], an energy aware load balancing algorithm is proposed for IoT network by selecting parent nodes using event rate for cluster formation and neural network predictor for ELT (Expected Life Time) prediction. In [START_REF] Elappila | Survivable path routing in wsn for iot applications[END_REF], a congestion and interference aware energy efficient routing technique in WSN for IoT is presented.

It consists of selecting the signal to interference and noise ratio of the link, the survivability factor of the path from the next hop node to the destination, and the congestion level at the next hop node. In [START_REF] Khan | Energy optimization of pr-leach routing scheme using distance awareness in internet of things networks[END_REF], a new routing protocol named Modified-Percentage LEACH Protocol is introduced based on existing protocol namely Percentage LEACH. Energy wastage is reduced by reducing communication between Cluster Heads and sink through threshold calculation on each CH for cluster selection and taking into consideration the distance of nodes from sink.

Authors in [START_REF] Kaur | An energy-efficient architecture for the internet of things (iot)[END_REF] proposed to switch to sleep the IoT sensors based on three conditions: if it is not necessary to sense the target environment in a given period of time; if the coverage area can be compromised for battery life; and if the battery level is critically low. In [START_REF] Hong | A topology control with energy balance in underwater wireless sensor networks for iot-based application[END_REF], TCEB, a topology control algorithm with energy balance, addresses the problem of how to find a reasonably reduced topology and the packets forwarding route for underwater wireless sensor networks for energy conservation. Non-cooperative game theory is introduced to the the cluster-head selection in order to optimize the set of the cluster-heads selection and to ensure the energy consumption of the whole network balance. Then, the intra-cluster and the inter-cluster topology construction are used in order to find the optimum reliable nodes to perform the forwarding task.

On bio-smart levels, [START_REF] Roy | biosmartsense: A bio-inspired data collection framework for energy-efficient, qoi-aware smart city applications[END_REF] a bioinspired distributed event sensing and data collection framework was proposed based on the gene regulatory networks (GRNs) in living organisms. This is achieved by customizing a heuristic for the Maximum Weighted Independent Set problem encompassing both quality and quantity of sensed data, where the first depends on the device energy levels while the second on the number of events sensed. A suboptimal device will be proposed depending on the residual energy.

In [START_REF] Muhammad | Intelligent and energy-efficient data prioritization in green smart cities: Current challenges and future directions[END_REF], an energy-efficient Data Prioritization framework is proposed by intelligent integration of the Internet of Things, artificial intelligence, and big data analytics for green smart cities. In [START_REF] Ejaz | Efficient energy management for the internet of things in smart cities[END_REF][START_REF] Tomasoni | Profiling energy efficiency of mobile crowdsensing data collection frameworks for smart city applications[END_REF], a unifying framework for energy-efficient optimization and scheduling of IoT-based smart cities. Finally, in [START_REF] Wang | Towards energy-efficient task scheduling on smartphones in mobile crowd sensing systems[END_REF],an Integer Linear Programming (ILP) formulation as well as two effective polynomial-time heuristic algorithms are proposed for energy-efficient task scheduling problem on smartphones in mobile crowd sensing systems.

Despite that most of the proposed techniques allow efficient energy saving, they fail to reach all aspects of IoT applications. Indeed, they are very com-plex and require huge processing. In this paper, we present an energy efficient data reduction method that it is less complex and suitable for limited resources sensor nodes.

The Network Architecture

In this section, we introduce the network architecture used in our technique. Two main concepts have been adopted in our scenario: grid-based architecture and periodic data acquisition. In the following, we describe each of them in more details.

Grid-based Network

We consider a grid-based distribution, where each square can be defined based on the dimensions of the whole area of interest and the density of the sensor nodes. In each square, a grid leader is elected or selected using an appropriate method. This grid leader is considered as intermediate node. It can be an ordinary node or a node with more capabilities. We consider that the sensor nodes in the same square will send their data directly to their grid leader, which in his turn summarizes and aggregates the received data coming from neighboring nodes. The idea is to remove useless redundant data, While following specific rules and before sending them to the sink. Figure 1 shows our sensor network architecture, where data transmission between sensor nodes and their appropriate grid leader is based on single-hop communication.

Sink Grid Leader Sensor node

Figure 1: Two-level data transmission architecture.

Periodic Data Acquisition Model

Data collection from Iot applications can be made by data streaming where, data flows primarily from the sensor node to the grid leader and finally to the sink. We distinguish two kinds of data streaming the periodic sampling and the event driven. In our approach we are interested in "periodic sampling" data model, where the acquisition of sensor data is forwarded to the grid leader and the to the sink on a periodic basis.

We consider that each period p is partitioned into time slots. At each slot t, each sensor node N i captures a new reading r i . At the end of the period p, N i collects a vector of τ readings, e.g. R p i = r 1 , r 2 , . . . , r τ , then it sends it to the sink. In our system, each sensor node sends periodically (period p) its data to the appropriate grid leader, which in turn sends it to the sink (Fig. 2) (Harb et al., 2018).

First phase data reduction

In this section we describe how the sensor node itself reduces the amount of its collected data before sending it to the grid leader. Indeed, data collected in vector R contains redundant measurements especially when the slot interval between two collected measures is short. The idea is to reduce the size of the the vector R p i by selecting similar and consecutive measures from it and computing their mean to send to the grid leader instead of sending the whole readings. Our proposed model is based on a measurement score aggregation system used to identify similar measures.

Score System

The score system is a guide used to determine similar measures within a vector R p i by assigning scores to each measure. Based on a score system, all measures belonging to the same interval will be assigned the same score and aggregated as similar measures. Table 1 gives an example of such a score system.

Sensory data reduction Algorithm

In this section we introduce the algorithm proposed to reduce the number of readings collected periodically by each sensor. The idea is to reduce the number of readings in the vector R p i to send to the grid leader. The algorithm works as follows: first we find the score of each reading present in R p i using the function score, which takes the reading as an input and returns the score of the reading according to a well defined score system. Then, if consecutive readings in R p i have the same score, we calculate the mean value of those readings. The basic idea is that we consider readings having the same score as similar and redundant and instead of sending all of them we send only their mean. Therefore, the process starts by finding the score for the first reading in R p i , then it checks the score of the next values until it reaches a reading whose score is different from the current one. Then, we calculate the mean of all previous readings, and the process iterates again to find readings with same score as current value. Hence, the final vector V R p checkbe f ore = check 15: end for 16: return V R p i After applying Algorithm 1, each sensor will send a vector of representative readings V R p i = (r 1 , f 1 ), (r 2 , f 2 ), . . . , (r k , f k ) to its proper grid leader, where k ≤ τ and f i represents the weight or frequency of r i .

Second phase data reduction

The grid leader receives a vector of reduced data from all neighboring sensors at the end of each period. At this stage, we propose an algorithm to reduce the number of data collected at grid leader level by eliminating similar or redundant vectors. Our objective is to group the readings observed by the grid leader in clusters using the K-means algorithm, then eliminate redundant data within each cluster by applying a mean based technique similar to the one applied at sensor level. In the next sections we explain in more details how we combined the K-means algorithm with a mean aggregation technique to clean data at grid leader level.

K-Means Clustering Algorithm

K-means clustering is a simple unsupervised learning algorithm that is used to solve clustering problems. k-means tries to divide a set of samples in k disjoint groups or clusters using the mean value of the members as the main indicator. The clusters are partitioned as points and all observations or data points are associated with the nearest cluster, computed, adjusted, and then the process starts over using the new adjustments until a desired result is reached. Although it can be proved that the procedure will always terminate, the algorithm is also significantly sensitive to the initial randomly selected cluster centers.

The performance of a clustering algorithm may be affected by the chosen value of K. Therefore, instead of using a single predefined K, a set of values might be adopted. It is important for the number of values considered to be reasonably large, to reflect the specific characteristics of the data sets. At the same time, the selected values have to be significantly smaller than the number of objects in the data sets, which is the main motivation for performing data clustering. The optimal value of K for many studied applications varied in the interval [3, 5].

Absolute Value Distance

One of the fundamental steps when applying the Kmeans algorithm is computing the distance between a reading and a mean value of a cluster. In this paper, we considered the absolute value distance which is a simple yet effective method to find the distance between two values. In mathematics, the distance between x and y is defined by a subtracting relationship: | xy |. Let us consider a data value in R i and mean value of a cluster µ , then the absolute value distance (A d ) between them can be calculated as follows:

A d (r i , µ) =| µ -r i |, (1)
where r i ∈ R i and µ is the mean value of a cluster.

K-Means and Absolute Value Distance

Algorithm 2 describes the procedure of K-Means algorithm to divide the n vectors R i received by the grid leader from the n neighboring sensors into a set of k clusters. First, the algorithm assigns k random values from the readings as centroids and allocates a cluster for each centroid. Then, we calculate the absolute value distance between each value r i and the k centroids of all clusters and assign the readings to the clusters according to the minimum distance.

In the next step, we calculate the mean value for each cluster and use it as the new centroid for that cluster. Then, we calculate the distance between the new centroid and the old one. If the distance is zero for all clusters, the algorithm stops and we return the clusters with the corresponding centroid of each. Else, we iterate and recalculate the distance between the readings r i and all centroids to allocate them to the one with the minimum distance. The algorithm stops when the distance between the mean and current centroid is zero in all clusters.

Algorithm 2 K-Means Adopted to Absolute Value Distance Algorithm.

Require:

List of datasets R p = {R p 1 , R p 2 , . . . , R p n }, K, where R p i = (r 1 , f 1 ), (r 2 , f 2 ), . . . , (r k , f k ) Ensure: List of k clusters C p = {C p 1 ,C p 2 , . . . ,C p k } where C p i = (r 1 , f 1 ), value(r 2 , f 2 ), . . . , (r k , f k ) . 1: for j ← 1 to k do 2: C j ← φ 3:
and randomly choose centroid x j belongs to C j 4: end for 5: repeat 6:

for each value r i ∈ R p i do 7:

Assign r i to the cluster C j with nearest x i 8:

end for 9:

for each cluster C j , where j ∈ 1, . . . , k do 10:

Update the centroid x i to be the centroid of all values currently in C j so that

x j = 1 |C j | ∑ r i for i ∈ C j 11:
end for 12: until 13: clusters' centroids no longer changes 14: return C p

Cluster Reduction at the Grid Leader

After applying the K-Means algorithm to the data received by the grid leader we will have K-clusters.

Next, we will reduce the data present in each cluster by utilizing the score system we defined earlier (cf. Section 4.1).

For the K clusters found in (5.3) we will aggregate the values having the same score using their mean value. This approach is similar to the one we initially performed in (4.2) but this time we use the frequency to calculate the mean value. So for each cluster C p i = (r 1 , f 1 ), (r 2 , f 2 ), . . . , (r k , f k ) , if n consecutive values r i , r i+1 , . . . , r i+n have the same score according to our score system, we aggregate them by calculating the mean value:

m j = r i * f i + r i+1 * f i+1 , + • • • + r i+n * f i+n |m i | (2)
At the end of this phase we will have a set of

K clusters C p = {C p 1 ,C p 2 , . . . ,C p k } where C p i = (m 1 , f 1 ), (m 2 , f 2 ), . . . , (m i , f i )
, where f represents the frequency value used to compute the mean and i is ≤ 10 (10 being the number of scores available). This data will be sent to the sink for a decision to take place as illustrated in the next section.

Decision making method at the Sink

The sink receives the data from the grid leader as clusters and stores this data after aggregating it, in a single cluster form D= (m 1 , f 1 ), (m 2 , f 2 ), . . . , (m n , f n ) .

Then it makes a decision based on this data and the evaluated risk as shown in Table 2. To calculate the risk, first we have to find the frequency associated with each score.

We then transform the aggregated data set D into the following form according to our score system: D c = (0, f req 0 ), (1, f req 1 ), (2, f req 2 ), . . . , (9, f req 9 ) .

Where the numbers 0, 1, 2, . . . , 9 represent scores from our score system in Table 1 while f req i represents the frequency of values having a score i.

Furthermore, the weight parameter is calculated according to the following formula:

weight i = f req i * i |D c | (3)
where |D c | is the total frequency of the set D c . Finally, the risk is obtained according to the formula:

0 * weight 0 + 1 * weight 1 + 2 * weight 2 + • • • + 9 * weight 9 6 .
(4) Based on the risk level, the decision will be taken according to Table 2.

Simulation Results

In this section, we show the relevance of our proposed technique after performing a simulation on real sensor data nodes deployed in Intel Berkeley research lab. 47 sensors were deployed where each of them collected temperature, humidity, light and voltage data from 28 February to 5 April 2004. A total of 2.3 millions readings were collected [START_REF] Harb | An enhanced k-means and anova-based clustering approach for similarity aggregation in underwater wireless sensor networks[END_REF]. In these series of simulation, we tested our algorithm while considering the temperature values. The sensors send their collected data to a grid leader where the K-means algorithm will be applied. The value of k is set first to 3, then to 4 and finally to 5. The period size in its turn is set first to 50 readings, then 100 readings and finally to 150 readings. Figure 3 shows the distribution of sensors inside the laboratory.

In these simulations Table 1 is adopted for the score system.

Data Aggregation Ratio at Sensor nodes

As mentioned before, the mean aggregation according to the score system, allows each sensor node to minimize the size of its sensed data by removing similar readings. Figure 4 shows the average number of temperature readings implemented on different size periods, using our technique. The obtained results show that our data filtering model allows sensors to significantly reduce its data transmission in a redundant zone, up to 92% the temperature readings for τ = 50.

Data Aggregation Ratio at Grid Leader

In Figure 5, we show the average number of remaining sets after applying K-means algorithm at the grid leader, when varying K values to 3, 4 and 5 respectively. The obtained results show that K-means can significantly eliminate redundant data sets generated by neighboring sensors. Subsequently, we observe that K-means can reduce up to 36% of the whole received sets at the grid leader. These results confirm that the clustering is a very efficient approach in terms of eliminating redundant data and providing useful information to the end user, comparing to other existing approaches.

Energy Consumption at Sensors

Energy consumption is the main metric being studied in this research. Figure 6 shows the average consumption of energy at sensor level by studying the decrease in the average energy remaining in sensors as a function of rounds. We suppose that the initial energy for each sensor is 50mJ and run the simulation until the energy becomes zero. A round consists of 15 periods. We can observe that the sensors survive for approximately 160 rounds when τ = 50, and 100 rounds when τ = 150.

Energy Consumption at Grid Leader

Figure 7 shows the results of energy consumption of K-means, when varying K. The obtained results are highly dependent on the number of remaining sets after applying K-means (see results of Figure 5); less the number of remaining sets thus less of energy is lost. Indeed, we observe that our technique gives important results regarding reducing the energy consumption of the sent data.

Conclusion and Future Work

Internet of Things (IoT) will play an important role in the future by collecting surrounding conditions and environment information. Thus, designing new energy efficient techniques while preserving data integrity for decision making appears to be crucial in order to eliminate redundant raw data and make such networks operate as long as possible. This paper proposed a real-time framework for energy-efficient and decision making in IoT-based applications. The first phase uses a score aggregation system and aims to reduce raw data collected by the sensors. The second phase allows grid leader nodes to eliminate redundant data collected by neighboring nodes using K-means clustering algorithm. The third phase will be dedicated to decision making based on a risk-decision table. Our technique has been evaluated based on a simulation on real sensors data. The results obtained with our technique showed significant energy savings.

Many future directions for our work can be traced. We seek to try another data clustering methods at the grid leader level, like decision trees and neural networks.

Figure 2 :

 2 Figure 2: Periodic data reduction scheme.

i

  contains the mean value of the readings having same score, as well as the weight of the mean value (lines 11-13). The weight of the mean value indicates the number of readings represented by the mean value. Note that only consecutive values having same score are aggregated by their mean, and not all values within R p i having same score. The algorithm is represented in algorithm 1. Algorithm 1 Sensor Mean Aggregation Algorithm. Require: Reading vector: R p i = [r 1 , r 2 , . . . , r τ ]. Ensure: Vector of representative readings of R checkbe f ore = Score(r 0 ) // score of first reading 3: f requency = 0 4: for each set reading r i ∈

Figure 3 :

 3 Figure 3: Distribution of sensors in Intel Berkeley lab.

Figure 4 :

 4 Figure 4: Aggregation ratio at each sensor during different periods.

Figure 5 :

 5 Figure 5: Filtering set ratio after applying K-means at the grid leader.

Figure 6 :

 6 Figure 6: Average energy consumption at sensors level.

Figure 7 :

 7 Figure 7: Percentage energy consumption.

Table 1 :

 1 Score System

	Measure Score
	≤16	0
	]16,17]	1
	]17,18]	2
	]18,19]	3
	]19,20]	4
	]20,21]	5
	]21,22]	6
	]22,23]	7
	]23,24]	8
	>24	9

Table 2 :

 2 Risk Decision

	Risk	Decision
	≤0.2	d 1
	]0.2, 0.4]	d 2
	]0.4, 0.6]	d 3
	]0.6, 0.8]	d 4
	> 0.8	d 5