Applied-Logic, Programming Languages and Systems (ALPS) Lab

Director: Prof. Gopal Gupta

Postdoc Researchers: Dr. Zhuo Chen, Dr. Serdar Erbatur, Dr. Elmer Salazar

PhD Students: Sarat Varanasi, Kinjal Basu, Fang Li, Huaduo Wang, Farhad Shakerin (recent graduate)

Collaborators: Dr. Joaquin Arias & Dr. Manuel Carro (IMDEA/UPM, Spain)

The ALPS Lab is engaged in research in Computational Logic, AI (automated reasoning, machine learning) and advanced programming languages. Much of the work revolves around exploring application of advanced logic programming techniques and answer set programming to these areas. Current project in AI are in areas of automating common sense reasoning, natural language text question-answering, automated conversational agents, inductive logic programming, and explainable AI. In programming languages, current focus is on co-induction and its applications, semantics of negation, and automated program synthesis. An (incomplete) list of current projects is below.
  1. Natural Language Question Answering based on Text Understanding: This project, called CASPR, is focused on modeling knowledge using answer set programming (ASP) using our query-driven s(CASP) implementation of it that supports commonsense reasoning. Knowledge contained in an English passage text is translated into an ASP knowledge-base. Relevant common sense knowledge from resources such as WordNet and VerbNet is translated into ASP as well. Finally, a question asked against the passage text is translated into an ASP query and executed against the knowledge-base assembled in the first two steps. Using our query-driven s(CASP) system, justification for the question's answer can also be computed. This line of work has the potential to solve the common sense reasoning problem of AI, a major road block in building truly intelligent systems. The system uses our novel, goal-directed implementation of answer set programming called s(CASP). The techniques developed are also being used to answer natural language questions about objects in a picture as well as bringing commonsense reasoning to automated driving of autonomous cars. We are also applying it for building chatbots that operate by "truly understanding" what a human is saying.
  2. Explainable AI/Inductive Learning of Default Theories: This line of research extends work done in the field of inductive logic programming (where one learns a logic program from examples and background knowledge) to learning normal logic programs, i.e., learning logic programs that contain negation as failure. Normal logic programs have been shown to model human-style common sense reasoning quite well. The inductive learning algorithms my group has developed learns a default relation as well as exceptions to it. The learning algorithm can also handle features that range over real numbers. The algorithms recursively learn exceptions to exceptions and so on thereby producing a learned theory that has high accuracy. The project is a step towards what is dubbed Explainable AI and will prove to be a very important contribution to the area of Machine Learning. Implementations have been developed (Software release coming soon). The technique has been extended to explain models learned from statistical machine learning methods. You can download the tool from here. Details are in the following papers:
  3. Query-driven (Predicate) Answer Set Programming: This problem pertains to executing answer set programs in a goal-directed, top-down manner. This problem was widely considered unsolvable and most implementations are based on using a SAT solver, and thus can only handle propositional programs. The idea of coinductive logic programming pioneered in the ALPS lab is what facilitated the first solution to this problem. It culminated in the Galliwasp system. Galliwasp was then generalized to the s(ASP) system that can execute predicate answer set programs directly, where predicates can contain arbitrary terms (most other systems available thus far can only handle propositional answer set programs). Both Galliwasp and s(ASP) are publicly available. s(ASP) has been used to develop a number of innovative applications. A student hackathon was recently organized around it. s(ASP) Resources:
  4. Galliwasp Resources: Papers and software for Galliwasp, a propositional goal-directed ASP system, are available.
  5. Coinductive Logic Programming: The idea is to give operational semantics to compute answers that are in the greatest fixpoint semantics. Coinductive LP has farreaching applications. Standard logic programming (or standard computation) is based on induction (least fixpoint semantics). Infiite structures such as perpetual programs, omega-automata, etc., cannot be modeled elegantly by induction. Rather, they need coinduction for modeling. The paper that introduced coinductive LP received the ICLP 2016 test-of-time award for being the most influential paper of ICLP 2006. Coinductive logic programming has been incorporated in many Prolog implementations, most notably in SWI Prolog.
  6. Modeling Real-time Systems with CLP(R): It is hard to model real-time systems faithfully (as time is continuous). Most systems model time by discretizing it. Discretizing time only produces an approximation. This work showed how time in real-time systems can be faithfully modeled using constraint logic programming over reals (CLP(R)). We began by showing how timed automata can be faithfully modeled; this was then generalized to timed grammars, timed push down automata, timed pi-calculus, timed linear temporal logic, timed planning, etc.