Mostepha Redouane Khouadjia
email: mostepha-redouane.khouadjia@inria.fr

Marc Schoenauer
email: marc.schoenauer@inria.fr

Vincent Vidal
email: vincent.vidal@onera.fr

Johann Dréo
email: johann.dreo@thalesgroup.com

Pierre Savéant
email: pierre.saveant@thalesgroup.com

Quality Measures of Parameter Tuning for Aggregated Multi-Objective Temporal Planning

come   L'archive ouverte pluridisciplinaire

Introduction

Parameter tuning is now well recognized as a mandatory step when attempting to solve a given set of instance of some optimization problem. All optimization algorithms behave very differently on a given problem, depending on their parameter values, and setting the algorithm parameters to the correct value can make the difference between failure and success. This is equally true for deterministic complete algorithms [START_REF] Hutter | Automated configuration of mixed integer programming solvers[END_REF] and for stochastic approximate algorithms [START_REF] Eiben | Parameter Control in Evolutionary Algorithms[END_REF][START_REF] Zhi | Modern continuous optimization algorithms for tuning real and integer algorithm parameters[END_REF]. Current approaches range from methods issued from racing-like methods [START_REF] Birattari | Automated algorithm tuning using F-Races: Recent developments[END_REF][START_REF] Dubois-Lacoste | Automatic configuration of state-of-the-art multi-objective optimizers using the TP+PLS framework[END_REF] to meta-optimization, using Gaussian Processes [START_REF] Bartz-Beielstein | Sequential parameter optimization[END_REF], Evolutionary Algorithms [START_REF] Nannen | Relevance estimation and value calibration of evolutionary algorithm parameters[END_REF] or Iterated Local Search [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF]. All these methods repeatedly call the target algorithm and record their performance on the given problem instances.

Quality criteria for parameter sets usually involve the solution quality of the target algorithm and the time complexity of the algorithm, and, in the case of a set of problem instances, statistics of these quantities over the whole set. The present work is concerned with the case of instance-based parameter tuning (i.e. a single instance is considered), and the only goal is the quality of the final solution, for a fixed computational budget. In this context, the objective of the meta-optimizer is generally also directly based on the quality of the solution.

However, things are different in the context of multi-objective optimization, when using an aggregation method, i.e. optimizing several linear combinations of the objectives, gathering all results into one single set, and returning the nondominated solutions within this set as an approximation of the Pareto front. Indeed, the objective of each single-objective run is the weighted sum of the problem objectives, and using this weighted sum as the objective for parameter tuning seems to be the most straightforward approach. However, the objective of the whole algorithm is to approximate the Pareto front of the multi-objective problem. And the hypervolume indicator [START_REF] Zitzler | Performance assessment of multiobjective optimizers: an analysis and review[END_REF] has been proved to capture into a single real value the quality of a set as an approximation of the Pareto front. Hence an alternative strategy could be to tune each single-objective run so as to optimize the hypervolume of its final population, as a by-product of optimizing the weighted sum of the problem objectives. This paper presents a case study of the comparison of both parameter-tuning approaches described above for the aggregated multi-objective approach, in the domain of AI planning [START_REF] Ghallab | Automated Planning, Theory and Practice[END_REF]. This domain is rapidly introduced in Section 2. In particular, MultiZeno, a tunable multi-objective temporal planning benchmark inspired by the well-known zeno IPC logistic domain benchmark, is described in detail. Section 3 introduces Divide-and-Evolve (DaE YAHSP ), a single-objective evolutionary AI planning algorithm that has obtained state-of-the-art results on different planning benchmark problems [START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF], and won the deterministic temporal satisficing track at IPC 2011 competition 4 . Section 4 details the experimental conditions of the forthcoming experiments, introduces the parameters to be optimized, the aggregation method, the meta-optimizer ParamILS, the parameter tuning method that has been chosen here [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF], and precisely defines the two quality measures to be used by ParamILS in the experiments: either the best fitness or the global hypervolume of its final population. Section 5 details the experimental results obtained by DaE YAHSP for solving MultiZeno instances using these two quality measures. The values of the parameters resulting from the ParamILS runs are discussed, and the quality of the approximations of the Pareto front given by both approaches are compared, and the differences analyzed.

