CSCI - UA 9472 - Artificial Intelligence

Assignment 3: Logical reasoning

Given date: November 8
Due date: November 30
Total: 40 pts
In this third assignment, we will implement a simple Logical agent by relying on the resolution algorithm of Propositional Logic.

Introduction: logical propositions

The final objective will be to code our logical agent to succeed in a simple world similar to the Wumpus world discussed in the lectures. The final world we will consider is shown below.

Before designing the full agent, we will focus on a series of simplified environments (see below). In order to help you in your implementation, you are provided with the class 'Expr' and the associated function 'expr' which can be used to store and process logical propositions. The logical expressions are stored as objects consisting of an operator 'op' which can be of the types '&' (and), '|' (or) '==>' (implication) or '<=>' (double implication) as well as '~' (not). A logical expression such as 'A & B' can be stored as a string by means of the function expr() as expr('A & B') or Expr('&', 'A', 'B').

The function expr() takes operator precedence into account so that the two lines

In [ ]:
e = expr('A & B ==> C & D')

will return '==>'. The knowledge based can be created as a list of logical propositions.

In [18]:
'''source : AIMA'''

import collections

Number = (int, float, complex)
Expression = (Expr, Number)

def Symbol(name):
    """A Symbol is just an Expr with no args."""
    return Expr(name)

class Expr:
    """source: Artificial Intelligence: A Modern Approach
    A mathematical expression with an operator and 0 or more arguments.
    op is a str like '+' or 'sin'; args are Expressions.
    Expr('x') or Symbol('x') creates a symbol (a nullary Expr).
    Expr('-', x) creates a unary; Expr('+', x, 1) creates a binary."""

    def __init__(self, op, *args):
        self.op = str(op)
        self.args = args

    # Operator overloads
    def __neg__(self):
        return Expr('-', self)

    def __pos__(self):
        return Expr('+', self)

    def __invert__(self):
        return Expr('~', self)

    def __add__(self, rhs):
        return Expr('+', self, rhs)

    def __sub__(self, rhs):
        return Expr('-', self, rhs)

    def __mul__(self, rhs):
        return Expr('*', self, rhs)

    def __pow__(self, rhs):
        return Expr('**', self, rhs)

    def __mod__(self, rhs):
        return Expr('%', self, rhs)

    def __and__(self, rhs):
        return Expr('&', self, rhs)

    def __xor__(self, rhs):
        return Expr('^', self, rhs)

    def __rshift__(self, rhs):
        return Expr('>>', self, rhs)

    def __lshift__(self, rhs):
        return Expr('<<', self, rhs)

    def __truediv__(self, rhs):
        return Expr('/', self, rhs)

    def __floordiv__(self, rhs):
        return Expr('//', self, rhs)

    def __matmul__(self, rhs):
        return Expr('@', self, rhs)

    def __or__(self, rhs):
        """Allow both P | Q, and P |'==>'| Q."""
        if isinstance(rhs, Expression):
            return Expr('|', self, rhs)
            return PartialExpr(rhs, self)

    # Reverse operator overloads
    def __radd__(self, lhs):
        return Expr('+', lhs, self)

    def __rsub__(self, lhs):
        return Expr('-', lhs, self)

    def __rmul__(self, lhs):
        return Expr('*', lhs, self)

    def __rdiv__(self, lhs):
        return Expr('/', lhs, self)

    def __rpow__(self, lhs):
        return Expr('**', lhs, self)

    def __rmod__(self, lhs):
        return Expr('%', lhs, self)

    def __rand__(self, lhs):
        return Expr('&', lhs, self)

    def __rxor__(self, lhs):
        return Expr('^', lhs, self)

    def __ror__(self, lhs):
        return Expr('|', lhs, self)

    def __rrshift__(self, lhs):
        return Expr('>>', lhs, self)

    def __rlshift__(self, lhs):
        return Expr('<<', lhs, self)

    def __rtruediv__(self, lhs):
        return Expr('/', lhs, self)

    def __rfloordiv__(self, lhs):
        return Expr('//', lhs, self)

    def __rmatmul__(self, lhs):
        return Expr('@', lhs, self)

    def __call__(self, *args):
        """Call: if 'f' is a Symbol, then f(0) == Expr('f', 0)."""
        if self.args:
            raise ValueError('Can only do a call for a Symbol, not an Expr')
            return Expr(self.op, *args)

    # Equality and repr
    def __eq__(self, other):
        """x == y' evaluates to True or False; does not build an Expr."""
        return isinstance(other, Expr) and self.op == other.op and self.args == other.args

    def __lt__(self, other):
        return isinstance(other, Expr) and str(self) < str(other)

    def __hash__(self):
        return hash(self.op) ^ hash(self.args)

    def __repr__(self):
        op = self.op
        args = [str(arg) for arg in self.args]
        if op.isidentifier():  # f(x) or f(x, y)
            return '{}({})'.format(op, ', '.join(args)) if args else op
        elif len(args) == 1:  # -x or -(x + 1)
            return op + args[0]
        else:  # (x - y)
            opp = (' ' + op + ' ')
            return '(' + opp.join(args) + ')'

