A Parallel Architecture for Constraint Satisfaction

Abstract

The Constraint Satisfaction Problem (CSP) has been a useful model for various industrial and engineering applications. These include image processing and pattern recognition, VLSI engineering, robotics manipulation, and computer hardware design automation. In this paper, we give a novel AI architecture for discrete relaxation that effectively prunes a backtracking search tree in CSP. This algorithm has been implemented on a finegrained, massively parallel hardware computer architecture. For practical application problems, many orders of magnitude of efficiency improvement can be reached on this hardware architecture. This enables real-time processing of a large class of practical problems. Keywords: Artificial Intelligence, backtrack search, constraint satisfaction problem (CSP), Discrete Relaxation Algorithm (DRA), AI architectures. 1 Introduction Constraint-based search problems have three components: variables, values, and constraints. The goal is to find an assignment of values to...