logic.py

"""Representations and Inference for Logic (Chapters 7-9, 12)

Covers both Propositional and First-Order Logic. First we have four
important data types:

    KB            Abstract class holds a knowledge base of logical expressions
    KB_Agent      Abstract class subclasses agents.Agent
    Expr          A logical expression, imported from utils.py
    substitution  Implemented as a dictionary of var:value pairs, {x:1, y:x}

Be careful: some functions take an Expr as argument, and some take a KB.

Logical expressions can be created with Expr or expr, imported from utils, TODO
or with expr, which adds the capability to write a string that uses
the connectives ==>, <==, <=>, or <=/=>. But be careful: these have the
operator precedence of commas; you may need to add parens to make precedence work.
See logic.ipynb for examples.

Then we implement various functions for doing logical inference:

    pl_true          Evaluate a propositional logical sentence in a model
    tt_entails       Say if a statement is entailed by a KB
    pl_resolution    Do resolution on propositional sentences
    dpll_satisfiable See if a propositional sentence is satisfiable
    WalkSAT          Try to find a solution for a set of clauses

And a few other functions:

    to_cnf           Convert to conjunctive normal form
    unify            Do unification of two FOL sentences
    diff, simp       Symbolic differentiation and simplification
"""

from utils import (
    removeall, unique, first, argmax, probability,
    isnumber, issequence, Expr, expr, subexpressions
)
import agents

import itertools
import random
from collections import defaultdict

# ______________________________________________________________________________


class KB:

    """A knowledge base to which you can tell and ask sentences.
    To create a KB, first subclass this class and implement
    tell, ask_generator, and retract.  Why ask_generator instead of ask?
    The book is a bit vague on what ask means --
    For a Propositional Logic KB, ask(P & Q) returns True or False, but for an
    FOL KB, something like ask(Brother(x, y)) might return many substitutions
    such as {x: Cain, y: Abel}, {x: Abel, y: Cain}, {x: George, y: Jeb}, etc.
    So ask_generator generates these one at a time, and ask either returns the
    first one or returns False."""

    def __init__(self, sentence=None):
        raise NotImplementedError

    def tell(self, sentence):
        """Add the sentence to the KB."""
        raise NotImplementedError

    def ask(self, query):
        """Return a substitution that makes the query true, or, failing that, return False."""
        return first(self.ask_generator(query), default=False)

    def ask_generator(self, query):
        """Yield all the substitutions that make query true."""
        raise NotImplementedError

    def retract(self, sentence):
        """Remove sentence from the KB."""
        raise NotImplementedError


class PropKB(KB):
    """A KB for propositional logic. Inefficient, with no indexing."""

    def __init__(self, sentence=None):
        self.clauses = []
        if sentence:
            self.tell(sentence)

    def tell(self, sentence):
        """Add the sentence's clauses to the KB."""
        self.clauses.extend(conjuncts(to_cnf(sentence)))

    def ask_generator(self, query):
        """Yield the empty substitution {} if KB entails query; else no results."""
        if tt_entails(Expr('&', *self.clauses), query):
            yield {}

    def ask_if_true(self, query):
        """Return True if the KB entails query, else return False."""
        for _ in self.ask_generator(query):
            return True
        return False

    def retract(self, sentence):
        """Remove the sentence's clauses from the KB."""
        for c in conjuncts(to_cnf(sentence)):
            if c in self.clauses:
                self.clauses.remove(c)

# ______________________________________________________________________________


def KB_AgentProgram(KB):
    """A generic logical knowledge-based agent program. [Figure 7.1]"""
    steps = itertools.count()

    def program(percept):
        t = next(steps)
        KB.tell(make_percept_sentence(percept, t))
        action = KB.ask(make_action_query(t))
        KB.tell(make_action_sentence(action, t))
        return action

    def make_percept_sentence(percept, t):
        return Expr("Percept")(percept, t)

    def make_action_query(t):
        return expr("ShouldDo(action, {})".format(t))

    def make_action_sentence(action, t):
        return Expr("Did")(action[expr('action')], t)

    return program


def is_symbol(s):
    """A string s is a symbol if it starts with an alphabetic char."""
    return isinstance(s, str) and s[:1].isalpha()


def is_var_symbol(s):
    """A logic variable symbol is an initial-lowercase string."""
    return is_symbol(s) and s[0].islower()


