Marius Bozga

Susanne Graf

Laurent Mounier

Iulian Ober

Jean-Luc Roux

Daniel Vincent

Timed Extensions for SDL ?

Keywords: SDL, time semantics, timed automata, urgencies

In this paper we propose some extensions necessary to enable the speci cation and description language SDL to become an appropriate formalism for the design of real-time and embedded systems. The extensions we envisage concern both roles of SDL: First, in order to make SDL a real-time speci cation language, allowing to correctly simulate and verify real-time speci cations, we propose a set of annotations to express in a exible way assumptions and assertions on timing issues such as execution durations, communication delays, or periodicity of external inputs. Second, in order to make SDL a real-time design language, several useful real-time programming concepts are missing. In particular we propose to extend the basic SDL timer mechanism by introducing new primitives such as cyclic timers, interruptive timers, and access to timer value. All these extensions relies on a clear and powerful time semantics for SDL, which extends the current one, and which is based on timed automata with urgencies.

Introduction

The ITU{T Speci cation and Description Language (SDL, 10]) is increasingly used in the development of real-time and embedded systems. For example many recent telecommunication protocols (such as Rmtp-II 18] or Pgm 17]) integrate such real-time features in their architecture, and these non-functional aspects are essential in the expected behaviour of the application. This kind of systems imposes particular constraints on the development language, and SDL is a suitable choice in many respects: it is formal, it is supported by powerful development environments integrating advanced facilities (like simulation, model checking, test generation, code generation, etc.), and thus it can cover several phases of the software development, ranging from analysis to implementation and on-target deployment. It appears however that several important needs for a real-time systems developer are not covered by SDL. These problems range from pure programming issues, like the lack of useful primitives commonly available in real-time operating systems, to speci cation issues, like the di culty to describe in a appropriate way the assumptions under which the system is supposed to be executed. Clearly, the needs are not the same for both uses of the language, and, in many cases, the programming side has been given priority in the supporting tools to the detriment of the speci cation side. Several proposals already exist to extend SDL with real-time features. We can mention for example the work carried out on performance evaluation [START_REF] Diefenbruch | Performance evaluation of SDL systems adjunct by queueing models[END_REF][START_REF] Mitschele-Thiel | Performance Engineering of SDL/MSC Systems[END_REF][START_REF] Roux | SDL Performance Analysis with ObjectGeode[END_REF][START_REF] Malek | PerfSDL: Interface to Protocol Performance Analysis by means of Simulation[END_REF], on schedulability analysis 4], or on real-time requirements 11]. In this paper we are more concerned with the use of SDL as a speci cation language for real-time systems and its application for formal validation. In particular, one of the important questions we address is what kind of real-time features should be modeled in SDL and at which level of abstraction. The simplest use of time which is frequent in communication protocols, is the use of timeouts (whose value is often meaningless) in order to avoid in nite waiting. The time semantics of SDL, together with the fact that timeouts are noti ed via a signal in the message queue of the process, corresponds exactly to this use: no guarantee can be given when the signal arrives and is dealt with, but it is after some nite time. Nevertheless, when SDL is used as a programming language, it is often done with much more restricted assumptions on the possible time behaviour in mind, and, if they are correct, the implemented system will behave as expected. As such assumptions are not (and cannot be) expressed explicitly, the speci cation cannot be validated: the veri cation using the standard SDL time progress may invalidate even apparently time independent safety properties. A typical workaround used for obtaining a convenient result at simulation time consists in using on one hand timers to force minimal waiting, and, on the other hand, a very restricted interpretation of time progress, allowing it only when the system is not active. This \synchrony hypothesis" is in general as unrealistic as the standard semantics. The right assumption would be that certain tasks will be executed timely, whereas for others this cannot be guaranteed and the correctness of the system must be veri ed even if they take longer than expected. The solution we propose to reconciliate these two extreme choices relies on a more exible time semantics for SDL, based on timed automata with urgencies 5]. In particular, urgencies give a very abstract means to express assumptions on the environment and on the underlying execution system, such as action durations, communication delays, or time constraints on external inputs. From the user point of view, all these \non functional" extensions are o ered in a uniform way by means of annotations on the SDL speci cation. The propositions presented in this paper are the results of the Interval IST project and preliminary work of its partners. The aim of Interval is to take into account real-time requirements during the whole development process of real-time systems and to de ne consistent extensions to the languages SDL, MSC and TTCN. The remainder of the paper is organized as follows: in section 2, we give an overview on the problems occurring when using SDL for real-time systems, concerning both programming and speci cation aspects, in section 3 we propose extensions allowing to improve SDL as a real-time speci cation language and in section 4 we propose necessary programming concepts. All new concepts are illustrated by examples illus-trating their use and proposed syntax. Finally, in section 5 we draw some conclusions and give some perspectives.

2 Real-time SDL: what is missing? SDL has the double aim of being on one hand a high-level speci cation formalism, meaning that it must abstract from certain implementation details, and on the other hand a programming formalism from which direct code generation is possible. These two roles of the language seem sometimes con icting, as the needs at the di erent levels are not the same in general. It is important that SDL can fully play this double role of being an implementation and a speci cation language, and all information needed for both uses of SDL must be expressible, but also in such a way that these two concerns are clearly separated. This feature is particularly crucial when dealing with real-time systems, in which non-functional elements need to be taken into account even in the early stages of the design. We summarize here the main di culties currently arising when trying to use SDL for the design and validation of real-time systems.

Real-time semantics

First of all, the semantics of SDL, as presented in Z.100, is very abstract in the sense that it allows to make no assumptions on time progress: actions take an indeterminate amount of time to be executed, and a process may stay an indeterminate amount of time in the current state before taking one of the next reable transitions. This notion of time that is external, unrelated to the SDL system, is realistic for code generation, in the sense that any actual implementation of the system conforms to this abstract semantics. However, for simulation and veri cation, this total absence of controllability of time is not satisfactory: timer extents do not have any signi cance besides de ning minimal bounds, any timer that gets in a queue may stay there for any amount of time, with the consequence that hardly any real-time property holds on models based on this abstract semantics. A simulator that would use the semantics of time as described in Z.100, would not be able to make any assumption on the way time progresses, and therefore many unrealistic executions will be present in the resulting graph. As a result, the simulator would not guarantee elementary properties like when a timer expires, it will be consumed by the concerned process in a reasonable amount of time (whatever the notion of reasonable is). Even worse, according to some previous version of Z.100, when two timers are set on the same transition (for example as two consecutive assignments), the timer with the lower delay is not always consumed rst. In practice, existing simulation and veri cation tools have foreseen means for limited control over time progress. However, the control over time they propose is in general quite limited and moreover these annotations are tool dependent whereas they are totally part of the speci cation in the sense that they describe assumptions on the system environment. The fact that designers and design languages neglect a clear description of relevant properties of the environment in which the system should be executed, is a frequent source of errors.

How to note non-functional aspects?

The development of a complex real-time protocol usually needs to consider several preliminary stages, during which some abstract or incomplete descriptions are produced. In order to properly validate (and document) these early designs, general assumptions on both the \environment" of the system and on its \non-functional" aspects have to be taken into account. For example, such assumptions concern:

