Lydia Habib

Ouazna Oukacha

Simon Enjalbert
email: simon.enjalbert@uphf.fr

Towards Tramway Safety by Managing Advanced Driver Assistance Systems depending on Grades of Automation

Keywords: Grades of Automation, Levels of Automation, Tramway, Advanced Driving Assistance Systems, Haptic Control, Automatic Control, Human-Machine System

This paper presents a preliminary study for the assessment of tram safety by managing Advanced Driver Assistance Systems depending on Grades of Automation. The Grades/Levels of Automation in automotive, aeronautics, maritime and railway systems are presented and compared with each other. Then, according to especially the implication level of a haptic system in each tram driving task, Grades of Automation for trams are proposed. In addition to the haptic system, a visual one that uses a Head-Up Display is defined. These systems are designed to help the tram driver cope with potential hazards by having a defensive driving. Therefore, the proposed Grades of Automation and the driver assistance systems are used in order to propose an experimental method to explore how this automation can affect the tram driver performance and the Human-Machine System safety.

INTRODUCTION

Tramway, tram or streetcar, also called trolley is a large and heavy electric vehicle that transports people, usually in cities, and runs on tracks in the road. The tram drivers have to manage a complex environment shared with pedestrians and other vehicles. Furthermore, they have to respect the traffic signals while boarding and serving passengers at different tram stations. Tram drivers also have to be punctual and ensure Human-Machine System security and, mainly the passengers safety.

Trams vehicles have a higher transport capacity, lesser traffic jam problem and lower emission of pollutants than other public transport vehicles. Therefore, trams have become an essential urban transport in many countries, especially in big cities. However, by their design and characteristics, trams are not always adapted to the complex and cramped environment they are used. From this observation, safety concerns arise and give place to many studies [START_REF] Vandenbulcke | Predicting cycling accident risk in brussels: a spatial case-control approach[END_REF], [START_REF] Richmond | Exploring the impact of a dedicated streetcar rightof-way on pedestrian motor vehicle collisions: a quasi experimental design[END_REF], [START_REF] Marti | Tram safety in mixed traffic: Best practices from switzerland[END_REF] and [START_REF] Currie | Vehicle and pedestrian safety at light rail stops in mixed traffic[END_REF]). [START_REF] Naweed | A study of tram collisions on a mixed-traffic environment in an australian metropolitan setting[END_REF] have identified factors related to tram collisions, in particular: lack of tram driver's situation awareness, time pressure and organizational behaviour. [START_REF] Naznin | Key challenges in tram/streetcar driving from the tram driver's perspective-a qualitative study[END_REF] have determined the need to investigate the road user factors affecting tram road safety and explored the key challenges in tram driving. To keep everyone safe as much as possible in and around the tram, and to run on-time are the priority challenges. The on-time running causes pressure and increases risk taking attitudes for a driver (going through red lights, for example), which endangers safety. [START_REF] Cacciabue | Unified driver model simulation and its application to the automotive, rail and maritime domains[END_REF] have studied the driver behaviour modelling and several types of drivermachine interaction in the different transport domains.

A concept involving the distribution of control between the human and machine system is called the Levels of Automation (LoAs) [START_REF] Sheridan | Human and computer control of undersea teleoperators[END_REF]). This paper deals with this concept and proposes Grades of Automation (GoAs) for trams, by defining the driving tasks allocation among the tram driver and assistance systems. Therefore, it establishes an experimental method to assess the impact of these GoAs on the Human-Machine System safety.

The section 2 of this paper presents a state of the art of LoAs by comparing different transport industries. Section 3 proposes driver assistance systems and GoAs for trams. The section 4 describes the general concept of the experimental tests. Finally, the section 5 provides the conclusion and perspectives.

STATE OF THE ART ON AUTOMATION IN TRANSPORT INDUSTRIES

Automation tends to reduce the scope of human activity by limiting the allocated tasks and makes the systems more and more autonomous. However, today many researchers consider the image of an increasing complexity of automated systems, and the role of human operator becomes increasingly important [START_REF] Parasuraman | Humans: Still vital after all these years of automation[END_REF]). Automation has many strengths, including lack of emotion and distraction, ability to implement actions precisely and to do many different tasks immediately, but also it has weaknesses, especially because it lacks the flexibility that humans have, which allows them to adapt to new or unpredictable events. Therefore, automation can be implemented with different degrees of reliability, and its introduction into a system requires careful preliminary testing and analysis to ensure the best fitting between Human and Machine while mitigating their respective weakness in order to get maximum Human-Machine performance. The LoAs are introduced and discussed in many other transport industries such as: automotive, aeronautics, maritime and railway sectors.

Automotive sector

The Society of Automotive Engineers (SAE) distinguishes 6 levels of driving automation from manual control (without automation) to full automation as defined in J3016 (SAE ( 2016)).

• Level 0 (manual control), the human driver performs all the driving tasks. • Level 1 (assisted driving) consists of the assistance tools called Advanced Driver Assistance Systems (ADAS) implemented in the vehicle, assisting the driver from time to time in certain tasks such as cruise control.

• Level 2 (partial automation), the vehicle system is capable of performing certain tasks such as acceleration and guidance on its own. However, the driver must remain engaged in the driving task and monitor the environment at all times. • At level 3 (conditional automation), the vehicle system may as well perform certain tasks on its own and ensure autonomous control of its environment. However, the driver must be able to regain control at the request of the vehicle [START_REF] Borojeni | Comparing shape-changing and vibro-tactile steering wheels for take-over requests in highly automated driving[END_REF]). • At level 4 (high automation), the vehicle system can also perform certain tasks and ensure the control of its environment under certain conditions without the driver. • At level 5 (full automation), the vehicle system can perform all driving tasks autonomously without the driver under all conditions.

Aeronautic sector

Unlike the automotive sector, a taxonomy of LoAs in aeronautics has not been properly defined in the literature.

In general aviation, SAE presented a classification of LoAs based on that of the automotive domain [START_REF] Airbus | Levels of aviation autonomy[END_REF]). In reference to [START_REF] Crespo | Less automation and full autonomy in aviation, dilemma or conundrum?[END_REF], the authors also proposed another description of LoAs in aeronautics. However, LoAs could be identified from the technological evolution of the civil transport airplane [START_REF] Airbus | A statistical analysis of commercial aviation accidents 1958-2019[END_REF]).

• Warning System (TAWS), and Airborne Collision Avoidance System (ACAS). The automated systems complete a wide variety of actions with pilot's permissions and decisions (the system identifies and proposes an action to face risks induced by the tasks, while human takes the decision to accept or not this action). • The fourth and latest generation of civil transport airplane was established in 1988. It brought more sophisticated technologies like the Fly-By-Wire (FBW) control system and flight envelope protection. Using the FBW technology, the pilot tells the flight computer what to do, then the computer translates the pilot's intention into action and executes the maneuver. At this high LoA, the pilot is still in the loop emergency situations.

Maritime sector

All levels distinguished by SAE cannot directly be applied to maritime passenger transport due to complexity of the environment (visibility, weather conditions and etc.). Like in the aeronautic sector, the taxonomy of LoAs is not clearly defined for maritime domain and it is known as "Autonomy Level (AL)". The International Maritime Organization (IMO) defined 4 degrees of automation, where it was presented as provisional definitions of autonomous ships. [START_REF] Register | Cyber-enabled ships-shipright procedure-autonomous ships[END_REF] proposed 7 ALs in maritime transport.

• AL0 (manual): this level is similar to other sectors, where human manually controls all actions. • AL1 and AL2 are called "On-board Decision Support" and "On & Off-board Decision Support" respectively, the human operator directs and controls all actions. Data is provided by systems on board for AL1 and it is given either on board or off the ship for AL2. • AL3 and AL4 are called "'Active' Human in the loop" and "Human in the loop: operator/supervisory" respectively. The decisions and actions are performed with Human supervision, the pilot can take control over the ship at any time for AL3 and he intervenes only if necessary for AL4. • AL5 and AL6 are both called "full automation", all decisions are entirely made and actioned by the system, the Human intervenes very rarely for AL5 and never for AL6.

Railway sector

In railway sector, the degrees of automation are named GoAs rather than LoAs. GoAs are defined in IEC 62290 (International Electrotechnical Commission) for Automatic Train Operation (ATO). The motivation to increase the GoAs of the rolling stock in the railway domain is to expand the systems' capacity and performance without endangering safety. The railway automation is described through 5 Grades of Automation (cf. Cappaert-Blondelle ( 2012)). The automated tasks are mainly concerned with train acceleration and braking, departure and stopping at the stations, monitoring of driving environment (e.g. event detection, sign recognition, etc.), doors closure and opening, and management of emergencies (cf. Table 1).

Table 1. Grades of Automation in rail stock sector.

(1) Prevention of collisions with obstacles and persons on tracks (2) Handling fire/smoke and passengers requests (call/evacuation. . . )

(3) Operation Control Center

Description

• GoA-0, the train driver must drive and ensure the safety of the train system, this level is called "onsight operation" and is similar to the current grade of the tram system. • GoA-1 represents the manual operation with the ATP system, the train driver controls acceleration and braking. The ATP system guarantees that the driver respects the speed limits, and it ensures the safety operation. The tram driver controls departure and stopping at the stations, doors closure and opening. Furthermore, he supervises the guideway and manages the emergencies. • GoA-2 is characterized by the manual driving of the train with ATP and ATO systems (most common today), the driver operates the doors and starts the train. The system is responsible for controlling the speed and stopping the train at the stations. The train driver must be ready to take over control at any time and handle emergency situations. • GoA-3 is the driverless control grade, the system is responsible for driving, departure and stopping the train. The train attendant operates the doors and takes over control in case of emergencies (driverless train). • GoA-4 is the unattended train operation, all the tasks are performed by the system without any on-train staff.

Comparison between transport industries

A comparison between the LoAs in automotive, aeronautics, maritime and railway sectors is given in the table 2.

As mentioned above, the high LoAs are already implemented in the railway sector. However, they cannot be directly transposed to the control of trams, because trams operate in a less secure, more complex and dynamic road environment than that of metros and trains. The trams can therefore be the subject to various disturbances such as meteorological changes and risky obstacles on the track. Due to these limitations, today it remains impossible to automate everything and design an efficient tram system to cope with all complex demands of the dynamic road environment autonomously. Therefore, the autonomous tram is not our objective, so the human driver will always be present in the cabin control.

The following part presents the different GoAs of the tram and the way to apply them for Advanced Driving Assistance System in order to improve Human-Machine System safety.

GRADES OF AUTOMATION FOR TRAMS USING ADVANCED DRIVER ASSISTANCE SYSTEMS

The trams operate in a temporal demanded mixed traffic environment that requires a high level of situation awareness, with consistently high perceptual demands for collision avoidance. Because of the nature of the tramdriving task and its relation with the road environment, our study is limited to GoA-0, GoA-1 and GoA-2 of the railway sector. GoA-0 is currently being used to drive the trams. GoA-1 is studied by La [START_REF] Delfa | Eco-driving command for tram-driver system[END_REF] and [START_REF] Enjalbert | On the eco-driving trajectory for tramway system[END_REF], it is called the ecodriving system that automatically generates speed profiles for the tram (ATP system). In this work, we defined other GoAs based on the GoA-2 which allows speed regulation.