def expr(x):
    """Shortcut to create an Expression. x is a str in which:
    - identifiers are automatically defined as Symbols.
    - ==> is treated as an infix |'==>'|, as are <== and <=>.
    If x is already an Expression, it is returned unchanged. Example:
    >>> expr('P & Q ==> Q')
    ((P & Q) ==> Q)
    return eval(expr_handle_infix_ops(x), defaultkeydict(Symbol)) if isinstance(x, str) else x

def expr_handle_infix_ops(x):
    """Given a str, return a new str with ==> replaced by |'==>'|, etc.
    >>> expr_handle_infix_ops('P ==> Q')
    "P |'==>'| Q"
    for op in infix_ops:
        x = x.replace(op, '|' + repr(op) + '|')
    return x

infix_ops = '==> <== <=>'.split()

class defaultkeydict(collections.defaultdict):
    """Like defaultdict, but the default_factory is a function of the key.
    >>> d = defaultkeydict(len); d['four']

    def __missing__(self, key):
        self[key] = result = self.default_factory(key)
        return result

class PartialExpr:
    """Given 'P |'==>'| Q, first form PartialExpr('==>', P), then combine with Q."""

    def __init__(self, op, lhs):
        self.op, self.lhs = op, lhs

    def __or__(self, rhs):
        return Expr(self.op, self.lhs, rhs)

    def __repr__(self):
        return "PartialExpr('{}', {})".format(self.op, self.lhs)

Question 1: to CNF (7pts)

Now that we can create a knowledge base, in order to implement the resolution algorithm that will ultimately enable our agent to leverage the information from the environment, we need our sentences to written in conjunctive normal form (CNF). That requires a number of steps which are recalled below:

  • Biconditional elimination: $(\alpha \Leftrightarrow \beta) \equiv ((\alpha\Rightarrow \beta) \wedge (\beta \Rightarrow \alpha))$
  • Implication elimination $\alpha \Rightarrow \beta \equiv \lnot \alpha \vee \beta$
  • De Morgan's Law $\lnot (A\wedge B) = (\lnot A \vee \lnot B)$, $\lnot(\alpha \vee B) \equiv (\lnot A \wedge \lnot B)$
  • Distributivity of $\vee$ over $\wedge$: $(\alpha \vee (\beta \wedge \gamma)) \equiv ((\alpha \vee \beta) \wedge (\alpha \vee \gamma))$

Relying on the function propositional_exp given above (to avoid having all the questions depend on question 1, we will now rely on this implementation from AIMA), complete the function below which should return the CNF of the logical propostion $p$.

In [ ]:
def to_CNF(p):
    '''function should return the CNF of proposition p'''
    return CNF

Question 2: The resolution rule (7pts)

Now that you have a function that can turn any logical sentence to a CNF, we will code the resolution rule. For any two propositions $p_1$ and $p_2$ written in conjunctive normal form, write a function Resolution that returns empty if the resolution rule applied to the two sentences cannot produce any new sentence and that returns the set of all propositions $p_i$ following from the resolution of $p_1$ and $p_2$ otherwise.

Study the disjuncts of both $p_1$ and $p_2$. For each of the disjunct in $p_1$ try to find in $p_2$ the negation of that disjunct. If this negation appears, returns the proposition resulting from combining $p_1$ and $p_2$ with a disjunction.

In [ ]:
def resolution_rule(p_1, p_2):
    '''applies the resolution rule on two propositions p_1 and p_2'''

Question 3: The resolution algorithm (6pts)