AI Planning

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 is a sequence of actions, and a feasible plan is a plan such that executing each action in turn from the initial state puts the systems into the goal state. The goal of (single objective) AI Planning is to find a feasible plan that minimizes some quantity related to the actions: number of actions for STRIPS problems, 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 (inspired by the wellknown Zeno problem of IPC series) 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 series of yearly conferences (http://icaps-conferences.org), and its biannual competition 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.

Multi-Objective AI Planning

Most existing work in AI Planning involves one single objective, even though real-world problems are generally multi-objective (e.g., optimizing the makespan while minimizing the cost, two contradictory objectives). An obvious approach to Multi-Objective AI planning is to aggregate the different objectives into a single objective, generally a fixed linear combination (weighted sum) of all objectives. The single objective is to be minimized, and the weights have to be positive (resp. negative) for the objectives to be minimized (resp. maximized) in the original problem. The solution of one aggregated problem is Pareto optimal if all weights are non-zero, or the solution is unique [START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF]. It is also well-known that whatever the weights, the optimal solution of an aggregated problem is always on the convex parts of the Pareto front. However, some adaptive techniques of the aggregation approach have been proposed, that partially address this drawback [START_REF] Jin | Adapting weighted aggregation for multiobjective evolution strategies[END_REF] and are able to identify the whole Pareto front by maintaining an archive of non-dominated solutions ever encountered during the search. Despite the fact that pure multi-objective approaches like e.g., dominancebased approaches, are able to generate a diverse set of Pareto optimal solutions, which is a serious advantage, aggregation approaches are worth investigating, as they can be implemented seamlessly from almost any single-objective algorithm, and rapidly provide at least part of the Pareto front at a low man-power cost.

This explains why all works in multi-objective AI Planning used objective aggregation, to the best of our knowlege 5 . Early works 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 [START_REF] Gerevini | Preferences and Soft Constraints in PDDL3[END_REF], 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 a too small number of entries.

Tunable Benchmarks for Multi-Objective Temporal Planning

For the sake of understandability, it is important to be able to experiment with instances of tunable complexity for which the exact Pareto fronts are easy to determine, and this is the reason for the design of the MultiZeno benchmark family. The reader will have by now solved the little puzzle illustrated in Figure 1, and found the solution with makespan 8, whose rationale is that no plane ever stays idle. In order to turn this problem into a not-too-unrealistic logistics multi-objective problem, some costs are added to all 3 central cities (1 to 3). This leads to the MultiZeno Cost problems, where the second objective is additive: each plane has to pay the corresponding tax every time it lands in that city 6 .

In the simplest instance, MultiZeno3, involving 3 passengers only, there are 3 obvious points that belong to the Pareto Front, using the small trick described above, and going respectively through city1, city 2 or city 3. 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. However, different cities can be used for the different passengers, leading to a Pareto Front made of 5 points, adding points [START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF][START_REF] Ghallab | Automated Planning, Theory and Practice[END_REF] and [START_REF] Chen | Temporal Planning using Subgoal Partitioning and Resolution in SGPlan[END_REF][START_REF] Bartz-Beielstein | Sequential parameter optimization[END_REF] to the obvious points [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF][START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF], [START_REF] Do | SAPA: A Multi-Objective Metric Temporal Planner[END_REF][START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF], and [START_REF] Haslum | Admissible Heuristics for Optimal Planning[END_REF][START_REF] Birattari | Automated algorithm tuning using F-Races: Recent developments[END_REF]. There are several ways to make this first simple instance more or less complex, by adding passengers, planes and central cities, and by tuning the different values of the makespans and costs. In the present work, only additional bunches of 3 passengers have been considered, in order to be able to easily derive some obvious Pareto-optimal solutions as above, using several times the little trick to avoid leaving any plane idle. This lead to the MultiZeno6, and MultiZeno9 instances, with respectively 6 and 9 passengers. The Pareto front of MultiZeno6 on domain described by Figure 1 can be seen on Figure 2-b. The other direction for complexification that has been investigated in the present work is based on the modification of the cost value for city 2, leading to different shapes of the Pareto front, as can be seen on Figure 2-a and 2-c. Further work will investigate other directions of complexification of this very rich benchmark test suite.

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 rest of this section will briefly recall the evolutionary parts of DaE X .

Representation, Initialization, and Variation Operators

Representation An individual in DaE X is 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 (instantiated predicates). Initialization 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], and an individual in DaE X is represented by a variable-length time-consistent sequence of partial states, and each partial state is a variable-length list of atoms that are not pairwise mutually exclusive (aka mutex), according to the partial mutex relation computed by the embedded planner. Crossover and mutation operators: are applied with respective user-defined probabilities Proba-cross and Proba-mut. They are defined on the DaE X representation in a straightforward manner -though constrained by the heuristic chronology and the partial mutex relation between atoms. One-point crossover is adapted to variable-length representation: both crossover points are independently chosen, uniformly in both parents. Only one offspring is kept, the one that respects the approximate chronological constraint on the successive states. Four mutation operators are included, and operate either at the individual level, by adding (addGoal) or removing (delGoal) an intermediate state, or at the state level by adding (addAtom) or removing (delAtom) some atoms in a uniformly chosen state. The choice among these mutations is made according to user-defined relative weights, named w-MutationName -see Table 1.

Hybridization and Multi-Objectivization

DaE X uses an external embedded planner to solve in turn the sequence of subproblems 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 a very large number of calls to this embedded planner are necessary for a single fitness evaluation, a sub-optimal but fast planner was found to be the best choice: YAHSP [START_REF] Vidal | A Lookahead Strategy for Heuristic Search Planning[END_REF] 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. 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).

However, even though YAHSP, like all known planners to-date, is a singleobjective planner, it is nevertheless possible since PDDL 3.0 to add in a PDDL domain file 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. Two strategies are then possible for YAHSP in the two-objective context of MultiZeno: it can optimize either the makespan or the cost, and simply compute the other quantity (cost or makespan) along the solution plan. The corresponding strategie will be referred to as YAHSP makespan and YAHSP cost .

In the multi-objective versions of DaE YAHSP the choice between both strategies is governed by user-defined weights, named respectively W-makespan and W-cost (see table 1). For each individual, the actual strategy is randomly chosen according to those weights, and applied to all subproblems of the individual.

Experimental Conditions

The aggregation method for multi-objective optimization runs in turn a series of single-objective problems. The fitness of each of these problems is defined using a single positive parameter α. In the following, F α will denote α * makespan+(1α) * cost, and DaE YAHSP run optimizing F α will be called the α-run. Because the range of the makespan values is approximately twice as large as that of the cost, the following values of α have been used instead of regularly spaced values: 0, 0.05, 0.1, 0.3, 0.5, 0.55, 0.7, 1.0. One "run" of the aggregation method thus amounts to running the corresponding eight α-runs, and returns as the approximation of the Pareto front the set of non-dominated solutions among the merge of the eight final populations. ParamILS [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF] is used to tune the parameters of DaE YAHSP . ParamILS uses the simple Iterated Local Search heuristic [START_REF] Lourenço | Iterated Local Search[END_REF] to optimize parameter configurations, and can be applied to any parameterized algorithm whose parameters can be discretized. ParamILS repeats local search loops from different random starting points, and during each local search loops, modifies one parameter at a time, runs the target algorithm with the new configuration and computes the quality measure it aims at optimizing, accepting the new configuration if it improves the quality measure over the current one.