def is_prop_symbol(s):
    """A proposition logic symbol is an initial-uppercase string."""
    return is_symbol(s) and s[0].isupper()


def variables(s):
    """Return a set of the variables in expression s.
    >>> variables(expr('F(x, x) & G(x, y) & H(y, z) & R(A, z, 2)')) == {x, y, z}
    True
    """
    return {x for x in subexpressions(s) if is_variable(x)}


def is_definite_clause(s):
    """Returns True for exprs s of the form A & B & ... & C ==> D,
    where all literals are positive.  In clause form, this is
    ~A | ~B | ... | ~C | D, where exactly one clause is positive.
    >>> is_definite_clause(expr('Farmer(Mac)'))
    True
    """
    if is_symbol(s.op):
        return True
    elif s.op == '==>':
        antecedent, consequent = s.args
        return (is_symbol(consequent.op) and
                all(is_symbol(arg.op) for arg in conjuncts(antecedent)))
    else:
        return False


def parse_definite_clause(s):
    """Return the antecedents and the consequent of a definite clause."""
    assert is_definite_clause(s)
    if is_symbol(s.op):
        return [], s
    else:
        antecedent, consequent = s.args
        return conjuncts(antecedent), consequent


# Useful constant Exprs used in examples and code:
A, B, C, D, E, F, G, P, Q, x, y, z = map(Expr, 'ABCDEFGPQxyz')


# ______________________________________________________________________________


def tt_entails(kb, alpha):
    """Does kb entail the sentence alpha? Use truth tables. For propositional
    kb's and sentences. [Figure 7.10]. Note that the 'kb' should be an
    Expr which is a conjunction of clauses.
    >>> tt_entails(expr('P & Q'), expr('Q'))
    True
    """
    assert not variables(alpha)
    symbols = list(prop_symbols(kb & alpha))
    return tt_check_all(kb, alpha, symbols, {})


def tt_check_all(kb, alpha, symbols, model):
    """Auxiliary routine to implement tt_entails."""
    if not symbols:
        if pl_true(kb, model):
            result = pl_true(alpha, model)
            assert result in (True, False)
            return result
        else:
            return True
    else:
        P, rest = symbols[0], symbols[1:]
        return (tt_check_all(kb, alpha, rest, extend(model, P, True)) and
                tt_check_all(kb, alpha, rest, extend(model, P, False)))


def prop_symbols(x):
    """Return the set of all propositional symbols in x."""
    if not isinstance(x, Expr):
        return set()
    elif is_prop_symbol(x.op):
        return {x}
    else:
        return {symbol for arg in x.args for symbol in prop_symbols(arg)}


def constant_symbols(x):
    """Return the set of all constant symbols in x."""
    if not isinstance(x, Expr):
        return set()
    elif is_prop_symbol(x.op) and not x.args:
        return {x}
    else:
        return {symbol for arg in x.args for symbol in constant_symbols(arg)}


def predicate_symbols(x):
    """Return a set of (symbol_name, arity) in x.
    All symbols (even functional) with arity > 0 are considered."""
    if not isinstance(x, Expr) or not x.args:
        return set()
    pred_set = {(x.op, len(x.args))} if is_prop_symbol(x.op) else set()
    pred_set.update({symbol for arg in x.args for symbol in predicate_symbols(arg)})
    return pred_set


def tt_true(s):
    """Is a propositional sentence a tautology?
    >>> tt_true('P | ~P')
    True
    """
    s = expr(s)
    return tt_entails(True, s)


def pl_true(exp, model={}):
    """Return True if the propositional logic expression is true in the model,
    and False if it is false. If the model does not specify the value for
    every proposition, this may return None to indicate 'not obvious';
    this may happen even when the expression is tautological."""
    if exp in (True, False):
        return exp
    op, args = exp.op, exp.args
    if is_prop_symbol(op):
        return model.get(exp)
    elif op == '~':
        p = pl_true(args[0], model)
        if p is None:
            return None
        else:
            return not p
    elif op == '|':
        result = False
        for arg in args:
            p = pl_true(arg, model)
            if p is True:
                return True
            if p is None:
                result = None
        return result
    elif op == '&':
        result = True
        for arg in args:
            p = pl_true(arg, model)
            if p is False:
                return False
            if p is None:
                result = None
        return result
    p, q = args
    if op == '==>':
        return pl_true(~p | q, model)
    elif op == '<==':
        return pl_true(p | ~q, model)
    pt = pl_true(p, model)
    if pt is None:
        return None
    qt = pl_true(q, model)
    if qt is None:
        return None
    if op == '<=>':
        return pt == qt
    elif op == '^':  # xor or 'not equivalent'
        return pt != qt
    else:
        raise ValueError("illegal operator in logic expression" + str(exp))