{ the expected duration of some internal task (which might be either informal or fully speci ed), { the periodicity of some inputs triggered by the environment, { or even the expected behaviour of the communication channels used within the system (these channels may be reliable or not, assumptions may be made on communication times, etc.).

Of course, some of these assumptions can already be partly included in the specication, either directly in SDL (e.g., using timers for explicit waiting) or using some separate formalisms o ered by the veri cation tools (like the Goal language 2] proposed in ObjectGeode to specify external observers). However, none of these two solutions is satisfactory: the rst one leads to a speci cation in which external and non-functional assumptions do not appear as such, and this is obviously not desirable for code generation (these timers need not to be implemented), whereas the second one is restricted to a particular tool. Our objective is to provide a more suitable framework, based on standardized annotations on SDL speci cations and compatible with the real-time semantics we propose.

High level synchronisations and other real-time primitives

Clearly, SDL has several characteristics that are attractive for real-time system designers: asynchronous communication is a rst class language feature, a speci cation is organized in a logical hierarchy that can be mapped in many ways to di erent physical con gurations of software modules (and SDL code generators usually provide this feature), external code may be called from SDL, making it possible to use system libraries directly in SDL. Several synchronisation mechanisms that are commonly employed in real-time systems should be usable as concept at the SDL level. In particular, SDL timers are rather limited: the only available primitives are set and reset operations, the active function (which allows to determine if a given timer is running or not), and timeouts are always transmitted in the form of signals in the input bu er of the process.

Deployment information

Z.100 asserts that the agents composing a system are executed truly in parallel. In the context of the very weak time semantics of SDL (only minimal waiting time can be enforced, and any action or message transmission takes either zero or an arbitrary amount of time), this simplifying assumption is possible, because any mapping on a set of processors and any notion of atomicity will lead to the same functional behaviour, and any time behaviour is included in the semantics. However, the introduction of a more precise notion of time introduces also global constraints, so that di erent degrees of atomicity or di erent mappings on processors will lead to di erent time behaviours, and | if the functional behaviour depends on real-time constraints | even to di erent functional behaviours. An obvious example is the fact that, if a set of processes are executed interleaved, their execution times must be added, whereas if they are truly parallel the global execution time will be the maximum of the individual execution times. One must obviously be very careful by trying to make assertions on global execution times using no or very abstract assumptions on the architecture on which the system is executed. However, it is not always necessary to introduce much knowledge about the architecture:

{ First of all, there exist time dependent properties which are not architecture dependent: for example, often the safety of a protocol may depend on the relative values of a set of timers, the expiration of which are used as implicit signal between processes. This is a common use of timers which cannot be expressed in the present SDL time semantics and still does not need any architecture indication. { In a system where time is consumed either in communications or in requests to external systems (like a distant data base or anywhere else in the environment), the execution times will not depend on the mapping of processes on processors whenever the execution time of all activities consuming a negligible amount of time can be safely simpli ed to zero. Also in the case where time is consumed within the system, but within a single process per processor, analysis of execution time is still possible in the same way. { In the case where time is consumed in several parts of the system, it would be su cient to indicate which parts of the system are executed in parallel and which ones are not. The distinction between block agents, process agents and sub-agent gives some limited possibility to indicate such an architectural information.

Going one step further, scheduling policies also can in uence the properties of the system in critical hard real-time systems. Moreover, there exists important advances in the synthesis of schedulers 3], where scheduling policies are expressed mainly in terms of dynamic priorities.

Extending speci cation aspects

As we mentioned above, what is missing in SDL to improve real-time systems speci cation is both a exible time semantics together with more facilities to express some \non functional" parts of the system or its environment. Our proposal is to solve these two problems uniformly { from the user point of view { by o ering the possibility to annotate the speci cation in a standardized way. In particular, we propose to distinguish between two types of annotations: { assumptions, which express a priori knowledge or hypotheses about the environment or the underlying execution system (system architecture, scheduling policy, etc). The use of assumptions is twofold: rst, they might be necessary for the veri cation of properties which do not hold otherwise. Second, they might be used for code generation, both to guide some implementation choices or to add speci c code in order to check their correctness at run-time or during the test phase.

{ assertions, which express expected (local) properties on the system components.

Such properties have to be proved on the speci cation, during the veri cation phase, possibly taking into account some of the assumptions.

The annotations we propose concern respectively, control over time progress by means of urgencies, durations and periodicity of actions, and exible channel speci cations.

Urgencies

A very abstract { and still very powerful { manner for making realistic assumptions on the time environment of a system is by means of transitions urgencies 5]: a transition is \urgent" if it is enabled and will be taken or disabled before time progresses. Three types of urgency assumptions (eager, lazy and delayable) are enough to control the progress of time with respect to the progress of the system: { eager transitions are urgent as soon as they are enabled: they are assumed to be executed \as soon as possible"; in a simulation state time does not progress as long as there are enabled eager transitions.

{ lazy transitions are never urgent: enabled lazy transitions do not inhibit time progress in any simulation state.

{ delayable transitions are a combination of eager and lazy transitions: they become urgent when time progress disables them. They are supposed to be executed within some interval of time in which they are enabled. A delayable transition usually has an enabling condition depending on time, such as now x or now ? x y (where x and y are numerical values) and time may progress in all simulation state in which this transition is enabled as long as now x (or now ? x y). When the extreme point of the interval is reached the transition becomes urgent. Notice that the attribute \delayable" is not primitive: a delayable transition with a guard now < x (for instance) can always been replaced by two transitions, a lazy one with the same guard and an eager one with guard now = x.

In particular, in SDL speci cations in which explicit time guards (others than timeouts) are not used, explicit delayable transitions are not useful. However, whenever a task or a communication is assumed to take some time speci ed by an interval this is expressed by a delayable transition in the semantics model.

Expressed in terms of urgencies, the semantics of time in Z-100 considers all transitions as lazy: time progress is not constraint at all, whatever transitions are enabled. Nevertheless, most SDL tools implement an eager semantics: transitions are red as soon as they are enabled without letting time progress. It appears in practice that none of these two extreme interpretations of time progress in isolation allows to obtain satisfactory models of real-time systems. It is often appropriate to mix these two extreme views of time progress: { one would like to consider some of the inputs as lazy (which is the standard point of view). When such a transition is enabled, the system can choose to react immediately or to wait. In the case of an external input laziness denotes the absence of knowledge about the possible arrival time of the input; for internal inputs laziness can be used to interpret internal action durations or internal propagation delays as unconstraint or unknown.

{ On the other hand, one would like to consider some of the inputs as eager to express that the system cannot ignore them when they are enabled and must react immediately without waiting. This can be used to guarantee an immediate response to critical events such as timeout expirations or other prioritary inputs. Some care must be taken here since one can easily write system speci cations in which time is blocked \forever" because at least one eager transition is always enabled (this is called a Zeno behaviour). This is particularly problematic when all transitions are assumed eager.

Default choices, depending on the type of the system and on the type of transitions, can be envisaged in order to provide an user-friendly way of specifying how urgencies are associated with system transitions. Example 1. A generic situation is presented in Figure 1. The informal action open must be executed in the interval de ned by timers t early and t late, as soon as the external signal open is received. Thus, if the open signal arrives too early, it must be saved; if it does not arrive in time, the action is executed anyway at the expiration date of t late. In order to obtain a realistic time behaviour of such a system, timeout consumptions have to be considered as eager: the action open is assumed to be executed at time t late at latest. In order to specify all possible behaviours, the (external) open signal input must be considered as lazy. Considering it as eager prevents the timer t late to expire since this transition is always enabled in state wait (in absence of an environment process that sends only a limited amount of open signals). In the case where the open signal is sent from within the system, the consuming transition might be considered as eager (meaning that one can assume that it will be executed as soon as possible within its allowance interval) and one may want to verify if the signal arrives always in the given interval depending on the time constraints of the other parts of the system.

Timer semantics Timers are the most used primitive to observe the time progress. The semantics of timer expirations has been revisited in the last version of Z.100. The behaviour of a timer, can be sketched by the automaton given in Figure 2.

Basically, it switches between inactive and active states depending on the set and reset actions performed on it. When active, once the expiration time is reached, it will expire and the timeout signal becomes available to the corresponding process instance. Previous version of Z.100 considered this expire transition as lazy, which means that one cannot make any assumption on the maximal time elapsed since its last setting. In other words, nothing can prevent the automaton from remaining in the running state after the expiration time. The current semantics introduces a more reliable timer concept ensuring the availability of the timeout signals exactly at expiration time. This can be done simply by considering the implicit expiration transition as eager. Note that this cannot be captured by the urgency annotation described before since it relies on an implicit semantic choice which cannot be explicited at the speci cation level. Also, this is not too restrictive: it still allows the situation in which the timeout is really consumed at a later point of time as the consumption time depends on the urgency of the consuming transition. Example 2. A second generic process is illustrated in Figure 3. The informal actions action 1, action 2, action 3 must be executed precisely at moments, respectively T0-d1, T0-d2, T0-d3, where T0 is given as parameter to the process. Let us assume rst that the informal actions correspond to external commands which need just to be initiated by the process e.g, actioning some external devices. That means it is reasonable to assume that the process is essentially idle, wiating for the timer expiration, and reacts imediately. Unfortunately, even if the SDL description of the process seems intuitive and concise, based on the standard semantics of SDL, no assumption can be made about the time at which the actions will be executed. Considering the timeout transitions as lazy, the actions are executed not earlier than the required moment. The eagerness of the timeout consumption transitions expresses the assumption that actions are executed at the moment at which the timer expirations are available.

Durations

SDL does not foresee the possibility to impose or to assume any quantitative restriction on the duration that an action may take to be executed or how long a process may stay idle in a state before executing one of the enabled actions. Also, concerning the amount of time that a signal may need to travel through a channel, only two cases can be distinguished: either 0 time or an arbitrary amount of time. Nevertheless, in real-time designs, such execution times may not only in uence the performance, but also the functional behaviour of the system.

Currently, it is possible in SDL to describe minimal and maximal durations by means of explicit waiting using timeouts and a notion of \invalid state" to mark the executions taking more than the maximal execution time as \uninteresting". This is used frequently in SDL speci cations, but it is a bad solution as it is cumbersome and it uses a programming construct in order to indicate assumptions about the environment. Such a speci cation can not be used directly for (automatic) code generation, since it is di cult to detect the nature of these timeouts. We suggest to explicitly indicate such durations using prede ned annotations. For instance, we propose to use either interval constraints (e.g. delay= 9.0,11.0]) or mean-values plus jitter (e.g., delay= 10.0 5%]) attached to the corresponding action or channel. Moreover, such annotations could be enriched with probability laws. This extension is mandatory for performance evaluation, but still not su cient, as we also need a model of available computation resources. Note that from a functional veri cation point of view probabilities are not necessary since all the behaviours have to be analyzed independently of their probability: veri cation wants to ensure absence of errors and not just \low probability" of them.

Periodicity

Many telecommunication applications are expected to cope with large streams of data arriving with high and continuous rates (e.g, multimedia services). In practice, components of such applications are designed to t in particular environments, able to deliver multiple inputs at given frequencies. Therefore, periodicity of inputs tends to be an important feature that has to be expressed at the speci cation level. Similar to duration, we propose to annotate external inputs with interval constraints (or mean-values plus jitter) describing the expected period (where applicable). Such annotations are not only mandatory for veri cation but they also clearly improve the readability of the speci cation since they allow to describe in a synthetic manner the relevant characteristics of the assumed environment.

Example 3. A typical producer/consumer system is illustrated in Figure 4. The producer reacts to external request signals and sends data signals to the consumer. When the consumer receives data, it sends an acknowledgment back to the producer. Several annotations are used here. First, we assume that request signals come from the environment at the given rate of one signal every 10 or 11 time units. Also, both data production and consumption times are supposed to be not negligible, the former being between 5 and 7 and the second between 4 and 5 time units.

Notice that, on the contrary to any description using timers or the global time now, here it is obvious to see that a production cycle can be greater than the period of request signals. This may be considered as problematic, as there exist scenarios in which the request signals accumulate inde nitely in the input queue of the producer. At this point, the use of probabilities may become important to decide if the design is acceptable or not.

Flexible channel speci cations

In SDL, only reliable FIFO channels exist as primitive concept. In its use as a speci cation language, however, a channel is often considered to be part of the environment of the implemented system and may represent an abstraction of a whole network. Many protocols are supposed to implement reliable communication through unreliable channels or networks. For veri cation it is therefore necessary to consider the situations where channels lose or reorder messages. Thus, by exible channel speci cation we mean typically that messages can be lost, reordered or delayed to some extent, leading to a well-de ned set of channel types. It is possible to describe any of these channel types by means of additional SDL processes, but it is not necessarily desirable to do so, for several reasons. First of all, these processes serve only for simulation and not for implementation. Also, in some (rare) cases it may be problematic as the transported signals do not carry the pid of the original sender anymore. Finally, the fact to have a prede ned set of channel attributes is an advantage for simulation and veri cation tools as this knowledge can be directly exploited by appropriate techniques and lead to more e cient algorithms (notice for example that an interesting set of properties is decidable for nite state machines communicating through lossy channels whereas they are undecidable in case of communication through reliable channels 1]). We propose annotations on channels allowing to specify a propagation delay in a similar way as execution times and distinguish between fully reliable (which never lose messages) and unreliable channels (where arbitrary losses are possible), and between ordered and unordered ones. Here again, for performance evaluation purposes, it is possible to extend these annotations to include a probability law which speci es a distribution of message losses or a degree of reordering.

Example 4. Figure 5 gives an example of use of annotations to denote propagation delays and reliability of channels. Notice that the default option for a channel is to be ordered and reliable in conformance to the standard SDL semantics.

Extending programming aspects

We make here two concrete proposals to improve SDL as a programming language for real-time systems. These proposals concern respectively the extension of the timer concept and the introduction of standardized packages to provide at the SDL level useful synchronization and atomicity primitives.

Extension of timer concepts

Timers play a central role in SDL to control and observe time progress. They are however limited with respect to what is commonly o ered in real-time systems, and we propose to extend them in several directions.

Interruptive timers and signals SDL timeouts are always received in the form of asynchronous signals. For general-purpose time dependent code this is usually ne, but it is di cult to write real emergency procedures using asynchronous timeouts.

To ensure that a piece of code is executed immediately, or in a speci ed interval, after the expiration of a timeout, the SDL designer must rst make sure that the corresponding agent (process) is idle when the timeout message is received, otherwise, the agent may consume the timeout message from the input queue only when it nishes its current job, which may be too late. This obliges to arti cially restructure the system, whereas in the implementation this task can be left for implementation where it even may be useless because of the existence of interrupts. Therefore, SDL needs a notion of emergency timer, whose expiration is taken into account immediately by the receiving agent. Emergency actions which interrupt the normal execution of an agent were already introduced in sdl-2000 with the advent of exceptions. What we need is an extension of this exception mechanism to be triggerable by system time.

We propose to de ne interruptive timers using an optional attribute (called interruptive). The behaviour of interruptive timers will rely on an extension of the exception mechanism already existing in SDL. More precisely, when an interruptive timer expires, instead of sending a timeout signal via the input port of the process, it will raise a timeout-exception in the concerned process. The handling of this exception is left to the user. However, special care is required to clarify what happens if an interruptive timer wants to interrupt a transition which is required atomic.

In particular, when an interruptive timer expires in a service, while another service (within the same process) is running and executes a time-consuming job.

Example 5. In Figure 6 we illustrate the use of an interruptive timer. When set, it receives as parameter the maximal allowed execution time T. Then, the process enters a loop executing some time-consuming job \decode". Two cases are possible: either the entire job is nished in time, or the maximally allowed time is reached before, when the process is processing a \decode". In the second case, an interruptive timer alarm is needed in order to break the normal execution ow, i.e, to abort the execution of decode and to stop the process immediately.

Note that for sake of readability we use the same notation for normal timeouts and interruptive timeouts. Nevertheless, the meaning is quite di erent: whereas the former denotes a normal SDL transition from a state, the latter is a shorthand notation for an exception handling at this state (and implicitly in all implicit states and actions within the state scope).

Timer consultation

The second extension we propose concerns the ability to consult the expiration time (which is of prede ned sort Time) assigned to a timer. In order to do so, our proposal is simply to add a prede ned value operator on timers (similar to the existing active construct). Such a primitive reduces the current distinction made in SDL between timers and other variables. In particular, the value of the timer can be passed via communi-cation signals from a process to another, used to compute the remaining duration until its expiration, or used to set another timer depending on it, etc.

Obviously, the same result can be obtained using variables of sort Time instead of { or in addition to { timers. But the use of an explicit timer concept (with a set of well de ned primitives) makes the speci cation more readable and the mapping into an implementation easier.

Cyclic timers Finally, the third extension concerns cyclic timers. The idea is to eliminate the current limitation in SDL, where timers are one-shot and have to be explicitly reset in order to model a periodic behaviour. This could be done by simply considering an optional timer attribute (called cyclic) which xes the nature of the timer at its declaration. When a cyclic timer is explicitly set in the speci cation, its period is computed (by subtracting the value of now from the expiration time). After that, at the expiration time (when the corresponding timeout signal is sent) this timer will be implicitly set again using the period and the value of now at expiration. This will continue until either an explicit reset or set occurs (the later restarts the whole behaviour, possibly with a new period). Finally, note that interruptive and cyclic attributes can be safely combined (i.e., the same timer can be both cyclic and interruptive).

Atomicity

There are no atomicity and synchronization primitives foreseen in SDL, the idea being that these are implementation details which should not be mentioned at SDL level. The fact is that in implementation oriented SDL descriptions, they are necessary and several SDL users have expressed the need for native SDL constructs for synchronization 9], especially to achieve atomicity and mutual exclusion. The reason is that such constructs are often used in the speci cation and the implementation of real-time systems such as those developed with SDL. The current practice in SDL is to use calls to external code (e.g. calls to OS primitives) in order to achieve these functionalities. This approach has at least the following obvious inconvenients: the SDL speci cation, which is supposed to be high-level, becomes unnecessary con guration and platform dependent, and the external code cannot be handled properly by simulation and veri cation tools. The need stated above can be addressed without making rst-order extensions to SDL. Synchronisation behaviour can be expressed in terms of existing primitives of SDL, such as asynchronous signal exchange and remote procedures. We propose the use of (standard) libraries for this purpose, as it is the case for other languages. Example 6. For example, a semaphore may be speci ed in SDL as a process type exporting two (empty) procedures P and V, implementing the usual operations on semaphores. The speci cation of such a semaphore type is shown in gure 7. The only prerequisite for this implementation to work is that the atomicity of P and V are preserved for a same instance of semaphore. This prerequisite is ensured by the execution semantics of SDL. Moreover, concurrent wait operations P which arrive after the semaphore is already blocked on a wait are implicitly sequentialized by the save operation from the busy state.

Conclusion and perspectives

We have de ned a number of real-time extensions of SDL in order to obtain a speci cation and modeling language really adequate for real-time systems based on general ideas and re ections we have proposed in 7]. The proposed extensions include:

{ a more exible time-progress semantics for SDL, including as particular cases both the time progress semantics of Z100 and the time-progress semantics used in veri cation tools;

{ powerful and exible annotations allowing to express non-functional aspects:

both very abstract ones necessary at an early design stage, and concrete ones useful for code generation, code annotation and performance analysis;

{ some primitives which allow to make speci cations simpler, easier to understand, and to better separate the implementation oriented and speci cation oriented features;

{ implementation oriented features like emergency timeouts which are mandatory for the use of SDL as a real-time modeling language.

These extensions have been submitted as a rst draft to the ITU-T (Study Group 10) within the framework of Question 7 Time expressiveness and performance annotations on ITU-T modeling languages. All these extensions are based on a uni ed and sound semantic framework which can be integrated smoothly into the existing semantics of SDL in which time progress is mainly \unconstraint". In particular, almost all of them require only local restrictions of the current non-deterministic time semantics. We have already started to extend existing SDL tools in order to deal with these extensions and they already proved their usefulness in real applications. We have implemented a translation of SDL with our proposed time extensions into communicating timed automata with urgencies which are the input language of the IF toolset 6]. IF has been developed at VERIMAG for the purpose of prototyping timed extensions of SDL-like languages. In particular, it includes a model-checker based on the Kronos-tool 19] allowing to verify quantitative time requirements.

In addition, the proposed timed extensions have been implemented also in the ObjectGeode simulator 14]. For both tools we obtain good results, both in what we can express and in what analysis we can perform on annotated models. As an example, we are currently modeling real-time multicast protocols 17, 18] using these annotations.

The main approaches which need to be compared with ours are QSDL 8, 13] and UML related real time extensions (such as UML- RT 16]). QSDL (Queuing SDL) is a performance analysis oriented extension of SDL using a resource mapping and annotations of tasks in terms of \computation power" from which execution and waiting times are computed depending on some scheduling policy which can be user de ned. The underlying semantics considers all non annotated transitions as taking zero time and all transitions are considered urgent, respectively delayable if they may take variable amount of time. In so far, this framework is compatible with ours, but is exclusively performance analysis oriented.

The foreseen real-time extensions of UML are all of a very syntactic nature. It is not clear if there will be a semantic time model at all. However, it is interesting to note that non-functional annotations concerning Quality of Service (such as throughput of channels, execution times,...) are planned and can take likewise the form of requirements and assumptions. The proposed extensions are not completely satisfactory from the user point of view. More extensions may well appear to be useful. In particular, there is a strong need for an expressive notion of deployment diagram, allowing to de ne the mapping of processes to resources, scheduling policies and QoS annotations. The proposed annotations on the SDL level will then have 3 di erent sources: some of them may be user de ned, especially at an early design stage; some of them will be generated from information extracted from such a deployment diagram (which goes far beyond the resource mapping of the QSDL proposal); nally, some will be obtained from analysis results of other parts of the system, especially in a compositional veri cation approach, which is the only one able to deal with large speci cations.

Fig. 1 .

 1 Fig. 1. Urgency assumptions -an example.

Fig. 2 .

 2 Fig. 2. Timer behaviour.

Fig. 3 .

 3 Fig. 3. Timeout urgencies -an example.

Fig. 4 .

 4 Fig. 4. Delay and periodicity assumptions.

Fig. 5 .

 5 Fig. 5. Channel assumptions.

Fig. 6 .

 6 Fig. 6. Interruptive timer example.

Fig. 7 .

 7 Fig. 7. Semaphore example.

? This work is supported by the Interval IST-11557 European project on timed extensions for sdl, msc and ttcn.


Emilio Molina
email: emolina@dim.uchile.cl

Corresponding author MISTEA Alain Rapaport
email: alain.rapaport@inrae.fr

Héctor Ram´ırez

Héctor Ramírez
email: hramirez@dim.uchile.cl

Equivalent Formulations of Optimal Control Problems with Maximum Cost and Applications

Keywords: Optimal control, maximum cost, Mayer problem, state constraint, differential i nclusion, numerical schemes, SIR model Mathematics Subject Classification ( 2000) 4 9N90, 4 9J35, 4

We revisit the optimal control problem with maximum cost with the objective to provide different equivalent reformulations suitable to numerical methods. We propose two reformulations in terms of extended Mayer problems with state constraints, and another one in terms of a differential i nclusion w ith u pper-semi c ontinuous r ight member without state constraint. For the latter we also propose a scheme that approximates from below the optimal value. These approaches are illustrated and discussed in several examples.

Introduction

We consider the optimal control problem which consists in minimizing the maximum of a scalar function over a time interval inf

u(•) ess sup t∈[t0,T ] y(t)
where y(t) = θ(t, ξ(t)) and ξ(•) is the solution of a controlled dynamics ξ = ϕ(ξ, u), ξ(t 0 ) = ξ 0 . This problem is not in the usual Mayer, Lagrange or Bolza forms of the optimal control theory, and therefore is not suitable to use the classical necessary optimality conditions of Pontryagin Maximum Principle or existing solving algorithms (based on direct method, shooting or Hamilton-Jacobi-Bellman equation). However, this problem falls into the class of optimal control with L ∞ criterion, for which several characterizations of the value function have been proposed in the literature [START_REF] Barron | The Bellman equation for minimizing the maximum cost[END_REF][START_REF] Barron | The L ∞ control problem with continuous control functions[END_REF][START_REF] Gonzalez | A Bellman's equation for minimizing the maximum cost[END_REF]. Typically, the value function is solution, in a general sense, of partial differential equation of the form min ∂ t V + inf u without boundary condition. Nevertheless, although necessary optimality conditions and numerical procedures have been formulated [START_REF] Barron | The Pontryagin maximum Principle for minimax problems of optimal control[END_REF][START_REF] Di Marco | A numerical procedure for minimizing the maximum cost[END_REF][START_REF] Di Marco | Minimax optimal control problems. Numerical analysis of the finite horizon case[END_REF][START_REF] Gianatti | Solving minimax control problems via nonsmooth optimization[END_REF], there is no practical numerical tool to solve such problems as it exists for Mayer problems, to the best of our knowledge. The aim of the present work is to study different reformulations of this problem into Mayer form in higher dimension with possibly state or mixed constraints, for which existing numerical methods can be used. Indeed, it has already been underlined in the literature that discrete-time optimal control problems with maximum cost do not satisfy the Principle of Optimality but can be transformed into problems of higher dimension with additively separable objective functions [START_REF] Morgan | Extensions of the Dynamic Programming Framework: Battery Scheduling, Demand Charges, and Renewable Integration[END_REF][START_REF] Morgan | A generalization of Bellman's equation with application to path planning, obstacle avoidance and invariant set estimation[END_REF]. We pursue here this idea but in the continuous time framework, which faces the lack of differentiability of the max function. This manuscript is organized as follows. In Section 2, we establish the setup and the hypotheses of this article, and define the problem. In Section 3, we provide equivalent formulations of the studied problem in the form of two Mayer problems with fixed initial condition, and under state or mixed constraint. In Section 4, we propose another formulation in terms of differential inclusion but without constraints, and then we show how the optimal value can be approximated from below by a sequence of more regular Mayer problems. Section 5 is devoted to numerical illustrations. We consider two problems for which the optimal solution can be determined explicitly (one borrowed from epidemiology), which allows to estimate and compare the numerical performances of the different formulations. These problems have been chosen linear with respect to the control variable in order to present discontinuous optimal controls, which are known to be numerically more sensitive. More precisely, the optimal solution of the first problem has pure bang-bang controls, while the second one possesses a singular arc. We discuss the issues arising in the numerical implementations of the different formulations, and compare numerically with L p approximations. Finally, we discuss in Section 6 about the potential merits of the different formulations as practical methods to compute optimal solution of L ∞ control problems.

Problem and Hypotheses

We shall consider autonomous dynamical systems defined on an invariant domain D of R n+1 of the form ẋ = f (x, y, u), ẏ = g(x, y, u),

(where g is a scalar function) where the values of the control u(•) belong to a given set U ⊂ R p . More specifically, throughout the paper, we shall assume that the following properties are fulfilled.

Assumption 1

i. U is a compact set.

ii. The maps f and g are C 1 on D × U .

iii. The maps f and g have linear growth, that is there exists a number C > 0 such that

||f (x, y, u)|| + |g(x, y, u)| ≤ C(1 + ||x|| + |y|), (x, y) ∈ D, u ∈ U.
For instance, y(•) can be a smooth output of a dynamics

ẋ = f (x, u), y = h(x),
which can be rewritten as ẋ

= f (x, u), ẏ = g(x, u) := ∇h(x) T • f (x, u).
Let U be the set of measurable functions u(•) : [0, T ] → U and consider (x 0 , y 0 ) ∈ D, T > 0. Under the usual arguments of the theory of ordinary differential equations, Assumption 1 ensures that for any u(•) ∈ U there exists a unique absolutely continuous solution (x(•), y(•)) of ( 1) on [0, T ] for the initial condition (x(0), y(0)) = (x 0 , y 0 ) (see, for instance, [START_REF] Fleming | Deterministic and Stochastic Optimal Control[END_REF]). Define then the solutions set

S := {(x(•), y(•)) ∈ AC([0, T ], R n+1 ), sol. of (1) for u(•) ∈ U with (x(0), y(0)) = (x 0 , y 0 )}.
We consider then the optimal control problem which consists in minimizing the "peak" of the function y(•)

P : inf u(•)∈U max t∈[0,T ] y(t) = inf (x(•),y(•))∈S max t∈[0,T ]
y(t) .

Formulations With Constraint

A first approach considers the family of constrained sets of solutions

S z := {(x, y) ∈ S, y(t) ≤ z, t ∈ [0, T ]}, (z ∈ R)
and to look for the optimization problem inf{z; S z ̸ = ∅}.

This problem can be reformulated as a Mayer problem

P 0 : inf u(•)∈U z(T ) for the extended dynamics in D × R    ẋ = f (x, y, u), ẏ = g(x, y, u), ż = 0, under the state constraint C : z(t) -y(t) ≥ 0, t ∈ [0, T ]
where z(0) is free. Direct methods can be used for such a problem. However, as z(0) is free, solutions are not sought among solutions of a Cauchy problem, which prevents using other methods based on dynamic programming such as the Hamilton-Jacobi-Bellman equation.

We propose another extended dynamics in D × R with an additional control v(•) with values in [0, 1]

   ẋ = f (x, y, u), ẏ = g(x, y, u), ż = max(g(x, y, u), 0)(1 -v). (2)
Let V be the set of measurable functions v : [0, T ] → [0, 1]. Note that under Assumption 1, for any (x 0 , y 0 , z 0 ) ∈ D × R and (u, v) ∈ U × V, there exists an unique absolutely solution (x(•), y(•), z(•)) of ( 2) on [0, T ] for the initial condition (x(0), y(0), z(0)) = (x 0 , y 0 , z 0 ). Here, we fix the initial condition with z 0 = y 0 and consider the Mayer problem

P 1 : inf (u(•),v(•))∈U ×V z(T ) under the constraint C
and shows its equivalence with problem P. We first consider fixed controls u(•).

admits an optimal solution. Moreover, an optimal solution verifies

z(T ) = max t∈[0,T ] y(t) (4)
and is reached for a control v(•) that takes values in {0, 1}.

Proof From equations (2), one get that any solution z(•) is non decreasing, and as z satisfies the constraint z ≥ y, we deduce that one has

z(T ) ≥ max t∈[0,T ] y(t) (5)
for any solution of (2), and thus

max t∈[0,T ] y(t) ≤ inf v∈V z(T ) under the constraint z(t) ≥ y(t), t ∈ [0, T ].
Let x(•), y(•) be the solution of (1) for the control u(•) and let I be the set of invisible points from the left of y, that is

I := {t ∈ (0, T ), y(t ′ ) > y(t) for some t ′ < t} .
Consider then the control

v(t) = 1, t ∈ int I, 0, t / ∈ int I. ( 6
)
When I is empty, y(•) is a non decreasing function and, when v(t) = 0 for all t ∈ [0, T ], one has z(t) = y(t) for any t ∈ [0, T ]. Therefore, one has

z(T ) = y(T ) = max t∈[0,T ] y(t).
When I is non empty, there exists, from the sun rising Lemma [START_REF] Tao | An introduction to measure theory[END_REF], a countable set of disjoint non-empty intervals

I n = (a n , b n ) of [0, T ] such that -the interior of I is the union of the intervals I n , -one has y(a n ) = y(b n ) if b n ̸ = T , -if b n = T , then y(a n ) ≥ y(b n ).
Note that when t / ∈ int I, one has y(t) ≥ y(t ′ ) for any t ′ ≤ t. Therefore, the solution z with control (6) verifies z(t) = y(t), t / ∈ int I, y(a n ), t ∈ I n for some n, (see Figure 1 as an illustration). Let t be the largest time in [0, T ] such that

y( t) = max t∈[0,T ] y(t),
which implies that any point t ′ > t in [0, T ] is invisible from the left. Therefore, one has z(T ) = z( t). As for any t z(t) is equal to y(τ ) for some τ , one has necessarily z( t) ≤ y( t). Thus, from [START_REF] Brown | Measurable selections of extrema[END_REF] Remark 3.1 The proof of Proposition 3.2 gives an optimal construction of z(•) which is the lower envelope of non decreasing continuous functions above the function y(•), as depicted on Figure 1. However, there is no uniqueness of the optimal control v(•). Any admissible solution z(•) that is above y(•) and such that z(t) = ŷ for t ≥ t = min{t ∈ (0, T ], y(t) = ŷ}, where ŷ := max s∈[0,T ] y(s), is also optimal.

We then obtain the equivalence between problems P 1 and P in the following sense.

Proposition 3.2 If (u ⋆ (•), v ⋆ (•)) is optimal for Problem P 1 , then u ⋆ (•) is optimal for Problem P. Conversely, if u ⋆ (•) is optimal for Problem P, then (u ⋆ (•), v ⋆ (•)
) is optimal for Problem P 1 where v ⋆ (•) is optimal for the problem (3) for the fixed control u ⋆ (•).

Let us give another equivalent Mayer problem but with a mixed constraint (this will be useful in the next section). We consider again the extended dynamics (2), with a control v(•) which values belong to [0, 1] and the initial conditions (x(0), y(0), z(0)) = (x 0 , y 0 , y 0 ). Define then the mixed constraint

C m : max(y(t) -z(t), 0)(1 -v(t)) + z(t) -y(t) ≥ 0, a.e. t ∈ [0, T ]
and the optimal control problem

P 2 : inf (u(•),v(•))∈U ×V z(T ) under the constraint C m .
Proposition 3.3 Problems P 1 and P 2 are equivalent.

Proof One can immediately see that for any admissible solution that satisfies constraint C, the constraint C m is necessarily fulfilled as max(y -z, 0) is identically null. Conversely, fix an admissible control u(•) and consider a control v(•) that satisfies C m . We show that this implies that the solution (y(•), z(•)) verifies necessarily z(t) ≥ y(t) for any t ∈ [0, T ]. If not, consider the non-empty set

E := {t ∈ [0, T ]; z(t) -y(t) < 0}.
which is open as z -y is continuous. Note that one has ż(t) -ẏ(t) ≥ 0 for a.e. t ∈ E. Therefore z -y is non decreasing in E and we deduce that for any t ∈ E, the interval [0, t] is necessarily included in E, which then contradicts the initial condition z(0) = y(0).

Formulation Without State Constraint

We posit Π = (x, y, z) ∈ D × R and consider the differential inclusion

Π ∈ F (Π) := (u,v)∈U ×[0,1]   f (x, y, u) g(x, y, u) h(x, y, z, u, v)   (7) with h(x, y, z, u, v) = max(g(x, y, u), 0)(1 -v1 R + (z -y))
where 1 R + is the indicator function

1 R + (ζ) = 1, ζ ≥ 0, 0, ζ < 0.
Let Π 0 = (x 0 , y 0 , y 0 ) and denote by S ℓ the set of absolutely continuous solutions of [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF] with Π(0) = Π 0 ∈ D × R. We consider the Mayer problem

P 3 : inf Π(•)∈S ℓ z(T ). Assumption 2 ∀(x, y) ∈ D, G(x, y) := u∈U f (x, y, u) g(x, y, u) is convex.
Proposition 4.1 Under Assumption 2, problem P 3 admits an optimal solution. Moreover, any optimal solution

Π(•) = (x(•), y(•), z(•)) verifies z(T ) = max t∈[0,T ] y(t)
with (x(•), y(•)) solution of (1) for some control u(•) ∈ U, that in turn is optimal for problem P.

Proof We fix the initial condition Π(0) = Π 0 and consider the augmented dynamics

Π ∈ F † (Π) := (u,v,α)∈U ×[0,1] 2   f (x, y, u) g(x, y, u) h † (x, y, z, u, v, α)   (8)
with

h † (x, y, z, u, v, α) = (1 -α)h(x, y, z, u, v) + α max w∈U h(x, y, z, w, 0).
Under Assumption 2, the values of F † are convex compact. One can straightforwardly check that the set-valued map F † is upper semi-continuous1 with linear growth. Therefore, the reachable set S † ℓ (T ) (where S † ℓ denotes the set of absolutely continuous solutions of [START_REF] Di Marco | A numerical procedure for minimizing the maximum cost[END_REF] with 8) which minimizes z(T ).

Π(0) = Π 0 ) is compact (see for instance [1, Proposition 3.5.5]). Then, there exists a solution Π ⋆ (•) = (x ⋆ (•), y ⋆ (•), z ⋆ (•)) of (
Note that any admissible solution (x(•), y(•), z(•)) of system (2) that satisfies the constraint C m belongs to S ℓ ⊂ S † ℓ . We then get the inequality

z ⋆ (T ) ≤ inf{z(T ); (x(•), y(•), z(•)) sol. of (2) with C m }. (9)
Let us show that any solution

Π(•) = (x(•), y(•), z(•)) in S ℓ verifies z(T ) ≥ max t∈[0,T ] y(t). (10)
We show that one has z(t) ≥ y(t) for any t ∈ [0, T ]. We proceed by contradiction, as in the proof of Proposition 3.3.

If the set E = {t ∈ (0, T ); z(t) -y(t) < 0} is non-empty, one has ż(t) -ẏ(t) ≥ 0 for a.e. t ∈ E which implies, by continuity, that one has z(0) -y(0) < 0 which contradicts the initial condition z(0) = y(0). Moreover, as the map h is non-negative, z(•) is non decreasing and we conclude that (10) is verified. On another hand, thanks to Assumptions 1 and 2, we can apply Filippov's Lemma to the set-valued map G, which asserts that (x(•), y(•)) is solution of (1) for a certain u(•) ∈ U. With [START_REF] Fleming | Deterministic and Stochastic Optimal Control[END_REF], we obtain

z ⋆ (T ) ≥ max t∈[0,T ] y ⋆ (t) ≥ inf u∈U max t∈[0,T ] y(t); (x(•), y(•)) sol. of (1) (11)
where

(x ⋆ (•), y ⋆ (•)) is solution of (1) for a certain u ⋆ (•) ∈ U.
Finally, inequalities ( 9) and ( 11) with Propositions 3.2 and 3.3 show that z ⋆ (T ) is reached by a solution of (2) under the constraint C m , and that u ⋆ (•) is optimal for problem P. We also conclude that the optimal value z ⋆ (T ) is reached by a solution in S ℓ , which is thus optimal for problem P 3 .

Remark 4.1 Let us stress that the function h is not continuous, which does not allow to use Filippov's Lemma for the set valued map F . This means that one cannot guarantee a priori that an absolutely continuous solution

Π(•) = (x(•), y(•), z(•)) can be synthesized by a measurable control (u(•), v(•)). Proposition 4.1 shows that (x(•), y(•))
is indeed a solution of system (1) for a measurable control u(•), but one cannot guarantee a priori that z(•) can be generated by a measurable control v(•), which is irrelevant for our purpose.

We end this section by exhibiting an approximation scheme from below of the optimal cost. These approaches are of major interest for minimization problems because, since upper bounds are commonly obtained via any sub-optimal control of problem P 0 , P 1 , P 2 or P 3 (provided typically by a numerical scheme), they are useful to frame the optimal value of the problem. This will be illustrated in Section 5.

Let us consider the family of dynamics parameterized by θ > 0

   ẋ = f (x, y, u), ẏ = g(x, y, u), ż = h θ (x, y, z, u, v), (12)
with

h θ (x, y, z, u, v) = max(g(x, y, u), 0)(1 -v e -θ max(y-z,0) ).
Here the expression e -θ max(y-z,0) plays the role of an approximation of 1 R + (z -y) when θ tends to +∞.

We then define the family of Mayer problems

P θ 3 : inf Π(•)∈S θ z(T )
where S θ denotes the set of absolutely continuous solutions Π(•) = (x(•), y(•), z(•)) of ( 12) for the initial condition Π(0) = Π 0 . Let us underline that, for problems with Lipschitz dynamics and without state constraints, necessary conditions based on Pontryagin Maximum Principle can be derived, leading to shooting methods that are known to be very accurate. They can be initialized from numerical solutions of problems P 1 or P 2 , that in turn can be obtained, for instance, through direct methods.

Proposition 4.2 Under Assumption 2, consider any increasing sequence of numbers θ n (n ∈ N) that tends to +∞. For each n ∈ N, the problem P θn 3 admits an optimal solution, and for any sequence of optimal solutions (x n (•),

y n (•), z n )(•)) of P θn
3 , the sequence (x n (•), y n (•)) converges, up to sub-sequence, uniformly to an optimal solution (x ⋆ (•), y ⋆ (•)) of Problem P, and its derivatives weakly to ( ẋ⋆ (•), ẏ⋆ (•)) in L 2 . Moreover, z n (T ) is an increasing sequence that converges to max t∈[0,T ] y ⋆ (t).

Proof As in the proof of Proposition 4.1, we consider for any θ > 0 the convexified dynamics [START_REF] Aubin | Viability Theory[END_REF] . By Proposition 4.1, we know that there exists an optimal solution (x(•), y(•), z(•)) of problem P 3 such that z(T ) = ȳ. Clearly, this solution belongs to S θ for any θ, and we thus get

  u∈U max t∈[0,T ] y(t); (x(•), y(•)) sol. of
z ⋆ θ (T ) ≤ ȳ. ( 13
)
Let

F θ (Π) := (u,v)∈U ×[0,1]   f (x, y, u) g(x, y, u) h θ (x, y, z, u, v)  
and note that one has lim

θ→+∞ d (F θ (Π), F (Π)) = 0, Π ∈ D × R. ( 14
)
Consider an increasing sequence of numbers θ n (n ∈ N), and denote

Π n (•) = (x n (•), y n (•), z n (•)
) an optimal solution of problem P θn 3 . Note that one has

S θn+1 ⊂ S θn • • • ⊂ S θ0 . (15)
Therefore, the sequence Πn (•) is bounded, and Π n (•) as well. As F is upper semi-continuous, we obtain that Π n (•) converges uniformly on [0, T ], up to a sub-sequence, to a certain

Π ⋆ (•) = (x ⋆ (•), y ⋆ (•), z ⋆ (•)
) which belongs to S l (see for instance [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF]Th. 3.1.7]). From property [START_REF] Morgan | A generalization of Bellman's equation with application to path planning, obstacle avoidance and invariant set estimation[END_REF], we obtain that z n (T ) is a non decreasing sequence that converges to z ⋆ (T ), and from (13), we get passing at the limit

z ⋆ (T ) ≤ ȳ.
On another hand, (x ⋆ (•), y ⋆ (•), z ⋆ (•)) belongs to S l and we get from Proposition 4.1 the inequality

z ⋆ (T ) ≥ ȳ.
Therefore, one has z ⋆ (T ) = ȳ and (x ⋆ (•), y ⋆ (•), z ⋆ (•)) is then an optimal solution of problem P 3 . From Proposition 4.1, we obtain that one has necessarily

z ⋆ (T ) = max t∈[0,T ] y ⋆ (t).
Finally, the sequence ( ẋn (•), ẏn (•)) being bounded, it converges, up to a sub-sequence, weakly to ( ẋ⋆ (•), ẏ⋆ (•)) in L 2 thanks to Alaoglu's Theorem.

Numerical Illustrations

Our aim is to illustrate the different formulations on problems for which the optimal solution is known. We have considered here only direct and Hamilton-Jacobi-Bellman numerical methods, and not indirect methods. As underlined for instance in [START_REF] Caillau | Numerics for finite-dimensional optimal control problems[END_REF], computational schemes based on the Maximum Principle of Pontryagin (such as the shooting method), although usually quite accurate, require an a priori knowledge of the structure of the solution as well as a good approximation of the adjoint state. Here, our objective is to show that solving numerically problems with maximum cost considering the equivalent formulations we propose can be done straightforwardly with existing software based on direct or Hamilton-Jacobi-Bellman methods, without having to provide the structure of the optimal solution.

A Particular Class of Dynamics

We consider dynamics of the form

(Σ) : ẋ = f (x), ẏ = g(x, u). x ∈ R n , u ∈ U, Proposition 5.1 A feedback control x → ϕ ⋆ (x) such that g(x, ϕ ⋆ (x)) = min u∈U g(x, u), x ∈ R n
is optimal for problem P.

Proof For a given x 0 in R n , let x(•) be the solution of ẋ = f (x), x(0) = x 0 independently to the control u(•). For any control u(•), the corresponding solution y(•) verifies

y(t) = y(0) + t 0 g(x(τ ), u(τ )) dτ ≥ y(0) + t 0 min v∈U g(x(τ ), v) dτ, t ≥ 0. ( 16
)
Consider the (measurable) map ϑ(t, u) := g(x(t), u), (t, u) ∈ [0, T ] × U.

From the existence of measurable selection of extrema of measurable maps (see, for instance, Theorem 2 in [START_REF] Brown | Measurable selections of extrema[END_REF]), there exists a measurable control u ⋆ (•) such that

ϑ(t, u ⋆ (t)) = min v∈U ϑ(t, v), t ∈ [0, T ].
Let y ⋆ (•) be defined as

y ⋆ (t) := y(0) + t 0 g(x(τ ), u ⋆ (t)) dτ = y(0) + t 0 min v∈U g(x(τ ), v) dτ, t ≥ 0.
Clearly, y ⋆ (•) is solution of Σ for the control u ⋆ (•) and one gets from ( 16)

max t y(t) ≥ max t y ⋆ (t).
We conclude that y ⋆ (•) is an optimal trajectory of problem P for the control generated by the feedback ϕ ⋆ .

As a toy example, we have considered the system

ẋ = 1, x(0) = 0, ẏ = (1 -x)(2 -x)(4 -x)(1 + u/2), y(0) = 0, u ∈ [-1, 1] for which ϕ ⋆ (x) = -sign (1 -x)(2 -x)(4 -x)
is an optimal control which minimizes max t∈[0,T ] y(t). The optimal control is thus pure bang-bang. Remark that this problem can be equivalently written with a scalar non-autonomous dynamics

ẏ = (1 -t)(2 -t)(4 -t)(1 + u/2)
for which the open-loop control

u ⋆ (t) = -sign (1 -t)(2 -t)(4 -t)
is optimal.

For T = 5, we have first computed the exact optimal solution of problem P with the open-loop u ⋆ (•), by integrating the dynamics with Scipy in Python software (see Figure 2). Effects of perturbations on the switching times on the criterion are presented in Table 1, which show a quite high sensitivity of the optimal control for this problem (as it often the case for bang-bang controls). Then, we have solved numerically problems P 0 to P 2 with a direct method (Bocop software using Gauss II integration scheme) for 500 time steps and an optimization relative tolerance equal to and 1 as we know that the optimal solution is reached for v ∈ {0, 1} (see Proposition 3.1). The numerical results and computation times are summarized in Table 2, while Figure 3 presents the corresponding trajectories. We note that the direct method give very accurate results, and the computation time for problem P 0 is the lowest because it has only one control. The computation time for problem P 2 is slightly higher than for P 1 because the mixed constraint C m is heavier to evaluate. The numerical method for problem P 3 is of completely different nature as it computes the optimal solution for all the initial conditions on the grid, which explains a much longer computation time. The accuracy of the results is also directly related to the size of the discretization grid and can be improved by increasing this size but at the price of a longer computation time.

It can be noticed in Figure 3 some differences between the obtained trajectories. Let us underline that after the peak of y(•), there is no longer uniqueness of the optimal control (indeed any value of the control does not modify the value of the peak). Hence, we may think about considering an additional cost after the peak to avoid this multiplicity. However, since neither the value of the peak, nor the time when it is reached, are known, this does not seem easy to implement.

Application to an Epidemiological Model

The SIR model is one of the most basic transmission model in epidemiology for a directly transmitted infectious disease (see [START_REF] Weiss | The SIR model and the foundations of public health[END_REF] for a complete introduction) and it retakes great importance nowadays due to Covid-19 epidemic.

Consider on a time horizon [0, T ] variables S(t), I(t) and R(t) representing the fraction of susceptible, infected and recovery individuals at time t ∈ [0, T ], so that one has S(t) + I(t) + R(t) = 1 with S(t), I(t), R(t) ≥ 0. Let β > 0 be the rate of transmission and γ > 0 the recovery rate. Interventions as lock-downs and curfew are modeled as a factor in rate transmission that we denote u and which represents our control variable taking values in [0, u max ] with u max ∈ (0, 1), where u = 0 means no intervention and u = u max the most restrictive one which reduces as much as possible contacts among population. The SIR dynamics including the control is then given by the following equations:

Ṡ = -(1 -u)βSI, (17)
İ = (1 -u)βSI -γI, (18)
Ṙ = γI. (19)
When the reproduction number R 0 = β/γ is above one and the initial proportion of susceptible is above the herd immunity threshold S h = R -1 0 , it is well known that there is an epidemic outbreak. Then, the objective is to minimize the peak of the prevalence max

t∈[0,T ] I(t) with respect to control u(•) subject to a L 1 budget T 0 u(t) ≤ Q (20)
on a given time interval [0, T ] where T is in chosen large enough to ensure the herd immunity of the population is reached at date T . Note that one can drop the R dynamics to study this problem. If the constraint (20) were not imposed, then the optimal solution would be the trivial control u(t) = u max , t ∈ [0, T ], which is in general unrealistic from a operational point of view. A similar problem has been considered in [START_REF] Morris | Optimal, near-optimal, and robust epidemic control[END_REF] but under the constraint that intervention occurs only once on a time interval of given length, that we relax here. Note that the constraint (20) can be reformulated as a target condition, considering the augmented dynamics

Ṡ = -(1 -u)βSI, (21)
İ = (1 -u)βSI -γI, (22)
Ċ = -u(t), (23)
with initial condition C(0) = Q and target {C ≥ 0}. Extension of the results of Sections 3 and 4 to problems with target do not present any particular difficulty, and is left to the reader. For initial conditions I 0 = I(0) > 0 and S 0 = S(0) > S h , the optimal solution has been determined in [START_REF] Molina | An optimal feedback control that minimizes the epidemic peak in the SIR model under a budget constraint[END_REF] as the feedback control

ψ(I, S) := 1 -S h S if I = Ī and S > S h , 0 otherwise, where Ī :
= I 0 + S 0 -S h -S h log S0 S h QβS h + 1
is the optimal value of the peak. The proof of the optimality of this feedback is out of the scope of the present paper and can be found in [START_REF] Molina | An optimal feedback control that minimizes the epidemic peak in the SIR model under a budget constraint[END_REF]. This control strategy consists in three phases:

1. no intervention until the prevalence I reaches Ī (null control), 2. maintain the prevalence I equal to Ī until S reaches S h (singular control), 3. no longer intervention when S > S h (null control), as illustrated in Figure 4 for the parameters given in Table 3. Note that differently to the previous example, this Optimal control u Fig. 4 The optimal solution for the SIR problem.

control strategy is intrinsically robust with respect to a bad choice of Ī: the maximum value of I is always guaranteed to be equal to Ī. However, a mischoice of Ī has an impact on the budget (see [START_REF] Molina | An optimal feedback control that minimizes the epidemic peak in the SIR model under a budget constraint[END_REF] for more details). Table 3 Parameters used in numerical computations and optimal value of the peak.

Adding the z-variable, we end up with a dynamics in dimension four, which is numerically heavier than for the previous example. In particular, methods based on the value function are too time consuming to obtain accurate results for refined grids in a reasonable computation time. So we have considered direct methods only. We do not consider here problem P 3 , but instead its regular approximations P θ 3 suitable to direct methods. For direct methods that use algebraic differentiation of the dynamics, convergence and accuracy are much better if one provides differentiable dynamics. This is why we have approximated the max(•, 0) operator for problems P 1 and P 2 by the Laplace formula log e λξ + 1 λ -→ λ→+∞ max(ξ, 0), ξ ∈ R with λ = 100 for the numerical experiments. For problem P θ 3 , one has to be careful about the interplay between the approximations of max(•, 0) and the sequence θ n → +∞, to provide approximations from below of the optimal value. The function h θ is thus approximated by the expression

h θ (x, y, z, u, v) ≃ log e λ1g(x,y,u) + 1 λ 1 1 -ve θ λ 2
log(e λ 2 (y-z) +1)

which depends on three parameters λ 1 , λ 2 and θ. Posit for convenience

α := θ λ 2
and consider the function 2. For any ε ∈ (0, 1), one has ω α,λ2 -ε 2 = ε and ω α,λ2 (0) = 1 -ε exactly for

ω α,λ2 (
α = - log(1 -ε) log(2) , λ 2 = log(ε -1 α -1) ε 2 . ( 24
)
Proof One has first Finally, with simple algebraic manipulation of the conditions ω α,λ2 -ε 2 = ε and ω α,λ2 (0) = 1 -ε, one obtains straightforwardly the expressions (24). We have taken λ 1 = 5000 and considered a sequence of approximations of the indicator function for the values given in Table 4 according to expressions (24) of Lemma 5.1 (see Figure 5).

ω ′ α,λ2 (ξ) = λ 2 α e -λ2x e -λ2ξ + 1 ω α,λ2 (
Computations have been performed with Bocop software on a standard laptop computer (with a Gauss II integration scheme, 600 time steps and relative tolerance 10 -10 ). As one can see in Figure 6 and Table 5 problems P 0 , P 1 , P 2 give the peak values with a very good accuracy, and present similar performances in terms of computation time. In Figure 7 and Table 6, the numerical solutions of P θ 3 are illustrated for the values of α and λ 2 given in Table 4. As expected, the numerical computation of the family of problems P θ 3 provides an increasing sequence of approximation from below of the optimal value and thus complements the computation of problems P 0 , P 1 or P 2 . From Figures of Tables 5 and6, one can safely guarantee that the optimal value belongs to the interval [0.1010, 0.1015]. However, the trajectories found for P θ 3 are not as closed as the ones of problems P 0 , P 1 or P 2 . This can be explained by the fact that problems P θ 3 are not subject to the constraint z(t) ≥ y(t) and thus provides trajectories for which z(T ) is indeed below max t y(t). Finally, we have compared our approximation technique with the classical approximation of the L ∞ criterion by L p norms P L p : inf

u(•)∈U ||y(t)|| p
with the same direct method. To speed up the convergence, we have used the Bocop facility which allows a batch mode which consists in initializing the search from a solution found for a former value of p, that have been taken p ∈ {2, 5, 10, 15} (see Figure 8). Besides, to ensure convergence it was necessary take 1200 time step instead of 600 as in previous simulations. The total time of the process is 78s after summing computation times given in methods. Moreover, the same method for p = 15 but initialized from the solution found for p = 2 gives poor results for a computation time of 50s (see Figure 9). We conclude that the L p approximation is not practically reliable for this kind of problems.

Discussion and Conclusions

In this work, we have presented different reformulations of optimal control problems with maximum cost in terms of extended Mayer problems, and tested them numerically on two examples whose optimal solution has bang-bang controls and singular arcs. We have proposed two kinds of formulations: one with state or mixed constraints suitable to direct methods, and another one without any constraint but less regular and suitable to dynamical programming type methods. Moreover, for the latter one, we have proposed an approximation scheme generated by a sequence of regular Mayer unconstrained problems, which performs better than approximations based on L p norms. However, although this second approach requires larger computation time, it complements the first one providing approximations of the optimal value from above. This first work puts in perspective the study of necessary optimality conditions for the maximum cost problems with the help of these formulations, which will be the matter of a future work.

Finally, we summarize advantages and drawbacks of the different formulations for numerical computations in Table 8, that could help practitioners in the choice of the method.

Proposition 3 . 1

 31 For any control u(•) ∈ U, the optimal control problem inf v∈V z(T ) under the constraint C

  ) under the constraint C.

Fig. 1

 1 Fig.1Illustration of the function z (in red) corresponding to a function y (in blue) with the control given by expression[START_REF] Caillau | Numerics for finite-dimensional optimal control problems[END_REF].

Fig. 2 3 Fig. 3

 233 Fig. 2 Optimal solution: y(•) on the left, u ⋆ (•) on the right

Lemma 5 . 1 1 .

 511 ξ) := e -α log(e -λ 2 ξ +1) , ξ ∈ R which approximates the indicator function 1 R + . One has the following properties. For any positive numbers α, λ 2 , the function ω α,λ2 is increasing with lim ξ→-∞ ω α,λ2 (ξ) = 0, lim ξ→+∞ ω α,λ2 (ξ) = 1.

  ξ) > 0 and the function ω α,λ2 (•) is thus increasing. From lim ξ→-∞ -α log(e -λ2ξ + 1) = -∞ λ2 (ξ) = 1.

Fig. 5

 5 Fig. 5 Approximation of the indicator function with different values of ε (zoom on the abscissa axis on the right).

2 Fig. 6 Fig. 7

 267 Fig.6Comparisons of numerical results for the methods P 0 , P 1 , P 2 .

15 Fig. 9

 159 Fig. 9 Numerical solution for P L 15 without batch iteration (computation time 50s).

Table 1

 1 Sensitivity to the optimal switching.

	disturbance	max	y(t)	error
		t∈[0,T ]
	0	2.24985	0
	0.001%	2.24985	4.10 -6 %
	0.01%	2.25010	0.01%
	0.1%	2.69457	20%

Table 2

 2 Comparison of the numerical results.

	problem	max	y(t)	error	computation time
		t∈[0,T ]
	P	2.24705	0	-
	P 0	2.249888	0.126%	0.5 s
	P 1	2.24998	0.130%	1.8 s
	P 2	2.249941	0.129%	3.8 s
	P 3	2.26778	0.8%	248 s

10 -10

. For problem P 3 , as the dynamics is not continuous, direct methods do not work well and we have used instead a numerical scheme based on dynamic programming (BocopHJB software) with 500 time steps and a discretization of 200 × 200 points of the state space. For the additional control v, we have considered only two possible values 0

Table 4

 4 Values of parameters α, λ 2 for different ε.

	ε	α	λ 2
	0.2	0.32	124
	0.15	0.234 360
	0.1	0.152 1514
	0.075 0.112 4094
	0.05	0.074 16193

Table 5

 5 Comparison of performances for problems P 0 , P 1 , P 2 .

	problem	max	y(t) computation time
		t∈[0,T ]
		P 0	0.1015		10 s
		P 1	0.1015		12 s
		P 2	0.1015		13 s
	ε	z(T )	max	y(t)	computation time
			t∈[0,T ]
	0.2	0.0684	0.1038	80 s
	0.15	0.0823	0.1038	65 s
	0.1	0.0954	0.1037	51 s
	0.075 0.0993	0.1050	83 s
	0.05	0.1010	0.1036	97 s

Table 6

 6 Comparison of performances for problem P θ 3 .

Table 7 .

 7 However, one can see that the trajectory found for p = 15 is quite far to give a peak value close from the other Numerical solutions for problems P L p .

				state I								control
	0.08 0.10 0.12						1 L 2 L 5 L 10 L 15		0.4 0.5 0.6						1 L 2 L 5 L 10 L 15
	0.06								0.3
	0.04								0.2
	0.02								0.1
	0.00								0.0
	0	50	100	150	200	250	300		0	50	100	150	200	250	300
	Fig. 8 p	max	y(t)	||y(t)||p	computation time
						t∈[0,T ]
					2	0.119653	1.0222		34 s
					5	0.105244	0.2474		14 s
					10	0.105375	0.15678		13 s
					15	0.105170	0.13549		17 s

Table 7

 7 Comparison of the numerical results with the L p approximation.

Table 8

 8 Comparison of the different formulations.

	Formulation	P 0	P 1 or P 2	P 3	P θ 3
	suitable to direct methods	yes	yes	no	yes
	suitable to Hamilton-Jacobi-Bellman methods	no	yes	yes	yes
	suitable to shooting methods without constraint	no	no	no	yes
	provides approximations from below	no	no	no	yes

A set-valued map F : X ⇝ X is upper semi-continuous at ξ ∈ X if and only if for any neighborhood N of F (ξ), there exists η > 0 such that for any ξ ′ ∈ B X (ξ, η) one has F (ξ ′ ) ⊂ N (see for instance[START_REF] Aubin | Viability Theory[END_REF]).

Acknowledgements The authors are grateful to Pierre Martinon for fruitful discussions and advices. This work was partially supported by ANID-PFCHA/Doctorado Nacional/2018-21180348, FONDECYT grant 1201982 and Centro de Modelamiento Matemático (CMM) FB210005 BASAL fund for center of excellence, all of them from ANID (Chile).