---
title: "A Comparison of ATMS and CSP Techniques"
authors:
  - "Johan de Kleer"
doi: ""
url: "https://ijcai.org/proceedings/1989/46"
pdf: "https://ijcai.org/proceedings/1989/0046.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "290-295"
track: "Search"
keywords:
---

# A Comparison of ATMS and CSP Techniques

Johan de Kleer

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, pages 290-295.

## 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 .