# ______________________________________________________________________________

# Convert to Conjunctive Normal Form (CNF)


def to_cnf(s):
    """Convert a propositional logical sentence to conjunctive normal form.
    That is, to the form ((A | ~B | ...) & (B | C | ...) & ...) [p. 253]
    >>> to_cnf('~(B | C)')
    (~B & ~C)
    """
    s = expr(s)
    if isinstance(s, str):
        s = expr(s)
    s = eliminate_implications(s)  # Steps 1, 2 from p. 253
    s = move_not_inwards(s)  # Step 3
    return distribute_and_over_or(s)  # Step 4


def eliminate_implications(s):
    """Change implications into equivalent form with only &, |, and ~ as logical operators."""
    s = expr(s)
    if not s.args or is_symbol(s.op):
        return s  # Atoms are unchanged.
    args = list(map(eliminate_implications, s.args))
    a, b = args[0], args[-1]
    if s.op == '==>':
        return b | ~a
    elif s.op == '<==':
        return a | ~b
    elif s.op == '<=>':
        return (a | ~b) & (b | ~a)
    elif s.op == '^':
        assert len(args) == 2  # TODO: relax this restriction
        return (a & ~b) | (~a & b)
    else:
        assert s.op in ('&', '|', '~')
        return Expr(s.op, *args)


def move_not_inwards(s):
    """Rewrite sentence s by moving negation sign inward.
    >>> move_not_inwards(~(A | B))
    (~A & ~B)"""
    s = expr(s)
    if s.op == '~':
        def NOT(b):
            return move_not_inwards(~b)
        a = s.args[0]
        if a.op == '~':
            return move_not_inwards(a.args[0])  # ~~A ==> A
        if a.op == '&':
            return associate('|', list(map(NOT, a.args)))
        if a.op == '|':
            return associate('&', list(map(NOT, a.args)))
        return s
    elif is_symbol(s.op) or not s.args:
        return s
    else:
        return Expr(s.op, *list(map(move_not_inwards, s.args)))


def distribute_and_over_or(s):
    """Given a sentence s consisting of conjunctions and disjunctions
    of literals, return an equivalent sentence in CNF.
    >>> distribute_and_over_or((A & B) | C)
    ((A | C) & (B | C))
    """
    s = expr(s)
    if s.op == '|':
        s = associate('|', s.args)
        if s.op != '|':
            return distribute_and_over_or(s)
        if len(s.args) == 0:
            return False
        if len(s.args) == 1:
            return distribute_and_over_or(s.args[0])
        conj = first(arg for arg in s.args if arg.op == '&')
        if not conj:
            return s
        others = [a for a in s.args if a is not conj]
        rest = associate('|', others)
        return associate('&', [distribute_and_over_or(c | rest)
                               for c in conj.args])
    elif s.op == '&':
        return associate('&', list(map(distribute_and_over_or, s.args)))
    else:
        return s


def associate(op, args):
    """Given an associative op, return an expression with the same
    meaning as Expr(op, *args), but flattened -- that is, with nested
    instances of the same op promoted to the top level.
    >>> associate('&', [(A&B),(B|C),(B&C)])
    (A & B & (B | C) & B & C)
    >>> associate('|', [A|(B|(C|(A&B)))])
    (A | B | C | (A & B))
    """
    args = dissociate(op, args)
    if len(args) == 0:
        return _op_identity[op]
    elif len(args) == 1:
        return args[0]
    else:
        return Expr(op, *args)


_op_identity = {'&': True, '|': False, '+': 0, '*': 1}


def dissociate(op, args):
    """Given an associative op, return a flattened list result such
    that Expr(op, *result) means the same as Expr(op, *args)."""
    result = []

    def collect(subargs):
        for arg in subargs:
            if arg.op == op:
                collect(arg.args)
            else:
                result.append(arg)
    collect(args)
    return result


