Too Good to Throw Away: A Powerful Reuse Strategy for Reiter’s Hitting Set Tree

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Extended Abstracts

Reiter's HS-Tree is one of the most popular diagnostic search algorithms due to its desirable properties and general applicability. In sequential diagnosis, where the addressed diagnosis problem is subject to successive change through the acquisition of additional knowledge about the diagnosed system, HS-Tree is used in a stateless fashion. That is, the existing search tree is discarded when new knowledge is obtained, albeit often large parts of the tree are still relevant and have to be rebuilt in the next iteration, involving redundant operations and costly reasoner calls. As a remedy, we propose DynamicHS, a variant of HS-Tree that avoids these redundancy issues by maintaining state throughout sequential diagnosis while preserving all desirable properties of HS-Tree. Evaluations in a problem domain where HS-Tree is the state-of-the-art diagnostic method reveal stable and significant time savings achieved by DynamicHS.

10.1609/socs.v11i1.18527