Sorting Sequential Portfolios in Automated Planning

1 Introduction

The notion of portfolio has been revived from the Modern Portfolio Theory literature [Markowitz, 1952] with the aim of improving the performance of modern solvers. This notion has been applied to some problem-solving tasks with remarkable results. Indeed, the results of the International Planning Competition 2014 (IPC 2014) 1 show that three awarded planners and twenty nine out of sixty seven participant planners in the deterministic tracks were portfolios or planners that consisted of a collection of solvers.

A portfolio is termed static if its behavior is not modified once it has been configured -i. e., neither the component solvers and their allotted time nor the order of the execution sequence can be altered. If the portfolio has the ability to define a new behavior for each input instance, then it is termed dynamic. Also, if the portfolio invokes solvers in sequence, it is termed sequential, as opposed to parallel portfolios, which run multiple solvers concurrently.

The component solvers of the sequential portfolios considered in this work are not allowed to share any information. Thus, they can not take advantage of their position by using information from previous executions (e.g., a cost upper bound in satisficing planning). Additionally, preemptive mode (i.e., the ability to stop execution and resume it later on if necessary) is not allowed.

1 http://ipc.icaps-conference.org

The order in which the component solvers of a sequential portfolio are executed is a relevant issue that has not been analyzed in depth yet. Most successful portfolio approaches for Automated Planning only focus on maximizing performance (measured as overall quality or coverage) for a fixed time limit. We hypothesize that the order of the component solvers affects the performance of the portfolio over time. Thus, a sequential portfolio should be sorted if its performance over time is relevant. As a consequence, in optimal planning, the average time required to solve problems can be significantly reduced while in satisficing planning, lowersolution costs can be found more quickly, while preserving coverage or quality respectively.

An example of the interest in this particular problem can be found in the real world. The Power Restoration Problem [Hentenryck et al., 2011] is very similar to the problem described in this work. The electrical components that must be repaired are problems to be solved by solvers. The reward (power restored) for repairing each particular component is the number of problems solved (or the quality of the solutions found) by a solver within its allotted time. This allotted time represents the time required (cost) to fix each component. Finally, the goal is to maximize the power flow (by repairing electrical components) in the network as quickly as possible (coverage or quality over time).

The contributions of this work are summarized as follows:

1. The problem of ordering component solvers in a sequential (static or dynamic) portfolio is formally defined.
2. Two different algorithms to solve the problem are proposed and compared. We empirically show that our greedy approach produces near-optimal solutions very quickly and that it generalizes much better than an optimal solution wrt to a specific training set which has been observed to suffer from overfitting.
3. An extensive evaluation is performed with the algorithms introduced here, a random ordering algorithm and others from the literature with data from the last three IPCs.

The paper is organized as follows: first, Section 2 introduces Related Work. Section 3 formally defines the problem targeted in this work. Sections 4 and 5 describe the optimal and greedy approaches proposed. Section 6 reports the experimental results, and Section 7 ends with some conclusions and future work.

2 Background

Fast Downward Stone Soup (FDSS) [Helmert et al., 2011] was one of the awarded planners in the IPC 2011. The FDSS technique explores the space of static portfolios that can be configured with a set of candidate planners using a hill-climbing search. The FDSS-1 portfolio for the satisficing track sorts planners by decreasing order of coverage. The component planners of FDSS-1 for optimal planning are sorted by decreasing memory usage. The remaining portfolios were sorted by other arbitrary orderings, which were not detailed by the authors.

PBP [Gerevini et al., 2014] was the winner of the learning tracks of IPC 2008 and IPC 2011. It is a portfolio-based planner with macro-actions, which automatically configures a sequential portfolio of domain-independent planners for a specific domain. PBP uses the domain-specific knowledge with the purpose of selecting a cluster of planners for configuring the portfolio. This cluster of planners is sorted in ascending order of the allotted CPU time to run each solver.