def conjuncts(s):
    """Return a list of the conjuncts in the sentence s.
    >>> conjuncts(A & B)
    [A, B]
    >>> conjuncts(A | B)
    [(A | B)]
    """
    return dissociate('&', [s])


def disjuncts(s):
    """Return a list of the disjuncts in the sentence s.
    >>> disjuncts(A | B)
    [A, B]
    >>> disjuncts(A & B)
    [(A & B)]
    """
    return dissociate('|', [s])

# ______________________________________________________________________________


def pl_resolution(KB, alpha):
    """Propositional-logic resolution: say if alpha follows from KB. [Figure 7.12]"""
    clauses = KB.clauses + conjuncts(to_cnf(~alpha))
    new = set()
    while True:
        n = len(clauses)
        pairs = [(clauses[i], clauses[j])
                 for i in range(n) for j in range(i+1, n)]
        for (ci, cj) in pairs:
            resolvents = pl_resolve(ci, cj)
            if False in resolvents:
                return True
            new = new.union(set(resolvents))
        if new.issubset(set(clauses)):
            return False
        for c in new:
            if c not in clauses:
                clauses.append(c)


def pl_resolve(ci, cj):
    """Return all clauses that can be obtained by resolving clauses ci and cj."""
    clauses = []
    for di in disjuncts(ci):
        for dj in disjuncts(cj):
            if di == ~dj or ~di == dj:
                dnew = unique(removeall(di, disjuncts(ci)) +
                              removeall(dj, disjuncts(cj)))
                clauses.append(associate('|', dnew))
    return clauses

# ______________________________________________________________________________


class PropDefiniteKB(PropKB):
    """A KB of propositional definite clauses."""

    def tell(self, sentence):
        """Add a definite clause to this KB."""
        assert is_definite_clause(sentence), "Must be definite clause"
        self.clauses.append(sentence)

    def ask_generator(self, query):
        """Yield the empty substitution if KB implies query; else nothing."""
        if pl_fc_entails(self.clauses, query):
            yield {}

    def retract(self, sentence):
        self.clauses.remove(sentence)

    def clauses_with_premise(self, p):
        """Return a list of the clauses in KB that have p in their premise.
        This could be cached away for O(1) speed, but we'll recompute it."""
        return [c for c in self.clauses
                if c.op == '==>' and p in conjuncts(c.args[0])]


def pl_fc_entails(KB, q):
    """Use forward chaining to see if a PropDefiniteKB entails symbol q.
    [Figure 7.15]
    >>> pl_fc_entails(horn_clauses_KB, expr('Q'))
    True
    """
    count = {c: len(conjuncts(c.args[0]))
             for c in KB.clauses
             if c.op == '==>'}
    inferred = defaultdict(bool)
    agenda = [s for s in KB.clauses if is_prop_symbol(s.op)]
    while agenda:
        p = agenda.pop()
        if p == q:
            return True
        if not inferred[p]:
            inferred[p] = True
            for c in KB.clauses_with_premise(p):
                count[c] -= 1
                if count[c] == 0:
                    agenda.append(c.args[1])
    return False


""" [Figure 7.13]
Simple inference in a wumpus world example
"""
wumpus_world_inference = expr("(B11 <=> (P12 | P21))  &  ~B11")


""" [Figure 7.16]
Propositional Logic Forward Chaining example
"""
horn_clauses_KB = PropDefiniteKB()
for s in "P==>Q; (L&M)==>P; (B&L)==>M; (A&P)==>L; (A&B)==>L; A;B".split(';'):
    horn_clauses_KB.tell(expr(s))

# ______________________________________________________________________________
# DPLL-Satisfiable [Figure 7.17]


def dpll_satisfiable(s):
    """Check satisfiability of a propositional sentence.
    This differs from the book code in two ways: (1) it returns a model
    rather than True when it succeeds; this is more useful. (2) The
    function find_pure_symbol is passed a list of unknown clauses, rather
    than a list of all clauses and the model; this is more efficient."""
    clauses = conjuncts(to_cnf(s))
    symbols = list(prop_symbols(s))
    return dpll(clauses, symbols, {})


