Back to Backtracking: Controlling the ATMS

Engineering

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 5

Automated Reasoning

The ATMS (Assumption-Based Truth Maintenance System) provides a very general facility for all types of default reasoning. One of the principal advantages of the ATMS is that all of the possible (usually mutually inconsistent) solutions or partial solutions are directly available to the problem solver. By exploiting this capability of the ATMS, the problem solver can efficiently work on all solutions simultaneously and avoid the computational expense of backtracking. However, for some applications this ATMS capability is more of a hindrance than a help and some form of backtracking is necessary. This paper first outlines some of the reasons why backtracking is still necessary, and presents a powerful backtracking algorithm which we have implemented which backtracks more efficiently than other approaches.