Howe et al. [Howe et al., 2000] introduced BUS, which runs 6 planners in a round-robin scheme, until one component planner finds a solution. For each input instance, it extracts some features from the given planning task. The component planners are then sorted in descending order of the ratio P(Ai) T (Ai) , where P (Ai) is the expected probability of success of algorithmAi, and T(Ai) is the expected run time of algorithm Ai. Both estimations are provided by linear regression models based on instance features.

Cenamor et al. presented two strategies for configuring sequential portfolios [Cenamor et al., 2015]: IBACOP distributes uniformly all the available time among all planners selected by a Pareto efficiency analysis; IBACOP2, uses learned models to select the five planners with the highest confidence for solving the input task and distributes time uniformly among them. Both portfolios won the satisficing track of the IPC 2014. On the other hand, CEDALION is a new successful portfolio generation technique from highly parameterized solvers [Seipp et al., 2015]. Among these, only IBACOP2 sorts its component planners -using the confidence provided by the learned models.

3 Formal Description

In Automated Planning, the performance of a solver s is measured over a set of instances I (s can be either a solver or a portfolio). Every solver s is executed over every instance i ∈ I to obtain the set Rsi of solutions. This set contains every solution found by s within a given time bound t. We consider time as discrete in this work with a discretization of one second. Each element of Rsi stores the cost of the corresponding solution and a timestamp with the time required to find it. In case of solving problems optimally, solvers generate at most one solution per instance. In satisficing planning, solvers can generate multiple solutions. Therefore, the performance of s over time is measured by evaluating a specific metric over time. The most usual metrics are:

1. Coverage, C(s, I, t): number of problems in the benchmark I solved by the solver s in time less or equal than t per instance. It is the metric of the optimal track of the last three IPCs.
2. Overall quality, Q(s, I, t). Quality is mapped to the interval [0, 1] according to the expression cost∗i costs,i where costs,i is the best solution found by solver s for instance i in time less or equal than t and cost∗i is the best solution found for the same instance by any solver within the same time bound. The overall quality is computed as the sum of the quality over all instances. It is the metric for the satisficing track of the last three IPCs.

In the following, P(s, I, t) denotes generically either coverage, C(s, I, t) or overall quality, Q(s, I, t). Recall that every solver is executed t seconds on each instance to compute a specific metric. Next, we analyze the performance of portfolios of solvers over time.

Definition 1 A sequential portfolio ρ is a collection of n pairs 〈si, ti〉ni=1 , where si is a component solver and ti is the time allotted to its execution.

The preceding definition does not define any ordering among solvers in a portfolio. Indeed, the performance of the portfolio in time T ≥ ∑i ti is the same for any ordering.

Definition 2 An ordering τ of a sequential portfolio ρ is a full permutation over the solvers in ρ that defines the execution sequence, τ .= {s1, s2, . . . , sn}.

Let ρτ denote the sorted sequential portfolio of solvers in ρ whose execution ordering is given by τ .

In order to analyze the performance of a sorted sequential portfolio, we need to analyze separately the contribution of each solver to the overall performance.

Definition 3 A partial ordering τk is a partial permutation over the first k solvers in the full permutation τ : τk .= {s1, s2, ..., sk}.

Let ρτk denote the sorted sequential portfolio of solvers in ρ that considers only the first k solvers according to the ordering in τk.

Therefore, the first solver, s1, completes its execution after t1 seconds, the second solver will finish after (t1+t2) seconds and, in general, the j-th solver sj will complete its execution after ∑jk=1 tk seconds. Now, we can define how to measure the performance of the resulting portfolio over time as shown below.

Definition 4 The performance of a sorted sequence of solvers ρτ for a given problem set I over time t, P(ρτ , I, t) is defined as the sum of the best performance over all solvers in ρ executed in the order specified by τ for every instance in I in time less or equal than t.

