Sage Journals: Discover world-class research

Abstract

Several efficient SAT-based methods for computing the preferred extensions in (abstract) argumentation frameworks (AF) are proposed lately. However, only complete SAT solvers have been exploited so far. It is a natural question that how the appealing stochastic local search (SLS) approach could advance the performance. In this paper, we developed two SLS algorithms for computing the preferred extensions in AF, and a complete one which combines the strength of the better one with complete SAT solvers. Our first SLS algorithm Ite-CCA_EP works by calling an SLS SAT solver Swcca in an iterative manner with adaptive heuristics. Our second SLS algorithm Inc-CCA_EP realized an incremental version of Swcca, specially designed for computing the preferred extensions in AF. Though Ite-CCA_EP and Inc-CCA_EP do not guarantee completeness, they notably outperform a state-of-the-art solver consistently on most benchmarks with non-empty preferred extensions. Experimental results also show that Inc-CCA_EP is more efficient than Ite-CCA_EP, which inspired the design of a novel complete algorithm called CCASAT_EP that uses Inc-CCA_EP as an efficient preprocessor. Further experiments show that CCASAT_EP is competitive to the state-of-the-art methods.

Keywords

Abstract argumentation stochastic local search preferred semantics

Get full access to this article

View all access options for this article.

References

Atseria,

J.K.

Fichte and

Thureley, Clause-learning algorithms with many restarts and bounded-width resolution, Journal of Artificial Intelligence Research 40 (2011), 353–373.

Balint and

Frohlich, Improving stochastic local search for SAT with a new probability distribution, in: Proceedings of the 13th Theory and Applications of Satisfiability Testing, Springer, Edinburgh, UK, 2010, pp. 10–15.

A.L.

Barabasi and

Albert, Emergence of scaling in random networks, Science 286(5439) (1999), 509–512. doi:10.1126/science.286.5439.509.

Besnard and

Doutre, Checking the acceptability of a set of arguments, in: Proceedings of the 10th International Workshop on Non-Monotonic Reasoning, Whistler, Canada, 2004, pp. 59–64.

Bistarelli,

Rossi and

Santini, Efficient solution for credulous/sceptical acceptance in lower-order Dung’s semantic, in: Proceedings of the 26th IEEE International Conference on Tools with Artificial Intelligence, IEEE Computer Society, Limassol, Cyprus, 2014, pp. 800–804.

Bistarelli,

Rossi and

Santini, Benchmarking hard problems in random abstract AFs: The stable semantics, in: Proceedings of the 5th Conference on Computational Models of Argument, IOS Press, Pitlochry, Scotland, 2014.

Bistarelli,

Rossi and

Santini, A first comparison of abstract argumentation reasoning-tools, in: Proceedings of the 21st European Conference on Artificial Intelligence, IOS Press, Prague, Czech Republic, 2014, pp. 969–970.

Bistarelli,

Rossi and

Santini, A comparative test on the enumeration of extension in abstract argumentation, Fundamenta Informaticae 140(3–4) (2015), 263–278. doi:10.3233/FI-2015-1254.

M.L.

Bonet and

Buss, Improved separations of regular resolution from clause learning proof systems, Journal of Artificial Intelligence Research 49 (2014), 669–703.

10.

Cai,

Luo,

Thornton and

Su, Tailing local search for partial MaxSAT, in: Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI Press, Québec City, Québec, Canada, 2014, pp. 2623–2629.

11.

Cai and

Su, Configuration checking with aspiration in local search for SAT, in: Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI Press, Toronto, Ontario, Canada, 2012, pp. 434–440.

12.

Cai,

Su and

Sattar, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artificial Intelligence 75(9–10) (2011), 1672–1696. doi:10.1016/j.artint.2011.03.003.

13.

Cerutti,

P.E.

Dunne,

Giacomin and

Vallati, Computing preferred extensions in abstract argumentation: A SAT-based approach, in: Proceedings of the 2nd Theory and Applications of Formal Argumentation, Springer, Beijing, China, 2013, pp. 176–193.

14.

Cerutti,

Giacomin and

Vallati, ArgSemSAT: Solving argumentation problems using SAT, in: Proceedings of the 5th International Conference on Computational Models of Argument, IOS Press, Scottish Highlands, UK, 2014, pp. 455–456.

15.

Cerutti,

Giacomin,

Vallati and