def dpll(clauses, symbols, model):
    """See if the clauses are true in a partial model."""
    unknown_clauses = []  # clauses with an unknown truth value
    for c in clauses:
        val = pl_true(c, model)
        if val is False:
            return False
        if val is not True:
            unknown_clauses.append(c)
    if not unknown_clauses:
        return model
    P, value = find_pure_symbol(symbols, unknown_clauses)
    if P:
        return dpll(clauses, removeall(P, symbols), extend(model, P, value))
    P, value = find_unit_clause(clauses, model)
    if P:
        return dpll(clauses, removeall(P, symbols), extend(model, P, value))
    if not symbols:
        raise TypeError("Argument should be of the type Expr.")
    P, symbols = symbols[0], symbols[1:]
    return (dpll(clauses, symbols, extend(model, P, True)) or
            dpll(clauses, symbols, extend(model, P, False)))


def find_pure_symbol(symbols, clauses):
    """Find a symbol and its value if it appears only as a positive literal
    (or only as a negative) in clauses.
    >>> find_pure_symbol([A, B, C], [A|~B,~B|~C,C|A])
    (A, True)
    """
    for s in symbols:
        found_pos, found_neg = False, False
        for c in clauses:
            if not found_pos and s in disjuncts(c):
                found_pos = True
            if not found_neg and ~s in disjuncts(c):
                found_neg = True
        if found_pos != found_neg:
            return s, found_pos
    return None, None


def find_unit_clause(clauses, model):
    """Find a forced assignment if possible from a clause with only 1
    variable not bound in the model.
    >>> find_unit_clause([A|B|C, B|~C, ~A|~B], {A:True})
    (B, False)
    """
    for clause in clauses:
        P, value = unit_clause_assign(clause, model)
        if P:
            return P, value
    return None, None


def unit_clause_assign(clause, model):
    """Return a single variable/value pair that makes clause true in
    the model, if possible.
    >>> unit_clause_assign(A|B|C, {A:True})
    (None, None)
    >>> unit_clause_assign(B|~C, {A:True})
    (None, None)
    >>> unit_clause_assign(~A|~B, {A:True})
    (B, False)
    """
    P, value = None, None
    for literal in disjuncts(clause):
        sym, positive = inspect_literal(literal)
        if sym in model:
            if model[sym] == positive:
                return None, None  # clause already True
        elif P:
            return None, None      # more than 1 unbound variable
        else:
            P, value = sym, positive
    return P, value


def inspect_literal(literal):
    """The symbol in this literal, and the value it should take to
    make the literal true.
    >>> inspect_literal(P)
    (P, True)
    >>> inspect_literal(~P)
    (P, False)
    """
    if literal.op == '~':
        return literal.args[0], False
    else:
        return literal, True

# ______________________________________________________________________________
# Walk-SAT [Figure 7.18]


def WalkSAT(clauses, p=0.5, max_flips=10000):
    """Checks for satisfiability of all clauses by randomly flipping values of variables
    """
    # Set of all symbols in all clauses
    symbols = {sym for clause in clauses for sym in prop_symbols(clause)}
    # model is a random assignment of true/false to the symbols in clauses
    model = {s: random.choice([True, False]) for s in symbols}
    for i in range(max_flips):
        satisfied, unsatisfied = [], []
        for clause in clauses:
            (satisfied if pl_true(clause, model) else unsatisfied).append(clause)
        if not unsatisfied:  # if model satisfies all the clauses
            return model
        clause = random.choice(unsatisfied)
        if probability(p):
            sym = random.choice(list(prop_symbols(clause)))
        else:
            # Flip the symbol in clause that maximizes number of sat. clauses
            def sat_count(sym):
                # Return the the number of clauses satisfied after flipping the symbol.
                model[sym] = not model[sym]
                count = len([clause for clause in clauses if pl_true(clause, model)])
                model[sym] = not model[sym]
                return count
            sym = argmax(prop_symbols(clause), key=sat_count)
        model[sym] = not model[sym]
    # If no solution is found within the flip limit, we return failure
    return None

# ______________________________________________________________________________