The most prominent parameters of DaE YAHSP that have been subject to optimization can be seen in Table 1. Quality Measures for ParamILS: The goal of the experiments presented here is to compare the influence of two quality measures of ParamILS for the aggregated DaE YAHSP on MultiZeno instances. In Aggreg F itness , the quality measure used by ParamILS to tune the α-run of DaE YAHSP is F α , the fitness also used by the target α-run. In Aggreg Hyper , ParamILS uses, for each of the α-run, the same quality measure, i.e., the unary hypervolume [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] of the final population of the α-run w.r.t. the exact Pareto front of the problem at hand (or its best available approximation when it is not available). The lower the better (a value of 0 indicates that the exact Pareto front has been reached). Implementation: Algorithms have been implemented within the ParadisEO-MOEO framework 7 . All experiments were performed on the MultiZeno3, MultiZeno6, and MultiZeno9 instances. The first objective is the makespan, and the second objective is the cost. The values of the different flight durations (makespans) and costs are those given on Figure 1 except otherwise stated. Performance Assessment and Stopping Criterion For all experiments, 11 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 8 . The main quality measure used here to compare Pareto Fronts is, as above, 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 algorithms with respect to the complete true Pareto front. For aggregated runs, the union of all final populations of the α-runs for the different values of α is considered the output of the complete 'run'. 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, for each point of the front, the ratio of actual runs (out of 11) that discovered it at any given time. This allows some other point of view on the comparison between algorithms, even when none has found the whole Pareto front. Such hitting plots will be used in the following, together with more classical plots of hypervolume vs computational effort. In any case, Finally, 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 solved -the computational efforts will be measured in terms of CPU time and not number of function evaluations -and that goes for the stopping criterion: The absolute limits in terms of computational efforts were set to 300, 600, and 1800 seconds respectively for MultiZeno3, MultiZeno6, and MultiZeno9. The stopping criterion for ParamILS was likewise set to a fixed wall-clock time: 48h (resp. 72h) for MultiZeno3 and 6 (resp. MultiZeno9), corresponding to 576, 288, and 144 parameter configuration evaluations per value of α for MultiZeno3, 6 and 9 respectively.

Experimental Results

ParamILS Results

Table 2 presents the optimal values for DaE YAHSP parameters of Table 1 found by ParamILS in both experiments, for all values of α -as well as for the multiobjective version of DaE YAHSP presented in [START_REF] Khouadjia | Multi-objective AI planning: Evaluating DAEYAHSP on a tunable benchmark[END_REF] (last column, entitled IBEA H ).

The most striking and clear conclusion regards the weights for the choice of YAHSP strategy (see Section 3.2) W-makespan and W-cost. Indeed, for the Aggreg Hyper approach, ParamILS found out that YAHSP should optimize only the makespan (W-cost = 0) for small values of α, and only the cost for large values of α while the exact opposite is true for the Aggreg F itness approach. Remember that small (resp. large) values of α correspond to an aggregated fitness having all its weight on the cost (resp. the makespan). Hence, during the 0-or 0.5-runs, the fitness of the corresponding α-run is pulling toward minimizing the cost: but for the Aggreg Hyper approach, the best choice for YAHSP strategy, as identified by ParamILS, is to minimize the makespan (i.e., setting W-cost to 0): as a result, the population has a better chance to remain diverse, and Fig. 3: Evolution of the Hypervolume for both approaches, for all α-runs and overall, on MultiZeno instances. Warning: Hypervolume is in log scale, and the X-axis is not the value 0, but 6.7 10 -5 for MultiZeno6 and 0.0125 for MultiZeno9.

hence to optimize the hypervolume, i.e., ParamILS quality measure. In the same situation ( small α), on the opposite, for Aggreg F itness , ParamILS has identified that the best strategy for YAHSP is to also favor the minimization of the cost, setting W-makespan to zero. The symmetrical reasoning can be applied to the case of large values of α. For the multi-objective version of DaE YAHSP (IBEA column in Table 2), the best strategy that ParamILS came up with is a perfect balance between both strategies, setting both weights to 1.

The values returned by ParamILS for the other parameters are more difficult to interpret. It seems that large values of Proba-mut are preferable for Aggreg Hyper for α set to 0 or 1, i.e. when the DaE YAHSP explores the extreme sides of the objective space -more mutation is needed to depart from the boundary of the objective space and cover more of its volume. Another tendancy is that ParamILS repeatedly found higher values of Proba-cross and lower values of Proba-mut for Aggreg Hyper than for Aggreg F itness . Together with large population sizes (compared to the one for IBEA for instance), the 1-point crossover of DaE YAHSP remains exploratory for a long time, and leads to viable individuals that can remain in the population even though they don't optimize the α-fitness, thus contributing to the hypervolume. On the opposite, large mutation rate is preferable for Aggreg F itness as it increases the chances to hit a better fitness, and otherwise generates likely non-viable individuals that will be quickly eliminated by selection, making DaE YAHSP closer from a local search. The values found for IBEA, on the other hand, are rather small -but the small population size also has to be considered here: because it aims at exploring the whole objective space in one go, the most efficient strategy for IBEA is to make more but smaller steps, in all possible directions.

Comparative Results

Figure 3 represents the evolution during the course of the runs of the hypervolumes (averaged over the 11 independent runs) of some of the (single-objective) α-runs, for both methods together (labelled α hyp or α f it ), as well as the evolution of the overall hypervolume, i.e., the hypervolume covered by the union of all populations of the different α-runs as a function of CPU time. Only the results on MultiZeno6 and MultiZeno9 are presented here, but rather similar behaviors can be observed for the two approaches on these two instances, and similar results were obtained on MultiZeno3, though less significantly different.

