Greco, Gianluigi Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results. (English) Zbl 1129.68084 Ann. Math. Artif. Intell. 50, No. 1-2, 143-194 (2007). Summary: An extension of abduction is investigated where explanations are jointly computed by sets of interacting agents. On the one hand, agents are allowed to partially contribute to the reasoning task, so that joint explanations can be singled out even if each agent does not have enough knowledge for carrying out abduction on its own. On the other hand, agents maintain their autonomy in choosing explanations, each one being equipped with a weighting function reflecting its perception about the reliability of sets of hypotheses. Given that different agents may have different and possibly contrasting preferences on the hypotheses to be chosen, some reasonable notions of agents’ agreement are introduced, and their computational properties are thoroughly studied. As an example application of the framework discussed in the paper, it is shown how to handle data management issues in Peer-to-Peer systems and, specifically, how to provide a repair-based semantics to inconsistent ones. MSC: 68T27 Logic in artificial intelligence 68M14 Distributed systems 68N17 Logic programming 68T30 Knowledge representation Keywords:Abduction; Nonmonotonic reasoning; Data integration Software:IMPACT; Smodels; LAILA; Datalog PDFBibTeX XMLCite \textit{G. Greco}, Ann. Math. Artif. Intell. 50, No. 1--2, 143--194 (2007; Zbl 1129.68084) Full Text: DOI References: [1] Abdelbar, A.M.: Approximating cost-based abduction is NP-hard. Artif. Intell. 159, 231–239 (2004) · Zbl 1086.68132 [2] Apt, K.R., Rossi, F., Venable, K.B.: CP-nets and nash equilibria. In: Proceedings of the 3rd International Conference on Computational Intelligence, Robotics and Autonomous Systems (CIRAS’05) (2005) [3] Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: Proceedings of the 18th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS’99), pp. 68–79 (1999) · Zbl 1079.68026 [4] Arieli, O., Denecker, M., van Nuffelen, B., Bruynooghe, M.: Coherent integration of databases by abductive logic programming. J. Artif. Intell. Res. 21, 245–286 (2004) · Zbl 1080.68570 [5] Bertossi, L.E., Bravo, L.: Query answering in peer-to-peer data exchange systems. In: Proceedings of the EDBT Workshops, pp. 476–485 (2004) [6] Bertossi, L.E., Chomicki, J., Cortes, A., Gutierrez, C.: Consistent answers from integrated data sources. In: Proceedings of the 6th International Conference on Flexible Query Answering Systems (FQAS’02), pp. 71–85 (2002) [7] Bracciali, A., Mancarella, P., Stathis, K., Toni, F.: On modelling multi-agent systems declaratively. In: Proceedings of the 2nd International Workshop on Declarative Agent Languages and Technologies (DALT’04), pp. 53–68 (2004) [8] Bravo, L., Bertossi, L.E.: Logic programming for consistently querying data integration systems. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), pp. 10–15 (2003) [9] Brewka, G., Niemelä, I., Truszczynski, M.: Answer set optimization. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), pp. 867–872 (2003) [10] Buccafurri, F., Gottlob, G.: Multiagent compromises, joint fixpoints, and stable models. In: Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part I, pp. 561–585. Springer, London, UK (2002) · Zbl 1012.68191 [11] Calì, A., Lembo, D., Rosati, R.: On the decidability and complexity of query answering over inconsistent and incomplete databases. In: Proceedings of the 22nd ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS’03), pp. 260–271 (2003) [12] Calì, A., Lembo, D., Rosati, R.: Query rewriting and answering under constraints in data integration systems. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), pp. 16–21 (2003) [13] Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Logical foundations of peer-to-peer data integration. In: Proceedings of the 23rd ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS’04), pp. 241–251 (2004) [14] Charniak, E., Shimony, S.: Cost-based abduction and MAP explanations. Artif. Intell. 66, 345–374 (1994) · Zbl 0807.68079 [15] Chopra, S., Meyer, T., Ghose, A.: Social choice, merging and elections. In: Proceedings of 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’01), pp. 466–477 (2001) · Zbl 1001.68559 [16] Ciampolini, A., Lamma, E., Mello, P., Toni, F., Torroni, P.: Cooperation and competition in ALIAS: a logic framework for agents that negotiate. Ann. Math. Artif. Intell. 37(1–2), 65–91 (2003) · Zbl 1023.68095 [17] Ciampolini, A., Lamma, E., Mello, P., Torroni, P.: LAILA: a language for coordinating abductive reasoning among logic agents. Comput. Lang. 27(4), 137–161 (2001) · Zbl 0997.68015 [18] Console, L., Dupre, D.T., Torasso, P.: On the relationship between abduction and deduction. J. Log. Comput. 1(5), 661–690 (1991) · Zbl 0734.68085 [19] Cox, J.S., Durfee, E.H., Bartold, T.: A distributed framework for solving the multiagent plan coordination problem. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’05), pp. 821–827 (2005) [20] Davin, J., Modi, P.J.: Hierarchical variable ordering for multiagent agreement problems. In: Proceedings of the 7th International Workshop on Distributed Constraint Reasoning (DCR ’06), pp. 1433–1435 (2006) [21] De Vos, M., Crick, T., Padget, J., Brain, M., Cliffe, O., Needham, J.: Multi-agent platform using ordered choice logic programming. In: Proceedings of the 3rd International Workshop on Declarative Agent Languages and Technologies (DALT’05), pp. 67–83 (2005) [22] De Vos, M., Vermeir, D.: Choice logic programs and Nash equilibria in strategic games. In: Proceedings of the 13th International Workshop and 8th Annual Conference of the EACSL on Computer Science Logic (CSL’99), pp. 266–276 (1999) · Zbl 0952.68030 [23] De Vos, M., Vermeir, D.: Extending answer sets for logic programming agents. Ann. Math. Artif. Intell. 42(1–3), 103–139 (2004) · Zbl 1079.68095 [24] Denecker, M., Kakas, A.C.: Abduction in logic programming. In: Lecture Notes in Computer Science, Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part I, vol. 2407, pp. 402–436 (2002) · Zbl 1012.68503 [25] Dix, J., Zhang, Y.: IMPACT: a multi-agent framework with declarative semantics. In: Multi-agent Programming, LNAI 3346. Springer, Berlin Heidelberg New York (2005) [26] Domshlak, C., Rossi, F., Venable, K.B., Walsh, T.: Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), pp. 215–220 (2003) [27] Dung, P.M.: Negation as hypotheses: an abductive foundation for logic programming. In: Proceedings of the 8th International Conference on Logic Programming (ICLP’91), pp. 3–17 (1991) [28] Eiter, T., Fink, M., Greco, G., Lembo., D.: Efficient evaluation of logic programs for querying data integration systems. In: Proceedings of the 19th International Conference on Logic Programming (ICLP’03), pp. 348–364 (2003) · Zbl 1204.68080 [29] Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. Assoc. Comput. Mach. 42(1), 3–42 (1995) · Zbl 0886.68121 [30] Eiter, T., Gottlob, G., Mannila, H.: Disjunctive datalog. ACM Trans. Database Syst. 22(3), 364–418 (1997) [31] Eiter, T., Subrahmanian, V.S., Pick, G.: Heterogeneous active agents I: semantics. Artif. Intell. (1–2)(108), 179–255 (1999) · Zbl 0914.68123 [32] Endriss, U., Mancarella, P., Sadri, F., Terreni, G., Toni, F.: The CIFF proof procedure for abductive logic programming with constraints. In: Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA’04), pp. 31–43 (2004) · Zbl 1111.68674 [33] Faratin, P., van de Walle, B.: Agent preference relations: strict, indifferent, and incomparable. In: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’02), pp. 1317–1324 (2002) [34] Franconi, E., Kuper, G., Lopatenko, A., Serafini, L.: A robust logical and computational characterisation of peer-to-peer database systems. In: Proceedings of the 1st International Workshop on Databases, Information Systems and Peer-to-peer Computing (DBISP2P’03), pp. 64–76 (2003) [35] Gavanelli, M., Lamma, E., Mello, P., Torroni, P.: An abductive framework for information exchange in multi-agent systems. In: Proceedings of the 4th International Workshop on Computational Logic in Multi-agent Systems (CLIMA IV), pp. 34–52 (2004) · Zbl 1110.68503 [36] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Proceedings of the 5th International Conference on Logic Programming (ICLP’88), pp. 1070–1080 (1988) [37] Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: hard and easy games. In: Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK’03), pp. 215–230 (2003) · Zbl 1134.91312 [38] Gottlob, G., Leone, N., Veith, H.: Succinctness as a source of complexity in logical formalisms. Ann. Pure Appl. Logic 97(1), 231–260 (1999) · Zbl 0933.03048 [39] Greco, G., Greco, S., Zumpano, E.: A logic programming approach to the integration, repairing and querying of inconsistent databases. In: Proceedings of the 17th International Conference on Logic Programming (ICLP’01), pp. 348–364 (2001) · Zbl 1053.68564 [40] Greco, G., Greco, S., Zumpano, E.: A logical framework for querying and repairing inconsistent databases. IEEE Trans. Knowl. Data Eng. 15(6), 1389–1408 (2003) · Zbl 05109769 [41] Greco, G., Scarcello, F.: On the complexity of computing peer agreements for consistent query answering in peer-to-peer data integration systems. In: Proceedings of 14th ACM Conference on Information and Knowledge Management (CIKM’05), pp. 36–43 (2005) [42] Hindriks, K.V., de Boer, F.S., van der Hoek, W., Meyer, J.J.C.: Semantics of communicating agents based on deduction and abduction. In: Lecture Notes in Computer Science, Issues in Agent Communication, vol. 1916, pp. 63–79 (2000) [43] Johnson, D.S.: A catalog of complexity classes. MIT Press, Cambridge, MA, USA (1990) · Zbl 0900.68246 [44] Kakas, A.C., Mancarella, P.: Generalized stable models: a semantics for abduction. In: Proceedings of the 9th European Conference on Artificial Intelligence (ECAI’90), pp. 385–391 (1990) [45] Kakas, A.C., Moraitis, P.: Argumentation based decision making for autonomous agents. In: Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’03), pp. 883–890 (2003) [46] Kakas, A.C., van Nuffelen, B., Denecker, M.: A-System: problem solving through abduction. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01), pp. 591–596 (2001) [47] Kraus, S.: Negotiation and cooperation in multi-agent environments. Artif. Intell. 94(1–2), 79–97 (1997) · Zbl 0904.68168 [48] Lang, J.: Some representation and computational issues in social choice. In: Proceedings of 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’05), pp. 15–26 (2005) · Zbl 1122.68657 [49] Lenzerini, M.: Principles of P2P data integration. In: Proceedings of the 3rd International Workshop on Data Integration Over the Web (DiWeb’04), pp. 7–21 (2004) [50] Leone, N., Pfeifer, G., Faber, W., Calimeri, F., Dell’Armi, T., Eiter, T., Gottlob, G., Ianni, G., Ielpa, G., Koch, C., Perri, S., Polleres, A.: The DLV System. In: Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA’02), pp. 537–540 (2002) · Zbl 1014.68871 [51] Lin, F., You, J.H.: Abduction in logic programming: a new definition and an abductive procedure based on rewriting. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01), pp. 655–666 (2001) [52] Mailler, R., Lesser, V.: Solving distributed constraint optimization problems using cooperative mediation. In: Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’04), pp. 438–445 (2004) [53] Modi, P.J., Veloso, M.: Bumping strategies for the multiagent agreement problem. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS’05), pp. 390–396 (2005) [54] Mura, P.L., Shoham, Y.: Conditional, hierarchical, multi-agent preferences. In: Proceedings of 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK’98), pp. 215–224 (1998) [55] Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286–295 (1951) · Zbl 0045.08202 [56] van Nieuwenborgh, D., Heymans, S., Vermeir, D.: On programs with linearly ordered multiple preferences. In: Proceedings of the 20th International Conference on Logic Programming (ICLP’04), pp. 180–194 (2004) · Zbl 1104.68389 [57] van Nuffelen, B., Cortés-Calabuig, A., Denecker, M., Arieli, O., Bruynooghe, M.: Data integration using ID-logic. In: Proceedings of the 16th International Conference on Advanced Information Systems Engineering (CAiSE’04), pp. 67–81 (2004) [58] Osborne, M., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge, MA, USA (1994) · Zbl 1194.91003 [59] Papadimitriou, C.: Computational Complexity. Addison-Wesley Publishing Company, Reading, MA, USA (1995) · Zbl 0557.68033 [60] Parsons, S., Wooldridge, M.: Game theory and decision theory in multi-agent systems. Auton. Agent. Multi-Agent Syst. 5(3), 243–254 (1994) · Zbl 05387378 [61] Peirce, C.S.: Abduction and induction. In: Philosophical Writings of Peirce, pp. 150–156 (1955) [62] Peltz, C.: Web services orchestration and choreography. IEEE Comput. 36(10), 46–52 (2003) [63] Perri, S., Scarcello, F., Leone, N.: Abductive logic programs with penalization: semantics, complexity and implementation. Theory and Practice of Logic Programming 5(1–2), 123–159 (2005) · Zbl 1093.68020 [64] Petcu, A., Faltings, B.: A distributed, complete method for multi-agent constraint optimization. In: Proceedings of the 5th International Workshop on Distributed Constraint Reasoning (DCR’04), IC/2004/65 (2004) [65] Pivkina, I., Pontelli, E., Son, T.C.: Revising knowledge in multi-agent systems using revision programming with preferences. In: Proceedings of the 4th International Workshop on Computational Logic in Multi-agent Systems (CLIMA IV), pp. 134–158 (2004) · Zbl 1110.68508 [66] Przymusinska, H., Przymusinski, T.: Semantic issues in deductive databases and logic programs. In: Formal Techniques in Artificial Intelligence, pp. 321–367 (1990) · Zbl 0704.68034 [67] Rossi, F., Venable, K., Walsh, T.: mCP nets: representing and reasoning with preferences on multiple agents. In: Proceedings of the 19th Conference on Artificial Intelligence (AAAI’04), pp. 729–734 (2004) [68] Sadri, F., Toni, F., Torroni, P.: An abductive logic programming architecture for negotiating agents. In: Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA’02), pp. 419–431 (2002) · Zbl 1013.68205 [69] Sandholm, T.W.: Distributed Rational Decision Making. MIT Press, Cambridge, MA, USA (1999) [70] Schlosser, M.T., Sintek, M., Decker, S., Nejdl, W.: HyperCuP – hypercubes, ontologies, and efficient search on peer-to-peer networks. In: Proceedings of the 1st International Workshop on Agents and Peer-to-peer Computing (AP2PC’02), pp. 112–124 (2002) · Zbl 1023.68834 [71] Schroeder, M., de Almeida Mora, I., Pereirat, L.M.: A deliberative and reactive diagnosis agent based on logic programming. In: Proceedings of the 8th International Conference on Tools with Artificial Intelligence (ICTAI’96), pp. 436 (1996) [72] Syrjänen, T., Niemelä, I.: The Smodels system. In: Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’01), pp. 434–438 (2001) · Zbl 1010.68797 [73] Yager, R.R.: Fusion of multi-agent preference orderings. Fuzzy Sets Syst. 117(1), 1–12 (2001) · Zbl 1032.91045 [74] Yokoo, M., Hirayama, K.: Algorithms for distributed constraint satisfaction: a review. Auton. Agent. Multi-Agent Syst. 3(2), 185–207 (2000) · Zbl 05387453 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.