NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Generalizing Backtrack-Free Search: A Framework for Search-Free Constraint SatisfactionTractable classes of constraint satisfaction problems are of great importance in artificial intelligence. Identifying and taking advantage of such classes can significantly speed up constraint problem solving. In addition, tractable classes are utilized in applications where strict worst-case performance guarantees are required, such as constraint-based plan execution. In this work, we present a formal framework for search-free (backtrack-free) constraint satisfaction. The framework is based on general procedures, rather than specific propagation techniques, and thus generalizes existing techniques in this area. We also relate search-free problem solving to the notion of decision sets and use the result to provide a constructive criterion that is sufficient to guarantee search-free problem solving.
Document ID
20000119024
Document Type
Other
Authors
Jonsson, Ari K. (Research Inst. for Advanced Computer Science Moffett Field, CA United States)
Frank, Jeremy (Caelum Research Corp. Moffett Field, CA United States)
Date Acquired
August 19, 2013
Publication Date
January 1, 2000
Subject Category
Cybernetics, Artificial Intelligence and Robotics
Distribution Limits
Public
Copyright
Other