Now that we have a resolution function we can embed it into a resolution algorithm. Complete the function Resolution below which implements the resolution algorithm. The algorithm takes as input a knowledge base written in conjunctive normal form, and a proposition $\alpha$ and should return true or false (as stored in the variable 'is_entailed') depending on whether $\alpha$ is entailed by the knowledge base KB.

In [ ]:
def resolution(KB, alpha):
    '''determines whether the sentence alpha 
    is entailed by the knowledge base KB. The 
    variable is_entailed should return true or false 
    according to the outcome'''
    return is_entailed

Question 4 (8pts): A first logical agent

Given our resolution algorithm, we will finally be able to design our first logical agent. As a first step, we consider a simple agent located on the bottom left cell of a 5 by 5 grid world. The world contains a single threat represented by a ghost which occupies a single cell and emits a loud noise ('OOooo') audible in the immediately adjacent cells.

To implement the agent, we will use the following approach:

Each cell will be represented by its (x,y) coordinate ((0,0) being the bottom leftmost cell). On top of this we will consider the following symbols

  • $D_{(x, y)}$ (which you can store as the string 'Dxy' or 'D_xy' as you want) indicating whether there is an exit on the cell or not (when the agent reach the exit, the simulation ends),

  • $G_{(x, y)}$ which encodes whether the ghost is located on cell $(x, y)$ or not

  • $O_{(x, y)}$ which encodes whether a "Ooooo" is heard on the cell $(x, y)$

Using those three symbols, the state of the world can be defined with a total of 3*25 symbols.

In a while loop running until the door is found, code a simple logical agent that moves at random in the non-threatening cells until it finds the escape cell. Also consider the following:

  • The agent should keep track of a knowledge base KB (list of logically true propositions together with a dictionnary storing the symbols that are known to be true) including all the sentences that the agent can generate based on the information it collected at the previous steps.
  • You might want to have a simple function, which given a symbol returns the adjacent symbols (symbols corresponding to spatially adjacent cells). you can store those as strings
  • The agent should be equipped with the resolution algorithm that you coded above. Before each new move, the next cell should be determined at random (from the set of all non visited cells) and the agent should use the resolution algorithm to determine whether the ghost is on the cell or not. If there is no indication that the ghost is located on the cell, the agent should make the move.

In [ ]:
exitNotFound = True

while exitNotFound:
    '''Agent should explore the world at random, probing the 
    knowledge base for any potential threat. if the KB does not 
    indicate any specific threat, the agent should move in one of 
    the adacent (cleared) cell. The simulation ends when the agent 
    reaches the exit door'''

Question 5: Getting used to danger.. (6pts)

Now that our agent knows how to handle a ghost, we will increase the level of risk by including spike traps in the environment.

  • Our agent has an edge: evolution has endowed it with a sort of additional ($6^{th}$) sense so that it can feel something 'bad' is about to happen when it is in a cell adjacent to a trap. We represent this ability with the eye combined with the exclamation mark.
  • Since, as we all know, ghosts are purely imaginary entities, the $6th$ sense only works for the spike traps.
  • The ghost can still be located by means of the noise it generates which can be heard on all adjacent cells.

Starting from the agent you designed in the previous questions, improve this agent so that it takes into account the spike traps. You should now have a knowledge base defined on a total of 25*5 symbols describing whether each cell contains a ghost, a 'OOoo' noise, a spike trap, activated the agent's'6th sense', or contains the exit door. The search ends when the agent reaches the door.

In [ ]:
exit_door = False 

while exit_door != True:
    '''Complete the loop with the simulation of the ghost 
    + spike trap logical agent. The simulation should start 
    from the bottom leftmost cell'''

Bonus: For where your treasure is.. (6pts)

We finally consider the whole environment. This environment is composed of all the elements from the previous questions but it now also includes a treasure chest. The final objective this time is to find the chest first and then reach the exit. Although some of the previous symbols are omitted for clarity, the ghost can always be located by means of the sound it produces, the agent can still trust its $6^{\text{th}}$ sense regarding the spike trap and the treasure chest can be perceived in adjacent cells, by means of the shine it produces.

When the knowledge base does not indicate any threat, the agent should move at random in one of the adjacent cells.

The world now contains a total of 25*7 symbols.

In [ ]:
treasure_notFound = True
exitFound = False

while treasure_notFound and exitFound!=True:
    '''Simulation should complete when the treasure chest 
    has been found and the exit has been reached. 
    The agent should start from bottom leftmost cell'''