Algorithmic multi-objective heuristics construction in the A ∗ search

Abstract

Merging multi-objective optimization and expert systems technology results in reduced modeling efforts and enhanced problem-solving tools. Search is one of the ways to combine multi-objective optimization and knowledge-intensive computation schemes. Search is usually associated with prohibitive computational costs and heuristics are often used to alleviate the computational burden. We propose an efficient algorithm for constructing multi-objective heuristics. We also develop some sufficiency conditions for the admissibility of the heuristic. Our multi-objective A∗ algorithm has been implemented and experimentally evaluated. Its time performance is comparable and often superior to that of other more conventional algorithms.