Grades of Automation for trams

The GoAs for trams are defined from the allocation of two tasks (acceleration/deceleration and stopping at the station) between the driver and the automated system. Given the importance of the safety aspect of the driver-tram system, which is the focus of this work, we considered the dead man's switch device to study whether the safety of the Human-Machine System is maintained when the dead man's switch is disabled at a high GoA (GoA-2.3). The dead man's switch or driver's safety device is commonly used in the railway domain to permanently monitor the tram driver consciousness. The defined taxonomy of GoAs for trams is presented in Table 3.

The defined GoAs determine the force between the driver and an automated system applied to the manipulator when performing the acceleration/deceleration task. We note System Desactivated that at each GoA, the driver controls the tram departure.

The GoA-0 is equivalent to the GoA-0 of the rail stock taxonomy, where the driver is the only responsible for driving the tram. The GoA-1 is equivalent to the GoA-1 of the rail stock taxonomy, where the driver controls the acceleration/deceleration task with an automated system that grantees the respect of the speed limits. The GoA-2.1, GoA-2.2 and GoA-2.3 are equivalent to the GoA-2 of the rail-stock taxonomy. However, At GoA-0, GoA-1 and GoA-2.1, the driver is responsible for stopping the tram at stations except for the GoA-2.2 and GoA-2.3. Furthermore, at each GoA the dead man's switch is activated except for GoA-2.3.

In order to perform all the above mentioned driving tasks of the tram, two transmission systems are defined: visual and haptic. The visual system enables the driver to observe and analyse the environment and the haptic system to control and drive the tram.

Head-up visual system

The head-up visual system is based on a Head-Up Display (HUD). The HUD is a screen that is used to display an image into the driver's line of sight on a transparent display. It helps to improve the driver's situation awareness by getting information without looking away. HUDs are widely used in both military and commercial aviation with gradual adaptation in general aviation and passenger cars but much less common in rolling stock. The developed HUD is represented in Fig. 1, with the various indicators labelled in orange on the interface.

The distance to the next speed limit is represented by an arc (cf. label 5 in Fig. 1) from the current speed limit until the next lower one (cf. label 3 and 4 in Fig. 1

respectively).

The arc is displayed when the tram reaches a given distance from the next lower limit speed. In fact, we argue that braking is safe. The tram driver must not exceed the speed limit and has to anticipate deceleration. Therefore, it is important to inform him in advance of only the decrease in the speed limit. On the contrary, the increase in speed limit can be unanticipated without endangering safety.

The size of the arc decreases in proportion to the distance remaining from the next lower speed limit.

The target speed (cf. label 6 in Fig. 1) is calculated by an eco-driving controller developed in previous work La [START_REF] Delfa | Eco-driving command for tram-driver system[END_REF]. The controller solves online an optimal control problem in order to select the best speed profile that minimizes the tram-driver energy consumption and enhances the safety. It takes into consideration criteria such as the timetable, the tram and the track models.

Haptic system

According to the GoA presented in the Table 3, a haptic manipulator is used to provide acceleration limits to the driver or to perform the acceleration/deceleration task autonomously without the intervention of the driver. The haptic manipulator structure is similar to the manual one with an added function of a haptic feedback that would allow to provide sensory stimuli to the driver for better situation awareness and efficient control. The single axis manipulator is the structure whose vertical axis can move up and down. This movement is indicated by the two arrows on the right side of the manipulator, with 5 color zones that are dedicated to the different types of operations (cf. Fig. 2) and as explained in detail by La [START_REF] Delfa | Design of a cooperative eco-driving rail control system: an experimental study[END_REF]:

• Green zone: is indicated by an arrow pointing upwards. This zone allows the driver to increase the tractive effort or to reduce/maintain the speed of the tram) • White zone: is called the neutral zone and is located between the two green and yellow zones. It is a transition point between steering and braking. Thus, the tractive effort in this zone is equal to zero. We note that the manipulator returns to the neutral zone each time the tram stops. • Yellow zone: is indicated by an arrow pointing downwards. This area allows the driver to reduce the tractive effort and to activate the electric braking to stop the tram smoothly. • Orange zone: allows the driver to apply the reinforced electrical braking and to activate the mechanical one. • Red zone: corresponds to emergency braking.

At GoA-0, the driver performs the acceleration/deceleration task without any assistance from the haptic manipulator. At GoA-1, the driver controls the acceleration and deceleration. However, the haptic system prevents and ensures the safety operations. Indeed, the driver controls the tram speed within a certain safety margin, beyond which the haptic system alerts the driver. Then, if the driver does not decelerate, the haptic system regains authority and progressively applies a stiffness in the manipulator until a mechanical stop is reached. At GoA-2.1, GoA-2.2 and GoA-2.3, the haptic system is responsible for driving the tram. However, the driver must stay fully alert and be ready to take control at any time. If the driver intervenes on the control (exerts a force on the manipulator), the acceleration/deceleration task is allocated to him and the authority is managed in the same way as at GoA-1. The HUD and the haptic manipulator will be implemented in the PSCHITT-Rail simulator for a future experiment which is presented in the following part.

FUTURE EXPERIMENT

This section proposes an experimental method for a future experiment. Its objective is to evaluate the impact of the defined GoAs (cf. Table 3) on the driver performance and the Human-Machine System safety.

Method

Materials. The PSCHITT-Rail (Collaborative, Hybrid, Intermodal Simulation Platform in Land Transport-Rail) designed by LAMIH was used as the tram simulator for this experiment (cf. Fig 3). The PSCHITT-Rail simulator is a cabin installed on a motion platform with six degrees of freedom. It is composed of real tram equipments interfaced with the software part. The simulator is equipped with a dashboard, a manipulator, a realistic sound rendering and a visual field projected on a screen giving a panoramic view of 225 • .The simulator allows to implement personal dynamic tram model, to record the simulation data (speed, manipulator position...) and to create different scenarios, for instance, by modifying the density of cars and pedestrians. It is based on the OK-SimRail simulation software developed by AVSimulation company.

Procedure. A slide show of the simulator and driver assistance systems description will be given to the participants before the training session. Then, they will be asked to fill out a consent form and reply to a demographic questionnaire. Before starting the testing, the participants will be trained on the driving task using the tram simulator with the HUD and the suitable GoA. Each participant will be allowed to ask any questions related to the experimental platform or the task to perform. When the training session will be correctly performed by the participants, the testing session will be started. At the end of each experimental condition (GoA-0, GoA-1, and GoA-2.1 or GoA-2.2 or GoA-2.3), the participants will be asked to answer some questions about their experience during the experiment. In order to avoid the learning effect, the scenario in the training simulated environment and the experimental one will be changed. In addition, to avoid the order effect, the GoA order will be counter-balanced between the participants. The participants will have to safely and punctually drive/supervise the simulated tram along a 6 km-long simulated track. This track will resembled the drive from station A to station B with 12 stations to stop. The allowed speed limits will be ranged from (30 -70) km/h so that the participants will drive approximatively 4 min under each GoA. At the end of each experimental condition, the participants will be asked to fill out some other questionnaires including questions corresponding to their experience during the experiment.

Data collection.

Objective and subjective data will be collected during the experiment. The objective data are:

• The different speeds (tram, limits, targets).

• The times at the stations (expected and arrival).

• The number of accidents.

The subjective data are the responses to post-experiment questionnaires related to the feelings of comfort, safety, quality of control and workload.

Hypothesis and Indicators

During an itinerary, the driver is subjected to several stressful traffic situations that lead to a change in his behaviour. In fact, the tram driver can be disturbed by, for example, traffic lights, speed limit signs, station stops, crosswalks, turns, intersections, and cars. The future experiment aims to investigate whether the automated driving (GoA-2.1, GoA-2.2 and GoA-2.3) improves performance and safety in comparison to the no and less automated one (GoA-0 and GoA-1). These driving modes will be examined during the experiment to test these following hypothesis:

• H1: The respect of speed limits increases with the GoA regarding the "acceleration/deceleration" task. • H2: The punctuality (schedule respect) increases with the GoA regarding the "stopping at the station" task. • H3: The number of accidents decreases when the GoA increases.

• H4: The feelings of comfort, safety, quality of control increase with the GoA while the workload decreases.

These hypothesis will be tested using the data presented in Section 4.1. These data will be manipulated to obtain Indicators that will respectively be used for each hypothesis:

• I1: The difference between the targeted speed and the tram speed. • I2: The difference between the time a station is reached and the one it was expected to. • I3: The number of times over speeding, and potentially the number of people and cars getting hit by the tram. • I4: Post experiment questionnaires.

Thanks to these indicators, we expect to validate the hypothesis and to conclude about the impact of Advanced Driver Assistance Systems depending on GoA on the Human-Machine System safety.

CONCLUSIONS AND PERSPECTIVES

In this paper, we have presented the Levels/Grades of automation in the aviation, rail, road and maritime transports and then made a comparison among them. Afterwards, we defined two driver assistance systems dedicated to trams: a visual one that is presented by an HUD and a haptic one that is materialized by a manipulator with a haptic feedback. Then, we proposed a taxonomy of GoAs for trams that is especially related to the haptic system degrees of assistance. The objective of the haptic and visual driving assistance systems is to improve the drivertram system safety by enhancing the quality of control and the driver situation awareness. These systems and the GoAs are being implemented on the PSCHITT-rail tram simulator that will soon be used to test the hypothesis in order to identify the best Human-Machine System cooperation, i.e. GoA.

  This work has been funded by the Project: ELSAT 2020 by CISIT / GS2RI: Greener & Safer Rail Road Interaction.

Fig. 1 .

 1 Fig. 1. The Head-Up Display.(1) the current speed and the unit it is measured in. (2) the needle moves around the gauge as a visual representation of speed. (3) the current maximum permitted speed. (4) the next speed limit. (5) a simplified representation of the distance to the next lower speed limit. (6) the current target speed. (7) the next station and the time this station is expected to be reached.

Fig. 2 .

 2 Fig. 2. Haptic driver assistance system of a tram.

Fig. 3 .

 3 Fig. 3. PSCHITT-rail tram simulator.

Table 2 .

 2 Comparison of Levels of Automation in automotive, aeronautics, maritime and railway sectors

	Automotive	Aeronautics	Maritime	Railway
	No automation			No automation
	(LoA0)	Manual	Manual (Al0)	(GoA0)
	Driver assistance			Manual driving
	(LoA1)	Assisted	(Al1) and (Al2)	with ATP (GoA1)
	Partial automation			Manual driving
	(LoA2)	Highly assisted (Al3) and (Al4) with ATP and ATO (GoA2)
	Conditional automation (LoA3) High automation	Highly automated (Al5) and (Al6)	Driverless train (GoA3)
	(LoA4)
	Full automation			Unattended train
	(LoA5)	/	/	(GoA4)

