M R Khouadjia

M Schoenauer
email: marc.schoenauer@inria.fr

V Vidal

J Dréo

P Savéant

Multi-Objective AI Planning: Evaluating DaE YAHSP on a Tunable Benchmark

All standard Artifical Intelligence (AI) planners to-date can only handle a single objective, and the only way for them to take into account multiple objectives is by aggregation of the objectives. Furthermore, and in deep contrast with the single objective case, there exists no benchmark problems on which to test the algorithms for multi-objective planning. Divide-and-Evolve (DaE) is an evolutionary planner that won the (singleobjective) deterministic temporal satisficing track in the last International Planning Competition. Even though it uses intensively the classical (and hence single-objective) planner YAHSP (Yet Another Heuristic Search Planner), it is possible to turn DaEYAHSP into a multi-objective evolutionary planner. A tunable benchmark suite for multi-objective planning is first proposed, and the performances of several variants of multi-objective DaEYAHSP are compared on different instances of this benchmark, hopefully paving the road to further multi-objective competitions in AI planning.

Introduction

An AI Planning problem (see e.g. [START_REF] Ghallab | Automated Planning, Theory and Practice[END_REF]) is defined by a set of predicates, a set of actions, an initial state and a goal state. A state is a set of non-exclusive instantiated predicates, or (Boolean) atoms. An action is defined by a set of pre-conditions and a set of effects: the action can be executed only if all preconditions are true in the current state, and after an action has been executed, the effects of the action modify the state: the system enters a new state. A plan in AI Planning is a sequence of actions that transforms the initial state into the goal state. The goal of AI Planning is to find a plan that minimizes some quantity related to the actions: number of actions, or sum of action costs in case actions have different costs, or makespan in the case of temporal planning, when actions have a duration and can eventually be executed in parallel. All these problems are P-SPACE.

A simple planning problem in the domain of logistics is given in Figure 1: the problem involves cities, passengers, and planes. Passengers can be transported from one city to another, following the links on the figure. One plane can only carry one passenger at a time from one city to another, and the flight duration (number on the link) is the same whether or not the plane carries a passenger (this defines the domain of the problem). In the simplest non-trivial instance of such domain, there are 3 passengers and 2 planes. In the initial state, all passengers and planes are in city 0, and in the goal state, all passengers must be in city 4. The not-so-obvious optimal solution has a total makespan of 8 and is left as a teaser for the reader.

