Affordable Access

Publisher Website

Constraint Satisfaction Techniques-Chapter 8

Elsevier Inc.
DOI: 10.1016/b978-155860856-6/50013-2
  • Design


Publisher Summary Constraint satisfaction is a general and powerful problem-solving paradigm that is applicable to a broad set of areas, ranging from planning and scheduling to computer vision, pattern recognition, Computer-aided design (CAD), modeling, and decision support systems. The general formulation of a constraint satisfaction problem (CSP) is as follows. Given (1) a set of variables and their respective domains, and (2) a set of constraints on the compatible values that the variables may take, the problem is to find a value for each variable within its domain such that these values meet all the constraints. This chapter provides a general introduction to CSP techniques, as well as some developments on their specific use in planning. The chapter first reviews the essential definitions and concepts of CSPs over finite domains. This chapter presents an approach for encoding a planning problem into a CSP and then extracting a plan from the solution of that CSP. Algorithms for solving a CSP and filtering techniques for testing its consistency are introduced. The chapter briefly discusses two particular classes of CSPs of relevance to planning: active CSPs and valued CSPs. CSP techniques in the plan-space approach and the graph-plan approach are discussed in the chapter. The chapter ends with a discussion and exercises.

There are no comments yet on this publication. Be the first to share your thoughts.