Table 3 .

 3 Description of the GoAs for trams

	GoAs	Acceleration	Stopping	Dead
		/Deceleration	at the station man's switch
	GoA-0	Driver	Driver	Activated
	GoA-1	Driver/System	Driver	Activated
	GoA-2.1 System/Driver	Driver	Activated
	GoA-2.2 System/Driver	System	Activated
	GoA-2.3 System/Driver

ACKNOWLEDGEMENTS

The present research work has been supported by: The ELSAT 2020 project / GS2RI: Greener & Safer Rail Road Interaction, The European Community, The French Ministry of Higher Education and Research, And The Hauts-de-France Region. The authors gratefully acknowledge the support of these institutions.


Spyridon Kamvissis

LONG TIME BEHAVIOR FOR THE FOCUSING NONLINEAR SCHROEDINGER EQUATION WITH REAL SPECTRAL SINGULARITIES

We consider the effect of real spectral singularities on the long time behavior of the solutions of the focusing Nonlinear Schrödinger equation. We find that for each spectral singularity λ ′ ∈ R, such effect is limited to the region of the (x,t)plane in which λ ′ is close to the point of stationary phase λ 0 = -x 4t (the phase here being defined in a standard way by, say, the evolution of the Jost functions). As we approach that region, the solution performs decaying oscillations; the order of decay is O(( logt t ) 1/2 ). Inside that region the solution is asymptotically identified as a selfsimilar solution of NLS expressible in terms of a Painlevé 4 transcedent. We prove our result by using the Riemann-Hilbert factorization formulation of the inverse scattering problem. We recover our asymptotics by transforming our problem to one which is equivalent for large time. Around the shock front the limiting "model" Riemann-Hilbert problem can be interpreted as the one corresponding to the genus 0 algebro-geometric solution of the equation. Inside the shock region, the Riemann-Hilbert problem is related to the Painlevé 4 equaton.

1.INTRODUCTION

We consider the nonlinear Schrödinger equation (focusing case)

(1.1) iq t + q xx + 2q|q| 2 = 0 under initial data (1.2) q(x, 0) = q 0 (x), belonging in the Schwartz class.

As is well known (see [NMPZ], [FT]), the problem (1.1)-(1.2) can be integrated through the method of inverse scattering. We will here present some of the results we will need without proof.

The associated linear system is

(1.3) ψ x = iλ iq(x) iq(x) -iλ ψ,
where the bar denotes conjugation. Jost functions ψ 1 , ψ 2 , φ 1 , φ 2 are defined on the real line as (column vector) solutions of (1.3) satisfying the asymptotic conditions

(1.4)

ψ 1 (x, λ) ∼ e iλx 0 , as x → +∞, ψ 2 (x, λ) ∼ 0 e -iλx , as x → +∞, φ 1 (x, λ) ∼ e iλx 0 , as x → -∞,
φ 2 (x, λ) ∼ 0 e -iλx , as x → -∞.

Furthermore, ψ 1 and φ 2 can be meromorphically extended to the upper half-plane, while ψ 2 and φ 1 can be meromorphically extended to the lower half-plane. Indeed, one has (1.5) ( ψ 1 (x, λ)e -iλx φ 2 (x, λ)e iλx ) → I, as λ → ∞, Imλ ≥ 0, ( φ 1 (x, λ)e -iλx ψ 2 (x, λ)e iλx ) → I, as λ → ∞, Imλ < 0.

I is here the identity matrix. We point out the symmetry

(1.6) ψ(x, λ) = 0 1 -1 0 ψ(x, λ),
where ψ = ( ψ 1 ψ 2 ); the same symmetry is satisfied by φ = ( φ 1 φ 2 ). On the real line, φ and ψ are solutions of system (1.3). Hence there exist 'scattering coefficients' a(λ), b(λ) such that (1.7)

φ 2 (x, λ) = a(λ)ψ 2 (x, λ) + b(λ)ψ 1 (x, λ) φ 1 (x, λ) = ā(λ)ψ 1 (x, λ) -b(λ)ψ 2 (x, λ).
Although ā and b are a priori independent of a and b, one can see from the symmetries above that they are after all their complex conjugates. Furthermore one can show

(1.8) |a(λ)| 2 + |b(λ)| 2 = 1.
The time evolution of the scattering coefficients is given by (1.9) a(λ, t) = a(λ, 0), b(λ, t) = b(λ, 0)e 4iλ 2 t .

It turns out that a(λ) can be analytically extended to the upper half-plane, while ā(λ) can be analytically extended to a function a * (λ) = ā( λ) in the lower half-plane. In general, this is not also true for b. Generically, a has only a finite number of zeros in the upper half-plane and no zero at all on the real line (cf. [BC]). However, there are cases where this is not true. One can have, for example, an infinity of non-real zeros with a limit point on the real line (see [Z] for an example).

It is well-known that in the generic case, non-real zeros of a correspond to solitons for long times (see [FT] for example). Our goal is to study the effect of real zeros of a. We will only consider the case of finitely many zeros of a. For simplicity we will state and prove our results in the case where no non-real zeros of a are present and only one real simple zero exists. However, it should eventually become clear that this is only a superficial constraint, and indeed we will indicate at the end of this work what happens in the more general case (of finitely many zeros).

A simple example of initial data producing exactly one real spectral singularity is the following ( [CK]). Let X > 0 and

(1.10)

u 0 (x) = π 2X , 0 < x < X, = 0, otherwise.
Then a(λ) has exactly one (simple) zero at λ = 0 and a ′ (0) = -2iX π . Even though u 0 is discontinuous, the standard direct and inverse scattering theory is applicable.

We define the 2 × 2-matrix-valued function Ψ as follows. Let

(1.11)

Ψ = ψ 1 e -iλx φ2e iλx a(λ) , for Imλ > 0, = φ1e -iλx a * (λ)
ψ 2 e iλx , for Imλ < 0.

Letting Ψ + and Ψ -denote the limits of Ψ on the real line from above and below respectively, we have (after a few calculations)

(1.12)

Ψ + (z) = Ψ -(z) 1 r(λ)e 2iλx+4iλ 2 t r(λ)e -2iλx-4iλ 2 t 1 + |r(λ)| 2 , Imλ = 0,
where r(λ) = b(λ,t=0) a(λ,t=0) . Note that the jump matrix has determinant 1. Finally, one can prove that a(λ

) = 1 + O(1/λ) as λ → ∞, Imλ ≥ 0. Hence (1.13) Ψ(λ = ∞) = I.
We thus end up with a Riemann-Hilbert factorization problem: Ψ is a matrix function, analytic in the complement of the real line, satisfying the jump condition (1.12) and the asymptotic condition (1.13).

Note that in the generic case of finitely many zeros off the real line and no real zero, Ψ is meromorphic and neither Ψ + or Ψ -nor the jump matrix have any singularities. In the case we are interested in, however, both Ψ ± and the jump matrix have singularities exactly at the zeros of a(λ).

Conversely, the solution of the Riemann-Hilbert problem enables us to recover q(x, t). Indeed (see e.g [NMPZ])

(1.14) q(x, t) = -2lim λ→∞ λΨ 12 .

Thus, the initial value problem (1.1)-(1.2) is reduced to the above Riemann-Hilbert on which we focus from now on.

The interest of the problem treated in this paper is twofold. On the first hand, as we will see later, the physical effect of the spectral singularity is a 'collisionless shock' type phenomenon; we thus have an interesting connection with the theory of 'dispersive shocks' for nonlinear wave equations (cf.also [DVZ], [AS]). On the other hand, ours is a first step towards the completion of the solution of the problem of long-time asymptotics of integrable equations in the case of Schwartz data, in the following sense: although the related direct and inverse scattering problems are now completely solved (see [Z], [START_REF] Deift | Direct and Inverse Scattering on the Line with Arbitrary Singularities[END_REF]) for the most general cases of Lax operators and even in the non-generic exceptional cases of data for which there are either infinitely many spectral singularities off the associated Riemann-Hilbert contour or there are (possibly infinitely many) spectral singularities on the contour, the longtime asymptotics problem is still far from having a complete solution, even in cases as simple as the NLS equation. In fact, the present paper is the first of a series; in a recent article (see [K]) we treat the infinite-soliton case, while a treatment of the case of infinitely many real (i.e. on the Riemann-Hilbert contour) spectral singularities for the NLS equation will appear soon.

We now state our main result, to be proved in section 3. THEOREM 1.1. Let q be the solution of (1.1) with initial data in the Schwartz class, and such that a (simple) spectral singularity exists at λ = 0 and nowhere else. Let λ 0 = -x 4t , τ = tλ 2 0 and M be a given positive constant. Then the leading order asymptotics of q, as t → ∞, is as follows.

In region I: x < 0, λ 0 < -M, q is given by formulae (2.5) and (2.6). In region II: x < 0, λ 0 → 0, τ → ∞, q is given by formula (3.18). In region III: λ 0 → 0, τ < M, q is given by (3.19). In region IV: x > 0, λ 0 → 0, τ → ∞, q is given by (3.18). In region V: x > 0, λ 0 > M, q is given by (2.5)-(2.6).

The plan of the rest of the paper is as follows. In section 2, we solve the Riemann-Hilbert factorization problem in the case where the zeroes of a, are away from the stationary point λ 0 = -x 4t of the phase Θ = λx + 2λ 2 t. Indeed, we show that no spectral singularity has any effect at all in the long time behavior of q(x, t). In section 3, we consider the more interesting case where λ 0 -λ ′ → 0 with time, for some real singularity λ ′ . In section 4, we discuss a generalization of our results.

The problem of a real spectral singularity was first considered by Ablowitz and Segur. In [AS] they study the collisionless shock phenomenon for the KdV equation with decaying initial data and they dedicate a small section to the focusing nonlinear Schroedinger equation, where they address the problem of a real spectral singularity by considering non-real ones, say κ 0 , and taking the limit as Imκ 0 → 0. Their treatment is heuristic and non-rigorous. It is satisfactory however that their estimate for the decay of the solution on the 'shock' front agrees with ours. For the sake of the reader, we present the result of Ablowitz and Segur below.

RESULT of [AS]. In the shock front region (corresponding to our regions II and IV), the solution of (1.1)-(1.2) has the following asymptotic expression

q(x, t) = t -1/2 R(x/t, t)e itθ(x/t,t)
where

(1.15) θ ∼ 1 4 x 2 t 2 + 2 logt t f 2 ( x t ) + O( 1 t ), R ∼ f ( x t ) + 4f ( x t )(3[f ′ ( x t )] 2 + f ( x t )f ′′ ( x t )) logt t , f 2 (-4k) ∼ 1 4π (logt -loglogt -2logm),
where k

= λ ′ + m( logt t ) 1/2 .
In particular (cf. (4.10) of [AS])