First of all, Aggreg Hyper appears as a clear winer against Aggreg F itness , as confirmed by the Wilcoxon test with 95% confidence: On both instances, the two lowest lines are the results of the overall hypervolume for, from bottom to top, Aggreg Hyper and Aggreg F itness , that reach respectiveley values of 6.7 10 -5 and 0.015 on MultiZeno6 and 0.0127 and 0.03155 on MultiZeno9. And for each value of α, a similar difference can be seen. Another remark is that the central values of α (0.5, 0.7 and 0.3, in this order) outperform the extreme values (1 and 0, in this order): this is not really surprising, considering that these runs, that optimize a single objective (makespan or cost), can only spread in one direction, while more 'central' values allow the run to cover more volume around their best solutions. Finally, in all cases, the 0-runs perform significantly worse than the corresponding 1-runs, but this is probably only due to the absence of normalization between both objectives.

Another comparative point of view on the convergence of both aggregation approaches is given by the hitting plots of Figure 4. These plots represent, for each point of the true Pareto front, the ratio along evolution of the runs (remember that one 'run' represent the sum of the eight α-runs, see Section 4) that reached that point, for all three instances MultiZeno{3,6,9}. On MultiZeno3 (results not shown here for space reasons), only one point, [START_REF] Chen | Temporal Planning using Subgoal Partitioning and Resolution in SGPlan[END_REF][START_REF] Bartz-Beielstein | Sequential parameter optimization[END_REF], is not found by 100% of the runs. But it is found by 10/11 runs by Aggreg Hyper and only by 6/11 runs by Aggreg F itness . On MultiZeno6, the situation is even clearer in favor of Aggreg Hyper : Most points are found very rapidly by Aggreg Hyper , and only point (56, 12) is not found by 100% of the runs (it is missed by 2 runs); on the other hand, only 4 points are found by all α-runs of Aggreg F itness , the extreme makespan (60, 10), and the 3 extreme costs [START_REF] Chen | Temporal Planning using Subgoal Partitioning and Resolution in SGPlan[END_REF]30), [START_REF] Haslum | Admissible Heuristics for Optimal Planning[END_REF][START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF], and [START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF][START_REF] Lourenço | Iterated Local Search[END_REF]. The other points are discovered by different runs . . . but overall, not a single run discovers all 11 points. Finally, the situation is even worse in the Mul-tiZeno9 case: only 6 points (out of 17) are ever discovered by Aggreg F itness , while Aggreg Hyper somehow manages to hit 12 different points. Hence again, no method does identify the full Pareto front.

But take a look at Figure 5, that displays the union of the 11 Pareto front returned by the aggregated runs, for both Aggreg Hyper and Aggreg F itness . No big difference is observed on MultiZeno6, except maybe a higher diversity away from the Pareto front for Aggreg Hyper . On the other hand, the difference is clear on MultiZeno9, where Aggreg F itness completely misses the center of the Pareto-delimited region of the objective space. Preliminary runs have been made with the two other instances presented in Section 2.2, where the costs of city2 have changed, respectively to 1.1 and 2.9, giving the Pareto fronts that are displayed in Figure 2. However, no specific parameter tuning was done for these instances, and all parameters have been carried on from the ParamILS runs on the corresponding MultiZeno instance where the cost of city2 is 2. First, it is clear that the overall performance of both aggregation methods is rather poor, as none ever finds the complete Pareto front in the 1.1 case, and only one run out of 11 finds it in the 2.9 case. Here again, only the extreme points are reliably found by both methods. Second, the advantage of Aggreg Hyper over Aggreg F itness is not clear any more: some points are even found more often by the latter. Finally, and surprisingly, the ankle point in the case 1.1 (Figure 2-a) is not found as easily as it might have seemed; and the point on the concave part of the case 2.9 (point (56, 22.8), see Figure 2-c) is nevertheless found by respectively 9 and 4 runs, whereas aggregation approaches should have difficulties to discover such points.

Conclusion and Perspectives

This paper has addressed several issues related to parameter tuning for aggregated approaches to multi-objective optimization. For the specific case study in AI temporal planning presented here, some conclusions can be drawn. First, the parameter tuning of each single-objective run should be made using the hypervolume (or maybe some other multi-objective indicator) as a quality measure for parameter configurations, rather than the usual fitness of the target algorithm. Second, the Aggreg Hyper approach seems to obtain better results than the multi-objective DaE YAHSP presented in [START_REF] Khouadjia | Multi-objective AI planning: Evaluating DAEYAHSP on a tunable benchmark[END_REF], in terms of hypervolume, as well as in terms of hitting of the points of the Pareto front. However, such comparison must take into account that one run of the aggregated approach requires eight times the CPU time of one single run: such fair comparison is the topic of ongoing work.

Finally, several specificities of the case study in AI planning make it very hazardous to generalize the results to other problems and algorithms without further investigations: DaE YAHSP is a hierarchical algorithm, that uses an embedded single objective planner that can only take care of one objective, while the evolutionary part handles the global behavior of the population; and the MultiZeno instances used here have linear, or quasi-linear Pareto front; ongoing work is concerned with studying other domains along the same lines.

In any case, several issues have been raised by these results, and will be the subject of further work. At the moment, only instance-based parameter tuning was performed -and the preliminary results on the other instances with different Pareto front shapes (see Figure 6) suggest that the best parameter setting is highly instance-dependent (as demonstrated in a similar AI planning context in [START_REF] Bibaï | On the Generality of Parameter Tuning in Evolutionary Planning[END_REF]). But do the conclusions drawn above still apply in the case of classdriven parameter tuning? Another issue that was not discussed here is that of the delicate choice of the values for α. Their proper choice is highly dependent on the scales of the different objectives. Probably some adaptive technique, as proposed by [START_REF] Jin | Adapting weighted aggregation for multiobjective evolution strategies[END_REF], would be a better choice.