In case that t < ∑ni=1 ti not all component solvers will be considered to compute P(ρτ , I, t). In this case, only the solutions found by those solvers in ρτ that could be run before t are considered. The timestamp of each considered solution is equal to the time required to find it by solver sk plus ∑k-1 i=1 ti. Next, we define the performance of a component solver, si, that occupies the i-th position in a permutation τ. It is computed as the increase in performance of the ordered portfolio by adding si to the portfolio.

Definition 5 Let Psi (ρτ , I) denote the performance of a component solver si in a partial permutation τi (that considers only the first i solvers in τ) wrt the benchmark I:

where τi denotes the partial permutation of all solvers in τ until si; tsi is the sum of the allotted times of all solvers in ρτi ; and, si-1 denotes the previous solver of si in the partial permutation.

The performance of a solver si is defined as a function of the ordered portfolio ρτ since different solvers in ρ or different orderings τ would yield different performances -i. e., the performance of a solver depends on the previous solvers. Consider a sequential portfolio ρ for optimal planning which consists of two solvers s1 and s2 which are allocated 4 and 7 seconds respectively. Let us assume that the performance of these solvers with respect to a set I of 20 planning tasks is:

• s1 solves instances 11 to 20. Hence, P(s1, I, 4) = 10.
• s2 solves tasks 1 to 18, resulting in P(s2, I, 7) = 18.

Assume further that both solvers solve the aforementioned instances in one second each. Therefore, P(s1, I, 1) = 10 and P(s2, I, 1) = 18. Figure 1 shows the performance over time of the two possible orderings for the given portfolio, τ1 : (s1, s2) (red solid line) and τ2 : (s2, s1) (blue dashed line). P(s1, I, 4) is equal to 10 since s1 solved 10 instances within its time span. However, the performance of s1 in each portfolio is different. Ps1 (ρτ1 , I) is equal to 10 because s1 is the first solver to be executed. However, the performance Ps1 (ρτ2 , I) is equal to two since instances 11-18 have already been solved by the previous solver s2. As shown in Figure 1, the performance of a sequential portfolio ρτ at time T = ∑i ti, P(ρ, I, T), is the same for every permutation τ. However, the performance of these orderings over time differs. Figure 1 also exemplifies a case where the portfolio achieving its maximum performance sooner is not the one with the best overall performance and, indeed, the first portfolio (red solid line) inscribes a smaller area than the second one.

The key observation is that the performance of ordered portfolios ρτ over time can be seen as bivariate density functions, fρτ (x, t). They are defined as the probability that the sorted portfolio ρτ reaches a performance P equal to x in t seconds: Prob(P = x, T = t). Accordingly, we define the probability function as follows.

Definition 6 Let Prob(P ≤ x, T = t) denote the probability that a portfolio ρτ reaches a performance equal to x or less in time t:

This observation leads to propose the area inscribed by this probability function as the optimization criteria to compare different permutations τ of the same portfolio ρ. Thus, we define the optimization task as follows.

Definition 7 Given a collection of n component solvers of a sequential portfolio ρ find the permutation τ ∗ of solvers s ∈ ρ for a given benchmark I such that it maximizes Fρτ (x, t):

As a result, this task will sort the component solvers of the input portfolio ρ with the aim of maximizing the area inscribed by the probability function shown in Definition 6 of the resulting ordering τ (see Definition 2).

4 Optimal Approach

We first use heuristic search with an admissible heuristic function to find the optimal ordering with respect to a given benchmark. Specifically, we propose Depth First Branch and Bound (DFBnB). It requires two parameters: a sequential portfolio ρ and the set Rsi, which will be used to compute the area inscribed by the probability function of every combination of the component solvers.

To find the optimal ordering τ ∗ , DFBnB starts with the empty permutation τ0. Each node m contains the current partial permutation τm and the set A of solvers that are not yet in ρτm (initially, A = {si | si ∈ ρ} i. e., all solvers in ρ). The successors of each node are generated by adding a solver s ∈ A to the current permutation (and thus removing it from A). Each node defines a partial permutation of the component solvers in ρ, while each leaf node defines a full permutation of all solvers in ρ.