|q| ∼ 1 2π 1/2 ( logt t ) 1/2 .
Note that this formula agrees with our (3.18). The method of this paper follows the spirit of the work of Deift and Zhou (see [DZ], [DVZ]), who invented a new (and for the first time rigorous) method for recovering long-time asymptotics of integrable 'soliton' equations, by using the fact that the inverse scattering problem for such equations can be stated as a Riemann-Hilbert factorization problem. We also make use of results of Deift, Its and Zhou for the defocusing nonlinear Schroedinger equation ( [DIZ]). We note that the present work is the first in this spirit that deals with problems for which the jump matrix blows up at a point. ACKNOWLEDGEMENTS. We wish to thank Jean-Claude Guillot for pointing our attention to this problem and for the reference [CK] as well as illuminating discussions. We also thank Percy Deift for discussions concerning Riemann-Hilbert problems on a Riemann surface, Daniel Battig for discussions concerning the periodic problem for the NLS system and Dan Dix for helpful discussions and for pointing out reference [AS]. Finally we thank the referees for helpful comments concerning our presentation.

AWAY FROM A SINGULARITY

As mentioned in the introduction, Deift, Its and Zhou have analyzed the long time behavior of the defocusing nonlinear Schroedinger equation. In that case, the Riemann-Hilbert problem agrees (modulo a minus sign) with (1.12)-(1.13) except that no spectral singularities exist at all (real or non-real). The question is how is the analysis of the problem affected when Ψ and the jump matrix in (1.12) have a singularity. In this section, we show that when for all singularities λ ′ , λ 0 -λ ′ = O(1), they have no effect at all. We will only restrict ourselves to the case λ 0 > λ ′ , since obviously the case λ 0 < λ ′ is similar (and easier).

1. We begin by considering an auxiliary scalar factorization problem. Let d be a function analytic in C \ (-∞, λ 0 ] such that (2.1)

d + (λ) = d -(λ)(1 + |r(λ)| 2 ) for -∞ < λ ≤ λ 0 , d + (λ) = d -(λ) for λ > λ 0 d → 1 as λ → ∞.
When there is no spectral singularity at 0, it can be easily checked that the solution of the above scalar problem is given by

d(λ) = exp( 1 2πi λ0 -∞ log(1 + |r(s)| 2 ) s -λ ds).
PROPOSITION 2.1. Problem (2.1) has a unique solution which has no zeros and its only singularities are at zeros of a. More precisely, near a zero of

a d + (λ)a(λ), d(λ)a(λ), d-(λ)
ā(λ) and d(λ) a * (λ) are bounded above and below. PROOF: First note that

1 + |r(λ)| 2 = 1 |a(λ)| 2 = 1 a(λ)a * (λ) , for λ ∈ R.
Also recall that a is analytic in the upper half-plane, a * is analytic in the lower half-plane and a(λ

) = 1 + O( 1 λ ) as λ → ∞, Im λ ≥ 0.
Consider the contour depicted in figure 2.1 (the exact choice of lines l 2 and l 3 is irrelevant provided a, a * have no zeros in regions A 2 , A 3 or on lines l 2 , l 3 ) and define

δ(λ) = d(λ), λ ∈ A 1 , δ(λ) = d(λ)a(λ), λ ∈ A 2 , δ(λ) = d(λ)(a * (λ)) -1 , λ ∈ A 3 .
δ satisfies the following scalar problem: it is analytic in C \ (l 2 ∪ l 3 ) and,

δ + = δ -a, on l 2 , δ + = δ -(a * ) -1 , on l 3 .
As a has neither zeros nor poles on l 2 ∪ l 3 we see that this scalar factorization problem has a unique solution with neither zeros nor poles; even though a has a discontinuity at λ 0 , δ is bounded near λ 0 (see e.g. [G], p.448). The result follows.

Figure 2.1

It can be easily seen now that near λ 0 the behavior of d is

