Matching qualitative constraint networks with online reinforcement learning

M.C. Chipofya*

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

6 Downloads (Pure)


Local Compatibility Matrices (LCMs) are mechanisms for computing heuristics for graph matching that are particularly suited for matching qualitative constraint networks enabling the transfer of qualitative spatial knowledge between qualitative reasoning systems or agents. A system of LCMs can be used during matching to compute a pre-move evaluation, which acts as a prior optimistic estimate of the value of matching a pair of nodes, and a post-move evaluation which adjusts the prior estimate in the direction of the true value upon completing the move. We present a metaheuristic method that uses reinforcement learning to improve the prior estimates based on the posterior evaluation. The learned values implicitly identify unprofitable regions of the search space. We also present data structures that allow a more compact implementation, limiting the space and time complexity of our algorithm.
Original languageEnglish
Number of pages14
Publication statusPublished - 29 Sept 2016
Externally publishedYes
Event2nd Global Conference on Artificial Intelligence - Berlin, Germany
Duration: 29 Sept 20162 Oct 2016
Conference number: 2


Conference2nd Global Conference on Artificial Intelligence
Abbreviated titleGCAI 2016
Internet address


  • ITC-CV


Dive into the research topics of 'Matching qualitative constraint networks with online reinforcement learning'. Together they form a unique fingerprint.

Cite this