DFBnB uses f(m) = g(m) + h(m). The g-value is the area inscribed by Fρτm after Tρτm seconds, where Tρτm is equal to the sum of the time spans of every solver in ρτm :

Suppose that DFBnB is initially given the portfolio ρ = {〈s1, 540〉, 〈s2, 630〉, 〈s3, 630〉}. Assume also that the DFBnB search is in a state m, where only the solver s3 has been selected, so that ρτm : {〈s3, 630〉} and Tρτm = 630. Figure 2 shows the area inscribed by the probability function Fρτm in the interval [0, 630] (blue line pattern area), where points denoted with uppercase letters allow us to define the areas inscribed by the probability function. Thus, the area inscribed by Fρτm is computed as the sum of the rectangular areas area(T0A0A1T1), area(T1A2A3T2) and area(T2A4A5T3).

In relation to h(m), we have defined an admissible heuristic termed SQUARE that optimistically estimates the area inscribed by the probability function FA. It just assumes that the order of the solvers contained in A is not relevant so that the portfolio will reach the performance P(ρ, I, T) of the portfolio ρ at time T with a 100% probability, one second after the first solver in A starts its execution. h(m) is computed as follows:

where TA is equal to the sum of the time spans of every solver in A. The area inscribed by FA is composed of two rectangular areas. The first one is defined in the interval [Tρτm , Tρτm + 1], the first second of the execution of the first solver in A. This area is represented by the first term in h(m). It is computed as the probability value of reaching a performance equal to x or less in time Tρτm multiplied by the time interval (one second). The second area is defined by the probability function FA in the interval [Tρτm + 1, Tρτm + TA].

Following the example in Figure 2, A = {s1, s2} and TA = 540 + 630 = 1170. Since these solvers have not yet been included in ρτm , the area inscribed by FA (yellow solid area) is computed using the SQUARE heuristic. The estimated yellow solid area is equal to the sum of the rectangular areas area(T3A5B0T4) (first term of the heuristic function), area(T4BCT5) (solver s1) and area(T5CDT6) (solver s2). The rectangular areas area(T4BCT5) and area(T5CDT6) are equal to TA - 1 = 1169. Hence:

This technique yields optimal orderings for a specific set of planning tasks. However, it can suffer from overfitting when evaluating its performance over a different benchmark.

5 Greedy Approach

The time required to find the optimal solution increases dramatically with the number of component solvers, since there are n! different orderings. Thus, we propose an alternative approach based on greedy search to quickly find a suboptimal solution with good quality.

We assume that the performance Psi (ρτ , I) can be approximated with a straight line in the interval [δ, δ + ti], where δ is the sum of the allotted time to ρτi-1 and ti is the execution time of si. The slope of this line is computed as the performance Psi (ρτ , I) divided by ti. We have selected the slope as a heuristic (to be denoted as SLOPE) because it is a conservative approximation of the growth in performance of a component solver in the portfolio. Also, it considers the performance of each component solver wrt the performance achieved by the previous solvers in the term Psi (ρτ , I) -see Definition 5.

We propose hill-climbing in the space of partial permutations of the input portfolio ρ as the search technique. It takes the same parameters as DFBnB described previously. The search is initialized with the empty permutation τ0, and the set A = {si | si ∈ ρ}. At each step, it selects the solver si ∈ A which has the largest ratio Psi (ρτ , I)/ti. Then, the selected solver is added to the current permutation and removed from A. Finally, the algorithm returns the ordered portfolio ρτ .

6 Experimental Setup and Results

The proposed algorithms (SLOPE and DFBnB) are compared with other ordering strategies and their performance is reported. Inspired by the ordering criteria used by state-of-theart portfolios in Automated Planning, we have defined the following algorithms to compare against our solutions. 2