d(λ) ∼ (λ -λ 0 ) -iν exp( 1 2πi λ0 -∞ |log(s -λ)|dlog(1 + |r(λ(s))| 2 ) where ν = 1 2π log(1 + |r(λ 0 )| 2 ) > 0.
2. We will next provide an appropriate contour deformation (following [DIZ]) which will be guided by an analysis of the signature of the phase Θ = λx + 2λ 2 t appearing in the exponents of (1.12) (see figure 2.

2).

A fundamental fact is that the jump matrix of (1.12) admits the following factorizations (hence justifies our construction of d).

d 0 rde -2iΘ d -1 d -1 rd -1 e 2iΘ 0 d f or λ > λ 0 and d - rd -1 -e 2iΘ 1+|r| 2 0 d -1 - d -1 + 0 rd+e -2iΘ 1+|r| 2 d + , for λ < λ 0 .
We deform our contour as in figure 2.3.

Guided by the above factorizations, we define (2.2)

Ψ 1 = Ψ d -rd -1 e 2iΘ 0 d -1 , λ ∈ D 1 , Ψ 1 = Ψ d 0 0 d -1 , λ ∈ D 2 , Ψ 1 = Ψ d 0 -rd 1+|r| 2 e -2iΘ d -1 , λ ∈ D 3 , Ψ 1 = Ψ d rd -1 e 2iΘ 1+|r| 2 0 d -1 , λ ∈ D 4 , Ψ 1 = Ψ d 0 0 d -1 , λ ∈ D 5 , Ψ 1 = Ψ d 0 rde -2iΘ d -1 , λ ∈ D 6 .
REMARK. For such a deformation we need to assume that b, b can be analytically extended, at least in a small strip containing the real line (note that the actual choice of the curves l j is not important as long as they are in the right quadrant). This would be indeed true under more restrictive data. However, such an assumption is not necessary. As shown in [DZ] (see also [DIZ]) b can be approximated by a rational function whose poles do not affect the analysis.

Figures 2.2 and 2.3

A straightforward calculation shows that there is no jump across the real line. We have

(2.3) Ψ 1 (∞) = I.
The jump is

(2.4)

Ψ 1 + = Ψ 1 -u 1 x,t , where u 1 x,t = 1 -rd -2 e 2iΘ 0 1 , on l 1 , = 1 0 -rd 2 e -2iΘ 1+|r| 2 1 , on l 2 , = 1 rd -2 e 2iΘ 1+|r| 2 0 1 , on l 3 , = 1 0 rd 2 e -2iΘ 1 on l 4 .
3. The important observation is that this is a Riemann-Hilbert factorization problem without singularities at all. Indeed, the jump matrices have no poles as a has no zeros on l 1 ∪ l 2 ∪ l 3 ∪ l 4 . Also, Ψ 1 has no poles even at the points where a(λ) = 0. This follows easily from the scattering relations (1.7), the definition of Ψ (1.11), and proposition 2.1 which gives the behavior of d ± near the zeros of a.

In other words, we end up with exactly the same problem as the one corresponding to initial data that produce no real spectral singularities at all. Hence, the analysis of Deift, Its and Zhou goes through completely unaltered. Note also that the solution of (1.1)-(1.2) is still recovered in the same way (see (1.14)) since the modifications above have no effect on Ψ up to order 1 λ . We will not provide the analysis of Deift, Its and Zhou in detail. We refer the reader to [DIZ] instead. We will only recall that as the jumps (2.4) are exponentially small away from the stationary phase point λ 0 the problem is reduced to one on a small cross near λ 0 . The new problem can be solved explicitly (after some rescaling) in terms of parabolic cylinder functions. For the reader's convenience we provide the leading order asymptotics for q.

THEOREM 2.1. Let M > 1, K > 0 be fixed and assume that for any real zero of a, say λ ′ , we have λ -λ ′ ≤ K. We have

(2.5) q(x, t) = t -1/2 α(λ 0 )e i|x| 2 4t -iν(λ0)log(8t) + E(x, t),
where, as t → ∞,

(2.6) E(x, t) = O(t -1 logt), for |λ 0 | ≤ M,
and for any j,

E(x, t) = O(|x| -j + c j (z 0 )x -1 log|x|), for |λ 0 | ≥ M -1 ,
where

ν(λ) = 1 2π log(1 + |r(λ)| 2 ) > 0, |α(λ 0 )| 2 = ν(λ 0 ) 2 , argα(λ 0 ) = argΓ(iν(λ 0 )) -argr(λ 0 ) + π 4 + 1 π λ0 -∞ log(λ 0 -λ)d(log(1 + |r(λ)| 2 ).

NEAR A SINGULARITY

In this section we consider the effect of a real spectral singularity which is close enough to the stationary phase point λ 0 . For simplicity, we will assume that there are no non-real singularities and that there is only one real simple singularity, i.e. a has a simple zero, say at zero (but see section 4 about these assumptions). We write a(λ) = λ ã(λ), with ã(λ) ̸ = 0.

In this case, the analysis of [DIZ] breaks down, so the method of section 2 is no more useful. The behavior of d (the solution of problem (2.1)) is more complicated near λ 0 ; it is no more bounded there, and the relevant resolvent operators are also unbounded, so the standard method of [DIZ] cannot be applied directly. We will instead study this case by deforming the original problem in a different way.

1. Let

(3.1) τ = x 2 16t = tλ 2 0 .
We consider the region defined by (3.2)

λ 0 → 0, τ → ∞, as t → ∞.
Our first step will be to rescale appropriately so that the distance between the spectral singularity and the stationary phase point is O(1). We next introduce a contour deformation (different from section 2) which is still guided by the signature of the phase Θ. It now turns out that, in the region we are interested in, the factorization problem takes a very special shape. After a final conjugation involving an appropriate multi-valued function we end up with a problem on a vertical band, that can be solved in terms of the genus-0 algebro-geometric solution of equation (1.1).

REMARK. A comprehensive reference for scalar problems with singular jumps (like (2.1)) is the book by Gakhov ([G]).

2. Let Ψ (1) (λ) = Ψ(λ 0 λ). Condition (1.13) becomes (3.3) Ψ

(1)

+ = Ψ (1) -e iτ (2λ 2 -4λ)σ3 1 r(λ 0 λ) r(λ 0 λ) 1 + |r(λ 0 λ)| 2 e -iτ (2λ 2 -4λ)σ3 .
The rescaled phase is

(3.4) Φ = τ (λ 2 -2λ).
The singularity of the problem is now at λ = 0 while the stationary phase point is at λ = 1.

3. Let d be the solution of the scalar problem (2.1). We introduce a new contour Σ as shown in figure 3.1. We denote the vertical band joining points 1 + iA and 1 -iA by B. A is a real positive parameter to be specified later.

Ψ (2) = Ψ (1) D -RD -1 e 2iΦ 0 D -1 , λ ∈ E 1 , Ψ (2) = Ψ (1) D 0 0 D -1 , λ ∈ E 2 , Ψ (2) = Ψ (1) D 0 -RD 1+|R| 2 e -2iΦ D -1 , λ ∈ E 3 , Ψ (2) = Ψ (1) D RD -1 e 2iΦ 1+|R| 2 0 D -1 , λ ∈ E 4 , Ψ (2) = Ψ (1) D 0 0 D -1 , λ ∈ E 5 , Ψ (2) = Ψ (1) D 0 RDe -2iΦ D -1 , λ ∈ E 6 .
Here R(λ) = r(λ 0 λ) and D(λ) = d(λ 0 λ).

A straightforward calculation shows that there is no jump across the real line. We also have (3.6)

Ψ (2) (∞) = I.
The jump conditions for Ψ (2) are (3.7)

Ψ (2) + = Ψ (2) -u (2)
x,τ , where

u (2) x,τ = 1 -RD -2 e 2iΦ 0 1 , on l ′ 1 , = 1 0 -RD 2 e -2iΦ 1+|R| 2 1 , on l ′ 2 , = 1 RD -2 e 2iΦ 1+|R| 2 0 1 , on l ′ 3 , = 1 0 RD 2 e -2iΦ 1 , on l ′ 4 , = 1 -RD -2 e 2iΦ RD 2 e -2iΦ 1+|R| 2 1 1+|R| 2 , on the top half of B, = 1 1+|R| 2 -RD -2 e 2iΦ 1+|R| 2
RD 2 e -2iΦ 1 , on the bottom half of B.

Once more this is a Riemann-Hilbert factorization problem without singularities at all. The proof of this is the same as in section 2. 4. We observe that, as in section 2, because of the structure sign of Φ the jumps across Σ \ B are exponentially close to I as τ → +∞. We thus end up with a Riemann-Hilbert factorization problem across B.

THEOREM 3.1. Let Ψ (3) be analytic in C \ B , such that (3.8)

Ψ (3) + = Ψ (3) -u (3)
x,τ on , where

u (3) x,τ = 1 -RD -2 e 2iΦ RD 2 e -2iΦ 1+|R| 2 1 1+|R| 2 , on the top half of B, = 1 1+|R| 2 -RD -2 e 2iΦ 1+|R| 2
RD 2 e -2iΦ 1 , on the bottom half of B.

and

(3.9)

Ψ (3) (∞) = I.
Then Ψ (2) -Ψ (3) = O(τ -l ), for any positive l, as τ → ∞, uniformly in x, in compact subsets of the λ-Riemann-sphere. PROOF: The proof is omitted (see [DZ]). The important observation here is that RD -2 and RD 2 1+|R| 2 are actually under control on the top half of B while -RD -2 1+|R| 2 and RD 2 are under control on the bottom half. For example (again see [G], p.448) D behaves like λ -1/2 0 (λ -1) -1/2 and RD -2 is bounded. Note here that it is crucial to chose the segment B at right angles with the real line; the behavior of D depends essentially on the direction in which we approach λ = 1. 5. We introduce the multi-valued function

(3.10) Ω = 2(λ -1)((λ -1) 2 + A 2 ) 1/2 -A 2 -2.
We consider this as a function on C, chosing the branch consistently with the condition

(3.11) Ω = 2λ 2 -4λ + O( 1 λ 2 ), as λ → ∞.
Naturally, Ω has a jump across B. Also, (3.12)

Ω + + Ω -= -2(A 2 + 2), i(Ω + -Ω -) < 0, on the top half of B, i(Ω + -Ω -) > 0,
-u (4)

x,τ , where u (4)

x,τ = e iτ (Ω+-Ω-) -RD -2 e iτ (Ω++Ω-)

RD 2 e -iτ (Ω + +Ω -) 1+|R| 2

1

1+|R| 2 e -iτ (Ω+-Ω-) , on the top half of B,

= e iτ (Ω + -Ω -) 1+|R| 2 -RD -2 e iτ (Ω + +Ω -) 1+|R| 2
RD 2 e -iτ (Ω++Ω-) e -iτ (Ω+-Ω-) , on the bottom half of B,

Ψ (4) (∞) = I.
REMARK. The choice of Ω is inspired by the theory of algebro-geometric solutions of the NLS equation (cf. [BBEIM]). We are seeking a generalized differential τdΩ on a Riemann surface, whose integral behaves like the phase 2Φ as λ → ∞. The actual Riemann surface (of genus 0 in our case ) is dictated by the Riemann-Hilbert contour B in (3.8).

REMARK. The top diagonal term in the first matrix of (3.14) is small. To make the second diagonal term small we need to specify A. This will be done below. Similarly, the top diagonal term in the second matrix will be small when A is appropriately specified. 6. As it stands, (3.14) does not look like an improvement over the original Riemann-Hilbert problem. However, we shall now show that near the 'shock' region, it can be much simplified. In this subsection, we consider the 'shock front', i.e. the region II of theorem 1.1.

We choose A such that |λ 0 | = e -τ A 2 , i.e.

(3.15)

A = ( -log |λ 0 | τ ) 1/2 .
A and τ depend on x and t and should be thought of as a 'slow' and a 'fast' varaible, respectively.

Because of (3.15), the diagonal terms of u (4)

x,τ tend rapidly to 0, as τ → ∞, λ 0 → 0. As in subsection 4, we end up with (3.16)

Ψ (5) + = Ψ (5) -u (5)
x,τ , where

u (5) x,τ = 0 C(λ 0 )λ 0 e -iτ (2A 2 +4) -1 C(λ0)λ0 e iτ (2A 2 +4) 0 , λ ∈ B, Ψ (5) (∞) = I,
where (3.17)

C(λ 0 ) ∼ - b(0) exp(iarg(a ′ (0))) (λ 0 ) 2iν exp( 1 2πi 0 -∞ log(-s)dlog(|ã(s)| 2 ) ), as λ 0 → 0.
Note that there is no discontinuity at λ = 1. Here one uses the fact that when a(λ) = 0, |b(λ)| = 1 (see (1.8)), hence b(0) = 1 b(0) . Problem (3.16) can be solved explicitly. It can be interpreted as a form of the Riemann-Hilbert problem for the genus-0 algebro-geometric solution of (1.1) (see e.g. [MA], [LM], [BBEIM] ch.4). We analyze and solve (3.16) in the appendix.

Keeping track of the different transformations of Ψ and recalling (1.14), we have: THEOREM 3.2. The effect of a real spectral singularity at λ ′ is only felt in the region λ ′ -λ 0 → 0. In the case, say, λ ′ = 0 we have, as λ 0 → 0 and τ → ∞,

(3.18) q(x, t) ∼ (-log(|λ 0 |)) 1/2 t 1/2 • exp(-4iτ - i π log(|λ 0 |)log(|a ′ (0)λ 0 |) - i 2π 0 -∞ log(-s)dlog|ã(s)| 2 ),
where λ 0 = -x 4t , a, b are the scattering coefficients defined in (1.7) and ã(s) = a(s) s . In particular, in the region -x 4t ∼ ( logt t ) 1/2 the amplitude of the solution decays like O(( log t t ) 1/2 ).

7. The region τ → ∞, λ 0 → 0 corresponds to the 'front' of the region in which the effect of the real singularity is felt. We conclude this section by considering the region where τ is bounded.

In this region (especially as τ → 0) no simple rescaling works with the same geometry. One needs a new kind of Riemann-Hilbert deformation.

We begin with the problem (3.7) which is still exactly equivalent to the original Riemann-Hilbert problem (1.12). But we do not aim to "erase" the half-lines l i this time. Instead we see that the problem (3.7) is asymptotically equivalent to the Riemann-Hilbert problem for the Painlevé 4 equation ( [FMA], [FZ])

d 2 u dx 2 = 1 2u ( du dx ) 2 + 3 2 u 3 + 4xu 2 + 2x 2 u -2u,
by means of the rescaling λ → λ(4it) 1/2 , x → x(4it) -1/2 . Choosing A ∼ τ and rotating the Painlevé 4 problem appropriately, we see that the two Riemann-Hilbert problems are identified outside the circle of radius A. Inside the circle there is no identification, but we can show, using general symmetry facts and a vanishing theorem of Zhou ([Z]), that there is a matching transformation taking one Riemann-Hilbert problem to another. We thus have THEOREM 3.3. When τ < M, as t → ∞, the asymptotics for the solution of (1.1),(1.2) is (3.19) q(x, t) ∼ 1 t 1/2 u(xt -1/2 ), where u can be expressed in terms of a solution of Painlevé 4 such that 1 t 1/2 u(xt -1/2 ) is actually a self-similar exact solution of (1.1) (see e.g. [BP], [C], [BCH]). The actual solution is defined in terms of 4 constants ( [FMA] MATCHING. It can be shown that the formulae of region I match the formulae for region II by extending the [DIZ] analysis slightly into the region where τ = O(logt). Using known results on Painlevé 4 asymptotics by Kitaev [Ki], one can also show that the formulae of region II match the formulae for region III. Similarly, the formulae of region IV match the formulae for region II. and the the formulae of region V match the formulae for region IV.

Figure

  Figure 3.1

  on the bottom half of B.Defining (3.13)Ψ (4) = Ψ (3) e i(2Φ-τ Ω)σ3 , with σ 3 = diag(1, -1) (a Pauli matrix), we end up with the following Riemann-

  ) a, b, c, d which can be explicitly expressed in terms of the scattering data. More precisely s)dlog(|ã(s)| 2 )), and b = -ā, c = -a |ã(0)| 2 , d = -c.

SPYRIDON KAMVISSIS UNIVERSITE PARIS-XIII, FRANCE AND ECOLE NORMALE SUPERIEURE, CACHAN, FRANCE

HIGHER ORDER ZEROS AND FINITELY MANY SINGULARITIES

It should be clear by the discussion of sections 2 and 3 that there is nothing special about a singularity at zero. In the general case of finitely many singularities the following is true: for each real singularity λ i , there is a region where λ i -λ 0 → 0, as t → ∞, in which the solution decays with leading asymptotics similar to (3.18) and (3.19). Non-real singularities correspond to solitons as usual (see e.g [FT], [K] for the infinite case).

On the other hand, it is clear from section 3 that the order of the zero of a is not important; the order of the solution remains the same but there is a minor change in the phase. We leave the details to the reader.

As mentioned in section 1, a study of the interesting generalization of our result in the case of infinitely many real singularities is under way (for examples of such initial data see [Z]).

APPENDIX. THE RIEMANN-HILBERT PROBLEM FOR THE GENUS-0 SO-LUTION

In this appendix we solve the Riemann-Hilbert problem (3.16). We do this by diagonalizing the jump matrix and thus reducing the problem to a scalar one which can then be solved explicitly.

Let G = Cexp(-iτ (2A 2 + 4)) and

The eigenvalues of S are i and -i; we have

Then Λ solves the scalar problem (A.4)

Let the matrix µ be defined by

Thus µ is the solution of (3.16). Furthermore, near infinity,

In particular lim λ→∞ (2λµ 12 ) = -GA. The asymptotics of q is now immediately recovered through (1.14). REMARK: One can interpret problem (3.16) as the Riemann-Hilbert problem for the genus-0 solution of the NLS equation. Although the use of the term 'algebrogeometric solution' may sound pretentious in the very simple special case of genus 0, it is worth pointing out the fact that what we encounter here is an instance of a very general phenomenon, where the long-time behavior of the solution of a soliton equation in a particular region is related to a different type of solution, which is indeed connected with Riemann surfaces, and the associated theory of theta functions connected with the Abel map. For a discussion of that theory in the context of the nonlinear Schroedinger equation (focusing and defocusing) see [MA], [LM] and [BBEIM] (chapter 4). BIBLIOGRAPHY


