PyConA: Constraint Acquisition in Python

PyConA (https://github.com/CPMpy/PyConA) is a python-based, open-source package for Constraint Acquisition (CA). In CA, the goal is to assist the user in modeling Constraint Programming (CP) problems, by learning the constraints through user interaction.

PyConA is based on the powerful CPMpy Constraint Programming and Modeling library in python (https://github.com/CPMpy/cpmpy), which is used for modeling the constraint problems.

Currently, only interactive CA methods are implemented in PyConA; passive CA methods might be added later.

Interactive Constraint Acquisition

In interactive CA, the system interacts with an Oracle, which can be a human user or a software system. The CA system asks queries and based on the answers of the oracle it either learns or excludes constraints.

PyConA is a generic CA library implementing a range of interactive CA methods, using the following modules:

• Interactive CA Algorithm: The top-level algorithm to be used.
• Query Generation: The query generation system to be used to generate top-level queries.
• FindScope: The FindScope system to be used for finding the scope of violated constraints.
• FindConstraint: The FindConstraint system to be used for finding the exact violated constraints in the given scopes.

A detailed presentation of CA methods can be found at:

• Video
• Slides

Features

The repository has implemented various approaches and methods from the literature:

• Algorithms: QuAcq [1-2], MQuAcq [3-4], MQuAcq-2 [5], GrowAcq [6], P-QuAcq[7], G-QuAcq [8]
• Query Generation: TQ-Gen [9], PQ-Gen [6]
• FindScope: FindScope [1], Findscope-2 [2, 4]
• FindC: FindC [1], FindC-2 [2]
• ML-based CA system and query generation objectives from [10]

Installation

Clone and Install from this Repo

git clone -b main https://github.com/CPMpy/PyConA.git

Pip install through pip

You can install pycona through pip

pip install pycona

Basics

In PyConA, the ProblemInstance class represents the instance of the problem the user wants to acquire the constraints for. It must be initialized with the variables of the problem and a language. A CA system is then used to acquire the constraints. A CA system uses a CA environment to configure its options. PyConA currently implements only interactive CA algorithms (module .active_algorithms).The core of interactive CA systems is the AlgorithmCAInteractive class. This is subclassed with different algorithms presented in the literature.

Basic Tutorials

• Introductory Example
• Comparing different algorithms and methods
• Prediction-based CA system
• CP24 Tutorial Demo

Documentation

Coming soon

References

[1] Bessiere, C., at al. (2013, June). Constraint acquisition via partial queries. In _Twenty-Third International Joint Conference on Artificial Intelligence.

[2] Bessiere, C., et al. (2023). Learning constraints through partial queries. Artificial Intelligence, 319, 103896.

[3] Tsouros, D. C., Stergiou, K., & Sarigiannidis, P. G. (2018). Efficient methods for constraint acquisition. In Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings 24 (pp. 373-388). Springer International Publishing.

[4] Tsouros, D. C., & Stergiou, K. (2020). Efficient multiple constraint acquisition. Constraints, 25(3), 180-225.

[5] Tsouros, D. C., Stergiou, K., & Bessiere, C. (2019). Structure-driven multiple constraint acquisition. In Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30–October 4, 2019, Proceedings 25 (pp. 709-725). Springer International Publishing.

[6] Tsouros, D. C., Berden, S., & Guns, T. (2023). Guided Bottom-Up Interactive Constraint Acquisition}}. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) (Vol. 280, p. 36).

[7] Daoudi, A., Mechqrane, Y., Bessiere, C., Lazaar, N., & Bouyakhf, E. H. (2016, July). Constraint Acquisition with Recommendation Queries. In IJCAI (pp. 720-726).

[8] Daoudi, A., Lazaar, N., Mechqrane, Y., Bessiere, C., & Bouyakhf, E. H. (2015, November). Detecting types of variables for generalization in constraint acquisition. In 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 413-420). IEEE.

[9]Ait Addi, H., Bessiere, C., Ezzahir, R., & Lazaar, N. (2018). Time-bounded query generator for constraint acquisition. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15 (pp. 1-17). Springer International Publishing.

[10] Tsouros, D., Berden, S., & Guns, T. (2024, March). Learning to learn in interactive constraint acquisition. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 8, pp. 8154-8162)