×

Automated non-monotonic reasoning in System P. (English) Zbl 1496.68341

Summary: This paper presents a novel approach to automated reasoning in System P. System P axiomatizes a set of core properties that describe reasoning with defeasible assertions (defaults) of the form: if \(\alpha\) then normally (usually or typically) \( \beta \). A logic with approximate conditional probabilities is used for modeling default rules. That representation enables reducing the satisfiability problem for default reasoning to the (non)linear programming problem. The complexity of the obtained instances requires the application of optimization approaches. The main heuristic that we use is the Bee Colony Optimization (BCO). As an alternative to BCO, we use Simplex method and Fourier-Motzkin Elimination method to solve linear programming problems. All approaches are tested on a set of default reasoning examples that can be found in literature. The general impression is that Fourier-Motzkin Elimination procedure is not suitable for practical use due to substantially high memory usage and time consuming execution, the Simplex method is able to provide useful results for some of the tested examples, while heuristic approach turns out to be the most appropriate in terms of both success rate and time needed for reaching conclusions. In addition, the BCO method was tested on a set of randomly generated examples of larger dimensions, illustrating its practical usability.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68T27 Logic in artificial intelligence
90C59 Approximation methods and heuristics in mathematical programming

Software:

DeReS; dl2asp; CUDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramé, A.; Habet, D.; Toumi, D., Improving configuration checking for satisfiable random k-sat instances, Ann. Math. Artif. Intell., 79, 1-3, 5-24 (2017) · Zbl 1404.68136
[2] Adams, E.w.: The logic of conditionals: An application of probability to deductive logic. vol. 86. Springer (1975) · Zbl 0324.02002
[3] Benferhat, S.; Saffiotti, A.; Smets, P., Belief functions and default reasoning, Artif. Intell., 122, 1, 1-69 (2000) · Zbl 0948.68112
[4] Booth, R.; Paris, JB, A note on the rational closure of knowledge bases with both positive and negative knowledge, J. Log. Lang. Inf., 7, 2, 165-190 (1998) · Zbl 0906.03026
[5] Camazine, S.; Sneyd, J., A model of collective nectar source by honey bees: self-organization through simple rules, J. Theor. Biol., 149, 547-571 (1991)
[6] Chen, Y., Wan, H., Zhang, Y., Zhou, Y.: Dl2asp: Implementing default logic via answer set programming. In: European Workshop on Logics in Artificial Intelligence, pp. 104-116. Springer (2010) · Zbl 1306.68188
[7] Cholewinski, P.; Marek, VW; Truszczynski, M., Default reasoning system deres, KR, 96, 518-528 (1996)
[8] Cholewiński, P.; Marek, VW; Truszczyński, M.; Mikitiuk, A., Computing with default logic, Artif. Intell., 112, 1-2, 105-146 (1999) · Zbl 0996.68195
[9] Davidović, T.; Ramljak, D.; Šelmić, M.; Teodorović, D., Bee colony optimization for the p-center problem, Comput. Oper. Res., 38, 10, 1367-1376 (2011) · Zbl 1208.90103
[10] Davidović, T.; Teodorović, D.; Šelmić, M., Bee colony optimization Part I: The algorithm overview, Yugoslav J. Oper. Res., 25, 1, 33-56 (2015) · Zbl 1488.90244
[11] Djeffal, M.; Drias, H., Multilevel bee swarm optimization for large satisfiability problem instances, Intell. Data Eng. Autom. Learn.-IDEAL, 2013, 594-602 (2013)
[12] Dubois, D., Prade, H.: Possibilistic logic, preferential models, non-monotonicity and related issues. In: Proceedings of the 12th International joint conference on Artificial Intelligence, IJCAI ’91, vol. 91, pp. 419-424 (1991) · Zbl 0744.68116
[13] Eiter, T.; Lukasiewicz, T., Default reasoning from conditional knowledge bases: Complexity and tractable cases, Artif. Intell., 124, 2, 169-241 (2000) · Zbl 0952.68139
[14] Fagin, R.; Halpern, JY; Megiddo, N., A logic for reasoning about probabilities, Inf. Comput., 87, 1, 78-128 (1990) · Zbl 0811.03014
[15] Friedman, N.; Halpern, JY, Plausibility measures and default reasoning, J. ACM, 48, 4, 648-685 (2001) · Zbl 1127.68438
[16] Geffner, H., Default Reasoning: Causal and Conditional Theories, vol. 4 (1992), Cambridge: MIT Press, Cambridge
[17] Geffner, H.; Pearl, J., Conditional entailment: bridging two approaches to default reasoning, Artif. Intell., 53, 2, 209-244 (1992) · Zbl 1193.68235
[18] Georgakopoulos, G.; Kavvadias, D.; Papadimitriou, CH, Probabilistic satisfiability, J. Complex., 4, 1, 1-11 (1988) · Zbl 0647.68049
[19] Goldszmidt, M.; Pearl, J., On the consistency of defeasible databases, Artif. Intell., 52, 2, 121-149 (1991) · Zbl 0749.68026
[20] Goldszmidt, M., Pearl, J.: Rank-based systems: a simple approach to belief revision, belief update, and reasoning about evidence and actions. In: Proceedings of the 3rd International conference on principles of knowledge representation and reasoning, KR ’92, vol. 92, pp. 661-672 (1992)
[21] Hansen, P., Jaumard, B.: Probabilistic Satisfiability. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp. 321-367. Springer (2000) · Zbl 1015.68198
[22] Ikodinović, N.; Rašković, M.; Marković, Z.; Ognjanović, Z., A first-order probabilistic logic with approximate conditional probabilities, Log. J. IGPL, 22, 4, 539-564 (2014) · Zbl 1305.03021
[23] Jovanović, D., Mladenović, N., Ognjanović, Z.: Variable neighborhood search for the probabilistic satisfiability problem. Metaheuristics, 173-188 (2007) · Zbl 1171.90561
[24] Kavvadias, D.; Papadimitriou, CH, A linear programming approach to reasoning about probabilities, Ann. Math. Artif. Intell., 1, 1-4, 189-205 (1990) · Zbl 0878.68034
[25] Keisler, H.j.: Elementary calculus: an infinitesimal approach. Prindle Weber & Schmidt (1986) · Zbl 0655.26002
[26] Kilani, Y., Comparing the performance of the genetic and local search algorithms for solving the satisfiability problems, Appl. Soft Comput., 10, 1, 198-207 (2010)
[27] Kraus, S.; Lehmann, D.; Magidor, M., Nonmonotonic reasoning, preferential models and cumulative logics, Artif. Intell., 44, 1, 167-207 (1990) · Zbl 0782.03012
[28] Krüger, TJ; Davidović, T., Empirical analyis of the bee colony optmization method on 3-SAT problem. Proc. 43rd Symposium on Operations Research, SYM-OP-IS, 2016, 297-301 (2016)
[29] Lehmann, D., Another perspective on default reasoning, Ann. Math. Artif. Intell., 15, 1, 61-82 (1995) · Zbl 0857.68096
[30] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artif. Intell., 55, 1, 1-60 (1992) · Zbl 0762.68057
[31] Liao, T.; Aydın, D.; Stützle, T., Artificial bee colonies for continuous optimization: Experimental analysis and improvements, Swarm Intell, 7, 4, 327-356 (2013)
[32] Lü, Z.; Hao, JK, Adaptive memory-based local search for MAX-SAT, Appl. Soft Comput., 12, 8, 2063-2071 (2012)
[33] Lukasiewicz, T.: NMPROBLOG. http://www.kr.tuwien.ac.at/staff/lukasiew/nmproblog.html. [Online; accessed 20-August-2020]
[34] Lukasiewicz, T., Probabilistic default reasoning with conditional constraints, Ann. Math. Artif. Intell., 34, 1-3, 35-88 (2002) · Zbl 1002.68175
[35] Lukasiewicz, T.: Nonmonotonic probabilistic logics under variable- strength inheritance with overriding: Algorithms and implementation in nmproblog (2005) · Zbl 1082.03025
[36] Lukasiewicz, T., Weak nonmonotonic probabilistic logics, Artif. Intell., 168, 1, 119-161 (2005) · Zbl 1132.68737
[37] Lukasiewicz, T., Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation, Int. J. Approx. Reason., 44, 3, 301-321 (2007) · Zbl 1118.68167
[38] Makinson, D.: General Theory of Cumulative Inference. In: International Workshop on Non-Monotonic Reasoning, pp. 1-18. Springer (1988) · Zbl 0675.03007
[39] Marchiori, E., Rossi, C.: A flipping genetic algorithm for hard 3-SAT problems. In: Proceedings of the Genetic and Evolutionary Computation Conference, vol. 1, pp. 393-400 (1999)
[40] Marković, G.; Teodorović, D.; Aćimović-Raspopović, V., Routing and wavelength assignment in all-optical networks based on the bee colony optimization, AI Commun., 20, 4, 273-285 (2007) · Zbl 1185.90174
[41] Munawar, A.; Wahib, M.; Munetomo, M.; Akama, K., Hybrid of genetic algorithm and local search to solve max-sat problem using nvidia cuda framework, Genet. Program Evolvable Mach., 10, 4, 391-415 (2009)
[42] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 4, 308-313 (1965) · Zbl 0229.65053
[43] Nicolas, P., Saubion, F., Stéphan, I.: Gadel: a Genetic Algorithm to Compute Default Logic Extensions. In: ECAI, pp. 484-490 (2000)
[44] Nicolas, P.; Saubion, F.; Stéphan, I., Heuristics for a default logic reasoning system, Int. J. Artif. Intell. Tools, 10, 4, 503-523 (2001)
[45] Nicolas, P., Schaub, T.: The Xray System: an Implementation Platform for Local Query-Answering in Default Logics. In: Applications of Uncertainty Formalisms, pp. 354-378. Springer (1998)
[46] Nikolić, M.; Teodorović, D., Empirical study of the bee colony optimization (BCO) algorithm, Expert Syst. Appl., 40, 11, 4609-4620 (2013)
[47] Nikolić, M.; Teodorović, D., Empirical study of the Bee Colony Optimization (BCO) algorithm, Expert Syst. Appl., 40, 11, 4609-4620 (2013)
[48] Nilsson, NJ, Probabilistic logic, Artif. Intell., 28, 71-87 (1986) · Zbl 0589.03007
[49] Ognjanović, Z., Kratica, J., Milovanović, M.: A genetic algorithm for satisfiability problem in a probabilistic logic: A first report: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, pp. 805-816 (2001) · Zbl 1001.68566
[50] Ognjanović, Z.; Midić, U.; Kratica, J., A genetic algorithm for probabilistic SAT problem, Artif. Intell. Soft Comput.-ICAISC, 2004, 462-467 (2004) · Zbl 1058.68648
[51] Ognjanović, Z., Midić, U., MladenoviĆ, N.: A hybrid genetic and variable neighborhood descent for probabilistic SAT problem. In: Hybrid Metaheuristics, pp. 42-53. Springer (2005)
[52] Ognjanović, Z.; Rašković, M., Some first-order probability logics, Theor. Comput. Sci., 247, 1, 191-212 (2000) · Zbl 0954.03024
[53] Pearl, J.: Probabilistic semantics for nonmonotonic reasoning: a survey. In: Proceedings of the 1st International conference on principles of knowledge representation and reasoning, KR ’89, vol. 92, pp. 669-710 (1989) · Zbl 0703.03008
[54] Pearl, J., System, Z.: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In: Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 121-135. Morgan Kaufmann Publishers Inc (1990)
[55] Rana, S., Whitley, D.: Genetic Algorithm Behavior in the MAXSAT Domain. In: Parallel Problem Solving from Nature—PPSN V, pp. 785-794. Springer (1998)
[56] Rašković, M.; Marković, Z.; Ognjanović, Z., A logic with approximate conditional probabilities that can model default reasoning, Int. J. Approx. Reason., 49, 1, 52-66 (2008) · Zbl 1184.68520
[57] Reiter, R.: On reasoning by default. In: Proceedings of the 1978 workshop on Theoretical issues in natural language processing, pp. 210-218. Association for Computational Linguistics (1978)
[58] Reiter, R., A logic for default reasoning, Artif. Intell., 13, 1, 81-132 (1980) · Zbl 0435.68069
[59] Robinson, A.: “Non-standard analysis” Studies in Logic and the Foundations of Mathematics (1966) · Zbl 0151.00803
[60] Schaub, T., A new methodology for query answering in default logics via structure-oriented theorem proving, J. Autom. Reason., 15, 1, 95-165 (1995) · Zbl 0842.68075
[61] Schaub, T., Linke, T., Brüning, S., Nicolas, P.: XRay: User’s Guide & Reference Manual. http://www.cs.uni-potsdam.de/wv/xray/. [Online; accessed 20-August-2020]
[62] Selman, B., Kautz, H.A., Cohen, B.: Noise Strategies for Improving Local Search. In: AAAI, vol. 94, pp. 337-343 (1994)
[63] Stojanović, T.; Davidović, T.; Ognjanović, Z., Bee colony optimization for the satisfiability problem in probabilistic logic, Appl. Soft Comput., 31, 339-347 (2015)
[64] Stützle, T.; Hoos, H.; Roli, A., A Review of the Literature on Local Search Algorithms for MAX-SAT. Rapport Technique AIDA-01-02, Intellectics Group (2001), Germany: Darmstadt University of Technology, Germany
[65] Teodorović, D.: Bee Colony Optimization (BCO). In: Lim, C.P., Jain, L.C., Dehuri, S. (eds.) Innovations in Swarm Intelligence, pp. 39-60. Springer, Berlin (2009)
[66] Teodorović, D.; Dell’Orco, M., Mitigating traffic congestion: solving the ride-matching problem by bee colony optimization, Transport. Plan. Techn., 31, 135-152 (2008)
[67] Teodorović, D.; Šelmić, M.; Davidović, T., Bee colony optimization Part II: The application survey, Yugoslav J. Oper. Res., 25, 2, 185-219 (2015) · Zbl 1488.90244
[68] Villagra, M., Barán, B.: Ant colony optimization with adaptive fitness function for satisfiability testing. Log. Lang. Inf. Comput., 352-361 (2007) · Zbl 1213.68588
[69] Šelmić, M.; Teodorović, D.; Vukadinović, K., Locating inspection facilities in traffic networks: an artificial intelligence approach, Transport. Plan. Techn., 33, 481-493 (2010)
[70] Winston, WL; Venkataramanan, M.; Goldberg, JB, Introduction to Mathematical Programming, vol. 1 (2003), Pacific Grove: Thomson/Brooks/Cole Duxbury, Pacific Grove
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.