Amélie Cordier
email: amelie.cordier@liris.cnrs.fr

Béatrice Fuchs
email: beatrice.fuchs@liris.cnrs.fr

Lana Léonardo

De Carvalho

Jean Lieber
email: jean.lieber@loria.fr

Alain Mille
email: alain.mille@liris.cnrs.fr

Opportunistic Acquisition of Adaptation Knowledge and Cases -The IakA approach

A case-based reasoning system relies on different knowledge containers, including cases and adaptation knowledge. The knowledge acquisition that aims at enriching these containers for the purpose of improving the accuracy of the CBR inference may take place during design, maintenance, and also on-line, during the use of the system. This paper describes IakA, an approach to on-line acquisition of cases and adaptation knowledge based on interactions with an oracle (a kind of "ideal expert"). IakA exploits failures of the CBR inference: when such a failure occurs, the system interacts with the oracle to repair the knowledge base. IakA-NF is a prototype for testing IakA in the domain of numerical functions with an automatic oracle. Two experiments show how IakA opportunistic knowledge acquisition improves the accuracy of the CBR system inferences. The paper also discusses the possible links between IakA and other knowledge acquisition approaches.

Introduction

Case-based reasoning exploits knowledge, such as domain knowledge and adaptation knowledge, to perform inferences on cases. The more complete and accurate the knowledge is, the better the inferences are. Hence, building efficient knowledge bases is of particular importance. The building of the knowledge base for a CBR system is often done beforehand, during the design phase. However, in order to make systems capable of evolving, the knowledge base has to evolve as well, thus additional knowledge acquisition has to be possible during the system use. In systems offering such a possibility, the acquired knowledge is reused in further reasoning sessions to improve the solutions produced.

Several ways of performing knowledge acquisition have been explored in CBR related research. Knowledge engineers and domain experts can collaborate to model knowledge of the domain. This manual approach is efficient because it allows the acquisition of relevant knowledge coming from the expert but it is rather constrained by the availability of the expert and of the knowledge engineer. Other approaches rely on the knowledge already available in the system (often in the cases) to infer new knowledge, like adaptation rules. These approaches are efficient in the sense that they automate the acquisition process but they produce a large amount of knowledge that has to be validated by an expert. Moreover, this validation phase is performed off-line, out of a specific context, thus it may be felt by an expert as an irksome task. Hybrid approaches, such as IakA, combine the reasoning capabilities of the system with interactions with the expert to acquire missing knowledge in context.

Usually, knowledge acquisition approaches assume that the knowledge of the system is organized in separate knowledge containers and that the reasoning process is split into several distinct steps. These assumptions are helpful better to understand CBR, but they do not reflect the reality. Actually, knowledge containers are closely interconnected (not to say identical) and the steps of the CBR process contribute to the achievement of the same objective: problem solving. The adaptation-guided retrieval principle [START_REF] Smyth | Retrieving Adaptable Cases: The Role of Adaptation Knowledge in Case Retrieval[END_REF] is a good illustration of this point: adaptation knowledge is used to support retrieval, and retrieval and adaptation steps contribute to the problem solving. This paper advocates a unified view of CBR steps and knowledge containers. In IakA, the CBR process is considered as a whole and the knowledge acquisition process focuses on the knowledge of the system: cases and adaptation knowledge are acquired at the same time. This paper presents IakA, an interactive and opportunistic approach for knowledge acquisition in CBR. IakA is interactive in so far as it exploits interactions between the expert and the system during CBR sessions. Its opportunistic aspect is due to the fact that reasoning failures trigger the acquisition process: the system seizes this opportunity to identify missing knowledge and to acquire it. One of the main advantages of this approach is that it focuses on knowledge known to be needed, which constitutes a strong guidance for the knowledge acquisition process and alleviates the effort required by the expert. In IakA, cases are adapted using adaptation knowledge. When a failure occurs, the applicability of the adaptation knowledge for this case has to be questioned. The expert plays two important roles: identifying the failure and correcting the faulty adaptation knowledge. As the adaptation knowledge is corrected in the context of the case being solved, it stays linked with the case. The case and its related adaptation knowledge are then added to the knowledge base.

The remainder of this paper is organized as follows. Section 2 compares several approaches of knowledge acquisition in CBR. Then, section 3 describes IakA, a set of principles for interactive knowledge acquisition in CBR systems which perform approximate reasoning (i.e when the aim is to find an approximate solution for a problem). The modelling of the expert by an oracle is discussed. Formalizing the adaptation knowledge acquisition process is described and the classical assumption of CBR-similar problems have similar solutionsis questioned. Section 4 is dedicated to IakA-NF, a prototypical CBR application implementing the principles of IakA in the numerical functions domain and describes two experiments. Section 5 discusses the complementarity of the Ia-kA approach with other knowledge approaches introduced in section 2. Finally, section 6 concludes the paper and outlines some prospects for future work.

Knowledge acquisition in CBR

It has long been argued that CBR was a solution to the knowledge acquisition bottleneck in knowledge-based systems because it is easier to collect cases than other pieces of knowledge. However, CBR only partly overcomes this problem because it also requires substantial effort to acquire the knowledge involved in the reasoning process. As with other knowledge-based systems, the implementation of knowledge-intensive CBR systems has to cope with the knowledge acquisition problem, and this issue has motivated significant research.

Adaptation-guided retrieval [START_REF] Smyth | Retrieving Adaptable Cases: The Role of Adaptation Knowledge in Case Retrieval[END_REF] aims at retrieving a prior case that is the easiest to adapt, given the available adaptation knowledge. Thus the adaptation step is central and adaptation knowledge plays a major role in CBR. For this reason, several studies focus on adaptation knowledge acquisition to improve the global quality of the system [START_REF] Leake | Learning to integrate multiple knowledge sources for case-based reasoning[END_REF][START_REF] Cordier | Engineering and Learning of Adaptation Knowledge in Case-Based Reasoning[END_REF].

Knowledge acquisition takes place at different stages of the life cycle of a CBR system. Initial knowledge acquisition can be done with experts who manually model the domain knowledge, or with the assistance of automated learning methods. Such approaches are off-line in that they take place outside a CBR reasoning cycle. Among off-line methods, machine-learning techniques have been used for instance in [START_REF] Hanney | Learning Adaptation Rules from Cases[END_REF]. In these methods, the case base is exploited to learn adaptation rules. Adaptation rules are generated by examining the differences between problems related to the differences between solutions. In the same vein, Craw et al. experiment further with this method by applying learning algorithms, such as C4.5, in the tablet formulation domain [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF] . The CabamakA system uses a knowledge discovery process to acquire adaptation knowledge [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF]. Data mining algorithms are applied to detect regularities which are candidates to become adaptation rules. Adaptation rules are then validated by a domain expert. Offline methods have been successfully applied, nevertheless these methods do not make it possible to acquire knowledge that is not yet in the cases.

On-line methods take advantage of a reasoning cycle to learn from a problemsolving session. One of the first CBR systems, Chef, a case-based planner in the cooking domain, experimented learning from failures [START_REF] Hammond | Explaining and Repairing Plans That Fail[END_REF]. Chef learns by storing successfully adapted plans or repaired plans. When an adapted plan fails, Chef builds a causal explanation of the failure in order to anticipate a future similar problem. Hammond qualifies his approach as an incremental repair process after a test or an execution: for a given problem, a first error-prone solution is produced and further tested and repaired incrementally using a causal model. Chef differs in that it takes advantage of a failure to anticipate it in further reasoning cycles. Dial is a disaster response planning system that retrieves and adapts prior similar past plans [START_REF] Leake | Learning to Improve Case Adaptation by Introspective Reasoning and CBR[END_REF]. Adaptation is performed with help either of general adaptation rules, or of prior successful adaptation cases, or of the user.

Adaptation is a combination of transformations combined with memory search processes of knowledge required by the transformation. The adaptation effort is stored and reused for an adaptation-guided retrieval approach. FrakaS [1] is a system for enriching domain knowledge when failures due to the incompleteness of the knowledge base occur. When such a failure occurs, a knowledge acquisition process involving the domain expert is triggered. Interactions with the expert allow the system to add new knowledge to its knowledge base and to collect an explanation of the failure. This knowledge is stored and reused to avoid the failure reoccurring in further reasoning. FrakaS is an example of the opportunistic knowledge acquisition approach in which new knowledge is acquired from outside the system. Next section presents IakA, a complementary approach to FrakaS.

IakA: InterActive Knowledge Acquisition

IakA is an approach to interactive knowledge acquisition in CBR systems that produce approximate solutions. The main idea of the approach is to exploit reasoning failures and their repairs to acquire cases and adaptation knowledge. Indeed, the occurrence of a failure highlights the fact that knowledge is missing. When correcting a failure, the required knowledge is added to the knowledge base and is reused in the following reasoning sessions to improve the solutions. The acquisition process is made possible thanks to an oracle that is capable of correcting solutions and providing the necessary adaptation knowledge.

Definitions and hypotheses

In this work, the notions of problem and solution are assumed to be well defined. If pb is a problem (resp., sol is a solution), then pb (resp., sol) is an expression in a knowledge representation formalism representing a problem (resp., a solution). L pb denotes the problem space and L sol denotes the solution space. Moreover, a binary relation on L pb × L sol is assumed to exist with the semantics "has for solution". This relation is generally not completely known by the system, but some of its instances are: they are the pairs (srce, Sol(srce)) ∈ L pb × L sol , called source cases. The aim of the CBR process is to find a solution for the target problem denoted tgt. Sol(tgt) is a candidate solution of tgt, i.e. the solution produced by the CBR system.

In order to adapt the solution of a case, IakA relies on adaptation knowledge mainly composed of adaptation operators.

Definition 1 (Adaptation operator -AO r = (r, A r )). An adaptation operator AO r is a pair (r, A r ) where r is a binary relation between problems (r ⊆ L pb × L pb ). A r is an adaptation function: if (srce, Sol(srce), tgt) ∈ L pb × L sol × L pb and srce r tgt then A r (srce, Sol(srce), tgt) is a candidate solution of srce.

Adaptation operators are organized in adaptation methods. An adaptation method is linked to a source case.

Definition 2 (Adaptation method -AM(srce)).

The adaptation method AM(srce) associated with the case (srce, Sol(srce)) is a finite set of adaptation operators AO r = (r, A r ). An adaptation method may also contain strategic knowledge for managing the adaptation operators.

The notions of adaptation operators and adaptation methods can be likened respectively to adaptation specialists and adaptation strategies defined in [START_REF] Smyth | Adaptation-Guided Retrieval: Questioning the Similarity Assumption in Reasoning[END_REF]. The adaptation method is used to build a similarity path and an associated adaptation path.

