Scaling Up First-Order Logical Reasoning using Graphical Structure

Principal Investigator

  • Eyal Amir, University of Illinois at Urbana-Champaign


  • Deepak Ramachandran, University of Illinois at Urbana-Champaign
  • Igor Gammer, University of Illinois at Urbana-Champaign

    This work is supported by award NSF IIS 05-46663 (CAREER Award) titled CAREER: Scaling Up First-Order Logical Reasoning with Graphical Structure.

    Research Objectives

    The ability to represent and reason about objects and relations between them is central to many approaches and applications in Artificial Intelligence (AI), including common-sense query answering, natural-language processing, planning, and diagnosis problem solving. In recent years the number of objects and relations that applications need to consider has increased dramatically, and current real-world applications require reasoning mechanisms that can scale to thousands and more objects and relations. Traditional approaches to logical reasoning that focus on propositional theories are impractical for such real-world domain because propositional representations of the associated theories have explosive sizes, rendering inference useless. On the other hand, current inference in First-Order Logic (FOL) is impractical here as well because it focuses on mathematical theories that are much smaller and lack the structure of real-world common-sense domain theories.

    This project focuses on scaling up inference over FOL with graph-based structures that are available in real-world domains. In this research we focus first on inference in FOL, and then apply the insights we gain from general FOL to inference with first-order structure on more specialized scenarios (most times avoiding general FOL inference while still using the same structure). The key idea in this approach is a methodology for inference in FOL that can ignore most interactions between objects, functions, and predicates, and be fast and correct. In this methodology, a given theory is first partitioned into a tree of subtheories, according to different measures of efficiency that depend on the target inference algorithm.

    Our research starts with creating a theory of such structures in FOL knowledge bases, anticipating future use of the graph structures by inference algorithms. We then consider two paradigms for inference: one in which we use the structure to create compact propositional encodings of the original theory, and one in which inference is carried out directly in FOL guided by the graph structure. In a complementary effort, we plan to develop algorithms that partition a given theory automatically according to different optimization criteria that match the target inference algorithm.

    See also the Partitioning and Reasoning project web page.


    Jaesik Choi and Eyal Amir, Combining Planning and Motion Planning, in Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA'09), 2009 (PS,PDF).  [new]
    Hannaneh Hajishirzi, Afsaneh Shirazi, Jaesik Choi, and Eyal Amir, Greedy Algorithms for Sequential Sensing Decisions, in Proceedings of the 2009 International Joint Conference on Artificial Intelligence (IJCAI'09), 2009 (PS,PDF).  [new]
    Eyal Amir and Sheila McIlraith, Strategies for Focusing Structure-Based Theorem Proving, (submitted for publication), 2008. (PDF, PS)
    Afsaneh Shirazi and Eyal Amir, Factored Models for Probabilistic Modal Logic, in Proceedings of the 2008 Conference of the Association for the Advancement of Artificial Intelligence (AAAI'08), 2008 (PS,PDF).
    Hannaneh Hajishirzi and Eyal Amir, Sampling First Order Logical Particles, in Proceedings of the 2008 International Conference on Uncertainty in Artificial Intelligence (UAI'08), 2008 (PS,PDF).
    Jaesik Choi and Eyal Amir, Factor-Guided Motion Planning for a Robot Arm, in Proceedings of the 2007 IEEE International Conference on Intelligent Robots and Systems (IROS'07), 2007 (PS,PDF).
    Igor Gammer and Eyal Amir, Solving Satisfiability in Ground Logic with Equality by Efficient Conversion to Propositional Logic, in 7th Symposium on Abstraction, Reformulation, and Approximation (SARA'07), 2007 (PS,PDF).
    Deepak Ramachandran and Eyal Amir, Bayesian Inverse Reinforcement Learning, in 20th International Joint Conference on Artificial Intelligence (IJCAI'07), 2007 (PS,PDF).
    Dafna Shahaf and Eyal Amir, Logical Circuit Filtering, in 20th International Joint Conference on Artificial Intelligence (IJCAI'07), 2007 (PS,PDF).
    Jaesik Choi and Eyal Amir, Factored planning for controlling a robotic arm: theory, 5th International Cognitive Robotics workshop (CogRob 2006), 2006.
    R. Braz, Eyal Amir, and D. Roth, MPE and Partial Inversion in Lifted Probabilistic Variable Elimination, in 21st National Conference on Artificial Intelligence (AAAI'06), 2006 (PS,PDF).
    D. Ramachandran and E. Amir, Compact Propositional Encodings of First-Order Theories, in 20th National Conference on Artificial Intelligence (AAAI'05), 2005 (PS,PDF).  [new]

    Eyal Amir Last updated on September 1, 2009.