class WumpusKB(PropKB):
    """
    Create a Knowledge Base that contains the atemporal "Wumpus physics" and temporal rules with time zero.
    """
    def __init__(self,dimrow):
        super().__init__()
        self.dimrow = dimrow
        self.tell('( NOT W1s1 )')
        self.tell('( NOT P1s1 )')
        for i in range(1, dimrow+1):
            for j in range(1, dimrow+1):
                bracket = 0
                sentence_b_str = "( B" + i + "s" + j + " <=> "
                sentence_s_str = "( S" + i + "s" + j + " <=> "
                if i > 1:
                    sentence_b_str += "( P" + (i-1) + "s" + j + " OR "
                    sentence_s_str += "( W" + (i-1) + "s" + j + " OR "
                    bracket += 1

                if i < dimRow:
                    sentence_b_str += "( P" + (i+1) + "s" + j + " OR "
                    sentence_s_str += "( W" + (i+1) + "s" + j + " OR "
                    bracket += 1

                if j > 1:
                    if j == dimRow:
                        sentence_b_str += "P" + i + "s" + (j-1) + " "
                        sentence_s_str += "W "+ i + "s" + (j-1) + " "
                    else:
                        sentence_b_str += "( P" + i + "s" + (j-1) + " OR "
                        sentence_s_str += "( W" + i + "s" + (j-1) + " OR "
                        bracket += 1

                if j < dimRow:
                    sentence_b_str += "P" + i + "s" + (j+1) + " "
                    sentence_s_str += "W" + i + "s" + (j+1) + " "


                for _ in range(bracket):
                    sentence_b_str += ") "
                    sentence_s_str += ") "

                sentence_b_str += ") "
                sentence_s_str += ") "

                self.tell(sentence_b_str)
                self.tell(sentence_s_str)


        ## Rule that describes existence of at least one Wumpus
        sentence_w_str = ""
        for i in range(1, dimrow+1):
            for j in range(1, dimrow+1):
                if (i == dimrow) and (j == dimrow):
                    sentence_w_str += " W" + dimRow + "s" + dimrow + " "
                else:
                    sentence_w_str += "( W" + i + "s" + j + " OR "
        for _ in range(dimrow**2):
            sentence_w_str += ") "
        self.tell(sentence_w_str)


        ## Rule that describes existence of at most one Wumpus
        for i in range(1, dimrow+1):
            for j in range(1, dimrow+1):
                for u in range(1, dimrow+1):
                    for v in range(1, dimrow+1):
                        if i!=u or j!=v:
                            self.tell("( ( NOT W" + i + "s" + j + " ) OR ( NOT W" + u + "s" + v + " ) )")

        ## Temporal rules at time zero
        self.tell("L1s1s0")
        for i in range(1, dimrow+1):
            for j in range(1, dimrow + 1):
                self.tell("( L" + i + "s" + j + "s0 => ( Breeze0 <=> B" + i + "s" + j + " ) )")
                self.tell("( L" + i + "s" + j + "s0 => ( Stench0 <=> S" + i + "s" + j + " ) )")
                if i != 1 or j != 1:
                    self.tell("( NOT L" + i + "s" + j + "s" + "0 )")
        self.tell("WumpusAlive0")
        self.tell("HaveArrow0")
        self.tell("FacingEast0")
        self.tell("( NOT FacingWest0 )")
        self.tell("( NOT FacingNorth0 )")
        self.tell("( NOT FacingSouth0 )")


    def make_action_sentence(self, action, time):
        self.tell(action + time)


    def make_percept_sentence(self, percept, time):
        self.tell(percept + time)

    def add_temporal_sentences(self, time):
        if time == 0:
            return
        t = time - 1

        ## current location rules (L2s2s3 represent tile 2,2 at time 3)
        ## ex.: ( L2s2s3 <=> ( ( L2s2s2 AND ( ( NOT Forward2 ) OR Bump3 ) )
        ## OR ( ( L1s2s2 AND ( FacingEast2 AND Forward2 ) ) OR ( L2s1s2 AND ( FacingNorth2 AND Forward2 ) ) )
        for i in range(1, self.dimrow+1):
            for j in range(1, self.dimrow+1):
                self.tell("( L" + i + "s" + j + "s" + time + " => ( Breeze" + time + " <=> B" + i + "s" + j + " ) )")
                self.tell("( L" + i + "s" + j + "s" + time + " => ( Stench" + time + " <=> S" + i + "s" + j + " ) )")
                s = "( L" + i + "s" + j + "s" + time + " <=> ( ( L" + i + "s" + j + "s" + t + " AND ( ( NOT Forward"\
                    + t + " ) OR Bump" + time + " ) )"

                count = 2
                if i != 1:
                    s += " OR ( ( L" + (i - 1) + "s" + j + "s" + t + " AND ( FacingEast" + t + " AND Forward" + t\
                         + " ) )"
                    count += 1
                if i != self.dimrow:
                    s += " OR ( ( L" + (i + 1) + "s" + j + "s" + t + " AND ( FacingWest" + t + " AND Forward" + t\
                         + " ) )"
                    count += 1
                if j != 1:
                    if j == self.dimrow:
                        s += " OR ( L" + i + "s" + (j - 1) + "s" + t + " AND ( FacingNorth" + t + " AND Forward" + t\
                             + " ) )"
                    else:
                        s += " OR ( ( L" + i + "s" + (j - 1) + "s" + t + " AND ( FacingNorth" + t + " AND Forward" \
                             + t + " ) )"
                        count += 1
                if j != self.dimrow:
                    s += " OR ( L" + i + "s" + (j + 1) + "s" + t + " AND ( FacingSouth" + t + " AND Forward" + t\
                         + " ) )"

                for _ in range(count):
                    s += " )"

                ## add sentence about location i,j
                self.tell(s)

                ## add sentence about safety of location i,j
                self.tell("( OK" + i + "s" + j + "s" + time + " <=> ( ( NOT P" + i + "s" + j + " ) AND ( NOT ( W" + i\
                          + "s" + j + " AND WumpusAlive" + time + " ) ) ) )")

        ## Rules about current orientation
        ## ex.: ( FacingEast3 <=> ( ( FacingNorth2 AND TurnRight2 ) OR ( ( FacingSouth2 AND TurnLeft2 )
        ## OR ( FacingEast2 AND ( ( NOT TurnRight2 ) AND ( NOT TurnLeft2 ) ) ) ) ) )
        a = "( FacingNorth" + t + " AND TurnRight" + t + " )"
        b = "( FacingSouth" + t + " AND TurnLeft" + t + " )"
        c = "( FacingEast" + t + " AND ( ( NOT TurnRight" + t + " ) AND ( NOT TurnLeft" + t + " ) ) )"
        s = "( FacingEast" + (t + 1) + " <=> ( " + a + " OR ( " + b + " OR " + c + " ) ) )"
        this.tell(s)

        a = "( FacingNorth" + t + " AND TurnLeft" + t + " )"
        b = "( FacingSouth" + t + " AND TurnRight" + t + " )"
        c = "( FacingWest" + t + " AND ( ( NOT TurnRight" + t + " ) AND ( NOT TurnLeft" + t + " ) ) )"
        s = "( FacingWest" + (t + 1) + " <=> ( " + a + " OR ( " + b + " OR " + c + " ) ) )"
        this.tell(s)

        a = "( FacingEast" + t + " AND TurnLeft" + t + " )"
        b = "( FacingWest" + t + " AND TurnRight" + t + " )"
        c = "( FacingNorth" + t + " AND ( ( NOT TurnRight" + t + " ) AND ( NOT TurnLeft" + t + " ) ) )"
        s = "( FacingNorth" + (t + 1) + " <=> ( " + a + " OR ( " + b + " OR " + c + " ) ) )"
        this.tell(s)

        a = "( FacingWest" + t + " AND TurnLeft" + t + " )"
        b = "( FacingEast" + t + " AND TurnRight" + t + " )"
        c = "( FacingSouth" + t + " AND ( ( NOT TurnRight" + t + " ) AND ( NOT TurnLeft" + t + " ) ) )"
        s = "( FacingSouth" + (t + 1) + " <=> ( " + a + " OR ( " + b + " OR " + c + " ) ) )"
        this.tell(s)

        ## Rules about last action
        self.tell("( Forward" + t + " <=> ( NOT TurnRight" + t + " ) )")
        self.tell("( Forward" + t + " <=> ( NOT TurnLeft" + t + " ) )")

        ##Rule about the arrow
        self.tell("( HaveArrow" + time + " <=> ( HaveArrow" + (time - 1) + " AND ( NOT Shot" + (time - 1) + " ) ) )")

        ##Rule about Wumpus (dead or alive)
        self.tell("( WumpusAlive" + time + " <=> ( WumpusAlive" + (time - 1) + " AND ( NOT Scream" + time + " ) ) )")

        