Definition 3 (Similarity path -SP).

A similarity path from a problem srce to a problem tgt is a set of q triples (pb i-1 , r i , pb i ) with :

pb i : q + 1 problems; pb 0 = srce and pb q = tgt; pb i-1 r i pb i (for i ∈ {1, . . . , q}); r i is such that (r i , A ri ) is an available adaptation operator. P(srce, tgt) denotes the set of similarity paths that can be built from srce to tgt.

The adaptation path is built after the similarity path.

Definition 4 (Adaptation path -AP).

The adaptation path AP associated to a similarity path SP is a set of q triples ( Sol(pb i-1 ), A ri , Sol(pb i )) with :

-Sol(pb 0 ) = Sol(srce) and Sol(pb q ) = Sol(tgt); -Sol(pb i ) = A ri (pb i-1 , Sol(pb i-1 ), pb i ). Figure 1 shows an example of a similarity path and its adaptation path. In order to choose between several similarity paths relating the same srce and tgt, the notion of length of a similarity path is introduced. This notion relies on the notion of estimated adaptation error.

Definition 5 (Adaptation error -e r and its estimatione r ). Each adaptation operator AO r introduces a numerical error e r , function of the problems srce and tgt related by r: e r (srce, tgt) ∈ R + . This error is known by the oracle but the system only knows an estimated value e r (srce, tgt) of it. Moreover, e r is assumed to have the following property: e r (srce, tgt) = 0 if srce = tgt. Definition 6 (Length of a similarity path -ℓ(SP)).

ℓ(SP) = q i=1 e r (pb i-1 , pb i )
Finally, the distance from a problem to another one is defined as the length of the shortest similarity path. 1 Definition 7 (Distance between problems -dist(srce, tgt)). dist(srce, tgt) = min{ℓ(SP) | SP ∈ P(srce, tgt)} Given these definitions, the retrieval process consists in building a similarity path, and consequently an adaptation path, from srce to tgt that minimizes the length ℓ(SP) and the adaptation process consists in following the adaptation path.

Illustration of the definitions. This example is given in a fictive domain where problems consist of ordered pairs of shapes and solutions consist of single shapes. Shapes have two properties: number of edges and color. It must be remarked that there is no available rule allowing the computation of the solution knowing the problem. Figure 2 illustrates the concept of adaptation operator. The candidate solution for the target problem (on the right) is obtained by adaptation of the source case (on the left). The relation r between srce and tgt means: to go from srce to tgt, a edge has to be added to the first shape of the pair. Except this difference, all the relevant attributes of the shapes are identical. To r is associated the adaptation function A r which meaning is: If there is one more edge on the first shape of the target problem, then the source solution must be adapted by adding one edge to it. Hence, Sol(tgt) is obtained by application of A r on Sol(srce).

Mechanisms of the IakA approach

The key idea of IakA is to exploit failures to acquire cases and adaptation knowledge. In systems that produce approximate solutions, a failure occurs when the distance between the solution of the system and the "ideal solution" is too large. IakA relies on the availability of an oracle which is able to say if a solution is satisfactory or not, to correct a non-satisfactory solution and to give adaptation 1 Technically, an inf should be used instead of a min: it is possible to find a series of similarity paths (SPn)n such that ℓ(SPn) > 0 and lim n→∞ ℓ(SPn) = 0. To avoid this theoretical problem, it is assumed that the number q of steps in a similarity path is bounded by a constant (e.g., q ≤ 10 100 ). operators for a case. Hence, the oracle is able to compute a distance between solutions and to compare it to a tolerance threshold denoted by ε (ε > 0): if the distance is larger than ε, the solution is not satisfactory.

In CBR, the occurrence of a failure means that a piece of knowledge that was used during adaptation has to be corrected or made precise. In the framework of IakA, adaptation methods, adaptation operators and adaptation errors may be questioned.

A main advantage of the IakA approach is that the different pieces of knowledge (in particular, the adaptation operators) are separated and tested independently thus enabling the faulty knowledge to be identified more easily. Indeed, when a solution is not satisfactory, the adaptation operators involved are tested by the oracle one after the other. If the oracle identifies a faulty adaptation operator, it corrects it. The new piece of knowledge is added to the knowledge base of the system and a new CBR cycle is performed in order to find a better solution for the current problem. Adaptation operators are corrected and a new CBR cycle is performed until a satisfactory solution is found.

Justification of the IakA approach. The CBR inference is based on the following principle (see, e.g., [START_REF] Dubois | Fuzzy Modelling of Case-Based Reasoning and Decision[END_REF]): Similar problems have similar solutions.

(CBR principle)

The similarity between problems is the knowledge of the retrieval step, often in the form of a similarity measure or a distance between problems. The similarity between solutions is linked with the adaptation: the higher the error caused by adaptation is, the less the solutions are similar. This principle can be replaced by its contraposition:

Dissimilar solutions solve dissimilar problems.

Therefore, a failure of the CBR inference indicates:

(a) Either that srce and tgt are not (enough) similar; (b) Or a failure in the CBR principle.

The failure (a) can also be split into two sub-situations:

(a1) There is no source case similar to the target problem; (a2) There is at least a source case (srce ′ , Sol(srce ′ )) = (srce, Sol(srce)) that is similar to tgt but it has not been retrieved.

Each of the failures of type (a1), (a2), and (b) leads to a knowledge acquisition from the oracle. When a failure of type (a1) occurs, the oracle may provide a new source case (with its associated adaptation method), that is similar to the target problem (for instance a case (tgt, Sol(tgt)) and an adaptation method AM(tgt)).

When a failure of type (a2) occurs, this questions the similarity between problems that constitute the retrieval knowledge: (srce, Sol(srce)) is closer to tgt than (srce ′ , Sol(srce ′ )) and it should be the contrary. With a similarity based on the estimated adaptation errors, the interactions with the oracle should lead to a modification of these estimated errors.

When a failure of type (b) occurs, the similar problems srce and tgt have no similar solution. In other words, in a neighborhood of srce, the solution varies in an irregular manner. This situation can be interpreted with the notion of (dis)continuity of numerical functions f : R n → R. Indeed, if L pb = R n , L sol = R, and Sol(pb) solves pb if f (pb) = Sol(pb), then the continuity of f is defined intuitively with the CBR principle: if x 1 is close to x 2 then f (x 1 ) is close to f (x 2 ). A type (b) failure means that there is a discontinuity close to srce. The interactions with the oracle may be useful to better locate the discontinuity points. It may occur that these discontinuity points involve a partition of the problem space in several points. For example, if L pb = R and 4 is a discontinuity point highlighted by the oracle, then L pb is partitioned in {]-∞, 4[, {4}, ]4, +∞[}. This implies that two problems of two different parts of this partition should never be considered as similar. With the previous example, 3.99 is dissimilar to 4.01. Therefore, the knowledge of this discontinuity point can be used as pieces of retrieval knowledge.

This justification of the IakA approach based on the CBR principle and the proximity of this principle to the notion of continuity suggest that it should be tested in domains where continuity is well-defined. The numerical functions constitute such domains. IakA-NF, described in the following section, is a prototype implementing IakA with numerical functions.

4 IakA-NF: a prototype implementing the IakA approach 4.1 The IakA-NF system IakA-NF is a prototypical CBR engine implementing the principles of IakA in the application domain of the numerical functions (f : R n → R). The aim of this prototype is to solve problems by approximation, i.e., given n variables (x 1 , ..., x n ), the goal is to find an approximate value of f (x 1 , ..., x n ) by CBR.

In IakA-NF, a problem is a n-tuple of real numbers and a solution is an approximation of the value of the function f for these values. f CB denotes the approximation of the function f obtained from the CBR system using the case base CB (and the adaptation methods). To each case is associated an adaptation method containing n adaptation operators. In the numerical functions domain, an intuitive way to define adaptation operators is to use the notion of partial derivatives. Indeed, the influence of the variation of a problem variable on the solution can be expressed by the partial derivative of this variable.

The retrieval is performed according to the distance defined in definition 7. The adaptation consists in applying the different adaptation operators of the retrieved adaptation method. The solution is obtained by adding to the solution of srce the variations involved by the different variables of the problem (calculated using the partial derivatives).

The knowledge acquisition process is performed according to the principle introduced before: a candidate solution produced by the system is always tested by the oracle. If the solution is not satisfactory, the involved adaptation operators are tested and corrected if needed, until a satisfactory solution is found. Then, the newly solved case (tgt, Sol(tgt)) is added to the case base together with its adaptation method, given by the oracle.

The oracle is simulated by the function f and by a tolerance threshold ε > 0 (the maximal tolerated error). The oracle is capable of computing the distance between two solutions, to give the correct solution for a case and to give the adaptation methods.

The following example illustrates the mechanism of IakA-NF with a function f a : R → R. The first part of the example describes the notations used and the knowledge available in the system:

Example : Oracle knowledge, source case and target problem are defined as follows:

fa : R → R fa(x) =  1 + arctan(3x) if x ≥ 0 -1 + arctan(3x) if x < 0 srce = x s tgt = x t Sol(srce) = y s g Sol(tgt) = e y t
Moreover, there is only one adaptation operator AOr in the adaptation method AM(srce). It is defined by x s r x t holds for any x s and x t , and e y t = Ar(x s , y s , x t ) = y s + ∂y s ∂x (x tx s ).

Experiments

Several experiments have been conducted with IakA-NF. Two of them are presented below.

Influence of the tolerance threshold of the oracle. The aim of this experiment is to analyze the impact of ε (the tolerance threshold of the oracle) on the quality of the results produced by the system. The hypothesis is that the smaller ε is, the better the results are (for a constant number of solved problems).

In order to conduct this experiment, an initial knowledge base is built; it consists 20 cases randomly generated (and solved by the oracle O fm ) and their associated adaptation methods (also given by the oracle O fm ).

O fm = (f m , ε) f m : R → R f m (x) = x + 10 sin(5x) + 7 cos(4x)
Moreover, 70 target problems are randomly generated. The same initial knowledge base and set of problems are used for all the tests in this experiment.

Two systems are run in parallel: the control system and the IakA system. The goal is to solve the 70 problems of the set of problems. In both systems, problems are solved according to the IakA approach (test and repair of the knowledge of the system). The difference is that solved cases are not added to the case base in the control system whereas they are in the IakA system.

The purpose of the experiment is to make ε vary, thus the experimental protocol described above is made 10 times with 10 different values for ε. For each experiment, we compare, for each case, the difference between the error made by the control system and by the IakA system.

