Document Open Access Logo

Understanding How People Approach Constraint Modelling and Solving

Authors Ruth Hoffmann , Xu Zhu , Özgür Akgün , Miguel A. Nacenta

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.28.pdf
  • Filesize: 2.53 MB
  • 18 pages

Document Identifiers

Author Details

Ruth Hoffmann
  • School of Computer Science, University of St Andrews, UK
Xu Zhu
  • School of Computer Science, University of St Andrews, UK
Özgür Akgün
  • School of Computer Science, University of St Andrews, UK
Miguel A. Nacenta
  • Department of Computer Science, University of Victoria, Canada

Funding

This work is partially funded by NSERC Discovery Grant 2020-04401 (Canada).
  • Zhu, Xu: University of St Andrews and EPSRC grant DTG1796157.

Cite As Get BibTex

Ruth Hoffmann, Xu Zhu, Özgür Akgün, and Miguel A. Nacenta. Understanding How People Approach Constraint Modelling and Solving. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.28

Abstract

Research in constraint programming typically focuses on problem solving efficiency. However, the way users conceptualise problems and communicate with constraint programming tools is often sidelined. How humans think about constraint problems can be important for the development of efficient tools that are useful to a broader audience. For example, a system incorporating knowledge on how people think about constraint problems can provide explanations to users and improve the communication between the human and the solver.
We present an initial step towards a better understanding of the human side of the constraint solving process. To our knowledge, this is the first human-centred study addressing how people approach constraint modelling and solving. We observed three sets of ten users each (constraint programmers, computer scientists and non-computer scientists) and analysed how they find solutions for well-known constraint problems. We found regularities offering clues about how to design systems that are more intelligible to humans.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Human-centered computing → Empirical studies in interaction design
Keywords
  • Constraint Modelling
  • HCI
  • User Study
  • Grounded Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey on explainable artificial intelligence (XAI). IEEE Access, 6:52138-52160, 2018. URL: https://doi.org/10.1109/ACCESS.2018.2870052.
  2. Özgür Akgün, Ian Miguel, Christopher Jefferson, Alan M. Frisch, and Brahim Hnich. Extensible automated constraint modelling. In AAAI 2011. AAAI Press, 2011. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3687.
  3. Krzysztof R. Apt. Principles of constraint programming. Cambridge University Press, 2003. Google Scholar
  4. Andreas Bauer, Viorica Botea, Mark Brown, Matt Gray, Daniel Harabor, and John K. Slaney. An integrated modelling, debugging, and visualisation environment for G12. In CP 2010. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15396-9_42.
  5. Amine Benamrane, Imade Benelallam, and El-Houssine Bouyakhf. Constraint programming based techniques for medical resources optimization: medical internships planning. J. Ambient Intell. Humaniz. Comput., 11(9):3801-3810, 2020. URL: https://doi.org/10.1007/s12652-019-01587-6.
  6. Bart Bogaerts, Emilio Gamba, Jens Claes, and Tias Guns. Step-wise explanations of constraint satisfaction problems. In ECAI 2020. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200149.
  7. Mavis Chan, Cecilia Chun, Holly Fung, Jimmy H. M. Lee, and Peter J. Stuckey. Teaching constraint programming using fable-based learning. In AAAI. AAAI Press, 2020. URL: https://aaai.org/ojs/index.php/AAAI/article/view/7059.
  8. Andrea A. diSessa. Metarepresentation: Native Competence and Targets for Instruction. Cognition and Instruction, 22(3):293-331, 2004. URL: https://doi.org/10.1207/s1532690xci2203_2.
  9. Mengnan Du, Ninghao Liu, and Xia Hu. Techniques for interpretable machine learning. Commun. ACM, 63(1):68-77, 2020. URL: https://doi.org/10.1145/3359786.
  10. Joan Espasa, Ian P. Gent, Ruth Hoffmann, Christopher Jefferson, and Alice M. Lynch. Using small muses to explain how to solve pen and paper puzzles. CoRR, abs/2104.15040, 2021. URL: http://arxiv.org/abs/2104.15040.
  11. Eugene C. Freuder. In pursuit of the holy grail. Constraints An Int. J., 2(1):57-61, 1997. URL: https://doi.org/10.1023/A:1009749006768.
  12. Eugene C. Freuder. Progress towards the holy grail. Constraints An Int. J., 23(2):158-171, 2018. URL: https://doi.org/10.1007/s10601-017-9275-0.
  13. Eugene C. Freuder and Mark Wallace. Constraint technology and the commercial world (interview). IEEE Intell. Syst., 15(1):20-23, 2000. URL: https://doi.org/10.1109/MIS.2000.820324.
  14. Thom W. Frühwirth and Slim Abdennadher. Essentials of constraint programming. COGTECH. Springer, 2003. URL: http://www.springer.com/computer/swe/book/978-3-540-67623-2.
  15. Cristian Galleguillos, Zeynep Kiziltan, and Ricardo Soto. A job dispatcher for large and heterogeneous HPC systems running modern applications. In CP 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CP.2021.26.
  16. James H. Gerlach and Feng-Yang Kuo. Understanding human-computer interaction for information systems design. MIS Q., 15(4):527-549, 1991. URL: http://misq.org/understanding-human-computer-interaction-for-information-systems-design.html.
  17. Barney G Glaser and Anselm L Strauss. The discovery of grounded theory: Strategies for qualitative research. Routledge, 2017. Google Scholar
  18. Sarah Goodwin, Christopher Mears, Tim Dwyer, Maria Garcia de la Banda, Guido Tack, and Mark Wallace. What do constraint programming users want to see? exploring the role of visualisation in profiling of models and search. IEEE Trans. Vis. Comput. Graph., 23(1):281-290, 2017. URL: https://doi.org/10.1109/TVCG.2016.2598545.
  19. Francis Heylighen. Formulating the Problem of Problem-Formulation. In Cybernetics and Systems '88, pages 949-957. Kluwer Academic Publishers, Dordrecht, 1988. Google Scholar
  20. Wonil Hwang and Gavriel Salvendy. Number of people required for usability evaluation: the 10+/-2 rule. Commun. ACM, 53(5):130-133, 2010. URL: https://doi.org/10.1145/1735223.1735255.
  21. Christopher Jefferson, Ian Miguel, Brahim Hnich, Toby Walsh, and Ian P Gent. CSPLib: A problem library for constraints, 1999. URL: http://www.csplib.org.
  22. Antje Kohnle and Gina Passante. Characterizing representational learning: A combined simulation and tutorial on perturbation theory. Physical Review Physics Education Research, 13(2):020131, 2017. URL: https://doi.org/10.1103/PhysRevPhysEducRes.13.020131.
  23. Robert Kozma and Joel Russell. Students Becoming Chemists: Developing Representational Competence. In Visualization in Science Education, Models and Modeling in Science Education, pages 121-145. Springer Netherlands, Dordrecht, 2005. URL: https://doi.org/10.1007/1-4020-3613-2_8.
  24. Michael Leuschel and Michael Butler. Prob: A model checker for b. In International symposium of formal methods europe, pages 855-874. Springer, 2003. Google Scholar
  25. Mary L McHugh. Interrater reliability: the kappa statistic. Biochemia Medica, 22(3):276-282, 2012. URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3900052/.
  26. Gonzalo Gabriel Méndez, Uta Hinrichs, and Miguel A. Nacenta. Bottom-up vs. top-down: Trade-offs in efficiency, understanding, freedom and creativity with infovis tools. In CHI 2017. ACM, 2017. URL: https://doi.org/10.1145/3025453.3025942.
  27. Bonnie A. Nardi. A Small Matter of Programming: Perspectives on End User Computing. MIT press, 1993. URL: https://books.google.co.uk/books?hl=en&lr=&id=0drDRT370eoC&oi=fnd&pg=PR11&dq=nardi+small+matter+of+programming&ots=eFmV2hPujA&sig=ddWW4jgU1jebzDZpk7plDRCtcoU.
  28. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. Minizinc: Towards a standard CP modelling language. In CP 2007. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74970-7_38.
  29. Jakob Nielsen. Estimating the number of subjects needed for a thinking aloud test. Int. J. Hum. Comput. Stud., 41(3):385-397, 1994. URL: https://doi.org/10.1006/ijhc.1994.1065.
  30. Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, and Patrick Spracklen. Automatically improving constraint models in savile row. Artif. Intell., 251:35-61, 2017. URL: https://doi.org/10.1016/j.artint.2017.07.001.
  31. Orit Parnafes and Andrea A. diSessa. Relations between types of reasoning and computational representations. Int. J. Comput. Math. Learn., 9(3):251-280, 2004. URL: https://doi.org/10.1007/s10758-004-3794-7.
  32. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. Scikit-learn: Machine learning in python. J. Mach. Learn. Res., 12:2825-2830, 2011. URL: http://dl.acm.org/citation.cfm?id=2078195.
  33. Patrick Prosser. Teaching constraint programming. In CP 2014. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-10428-7_2.
  34. Bochra Rabbouch, Foued Saâdaoui, and Rafaa Mraihi. Constraint programming based algorithm for solving large-scale vehicle routing problems. In HAIS 2019. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-29859-3_45.
  35. S I Robertson. Problem Solving. Psychology Press, 2001. Google Scholar
  36. Maxim Shishmarev, Christopher Mears, Guido Tack, and Maria Garcia de la Banda. Visual search tree profiling. Constraints An Int. J., 21(1):77-94, 2016. URL: https://doi.org/10.1007/s10601-015-9202-1.
  37. Herbert A Simon and John R Hayes. The understanding process: Problem isomorphs. Cognitive psychology, 8(2):165-190, 1976. Google Scholar
  38. Mohammed H. Sqalli and Eugene C. Freuder. Inference-based constraint satisfaction supports explanation. In AAAI/IAAI 1996. AAAI Press / The MIT Press, 1996. URL: http://www.aaai.org/Library/AAAI/1996/aaai96-048.php.
  39. Maarten Van Someren, Yvonne F. Barnard, and J. Sandberg. The think aloud method: A practical approach to modelling cognitive processes. London: AcademicPress, 11, 1994. Google Scholar
  40. Xu Zhu, Miguel A. Nacenta, Özgür Akgün, and Peter Nightingale. How people visually represent discrete constraint problems. IEEE Trans. Vis. Comput. Graph., 26(8):2603-2619, 2020. URL: https://doi.org/10.1109/TVCG.2019.2895085.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact