Automating commonsense reasoning, i.e., automating the human thought process, has been considered ifendishly dificult. It is widely believed that automation of commonsense reasoning is needed to build intelligent systems that can rival humans. We argue that answer set programming (ASP) along with its goal-directed implementation allows us to reach this automation goal. We discuss essential elements needed for automating the human thought process, and show how they are realized in ASP and the s(CASP) goal-directed ASP engine.
Artificial Intelligence (AI) researchers are coming to the realization that for intelligent systems
to be as good as humans, they must incorporate commonsense reasoning. While machine
learning technologies have had tremendous successes, they alone are not enough. Intelligent
behavior includes both learning and (commonsense) reasoning, and automating commonsense
reasoning is equally important. Indeed, automating commonsense reasoning has been the goal
of research in artificial intelligence for a long time. Automation of commonsense reasoning
requires formalizing the human thought process, which has proven to be hard. The quest to
formalize the human thought process led to the founding of the field of Logic. The study of
logic as a means to formalize reasoning has been conducted over several millennia [
The early problems of naive set theory found by Russell—as illustrated by Russell’s paradox
[
Because of this dogmatic focus on restricting reasoning to inductive structures since the early
20ℎ century, systems of logic could not reason about themselves. Meta-reasoning within the
logic was disallowed due to fears of unsoundness and circularity. Thus, classical logics do not
have the ability to derive a conclusion based on failure of a proof in that logic itself. Tarski
stipulated that given a logic L1, we need another logic L2 to reason about L1, and yet another
logic L3 to reason about L2, and so on, ad infinitum [
In the late 1970s and 1980s considerable efort started to being invested in adding negation to
logic programming. The concept of negation as failure [
While coinduction [
To understand the significance of automating commonsense reasoning, consider autonomous
driving. To learn to drive, a human driver has to mostly focus on learning how to control the
car (steering, accelerator, brakes) and know the rules of the road. A human doesn’t have to
be explicitly taught that if a pedestrian is in front of the car, they must brake and stop. In
contrast, for an autonomous car, steering, braking, accelerating can be readily automated with
advances in control theory, however, “knowing” how it must react to trafic on the road is a
major obstacle today. For a human driver, how he/she must behave on the road is dictated by
their commonsense and the rules that they learn during driver education. Learning to steer,
brake and accelerate (and use the clutch, for stick-shift cars) is the harder part for humans.
Thus, an autonomous vehicle that takes driving decisions based on automated commonsense
reasoning may perform better than one that is based purely on machine learning technology
[
In the rest of the paper we make a case for how answer set programming executed using goal-directed implementations of ASP with predicates leads to automation of commonsense reasoning. We assume the reader has familiarity with logic programming and Prolog.
Aside from being able to perform deduction, the main characteristics of human commonsense reasoning are that (i) we can reason with incomplete information (e.g., default reasoning), (ii) perform assumption-based or circular reasoning, and (iii) reason with constraints. We explain these aspects in more detail.
Humans often reason with incomplete information. Reasoning with incomplete information amounts to drawing a conclusion from a failed proof as the proof cannot be completed due to insuficient information. Inference procedures in classical logic assume complete information. This means that if we give axioms to define a property in classical logic, then nothing can be concluded about ¬ if we are unable to prove . Separate axioms are needed to draw conclusions about ¬. Humans, in contrast, very often, will infer negation of if they fail to prove , given the axioms about . A human’s ability to draw such conclusions is modeled through negationas-failure. Humans use negation-as-failure (NAF) copiously in their day-to-day reasoning process.
Negation-as-failure ( ) is quite distinct from negation in classical logic (¬). Negation-asfailure is traditionally represented as ‘not p’ and can be interpreted as no evidence that p holds. Negation in classical logic (termed classical negation) is denoted as -p and can be interpreted to mean that p is definitely false (that is, there is definite evidence that p does not hold).
Negation-as-failure allows us to draw conclusions when a proof fails. As an example, consider the recursive logic programming rules (axioms) for reachability of one node from another node in a graph, where edge/2 represents the graph edge relation.
reach(X,Y)⇐ edge(X,Y).
reach(X,Y)⇐ edge(X,Z) ∧ reach(Z,Y).
We can use these (classical) logic axioms to check if a given node can be reached from another. However, we cannot use them to check if a given node cannot be reached from another node: we will need separate axioms for non-reachability. In contrast, with NAF, we can use not reach(A,B) to check if A is unreachable from B. not reach(A,B) simply says that if proof for reach(A,B) fails, we conclude B is unreachable from A. Failure of a proof means that there is no way to make progress in the proof. We could take an action based on this failed proof (e.g., use a helicopter to go from point A to point B, where edge represents a road-connection between cities [nodes]).
It should be mentioned that fault is not of logic, rather how a set of formulas are interpreted.
As humans we frequently interpret an implication (if statement) as a bi-implication (if and only
if statement). To draw negative inferences automatically, we have to use the idea of program
completion [
not reach(X,Y) ⇐ not edge(X,Y) ∧ not (edge(X,Z) ∧ reach(Z,Y)). This rule can be written as a logic program by applying De Morgan’s law. As humans, we automatically complete such rules in our mind. The dual rule essentially allows us to infer that not reach(X,Y) holds if we fail to prove that X can reach Y. By completing a program we are assuming that the rule is causal. Thus, given the rule p ⇐ B., which states that p can be inferred if B holds, its completion allows us to conclude that p does not hold if we have no evidence that B holds.
Humans also perform circular reasoning, or assumption based reasoning. Consider the following statement about Jack and Jill who are in love with each other:
Jack will eat dinner if Jill will eat dinner.
Jill will eat dinner if Jack will eat dinner.
To answer the question if Jack will eat dinner, we end up performing circular reasoning. If we reflect on these statements, then we can see that there are two possibilities: either both will eat dinner, or none will eat. If we interpret the above statements as logic program rules: jack_eats ⇐ jill_eats.
jill_eats ⇐ jack_eats. then the completion of these rules is
jill_eats ⇔ jack_eats
Viewed as a propositional formula, we can produce two models: {jill_eats = true,
jack_eats = true} and {jill_eats = false, jack_eats = false}. The first one
corresponds to both eating dinner and the second one to none eating dinner. If we stay in the realm
of propositions, there is no problem, despite the apparent circular dependence, we can compute
the two models. The problem arises when we graduate to predicates. Consider the rule:
eat_dinner(X) ⇐ loves(X,Y), eat_dinner(Y).
then giving this rule an operational semantics to perform computation becomes complicated.
Coinduction and coinductive logic programming, based on greatest fixpoint semantics, can be
used to give operational semantics to such circular rules containing predicates [
Humans perform reasoning under constraints. For example, we know that we cannot sit and walk at the same time. So the moment we know that a person was sitting on a chair, we conclude that he/she was not walking. From the knowledge that the person was sitting, we can even conclude that the person could not have moved away from the spot that person was in. These constraints can be thought of as integrity constraints and we employ them to make our proof process eficient. Constraints can be generally stated as declaring that the conjunction of a set of propositions or predicates is false, e.g.,
false ⇐ sitting(X) ∧ walking(X).
As an aside, for any proposition or predicate p, we have the following implicit constraint in our mind:
false ⇐ p ∧ -p.
Negation-as-failure models incomplete information. Along with assumption-based reasoning and constraints, human thought processes can now be coded as rules in logic. Consider the following four statements:
The question we want to answer is: who will go to Mexico? Notice that each rule is quite easy to understand by itself, however, it is hard to understand what these rules mean when put together, i.e., it is nearly impossible to compute the model of this program in our head. These rules are also circular. Thus, as humans, these rules will make sense if we consider models of these rules that preserve the consistency. Since these rules are circular, i.e., are based on assumptions, we will make assumptions and then check that the rules are satisfied. Those assumptions that satisfy the rules are the ones that, as humans, we are interested in as the answers we want to compute.
Note also that, as humans, we give an operational semantics to logic rules such as the ones we have seen above. For instance, consider the rule:
flies(tweety) ⇐ bird(tweety)
This rule will have 3 models: {bird(tweety) = true, flies(tweety) = true},
{bird(tweety) = false, flies(tweety) = true}, and {bird(tweety) = false,
flies(tweety) = false}. We generally ignore the models where the antecedent
bird(tweety) is false. The first model where the consequent and the antecedent are true is
termed a supported model [
Moreover, when we see such rules, we automatically “complete" them in our mind (in the
sense of program completion discussed earlier). That is, we interpret the above rule as:
flies(tweety) ⇔ bird(tweety)
That is, we implicitly assume that if Tweety is not a bird, it does not fly. Wason’s selection task
[
Answer set programming (ASP), that extends Prolog with negation-as-failure based on the
stable model semantics, supports the features discussed above: negation-as-failure, constraints,
circular reasoning, completion, and supported models. These features allow ASP to closely
emulate the human thought process [
Answer set programming (ASP) [
ASP supports better semantics for negation (negation as failure or NAF) than does standard
logic programming and Prolog. An ASP program consists of rules that look like Prolog rules.
However, the semantics of an ASP program P is given in terms of the answer sets (models) of
the program ground(P), where ground(P) is the program obtained from the substitution of
elements of the Herbrand universe2 for variables in P [
p :- q1, ..., q, not r1, ..., not r.
where ≥ 0 and ≥ 0. Each of p and q (∀ ≤ ) is a literal, and each not r (∀ ≤ ) is a
NAF -literal. The declarative semantics of an Answer Set Program P is given via the
GelfondLifschitz transform [
The goal in ASP is to compute an answer set given an answer set program, i.e., compute the set that contains all propositions that if set to true will serve as a model of the program (those propositions that are not in the set are assumed to be false). Intuitively, the rule above says that p is in the answer set if q1, ..., q are in the answer set and r1, ..., r are not in the answer set.
As mentioned earlier, default negation or negation as failure is represented as not p and can be interpreted as no evidence that p holds. Classical negation is denoted as -p and can be interpreted to mean that p is definitely false. To further understand the distinction, consider a case of bank being allegedly robbed by an individual . If we fail to prove that robbed the bank, then not robbed(i,b) holds true (there is no evidence that robbed bank ). In contrast, if we able to definitively show that did not rob bank by demonstrating, for example, that the bank was located in Dallas, but was seen at the Boston airport at the time the robbery happened, then -robbed(i,b) is true. In the latter case we have an explicit proof to demonstrate that robbed(i,b) is false.
The two types of negation allow us to realize various “shades" of truth, namely, definitely true, maybe true, unknown, maybe false, and definitely false . They are crucial in allowing ASP to simulate commonsense reasoning. ASP only considers supported models. It also assumes that the programs are completed with the caveat that cyclical programs that do not involve negation will be assigned only a single model in which the propositions involved in the cycle are assigned false. Thus, given the rules above about Jack and Jill eating dinner, the only model ASP will admit is the one where they both don’t eat. This assumption is made to stay consistent with Prolog, from which ASP originates. Next, we discuss how commonsense reasoning can be automated with ASP.
2The Herbrand universe of a logic program is the set of terms that can be constructed from its constants and function symbols.
Humans use default reasoning [
Multiple default conclusions can be drawn in some situations, and humans will use additional
reasoning to prefer one default over another. Thus, default rules with exceptions and preferences
capture a bulk of human reasoning. (More details on default reasoning can be found in [
Classical logic is unable to model default reasoning and non-monotonicity in an elegant way. We need a formalism that is non-monotonic and can support default reasoning to model the human thought process. ASP is such a formalism. ASP supports both negation-as-failure (not p) as well as classical negation (-p), where p is a proposition or a predicate. Combining these two forms of negations results in nuanced reasoning close to how humans reason:
2. not -p: denotes that p maybe true (i.e., no evidence that p is false). 3. not p ∧ not -p: denotes that p is unknown (i.e., no evidence of either p or -p being true). 4. not p: denotes that p may be false (no evidence that p is true).
5. -p: denotes that p is definitely false.
The above insight can be used, for example, to model the exceptions to Tweety’s ability to fly in
two possible ways. Consider the rules:
flies(X):- bird(X), not abnormal_bird(X). % default
abnormal_bird(X):-penguin(X). % exception
which state that if we know nothing about a bird, X, we conclude that it flies. This is in contrast
to the rules:
flies(X):- bird(X), not abnormal_bird(X). % default
abnormal_bird(X):-not -penguin(X). % exception
which states that a bird flies only if we can explicitly rule out that it is a penguin. So in the
latter case, if we know nothing about a bird, we will conclude that it does not fly. Which of the
two rules one will use depends on how conservative or aggressive one wants to be in jumping
to the default conclusion. Note that exceptions can have exceptions, which in turn can have
their own exceptions, and so on. For example, animals normally don’t fly, unless they are birds.
Thus, birds are exception to the default of not flying. Birds, in turn, normally fly, unless they are
penguins. Thus, a penguin is an exception to the exception for not flying. Defaults, exceptions,
exceptions to exceptions, and so on, allow us humans to perform reasoning elegantly and in an
elaboration tolerant manner [
The abnormal predicate represents exception to the default conclusion. Such an exception is called a weak exception. A strong exception can be directly stated by specifying objects that definitely cannot fly. For example, if we know that ostriches cannot fly, we represent it as: -flies(X):-ostrich(X). which implicitly states that an ostrich X can never satisfy flies(X). However, we will have to extend our default rule above to avoid a contradiction if we have the knowledge that ostriches are birds
bird(X):-ostrich(X).
The extended rule is as follows:
flies(X):-bird(X), not abnormal_bird(X), not -flies(X). % default The extension prevents the original rule from concluding that X flies if there is definitive evidence that it does not, thereby preventing a contradiction. Note that ostriches are not declared to be abnormal birds.
Defaults, strong/weak exceptions, nested exceptions, and aggressive/conservative reasoning,
allow us to construct a set (e.g., birds that can fly) in a nuanced, elaboration tolerant manner as
we gradually learn more information about which birds can fly and which cannot. Elements are
included or excluded from the set as we acquire more knowledge and the set is gradually refined
as the decision boundary is adjusted. Default rules with nested exceptions are an excellent
vehicle for representing the rules underlying a machine learning model [
Note that these 5 shades of truth discussed above are efective, because that’s what humans
use. Humans do not use probabilities in their day to day life. When told that Tweety is a bird, we
do not say that Tweety’s chance of flying is 95% (or whatever probability one can come up with
for a bird to fly). We will jump to the conclusion that Tweety flies, and if contrary information
becomes available later, we revise it. This has been borne out by earlier research. Quoting from
the AI text book by Ginsberg [
“An experiment was done in which MYCIN’s set of truth values (the real numbers between -1 and 1) was replaced with a just a set of four values: -1 (certainly false), -0.3 (evidence against), +0.3 (evidence for), and +1 (certainly true). The declarative sentences labeled with certainty factors that fell between these values were simply given the closest label possible. The interesting thing is that MYCIN’s performance did not degrade after this change was made."
Note that the value unknown (zero) is missed. Perhaps modeling it also would have brought MYCIN closer to a human expert.
Humans can represent multiple possible worlds in parallel in their minds and reason over each.
For example, in the real world, fish do not talk like humans, while in a cartoon world, fish
(cartoon characters) can talk. Humans can maintain the distinction between various worlds in
their minds and reason within each one of them. These multiple worlds may have aspects that
are common (fish can swim in both the real and cartoon worlds) and aspects that are disjoint
(fish can talk only in the cartoon world). Thus, we need a logic that can support multiple
possible worlds. Classical logic, due to various historical choices made (allowing only inductive
structures and inductive proofs [
teaches(mary, db):-not teaches(john, db). an ASP engine will produce two worlds: one in which John teaches databases and Mary does not
{teaches(john, db), not teaches(mary,db)} and the other one where Mary teaches and John does not
{teaches(john, db), not teaches(mary,db)} For clarity, we explicitly list both positive and negative literals in the answer set here. ASP will assign models to such non-well founded programs. If we interpret the rules operationally as in Prolog, then a call to teaches(john, db) will loop forever. Such a cyclical set of rules where the recursive call is in the scope of even number of negations is called an even loop over negation.
Consider the example that comes from Peter Norvig in which he gives a challenge problem that is hard to model in classical logic: 1. People can talk. 2. Non-human animals are not able to talk. 3. Human-like cartoon characters can talk. 4. Fish can swim. 5. A fish is a non-human animal. 6. Nemo is a human-like cartoon character.
7. Nemo is a fish.
The question is “can Nemo talk?” and, “can Nemo swim?”. The answer to “Can Nemo talk?” leads to a contradiction under classical logic. This happens because two worlds (real and cartoon) are intertwined here. Humans easily recognize this, but it is harder for machines. However, this is easily resolved in ASP, where we can have two worlds: real world (rw) and cartoon world (cw). We just have to know which statement is true in which world(s). Note that some information is mutually exclusive between two worlds, while some may be common, and some may be known in one world but not (yet) in the other. The encoding in ASP for each of the statements is shown below. 1 talk(X):- people(X). 2 -talk(X):- non_human_animal(X), rw. 3 talk(X):- human_like_cc(X), cw. 4 swim(X):- fish(X). 5 non_human_animal(X):- fish(X), rw. 6 human_like_cc(nemo):- cw. 7 fish(nemo).
% people talk in both worlds % non human animals do not talk in rw % human-like cartoon char can talk in cw % fish swim in both worlds % fish is a non-human-animal in rw % Nemo is a human-like cartoon char in cw % Nemo is a fish in both worlds
% cw and rw are two separate worlds
An ASP engine will produce two models: one corresponding to the cartoon world (cw) and the
other to the real world (rw). Only cw will contain talk(nemo) while both worlds will contain
swim(nemo). Possible worlds can also be used to simulate abductive reasoning [
ASP can also model constraints elegantly. A constraint is a rule of the form: false:-p1, p2, . . ., p. which states that the conjunction of p1, p2, through p is false (the keyword false is often omitted). Constraints elegantly model global invariants or restrictions that our knowledge must satisfy, e.g., p and -p cannot be true at the same time, denoted
false:-p, -p.
Humans indeed use constraints in their everyday reasoning: as restrictions (two humans cannot occupy the same spot) and invariants (a human must breath to stay alive).
Earlier we saw even loops over negation. Odd loops over negation also exist, for example, programs such as:
p:- q, not p.
An odd loop over negation represents a constraint. If we complete the rule above, we obtain p ⇔ (q ∧ not p). A little thought will reveal that the only feasible model is p = false, q = false. In other words, this rule is stating that q must be false. This can be alternatively stated via a constraint.
:- q.
Note that if there is an alternative proof of p via other rules, then the above odd loop rule will be rendered inapplicable due to p being true through other means. If we wish to reason in terms of possible worlds, then even loops are used to generate multiple worlds and odd loops or constraints are used to “kill" worlds.
Next we show that ASP is a good vehicle for realizing deductive and abductive reasoning—also performed by humans—as well as a good way of representing inductive generalizations.
There are three major modes of reasoning that humans use in their day to day life: deduction, abduction, and induction. Consider the proposition p, q, and the formula p ⇒ q. Deduction: Given premises p and p ⇒ q, we deduce q. Suppose we are given the premises that Tweety is a bird (bird(tweety)), and the formula ∀() ⇒ (). From these two premises, we can deduce that flies(tweety) holds, i.e., Tweety can fly. Deductive reasoning is easily expressed using answer set programming. If we consider Rule 1, then given q1, ..., q, not r1, ..., not r, we can deduce p. Essentially, the antecedent can become more complex and can included negation-as-failure (NAF) literals.
Abduction: Given the observation q and the premise p ⇒ q, we abduce p. Suppose we observe Tweety flying ( flies(tweety) ), and we know that ∀() ⇒ (). From these, we can abduce that bird(tweety) holds, i.e., we assume (or advance the most likely explanation) that Tweety is a bird. Note that there may be other explanations, as Tweety may be an airplane. Generally, the set of abduced literals is fixed in advance. Abductive reasoning in ASP is elegantly modeled via possible worlds. If we make an assumption p, i.e., declare p to be abducible, then we can assert an even loop over negation: p:- not _notp.
_notp:-not p. where _notp is a dummy proposition. This even loop will result in two possible worlds: one in which p is true and one in which p is false. The assumption that will produce a consistent model (either p true or p false) is the correct assumption that we will abduce, if we add this even loop to a program where we want to find a likely explanation.
Induction: Given instances of p and corresponding instances of q that may be related, we may induce p ⇒ q. Thus, given the observations that Tweety is a bird and Tweety can fly, Sam is a bird and Sam can fly, Polly is a bird and Polly can fly, and so on, we may induce bird(X) ⇒ flies(X). Induction, of course, relates to learning associations between data. The results of rules induced can be elegantly captured as an answer set program. This is because ASP can be used to represent defaults with exceptions, which allows us to elegantly represent inductive generalizations. Consider the following rule: flies(X):-bird(X), not abnormal_bird(X).
abnormal_bird(X):-penguin(X).
The above default rule with exception, namely, normally birds fly unless they are penguins ,
elegantly captures the rule that a human may form in their mind after observing birds and their
ability to fly. The list of exceptions can grow (ostrich, wounded bird, baby bird, . . . ). Similarly,
the list of defaults rules can grow. For instance, we may have a separate rule for planes being able
to fly. Explainable machine learning tools that induce default theories as answer set programs
have been developed [
Given that deduction, abduction, and induction fit into the framework of ASP well, it gives us confidence that ASP can be a good means of representing commonsense knowledge.
ASP is a powerful, expressive paradigm for representing knowledge. It represents knowledge in
a manner very similar to how humans represent it and use it. However, it is a challenging task
to implement ASP. Most implementations of answer set programming work by first grounding
the program with elements of the program’s Herbrand universe, then suitably transforming
the program in a way such that the models of the transformed program computed with a SAT
solver are identical to the original program’s answer sets [
Humans, obviously, do not compute the entire model given the knowledge of the world, as it will be too ineficient. Humans also reason in a goal-directed manner, i.e., they establish a target goal and then attempt to establish that it holds. This can be simulated by goal-directed execution of ASP. The advantage of goal-directed execution of ASP is that only relevant part of the knowledge is used in proving a goal, very much like in Prolog. In goal-directed execution, programs containing predicates can be directly executed without requiring grounding.
Recently, goal-directed implementations of ASP have been realized that can execute answer
set programs containing predicates in a query-driven manner [
These goal-directed ASP systems support predicates that can take arbitrary terms as
arguments. Implementation of such systems became possible because of development of coinductive
logic programming [
The s(CASP) system can be thought of as Prolog extended with negation-as-failure based on the
stable model semantics. The s(CASP) system also supports constraints over reals. The s(CASP)
system provides support for full Prolog, however, in addition, it also supports coinductive
reasoning, constructive negation, dual rules, and support for universally quantified variables.
These are explained briefly next. More details can be found elsewhere [
As discussed earlier, answer set programs may contain circular rules, for example: p:- not q.
q:- not p.
If we ask the query ?-p in Prolog, given the rules above, the execution will loop forever. This is because p reduces to not q, which, in turn, reduces to not not p which equals p. If we appeal to greatest fixpoint semantics , then the query p should succeed. Essentially, what we are saying is that p succeeds if we assume p to hold. This yields the answer set in which p is true and q false. Note that all the literals encountered along the way (e.g., not q) will be in the (partial) answer set.
If we issue the query ?-not p, then we will find the other answer set where q is true and p is false. Thus, if we ask a query in s(CASP), it will give a partial answer set that is a subset of the world in which the query is true. If there are multiple such worlds in which the query holds, we will compute them one by one through backtracking (by typing a semi-colon, as in a Prolog system).
While circular reasoning of the type above seems counter-intuitive, as humans, we perform such assumption based (circular) reasoning all the time, as illustrated in the examples discussed earlier. Consider a murder mystery in which our goal is to find the murderer. We make various assumptions about who the murderer could be, and then perform reasoning with this assumption to find a consistent world in which this assumption holds. Assumption based reasoning is, essentially, abductive reasoning discussed earlier that ASP supports by introducing an even loop for each abducible. Abductive reasoning is thus elegantly supported in s(CASP).
Since s(CASP) allows general predicates that could be negated, support for constructive negation becomes essential. Consider a program consisting of the simple fact
p(a).
If we pose the query ?-not p(X), it should succeed with answer X ̸= a. Intuitively, X ̸= a means that X can be any term not unifiable with a. To support constructive negation, the implementation has to keep track of values that a variable cannot take. The Unification algorithm has to be extended, therefore, to account for such disequality-constrained values.
In the s(CASP) system, a variable can only be disequality-constrained against ground terms,
and the disequality of two compound terms may require backtracking to check all the cases:
p(1,Y) ̸= p(X,2) first succeeds with X ̸= 1 and then, upon backtracking, with Y ̸= 2. We
omit further details here, as they can be found elsewhere [
As we discussed earlier, given an answer set program, we work with its completion. To complete
the program, the s(CASP) system will add the dual rules [
(1, . . . ) :- . they are coalesced into a single rule containing disjunction of bodies: (1, . . . , ) :(1 = 11, . . . = 1, 1)∨ . . .
∨ (1 = 1, . . . = , ).
Next, the dual is represented as:
_ :- ¬ where represents the body of the coalesced clause. We will use De Morgan’s law to simplify the dual rule. Consider the following example: redcar(mycar).
redcar(X):-red(X), car(X).
This rule is rewritten as:
redcar(X):-(X = mycar); (red(X), car(X)). where ‘;’ denotes disjunction. The dual rule will, obviously, be: not_redcar(X):-X \=mycar. not_redcar(X):-not red(X).
not_redcar(X):-not car(X).
To make the execution more eficient, s(CASP) will rewrite the third clause as: not_redcar(X):-red(X), not car(X).
Essentially, the dual rule states that a non-red car is anything other than mycar as well as anything that is not red, and among red things those that are not cars.
An additional complication in computing the dual rules is the need to handle existential variables. Consider the following very simple rule:
p(X):-not q(X,Y).
This rule corresponds to the Horn clause:
∀(() ⇐ ∃ (, )) Its dual will be:
∀(_() ⇐ ∀ (, )) which, in s(CASP), will be represented as: not_p(X):-forall(Y, q1(X,Y)).
q1(X,Y):-q(X,Y).
Universal quantification in the body of the dual rule is needed because, for example, for the goal not p(a) to succeed, we must prove that q(a, Y) holds for every possible value of Y. The s(CASP) system handles all these issues and produces dual rules for arbitrary programs. The execution of the forall, however, is non-trivial, as often times the foralls are nested.
:- p(X), q(X). or as odd loops over negation such as:
r(X):-q(X), not r(X).
When a query is executed against a s(CASP) program, a partial answer set is computed that represents the answer. If this partial answer set does not satisfy the constraint, it is rejected, and backtracking ensues. This is achieved by appending the query with appropriate goals that correspond to executing these constraints. Thus, the s(cASP) system extends the query appropriately to capture the efect of a constraint no matter in which one of the two ways above it is expressed. An appropriate sub-goal is appended for each constraint in the program. As an example, consider the following simple program: p(X):-q(X), r(X).
:- t(a).
If we have the query:
?- p(X). then s(CASP) will augment this query and turn it into
?- p(X), not t(a). since t(a) must be false in every answer set. If the constraint was instead:
:- t(X). which states that t/1 must be false for every value of X in every answer set, then the extended query will be:
?- p(X), forall(Y, s(X)). where s(X) is defined as:
s(X):-not t(X).
Note that these extra sub-goals arising from constraints and odd loops over negation that are
added to the query should be executed as soon as a variable that occurs in the sub-goal is
bound during the execution. This will result in speedier execution, and is indeed supported by
s(CASP). In some cases the additional subgoals that the s(cASP) system augments to the query
will over-approximate the actual constraint. However, this over approximation only leads to
extra execution overhead, it does not impact the correctness of the execution [
A goal-driven implementation of ASP can generate a proof for the query, thus, justification
for each element of an answer set can be generated [
Next, we show examples of modeling commonsense knowledge in ASP and executing them under the s(CASP) system.
Consider first a very simple example, where we want to model the college admissions process
taken from [
If a student John has a fair GPA, but not a high GPA, the rules above will conclude that John
must be interviewed. Consider another example, this one from Levesque’s Prolog course on
Thinking As Computation [
1. George is a bachelor. 2. George was born in Boston, collects stamps. 3. A son of someone is a child who is male. 4. George is the only son of Mary and Fred. 5. A man is an adult male person. 6. A bachelor is a man who has never been married. 7. A (traditional) marriage is a contract between a man and a woman, enacted by a wedding and dissolved by a divorce. 8. While the contract is in efect, the man (called the husband) and the woman (called the wife) are said to be married.
9. A wedding is a ceremony where . . . bride . . . groom . . . bouquet . . .
From this knowledge, we would like to draw the following conclusions: (i) George has never been the groom at a wedding. (ii) Mary has an unmarried son born in Boston. (iii) No woman is the wife of any of Fred’s children. We can model the knowledge in ASP, translate the conclusions we want to draw into queries, and execute them on s(CASP). The following rules represent the knowledge mentioned above and is easily undestood: 1 % 1 2 bachelor(george). 3 % 2 4 birth_city(george, boston). 5 hobby(george, stamp_collecting). 6 % 3 7 son(X,Y):- child(X,Y), male(X). 8 child(X,Y):- son(X,Y). 9 male(X):- son(X,Y). 10 child(george,mary). 11 child(george,fred). 12 male(george). We’ve made some assumptions in coding the knowledge, e.g., a groom and a husband are synonymous. We can make these notions more precise. For example, we could code that a man is no longer called a groom after the wedding is over. This program can be loaded on s(CASP) and queries executed against it. To verify that George has never been the groom at a wedding, we will pose the query:
?- not groom(george).
To check that Mary has an unmarried son born in Boston, we model the concept of an unmarried son born in a certain city:
umsbb(M,X,C):-son(X,M), birth_city(X,C), not married(X,Y,T). then pose the query:
?- umsbb(mary,X,boston).
Likwise, to check that no woman is the wife of any of Fred’s children, we define the rule: fred_child_wife(Y):-child(X,fred), married(X,Y,T), female(Y). then ask the query:
?- not fred_child_wife(X).
All of the above queries succeed. This example illustrates how close the ASP rules are to the commonsense knowledge that is to be represented.
Goal-directed ASP systems s(ASP) and s(CASP) have been used for many innovative applications. Some of these are described below. Many more such applications are possible. Undergraduate Degree Audit: Determining if a student can graduate with an undergraduate degree at a US University is a hard problem. Typically, the criteria for graduation are laid down as a set of rules in the University’s undergraduate catalog. These rules can change every year. An example rule for the mathematics major is as follows:
Nine semester credit hours of upper-division MATH, STAT or ACTS courses, at least six of which must be MATH courses at the 4000-level. These courses cannot include those for which the catalog entry states: May not be used to satisfy mathematics requirements by students in Mathematics.
Rules may involve negation and may be non-deterministic. A mistake made in interpreting or
applying a rule can delay a student’s graduation. An ASP-based degree audit system has been
developed by us for CS, Math and Statistics majors. If a student can’t graduate, relational nature
of ASP will allow the computation—without any additional efort—of list of potential courses
that the student must take that will allow him/her to graduate. A major advantage of using ASP
is that as the catalog is changed, importing these changes into the system is relatively easy.
Modeling Expert Knowledge: Human expert knowledge can be modeled in ASP. In
collaboration with cardiologists, we have developed the CHeF system for automated treatment
of congestive heart failure (CHF) disease. The system has been developed with the s(ASP)
predicate ASP system. [
Legal Reasoning: The formal representation of a legal text to automatize reasoning about
them is well known in literature, and is recently gaining much attention thanks to the interest in
Rules as Code [
Modeling Cyberphysical Systems: Goal-directed ASP systems such as s(CASP) can also be
used to elegantly model cyber-physical systems’ behaviour using the event calculus [
Software Certification: Software certification refers to assuring that a software system’s risk
is acceptable. The certification process is carried by a human expert using frameworks such as
claim-arguments-evidence framework [
Logic-based Learning: A goal-directed implementation of ASP also leads to a logic-based
framework for reinforcement learning. Suppose we learn a theory from observations and
examples, e.g., if X is a bird then it flies. Then we encounter Tweety the penguin. Our conclusion
that flies(tweety) fails, when we were expecting it to succeed. At this point we can learn
that penguins are exceptional birds that do not fly. This is done by examining the failed proof
and repairing the program so that the repaired program allows us to draw the correct conclusion.
This technique has been applied to learning and updating playing strategies in games [
There has been significant amount of work on developing expert systems since the 80s. Expert systems reason through knowledge that is represented declaratively as if-then rules rather than in a procedural manner. There are two problems with this if-then rule formulation wrt modeling human expertise: 1. The goal of expert systems technology was to model expert knowledge, however, as discussed earlier, simple if-then rules are inadequate for modeling human expertise. Humans also use co-inductive reasoning that is not easily modeled in traditional languages that limit themselves to inductive reasoning (cf. the “Who will go to Mexico?” example above). 2. If-then rules are only used for deductive reasoning, and as discussed earlier, humans use abductive reasoning as well.
Answer set programming allows human-style commonsense reasoning to be modeled more faithfully, something that the formalisms employed by earlier expert systems did not or could not. Our experience with the CHeF system shows that ASP can model the human thought process quite accurately. Thus, ASP can be thought of as a better formalism for building expert systems. In addition, the s(CASP) proof tree for a failed query can be examined and failure(s) cured by employing additional knowledge, giving rise to logic-based learning. Explanation based learning, where we generalize from a single example, and then refine the rule(s) as we encounter more information can also be modeled with ASP and s(CASP). The process is very similar to what a human may follow for reasoning and learning in his/her day-to-day life.
Cyc [50] is one of the oldest AI project that attempts to model commonsense reasoning. In
Cyc, knowledge is presented in the form of a vast collection of ontologies that consist of implicit
knowledge and rules about the world that represents commonsense knowledge. The ontology
of Cyc as of 2017 contains around 1,500,000 terms. This includes around 500,000 collections,
50,000+ predicates and around a million well known entities. Cyc uses a community of agents
consisting of multiple reasoning agents that rely on more than 1000 heuristic modules to solve
inference problems. A potential problem with Cyc is knowing which agent to apply, and which
heuristic to use. For a commonsense reasoning system to be successful, it has to be modeled in a
very simple way and very simple inference processes must be used. Otherwise, it will be hard to
determine which decision procedure to apply. In the ASP approach, we rely only on defaults
and exceptions, constraints and multiple possible worlds to emulate the human thought process.
If we use complex reasoning processes then we may possess the individual pieces of knowledge
to answer a given question, but may not be able to compose these pieces together appropriately
to arrive at an answer. Thus, simplicity of inference procedures is extremely important. Most
commonsense reasoning tasks involves just making a small number of inferences.
11. Conclusion
The main contribution of this paper is to show a path towards emulating human intelligence,
one of the most profound challenges in science. The paradigm of logic programming/ASP
and the s(CASP) system are a step in the direction of developing the machinery to construct
human-level intelligence. The critical pieces needed are ability to handle incomplete information,
circular or assumption-based reasoning, and representing multiple possible worlds. We argued
that the dogma of permitting only inductive semantics from the time of Russell has been a
major hindrance to automating commonsense reasoning. We showed how both deductive
and abductive reasoning can be elegantly modeled, and how default rules are an elegant way
of representing inductive generalizations in the sense of machine learning. Development of
coinductive semantics [
While ASP declaratively represents knowledge in the form that humans seem to represent, the s(CASP) system can be thought of as providing an operational semantics to the human thought process. This opens up interesting possibilities. For instance, a more eficient procedure can be derived by partial evaluation of the s(CASP) program that represents knowledge for a specific task. Thus, it should be possible to declaratively represent knowledge about concurrency, data structures and mutual exclusion, and then automatically derive eficient concurrent algorithms for various data structures by partial evaluation or similar suitable program transformation [51]. Given that ASP and s(CASP) can represent the human thought process, it should be possible to automate any task, as long as a human can perform it and the knowledge involved can be represented as axioms in ASP.
However, many challenges still remain:
• Humans acquire commonsense knowledge over a long period of time. The first challenge
is how do we create this commonsense knowledgebase? It will be ideal if it is created
automatically. At present, to develop a commonsense reasoning application using s(CASP),
knowledge has to be explicitly represented and the rules have to be explicitly coded in
(predicate) ASP. Inferences are then made (i.e., queries executed) using the s(CASP) system.
As long as the domain is narrow, it is possible to accomplish this. Scaling it up to larger
domains and large amount of commonsense knowledge is the next challenge.
• Humans can hear or read natural language sentences or look at a picture and store the
knowledge depicted in the sentence or the picture in their minds. Then, they use this
information to reason in conjunction with their commonsense knowledge. The second
challenge, thus, is how do we extract the knowledge in text, dialogs, and pictures and
represent it as predicates? Once this knowledge is represented as predicates, then we
can use automated commonsense reasoning to draw inferences just like humans do.
Perhaps machine learning techniques can be used to extract knowledge represented
as ASP predicates, much in the same manner as language translators from one natural
language to another are built, except that the target language here will be that of ASP
predicates.
• The s(CASP) system performs backward chaining. When attempting to prove a goal,
humans follow a similar process. However, as various concepts are utilized in the
goaldriven proof tree generation, humans may recall other concepts related to the concepts
used in the proof. These concepts may be used, for example, to advance a conversation.
For example, if I am responding to a question from someone about my favorite actor in
the movie ‘Titanic’, then the conversation may shift towards the movie’s director. This is
because the concept of a movie’s director and actor are closely related, even though the
movie’s director is not directly involved in the answer to the question. We believe that
such local forward chaining—using knowledge that connects related concepts—is needed
to build, for example, conversational socialbots based on commonsense reasoning [52].
Once the above challenges are overcome, really advanced applications such as chatbots that
can understand and answer like a human, autonomous driving systems [