{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T12:23:32Z","timestamp":1763727812352,"version":"3.40.5"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T00:00:00Z","timestamp":1600646400000},"content-version":"unspecified","delay-in-days":20,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Efficient decision-making over continuously changing data is essential for many application domains such as cyber-physical systems, industry digitalization, etc. Modern stream reasoning frameworks allow one to model and solve various real-world problems using incremental and continuous evaluation of programs as new data arrives in the stream. Applied techniques use, e.g., Datalog-like materialization or truth maintenance algorithms to avoid costly re-computations, thus ensuring low latency and high throughput of a stream reasoner. However, the expressiveness of existing approaches is quite limited and, e.g., they cannot be used to encode problems with constraints, which often appear in practice. In this paper, we suggest a novel approach that uses the Conflict-Driven Constraint Learning (CDCL) to efficiently update legacy solutions by using intelligent management of learned constraints. In particular, we study the applicability of reinforcement learning to continuously assess the utility of learned constraints computed in previous invocations of the solving algorithm for the current one. Evaluations conducted on real-world reconfiguration problems show that providing a CDCL algorithm with relevant learned constraints from previous iterations results in significant performance improvements of the algorithm in stream reasoning scenarios.<\/jats:p>","DOI":"10.1017\/s147106842000037x","type":"journal-article","created":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T05:25:42Z","timestamp":1600665942000},"page":"625-640","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":9,"title":["Managing caching strategies for stream reasoning with reinforcement learning"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5617-5286","authenticated-orcid":false,"given":"CARMINE","family":"DODARO","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6003-6345","authenticated-orcid":false,"given":"THOMAS","family":"EITER","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6745-2197","authenticated-orcid":false,"given":"PAUL","family":"OGRIS","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0286-0958","authenticated-orcid":false,"given":"KONSTANTIN","family":"SCHEKOTIHIN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,9,21]]},"reference":[{"key":"S147106842000037X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.04.003"},{"volume-title":"In IJCAI","year":"2015","author":"Beck","key":"S147106842000037X_ref10"},{"key":"S147106842000037X_ref33","unstructured":"33. Sutton, R. S. and Barto, A. G. 2018. Reinforcement Learning: An Introduction, 2nd ed."},{"key":"S147106842000037X_ref18","unstructured":"18. Gaschnig, J. 1979. Performance measurement and analysis of certain search algorithms. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, USA."},{"key":"S147106842000037X_ref25","first-page":"2318","article-title":"The effect of restarts on the efficiency of clause learning","author":"Huang","year":"2007","journal-title":"In IJCAI."},{"key":"S147106842000037X_ref31","unstructured":"31. Silva, J. P. M. and Sakallah, K. A. 1996. Conflict analysis in search algorithms for satisfiability. In ICTAI. IEEE Computer Society, 467\u2013469."},{"key":"S147106842000037X_ref17","doi-asserted-by":"crossref","first-page":"1466","DOI":"10.1109\/TNET.2011.2181864","article-title":"Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations","volume":"5","author":"Gai","year":"2012","journal-title":"IEEE\/ACM Transactions on Networking 20"},{"key":"S147106842000037X_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068419000292"},{"key":"S147106842000037X_ref23","unstructured":"23. Gomes, C. P. , Selman, B. , and Kautz, H. A. 1998. Boosting combinatorial search through randomization. In AAAI\/IAAI. AAAI Press\/The MIT Press, 431\u2013437."},{"key":"S147106842000037X_ref22","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1613\/jair.5512","article-title":"Complexity of n-queens completion","author":"Gent","year":"2017","journal-title":"J. Artif. Intell. Res. 59"},{"key":"S147106842000037X_ref4","unstructured":"4. Anantharam, V. , Varaiya, P. , and Walrand, J. 1987. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewards. IEEE Trans. on Automatic Control 32, 11, 968\u2013976."},{"key":"S147106842000037X_ref3","doi-asserted-by":"crossref","unstructured":"3. Alviano, M. , Dodaro, C. , Leone, N. , and Ricca, F. 2015. Advances in WASP. In LPNMR. 40\u201354.","DOI":"10.1007\/978-3-319-23264-5_5"},{"key":"S147106842000037X_ref8","doi-asserted-by":"crossref","unstructured":"8. Bazoobandi, H. R. , Beck, H. , and Urbani, J. 2017. Expressive stream reasoning with laser. In ISWC. 87\u2013103.","DOI":"10.1007\/978-3-319-68288-4_6"},{"key":"S147106842000037X_ref9","unstructured":"9. Beck, H. , Bierbaumer, B. , Dao-Tran, M. , Eiter, T. , Hellwagner, H. , and Schekotihin, K. 2017. Stream reasoning-based control of caching strategies in CCN routers. In ICC. IEEE, 1\u20136."},{"key":"S147106842000037X_ref7","first-page":"1","article-title":"On the glucose SAT solver","volume":"1","author":"Audemard","year":"2018","journal-title":"Int. J. Artif. Intell. Tools 27,"},{"key":"S147106842000037X_ref16","doi-asserted-by":"crossref","first-page":"974","DOI":"10.1017\/S1471068419000309","article-title":"A distributed approach to LARS stream reasoning (system paper)","volume":"5","author":"Eiter","year":"2019","journal-title":"Theory Pract. Log. Program. 19,"},{"key":"S147106842000037X_ref28","doi-asserted-by":"crossref","unstructured":"28. Pipatsrisawat, K. and Darwiche, A. 2007. A lightweight component caching scheme for satisfiability solvers. In SAT. 294\u2013299.","DOI":"10.1007\/978-3-540-72788-0_28"},{"key":"S147106842000037X_ref29","doi-asserted-by":"crossref","first-page":"13260","DOI":"10.1109\/ACCESS.2019.2891969","article-title":"A roadmap toward the resilient internet of things for cyber-physical systems","author":"Ratasich","year":"2019","journal-title":"IEEE Access 7"},{"key":"S147106842000037X_ref32","unstructured":"32. Sutton, R. S. 1995. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In NIPS. MIT Press, 1038\u20131044."},{"key":"S147106842000037X_ref2","doi-asserted-by":"crossref","unstructured":"2. Alviano, M. , Dodaro, C. , Faber, W. , Leone, N. , and Ricca, F. 2013. WASP: A native ASP solver based on constraint learning. In LPNMR. 54\u201366.10.1007\/978-3-642-40564-8_6","DOI":"10.1007\/978-3-642-40564-8_6"},{"key":"S147106842000037X_ref6","first-page":"399","article-title":"Predicting learnt clauses quality in modern SAT solvers","author":"Audemard","year":"2009","journal-title":"In IJCAI."},{"key":"S147106842000037X_ref21","unstructured":"21. Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In ICLP\/SLP. MIT Press, 1070\u20131080."},{"key":"S147106842000037X_ref26","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1609\/aimag.v37i3.2672","article-title":"Grounding and solving in answer set programming","volume":"3","author":"Kaufmann","year":"2016","journal-title":"AI Magazine 37"},{"key":"S147106842000037X_ref14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0004-3702(86)90080-9","article-title":"An assumption-based TMS","volume":"2","author":"de Kleer","year":"1986","journal-title":"Artif. Intell. 28"},{"key":"S147106842000037X_ref34","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1017\/S1471068411000500","article-title":"XSB: extending prolog with tabled logic programming","volume":"1","author":"Swift","year":"2012","journal-title":"Theory Pract. Log. Program. 12,"},{"key":"S147106842000037X_ref12","first-page":"744","article-title":"Ticker: A system for incremental asp-based stream reasoning","volume":"5","author":"Beck","year":"2017","journal-title":"TPLP 17"},{"key":"S147106842000037X_ref24","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.compind.2016.05.006","article-title":"Design, modelling, simulation and integration of cyber physical systems: Methods and applications","author":"Hehenberger","year":"2016","journal-title":"Comput. Ind. 82"},{"key":"S147106842000037X_ref27","doi-asserted-by":"crossref","unstructured":"27. Nadel, A. and Ryvchin, V. 2012. Efficient SAT solving under assumptions. In SAT. 242\u2013255.","DOI":"10.1007\/978-3-642-31612-8_19"},{"key":"S147106842000037X_ref30","unstructured":"30. Rossi, D. and Rossini, G. 2012. On sizing CCN content stores by exploiting topological information. In INFOCOM Workshops. IEEE, 280\u2013285."},{"key":"S147106842000037X_ref5","doi-asserted-by":"crossref","unstructured":"5. Aschinger, M. , Drescher, C. , Friedrich, G. , Gottlob, G. , Jeavons, P. , Ryabokon, A. , and Thorstensen, E. 2011. Optimization methods for the partner units problem. In CPAIOR. 4\u201319.","DOI":"10.1007\/978-3-642-21311-3_4"},{"key":"S147106842000037X_ref20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1017\/S1471068418000054","article-title":"Multi-shot ASP solving with clingo","volume":"1","author":"Gebser","year":"2019","journal-title":"Theory Pract. Log. Program. 19,"},{"key":"S147106842000037X_ref1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1147\/rd.281.0002","article-title":"Optimizing preventive service of software products","volume":"1","author":"Adams","year":"1984","journal-title":"IBM J. Res. Dev. 28"},{"key":"S147106842000037X_ref15","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0004-3702(79)90008-0","article-title":"A truth maintenance system","volume":"3","author":"Doyle","year":"1979","journal-title":"Artif. Intell. 12"},{"key":"S147106842000037X_ref19","doi-asserted-by":"crossref","unstructured":"19. Gebser, M. , Grote, T. , Kaminski, R. , Obermeier, P. , Sabuncu, O. , and Schaub, T. 2012. Stream reasoning with answer set programming: Preliminary report. In KR. AAAI Press.","DOI":"10.1007\/978-3-642-20895-9_7"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106842000037X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,14]],"date-time":"2021-01-14T08:47:11Z","timestamp":1610614031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106842000037X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S147106842000037X"],"URL":"https:\/\/doi.org\/10.1017\/s147106842000037x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}