Visualizations to Summarize Search Behavior

Ian S. Howell, Berthe Y. Choueiry, Hongfeng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we argue that metrics that assess the performance of backtrack search for solving a Constraint Satisfaction Problem should not be visualized and examined only at the end of search, but their evolution should be tracked throughout the search process in order to provide a more complete picture of the behavior of search. We describe a process that organizes search history by automatically recognizing qualitatively significant changes in the metrics that assess search performance. To this end, we introduce a criterion for quantifying change between two time instants and a summarization technique for organizing the history of search at controllable levels of abstraction. We validate our approach in the context of two algorithms for enforcing consistency: one that is activated by a surge of backtracking and the second that modifies the structure of the constraint graph. We also introduce a new visualization for exposing the behavior of variable ordering heuristics and validate its usefulness both as a standalone tool and when displayed alongside search history.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
EditorsHelmut Simonis
PublisherSpringer Science and Business Media Deutschland GmbH
Pages392-409
Number of pages18
ISBN (Print)9783030584740
DOIs
StatePublished - 2020
Event26th International Conference on Principles and Practice of Constraint Programming, CP 2020 - Louvain-la-Neuve, Belgium
Duration: Sep 7 2020Sep 11 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12333 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Principles and Practice of Constraint Programming, CP 2020
CountryBelgium
CityLouvain-la-Neuve
Period9/7/209/11/20

Keywords

  • Constraint Satisfaction
  • Search
  • Visualization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Visualizations to Summarize Search Behavior'. Together they form a unique fingerprint.

  • Cite this

    Howell, I. S., Choueiry, B. Y., & Yu, H. (2020). Visualizations to Summarize Search Behavior. In H. Simonis (Ed.), Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings (pp. 392-409). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12333 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-58475-7_23