• Shorter Time Spans (STS): inspired by PBP, this algorithm sorts the component solvers of a given portfolio in increasing order of the allotted time to run each solver.
• Memory Failures (MF): inspired by FDSS, it uses the number of times that each component planner exceeds the available memory limit (and does not solve the task) to sort the given portfolio in decreasing order.
• Decreasing Coverage (DC): inspired by FDSS, it uses the number of problems solved by each component solver to sort the input portfolio in decreasing order.
• Random: sorts the solvers of the input portfolio randomly. This algorithm generates five random orderings and reports the average score of all generated orderings.
• Confidence: uses the confidence provided by the learned models to sort the input portfolio in decreasing order. It is defined by IBACOP2. Therefore, it only will be applied in the comparisons with dynamic input portfolios.

2 We also tried to use the ordering criteria defined by BUS against our approach, but the source code is not available.

Tie-breaking is resolved by using the order in which solvers were initially specified. We have used an Intel Xeon 2.93 GHZ quad core processor with 8 GB of RAM. The time limit T used is 1800 seconds.

6.1 Static Input Portfolios

Equation (1) is used to measure the quality of the resulting orderings. This equation compares the area inscribed by the probability function of each sorted portfolio with the optimal sorting computed with DFBnB over the evaluation set. Thus, higher scores stand for better anytime behaviors.

The performance of all the considered sortings has been evaluated with different evaluation test sets: either the training data set or an entirely new one (test set). The second type of experiments examines the generalization capabilities of all ordering approaches. Also, to avoid introducing any bias in the experimentation, different techniques for generating static sequential portfolios are considered:

• Mixed-integer programming technique (MIP). This approach focused on deriving the optimal static sequential portfolio for a particular metric and a given training set [N´u˜nez et al., 2012].
• Random portfolios. They consist of a random selection of planners from a pool of candidate planners (at most half the number of candidate planners) so that at least one problem is solved in each training domain. The time allotted to each component planner is also randomly chosen, such that the total time does not exceed T.
• Random-uniform portfolios. They are random portfolios where the total available time is uniformly distributed among all the component planners.

We have performed two sets of experiments. The first one considers all the planning tasks from the IPC 2008 to configure and sort the input portfolio (training set). The new domains defined in the IPC 2011 are then used to assess the performance of the resulting portfolio (test set). In this experiment, we have used the set of candidate planners considered in the design of FDSS (FDSS-1 or FDSS-2, depending on the experiment) to configure the input portfolios. The second set of experiments takes the whole collection of planning tasks from the IPC 2011 as training set and the domains of the IPC 2014 (which were not included in IPC 2011) as test set. The input portfolios have been configured considering all the participants of the IPC 2011 but LPRPGP. 3

The size of the candidate and component planners sets are defined in the ranges [8, 38] and [3, 14] respectively. The smaller planner sets were used in optimal planning, since there were few participants in the last IPCs. As a reference, IBACOP2, the state-of-the-art portfolio, considers 12 candidate planners and five component planners.

The ordering generated by DFBnB for the training sets (IPC 2008 and IPC 2011) will be denoted as DFBnB 2008 and DFBnB 2011 respectively. Also, the ordering computed with DFBnB over the test sets only will be used to compute the test score of the orderings generated using the training set.

Table 1 shows the score of the resulting ordered portfolios using MIP portfolios. The training results show that the anytime behavior of the portfolio sorted with our greedy approach (SLOPE) is usually extremely close to the optimal performance. As it can be seen, the test results show that the orderings obtained by SLOPE and STS (using data from the IPC 2008) are the optimal orderings for the test set. Also, the permutation computed with the technique that generates the best ordering for the training data (DFBnB 2008) shows overfitting as expected; it is worse than the random ordering, and it does not generalize well to unknown domains. Moreover, the orderings generated with MF and DC usually perform worse than the RANDOM ordering. Finally, our greedy approach outperforms the other approaches with a remarkable score (IPC 2011) and generalizes well on the IPC 2014.