Fig. 1 :

 1 Fig. 1: A schematic view of MultiZeno, a simple benchmark transportation domain: Flight durations of available routes are attached to the corresponding edges, costs 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 cost(city2) (all other values as in Figure1).

Fig. 4 :

 4 Fig. 4: Hitting plots on the 3 MultiZeno instances.

Fig. 5 :

 5 Fig. 5: Pareto fronts on MultiZeno instances.

Fig. 6 :

 6 Fig. 6: Hitting plots for different Pareto fronts for MultiZeno6. See Section 2.2 and compare with Figure 4-(a) and (b).

Table 1 :

 1 Set of DaE parameters and their discretizations for ParamILS, leading to approx. 1.5 • 10 9 possible configurations.

	Parameters	Range	Description
	W-makespan W-cost	0,1,2,3,4,5	Weighting for optimizing makespan during the search Weighting for optimizing cost during the search
	Pop-size	30,50,100,200,300 Population Size
	Proba-cross Proba-mut	0.0,0.1,0.2,0.5,0.8,1.0	Probability (at population level) to apply crossover Probability (at population level) to apply one mutation
	w-addAtom		Relative weight of the addAtom mutation
	w-addGoal w-delAtom	0,1,3,5,7,10	Relative weight of the addGoal mutation Relative weight of the delAtom mutation
	w-delGoal		Relative weight of the delGoal mutation
	Proba-change 0.0,0.1,0.2,0.5,0.8,1.0 Proba-delatom	Probability to change an atom in addAtom mutation Average probability to delete an atom in delAtom mutation
	Radius	1,3,5,7,10	Number of neighbour goals to consider in addGoal mutation

Table 2 :

 2 ParamILS results: Best parameters for DaE YAHSP on MultiZeno6 when comparing different approaches, statistical significance tests are made on the hypervolumes, using Wilcoxon signed rank test with 95% confidence level.

See http://www.plg.inf.uc3m.es/ipc2011-deterministic

with the exception of an early proof-of-concept for DaEX[START_REF] Schoenauer | Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning[END_REF] and its recently accepted follow-up[START_REF] Khouadjia | Multi-objective AI planning: Evaluating DAEYAHSP on a tunable benchmark[END_REF].

[START_REF] Bartz-Beielstein | Sequential parameter optimization[END_REF] In the MultiZeno Risk problem, not detailed here, the second objective is the risk: its maximal value ever encountered is to be minimized.

http://paradiseo.gforge.inria.fr/

⋆⋆ This work is being partially funded by the French National Research Agency under the research contract DESCARWIN (ANR-09-COSI-002).


Mostepha Redouane Khouadjia
email: mostepha-redouane.khouadjia@inria.fr

Marc Schoenauer
email: marc.schoenauer@inria.fr

Vincent Vidal
email: vincent.vidal@onera.fr

Johann Dréo
email: johann.dreo@thalesgroup.com

Pierre Savéant
email: pierre.saveant@thalesgroup.com

Multi-Objective AI Planning: Comparing Aggregation and Pareto Approaches

published or not. The documents may come

L'archive ouverte

Introduction

Most, if not all, classical AI planning solvers are single-objective. Given a planning domain (a set of predicates that describe the state of the system, and a set of actions with their pre-requisites and effects), and an instance of this domain (a set of objects on which the predicates are instantiated into boolean atoms, an initial state and a goal state), classical planners try to find, among the set of all feasible plans (sequences of actions such that, when applied to the initial state, the goal state becomes true), the one with the minimal number of actions (STRIP planning), or with the smallest cost (actions with costs) or with the smallest makespan (temporal planning, where actions have durations and can be applied in parallel). A detailed introduction to (single-objective) AI planning can be found in [1]. It is clear, however, that most planning problems are in fact multi-objective, as the optimal solution in real-world problems often involve some trade-off between makespan and cost [START_REF] Kambhampati | 1001 ways to skin a planning graph for heuristic fun and profit[END_REF]. A few trials have been made to turn some classical planners into multi-objective optimizers, either using some twist in PDDL 2.0 4 to account for both makespan and cost [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], or using the new hooks for several objectives offered by PDDL 3.0 [START_REF] Gerevini | Preferences and Soft Constraints in PDDL3[END_REF]. However, all these approaches are based on a linear aggregation of the different objectives, and were not pursued, as witnessed by the new "net-benefit" IPC track, dedicated to aggregated multiple objectives, that 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 due to a lack of entries.

In the framework of Evolutionary Algorithms (EAs), Pareto multi-objective optimization has received a lot of attention [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF], and any single-objective EA can "easily" be turned into a multi-objective EA, by modifying the selection step (and possible adding some archiving mechanism). Unfortunately, there exist very few evolutionary AI planners. Directly evolving plans, as in [START_REF] Brie | Genetic Planning Using Variable Length Chromosomes[END_REF], obviously does not scale up, and was never extended to multi-objective setting. Hence, as far as we are aware of, the state-of-the-art in evolutionary AI planning is the previous work of some of the authors, Divide-and-Evolve (DaE). DaE evolves variables length sequences of states, that start with the problem initial state and end at the problem goal state. DaE relies on a classical embedded planner to sequentially reach each state of the sequence from the previous one. The concatenation of all plans given by the embedded planner is a solution plan of the original problem. DaE can thus solve all types of planning problems that the embedded planner can solve. Proof-of-concept for DaE was obtained with DaE CPT [11], where the embedded planner was CPT, an exact planner [START_REF] Vidal | Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming[END_REF] -and already included some small multi-objective experiments. Since then, the DaE paradigm has evolved, and YAHSP a sub-optimal lookahead strategy planning system [START_REF] Vidal | A Lookahead Strategy for Heuristic Search Planning[END_REF] is now used as the embedded planner [START_REF] Bibaï | On the Benefit of Sub-Optimality within the Divide-and-Evolve Scheme[END_REF], and DaE YAHSP has reached state-of-the-art results in all planning domains [START_REF] Bibaï | An Evolutionary Metaheuristic Based on State Decomposition for Domain-Independent Satisficing Planning[END_REF], winning the temporal deterministic satisficing track at the last IPC in 2011 5 .

