Backtrack-free search for real-time constraint satisfaction

J. Christopher Beck; Tom Carchrae; Eugene C. Freuder; Georg Ringwelski

doi:10.1007/978-3-540-30201-8_10

Backtrack-free search for real-time constraint satisfaction

J. Christopher Beck
, Tom Carchrae
, Eugene C. Freuder
, Georg Ringwelski

University College Cork

University College Cork

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

Abstract

A constraint satisfaction problem (CSP) model can be preprocessed to ensure that any choices made will lead to solutions, without the need to backtrack. This can be especially useful in a real-time process control or online interactive context. The conventional machinery for ensuring backtrack-free search, however, adds additional constraints, which may require an impractical amount of space. A new approach is presented here that achieves a backtrack-free representation by removing values. This may limit the choice of solutions, but we are guaranteed not to eliminate them all. We show that in an interactive context our proposal allows the system designer and the user to collaboratively establish the tradeoff in space complexity, solution loss, and backtracks.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Mark Wallace
Publisher	Springer Verlag
Pages	92-106
Number of pages	15
ISBN (Print)	3540232419, 9783540232414
DOIs	https://doi.org/10.1007/978-3-540-30201-8_10
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3258
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-30201-8_10

Cite this

Beck, J. C., Carchrae, T., Freuder, E. C., & Ringwelski, G. (2004). Backtrack-free search for real-time constraint satisfaction. In M. Wallace (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 92-106). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3258). Springer Verlag. https://doi.org/10.1007/978-3-540-30201-8_10

Beck, J. Christopher ; Carchrae, Tom ; Freuder, Eugene C. et al. / Backtrack-free search for real-time constraint satisfaction. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Mark Wallace. Springer Verlag, 2004. pp. 92-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{a0afe467e4e4487a84e2fc6e8ebdf60c,

title = "Backtrack-free search for real-time constraint satisfaction",

abstract = "A constraint satisfaction problem (CSP) model can be preprocessed to ensure that any choices made will lead to solutions, without the need to backtrack. This can be especially useful in a real-time process control or online interactive context. The conventional machinery for ensuring backtrack-free search, however, adds additional constraints, which may require an impractical amount of space. A new approach is presented here that achieves a backtrack-free representation by removing values. This may limit the choice of solutions, but we are guaranteed not to eliminate them all. We show that in an interactive context our proposal allows the system designer and the user to collaboratively establish the tradeoff in space complexity, solution loss, and backtracks.",

author = "Beck, \{J. Christopher\} and Tom Carchrae and Freuder, \{Eugene C.\} and Georg Ringwelski",

year = "2004",

doi = "10.1007/978-3-540-30201-8\_10",

language = "English",

isbn = "3540232419",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "92--106",

editor = "Mark Wallace",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Beck, JC, Carchrae, T, Freuder, EC & Ringwelski, G 2004, Backtrack-free search for real-time constraint satisfaction. in M Wallace (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3258, Springer Verlag, pp. 92-106. https://doi.org/10.1007/978-3-540-30201-8_10

Backtrack-free search for real-time constraint satisfaction. / Beck, J. Christopher; Carchrae, Tom; Freuder, Eugene C. et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Mark Wallace. Springer Verlag, 2004. p. 92-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3258).

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

TY - CHAP

T1 - Backtrack-free search for real-time constraint satisfaction

AU - Beck, J. Christopher

AU - Carchrae, Tom

AU - Freuder, Eugene C.

AU - Ringwelski, Georg

PY - 2004

Y1 - 2004

N2 - A constraint satisfaction problem (CSP) model can be preprocessed to ensure that any choices made will lead to solutions, without the need to backtrack. This can be especially useful in a real-time process control or online interactive context. The conventional machinery for ensuring backtrack-free search, however, adds additional constraints, which may require an impractical amount of space. A new approach is presented here that achieves a backtrack-free representation by removing values. This may limit the choice of solutions, but we are guaranteed not to eliminate them all. We show that in an interactive context our proposal allows the system designer and the user to collaboratively establish the tradeoff in space complexity, solution loss, and backtracks.

AB - A constraint satisfaction problem (CSP) model can be preprocessed to ensure that any choices made will lead to solutions, without the need to backtrack. This can be especially useful in a real-time process control or online interactive context. The conventional machinery for ensuring backtrack-free search, however, adds additional constraints, which may require an impractical amount of space. A new approach is presented here that achieves a backtrack-free representation by removing values. This may limit the choice of solutions, but we are guaranteed not to eliminate them all. We show that in an interactive context our proposal allows the system designer and the user to collaboratively establish the tradeoff in space complexity, solution loss, and backtracks.

UR - https://www.scopus.com/pages/publications/35048858903

U2 - 10.1007/978-3-540-30201-8_10

DO - 10.1007/978-3-540-30201-8_10

M3 - Chapter

AN - SCOPUS:35048858903

SN - 3540232419

SN - 9783540232414

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 92

EP - 106

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Wallace, Mark

PB - Springer Verlag

ER -

Beck JC, Carchrae T, Freuder EC, Ringwelski G. Backtrack-free search for real-time constraint satisfaction. In Wallace M, editor, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 92-106. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-30201-8_10

Backtrack-free search for real-time constraint satisfaction

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this