Agenda control for heterogeneous reasoners. (English) Zbl 1101.68450
Summary: As artificial intelligence techniques are maturing and being deployed in large applications, the problem of specifying control and reasoning strategies is regaining attention. Complex AI systems tend to comprise a suite of modules, each of which is capable of solving a different aspect of the overall problem, and each of which may incorporate a different reasoning paradigm. The orchestration of such heterogeneous problem solvers can be divided into two subproblems: (1) When and how are various reasoning modes invoked? and (2) How is information passed between various reasoning modes? In this paper, we explore some solutions to this problem. In particular, we describe a logic programming system that is based on three ideas: equivalence of declarative and operational semantics, declarative specification of control information, and smoothness of interaction with non-logic-based programs. Meta-level predicates are used to specify control information declaratively, compensating for the absence of procedural constructs that usually facilitate formulation of efficient programs. Knowledge that has been derived in the course of the current inference process can at any time be passed to non-logic-based program modules. Traditional SLD inference engines maintain only the linear path to the current state in the SLD search tree: formulae that have been proved on this path are implicitly represented in a stack of recursive calls to the inference engine, and formulae that have been proved on previous, unsuccessful paths are lost altogether. In our system, previously proved formulae are maintained explicitly and therefore can be passed to other reasoning modules. As an application example, we show how this inference system acts as the knowledge representation and reasoning framework of PRET–a program that automates system identification.
MSC:
| 68N17 | Logic programming |
References:
| [1] | Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artificial Intelligence, 116, January (2000) · Zbl 0939.68827 |
| [2] | A. Barrett, D. Christianson, M. Friedman, C. Kwok, K. Golden, S. Penberthy, Y. Sun, D. Weld, UCPOP user’s manual (version 4.0), Technical Report 93-09-06d, Department of Computer Science and Engineering, University of Washington, November 1995; A. Barrett, D. Christianson, M. Friedman, C. Kwok, K. Golden, S. Penberthy, Y. Sun, D. Weld, UCPOP user’s manual (version 4.0), Technical Report 93-09-06d, Department of Computer Science and Engineering, University of Washington, November 1995 |
| [3] | Beckstein, C.; Kim, M., Generalized Earley deduction and its correctness, (Christaller, T., GWAI-91: 15th German Workshop on Artificial Intelligence. GWAI-91: 15th German Workshop on Artificial Intelligence, Informatik-Fachberichte, vol. 285 (1991), Springer: Springer Berlin, Heidelberg), 1-10 |
| [4] | C. Beckstein, R. Stolle, G. Tobermann, Meta-programming for generalized Horn clause logic, in: Fifth International Workshop on Metaprogramming and Metareasoning in Logic (META-96), Bonn, Germany, 1996, pp. 27-42. Available from <http://www.ksl.stanford.edu/people/stolle/Papers/meta96.{pdf,ps}; C. Beckstein, R. Stolle, G. Tobermann, Meta-programming for generalized Horn clause logic, in: Fifth International Workshop on Metaprogramming and Metareasoning in Logic (META-96), Bonn, Germany, 1996, pp. 27-42. Available from <http://www.ksl.stanford.edu/people/stolle/Papers/meta96.{pdf,ps} |
| [5] | C. Beckstein, G. Tobermann, Evolutionary logic programming with RISC, in: Fourth International Workshop on Logic Programming Environments, Washington, DC, November 1992, pp. 16-21, Technical Report TR 92-143, Center for Automation and Intelligent Systems Research at Case Western Reserve University; C. Beckstein, G. Tobermann, Evolutionary logic programming with RISC, in: Fourth International Workshop on Logic Programming Environments, Washington, DC, November 1992, pp. 16-21, Technical Report TR 92-143, Center for Automation and Intelligent Systems Research at Case Western Reserve University |
| [6] | Beckstein, C.; Tobermann, G., Algorithmic debugging and hypothetical reasoning, Journal of Automated Software Engineering, 4, 151-178 (1997) |
| [7] | Benzmüller, C.; Cheikhrouhou, L.; Fehrer, D.; Fiedler, A.; Huang, X.; Kerber, M.; Kohlhase, M.; Konrad, K.; Melis, E.; Meier, A.; Schaarschmidt, W.; Siekmann, J.; Sorge, V., ΩMega: Towards a mathematical assistant, (McCune, W., Fourteenth Conference on Automated Deduction (CADE-14), LNAI, Townsville, Australia (1997), Springer: Springer Berlin, Germany) · Zbl 1430.68393 |
| [8] | Bowen, K. A.; Kowalski, R. A., Amalgamating language and metalanguage in logic programming, (Clark, K. L.; Tärnlund, S. A., Logic Programming (1982), Academic Press: Academic Press London), 153-172 |
| [9] | Bradley, E.; Easley, M., Reasoning about sensor data for automated system identification, Intelligent Data Analysis, 2, 2, 123-138 (1998) |
| [10] | Bradley, E.; Easley, M.; Stolle, R., Reasoning about nonlinear system identification, Artificial Intelligence, 133, December, 139-188 (2001) · Zbl 0984.68158 |
| [11] | Bradley, E.; O’Gallagher, A.; Rogers, J., Global solutions for nonlinear systems using qualitative reasoning, Annals of Mathematics and Artificial Intelligence, 23, 211-228 (1998) · Zbl 0917.93030 |
| [12] | Bradley, E.; Stolle, R., Automatic construction of accurate models of physical systems, Annals of Mathematics and Artificial Intelligence, 17, 1-28 (1996) · Zbl 0891.68018 |
| [13] | B.G. Buchanan, Creativity at the meta-level, AI Magazine 22 (3) (2001), Presidential address at the Seventeenth National Conference on Artificial Intelligence (AAAI-00), Austin, TX; B.G. Buchanan, Creativity at the meta-level, AI Magazine 22 (3) (2001), Presidential address at the Seventeenth National Conference on Artificial Intelligence (AAAI-00), Austin, TX |
| [14] | A. Bundy, The use of explicit plans to guide inductive proofs, Technical Report 349, Department of Artificial Intelligence, Edinburgh, 1987; Short version appeared in: R. Lusk, R. Overbeek (Eds.), Ninth Conference on Automated Deduction, Springer, 1988, pp. 111-120; A. Bundy, The use of explicit plans to guide inductive proofs, Technical Report 349, Department of Artificial Intelligence, Edinburgh, 1987; Short version appeared in: R. Lusk, R. Overbeek (Eds.), Ninth Conference on Automated Deduction, Springer, 1988, pp. 111-120 · Zbl 0656.68106 |
| [15] | A. Bundy, Proof planning, in: B. Drabble (Ed.), Third International Conference on AI Planning Systems (AIPS-96), 1996, pp. 261-267; A. Bundy, Proof planning, in: B. Drabble (Ed.), Third International Conference on AI Planning Systems (AIPS-96), 1996, pp. 261-267 |
| [16] | J.G. Carbonell, J. Blythe, O. Etzioni, Y. Gil, R. Joseph, D. Kahn, C. Knoblock, S. Minton, A. Pérez, S. Reilly, M. Veloso, X. Wang, PRODIGY 4.0: The manual and tutorial, Technical Report CMU-CS-92-150, School of Computer Science, Carnegie Mellon University, June 1992; J.G. Carbonell, J. Blythe, O. Etzioni, Y. Gil, R. Joseph, D. Kahn, C. Knoblock, S. Minton, A. Pérez, S. Reilly, M. Veloso, X. Wang, PRODIGY 4.0: The manual and tutorial, Technical Report CMU-CS-92-150, School of Computer Science, Carnegie Mellon University, June 1992 |
| [17] | Castro, C.; Borovanský, P., The use of a strategy language for solving search problems, Annals of Mathematics and Artificial Intelligence, 29, 35-64 (2000) · Zbl 1001.68030 |
| [18] | Char, B. W.; Geddes, K. O.; Gonnet, G. H.; Leong, B. L.; Monagan, M. B.; Watt, S. M., Maple V Language Reference Manual (1991), Springer: Springer New York · Zbl 0758.68038 |
| [19] | M. Cherniack, S. Zdonik, Changing the rules: transformations for rule-based optimizers, in: ACM SIGMOD International Conference on Management of Data, Seattle, WA, June 1998; M. Cherniack, S. Zdonik, Changing the rules: transformations for rule-based optimizers, in: ACM SIGMOD International Conference on Management of Data, Seattle, WA, June 1998 |
| [20] | Davis, R., Meta-rules: reasoning about control, Artificial Intelligence, 15, 3 (1980) |
| [21] | de Kleer, J., An assumption-based TMS, Artificial Intelligence, 28, 127-162 (1986) |
| [22] | J. Denzinger, D. Fuchs, Cooperation of heterogeneous provers, in: International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, August 1999, pp. 10-15; J. Denzinger, D. Fuchs, Cooperation of heterogeneous provers, in: International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, August 1999, pp. 10-15 |
| [23] | J. Denzinger, M. Fuchs, M. Fuchs, High performance ATP systems by combining several AI methods, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 102-107; J. Denzinger, M. Fuchs, M. Fuchs, High performance ATP systems by combining several AI methods, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 102-107 |
| [24] | P. Devanbu, M. Freeland, S.A. Naqvi, A procedural approach to search control in PROLOG, in: European Conference on Artificial Intelligence (ECAI-86), 1986, pp. 53-57; P. Devanbu, M. Freeland, S.A. Naqvi, A procedural approach to search control in PROLOG, in: European Conference on Artificial Intelligence (ECAI-86), 1986, pp. 53-57 |
| [25] | M. Dincbas, J.P. Le Pape, Metacontrol of logic programs in METALOG, in: International Conference on Fifth Generation Computing Systems, 1984, pp. 361-370; M. Dincbas, J.P. Le Pape, Metacontrol of logic programs in METALOG, in: International Conference on Fifth Generation Computing Systems, 1984, pp. 361-370 |
| [26] | Earley, J., An efficient context-free parsing algorithm, Communications of the ACM, 13, 2, 94-102 (1970) · Zbl 0185.43401 |
| [27] | Easley, M.; Bradley, E., Reasoning about input-output modeling of dynamical systems, (in: Third International Symposium on Intelligent Data Analysis (IDA-99). in: Third International Symposium on Intelligent Data Analysis (IDA-99), Lecture Notes in Computer Science, vol. 1642 (1999), Springer: Springer Amsterdam, The Netherlands), 343-355 |
| [28] | J.O. Everett, K.D. Forbus, Scaling up logic-based truth maintenance systems via fact garbage collection, in: Thirteenth National Conference on Artificial Intelligence (AAAI-96), 1996, pp. 614-620; J.O. Everett, K.D. Forbus, Scaling up logic-based truth maintenance systems via fact garbage collection, in: Thirteenth National Conference on Artificial Intelligence (AAAI-96), 1996, pp. 614-620 |
| [29] | Forbus, K. D.; de Kleer, J., Building Problem Solvers (1993), MIT Press: MIT Press Cambridge, MA · Zbl 0819.68116 |
| [30] | Gabbay, D. M.; Sergot, M. J., Negation as inconsistency I, The Journal of Logic Programming, 3, 1, 1-36 (1986) · Zbl 0606.68086 |
| [31] | H. Gallaire, C. Lasserre, Controlling knowledge deduction in a declarative approach, in: International Joint Conference on Artificial Intelligence (IJCAI-79), 1979, pp. S1-S6; H. Gallaire, C. Lasserre, Controlling knowledge deduction in a declarative approach, in: International Joint Conference on Artificial Intelligence (IJCAI-79), 1979, pp. S1-S6 |
| [32] | Gallaire, H.; Lasserre, C., Metalevel control for logic programs, (Clark, K. L.; Tärnlund, S. A., Logic Programming (1982), Academic Press: Academic Press London) |
| [33] | Garey, M. R.; Johnson, D. S., Computers and Intractibility: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039 |
| [34] | M. Ginsberg, D. Geddis, Is there any need for domain-dependent control information? in: Ninth National Conference on Artificial Intelligence (AAAI-91), 1991, pp. 452-457; M. Ginsberg, D. Geddis, Is there any need for domain-dependent control information? in: Ninth National Conference on Artificial Intelligence (AAAI-91), 1991, pp. 452-457 |
| [35] | B. Gramlich, H. Kirchner, F. Pfenning (Eds.), Annals of Mathematics and Artificial Intelligence, vol. 29, Kluwer Academic Publishers, New York, 2000, Special Issue on Strategies in Automated Deduction; B. Gramlich, H. Kirchner, F. Pfenning (Eds.), Annals of Mathematics and Artificial Intelligence, vol. 29, Kluwer Academic Publishers, New York, 2000, Special Issue on Strategies in Automated Deduction |
| [36] | B.N. Grosof, Courteous logic programs: prioritized conflict handling for rules, Technical Report RC 20836, IBM Research, December 1997; B.N. Grosof, Courteous logic programs: prioritized conflict handling for rules, Technical Report RC 20836, IBM Research, December 1997 |
| [37] | Haynes, C. T., Logic continuations, The Journal of Logic Programming, 4, 157-176 (1987) · Zbl 0617.68003 |
| [38] | Hill, P.; Lloyd, J. W., The Gödel Programming Language (1994), MIT Press: MIT Press Cambridge, MA · Zbl 0850.68138 |
| [39] | Y.-C. Huang, B. Selman, H. Kautz, Control knowledge in planning: benefits and tradeoffs, in: National Conference on Artificial Intelligence (AAAI-99), Orlando, FL, August 1999; Y.-C. Huang, B. Selman, H. Kautz, Control knowledge in planning: benefits and tradeoffs, in: National Conference on Artificial Intelligence (AAAI-99), Orlando, FL, August 1999 |
| [40] | Hutter, D., Annotated reasoning, Annals of Mathematics and Artificial Intelligence, 29, 183-222 (2000) · Zbl 1001.68125 |
| [41] | F. Lin, Applications of the situation calculus to formalizing control and strategic information: the Prolog cut operator, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 1412-1418; F. Lin, Applications of the situation calculus to formalizing control and strategic information: the Prolog cut operator, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 1412-1418 |
| [42] | Lin, F., Search algorithms in the situation calculus, (Levesque, H. J.; Pirri, F., Logical Foundation for Cognitive Agents: Contributions in Honor of Ray Reiter (1999), Springer: Springer Berlin), 213-233 · Zbl 0944.68045 |
| [43] | (Ljung, L., System Identification; Theory for the User (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0615.93004 |
| [44] | Lloyd, J. W., Foundations of Logic Programming (1987), Springer: Springer Berlin · Zbl 0547.68005 |
| [45] | McCarty, L. T., Clausal intuitionistic logic I. Fixed-point semantics, The Journal of Logic Programming, 5, 1-31 (1988) · Zbl 0645.03006 |
| [46] | McCarty, L. T., Clausal intuitionistic logic II. Tableau proof procedures, The Journal of Logic Programming, 5, 93-132 (1988) · Zbl 0661.03004 |
| [47] | Melis, E.; Meier, A., Proof planning with multiple strategies, (Loyd, J.; Dahl, V.; Furbach, U.; Kerber, M.; Lau, K.; Palamidessi, C.; Pereira, L.; Stuckey, Y. S.P., First International Conference on Computational Logic (CL-2000). First International Conference on Computational Logic (CL-2000), LNAI, vol. 1861 (2000), Springer: Springer London, UK), 644-659 · Zbl 0983.68531 |
| [48] | Melis, E.; Siekmann, J., Knowledge-based proof planning, Artificial Intelligence, 115, 65-105 (1999) · Zbl 0939.68822 |
| [49] | Mendelson, E., Introduction to Mathematical Logic (1964), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0192.01901 |
| [50] | Minton, S., Quantitative results concerning the utility of explanation-based learning, Artificial Intelligence, 42, 363-391 (1990) |
| [51] | S. Minton, Is there any need for domain-dependent control information? A reply, in: Thirteenth National Conference on Artificial Intelligence (AAAI-96), 1996, pp. 855-862; S. Minton, Is there any need for domain-dependent control information? A reply, in: Thirteenth National Conference on Artificial Intelligence (AAAI-96), 1996, pp. 855-862 |
| [52] | P.J. Mosterman, G. Biswas, Formal specifications for hybrid dynamical systems, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 568-573; P.J. Mosterman, G. Biswas, Formal specifications for hybrid dynamical systems, in: Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997, pp. 568-573 |
| [53] | Naish, L., (in: Negation and Control in PROLOG. in: Negation and Control in PROLOG, Lecture Notes in Computer Sciences, vol. 238 (1985), Springer: Springer Berlin) · Zbl 0602.68006 |
| [54] | Pradhan, S.; Minker, J.; Subrahmanian, V. S., Combining databases with prioritized information, Journal of Intelligent Information Systems, 4, 3, 231-260 (1995) |
| [55] | Smith, D. E.; Genesereth, M. R., Ordering conjunctive queries, Artificial Intelligence, 26, 2, 171-215 (1985) · Zbl 0569.68077 |
| [56] | Son, T. C.; Baral, C.; McIlraith, S., Planning with different forms of domain-dependent control knowledge-an answer set programming approach, (Eiter, T.; Faber, W.; Truszczyński, M., Sixth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-01), Vienna, Austria. Sixth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-01), Vienna, Austria, LNAI, vol. 2173 (2001), Springer: Springer Berlin, Heidelberg), 226-239 · Zbl 1007.68591 |
| [57] | Stefik, M., Planning and meta-planning MOLGEN: Part 2, Artificial Intelligence, 16, 2, 141-170 (1981) |
| [58] | Sterling, L.; Shapiro, E., The Art of PROLOG (1986), MIT Press: MIT Press Cambridge, MA · Zbl 0605.68002 |
| [59] | R. Stolle, in: Orchestrating Reasoning for Automated System Identification, Lecture Notes in Computer Science, Springer, Heidelberg, in press, Revised version of Ph.D. thesis, University of Colorado at Boulder, 1998; R. Stolle, in: Orchestrating Reasoning for Automated System Identification, Lecture Notes in Computer Science, Springer, Heidelberg, in press, Revised version of Ph.D. thesis, University of Colorado at Boulder, 1998 |
| [60] | R. Stolle, E. Bradley, A customized logic paradigm for reasoning about models, in: Y. Iwasaki, A. Farquhar (Eds.), Tenth International Workshop on Qualitative Reasoning (QR-96), Stanford Sierra Camp, CA, 1996, pp. 235-244, AAAI Technical Report WS-96-01; R. Stolle, E. Bradley, A customized logic paradigm for reasoning about models, in: Y. Iwasaki, A. Farquhar (Eds.), Tenth International Workshop on Qualitative Reasoning (QR-96), Stanford Sierra Camp, CA, 1996, pp. 235-244, AAAI Technical Report WS-96-01 |
| [61] | R. Stolle, E. Bradley, Multimodal reasoning for automatic model construction, in: Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI, July 1998, pp. 181-188; R. Stolle, E. Bradley, Multimodal reasoning for automatic model construction, in: Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI, July 1998, pp. 181-188 |
| [62] | V.S. Subrahmanian, A simple formulation of the theory of metalogic programming, Technical Report LPRG-TR-88-32, Syracuse University, 1988; V.S. Subrahmanian, A simple formulation of the theory of metalogic programming, Technical Report LPRG-TR-88-32, Syracuse University, 1988 |
| [63] | G. Tobermann, Verallgemeinerte Hornklausellogik: vom logischen Kalkül zum Logik-Programmiersystem, Ph.D. thesis, Universität Erlangen-Nürnberg, 1994; G. Tobermann, Verallgemeinerte Hornklausellogik: vom logischen Kalkül zum Logik-Programmiersystem, Ph.D. thesis, Universität Erlangen-Nürnberg, 1994 |
| [64] | Ullman, J. D., Principles of Database and Knowledge-Base Systems, Vol. I (1988), Computer Science Press: Computer Science Press Rockville, MD |
| [65] | van der Laag, P., (in: An Analysis of Refinement Operators in Inductive Logic Programming. in: An Analysis of Refinement Operators in Inductive Logic Programming, Tinbergen Institute Research Series, vol. 102 (1995), Thesis Publishers: Thesis Publishers Amsterdam) · Zbl 0874.68047 |
| [66] | van Harmelen, F., Meta-level Inference Systems (1991), Morgan Kaufmann |
| [67] | D. Waltz, The importance of importance, AI Magazine 20 (3) (1999), Presidential address at the Sixteenth National Conference on Artificial Intelligence (AAAI-99), Orlando, FL; D. Waltz, The importance of importance, AI Magazine 20 (3) (1999), Presidential address at the Sixteenth National Conference on Artificial Intelligence (AAAI-99), Orlando, FL |
| [68] | D.H.D. Warren, Efficient processing of interactive relational database queries expressed in logic, in: Seventh International Conference on Very Large Data Bases, Cannes, France, 1981; D.H.D. Warren, Efficient processing of interactive relational database queries expressed in logic, in: Seventh International Conference on Very Large Data Bases, Cannes, France, 1981 |
| [69] | L.U. Yalcinalp, Meta-Programming for Knowledge Based Systems in PROLOG, Ph.D. thesis, Case Western Reserve University, 1991, Technical Report TR 91-141; L.U. Yalcinalp, Meta-Programming for Knowledge Based Systems in PROLOG, Ph.D. thesis, Case Western Reserve University, 1991, Technical Report TR 91-141 |
| [70] | Yip, K.; Zhao, F., Spatial aggregation: theory and applications, Journal of Artificial Intelligence Research, 5, 1-26 (1996) |
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.