Zanella, An SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation, in: Proceedings of the 14th Principles of Knowledge Representation and Reasoning, AAAI Press, Vienna, Austria, 2014.

16.

Charwat,

Dvorak,

S.A.

Gaggl,

J.P.

Wallner and

Woltran, Methods for solving reasoning problems in abstract argumentation – a survey, Artificial Intelligence 220 (2015), 28–63. doi:10.1016/j.artint.2014.11.008.

17.

Dimopoulos and

Sideris, Towards local search for answer sets, in: Proceedings of the 18th International Conference on Logic Programming, Springer, Copenhagen, Denmark, 2002, pp. 363–377.

18.

P.M.

Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–358. doi:10.1016/0004-3702(94)00041-X.

19.

Dvorak,

Jarvisalo,

J.P.

Wallner and

Woltran, Complexity-sensitive decision procedures for abstract argumentation, Artificial Intelligence 206 (2014), 53–78. doi:10.1016/j.artint.2013.10.001.

20.

Erdős and

Rényi, On the evolution of random graphs, Bulletin of the Institute of International Statistics 38(4) (1961), 343–347.

21.

Koenig and

Likhachev, D* Lite, in: Proceedings of the 18th AAAI Conference on Artificial Intelligence, AAAI Press, Edmonton, Alberta, Canada, 2002, pp. 476–483.

22.

Laitinen,

T.A.

Junttila and

Niemelä, Extending clause learning SAT solvers with complete parity reasoning, in: Proceedings of the IEEE 24th International Conference on Tools with Artificial Intelligence, IEEE Computer Society, Athens, Greece, 2012, pp. 65–72.

23.

Li,

Jiang and

Xu, Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique, in: Proceedings of the 9th International Conference on Learning and Intelligent Optimization, Springer, Lille, France, 2015, pp. 268–274. doi:10.1007/978-3-319-19084-6_26.

24.

Lin,

Sun and

Zhang, Theorem proving based on the extension rule, Journal of Automated Reasoning 31(1) (2003), 11–21. doi:10.1023/A:1027339205632.

25.

Luo,

Cai,

Su and

Wu, Clause states based configuration checking in local search for satisfiability, IEEE Transactions on Cybernetics 45(5) (2015), 1014–1027.

26.

Luo,

Cai,

Wu,

Jie and

Su, CCLS: An efficient local search algorithm for weighted maximum satisfiability, IEEE Transactions on Computers 64(7) (2015), 1830–1843. doi:10.1109/TC.2014.2346196.

27.

Martel and

Nguyen, Analyzing Kleinberg’s (and other) small-world models, in: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, ACM, Newfoundland, Canada, 2004, pp. 179–188.

28.

D.D.

Niu,

Liu and

Lü, A new stochastic local search approach for computing preferred extensions of abstract argumentation, in: Proceedings of the 22nd European Conference on Artificial Intelligence, IOS Press, The Hague, The Netherlands, 2016, pp. 1652–1653.

29.

Nofal,

Atkinson and

P.E.

Dunne, Algorithms for decision problems in argument systems under preferred semantics, Artificial Intelligence 207 (2014), 23–51. doi:10.1016/j.artint.2013.11.001.

30.

Oral and

Polat, MOD* Lite: An incremental path planning algorithm taking care of multiple objectives, IEEE Transactions on Cybernetics 46(1) (2016), 245–257. doi:10.1109/TCYB.2015.2399616.

31.

Pipatsrisawat and

Darwiche, On the power of clause-learning SAT solvers with restarts, in: Proceedings of the 15th Principles and Practice of Constraint Programming, Springer, Lisbon, Portugal, 2009, pp. 654–668.

32.

Pipatsrisawat and

Darwiche, On the power of clause-learning SAT solvers as resolution engines, Artificial Intelligence 175 (2011), 512–525. doi:10.1016/j.artint.2010.10.002.

33.

Thimm and

Villata, The first international competition on computational models of argumentation: Results and analysis, Artificial Intelligence 252 (2017), 267–294. doi:10.1016/j.artint.2017.08.006.

34.

D.A.D.

Tompkins,

Balint and

H.H.

Hoos, Captain jack: New variable selection heuristics in local search for SAT, in: Proceedings of the 14th Theory and Applications of Satisfiability Testing, Springer, Ann Arbor, MI, USA, 2011, pp. 302–316.

New stochastic local search approaches for computing preferred extensions of abstract argumentation

Abstract

Keywords

Get full access to this article

References