Two statistical tests are performed on the gathered data: the Z-test [START_REF] Kendall | The advanced theory of statistics: Tome 1 distribution theory[END_REF] and the Wilcoxon test [START_REF] Wilcoxon | Individual comparisons by ranking methods[END_REF] to measure the efficiency of the knowledge acquisition process. The value ρ, determined in each test, is the probability of obtaining the same results in a system performing knowledge acquisition as in a system without knowledge acquisition. For a IakA system, the smaller ρ is, the lower the chances of obtaining such results with the control system are. Therefore, the smaller ρ is, the better the IakA system is. The Z-test is a parametric test for two paired samples. As there is no guarantee that the initial distribution of cases and problems follows a normal law, the Wilcoxon test, a non-parametric test for two paired samples, is used to confirm the results of the first test. Figure 4 shows a graphical interpretation of the results of the Wilcoxon test (the results of the Z-test are similar). On the charts, we observe that the smaller ε is, the smaller ρ is, i.e., the more effective the system is. A significant difference (ρ < 0.01 i.e. 1%) in terms of reduction of the size of the error is achieved when ε = 10 (which is a high value in this domain). The conclusion is that the higher the tolerance threshold of the oracle is, the bigger the probability for the system to make a mistake is, which confirms the hypothesis of this experiment. Similar tests have been performed with problems of two and three variables, giving similar results.

Impact of a discontinuity on the CBR process. The aim of this experiment is to analyze the behavior of a CBR system solving problems by approximation when there is a discontinuity in the domain. This experiment is motivated by the observation (b) discussed in section 3. The hypothesis is that more interactions with the oracle are needed when a problem is in the neighborhood of a discontinuity.

As for the previous experiment, an initial knowledge base of 20 cases randomly generated is built by the oracle O fa , and 70 target problems are also randomly generated. The oracle is defined as O fa = (f a , ε) with f a as defined in section 4.1. The experiment consists in solving the 70 target problems with IakA-NF. The results are processed to count the number of problem-solving episodes that have required a correction from the oracle. As an example, figure 5 shows a graphical interpretation of the result of an experiment conducted with a tolerance threshold ε = 0.2. This experiment has been conducted several times with different values for ε (but still with the same initial knowledge base and the same series of problems). Table 1 gives the results of these experiments. Empirical results show a The interval "around discontinuity points" is determined manually before the experiment Table 1. Number of corrected cases and number of corrected cases around the discontinuity in function of the tolerance of the oracle.

that the number of cases learned around a discontinuity grows while the oracle tolerance threshold decreases. This tends to confirm the initial hypothesis of this experiment. The same experiment was also conducted with another function f ht involving two problems variables.

O f ht = (f ht , ε) f ht : R 2 → R f ht (x, y) = -3 -g(x, y) if x 2 + y 2 ≤ 4 -g(x, y) if x 2 + y 2 > 4 g(x, y) = sin x 2 + y 2 + x 7
For two-dimensional problems, the results and the conclusions are similar. Figure 6 illustrates the conclusion. In this example, the oracle is O f ht , ε = 1.0 and 20.000 problems are solved. Only 149 cases had to be corrected by the oracle, 113 of which during the first 1000 solved problems.

Discussion

IakA is different from off-line approaches in that the knowledge, coming from the external world, is acquired incrementally. Off-line approaches generate a large amount of knowledge at once, leading to a significant work for the domain expert to interpret the results. In IakA, the gradual acquisition alleviates the effort required by the oracle. IakA may be used as a complement of a first acquisition phase: it offers an easy way to acquire additional knowledge. Among on-line methods, Chef learns from failures but differs from IakA in that it exploits its own knowledge to explain failures and to avoid them in further reasoning. In Dial, an adaptation case base is used to support an incomplete adaptation rule base but it does not evolve over time. By contrast, IakA updates its existing adaptation methods whenever a failure occurs.

On-line learning in CBR is usually limited to the accumulation of cases and to their indexing. A failure due to system knowledge may reoccur several times if the involved knowledge is not corrected. In IakA, the role of the oracle is to correct such knowledge. The effort required from the oracle might seem quite important but it is limited compared to the one required in off-line methods. Moreover, this effort cannot be avoided when focusing on knowledge that usually resists other knowledge acquisition approaches.

Conclusion

This paper has described IakA, an approach for on-line acquisition of cases and adaptation knowledge based on interactions with an oracle (which can be considered as an "ideal expert"). IakA has been designed using the idea of a unified view of the knowledge involved in the CBR process. The failures of the CBR inference are used to repair the knowledge base (adaptation knowledge within cases). The decomposition of the adaptation process into several steps makes the identification of the knowledge involved in the failure easier. IakA-NF is a prototype for testing IakA in the domain of numerical functions with an automatic oracle. The tests show that IakA opportunistic knowledge acquisition improves the accuracy of the CBR system in the vicinity of the place where failures have occurred. They also show that this acquisition ceases to be efficient around discontinuity points, where the CBR principle is violated.

Although it has been tested, the IakA approach remains to be compared with a real-world application, using an expert instead of an oracle (where an expert can be seen as "a noisy oracle whose availability is usually quite low").

Three kinds of failure have been described in this paper. Failures of type (b) were the subject of experiments. However, additional work can be done to improve the efficiency of the knowledge acquisition. For instance, when several failures occur in the same part of the space, the system could point it out to the expert. The interaction, that takes place off-line, may lead to the explicit modelling of additional knowledge in this part of the space (e.g. "there is a discontinuity in 4"). This knowledge could then be added to the system, thus avoiding the consideration that 3.99 and 4.01 are similar in further reasoning. Failures of types (a1) and (a2) may also lead to knowledge acquisition. With regard to type (a1) failures, experiments are currently conducted to measure the impact of the addition of intermediate cases (by the oracle) when there is no similar source case. The study of failures of type (a2) is possible future work.

The IakA approach and its justification rely on the viewpoint of CBR as system producing approximate solutions. Another viewpoint is that of uncertain reasoning. A future work direction aims at generalizing the IakA approach and its justification so that it considers both viewpoints.

As discussed in section 5, IakA should inter-operate with other knowledge acquisition/extraction/learning approaches. Most of the time, these approaches are supposed to be applicable to different phases of CBR, with different goals and with different knowledge sources. However, IakA adopts a unified view of the CBR process and its knowledge. Therefore, more work must be done to connect the various approaches in a more general framework. For instance, a future work is to elaborate a strategy that focuses on the type of faulty knowledge (adaptation knowledge, strategic knowledge, domain knowledge, etc.) to trigger an appropriate acquisition method. Although this is a long-term future work, the authors' opinion is that this is an important issue in the field.

Fig. 1 .

 1 Fig. 1. A similarity path and the associated adaptation path.

Fig. 2 .

 2 Fig. 2. An example of adaptation operator.

Fig. 3 .

 3 Fig.3. Representation of the oracle knowledge fa and of the system knowledge fCB for an initial case base of 20 cases (circles represent cases).

Fig. 4 .

 4 Fig. 4. Evolution of the value of ρ in function of ε for the Wilcoxon test.

Fig. 5 .

 5 Fig. 5. Distribution of the corrected cases around a discontinuity (with ε = 0.2).The dotted line represents the function to approximate, the crosses are the solved cases that have required a correction from the oracle and the plain line represents the accumulation of the number of interactions with the oracle.

Fig. 6 .

 6 Fig. 6. Acquisition of cases around a discontinuity. The figure on the left represents the oracle knowledge. The figure on the right shows the cases learned by the system (after correction by the oracle): a high proportion of cases are acquired near discontinuity points. It must be remarked that there is a discontinuity around the top of the curve.


Anthony Bardou
email: anthony.bardou@ens-lyon.fr

Thomas Begin
email: thomas.begin@ens-lyon.fr

Anthony Busson
email: anthony.busson@ens-lyon.fr

Multi

Multi-Armed Bandit Algorithm for Spatial Reuse in WLANs : Minimizing Stations in Starvation

Keywords: reinforcement learning, starvations, spatial reuse, clear channel assessment

Introduction

Nowadays, access to WLANs is often regarded as a basic service. However, despite its importance, very few WLANs run at their maximum efficiency. Their current deployments often contain a dense number of access points (APs), which can have a major impact on the WLANs' performance because of the listen-before-talk property of 802.11. The recent amendment to the 802.11 standard (802.11ax or Wi-Fi 6) could be a game-changer as it enables WLANs to dynamically modify the transmission power of APs (a.k.a. TX_PWR) as well as their CCA (Clear Channel Assessment) threshold (a.k.a. OBSS/PD). In this work, we frame the proper tuning of these two parameters as a Multi-Armed Bandit problem, which allows us to derive an efficient and robust data-driven solution using Thompson sampling, an original sampling of WLAN configurations, and a tailor-made reward function assessing their quality.

Methods

Reward Function

In order to converge quickly to an efficient WLAN configuration in the configuration space C = ([-82, -62] × [1, 21]) N A (with N A the number of APs in the WLAN), our reinforcement learning agent must be able to assess the quality of a given configuration through a reward function. We propose a reward function R which is based on the stations' (STAs) effective and attainable throughputs (T i and T A i ), T + and T -the sets of STAs not in starvation and in starvation (defined by T i < αT A i for a fixed α ∈ [0, 1]) and the number of STAs in the WLAN N S . It is defined in Equation 1.

R (c) = |T -| j∈|T -| T - j αT A j + |T + | N S + j∈|T + | T + j T A j N S (N S + 1) (1)
This reward is bounded between 0 and 1 and mainly increases with the reduction of starvations in the WLAN. We suppose that R is sufficiently smooth over the discrete configuration space C, that is :

∃δ ∈ [0, 1], ∀c i , c j ∈ C, |R(c i ) -R(c j )| ≤ δ||c i -c j || 1 .
This property allows us to split our problem into two independent tasks, (i) look for promising configurations in C to fill a reservoir, done by a first agent, the sampler, and (ii) find the best configuration within the reservoir, done by a second agent, the optimizer.

Sampler and Optimizer

The sampler exploits the smoothness property of the reward to build a mixture of hyperspheres centered on the best configurations found so far. When triggered, the agent samples a configuration on the surface of these hyperspheres and updates its state, as shown in Figure 1.

Results

Our strategy was tested using the realistic network simulator ns-3 [START_REF]The Network Simulator ns-3[END_REF] and compared with other state-of-the-art solutions such as [START_REF] Wilhelmi | Potential and pitfalls of Multi-Armed Bandits for decentralized Spatial Reuse in WLANs[END_REF][START_REF] Afaqui | Evaluation of dynamic sensitivity control algorithm for IEEE 802.11ax[END_REF] in full buffer bidirectional (uplink and downlink) traffic on realistic network topologies based on the highly-dense WLAN deployed by Cisco in its offices in San Francisco [START_REF]High Density Wi-Fi Deployments[END_REF]. Our results show a significant, rapid and lasting improvement of all the performance metrics considered, by factors ranging from 38% to 140% when compared with the default configuration of 802.11 as shown in Figure 2. We can also observe significant improvement when compared to state-of-the-art solutions.

FIG. 1 -

 1 FIG.1-Plausible execution of our sampling algorithm for a WLAN with a single AP. The distribution density is shown in colors and the dashed line draws the frontier between authorized and unauthorized configurations according to 802.11ax.

FIG. 2 -

 2 FIG.2-Performance parameters on a realistic topology for each strategy.