The very preliminary work in [11] regarding multi-objective optimization has also been recently revisited with DaE YAHSP . The lack of existing benchmark suite for multi-objective planning led us to extend the small toy problem from [11] into a tunable benchmark domain, on which different multi-objectivization of DaE YAHSP (MO-DaE YAHSP ) were compared [START_REF] Khouadjia | Multi-Objective AI Planning: Evaluating DAE-YAHSP on a Tunable Benchmark[END_REF]. But because the only other approach in AI Planning is the aggregation of the objectives, there is a need to compare the multi-objective approach for DaE YAHSP with the single-objective approach based on the linear aggregation of the objectives: this is the purpose of the present work. Section 2 will briefly present planning problems and DaE YAHSP in the single-objective setting. In Section 3, the multi-objective context will be introduced. The multi-objective benchmark suite will be presented, and the multi-objectivization of DaE YAHSP will be detailed: because YAHSP is a singleobjective planner 6 , but can be asked to optimize either the makespan or the cost, specific strategies had to be designed regarding how it is called within MO-DaE YAHSP . Section 4 describes the experimental settings, detailing in particular the implementation of the aggregation approach for DaE YAHSP and the intensive parameter tuning that was performed for all competing algorithms using the offline problem-independent tuner ParamILS [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF]. The results will be presented and discussed in Section 5, and as usual, conclusion and hints about on-going and further work will be given in Section 6.

2 Single-Objective Background AI Planning Problems: A planning domain D is defined by a set of object types, a set of predicates, and a set of possible actions. An instance is defined by a set of objects of the domain types, an initial state, and a goal state. A predicate that is instantiated with objects is called an atom, and takes a boolean value. For a given instance, a state is defined by assigning values to all possible atoms. An action is defined by a set of pre-conditions (atoms) and a set of effects (changing some atom values): the action can be executed only if all pre-conditions are true in the current state, and after an action has been executed, the state is modified: the system enters a new state. The goal is to find a plan (sequence of actions) such that it leads from the initial state to the goal state, and minimizes either the number or costs of actions, or the makespan in the case of temporal planning where actions have durations and can be run in parallel.

A simple temporal planning problem in the domain of logistics (inspired by the well-known Zeno problem of IPC series) is given in Figure 1, and will be the basis of the benchmark used in this work: the problem involves cities, passengers, and planes (object types). Passengers can be transported from one city to another (action fly), 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. In the default case labeled "Lin." in the table right (forget about the costs for now), the not-so-obvious makespan-optimal solution has a total makespan of 8 and is left as a teaser for the reader.

Divide-and-Evolve: Let P D (I, G) denote the planning problem defined on domain D with initial state I and goal state G. 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. The fitness of a sequence is computed using the embedded planner X, that is called in turn on each of the sub-problems P D (S k , S k+1 ). 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 unfeasible individuals are always selected after feasible ones. 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 rest of this section will briefly recall the evolutionary parts of DaE X .

An individual in DaE X is a variable-length list of partial states of the given domain (similar to the goal state), and a partial state is a variable-length list of atoms (instantiated predicates). The initialization procedure 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]. Furthermore, most existing planners (and this is true for CPT and YAHSP, that have been used within DaE) start by computing some partial mutual exclusion between possible atoms: this information is also used to reduce the search space in DaE X , whenever possible. An individual in DaE X is hence a variable-length time-consistent sequence of partial states, and each partial state is a variable-length list of atoms that are not pairwise mutually exclusive.

Crossover and mutation operators are applied with respective user-defined probabilities p Cross and p Mut . They are defined on the DaE X representation in a straightforward manner -though constrained by the heuristic chronology and the partial mutex relation between atoms. One-point crossover is adapted to variable-length representation: both crossover points are independently chosen, uniformly in both parents. Only one offspring is kept, the one that respects the approximate chronological constraint on the successive states. Four different mutation operators are included, and operate either at the individual level, by adding (addState) or removing (delState) a state, or at the state level by adding or modifying (addChangeAtom) or removing (delAtom) some atoms in a uniformly chose state. The choice among these operators is made according to user-defined relative weights (named w-mutationname -see Table 1).

3 Multi-Objective Background Two modifications of DaE YAHSP are needed to turn it into an EMOA: use some multi-objective selection engine in lieu of the single-objective tournament selection that is used in the single-objective context; and compute the value of both objectives (makespan and cost) for both individuals. The former modification is straightforward, and several alternatives have been experimented within [START_REF] Khouadjia | Multi-Objective AI Planning: Evaluating DAE-YAHSP on a Tunable Benchmark[END_REF]. The conclusion is that the indicator-based selection using the hypervolume difference indicator [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] performs best -and only this one will be used in the following, denoted here MO-DaE YAHSP . As explained above, the computation of the fitness is done by YAHSP-and YAHSP, like all known planners to-date, is a single-objective planner. It is nevertheless possible, since PDDL 3.0 [START_REF] Gerevini | Preferences and Soft Constraints in PDDL3[END_REF], to specify other quantities of interest that are to be computed throughout the execution of the final plan, without interfering with the search. Within MO-DaE YAHSP , two strategies are then possible for YAHSP: it can be asked to optimize either the makespan or the cost, and to simply compute the cost or the makespan when executing the solution plan (for feasible individuals).