# ______________________________________________________________________________


class WumpusPosition():
    def __init__(self, X, Y, orientation):
        self.X = X
        self.Y = Y
        self.orientation = orientation


    def get_location(self):
        return self.X, self.Y

    def get_orientation(self):
        return self.orientation

    def equals(self, wumpus_position):
        if wumpus_position.get_location() == self.get_location() and \
                        wumpus_position.get_orientation()==self.get_orientation():
            return True
        else:
            return False
        
# ______________________________________________________________________________


class HybridWumpusAgent(agents.Agent):
    """An agent for the wumpus world that does logical inference. [Figure 7.20]"""

    def __init__(self):
        super().__init__()
        self.dimrow = 3
        self.kb = WumpusKB(self.dimrow)
        self.t = 0
        self.plan = list()
        self.current_position = WumpusPosition(1, 1, 'UP')


    def execute(self, percept):
        self.kb.make_percept_sentence(percept, self.t)
        self.kb.add_temporal_sentences(self.t)

        temp = list()

        for i in range(1, self.dimrow+1):
            for j in range(1, self.dimrow+1):
                if self.kb.ask_with_dpll('L' + i + 's' + j + 's' + self.t):
                    temp.append(i)
                    temp.append(j)

        if self.kb.ask_with_dpll('FacingNorth' + self.t):
            self.current_position = WumpusPosition(temp[0], temp[1], 'UP')
        elif self.kb.ask_with_dpll('FacingSouth' + self.t):
            self.current_position = WumpusPosition(temp[0], temp[1], 'DOWN')
        elif self.kb.ask_with_dpll('FacingWest' + self.t):
            self.current_position = WumpusPosition(temp[0], temp[1], 'LEFT')
        elif self.kb.ask_with_dpll('FacingEast' + self.t):
            self.current_position = WumpusPosition(temp[0], temp[1], 'RIGHT')

        safe_points = list()
        for i in range(1, self.dimrow+1):
            for j in range(1, self.dimrow+1):
                if self.kb.ask_with_dpll('OK' + i + 's' + j + 's' + self.t):
                    safe_points.append([i, j])

        if self.kb.ask_with_dpll('Glitter' + self.t):
            goals = list()
            goals.append([1, 1])
            self.plan.append('Grab')
            actions = plan_route(self.current_position,goals,safe_points)
            for action in actions:
                self.plan.append(action)
            self.plan.append('Climb')

        if len(self.plan) == 0:
            unvisited = list()
            for i in range(1, self.dimrow+1):
                for j in range(1, self.dimrow+1):
                    for k in range(1, self.dimrow+1):
                        if self.kb.ask_with_dpll("L" + i + "s" + j + "s" + k):
                            unvisited.append([i, j])
            unvisited_and_safe = list()
            for u in unvisited:
                for s in safe_points:
                    if u not in unvisited_and_safe and s == u:
                        unvisited_and_safe.append(u)

            temp = plan_route(self.current_position,unvisited_and_safe,safe_points)
            for t in temp:
                self.plan.append(t)

        if len(self.plan) == 0 and self.kb.ask_with_dpll('HaveArrow' + self.t):
            possible_wumpus = list()
            for i in range(1, self.dimrow+1):
                for j in range(1, self.dimrow+1):
                    if not self.kb.ask_with_dpll('W' + i + 's' + j):
                        possible_wumpus.append([i, j])

            temp = plan_shot(self.current_position, possible_wumpus, safe_points)
            for t in temp:
                self.plan.append(t)

        if len(self.plan) == 0:
            not_unsafe = list()
            for i in range(1, self.dimrow+1):
                for j in range(1, self.dimrow+1):
                    if not self.kb.ask_with_dpll('OK' + i + 's' + j + 's' + self.t):
                        not_unsafe.append([i, j])
            temp = plan_route(self.current_position, not_unsafe, safe_points)
            for t in temp:
                self.plan.append(t)

        if len(self.plan) == 0:
            start = list()
            start.append([1, 1])
            temp = plan_route(self.current_position, start, safe_points)
            for t in temp:
                self.plan.append(t)
            self.plan.append('Climb')



        action = self.plan[1:]

        self.kb.make_action_sentence(action, self.t)
        self.t += 1

        return action


def plan_route(current, goals, allowed):