A Comparison of ATMS and CSP Techniques

Abstract

A fundamental problem for most AI problem solvers is how to control search to avoid searching subspaces which previously have been determined to be inconsistent. Two of the standard approaches to this problem are embodied in the constraint satisfaction problem ( CSP) techniques which evolved from vision tasks and assumptionbased truth maintenance system (ATMS) techniques which evolved from applying constraint propagation techniques to reasoning about the physical world. This paper argues that both approaches embody similar intuitions for avoiding thrashing and shows how CSPs can be mapped to ATMS problems and vice versa. In particular , Mackworth's notions of node , arc, and path consistency, Freuder's notion of k-consistency, and Dechter and Pearl's notion of directed kconsistency have precise analogs in the ATMS framework .