The choice between both strategies is governed by user-defined weights, named respectively W-makespan and W-cost (see table 1). For each individual, the actual strategy is randomly chosen according to those weights, and applied to all subproblems of the individual. Note that those weights are tuned using ParamILS (see Section 4), and it turned out that the optimal values for MO-DaE YAHSP have always been equal weights: something that was to be expected, as no objective should be preferred to the other.

Aggregation-based Multi-Objective Divide-and-Evolve

Aggregation is certainly the easiest and most common way to handle multiobjective problems with a single-objective optimization algorithm: a series of single-objective optimization problems are tackled in turn, the fitness of each of these problems is defined by a linear combination of the objectives. In the case of makespan and cost, both to be minimized, each linear combination can be defined by a single parameter α in [0, 1]. In the following, F α will denote α * makespan + (1α) * cost, and DaE YAHSP run optimizing F α will be called the α-run. One "run" of the aggregation method thus amounts to running several α-runs, and returns the set of non-dominated individuals among the union of all final populations7 . Note that different alpha-runs might have different optimal values for their parameters: a complete parameter tuning run of ParamILS must be performed for each α-run to ensure a fair comparison with other well-tuned approaches.

The choice of the number of values to choose for the different α depends on the available resources. But the choice of the actual values aims at exploring Fig. 2: Pareto Fronts for the MultiZeno6 Cost problems described in Figure 1.

the objective space as uniformly as possible, and some issues might arise if both objectives are not scaled similarly. We hence propose here to use some evenly spaced values for α (see Section 4), but only after both objectives have been scaled into [0,1]. However, for such scaling to be possible, some bounds must be known for each objective. When they are not known, these bounds can be approximated from single-objective runs on each of the objectives in turn.

Multi-Objective Benchmarks:

The reader will have by now solved the little puzzle set in Section 2, and found the solution with makespan 8, that manages to leave no plane idle (detailed solution in [START_REF] Khouadjia | Multi-Objective AI Planning: Evaluating DAE-YAHSP on a Tunable Benchmark[END_REF]). In order to turn this problem into a multi-objective one, costs (or risks) are added to the fly actions that land in one of the central cities, leading to two types of problem: In MultiZeno Cost , the second objective is the total costs, that is accumulated every time a plane lands in a central city; In MultiZeno Risk , the second objective is the maximal risk encountered during the complete execution of a plan; both are to be minimized. The complexity of the instances can be increased by adding more passengers: instances with 3, 6 and 9 passengers will be used here. Finally, by tuning the values of the flight durations and the costs/risks, different shapes of the Pareto front can be obtained: Figure 1 summarizes three possible instances for the MultiZeno domain, and the corresponding Pareto fronts for the 6-passengers case are displayed in Figure 2.

Experimental Settings

Parameter Tuning: It is now widely acknowledged that the large number of parameters of most EAs, even though it is a source of flexibility, is also a weakness, in that a poor parameter setting can ruin the performances of the most promising algorithm. Whereas no generic approach exists for on-line control, there are today many available methods for off-line parameter tuning that should be used within any evolutionary experiment, in spite of their huge computational cost. In this work, unless otherwise stated, the user-defined parameters of both MO-DaE YAHSP and DaE YAHSP shown in Table 1 have been tuned anew for each instance, using the ParamILS framework [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF]. ParamILS performs an Iterated Table 1: Set of parameters off-line tuned using ParamILS.

Local Search in the space of possible parameter configurations, evaluating each configuration by running the algorithm to be optimized with this configuration on the given instance.

Stopping Criteria: Due to the variable number of calls to YAHSP the number of function evaluation is not representative of the CPU effort of runs of DaE YAHSP . Hence the stopping criterion of all DaE YAHSP run was set to a given wall-clock time (300, 600 and 1800 seconds for MultiZeno3, 6 and 9 respectively (on an Intel(R) Xeon(R) @ 2.67GHz or equivalent). That of MO-DaE YAHSP was set accordingly: for the sake of a fair comparison, because one run of the aggregated approach requires n runs of the single-objective version of DaE YAHSP , MO-DaE YAHSP was run for n times the time of each of the DaE YAHSP runs. In the following, n will vary from 3 to 8 (see Section 5). The stopping criterion for ParamILS was likewise set to a fixed wall-clock time: 48h (resp. 72h) for MultiZeno3 and 6 (resp. MultiZeno9), corresponding to 576, 288, and 144 parameter configuration evaluations for MultiZeno3, 6 and 9 respectively.

Performance Metrics and Results Visualization:

The quality measure used by ParamILS to optimize the parameters of both MO-DaE YAHSP and each of the α-runs of DaE YAHSP is the unary hypervolume I H - [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] of the set of nondominated 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). All reported differences in hypervolume have been tested using Wilcoxon signed rank test at 95% confidence level, unless otherwise stated.

However, and because the true front is made of a few scattered points (at most 17 for MultiZeno9 in this paper), it is also possible to visually monitor the empirical Cumulative Distribution Function of the probability to discover each point, as well as the whole front. This allows some deeper comparison between algorithms even when none has found the whole front. Such hitting plots will be used in the following, together with more classical plots of hypervolume vs time. Finally, because hitting plots only tell if a given point was reached and do not provide any information regarding how far from the other points the different runs ended, more details on the approximated Pareto fronts will be given by visualizing the merged final populations of all runs of given settings.

Implementation: For all experiments, 11 independent runs have been performed, implemented within the ParadisEO-MOEO framework8 . All performance assessment procedures (hypervolume calculations, statistical tests), have been achieved using the PISA performance assessment tool 9 .

Experimental Results

This section will compare the Pareto-based MO-DaE YAHSP and the aggregation approach Agg-DaE YAHSP on MultiZeno3, 6 and 9. Unless otherwise stated, the default domain definition leading to a linear Pareto front (see Figure 1 and 2-left) will be used, and one Agg-DaE YAHSP run will be made of 7 different α-runs, with α taking the values 0, 0.1, 0.3, 0.5, 0.7, 0.9, and 1.

