An Analysis of Multiobjective Search Algorithms and Heuristics

1 Introduction

Shortest path problems are a classical field of study in Artificial Intelligence. The A* algorithm [Hart et al., 1968] is a heuristic best-first algorithm that uses cost estimates to improve search efficiency. The algorithm is guaranteed to find optimal solutions when estimates are optimistic. Moreover, if they satisfy the consistency property, more informed heuristics result in less or at most equal search effort [Pearl, 1984].

Multiobjective Shortest Path Problems (MSP) must simultaneously consider several conflicting objectives. Therefore, arcs are labelled with cost vectors, where each component stands for a different relevant attribute to be minimized, e.g. distance, time, or travel cost when choosing alternative roads in a trip. This induces only a partial order preference relation called dominance. These problems rarely have a single optimal solution. Thus, multiobjective search algorithms try to find the set of all non-dominated (Pareto-optimal) solution paths, representing the optimal trade-offs between the objectives under consideration.

Multiobjective search is currently an active research field in Operational Research (OR) and Artificial Intelligence (AI). Many OR contributions concentrate on blind search algorithms (e.g. see [Hansen, 1979] [Raith and Ehrgott, 2009]). Regarding heuristic search, at least three different extensions of A* to the multiobjective case have been proposed, namely NAMOA* [Mandow and P´erez de la Cruz, 2005], MOA* [Stewart and White, 1991], and Tung & Chew's (TC) algorithm [Tung and Chew, 1992]. While NAMOA* and MOA* accept both blind and heuristic search, the Tung & Chew (TC) algorithm was devised only for heuristic search.

Several formal analyses have been presented for these algorithms. All have been shown admissible under analogous assumptions. Formal properties on the efficiency of MOA* and NAMOA* have been presented. In particular, NAMOA*

∗This work is funded by Consejer´ıa de Innovaci´on, Ciencia y Empresa, Junta de Andaluc´ıa (Spain), P07-TIC-03018

has been found to be optimal over the class of admissible multiobjective search algorithms [Mandow and P´erez de la Cruz, 2010]. However, little is known regarding which algorithm is better in practice or the actual benefits of heuristic information in multiobjective search performance.

For the single objective case, A* is known to reduce computational requirements with heuristic information. It would be of interest to know under which conditions the same holds in multiobjective search. In multiobjective algorithms, the number of nodes considered is not a significant performance measure [Hansen, 1979]. From a formal point of view, NAMOA* has been shown to produce fewer label expansions with more precise heuristics. However, the accuracy of heuristics could not be related to the number of labels expanded by Stewart and White for MOA*, and analogous results are not known for the TC algorithm.

Recent works show that heuristics precalculated with search, like pattern databases [Culberson and Schaeffer, 1998], can be used to boost efficiency in single-objective search. Tung & Chew [1992] presented two such precalculated heuristic functions for multiobjective search. However, little is known regarding their effectiveness in practice.

This thesis tries to address all these open questions.

2 First results

NAMOA*, MOA* and TC algorithms are best-first algorithms, they select at each iteration the most promising alternative to be further continued. The main differences lie in their different path/node expansion strategies. While MOA* selects a node (extending all found alternative paths to the node), NAMOA* and TC algorithms extend a single path (label). A typical vectorial heuristic is used by NAMOA* and MOA*, while TC presents an additional innovative scalar rule.

The heuristic estimates used in the selection of alternatives are described in the work of Tung & Chew [1992]. A first vectorial heuristic was used only for pruning of new alternatives in their algorithm. However, it has been adopted for pruning and also for selection in MOA* and NAMOA*. The second scalar heuristic is used only in TC algorithm for path selection, estimating a linear combination of all objectives.

Two different analyses have been conducted to compare the performance of the TC, MOA* and NAMOA* algorithms. These involve search in random bicriterion square grids of two classes: in class I problems, search is conducted from a corner to the opposite, while in class II ones, search proceeds from the center outwards. Variable parameters of the analyses are the correlation between objectives, depth of solutions and heuristic information.

The first analysis [Machuca et al., 2009] considered only NAMOA* and TC algorithms (a blind-like version was also provided for TC), and tried to evaluate the benefits in search efficiency of the precalculated TC heuristics over blind search. Class I problems with two uncorrelated objectives (zero correlation) were used. Results showed several important conclusions. In the first place, time devoted to heuristic precalculations was not very significant. Secondly, the heuristics allowed important savings in space requirements over blind search. However, the experiments showed that time requirements are highly influenced by the particular path selection strategy. The accurate scalar selection heuristic used in TC was found to penalize time requirements, and blind search was quicker for bigger problems. Contrary to intuition, no time improvement could be observed in heuristic versions. They perform fewer iterations but the more gradual discovery of nondominated solutions in blind versions results in a minor number of comparisons when checking the goodness of a new alternative.

The second analysis [Machuca et al., 2010] considered blind versions of MOA* and NAMOA* algorithms, and tried to evaluate the impact on the efficiency of their different node/path selection strategies. The empirical evaluation considered problems of classes I and II and two objectives, with correlation values 0.8, 0.4, 0, -0.4 and -0.8. One could think that considering simultaneously all known non-dominated paths of a node is more efficient. In fact, results show that MOA* is quicker for easier problems (high linear correlation and/or shallower solutions) both for class I and class II problems. However, it was found that MOA* incurs in a heavy time overhead for more difficult problems (low correlation and/or deeper solutions). Each time a new non-dominated path is found to a closed node, all its labels must be put back again into the open list. The results also show that memory requirements were very similar for class I problems, and that for class II problems, MOA* has an additional space overhead that tends to be smaller as the depth of solution increases, with an approximate relative ratio of only 15-25% more in difficult problems. The relative space difference with NAMOA* is actually smaller than originally expected, given that MOA* can consider for expansion many dominated paths during search. A statistical analysis was carried out, confirming that for a correlation equal or lower than 0 (harder problems), the relative performance follows polynomial laws when increasing solution depth.

3 Current and future work

Current work includes an extension to heuristic search of the second analysis including the three algorithms TC, MOA* and NAMOA*. This analysis should clarify the benefits of heuristic information and the goodness of the different algorithms over several classes of problems. The application of the algorithms to real world problems, like routing in road maps as described by Raith & Ehrgott [2009], is currently also a working topic.

From a formal point of view, a characterisation of the efficiency obtained by TC and MOA* algorithms with accurate heuristics (like those proposed by Tung & Chew) should be performed in terms of the number of label expansions. These works would complete the analysis of the behaviour of the heuristic multiobjective algorithms considered.

However, the research can be further continued. The determination of more informed precalculated heuristic is an interesting line that deserves investigation.

Finally, another interesting line of research would be the introduction of heuristic information in other blind multiobjective search algorithms like the two phases approach followed by Raith & Ehrgott [2009].