Table 2 presents the training and test results for the random and random-uniform portfolios. Since we are using random portfolios, we have executed 50 times the training and test phases, each one with a different random portfolio. As it can be seen, the SLOPE random portfolio achieves again a training score extremely close to the score of the best permutation (DFBnB solution) of the input portfolio. The test results for random portfolios show that the SLOPE portfolio outperforms others under the same conditions. Also, all the generated orderings usually perform better than RANDOM in the test set. The differences in test scores between SLOPE and STS are larger in satisficing planning than in optimal planning, mostly because in satisficing planning the ordering task is harder and there is much more variability in the areas of the portfolios.

Strikingly, the results for the random-uniform portfolio show that the SLOPE portfolio achieves a training score ex- Random Portfolios tremely close to the score obtained by the optimal sorting despite the fact that the uniform method penalizes the SLOPE heuristic. This method also penalizes the STS algorithm. However, the STS portfolio performs worse than the RANDOM portfolio. As it can be seen, the difference in test score between SLOPE and STS (the two algorithms that are penalized by using the uniform time assignment) is quite large. The scores of SLOPE, DFBnB 2008 and 2011 are very close. However, the time required by our greedy approach is exponentially shorter than the time required by DFBnB. Overall, all ordering algorithms (but DFBnB) sort a given portfolio in less than one second, while DFBnB can take several days to sort a given portfolio (depending on the number of component planners).

3 We experienced problems with the CPlex license.

6.2 Dynamic Input Portfolios

We now apply all the ordering algorithms defined above to IBACOP2, the winner of the IPC-2014 (satisficing planning). Instead of configuring the same portfolio for all test instances (as the approaches used in the previous experiments), IBACOP2 generates a different sequential portfolio for each input instance. Therefore, the score of each sorted ordering is computed as ∑i∈I score(ρiτ ), where ρiτ is the ordered portfolio computed for each input instance i. The generation of each portfolio is based on learned data using a training set.

We have considered all the instances defined in the IPC 2011 to sort the input portfolios and the domains of the IPC 2014 (which were not included in IPC 2011) to evaluate the resulting orderings.

As it can be seen in Table 3, the SLOPE portfolio achieves again near-optimal solutions in the training set. The training score obtained by the DC portfolio is remarkable while the training score of the STS portfolio is worse than the score achieved by the random ordering (similarly to the randomuniform portfolios). It is mainly due to the uniform method, which is applied by IBACOP2 to distribute the available time among the component solvers. The CONFIDENCE portfolio does not show training score because it was ordered by its learned models. On the other hand, the test score of the resulting orderings show that SLOPE again outperforms others. However, the test score of all the permutations are close among them.

7 Conclusions and FutureWork

In this work, we have presented a formal definition of the problem of sorting the component solvers in sequential portfolios. This open problem is addressed with the aim of improving the performance of the portfolios over time. In addition, we have introduced two algorithms to solve the aforementioned problem. The first one solves the problem optimally for a given data set using DFBnB and an admissible heuristic. Optimality is only guaranteed for the given training set. The second one is a greedy approach that uses the ratio between performance of each solver and execution time. Our results show that:

• The performance of the portfolio over time can significantly vary by using different ordering algorithms. Also, it can be improved by using a good ordering strategy, as shown by comparing against random orderings.
• DFBnB obtains an optimal ordering for the training set, but it does not generalize well to unknown domains. This optimal ordering shows overfitting when evaluating its performance over a different test set.
• Our greedy technique, SLOPE, computes orderings very fast, and obtains near-optimal solutions when compared against the optimal technique. Also, it generalizes much better than the state-of-the-art ordering techniques. The

good behavior of SLOPE does not depend on the algorithm used for generating the input portfolio, as shown by using randomly generated portfolios (with uniform and non-uniform times). We conjecture, in view of these results, that it is going to be difficult to find a better algorithm in terms of the balance between computation time, generalization power and quality of results.

In the future, we want to apply the ordering algorithms to portfolios generation techniques that generate several portfolios while solving the given input instance.

Acknowledgments

This work has been partially supported by MICINN project TIN2011-27652-C03-02.