The MultiZeno3 Problem proved to be too easy: both MO-DaE YAHSP and Agg-DaE YAHSP find the complete Pareto fronts, and the hitting plots reach 100% in less than 80s (resp. 90s) for the Cost (resp. Risk) version of the instance (not shown here). MO-DaE YAHSP is slightly slower (resp. faster) than Agg-DaE YAHSP in the Cost (resp. Risk) instance, but no significant difference is to be reported. Only instances -6 and -9 will be looked at in the following.

The Risk Objective: On these instances, however, the Risk objective proved to be almost too difficult to be of interest here, even though there are only 3 points on the Pareto Front, whatever the number of passengers: as can be seen on Figure 6, no algorithm could identify the complete Pareto front for the MultiZeno9 instance (line 4); for MultiZeno6 (line 2), MO-DaE YAHSP could reliably identify the whole front (in 9 runs out of 11), while only a single run of Agg-DaE YAHSP could identify the middle point (40,20). MO-DaE YAHSP is hence a clear winner here -however, too little information is brought by the risk value, as one single stop in a risky station will completely hide the possibly low-risk remaining of the plan. Further work will aim at designing a smoother fitness for such situations.

The rest of the paper will hence concentrate on the Cost versions of Multi-Zeno6 and 9 (simply denoted MultiZeno{6,9}), where significant differences between both approaches can be highlighted.

Results on the Default Instance: From the plots of the evolution of the average hypervolumes (Figure 3), MO-DaE YAHSP is the winner for MultiZeno6, and Agg-DaE YAHSP is the winner for MultiZeno9. Taking a closer look at the hitting plots (Figure 6), we can see for MultiZeno6 (line 1) that all runs of Results on other MultiZeno6 instances: Further experiments have been conducted on different variants of MultiZeno6 instance, described in Figure 1.

The corresponding hitting plots can be seen on Figure 5. As in the Linear default case, MO-DaE YAHSP is a clear winner -and this is confirmed by the plots of the approximate Pareto fronts (not shown), for which Agg-DaE YAHSP again shows a much larger dispersion away from the true front than MO-DaE YAHSP . All results presented until now have been obtained by first optimizing the parameters of all algorithms with ParamILS. Interestingly, when using the parameters optimized by ParamILS for the Linear instance on these other instances, the results are only slightly worse: this observation will motivate further work dedicated to the generalization of the parameter tuning across instances.

Discussion and Conclusion

The experiments presented in this paper have somehow demonstrated the greater efficiency of the Pareto-based approach to multi-objective AI Planning MO-DaE YAHSP compared to the more traditional approach by aggregation of the objectives Agg-DaE YAHSP . The case is clear on MultiZeno6, and on the different instances that have been experimented with, where MO-DaE YAHSP robustly finds the whole Pareto front (except for the Convex instance), whereas Agg-DaE YAHSP performs much worse in all aspects. This is also true on the MultiZeno9 instance, in spite of the better hypervolume indicator: indeed, a few more points on the Pareto front are found a little more often, but the global picture remains a poor approximation of the Pareto front. Other experiments on more instances are needed to confirm these first results, and on-going work is concerned with solving instances generated from IPC benchmarks by merging the cost and the temporal domains when the same instances exist in both.

Regarding the computational cost, one Agg-DaE YAHSP run requires several single-objective runs -and as many parameter tuning procedures. We have chosen here to use 7 different values for α, and it was clear from results not shown here that taking away a few of these resulted in a decrease of quality of the results. The computational cost of the parameter tuning could be reduced, too: first, a complete tuning anew for each instance is unrealistic, and was only done here for the sake of a fair comparison between both approaches; second, even on a single instance, it should be possible to tune all parameters (except those of YAHSP strategy) for all α-runs together. Finally, one of the most promising directions for future research is the on-line tuning of YAHSP strategy, e.g., using a self-adaptive approach, where the strategies are attached to the individual.

Fig. 1 :

 1 Fig. 1: Schematic view, and 3 instances, of simple MultiZeno benchmark.

3. 1

 1 Pareto-based Multi-Objective Divide-and-Evolve

Fig. 3 :

 3 Fig. 3: Evolution of hypervolume for DaE YAHSP (green squares) and Agg-DaE YAHSP (blue triangles) for MultiZeno6 (left) and MultiZeno9 (right).

Fig. 4 :

 4 Fig. 4: Pareto fronts approximations (union of all final populations).

Fig. 5 :

 5 Fig. 5: Hitting plots for MO-DaE YAHSP (left) and Agg-DaE YAHSP (right), for instances 2, 3, and 4 of MultiZeno6 from Figure 1 (from top to bottom).

Fig. 6 :

 6 Fig. 6: Hitting plots for MO-DaE YAHSP (left) and Agg-DaE YAHSP (right), for instances (from top to bottom) MultiZeno6 Cost , MultiZeno6 Risk , MultiZeno9 Cost , and MultiZeno9 Risk . The lower line on each plots is the experimental CDF for the probability to reach the whole Pareto front.

Planning Domain Definition Language, a dedicated language for the description of planning problems, set up for the International Planning Competitions (IPC).

See http://www.plg.inf.uc3m.es/ipc2011-deterministic

Note that it seems difficult, if at all opssible, to adapt it directly to multi-objective optimization, as it uses very different strategies for the makespan and the cost.

Some adaptive method has been proposed[START_REF] Jin | Adapting weighted aggregation for multiobjective evolution strategies[END_REF], where parameter α is adapted on-line, spanning all values within a single run: this is left for further work.

http://paradiseo.gforge.inria.fr/

⋆⋆ This work is being partially funded by the French National Research Agency under the research contract DESCARWIN (ANR-09-COSI-002)