Hierarchical Knowledge for Heuristic Problem Solving — A Case Study on the Traveling Salesperson Problem

Abstraction is a fundamental feature of human-level intelligence. But it is not clear how to combine knowledge on different levels of abstraction. This paper examines the use of hierarchical knowl-edge for heuristic problem-solving algorithms, regarding three options for integrating hierarchical knowledge into heuristic search: as a state evaluation heuristic, as a search-guiding heuristic and as a hierarchical search strategy. The Traveling Salesperson Problem serves as an example of a problem-solving task and the different strategies are evaluated with respect to tour length, robust-ness against misleading hierarchy assignments and acceptability of results by humans. It turns out that the most effective and stable results can be achieved with hierarchical knowledge as a search-guiding heuristic combined with other heuristics. 1