Abstract
Constraint satisfaction and combinatorial optimization form the crux of many AI problems. In constraint satisfaction, feasibility-reasoning mechanisms are used to prune the search space, while optimality-reasoning is used for combinatorial optimization. Many AI tasks related to diagnosis, trajectory tracking and planning can be formulated as hybrid problems containing both satisfaction and optimization components, and can greatly benefit from a proper blend of these independently powerful techniques.
We introduce the notion of model counting to bridge the gap between feasibility- and optimality-reasoning. The optimization part of a problem then becomes a search for the right set of constraints that must be satisfied in any good solution. These constraints, which we call the oracular constraints, replace the optimization component of a problem to revive the power of constraint reasoning systems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, A. and Furst, M. 1997. Fast Planning Through Planning Graph Analysis. Artificial Intelligence 90, 281–300.
Dechter, R. 1992. Constraint Networks. Encyclopedia of Artificial Intelligence, second edition, Wiley and Sons, pp 276–285, 1992.
Kautz, H., McAllester, D. and Selman, B. 1996. Encoding Plans in Propositional Logic. Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning, 374–384.
Kurien, J. and Nayak, P. P. 2000. Back to the Future for Consistency-Based Trajectory Tracking. Proceedings of the 17th National Conference on Artificial Intelligence (AAAI 2000).
Larrossa, J. and Meseguer, P. Partition-based Lower Bound for Max-CSP. 1999. Proceedings of CP’99, pages 303–315.
Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, E. and Tragoudas, S. 1991. Fast Approximation Algorithms for Multicommodity Flow Problem. In Proceedings of the 23rd ACM Symposium on the Theory of Computing, pages 101–111, May 1991.
Plotkin, S., Shmoys, D. and Tardos, E. 1995. Fast Approximation Algorithms for Fractional Packing and Covering Problems. Math of Oper. Research, 20(2):257–301, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kumar, T.K.S., Dearden, R. (2002). The Oracular Constraints Method. In: Koenig, S., Holte, R.C. (eds) Abstraction, Reformulation, and Approximation. SARA 2002. Lecture Notes in Computer Science(), vol 2371. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45622-8_22
Download citation
DOI: https://doi.org/10.1007/3-540-45622-8_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43941-7
Online ISBN: 978-3-540-45622-3
eBook Packages: Springer Book Archive