AI Planning is a very active field of research, as witnessed by the success of the ICAPS conferences (http://icaps-conferences.org), and its Intenational Planning Comptetition (IPC), where the best planners in the world compete on a set of problems. This competition has lead the researchers to design a common language to describe planning problems, PDDL (Planning Domain Definition Language). Two main categories of planners can be distinguished: exact planners are guaranteed to find the optimal solution . . . if given enough time; satisficing planners give the best possible solution, but with no optimality guarantee. A complete description of the state-of-the-art planners is far beyond the scope of this paper.

However, to the best of our knowledge, all existing planners are single objective (i.e. optimize one criterion, the number of actions, the cost, or makespan, depending on the type of problem), whereas most real-world problems are in fact multi-objective and involve several contradictory objectives that need to be optimized simultaneously. For instance, in logistics, the decision maker must generally find a trade-off between duration and cost (or/and risk).

An obvious solution is to aggregate the different objectives into a single objective, generally a fixed linear combination of all objectives. Early work in that area used some twist in PDDL 2.0 [START_REF] Do | SAPA: A Multi-Objective Metric Temporal Planner[END_REF][START_REF] Refanidis | Multiobjective Heuristic State-Space Planning[END_REF][START_REF] Gerevini | An Approach to Efficient Planning with Numerical Fluents and Multi-Criteria Plan Quality[END_REF]. PDDL 3.0, on the other hand, explicitly offered hooks for several objectives x, and a new track of IPC was dedicated to aggregated multiple objectives: the "net-benefit" track took place in 2006 [START_REF] Chen | Temporal Planning using Subgoal Partitioning and Resolution in SGPlan[END_REF] and 2008 [START_REF] Edelkamp | Optimal Symbolic Planning with Action Costs and Preferences[END_REF], . . . but was canceled in 2011 because of the small number of entries. In any case, no truly multi-objective approach to multi-objective planning has been proposed since the very preliminary proof-of-concept in the first Divide-and-Evolve paper [START_REF] Schoenauer | Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning[END_REF].

One goal of this paper is to build on this preliminary work, and to discuss various issues related to the challenge of solving multi-objective problems with an evolutionary algorithm that is heavily based on a single-objective planner (YAHSP [START_REF] Vidal | A Lookahead Strategy for Heuristic Search Planning[END_REF]) -and in particular to compare different state-of-the-art multiobjective evolutionary schemes when used within DaE YAHSP . However, experimental comparison requires benchmark problems. Whereas the IPC have validated a large set of benchmark domains, with several instances of increasing complexity in each domain, nothing yet exists for multi-objective planning. The other goal of this paper is to propose a tunable set of benchmark instances, based on a simplified model of the IPC logistics domain Zeno illustrated in Fig. 1. One advantage of this multi-objective benchmark is that the exact Pareto Front is known, at least for its simplest instances.

The paper is organized as follows: Section 2 rapidly introduces Divide-and-Evolve, more precisely the representation and variation operators that have been used in the single-objective version of DaE YAHSP that won the temporal deterministic satisficing track at the last IPC in 2011. Section 4 details the proposed benchmark, called MultiZeno, and gives hints about how to generate instances of different complexities within this framework. Section 3.2 rapidly introduces the 4 variants of multi-objective schemes that will be experimentally compared on some of the simplest instances of the MultiZeno benchmark and results of different series of experiments are discussed in Section 6. Section 7 concludes the paper, giving hints about further research directions.

Divide-and-Evolve

Let P D (I, G) denote the planning problem defined on domain D (the predicates, the objects, and the actions), with initial state I and goal state G. In STRIPS representation model [START_REF] Fikes | STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving[END_REF], a state is a list of Boolean atoms defined using the predicates of the domain, instantiated with the domain objects.

In order to solve P D (I, G), the basic idea of DaE X is to find a sequence of states S 1 , . . . , S n , and to use some embedded planner X to solve the series of planning problems P D (S k , S k+1 ), for k ∈ [0, n] (with the convention that S 0 = I and S n+1 = G). The generation and optimization of the sequence of states (S i ) i∈ [1,n] is driven by an evolutionary algorithm. After each of the sub-problems P D (S k , S k+1 ) has been solved by the embedded planner, the concatenation of the corresponding plans (possibly compressed to take into account possible parallelism in the case of temporal planning) is a solution of the initial problem. In case one sub-problem cannot be solved by the embedded solver, the individual is said unfeasible and its fitness is highly penalized in order to ensure that feasible individuals always have a better fitness than unfeasible ones, and are selected only when there are not enough feasible individual. A thorough description of DaE X can be found in [START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF]. The following rest of this section will focus on the evolutionary parts of DaE X .

Representation and Initialization

An individual in DaE X is hence a variable-length list of states of the given domain. However, the size of the space of lists of complete states rapidly becomes untractable when the number of objects increases. Moreover, goals of planning problems need only to be defined as partial states, involving a subset of the objects, and the aim is to find a state such that all atoms of the goal state are true. An individual in DaE X is thus a variable-length list of partial states, and a partial state is a variable-length list of atoms.

Previous work with DaE X on different domains of planning problems from the IPC benchmark series have demonstrated the need for a very careful choice of the atoms that are used to build the partial states [START_REF] Bibaï | On the Benefit of Sub-Optimality within the Divide-and-Evolve Scheme[END_REF]. The method that is used today to build the partial states is based on a heuristic estimation, for each atom, of the earliest time from which it can become true [START_REF] Haslum | Admissible Heuristics for Optimal Planning[END_REF]. These earliest start times are then used in order to restrict the candidate atoms for each partial state: the number of states is uniformly drawn between 1 and the number of estimated start times; For every chosen time, the number of atoms per state is uniformly chosen between 1 and the number of atoms of the corresponding restriction. Atoms are then added one by one: an atom is uniformly drawn in the allowed set of atoms (based on earliest possible start time), and added to the individual if it is not mutually exclusive (in short, mutex) with any other atom that is already there. Note that only an approximation of the complete mutex relation between atoms is known from the description of the problem, and the remaining mutexes will simply be gradually eliminated by selection, because they make the resulting individual unfeasible.

To summarize, an individual in DaE X is represented by a variable-length time-consistent sequence of partial states, and each partial state is a variablelength list of atoms that are not pairwise mutex.

Variation Operators

Crossover and mutation operators are defined on the DaE X representation in a straightforward manner -though constrained by the heuristic chronology and the partial mutex relation between atoms.

A simple one-point crossover is used, adapted to variable-length representation: both crossover points are independently chosen, uniformly in both parents. However, only one offspring is kept, the one that respects the approximate chronological constraint on the successive states. The crossover operator is applied with a population-level crossover probability.

Four different mutation operators are included: first, a population-level mutation probability is used; one an individual has been designated for mutation, the choice between the four mutation operators is made according to user-defined relative weights. The four possible mutations operate either at the individual level, by adding (addState) or removing (delState) a state, or at the state level by adding (addAtom) or removing (delAtom) some atoms in a uniformly chose state.

All mutation operators maintain the approximate chronology between the intermediate states (i.e., when adding a state, or an atom in a state), and the local consistency within all states (i.e. avoid pairwise mutexes).

Hybridization

DaE X uses an external embedded planner to solve the sequence of sub-problems defined by the ordered list of partial states. Any existing planner can in theory be used. However, there is no need for an optimality guarantee when solving the intermediate problems in order for DaE X to obtain good quality results [START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF]. Hence, and because several calls to this embedded planner are necessary for a single fitness evaluation, a sub-optimal but fast planner is used: YAHSP [8] is a lookahead strategy planning system for sub-optimal planning which uses the actions in the relaxed plan to compute reachable states in order to speed up the search process.

For any given k, if the chosen embedded planner succeeds in solving P D (S k , S k+1 ), the final complete state is computed by executing the solution plan from S k , and becomes the initial state of the next problem. If all the sub-problems are solved by the embedded planner, the individual is called feasible, and the concatenation of the plans for all sub-problems is a global solution plan for P D (S 0 = I, S n+1 = G). However, this plan can in general be further optimized by rescheduling some of its actions, in a step called compression. The computation of all objective values is done from the compressed plan of the given individual. Finally, because the rationale for DaE X is that all sub-problems should hopefully be easier than the initial global problem, and for computational performance reason, the search capabilities of the embedded planner YAHSP are limited by setting a maximal number of nodes that it is allowed to expand to solve any of the sub-problems (see again [START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF] for more details).

Multi-Objective Divide-and-Evolve

In some sense, the multi-objectivization of DaE X is straightforward -as it is for most evolutionary algorithms. The "only" parts of the algorithm that require some modification are the selection parts, be it the parental selection, that chooses which individual from the population are allowed to breed, and the environmental selection (aka replacement), that decides which individuals among parents and offspring will survive to the next generation. Several schemes have been proposed in the EMOA literature (see e.g. Section 3.2), and the end of this Section will briefly introduce the ones that have been used in this work. However, a prerequisite is that all objectives are evaluated for all potential solutions, and the challenge here is that the embedded planner YAHSP performs its search based on only one objective.

Multi-objectivization Strategies

Even though YAHSP (like all known planners to-date) only solves planning problems based on one objective. However, it is possible since PDDL 3.0 to add some other quantities (aka Soft Constraints or Preferences [START_REF] Gerevini | Preferences and Soft Constraints in PDDL3[END_REF]) that are simply computed throughout the execution of the final plan, without interfering with the search.

The very first proof-of-concept of multi-objective DaE X [START_REF] Schoenauer | Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning[END_REF], though using an exact planner in lieu of the satisficing planner YAHSP, implemented the simplest idea with respect to the second objective: ignore it (though computing its value for all individuals) at the level of the embedded planner, and let the evolutionary multi-objective take care of it. However, though YAHSP can only handle one objective at a time, it can handle either one in turn, provided they are both defined in the PDDL domain definition file. Hence a whole bunch of smarter strategies become possible, depending on which objective YAHSP is asked to optimize every time it runs on a sub-problem. Beyond the fixed strategies, in which YAHSP always uses the same objective throughout DaE YAHSP runs, a simple dynamic randomized strategy has been used in this work: Once the planner is called for a given individual, the choice of which strategy to apply is made according to roulette-wheel selection based on user-defined relative weights; In the end, it will return the values of both objectives. It is hoped that the evolutionary algorithm will find a sequential partitioning of the problem that will nevertheless allow the global minimization of both objectives. Section 6.2 will experimentally compare the fixed strategies and the dynamic randomized strategy where the objective that YAHSP uses is chosen with equal probability among both objectives.

Other possible strategies include adaptive strategies, where each individual, or even each intermediate state in every individual, would carry a strategy parameter telling YAHSP which strategy to use -and this strategy parameter would be subject to mutation, too. This is left for further work.

Evolutionary Multi-Objective Schemes

Several Multi-Objective EAs (MOEAs) have been proposed in the recent years, and this work is concerned with comparing some of the most popular ones when used within the multi-objective version of DaE YAHSP . More precisely, the following selection/reproduction schemescan be applied to any representation, and will be experimented with here: NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], SPEA2 [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization[END_REF], and IBEA [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF]. They will now be quickly introduced in turn.

The Non-dominated Sorting Genetic Algorithm (NSGA-II) has been proposed by Deb et al. [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. At each generation, the solutions contained in the current population are ranked into successive Pareto fronts in the objective space. Individuals mapping to vectors from the first front all belong to the best efficient set; individuals mapping to vectors from the second front all belong to the second best efficient set; and so on. Two values are then assigned for every solution of the population. The first one corresponds to the rank of the Pareto front the corresponding solution belongs to, and represents the quality of the solution in terms of convergence. The second one, the crowding distance, consists in estimating the density of solutions surrounding a particular point in the objective space, and represents the quality of the solution in terms of diversity. A solution is said to be better than another solution if it has a better rank value, or in case of equality, if it has a larger crowding distance.

The Strength Pareto Evolutionary Algorithm (SPEA) [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF], introduces an improved fitness assignment strategy. It intrinsically handles an internal fixedsize archive that is used during the selection step to create offspring solutions. At a given iteration of the algorithm, each population and archive member x is assigned a strength value S(x) representing the number of solutions it dominates. Then, the fitness value F (x) of solution x is calculated by summing the strength values of all individuals that x currently dominates. Additionally, a diversity preservation strategy is used, based on a nearest neighbor technique. The selection step consists of a binary tournament with replacement applied on the internal archive only. Last, given that the SPEA2 archive has a fixed size storage capacity, a pruning mechanism based on fitness and diversity information is used when the non-dominated set is too large. The Indicator-Based Evolutionary Algorithm (IBEA) [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] introduces a total order between solutions by means of a binary quality indicator. The fitness assignment scheme of this evolutionary algorithm is based on a pairwise comparison of solutions contained in the current population with respect to a binary quality indicator I. Each individual x is assigned a fitness value F (x) measuring the "loss in quality" that would result from removing x from the current population. Different indicators can be used. The most two popular, that will be used in this work, are the additive ǫ-indicator (I ǫ + ) and the hypervolume difference indicator (I H -) as defined in [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF]. Each indicator I(x, x ′ ) gives the minimum value by which a solution x ∈ X can be translated in the objective space to weakly dominate another solution x ′ ∈ X. An archive stores solutions mapping to potentially non-dominated points in order to prevent their loss during the stochastic search process.

A Benchmark Suite for Multi-Objective Temporal Planning

This section details the proposed benchmark test suite for multi-objective temporal planning, based on the simple domain that is schematically described in Figure 1. The reader will have by now solved the little puzzle set in the Introduction, and found the solution with makespan 8 (flying 2 passengers to city 1, one plane continues with its passenger to city 4 while the other plane flies back empty to city 0, the plane in city city 4 returns empty to city 1 while the other plane brings the last passenger there, and the goal is reached after both planes bring both remaining passengers to city 4). The rationale for this solution is that no plane ever stays idle.

In order to turn this problem into a not-too-unrealistic logistics multi-objective problem, some costs or some risks are added to all 3 central cities (1 to 3). This leads to two types of problems: In the MultiZeno Cost , the second objective is an additive objective: each plane has to pay the corresponding tax every time it lands in that city; In the MultiZeno Risk , the second objective is similar to a risk, and the maximal value encountered during the complete execution of a plan is to be minimized.

In both cases, there are 3 obvious points that belong to the Pareto Front: the solution with minimal makespan described above, and the similar solutions that use respectively city 2 and city 3 in lieu of city 1. The values of the makespans are respectively 8, 16 and 24, and the values of the costs are, for each solution, 4 times the value of the single landing tax, and exactly the value of the involved risk. For the risk case, there is no other point on the Pareto Front, as a single landing on a high-risk city sets the risk of the whole plan to a high risk. For the cost model however, there are other points on the Pareto Front, as different cities can be used for the different passengers. For instance, in the case of Figure 1, this leads to a Pareto Front made of 5 points, [START_REF] Vidal | A Lookahead Strategy for Heuristic Search Planning[END_REF][START_REF] Haslum | Admissible Heuristics for Optimal Planning[END_REF], [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF][START_REF] Vidal | A Lookahead Strategy for Heuristic Search Planning[END_REF], and (24,4) (going only through city 1, 2 and 3 respectively), plus [START_REF] Haslum | Admissible Heuristics for Optimal Planning[END_REF][START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF] and [START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF][START_REF] Edelkamp | Optimal Symbolic Planning with Action Costs and Preferences[END_REF]. Only the first 3 are the Pareto Front in the risk case.

Tuning the Complexity

There are several ways to make this first simple instance more or less complex. A first possibility is to add passengers. In this work, only bunches of 3 passengers have been considered, in order to be able to easily derive some obvious Pareto-optimal solutions, using several times the little trick to avoid leaving any plane idle. For instance, it is easy to derive all the Pareto solutions for 6 and 9 passengers -and in the following, the corresponding instances will be termed MultiZeno3, MultiZeno6, and MultiZeno9 respectively (sub-scripted with the type of second objective -cost or risk).

Of course, the number of planes could also be increased, though the number of passengers needs to remain larger than the number of planes to allow for nontrivial Pareto front. However, departing from the 3 passengers to 2 planes ratio would make the Pareto front not easy to identify any more.

Another possibility is to increase the number of central cities: this creates more points on the Pareto front, using either plans in which a single city is used for all passengers, or plans that use several different cities for different passengers (while nevertheless using the same trick to ensure no plane stays idle). In such configuration too the exact Pareto front remains easy to identify: further work will investigate this line of complexification.

Modifying the shape of the Pareto Front

Another way to change the difficulty of the problem without increasing its complexity is to tune the different values of the flight times and the cost/risk at each city. Such changes does not modify the number of points on the Pareto Front, but does change its shape in the objective space. For instance, simply modifying the cost α of city2, the central city in Figure 1, between 1 and 3 (the costs of respectively city1 and city3), the Pareto Front, which is linear for α = 2 becomes strictly convex for α < 2 and strictly concave for α > 2, as can be seen for two extreme cases (α = 1.1 and α = 2.9) on Figure 2. Further work will address the identification of the correct domain parameters in order to reach a given shape of the Pareto front.

Experimental Conditions

Implementation: All proposed multi-objective approaches (see Section 3.2) have been implemented within the ParadisEO-MOEO framework [START_REF] Liefooghe | ParadisEO-MOEO: A framework for evolutionary multi-objective optimization[END_REF]. All experiments were performed on the MultiZeno3, MultiZeno6, and MultiZeno9 instances. The first objective is the makespan, and the second objective either the (additive) cost or the (maximal) risk, as discussed in Section 4. The values of the different flight durations and cost/risks are those given on Figure 1 except otherwise stated.

Parameter tuning: All user-defined parameters have been tuned using the framework ParamILS [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF]. ParamILS handles any parameterized algorithm whose parameters can be discretized. Based on Iterated Local Search (ILS), ParamILS searches through the space of possible parameter configurations, evaluating configurations by running the algorithm to be optimized on a set of benchmark instances, searching for the configuration that yields overall best performance across the benchmark problems. Here, both the parameters of the multi-objective algorithms (including the internal parameters of the variation operators -see [START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF]) and YAHSP specific parameters (including the relative weights of the possible strategies (see Section 3.1) have been subject to ParamILS optimization.

For the purpose of this work, parameters were tuned anew for each instance (see [START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF] for a discussion about the generality of such parameter tuning, that falls beyond the scope of this paper).

Performance Metric: The quality measure used by ParamILS to optimize DaE YAHSP is the unary hypervolume I H - [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] of the set of non-dominated points output by the algorithm with respect to the complete true Pareto front (only instances where the true Pareto front is fully known have been experimented with). The lower the better (a value of 0 indicates that the exact Pareto front has been reached). However, and because the true front is known exactly, and is made of a few scattered points (at most 17 for MultiZeno9 in this paper), it is also possible to visually monitor when each point of the front is discovered by the algorithm. This allows some deeper comparison between algorithms even when none has found the whole front. Such attainment plots will be used in the following, together with more classical plots of hypervolume vs time.

For all experiments, 30 independent runs were performed. Note that all the performance assessment procedures, including the hypervolume calculations, have been achieved using the PISA performance assessment tool suite [START_REF] Bleuler | PISA a platform and programming language independent interface for search algorithms[END_REF].

Stopping Criterion: Because different fitness evaluations involve different number calls to YAHSP -and because YAHSP runs can have different computational costs too, depending on the difficulty of the sub-problem being solvedthe stopping criterion was a fixed amount of CPU time rather than the usual number of fitness evaluation. These absolute limits were set to 300, 600, and 900 seconds respectively for MultiZeno3, MultiZeno6, and MultiZeno9.

Experimental Results

Comparing Multi-Objective Schemes

The first series of experiments presented here are concerned with the comparison of the different multi-objective schemes briefly introduced in Section 3.2. Figure 3 displays a summary of experiments of all 4 variants for MultiZeno instances for both the Cost and Risk problems.

Some clear conclusions can be drawn from these results, that are confirmed by the statistical analyses presented in Table 1 using Wilcoxon signed rank test with 95% confidence level. First, looking at the minimal values of the hypervolume reached by the different algorithms shows that, as expected, the difficulty of the problems increases with the number of passengers, and for a given complexity, the Risk problems are more difficult to solve than the Cost ones. Second, from the plots and the statistical tests, it can be seen that NSGA-II is outperformed by all other variants on all problems, SPEA2 by both indicator-based variants on most instances, and IBEA H -is a clear winner over IBEA ε + except on MultiZeno6 risk . More precisely, Figure 4 show the cumulated final populations of all 30 runs in the objective space together with the true Pareto front for MultiZeno6-9 cost problems: the situation is not as bad as it seemed from Figure 3-(e) for MultiZeno9 cost , as most solutions that are returned by IBEA H -are close to the Pareto front (this is even more true on MultiZeno6 cost problem). A dynamic view of the attainment plots is given in Figure 6-(c

Influence of YAHSP Strategy

Next series of experiments aimed at identifying the influence of the chosen strategy for YAHSP (see Section 3.1). Figure 6-(a) (resp. 6-(b)) shows the attainment plots for the strategy in which YAHSP always optimizes the makespan (resp. the cost) on problem MultiZeno6 cost . Both extreme strategies lead to much worse results than the mixed strategy of Figure 5-(a), as no run discovers the whole front (last line, that never leaves the x-axis). Furthermore, and as could be expected, the makespan-only strategy discovers very rapidly the extreme points of the Pareto front that have a small makespan (points (20,30), (24,28) and (28,26)) and hardly discovers the other end of the Pareto front (points with makespan greater than 48), while it is exactly the opposite for the cost-only strategy. This confirms the need for a strategy that incorporates both approaches. best possible choice.

Note that similar conclusion could have been drawn from ParamILS results on parameter tuning (see Section 5): the choice of YAHSP strategy was one of the parameters tuned by ParamILS . . . and the tuned values for the weights of both strategies were always more or less equal.

Instances Algorithms Algorithms

N SGAII IBEA ε + IBEA H -SP EA2 Zeno3 cost N SGAII - ≡ ≡ ≡ IBEA ε + ≡ - ≡ ≡ IBEA H - ≡ ≡ - ≡ SP EA2 ≡ ≡ ≡ - Zeno3 risk N SGAII - ≡ ≡ ≡ IBEA ε + ≡ - ≡ ≻ IBEA H - ≡ ≡ - ≻ SP EA2 ≡ ≺ ≺ - Zeno6 cost N SGAII - ≺ ≺ ≺ IBEA ε + ≻ - ≡ ≡ IBEA H - ≻ ≡ - ≡ SP EA2 ≻ ≡ ≡ - Zeno6 risk N SGAII - ≺ ≺ ≡ IBEA ε + ≻ - ≻ ≻ IBEA H - ≻ ≺ - ≻ SP EA2 ≡ ≺ ≺ - Zeno9 cost N SGAII - ≺ ≺ ≺ IBEA ε + ≻ - ≺ ≡ IBEA H - ≻ ≻ - ≡ SP EA2 ≻ ≡ ≡ - Zeno9 risk N SGAII - ≺ ≺ ≺ IBEA ε + ≻ - ≺ ≡ IBEA H - ≻ ≻ - ≡ SP EA2 ≻ ≡ ≡ - 0

Shape of the Pareto Front

Figure 7 displays the attainment plots of IBEA H -for both extreme Pareto fronts shown on Figure 2 -while the corresponding plot for the linear case α = 2 is that of Figure 5-(a). Whereas the concave front is fully identified in 40% of the runs (right), the complete front for the strictly convex case (left) is never reached: in the latter case, the 4 most extreme points are found by 90% of the runs in less than 200 seconds, while the central points are hardly ever found. We hypothesize that the handling of YAHSP strategy regarding which objective to optimize (see Section 3.1) has a greater influence in the case of this strictly convex front than when the front is linear (α = 2) or almost linear, even if strictly concave (α = 2.9). In any case, no aggregation technique could ever solve the latter case, whereas it is here solved in 40% of the runs by DaE YAHSP .

Conclusion and Perspectives

The contributions of this paper are twofold. Firstly, MultiZeno, an original benchmark test suite for multi-objective temporal planning, has been detailed, and several levers identified that allow to generate more or less complex instances, that have been confirmed experimentally: increasing the number of passengers obviously makes the problem more difficult; modifying the cost of reaching the cities and the duration of the flights is another way to make the problem harder, though deeper work is required to identify the consequences of each modification. Secondly, several multi-objectivization of DaE X , an efficient evolutionary planner in the single-objective case, have been proposed.

However, even though the hypervolume-based IBEA H -clearly emerged as the best choice, the experimental comparison of those variants on the Multi-Zeno benchmark raises more questions than it brings answers. The sparseness of the Pareto Front has been identified as a possible source for the rather poor performance of all variants for moderately large instances, particularly for the risk type of instances. Some smoothening of the objectives could be beneficial to tackle this issue (e.g., counting for the number of times each risk level is hit rather than simply accounting for the maximal value reached). Another direction of research is to combat the non-symmetry of the results, due to the fact that the embedded planner only optimizes one objective. Further work will investigate a self-adaptive approach to the choice of which objective to give YAHSP to optimize. Finally, the validation of the proposed multi-objective DaE YAHSP can only be complete after a thorough comparison with the existing aggregation approaches -though it is clear that aggregation approaches will not be able to identify the whole Pareto front in case it has some concave parts, whereas the results reported here show that DaE YAHSP can reasonably do it.

Fig. 1 :

 1 Fig. 1: A schematic view of MultiZeno, a simple benchmark transportation problem: Durations of available flights are attached to the corresponding edges, costs/risks are attached to landing in the central cities (in grey circles).

9 Fig. 2 :

 92 Fig. 2: The exact Pareto Fronts for the MultiZeno6 problem for different values of the cost α of city2 (those of city1 and city3 being 3 and 1 respectively).

Fig. 4 :

 4 Fig. 4: Pareto fronts of IBEA H -on MultiZeno instances.

Fig. 5 :

 5 Fig. 5: Attainment plots for IBEA H -on MultiZeno6 instances.

Fig. 6 :

 6 Fig. 6: Attainment plots for two search strategies on MultiZeno6 cost .

Fig. 7 :

 7 Fig. 7: Attainment plots for different Pareto fronts for MultiZeno6 cost .

  ): two points of the Pareto front are more difficult to reach than the others, namely (48,[START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF]) and (56,12). Evolution of the Hypervolume indicator I H -(averaged over 30 runs) on MultiZeno instances (see Table1for statistical significances).

		0.03 0.04						ibeaepsilon ibeahyper nsgaII spea2		0.05 0.04				ibeaepsilon ibeahyper nsgaII spea2
											0.03
		0.02
											0.02
	Hypervolume Indicator (IH-)	0.01								Hypervolume Indicator (IH-)	0.01
											0.001
		0.001
		0	50		100	150	200	250		300	0		50	100	150	200	250	300
						Time (seconds)									Time (seconds)
			(a) MultiZeno3cost						(b) MultiZeno3 risk
		0.15						ibeaepsilon						ibeaepsilon
								ibeahyper						ibeahyper
		0.1						nsgaII spea2						nsgaII spea2
	Hypervolume Indicator (IH-)	0.01 0.02 0.03 0.04 0.05								Hypervolume Indicator (IH-)	0.6 0.3 0.35 0.4 0.45 0.5 0.55
											0.25
											0.2
		0	100		200	300	400	500		600	0.15
						Time (seconds)					0		100	200	300 Time (seconds)	400	500	600
			(c) MultiZeno6cost						(d) MultiZeno6 risk
											4
								ibeaepsilon						ibeaepsilon
								ibeahyper						ibeahyper
								nsgaII						nsgaII
								spea2						spea2
											3.5
	Hypervolume Indicator (IH-)									Hypervolume Indicator (IH-)	2 2.5 3
		0.6									1.5
		0.55
		0.5									1
		0.45									0	100	200	300	400	500	600	700	800	900
		0	100	200	300	400 Time (seconds) 500	600	700	800	900					Time (seconds)
			(e) MultiZeno9cost						(f) MultiZeno9 risk
	Fig. 3:

Table 1 :

 1 Wilcoxon signed rank tests at 95% confidence level (I H -metric).

This work was partially funded by DESCARWIN ANR project (ANR-09-COSI-002).


L Yu

J-P Barbot
email: barbot@ensea.fr

D Benmerzouk
email: dbenmerzouk@yahoo.fr

D Boutat
email: driss.boutat@ensi-bourges.fr

T Floquet

G Zheng
email: gang.zheng@inria.fr

Discussion about sliding mode algorithms, Zeno phenomena and observability

This chapter is devoted to a discussion about the relations between first and high order sliding mode algorithms and both types of Zeno (Chattering and Genuinely) behaviors of switched dynamical systems. Firstly, the Henstock-Kurzweil integral is recalled in order to set up the problem of switched systems with Zeno phenomena, which enables to include Filippov solution and take into account some singularities. Then, observer designs based on the well-known super twisting algorithm are proposed. For this kind of problems, the importance of finite time convergence of the observation error is studied, and some simulations are given to highlight the discussion. Lastly, the two tanks example is given in order to point out the differences between both Zeno phenomena types, to show that there is life after Zeno and that a higher order sliding mode observer can be efficient before, during and after both Zeno phenomena types.

This paper is a partial draft of the chapter in Lecture Notes in Control and Information Sciences, 2012, Volume 412 1 Discussion on Zeno and sliding mode behavior First order sliding mode concept has been well-known in control system theory for at least fifty years, especially since the book of Filippov [START_REF] Filippov | Classical solutions of differential equations with multi-valued right-hand sides[END_REF]. A system exhibiting a first order sliding mode behavior can be seen as a variable structure system converging in finite time towards some constraint manifold and then sliding on this manifold by means of permanent switches at an infinite frequency between two system structures. Commutations at infinite frequency between two subsystems is named as Zeno 1 phenomena in the hybrid dynamical system theory. The relation between first order sliding mode and Zeno phenomena generates a huge set of questions, such as:

1. Is first order sliding mode the only Zeno phenomena? 2. Do all Zeno phenomena always exhibit a sliding mode? 3. Is it possible to use a sliding mode approach in the context of hybrid dynamical systems? 4. Is there life after Zeno? 5. Are specific mathematical tools required?

The answer to the first question is no. In fact, since at least the pioneer works of S. Emelyanov, S. Korovin and A. Levant [START_REF] Emelyanov | Applying the principle of control by deviation to extend the set of possible feedback types[END_REF], [START_REF] Levant | Sliding order and sliding accuracy in sliding mode control[END_REF], a new type of sliding modes has been introduced called higher order sliding modes. This type of sliding mode ensures a finite time convergence onto a constraint manifold defined by the vanishing of some constraint variable s and at least its first derivative ṡ along the system trajectories. The requirement that ṡ must be also equal to zero in finite time has an important consequence on the qualitative behavior of Zeno phenomena. For example, in [START_REF] Perruquetti | Sliding Mode Control in Engineering[END_REF] Chapter 8 page 228, it is proved that the twisting algorithm generates an infinite number of commutation in finite time, where any dwell time 2 is strictly different to zero. Actually, one can distinguish different qualitative behaviors such as the chattering Zeno phenomena and the genuinely Zeno phenomena, see Ames et al. [START_REF] Ames | Is there life after Zeno? Taking executions past the breaking (zeno) point[END_REF]. Roughly speaking, the chattering Zeno phenomena is equivalent to obtain a dwell time equal to zero after a finite number of commutations, as it is exactly the case for first order sliding mode. On the other hand, the genuinely Zeno phenomena corresponds to obtain an infinity of commutation before obtaining a dwell time equal to zero, and this is exactly the case of the twisting algorithm.

The answer to the second question is also no. For instance, consider the bouncing ball example (see [START_REF] Ames | Is there life after Zeno? Taking executions past the breaking (zeno) point[END_REF] and [START_REF] Heymann | Analysis of Zeno behaviours in hybrid systems[END_REF]). This is a switched system with jumps (actually an impact system [6]) that exhibits a Zeno phenomena. This kind of system has only one dynamic and has a jump state at the impact instant before to roll on the floor. It is shown in [START_REF] Ames | Is there life after Zeno? Taking executions past the breaking (zeno) point[END_REF] that the bouncing ball case generates a genuinely Zeno phenomena and that the solution after the Zeno point (impact accumulation point) satisfies a holonomic constraint which is different from the Filippov solution.

The answer to the third question is yes. This will be proved in Section 4 where a sliding mode observer for a particular class of hybrid systems will be designed on the basis of our previous work [START_REF] Yu | Observability Normal Forms for a Class of Switched Systems with Zeno Phenomena[END_REF].

The answer to the fourth question is also yes. In the example of the bouncing ball, even if the model changes after the Zeno time, meaning in some sense that "there is no life of the original model after Zeno", it will be shown that it is not the case for the two tanks example.

The answer to the fifth question is also yes. In fact, in order to consider the most general class of systems, the most general definition of integral has to be considered. To the best of our knowledge, the most general integral definition is the Henstock-Kurzweil-Pettis integral (H-K-P integral). Nevertheless, for the sake of simplicity, this chapter will only deal with the Henstock-Kurzweil integral (H-K integral) [START_REF] Henstock | The General Theory of Integration[END_REF] which is recalled in the Section 3.

Zeno Types

In this chapter, we will consider Hybrid Dynamical Systems belonging to the following class of switched systems without state jump:

   ẋ = f (x) + g (x) q = f (x) + n ∑ i=1 g i (x) q i y = h(x) (1)
where x ∈ U ⊂ R n is the set of admissible continuous state, y ∈ R is the measured output and where the vector fields f : U → R n , g i : U → R n and h : U → R are sufficiently smooth. Moreover q i : R + → Q = {0, 1} is the discrete component of the discrete vector q.

The definition of time trajectory and Zeno phenomenon given in [START_REF] Lygeros | Dynamical Properies of Hybrid Automata[END_REF][START_REF] Goebel | Hybrid systems: generalized solutions and robust stability[END_REF] can be stated as follows: Definition 1. A time trajectory is a finite or infinite sequence of intervals T N = {I i } N i=0 , where N ∈ N, such that:

• I i = [τ i , τ i+1 ], τ i ≤ τ i+1 for all 0 ≤ i ≤ N . • If N is limited, either I N = [τ N , τ N+1 ] with τ N ≤ τ N+1 and τ ∞ bounded or I N = [τ N , τ N+1 [ for τ N ≤ τ N+1 ≤ ∞. • For all i corresponds a discrete transition q i (t) such that q i (t) is constant for t ∈ [τ i , τ i+1 ] . • For all i and t ∈ [τ i , τ i+1 ] corresponds a continuous evolution x(t). Definition 2. A dynamical system is called Zeno if t ∞ := ∞ ∑ i=0 (τ i+1 -τ i ) is bounded.
This means that the system takes an infinite amount of discrete transitions in a finite amount of time, in this case the time t ∞ is called Zeno time. It is known that there exist two fundamental types of Zeno: Definition 3.

• Chattering Zeno: There exist a finite number C ∈ N and a bounded value t ∞ such that:

t ∞ = ∞ ∑ i=0 (τ i+1 -τ i ) and ∀ j > C, [t j+1 -t j ] = 0.
• Genuinely Zeno: There exist C ∈ N and a bounded value t ∞ such that:

t ∞ = ∞ ∑ i=0 (τ i+1 -τ i ) and ∀ j > C, [t j+1 -t j ] > 0.
Consider for example the twisting algorithm [START_REF] Emelyanov | Applying the principle of control by deviation to extend the set of possible feedback types[END_REF][START_REF] Fridman | Higher order sliding modes as the natural phenomenon in control theory[END_REF][START_REF] Levant | Sliding order and sliding accuracy in sliding mode control[END_REF]. It is clear that the convergence on the constrained manifold given by s = ṡ = 0 is due to a Genuinely Zeno phenomenon [START_REF] Perruquetti | Sliding Mode Control in Engineering[END_REF]. Nevertheless, after the finite time convergence on this manifold, the Zeno behavior is a chattering phenomenon. So, for the twisting algorithm the Zeno type changes but the process never leaves the Zeno behavior.

Mathematical recalls of H-K integral

The H-K integral, also known as the gauge integral, the generalized Riemann integral, was defined independently by Henstock and Kurzweil in the 1950's. Let us recall both the definitions related to the Riemann integral and the H-K integral in order to clarify their differences.

τ i ∈ [x i-1 , x i ] ⊂ [a, b], consider f (P) := n ∑ i=1 f (τ i )(x i -x i-1 ).
For any given function δ

: [a, b] → R * + , P is said to be a δ -fine tagged partition of [a, b] if h i := x i -x i-1 < δ (τ i )
where δ is called a gauge for each i.

Definition 2 A number I is called the Riemann integral (respectively the H-

K inte- gral) of f : [a, b] → R if for each constant ε > 0, there exists a constant δ (respec- tively a function δ : [a, b] → R * + ), such that whenever P is a δ -fine tagged partition of [a, b], one has |I -f (P)| < ε.
Roughly speaking, the integral of f on [a, b] is obtained by approximating the region under the curve defined on [a, b] as a union of small rectangles. The Riemann integral requires that all those rectangles depend on a constant δ while the H-K integral uses a more sophisticated δ (δ depends on τ i ). In fact, when a function f oscillates more quickly at some points of the interval [a, b], one has to tighten the step h i at these points in order to approximate more accurately the associated surface. This is possible by choosing h i < δ (τ i ) such that δ (τ i ) is a sufficiently small positive value that depends on the place from where the rectangle of height f (τ i ) is considered (see Fig. 1).

Fig. 1 Illustrative explanation of H-K Gauge

To highlight the principle of the H-K integral, consider the two following examples.

Example 1 Consider the function f defined on [0, 1] as follows:

f (x) = x -1 sin(x -2 ) on ]0, 1] 0 for x = 0.

This function is neither Riemann nor Lebesgue integrable, but H-K integrable, and this can be proved by using a special choice of gauge (that requires skill and effort)

given as follows:

δ (τ) = √ ε if τ = 0 min τ 2 , ετ 4 24 if 0 < τ ≤ 1.
Example 2 Consider the function g defined on [0, 1] as follows:

g(x) = x if x ∈ Q 0 if x / ∈ Q
where Q represents the set of rationales. This function is discontinuous everywhere, and thus it is not Riemann integrable but H-K integrable. It can be proved that its value is equal to 0 by using a special choice of the gauge given by:

δ (τ) = 2 -j-1 ε if τ = p j 1 if τ / ∈ Q
where p 1 , p 2 , . . . , p j , . . . are the rationales.

Thus, taking a more general form of the gauge δ (instead of δ constant) yields a richer class of possible integrands and permits to obtain that:

Riemann integrable functions ⊂ Lebesgue integrable functions ⊂ H-K integrable functions

Note that the H-K integral can also be generalized to bounded or unbounded sets in R n and to more general spaces such as Banach spaces or ordered spaces. The most important feature of the H-K integral is its wider applicability. Moreover, it can avoid abstract notions such as set theory, σ algebras or inner and outer measures. This can be seen from the equivalence:

a set E ⊂ [a, b] is Lebesgue integrable ⇐⇒ its characteristic function is H-K integrable
Moreover, many classical results formulated in the framework of the Lebesgue theory, such as the Lemma of Fatou or the fundamental theorem of calculus, can be simplified (assumptions on continuity for example are omitted when H-K integrability is considered) [START_REF] Henstock | The General Theory of Integration[END_REF].

Another important result is the Hake's Theorem which states that it is not necessary to consider "improper" H-K integral (as it is the case of Riemann integral) because the construction of the H-K integral makes any "improper" H-K integral be a "proper" integral. Note also that other integrals, such as Denjoy integral, Perron integral, Lee and Vyborny integral, all turn out to be "equivalent" to the H-K integral.

Some authors proposed an extension of the H-K integral, called Kurzweil-Henstock-Pettis integral (H-K-P integral) (see [START_REF] Cichon | The Henstock-Kurweil-Pettis integral and exsitence theorems for the Cauchy problem[END_REF]) which offers an interesting possible applicability to Fourier analysis and differential equations. In this case, the solution of a Cauchy problem given by: Ẋ = f (t, X(t)) with X(0) = X 0 is studied as the solution of the following integral equation:

X(t) = X 0 + t 0 f (µ, X(µ))dµ
where the integral is in the sense of H-K. It does not require strong assumptions on the considered system. So it can be seen as a tool that defines more accurately (and take into account) the specific and quick oscillations of the considered dynamics.

Observability and observer design for some classes of Hybrid dynamical system

The following three classes of switched systems without jump are considered.

First basic observability form

The first proposed observability form is:

       ż1 ż2 ż3 . . . żn        =          0 • • • 0 0 0 1 . . . 0 0 0 0 . . . 0 0 0 . . . . . . . . . . . . . . . 0 • • • 0 1 0                 z 1 z 2 z 3 . . . z n        +        fq 0 0 . . . 0        (2)
y = h(z) = z n ( 3
)
where q is the discrete vector and fq is a continuous function with respect to z and parameterized by q. This system is regularly weakly locally observable and the observability is independent from the discrete vector q.

Second basic observability form

The second proposed observability form is:

ż = α 0 (z) + γ q (y), q ∈ Q (4) y = h(z) = z n ( 5
)
where z ∈ R n and y ∈ R

Assumption 1

The pair (α 0 (z), y) is regularly locally weakly observable 3 .

3 In addition to the classical locally weakly observability condition (see [START_REF] Hermann | Nonlinear controllability and observability[END_REF]), the first n -1 derivatives in the rank condition are requested to be regular i.e.

Rank    d h . . . dL n-1 α 0 h    | Z = n

Extended observability form

The following extended observability form includes both previous forms:

   ξ1 . . . ξr-1    =      0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1           ξ 1 . . . ξ r-1 ξ r      (6) η1 = ξr = α 0 (ξ , η) + γ q (ξ ) (7) η = β 0 (ξ , η) + δ q (ξ ) (8)
y = ξ 1 ( 9
)
where

ξ = (ξ 1 • • • ξ r ) T , η = (η 1 , • • • , η n-r+1 ) T and η = (η 2 , • • • , η n-r+1 ) T .

Assumption 2

The pair α 0 (ξ , η) β 0 (ξ , η) , η 1 is uniformly weakly locally observable4 .

In this paper, any consideration on the existence of the diffeomorphisms which transform a switched system into one of these forms is given, nevertheless sufficient conditions may be found in our previous work [START_REF] Yu | Observability Normal Forms for a Class of Switched Systems with Zeno Phenomena[END_REF].

Discussion on the observability of the first basic observability form

For the form (2)-( 3), an estimate of the continuous state ξ can be obtained via an algebraic estimator as defined in [START_REF] Mboup | A revised look at numerical differentiation with an application to nonlinear feedback control[END_REF][START_REF] Mboup | Parameter estimation via differential algebra and operational calculus[END_REF], a sliding mode observer ( [START_REF] Barbot | Sliding mode observer for triangular input form[END_REF][START_REF] Drakunov | Sliding mode observer: Tutorial[END_REF]), or a high order sliding mode observer [START_REF] Davila | Finite-time state observation for non-linear uncertain systems via higher-order sliding modes[END_REF][START_REF] Floquet | Super twisting algorithm-based step-by-step sliding mode observers for nonlinear systems with unknown inputs[END_REF][START_REF] Levant | Robust Extract Differentiation via Sliding mode Technique[END_REF][START_REF] Saadaoui | Exact differentiation and Sliding mode observer for switched Lagrangian systems[END_REF], because y and the n -1 first time derivatives of y provide sufficient information in order to estimate the continuous state.

Discussion on the observability of the second basic observability Form

In the form (4)-( 5), the discrete state q is not considered as an unknown perturbation but as an input, consequently the following assumption is requested:

Assumption 3

The discrete state q is known and γ q (y) is Henstock-Kurzweil-Pettis integrable5 (see [START_REF] Henstock | The General Theory of Integration[END_REF], [START_REF] Cichon | The Henstock-Kurweil-Pettis integral and exsitence theorems for the Cauchy problem[END_REF], [START_REF] Talvila | Estimates of the remainder in Taylor's theorem using the Henstock[END_REF]) or NV-Integrable [START_REF] Fogio | The NV-Integrals[END_REF].

Clearly, this assumption can not be satisfied in the case of Zeno phenomena, such as for the Chattering Zeno (i.e. after some time the dwell time is exactly equal to zero) or for the Genuinely Zeno (i.e. the dwell time is never equal to zero) [START_REF] Ames | Is there life after Zeno? Taking executions past the breaking (zeno) point[END_REF]. So, in practice, it is only possible to obtain the filtered discrete state q f , instead of the real discrete state q. Consequently, Assumption 3 is replaced by the following one: Assumption 4

• a-The system ( 4)-( 5) is affine with respect to the discrete state q, i.e. γ q (y) = γ(y)q, where γ is at least a C 1 function of y. • b-The functions γ(y)q and γ(y)q f are Henstock-Kurzweil-Pettis integrable and the mean value q f is measured via a low pass filter with a large enough bandwidth on the time interval [0, α].

Moreover, consider the following system: [START_REF] Diop | On nonlinear observability[END_REF] and assume that:

ż = α 0 (z) (10) y = h(z) = z n
Assumption 5 For the system ( 10)-( 11), there exists an observer such that the continuous state observation error (i.e. the difference between the continuous state ant its estimate) is exponentially stable.

Remark 1 Under some specific assumptions such as Lipschitz condition or persistent excitation, it is possible to design classical high gain observers [START_REF] Besanc ¸on | High-Gain Observer based State and Parameter Estimation in Nonlinear System[END_REF] or adaptive observers [START_REF] Busawon | An observer design for uniformly observable nonlinear systems[END_REF]. Without the perturbation term, those observers can guarantee the exponential stability of the continuous state observation error.

Then, it is possible to set the following proposition:

Proposition 1

•A) Under Assumptions 1, 3 and 5, system (4)-( 5) with Zeno phenomenon is observable6 .

•B) Under Assumptions 1, 4 and 5, system (4)-( 5) with Zeno phenomenon is practically observable 7 .

Proof. Proof of part A: there exists an observer of the form: ż = β (ẑ, y, ŷ) (12) ŷ = ẑn [START_REF] Emelyanov | Applying the principle of control by deviation to extend the set of possible feedback types[END_REF] which ensures the exponential stability of the continuous state observation error e = zẑ for system [START_REF] Fogio | The NV-Integrals[END_REF], [START_REF] Diop | On nonlinear observability[END_REF]. Consequently, there exists a Lyapunov function V (e) with respect to (10), ( 11) and ( 12), ( 13) such that:

V = ∂V ∂ e (α 0 (z) -β (ẑ, y, ŷ)) < -KV (14)
with K > 0. Modifying ( 12), ( 13) as follows: ż = β (ẑ, y, ŷ) + γ q f (y) with γ q f (y) = γ(y)q f (15) ŷ = z n [START_REF] Floquet | Super twisting algorithm-based step-by-step sliding mode observers for nonlinear systems with unknown inputs[END_REF] the state observation error for system (4)-( 5) and observer ( 15)-( 16) is exponentially stable. Using the previous Lyapunov function, one has:

V = ∂V ∂ e (α 0 (z) -β (ẑ, y, ŷ) + γ q (y) -γ q f (y)) < -K ′ V
where

K ′ = K + sup t∈[0,α] {|o(y(t))|}.
Proof of part B: the observation error for systems (4)-( 5) and ( 15)-( 16) becomes:

ė = α 0 (z) -β (ẑ, y, ŷ) + γ(y)(q -q f )
From condition b) of Assumption 4, one obtains that ṗ = γ(y)p with p = qq f is a Cauchy problem for each fixed initial value p 0 in the sense of Henstock-Kurzweil-Pettis integrals.

Using the same method as Filippov in [START_REF] Filippov | Differential Equations with Discontinuous Righthand sides[END_REF] page 17 and setting ε = ep, one has:

ε = α 0 (z) -β (ẑ, y, ŷ) (17)
which admits a local solution in the Carathéodory sense for t ∈ [0,Γ ] ⊂ [0, α]. Moreover, Assumption 5 and the observer ( 12)-( 13) ensure that there exists a Lyapunov function V (e) for ( 10)- [START_REF] Diop | On nonlinear observability[END_REF] which satisfies [START_REF] Filippov | Classical solutions of differential equations with multi-valued right-hand sides[END_REF]. Consequently, derivation of V (ε) with respect to [START_REF] Fridman | Higher order sliding modes as the natural phenomenon in control theory[END_REF] gives:

V = ∂V ∂ ε (α 0 (z) -β (ẑ, y, ŷ)) ( 18
)
Since ε = ep, one has ∂V ∂ ε | ε = ∂V ∂ e | ε and from Assumption 5, it is possible to rewrite [START_REF] Henstock | The General Theory of Integration[END_REF] as follows:

V = ∂V ∂ e | e (α 0 (z) -β (ẑ, y, ŷ)) - 1 2 ∂ 2 V ∂ e 2 | e [O(p) ⊗ (α 0 (z) -β (ẑ, y, ŷ))] + O(p 2 )
with lim p→0 O(p) = 0. As for all ε > 0, there exists a filter and t 1 ≥ 0 such that ∀t > t 1 , we have

p = sup 0≤t≤Γ t t 1 γ(y(σ ))(q(σ ) -q f (σ )) dσ | < ε one obtains V (ε) ≤ -K ′ V (ε) + 1 2 ∂ 2 V ∂ e 2 | e [O(p) ⊗ (α 0 (z) -β (ẑ, y, ŷ))] + |O(||p|| 2 )| (19)
Consequently, it is possible, for each

V d > 0, to set ε << V d 2 and the inequality (19) becomes V (ε) ≤ -K ′ V (ε) + |O(ε)| So, one can conclude that for e / ∈ E V d := {e : V (e) < V d }, one has: V (ε) ≤ - K ′′ 2 V (ε) for some K ′′ > 0 because ε << V d 2 guarantees that |O(ε)| < V d 2 .

Observability for the extended observability Form

For system (6)-( 9), according to the previous discussion on the observability for the two basic forms, one can easily conclude:

Corollary 1

Under Assumptions 2, 4 and 5, the system ( 6)-( 9) with Zeno phenomenon is practically observable.

Consequently, it is possible to design an hybrid observer for this system: for the observation of ξ , a step-by-step high order sliding mode observer can be designed to obtain a finite time estimate of ξ . So, after the convergence of ξ , ξ r (or η 1 ) can be considered as an output, and one can design an asymptotic observer (for example a high gain observer) to estimate η, as shown in Figure 2. Example 3 Consider the following system:

       ż1 = z 2 ż2 = z 3 -z 3 2 + 3 2 z 2 + 1 2 γ q (z 2 ) ż3 = -z 2 y = z 1 (20)
with γ q (z 2 ) = sign(w) • z 2 , where w is a high frequency noise. This form of q theoret- ically leads to a Zeno phenomena. For this example, one can follow the scheme shown in Fig. 2 to build an hybrid observer. First, one considers the states z 1 and z 2 , where z 1 is known and z 2 is observed through a sliding mode observer. Denote ẑ2 as the observation of z 2 . Then the remaining state dynamics has the following form: where the value of z 2 is taken as the output of the subsystem [START_REF] Johansson | Simulation of zeno hybrid automata[END_REF], i.e. y ′ = ẑ2 . One can observe the state z 3 using a high gain observer. The performances are shown in Fig. 3 and4, where Fig. 3 shows the state z 2 and the observed state ẑ2 and where Fig. 4 depicts the same for z 3 . In fact, the high gain observer (with ẑ2 as output and z 2 , z 3 as states) must be switched on only after the convergence of the finite time sliding mode observer (with z 1 as output and z 1 , z 2 as states). Hence one can assign ẑ3 to be zero at the beginning of the observation procedure.

   ż2 = z 3 -z 3 2 + 3 2 z 2 + 1 2 γ q (z 2 ) ż3 = -z 2 y ′ = z 2

The two tanks example

consider the two water tanks example [START_REF] Johansson | Simulation of zeno hybrid automata[END_REF] in Fig. 5, which is a typical switched system where Zeno behavior may exist if the commutation of the water distribution between both tanks is considered instantaneous with respect to the other dynamics.

The simplified model of the two water tanks system described in Fig. 5 is given by:

ḣ1 ḣ2 = v -v 1 -v 2 + -v v q
where h 1 , h 2 are the water levels for each tanks, v 1 , v 2 are the flows of water out of the tanks, v is a constant input flow of water which goes through a pipe and into either tank at any particular time point, and q is the switching state of the pipe which is determined by the transient conditions (see Fig. 6 and Fig. 7 for two different cases). By considering Torricelli's law, one has v 1 = √ 2gh 1 and v 2 = √ 2gh 2 , where g is the gravity. Then the dynamic can be rewritten as

ḣ1 ḣ2 = v - √ 2gh 1 - √ 2gh 2 + -v v q (21)
Assume that the only measured signal is y = h 1 + h 2 (v and q are supposed to be unknown). Then the system is regularly locally weakly observable:

rank dy d ẏ = rank 1 1 -1 √ 2gh 1 -1 √ 2gh 2 = 2 (22)
excepted on the set

S O S O = {(h 1 , h 2 ) T : h 1 = h 2 }.
This set is a set of observability singularities and it is a manifold of dimension n -1 = 1. Moreover, S O separates the state space in two parts. It is important to note that S O characterizes the singularity observability considering only y and ẏ. However, there exist several different observability definitions for nonlinear systems and hybrid systems [START_REF] Boutat | About the observability of piecewise dyamical system[END_REF], [START_REF] Diop | On nonlinear observability[END_REF], [START_REF] Heymann | Analysis of Zeno behaviours in hybrid systems[END_REF], [START_REF] Kang | On the observability of nonlinear and switched system[END_REF], [START_REF] Leonov | Dynamics and Control of Hybrid Mecanical Systems[END_REF], involving high order output derivatives with order greater than the dimension of the state space. Moreover, the system satisfies the observability matching condition [START_REF] Perruquetti | Sliding Mode Control in Engineering[END_REF] 8

∂ y ∂ q = ∂ ẏ ∂ q = 0 (23)
Conditions ( 22) and ( 23) are necessary and sufficient conditions for the existence of a diffeomorphism which transforms, at least locally, the system (21) into the first basic normal form. Then, under the diffeomorphism

ξ = φ (h 1 , h 2 ) with φ 1 (h 1 , h 2 ) = h 1 + h 2 and φ 2 (h 1 , h 2 ) = v - √ 2gh 1 - √ 2gh 2
, the system is locally transformed into the first basic normal form (2)-( 3):

ξ1 = ξ 2 (24) ξ2 = - g 2 (v - √ 2gh 1 -vq) √ h 1 + (vq - √ 2gh 2 ) √ h 2 y = ξ 1 where h 1 = 1 4   v -ξ 2 √ 2g + µ 2ξ 1 - (v -ξ 2 ) 2 2g   2 , h 2 = 1 4   v -ξ 2 √ 2g -µ 2ξ 1 - (v -ξ 2 ) 2 2g   2 .
Using this state transformation, one has to choose either the trajectories are in the subspaces

S + O = {(h 1 , h 2 ) : h 1 > h 2 } or S - O = {(h 1 , h 2 ) : h 1 < h 2 }
, where S O is the boundary between both of them. Thus, µ = 1 if the state is in S + O and µ = -1 if the state is in S - O . In both cases given in Fig. 6 and Fig. 7, the system behavior is principally or exclusively in the subspace h 1 > h 2 . Then the appropriate change of coordinates is µ = 1. This highlights the fact that the diffeomorphism is only a local 8 Considering a system of the following form:

ẋ = f (x) + g(x)q y = h(x)
the observability matching condition with respect to q is satisfied if L g h = ... = L n-2 g h = 0 transformation and in this case the validity domains are strongly related to S O .

Regarding the particular properties of the hybrid dynamical system (observability matching condition and regularly locally weakly observability) and taking advantage of the basic normal form (24), a higher order sliding mode observer [START_REF] Davila | Finite-time state observation for non-linear uncertain systems via higher-order sliding modes[END_REF][START_REF] Floquet | Super twisting algorithm-based step-by-step sliding mode observers for nonlinear systems with unknown inputs[END_REF][START_REF] Levant | Robust Extract Differentiation via Sliding mode Technique[END_REF] only made here of one super twisting algorithm step because the knowledge of the discrete state q is not required. The proposed observer is the following:

ξ1 = ξ2 + λ |y -ξ1 | 1 2 sign(y -ξ1 ) ξ2 = αsign(y -ξ1 ) (25)
ŷ = ξ1

Setting e 1 = ξ 1 -ξ1 and e 2 = ξ 2 -ξ2 , the observation error dynamics is:

ė1 = e 2 -λ |e 1 | 1 2 sign(e 1 ) ė2 = ξ2 -αsign(e 1 ) (26)
which is stable for appropriate values of α and λ [START_REF] Levant | Robust Extract Differentiation via Sliding mode Technique[END_REF][START_REF] Saadaoui | Exact differentiation and Sliding mode observer for switched Lagrangian systems[END_REF]. In the given simulations, λ = 5, α = 40 and a computation step equal to 10 -5 s is used with the solver ode5 of Matlab. Case 1 (Fig. 6) exhibits a chattering Zeno phenomena (I min = 0 when the state behavior reaches the sliding manifold h 1 = 2h 2 approximatively at time t = 0.2s) and the system slides on the switching manifold until h 1 ≃ 2.5 and h 2 ≃ 1.25 (see the green trajectory in Fig. 8 and Fig 9). Note that the Zeno time t ∞ in this case is not unique, because during all the period the system slides on the switching manifold, there is an infinite number of commutations in every small time interval. The fact that the Zeno behavior is not restricted to a particular time instant t ∞ , but appears during a finite or infinite time interval is characteristic of a sliding mode behavior.

Here, when the system has reached the switched manifold given by h 1 = 2h 2 , the system never leaves the constrained manifold (it is an invariant one).

The system behavior (in green) and the observer behavior (in red) are given in Fig. 8 and Fig. 9 for an appropriate choice of coordinate and a wrong choice of coordinate, respectively. The observation errors in original coordinates are given in Fig 10 . As the original behavior does not cross S O (in blue in Fig. 8 and Fig. 9), the observer (25) converges and it is not at all influenced by the Zeno behavior of the observed system (even if it is a chattering Zeno which slides on the switching manifold). Case 2 (Fig. 7) exhibits a genuinely Zeno phenomena. Roughly speaking, the system switches more and more quickly and infinitely until the time t ∞ ≃ 1.6 which corresponds to the time when the state is equal to the desired one (h 1 = 4 and h 2 = 1.5).

After that, there is still life [START_REF] Ames | Is there life after Zeno? Taking executions past the breaking (zeno) point[END_REF] (see the green trajectory in Fig. 12). The system trajectories in the phase plane are given in Fig. 11 and Fig. 12 with an appropriate and a wrong choice of coordinate, respectively. Life after Zeno is due to the fact that the input v is strictly smaller than v 1 + v 2 (the desired point is semi attractive, in fact the state behavior reaches (h 1 = 4, h 2 = 1.5) only if the initial conditions verify h 1 + h 2 ≫ 5.5). Since the original system trajectory (in green) crosses the observability singularity set S O , the observer trajectory diverges when the trajectory is in the opposite subspace. Moreover, when the system trajectory is close to the observability singularity set S O , the observation errors increase even if the coordinates choice is correct. The observation errors in the canonical coordinates ξ are given in Fig. 13 (e 1 = ξ 1 -ξ1 in blue and e 2 = ξ1 -ξ1 in red). The observation errors are shown only dur- ing the first second, because the higher order sliding mode observer [START_REF] Leonov | Dynamics and Control of Hybrid Mecanical Systems[END_REF] converges in a finite time ≃ 0.1s and is not substantially perturbed by the S O crossing or by the Zeno behavior of the original system. The observation errors in the original coordinates (h 1 , h 2 ) are given in Fig. 14 and it is clear, for such coordinates, that the error dynamics are strongly influenced by the crossing of S O . The Zeno time is t ∞ ≃ 1.6s (when h 1 = 4 and h 2 = 1.5). Then, the system converges to a limit cycle and the observer works well in both coordinates (original coordinates with appropriate choice and canonical coordinates) because the limit cycle does not cross S O .

Definition 1

 1 Consider a real function f defined on an interval [a, b] ⊂ R. For any tagged partition P of [a, b] such as a = x 0 < x 1 < x 2 < • • • < x n = b, and

Fig. 2

 2 Fig. 2 Hybrid observer scheme.

Fig. 3

 3 Fig.3Results of Observer for system (20) for z 2 .

Fig. 4

 4 Fig.[START_REF] Besanc ¸on | High-Gain Observer based State and Parameter Estimation in Nonlinear System[END_REF] Results of Observer for system (20) for z 3 .

Fig. 5 Fig. 6

 56 Fig. 5 Two water tanks system

Fig. 7

 7 Fig.[START_REF] Busawon | An observer design for uniformly observable nonlinear systems[END_REF] The transient of discrete state for the case 2 (h 1 = 4 and h 2 = 1.5).

Fig. 8

 8 Fig.8The phase plane with an appropriate choice of coordinate.

Fig. 9

 9 Fig.9he phase plane with a wrong choice of coordinate.

Fig. 10

 10 Fig.[START_REF] Fogio | The NV-Integrals[END_REF] The observation errors in the original coordinates.

Fig. 11

 11 Fig.11The phase plane with an appropriate choice of coordinate.

Fig. 12 Fig. 13

 1213 Fig.[START_REF] Drakunov | Sliding mode observer: Tutorial[END_REF] The phase plane with a wrong choice of coordinate.

Fig. 14

 14 Fig.[START_REF] Filippov | Classical solutions of differential equations with multi-valued right-hand sides[END_REF] The observation error in the original coordinates.

This refers to Zeno of Elea and its paradoxes, see for example "Achille and the tortoise"

uniformly with respect to ξ .

see also Denjoy-Khinchine integrable.

The observation error can be assigned to zero

The observation error can be constrained to lie within any measurable vicinity of zero but not zero.