This paper presents an algorithm for first-order Horn-clause abduction that uses an ATMS to avoid redundant computation. This algorithm is either more efficient or more general than any other previous abduction algorithm. Since computing all minimal abductive explanations is intractable, we also present a heuristic version of the algorithm that uses beam search to compute a subset of the simplest explanations. We present empirical results on a broad range of abduction problems from text understanding, plan recognition, and device diagnosis which demonstrate that our algorithm is at least an order of magnitude faster than an alternative abduction algorithm that does not use an ATMS.

PDF, PS

In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), pp. 494-499, Anaheim, CA, July 1991.

@InProceedings{ng:aaai91, title={An Efficient First-Order Horn-Clause Abduction System Based on the ATMS}, author={Hwee Tou Ng and Raymond J. Mooney}, booktitle={Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91)}, month={July}, address={Anaheim, CA}, key={atms}, pages={494-499}, url="http://www.cs.utexas.edu/users/ai-lab?ng:aaai91", year={1991} }