MPDL
Computing Research Methods Multi-Perspective Digital Library
|
|
|
Guests are welcome to view our materials. To subscribe, edit, view raw markup, etc., you'll need to register for an account. Accounts are free (and will always be free) - your involvement helps us directly and indirectly (by demonstrating that our work matters to our funders...) StartingPoints has more info.
MPDL » FOLWumpusLab » FOLWumpusLabReports
Introduction:FOL Wumpus lab make you understand about First Order Logic in terms of Wumpus world. This lab also help in a better hands-on Python, as we executed the Python implementation of Wumpus World as FOL. Later after understand we come up with the Research question on this version of wumpus world.The basic Outline of FOL Wumpus Lab Report 1. Intregating our FOL knowledge with knowledge engineering. 2. Implementing the Wumpus world as functionality of FOL. 3. And also get a hand on Python,by executing python implementation of Wumpus World as FOLKnowledge engineering in FOLIdentify the task Assemble the relevant knowledge Decide on a vocabulary of predicates, functions, and constants Encode general knowledge about the domain Encode a description of the specific problem instance Pose queries to the inference procedure and get answers Debug the knowledge baseImplementing the Wumpus world as functionality of FOL.Propositional and First-Order Logic is implemented as follows:
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
substitution Implemented as a dictionary of var:value pairs, {x:1, y:x}
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 (not yet implemented)
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 __future__ import generators
import re
import agents
from utils import *
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):
abstract
def tell(self, sentence):
"Add the sentence to the KB"
abstract
def ask(self, query):
"""Ask returns a substitution that makes the query true, or
it returns False. It is implemented in terms of ask_generator."""
try:
return self.ask_generator(query).next()
except StopIteration:
return False
def ask_generator(self, query):
"Yield all the substitutions that make query true."
abstract
def retract(self, sentence):
"Remove the sentence from the KB"
abstract
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 implies query; else False"
if not tt_entails(Expr('&', *self.clauses), query):
return
yield {}
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)
class KB_Agent(agents.Agent):
"""A generic logical knowledge-based agent. [Fig. 7.1]"""
def __init__(self, KB):
t = 0
def program(percept):
KB.tell(self.make_percept_sentence(percept, t))
action = KB.ask(self.make_action_query(t))
KB.tell(self.make_action_sentence(action, t))
t = t + 1
return action
self.program = program
def make_percept_sentence(self, percept, t):
return(Expr("Percept")(percept, t))
def make_action_query(self, t):
return(expr("ShouldDo(action, %d)" % t))
def make_action_sentence(self, action, t):
return(Expr("Did")(action, t))
class Expr:
"""A symbolic mathematical expression. We use this class for logical
expressions, and for terms within logical expressions. In general, an
Expr has an op (operator) and a list of args. The op can be:
Null-ary (no args) op:
A number, representing the number itself. (e.g. Expr(42) => 42)
A symbol, representing a variable or constant (e.g. Expr('F') => F)
Unary (1 arg) op:
'~', '-', representing NOT, negation (e.g. Expr('~', Expr('P')) => ~P)
Binary (2 arg) op:
'>>', '<<', representing forward and backward implication
'+', '-', '*', '/', '**', representing arithmetic operators
'<', '>', '>=', '<=', representing comparison operators
'<=>', '^', representing logical equality and XOR
N-ary (0 or more args) op:
'&', '|', representing conjunction and disjunction
A symbol, representing a function term or FOL proposition
Exprs can be constructed with operator overloading: if x and y are Exprs,
then so are x + y and x & y, etc. Also, if F and x are Exprs, then so is
F(x); it works by overloading the __call__ method of the Expr F. Note
that in the Expr that is created by F(x), the op is the str 'F', not the
Expr F. See http://www.python.org/doc/current/ref/specialnames.html
to learn more about operator overloading in Python.
WARNING: x == y and x != y are NOT Exprs. The reason is that we want
to write code that tests 'if x == y:' and if x == y were the same
as Expr('==', x, y), then the result would always be true; not what a
programmer would expect. But we still need to form Exprs representing
equalities and disequalities. We concentrate on logical equality (or
equivalence) and logical disequality (or XOR). You have 3 choices:
(1) Expr('<=>', x, y) and Expr('^', x, y)
Note that ^ is bitwose XOR in Python (and Java and C++)
(2) expr('x <=> y') and expr('x =/= y').
See the doc string for the function expr.
(3) (x % y) and (x ^ y).
It is very ugly to have (x % y) mean (x <=> y), but we need
SOME operator to make (2) work, and this seems the best choice.
WARNING: if x is an Expr, then so is x + 1, because the int 1 gets
coerced to an Expr by the constructor. But 1 + x is an error, because
1 doesn't know how to add an Expr. (Adding an __radd__ method to Expr
wouldn't help, because int.__add__ is still called first.) Therefore,
you should use Expr(1) + x instead, or ONE + x, or expr('1 + x').
"""
def __init__(self, op, *args):
"Op is a string or number; args are Exprs (or are coerced to Exprs)."
assert isinstance(op, str) or (isnumber(op) and not args)
self.op = num_or_str(op)
self.args = map(expr, args) ## Coerce args to Exprs
def __call__(self, *args):
"""Self must be a symbol with no args, such as Expr('F'). Create a new
Expr with 'F' as op and the args as arguments."""
assert is_symbol(self.op) and not self.args
return Expr(self.op, *args)
def __repr__(self):
"Show something like 'P' or 'P(x, y)', or '~P' or '(P | Q | R)'"
if len(self.args) == 0: # Constant or proposition with arity 0
return str(self.op)
elif is_symbol(self.op): # Functional or Propositional operator
return '%s(%s)' % (self.op, ', '.join(map(repr, self.args)))
elif len(self.args) == 1: # Prefix operator
return self.op + repr(self.args[0])
else: # Infix operator
return '(%s)' % (' '+self.op+' ').join(map(repr, self.args))
def __eq__(self, other):
"""x and y are equal iff their ops and args are equal."""
return (other is self) or (isinstance(other, Expr)
and self.op == other.op and self.args == other.args)
def __hash__(self):
"Need a hash method so Exprs can live in dicts."
return hash(self.op) ^ hash(tuple(self.args))
# See http://www.python.org/doc/current/lib/module-operator.html
# Not implemented: not, abs, pos, concat, contains, *item, *slice
def __lt__(self, other): return Expr('<', self, other)
def __le__(self, other): return Expr('<=', self, other)
def __ge__(self, other): return Expr('>=', self, other)
def __gt__(self, other): return Expr('>', self, other)
def __add__(self, other): return Expr('+', self, other)
def __sub__(self, other): return Expr('-', self, other)
def __and__(self, other): return Expr('&', self, other)
def __div__(self, other): return Expr('/', self, other)
def __truediv__(self, other):return Expr('/', self, other)
def __invert__(self): return Expr('~', self)
def __lshift__(self, other): return Expr('<<', self, other)
def __rshift__(self, other): return Expr('>>', self, other)
def __mul__(self, other): return Expr('*', self, other)
def __neg__(self): return Expr('-', self)
def __or__(self, other): return Expr('|', self, other)
def __pow__(self, other): return Expr('**', self, other)
def __xor__(self, other): return Expr('^', self, other)
def __mod__(self, other): return Expr('<=>', self, other) ## (x % y)
def expr(s):
"""Create an Expr representing a logic expression by parsing the input
string. Symbols and numbers are automatically converted to Exprs.
In addition you can use alternative spellings of these operators:
'x ==> y' parses as (x >> y) # Implication
'x <== y' parses as (x << y) # Reverse implication
'x <=> y' parses as (x % y) # Logical equivalence
'x =/= y' parses as (x ^ y) # Logical disequality (xor)
But BE CAREFUL; precedence of implication is wrong. expr('P & Q ==> R & S')
is ((P & (Q >> R)) & S); so you must use expr('(P & Q) ==> (R & S)').
>>> expr('P <=> Q(1)')
(P <=> Q(1))
>>> expr('P & Q | ~R(x, F(x))')
((P & Q) | ~R(x, F(x)))
"""
if isinstance(s, Expr): return s
if isnumber(s): return Expr(s)
## Replace the alternative spellings of operators with canonical spellings
s = s.replace('==>', '>>').replace('<==', '<<')
s = s.replace('<=>', '%').replace('=/=', '^')
## Replace a symbol or number, such as 'P' with 'Expr("P")'
s = re.sub(r'([a-zA-Z0-9_.]+)', r'Expr("\1")', s)
## Now eval the string. (A security hole; do not use with an adversary.)
return eval(s, {'Expr':Expr})
def is_symbol(s):
"A string s is a symbol if it starts with an alphabetic char."
return isinstance(s, str) and s[0].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 other than
TRUE or FALSE."""
return is_symbol(s) and s[0].isupper() and s != 'TRUE' and s != 'FALSE'
def is_positive(s):
"""s is an unnegated logical expression
>>> is_positive(expr('F(A, B)'))
True
>>> is_positive(expr('~F(A, B)'))
False
"""
return s.op != '~'
def is_negative(s):
"""s is a negated logical expression
>>> is_negative(expr('F(A, B)'))
False
>>> is_negative(expr('~F(A, B)'))
True
"""
return s.op == '~'
def is_literal(s):
"""s is a FOL literal
>>> is_literal(expr('~F(A, B)'))
True
>>> is_literal(expr('F(A, B)'))
True
>>> is_literal(expr('F(A, B) & G(B, C)'))
False
"""
return is_symbol(s.op) or (s.op == '~' and is_literal(s.args[0]))
def literals(s):
"""returns the list of literals of logical expression s.
>>> literals(expr('F(A, B)'))
[F(A, B)]
>>> literals(expr('~F(A, B)'))
[~F(A, B)]
>>> literals(expr('(F(A, B) & G(B, C)) ==> R(A, C)'))
[F(A, B), G(B, C), R(A, C)]
"""
op = s.op
if op in set(['&', '|', '<<', '>>', '%', '^']):
result = []
for arg in s.args:
result.extend(literals(arg))
return result
elif is_literal(s):
return [s]
else:
return []
def variables(s):
"""returns the set of variables in logical expression s.
>>> ppset(variables(F(x, A, y)))
set([x, y])
>>> ppset(variables(expr('F(x, x) & G(x, y) & H(y, z) & R(A, z, z)')))
set([x, y, z])
"""
if is_literal(s):
return set([v for v in s.args if is_variable(v)])
else:
vars = set([])
for lit in literals(s):
vars = vars.union(variables(lit))
return vars
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
>>> is_definite_clause(expr('~Farmer(Mac)'))
False
>>> is_definite_clause(expr('(Farmer(f) & Rabbit(r)) ==> Hates(f, r)'))
True
>>> is_definite_clause(expr('(Farmer(f) & ~Rabbit(r)) ==> Hates(f, r)'))
False
"""
op = s.op
return (is_symbol(op) or
(op == '>>' and every(is_positive, literals(s))))
## Useful constant Exprs used in examples and code:
TRUE, FALSE, ZERO, ONE, TWO = map(Expr, ['TRUE', 'FALSE', 0, 1, 2])
A, B, C, F, G, P, Q, x, y, z = map(Expr, 'ABCFGPQxyz')
def tt_entails(kb, alpha):
"""Use truth tables to determine if KB entails sentence alpha. [Fig. 7.10]
>>> tt_entails(expr('P & Q'), expr('Q'))
True
"""
return tt_check_all(kb, alpha, prop_symbols(kb & alpha), {})
def tt_check_all(kb, alpha, symbols, model):
"Auxiliary routine to implement tt_entails."
if not symbols:
if pl_true(kb, model): return pl_true(alpha, model)
else: return True
assert result != None
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 a list of all propositional symbols in x."
if not isinstance(x, Expr):
return []
elif is_prop_symbol(x.op):
return [x]
else:
s = set(())
for arg in x.args:
for symbol in prop_symbols(arg):
s.add(symbol)
return list(s)
def tt_true(alpha):
"""Is the sentence alpha a tautology? (alpha will be coerced to an expr.)
>>> tt_true(expr("(P >> Q) <=> (~P | Q)"))
True
"""
return tt_entails(TRUE, expr(alpha))
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."""
op, args = exp.op, exp.args
if exp == TRUE:
return True
elif exp == FALSE:
return False
elif is_prop_symbol(op):
return model.get(exp)
elif op == '~':
p = pl_true(args[0], model)
if p == None: return None
else: return not p
elif op == '|':
result = False
for arg in args:
p = pl_true(arg, model)
if p == True: return True
if p == None: result = None
return result
elif op == '&':
result = True
for arg in args:
p = pl_true(arg, model)
if p == False: return False
if p == 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 == None: return None
qt = pl_true(q, model)
if qt == None: return None
if op == '<=>':
return pt == qt
elif op == '^':
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 s to conjunctive normal form.
That is, of the form ((A | ~B | ...) & (B | C | ...) & ...) [p. 215]
>>> to_cnf("~(B|C)")
(~B & ~C)
>>> to_cnf("B <=> (P1|P2)")
((~P1 | B) & (~P2 | B) & (P1 | P2 | ~B))
>>> to_cnf("a | (b & c) | d")
((b | a | d) & (c | a | d))
>>> to_cnf("A & (B | (D & E))")
(A & (D | B) & (E | B))
"""
if isinstance(s, str): s = expr(s)
s = eliminate_implications(s) # Steps 1, 2 from p. 215
s = move_not_inwards(s) # Step 3
return distribute_and_over_or(s) # Step 4
def eliminate_implications(s):
"""Change >>, <<, and <=> into &, |, and ~. That is, return an Expr
that is equivalent to s, but has only &, |, and ~ as logical operators.
>>> eliminate_implications(A >> (~B << C))
((~B | ~C) | ~A)
"""
if not s.args or is_symbol(s.op): return s ## (Atoms are unchanged.)
args = 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)
else:
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)
>>> move_not_inwards(~(A & B))
(~A | ~B)
>>> move_not_inwards(~(~(A | ~B) | ~~C))
((A | ~B) & ~C)
"""
if s.op == '~':
NOT = lambda b: move_not_inwards(~b)
a = s.args[0]
if a.op == '~': return move_not_inwards(a.args[0]) # ~~A ==> A
if a.op =='&': return NaryExpr('|', *map(NOT, a.args))
if a.op =='|': return NaryExpr('&', *map(NOT, a.args))
return s
elif is_symbol(s.op) or not s.args:
return s
else:
return Expr(s.op, *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))
"""
if s.op == '|':
s = NaryExpr('|', *s.args)
if len(s.args) == 0:
return FALSE
if len(s.args) == 1:
return distribute_and_over_or(s.args[0])
conj = find_if((lambda d: d.op == '&'), s.args)
if not conj:
return NaryExpr(s.op, *s.args)
others = [a for a in s.args if a is not conj]
if len(others) == 1:
rest = others[0]
else:
rest = NaryExpr('|', *others)
return NaryExpr('&', *map(distribute_and_over_or,
[(c|rest) for c in conj.args]))
elif s.op == '&':
return NaryExpr('&', *map(distribute_and_over_or, s.args))
else:
return s
_NaryExprTable = {'&':TRUE, '|':FALSE, '+':ZERO, '*':ONE}
def NaryExpr(op, *args):
"""Create an Expr, but with an nary, associative op, so we can promote
nested instances of the same op up to the top level.
>>> NaryExpr('&', (A&B),(B|C),(B&C))
(A & B & (B | C) & B & C)
"""
arglist = []
for arg in args:
if arg.op == op: arglist.extend(arg.args)
else: arglist.append(arg)
if len(args) == 1:
return args[0]
elif len(args) == 0:
return _NaryExprTable[op]
else:
return Expr(op, *arglist)
def conjuncts(s):
"""Return a list of the conjuncts in the sentence s.
>>> conjuncts(A & B)
[A, B]
>>> conjuncts(A | B)
[(A | B)]
"""
if isinstance(s, Expr) and s.op == '&':
return s.args
else:
return [s]
def disjuncts(s):
"""Return a list of the disjuncts in the sentence s.
>>> disjuncts(A | B)
[A, B]
>>> disjuncts(A & B)
[(A & B)]
"""
if isinstance(s, Expr) and s.op == '|':
return s.args
else:
return [s]
def pl_resolution(KB, alpha):
"Propositional Logic Resolution: say if alpha follows from KB. [Fig. 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.
>>> for res in pl_resolve(to_cnf(A|B|C), to_cnf(~B|~C|F)):
... ppset(disjuncts(res))
set([A, C, F, ~C])
set([A, B, F, ~B])
"""
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(NaryExpr('|', *dnew))
return clauses
class PropHornKB(PropKB):
"A KB of Propositional Horn clauses."
def tell(self, sentence):
"Add a Horn Clauses to this KB."
op = sentence.op
assert op == '>>' or is_prop_symbol(op), "Must be Horn Clause"
self.clauses.append(sentence)
def ask_generator(self, query):
"Yield the empty substitution if KB implies query; else False"
if not pl_fc_entails(self.clauses, query):
return
yield {}
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 clauses_with_premise(self, p):
"""The list of clauses in KB that have p in the 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 HornKB entails symbol q. [Fig. 7.14]
>>> pl_fc_entails(Fig[7,15], expr('Q'))
True
"""
count = dict([(c, len(conjuncts(c.args[0]))) for c in KB.clauses
if c.op == '>>'])
inferred = DefaultDict(False)
agenda = [s for s in KB.clauses if is_prop_symbol(s.op)]
if q in agenda: return True
while agenda:
p = agenda.pop()
if not inferred[p]:
inferred[p] = True
for c in KB.clauses_with_premise(p):
count[c] -= 1
if count[c] == 0:
if c.args[1] == q: return True
agenda.append(c.args[1])
return False
## Wumpus World example [Fig. 7.13]
Fig[7,13] = expr("(B11 <=> (P12 | P21)) & ~B11")
## Propositional Logic Forward Chaining example [Fig. 7.15]
Fig[7,15] = PropHornKB()
for s in "P>>Q (L&M)>>P (B&L)>>M (A&P)>>L (A&B)>>L A B".split():
Fig[7,15].tell(expr(s))
# DPLL-Satisfiable [Fig. 7.16]
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.
>>> ppsubst(dpll_satisfiable(A&~B))
{A: True, B: False}
>>> dpll_satisfiable(P&~P)
False
"""
clauses = conjuncts(to_cnf(s))
symbols = 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 == False:
return False
if val != 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))
P = symbols.pop()
return (dpll(clauses, symbols, extend(model, P, True)) or
dpll(clauses, symbols, extend(model, P, False)))
def find_pure_symbol(symbols, unknown_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 unknown_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):
"""A unit clause has only 1 variable that is not bound in the model.
>>> find_unit_clause([A|B|C, B|~C, A|~B], {A:True})
(B, False)
"""
for clause in clauses:
num_not_in_model = 0
for literal in disjuncts(clause):
sym = literal_symbol(literal)
if sym not in model:
num_not_in_model += 1
P, value = sym, (literal.op != '~')
if num_not_in_model == 1:
return P, value
return None, None
def literal_symbol(literal):
"""The symbol in this literal (without the negation).
>>> literal_symbol(P)
P
>>> literal_symbol(~P)
P
"""
if literal.op == '~':
return literal.args[0]
else:
return literal
# Walk-SAT [Fig. 7.17]
def WalkSAT(clauses, p=0.5, max_flips=10000):
## model is a random assignment of true/false to the symbols in clauses
## See ~/aima1e/print1/manual/knowledge+logic-answers.tex ???
model = dict([(s, random.choice([True, False]))
for s in prop_symbols(clauses)])
for i in range(max_flips):
satisfied, unsatisfied = [], []
for clause in clauses:
if_(pl_true(clause, model), satisfied, unsatisfied).append(clause)
if not unsatisfied: ## if model satisfies all the clauses
return model
clause = random.choice(unsatisfied)
if probability(p):
sym = random.choice(prop_symbols(clause))
else:
## Flip the symbol in clause that miximizes number of sat. clauses
raise NotImplementedError
model[sym] = not model[sym]
# PL-Wumpus-Agent [Fig. 7.19]
class PLWumpusAgent(agents.Agent):
"An agent for the wumpus world that does logical inference. [Fig. 7.19]"""
def __init__(self):
KB = FOLKB() ## shouldn't this be a propositional KB? ***
x, y, orientation = 1, 1, (1, 0)
visited = set() ## squares already visited
action = None
plan = []
def program(percept):
stench, breeze, glitter = percept
x, y, orientation = update_position(x, y, orientation, action)
KB.tell('%sS_%d,%d' % (if_(stench, '', '~'), x, y))
KB.tell('%sB_%d,%d' % (if_(breeze, '', '~'), x, y))
if glitter: action = 'Grab'
elif plan: action = plan.pop()
else:
for [i, j] in fringe(visited):
if KB.ask('~P_%d,%d & ~W_%d,%d' % (i, j, i, j)) != False:
raise NotImplementedError
KB.ask('~P_%d,%d | ~W_%d,%d' % (i, j, i, j)) != False
if action == None:
action = random.choice(['Forward', 'Right', 'Left'])
return action
self.program = program
def update_position(x, y, orientation, action):
if action == 'TurnRight':
orientation = turn_right(orientation)
elif action == 'TurnLeft':
orientation = turn_left(orientation)
elif action == 'Forward':
x, y = x + vector_add((x, y), orientation)
return x, y, orientation
def unify(x, y, s):
"""Unify expressions x,y with substitution s; return a substitution that
would make x,y equal, or None if x,y can not unify. x and y can be
variables (e.g. Expr('x')), constants, lists, or Exprs. [Fig. 9.1]
>>> ppsubst(unify(x + y, y + C, {}))
{x: y, y: C}
"""
if s == None:
return None
elif x == y:
return s
elif is_variable(x):
return unify_var(x, y, s)
elif is_variable(y):
return unify_var(y, x, s)
elif isinstance(x, Expr) and isinstance(y, Expr):
return unify(x.args, y.args, unify(x.op, y.op, s))
elif isinstance(x, str) or isinstance(y, str) or not x or not y:
# orig. return if_(x == y, s, None) but we already know x != y
return None
elif issequence(x) and issequence(y) and len(x) == len(y):
# Assert neither x nor y is []
return unify(x[1:], y[1:], unify(x[0], y[0], s))
else:
return None
def is_variable(x):
"A variable is an Expr with no args and a lowercase symbol as the op."
return isinstance(x, Expr) and not x.args and is_var_symbol(x.op)
def unify_var(var, x, s):
if var in s:
return unify(s[var], x, s)
elif occur_check(var, x, s):
return None
else:
return extend(s, var, x)
def occur_check(var, x, s):
"""Return true if variable var occurs anywhere in x
(or in subst(s, x), if s has a binding for x)."""
if var == x:
return True
elif is_variable(x) and s.has_key(x):
return occur_check(var, s[x], s) # fixed
# What else might x be? an Expr, a list, a string?
elif isinstance(x, Expr):
# Compare operator and arguments
return (occur_check(var, x.op, s) or
occur_check(var, x.args, s))
elif isinstance(x, list) and x != []:
# Compare first and rest
return (occur_check(var, x[0], s) or
occur_check(var, x[1:], s))
else:
# A variable cannot occur in a string
return False
#elif isinstance(x, Expr):
# return var.op == x.op or occur_check(var, x.args)
#elif not isinstance(x, str) and issequence(x):
# for xi in x:
# if occur_check(var, xi): return True
#return False
def extend(s, var, val):
"""Copy the substitution s and extend it by setting var to val;
return copy.
>>> ppsubst(extend({x: 1}, y, 2))
{x: 1, y: 2}
"""
s2 = s.copy()
s2[var] = val
return s2
def subst(s, x):
"""Substitute the substitution s into the expression x.
>>> subst({x: 42, y:0}, F(x) + y)
(F(42) + 0)
"""
if isinstance(x, list):
return [subst(s, xi) for xi in x]
elif isinstance(x, tuple):
return tuple([subst(s, xi) for xi in x])
elif not isinstance(x, Expr):
return x
elif is_var_symbol(x.op):
return s.get(x, x)
else:
return Expr(x.op, *[subst(s, arg) for arg in x.args])
def fol_fc_ask(KB, alpha):
"""Inefficient forward chaining for first-order logic. [Fig. 9.3]
KB is an FOLHornKB and alpha must be an atomic sentence."""
while True:
new = {}
for r in KB.clauses:
r1 = standardize_apart(r)
ps, q = conjuncts(r.args[0]), r.args[1]
raise NotImplementedError
def standardize_apart(sentence, dic={}):
"""Replace all the variables in sentence with new variables.
>>> e = expr('F(a, b, c) & G(c, A, 23)')
>>> len(variables(standardize_apart(e)))
3
>>> variables(e).intersection(variables(standardize_apart(e)))
set([])
>>> is_variable(standardize_apart(expr('x')))
True
"""
if not isinstance(sentence, Expr):
return sentence
elif is_var_symbol(sentence.op):
if sentence in dic:
return dic[sentence]
else:
standardize_apart.counter += 1
v = Expr('v_%d' % standardize_apart.counter)
dic[sentence] = v
return v
else:
return Expr(sentence.op,
*[standardize_apart(a, dic) for a in sentence.args])
standardize_apart.counter = 0
class FolKB (KB):
"""A knowledge base consisting of first-order definite clauses
>>> kb0 = FolKB([expr('Farmer(Mac)'), expr('Rabbit(Pete)'),
... expr('(Rabbit(r) & Farmer(f)) ==> Hates(f, r)')])
>>> kb0.tell(expr('Rabbit(Flopsie)'))
>>> kb0.retract(expr('Rabbit(Pete)'))
>>> kb0.ask(expr('Hates(Mac, x)'))[x]
Flopsie
>>> kb0.ask(expr('Wife(Pete, x)'))
False
"""
def __init__ (self, initial_clauses=[]):
self.clauses = [] # inefficient: no indexing
for clause in initial_clauses:
self.tell(clause)
def tell(self, sentence):
if is_definite_clause(sentence):
self.clauses.append(sentence)
else:
raise Exception("Not a definite clause: %s" % sentence)
def ask_generator(self, query):
return fol_bc_ask(self, [query])
def retract(self, sentence):
self.clauses.remove(sentence)
def test_ask(q):
e = expr(q)
vars = variables(e)
ans = fol_bc_ask(test_kb, [e])
res = []
for a in ans:
res.append(pretty(dict([(x, v) for (x, v) in a.items() if x in vars])))
res.sort(key=str)
return res
test_kb = FolKB(
map(expr, ['Farmer(Mac)',
'Rabbit(Pete)',
'Mother(MrsMac, Mac)',
'Mother(MrsRabbit, Pete)',
'(Rabbit(r) & Farmer(f)) ==> Hates(f, r)',
'(Mother(m, c)) ==> Loves(m, c)',
'(Mother(m, r) & Rabbit(r)) ==> Rabbit(m)',
'(Farmer(f)) ==> Human(f)',
# Note that this order of conjuncts
# would result in infinite recursion:
#'(Human(h) & Mother(m, h)) ==> Human(m)'
'(Mother(m, h) & Human(h)) ==> Human(m)'
])
)
def fol_bc_ask(KB, goals, theta={}):
"""A simple backward-chaining algorithm for first-order logic. [Fig. 9.6]
KB should be an instance of FolKB, and goals a list of literals.
>>> test_ask('Farmer(x)')
['{x: Mac}']
>>> test_ask('Human(x)')
['{x: Mac}', '{x: MrsMac}']
>>> test_ask('Hates(x, y)')
['{x: Mac, y: Pete}']
>>> test_ask('Loves(x, y)')
['{x: MrsMac, y: Mac}', '{x: MrsRabbit, y: Pete}']
>>> test_ask('Rabbit(x)')
['{x: MrsRabbit}', '{x: Pete}']
"""
if goals == []:
yield theta
raise StopIteration()
q1 = subst(theta, goals[0])
for r in KB.clauses:
sar = standardize_apart(r)
# Split into head and body
if is_symbol(sar.op):
head = sar
body = []
elif sar.op == '>>': # sar = (Body1 & Body2 & ...) >> Head
head = sar.args[1]
body = sar.args[0] # as conjunction
else:
raise Exception("Invalid clause in FolKB: %s" % r)
theta1 = unify(head, q1, {})
if theta1 is not None:
if body == []:
new_goals = goals[1:]
else:
new_goals = conjuncts(body) + goals[1:]
for ans in fol_bc_ask(KB, new_goals, subst_compose(theta1, theta)):
yield ans
raise StopIteration()
def subst_compose (s1, s2):
"""Return the substitution which is equivalent to applying s2 to
the result of applying s1 to an expression.
>>> s1 = {x: A, y: B}
>>> s2 = {z: x, x: C}
>>> p = F(x) & G(y) & expr('H(z)')
>>> subst(s1, p)
((F(A) & G(B)) & H(z))
>>> subst(s2, p)
((F(C) & G(y)) & H(x))
>>> subst(s2, subst(s1, p))
((F(A) & G(B)) & H(x))
>>> subst(subst_compose(s1, s2), p)
((F(A) & G(B)) & H(x))
>>> subst(s1, subst(s2, p))
((F(C) & G(B)) & H(A))
>>> subst(subst_compose(s2, s1), p)
((F(C) & G(B)) & H(A))
>>> ppsubst(subst_compose(s1, s2))
{x: A, y: B, z: x}
>>> ppsubst(subst_compose(s2, s1))
{x: C, y: B, z: A}
>>> subst(subst_compose(s1, s2), p) == subst(s2, subst(s1, p))
True
>>> subst(subst_compose(s2, s1), p) == subst(s1, subst(s2, p))
True
"""
sc = {}
for x, v in s1.items():
if s2.has_key(v):
w = s2[v]
sc[x] = w # x -> v -> w
else:
sc[x] = v
for x, v in s2.items():
if not (s1.has_key(x)):
sc[x] = v
# otherwise s1[x] preemptys s2[x]
return sc
# Example application (not in the book).
# You can use the Expr class to do symbolic differentiation. This used to be
# a part of AI; now it is considered a separate field, Symbolic Algebra.
def diff(y, x):
"""Return the symbolic derivative, dy/dx, as an Expr.
However, you probably want to simplify the results with simp.
>>> diff(x * x, x)
((x * 1) + (x * 1))
>>> simp(diff(x * x, x))
(2 * x)
"""
if y == x: return ONE
elif not y.args: return ZERO
else:
u, op, v = y.args[0], y.op, y.args[-1]
if op == '+': return diff(u, x) + diff(v, x)
elif op == '-' and len(args) == 1: return -diff(u, x)
elif op == '-': return diff(u, x) - diff(v, x)
elif op == '*': return u * diff(v, x) + v * diff(u, x)
elif op == '/': return (v*diff(u, x) - u*diff(v, x)) / (v * v)
elif op == '**' and isnumber(x.op):
return (v * u ** (v - 1) * diff(u, x))
elif op == '**': return (v * u ** (v - 1) * diff(u, x)
+ u ** v * Expr('log')(u) * diff(v, x))
elif op == 'log': return diff(u, x) / u
else: raise ValueError("Unknown op: %s in diff(%s, %s)" % (op, y, x))
def simp(x):
if not x.args: return x
args = map(simp, x.args)
u, op, v = args[0], x.op, args[-1]
if op == '+':
if v == ZERO: return u
if u == ZERO: return v
if u == v: return TWO * u
if u == -v or v == -u: return ZERO
elif op == '-' and len(args) == 1:
if u.op == '-' and len(u.args) == 1: return u.args[0] ## --y ==> y
elif op == '-':
if v == ZERO: return u
if u == ZERO: return -v
if u == v: return ZERO
if u == -v or v == -u: return ZERO
elif op == '*':
if u == ZERO or v == ZERO: return ZERO
if u == ONE: return v
if v == ONE: return u
if u == v: return u ** 2
elif op == '/':
if u == ZERO: return ZERO
if v == ZERO: return Expr('Undefined')
if u == v: return ONE
if u == -v or v == -u: return ZERO
elif op == '**':
if u == ZERO: return ZERO
if v == ZERO: return ONE
if u == ONE: return ONE
if v == ONE: return u
elif op == 'log':
if u == ONE: return ZERO
else: raise ValueError("Unknown op: " + op)
## If we fall through to here, we can not simplify further
return Expr(op, *args)
def d(y, x):
"Differentiate and then simplify."
return simp(diff(y, x))
# Utilities for doctest cases
# These functions print their arguments in a standard order
# to compensate for the random order in the standard representation
def pretty(x):
t = type(x)
if t == dict:
return pretty_dict(x)
elif t == set:
return pretty_set(x)
def pretty_dict(d):
"""Print the dictionary d.
Prints a string representation of the dictionary
with keys in sorted order according to their string
representation: {a: A, d: D, ...}.
>>> pretty_dict({'m': 'M', 'a': 'A', 'r': 'R', 'k': 'K'})
"{'a': 'A', 'k': 'K', 'm': 'M', 'r': 'R'}"
>>> pretty_dict({z: C, y: B, x: A})
'{x: A, y: B, z: C}'
"""
def format(k, v):
return "%s: %s" % (repr(k), repr(v))
ditems = d.items()
ditems.sort(key=str)
k, v = ditems[0]
dpairs = format(k, v)
for (k, v) in ditems[1:]:
dpairs += (', ' + format(k, v))
return '{%s}' % dpairs
def pretty_set(s):
"""Print the set s.
>>> pretty_set(set(['A', 'Q', 'F', 'K', 'Y', 'B']))
"set(['A', 'B', 'F', 'K', 'Q', 'Y'])"
>>> pretty_set(set([z, y, x]))
'set([x, y, z])'
"""
slist = list(s)
slist.sort(key=str)
return 'set(%s)' % slist
def pp(x):
print pretty(x)
def ppsubst(s):
"""Pretty-print substitution s"""
ppdict(s)
def ppdict(d):
print pretty_dict(d)
def ppset(s):
print pretty_set(s)
class logicTest: """
### PropKB
>>> kb = PropKB()
>>> kb.tell(A & B)
>>> kb.tell(B >> C)
>>> kb.ask(C) ## The result {} means true, with no substitutions
{}
>>> kb.ask(P)
False
>>> kb.retract(B)
>>> kb.ask(C)
False
>>> pl_true(P, {})
>>> pl_true(P | Q, {P: True})
True
# Notice that the function pl_true cannot reason by cases:
>>> pl_true(P | ~P)
# However, tt_true can:
>>> tt_true(P | ~P)
True
# The following are tautologies from [Fig. 7.11]:
>>> tt_true("(A & B) <=> (B & A)")
True
>>> tt_true("(A | B) <=> (B | A)")
True
>>> tt_true("((A & B) & C) <=> (A & (B & C))")
True
>>> tt_true("((A | B) | C) <=> (A | (B | C))")
True
>>> tt_true("~~A <=> A")
True
>>> tt_true("(A >> B) <=> (~B >> ~A)")
True
>>> tt_true("(A >> B) <=> (~A | B)")
True
>>> tt_true("(A <=> B) <=> ((A >> B) & (B >> A))")
True
>>> tt_true("~(A & B) <=> (~A | ~B)")
True
>>> tt_true("~(A | B) <=> (~A & ~B)")
True
>>> tt_true("(A & (B | C)) <=> ((A & B) | (A & C))")
True
>>> tt_true("(A | (B & C)) <=> ((A | B) & (A | C))")
True
# The following are not tautologies:
>>> tt_true(A & ~A)
False
>>> tt_true(A & B)
False
### [Fig. 7.13]
>>> alpha = expr("~P12")
>>> to_cnf(Fig[7,13] & ~alpha)
((~P12 | B11) & (~P21 | B11) & (P12 | P21 | ~B11) & ~B11 & P12)
>>> tt_entails(Fig[7,13], alpha)
True
>>> pl_resolution(PropKB(Fig[7,13]), alpha)
True
### [Fig. 7.15]
>>> pl_fc_entails(Fig[7,15], expr('SomethingSilly'))
False
### Unification:
>>> unify(x, x, {})
{}
>>> unify(x, 3, {})
{x: 3}
>>> to_cnf((P&Q) | (~P & ~Q))
((~P | P) & (~Q | P) & (~P | Q) & (~Q | Q))
"""
Implementing Agents and Environments as follows:
"""The class hierarchies are as follows:
Object ## A physical object that can exist in an environment
Agent
Wumpus
RandomAgent
ReflexVacuumAgent
...
Dirt
Wall
...
Environment ## An environment holds objects, runs simulations
XYEnvironment
VacuumEnvironment
WumpusEnvironment
EnvGUI ## A window with a graphical representation of the Environment
EnvToolbar ## contains buttons for controlling EnvGUI
EnvCanvas ## Canvas to display the environment of an EnvGUI
"""
# TO DO:
# Implement grabbing correctly.
# When an object is grabbed, does it still have a location?
# What if it is released?
# What if the grabbed or the grabber is deleted?
# What if the grabber moves?
#
# Speed control in GUI does not have any effect -- fix it.
from utils import *
import random, copy
#______________________________________________________________________________
class Object (object):
"""This represents any physical object that can appear in an Environment.
You subclass Object to get the objects you want. Each object can have a
.__name__ slot (used for output only)."""
def __repr__(self):
return '<%s>' % getattr(self, '__name__', self.__class__.__name__)
def is_alive(self):
"""Objects that are 'alive' should return true."""
return hasattr(self, 'alive') and self.alive
def show_state (self):
"""Display the agent's internal state. Subclasses should override."""
print "I don't know how to show_state."
def display(self, canvas, x, y, width, height):
# Do we need this?
"""Display an image of this Object on the canvas."""
pass
class Agent (Object):
"""An Agent is a subclass of Object with one required slot,
.program, which should hold a function that takes one argument, the
percept, and returns an action. (What counts as a percept or action
will depend on the specific environment in which the agent exists.)
Note that 'program' is a slot, not a method. If it were a method,
then the program could 'cheat' and look at aspects of the agent.
It's not supposed to do that: the program can only look at the
percepts. An agent program that needs a model of the world (and of
the agent itself) will have to build and maintain its own model.
There is an optional slots, .performance, which is a number giving
the performance measure of the agent in its environment."""
def __init__(self):
self.program = self.make_agent_program()
self.alive = True
self.bump = False
def make_agent_program (self):
def program(percept):
return raw_input('Percept=%s; action? ' % percept)
return program
def can_grab (self, obj):
"""Returns True if this agent can grab this object.
Override for appropriate subclasses of Agent and Object."""
return False
def TraceAgent(agent):
"""Wrap the agent's program to print its input and output. This will let
you see what the agent is doing in the environment."""
old_program = agent.program
def new_program(percept):
action = old_program(percept)
print '%s perceives %s and does %s' % (agent, percept, action)
return action
agent.program = new_program
return agent
#______________________________________________________________________________
class TableDrivenAgent (Agent):
"""This agent selects an action based on the percept sequence.
It is practical only for tiny domains.
To customize it you provide a table to the constructor. [Fig. 2.7]"""
def __init__(self, table):
"Supply as table a dictionary of all {percept_sequence:action} pairs."
## The agent program could in principle be a function, but because
## it needs to store state, we make it a callable instance of a class.
self.table = table
super(TableDrivenAgent, self).__init__()
def make_agent_program (self):
table = self.table
percepts = []
def program(percept):
percepts.append(percept)
action = table.get(tuple(percepts))
return action
return program
class RandomAgent (Agent):
"An agent that chooses an action at random, ignoring all percepts."
def __init__(self, actions):
self.actions = actions
super(RandomAgent, self).__init__()
def make_agent_program (self):
actions = self.actions
return lambda percept: random.choice(actions)
#______________________________________________________________________________
loc_A, loc_B = (0, 0), (1, 0) # The two locations for the Vacuum world
class ReflexVacuumAgent (Agent):
"A reflex agent for the two-state vacuum environment. [Fig. 2.8]"
def __init__(self):
super(ReflexVacuumAgent, self).__init__()
def make_agent_program (self):
def program((location, status)):
if status == 'Dirty': return 'Suck'
elif location == loc_A: return 'Right'
elif location == loc_B: return 'Left'
return program
def RandomVacuumAgent():
"Randomly choose one of the actions from the vaccum environment."
return RandomAgent(['Right', 'Left', 'Suck', 'NoOp'])
def TableDrivenVacuumAgent():
"[Fig. 2.3]"
table = {((loc_A, 'Clean'),): 'Right',
((loc_A, 'Dirty'),): 'Suck',
((loc_B, 'Clean'),): 'Left',
((loc_B, 'Dirty'),): 'Suck',
((loc_A, 'Clean'), (loc_A, 'Clean')): 'Right',
((loc_A, 'Clean'), (loc_A, 'Dirty')): 'Suck',
# ...
((loc_A, 'Clean'), (loc_A, 'Clean'), (loc_A, 'Clean')): 'Right',
((loc_A, 'Clean'), (loc_A, 'Clean'), (loc_A, 'Dirty')): 'Suck',
# ...
}
return TableDrivenAgent(table)
class ModelBasedVacuumAgent (Agent):
"An agent that keeps track of what locations are clean or dirty."
def __init__(self):
self.model = {loc_A: None, loc_B: None}
super(ModelBasedVacuumAgent, self).__init__()
def make_agent_program (self):
model = self.model
def program((location, status)):
"Same as ReflexVacuumAgent, except if everything is clean, do NoOp"
model[location] = status ## Update the model here
if model[loc_A] == model[loc_B] == 'Clean': return 'NoOp'
elif status == 'Dirty': return 'Suck'
elif location == loc_A: return 'Right'
elif location == loc_B: return 'Left'
return program
#______________________________________________________________________________
class Environment (object):
"""Abstract class representing an Environment. 'Real' Environment classes
inherit from this. Your Environment will typically need to implement:
percept: Define the percept that an agent sees.
execute_action: Define the effects of executing an action.
Also update the agent.performance slot.
The environment keeps a list of .objects and .agents (which is a subset
of .objects). Each agent has a .performance slot, initialized to 0.
Each object has a .location slot, even though some environments may not
need this."""
def __init__(self):
self.objects = []
self.agents = []
def object_classes (self):
return [] ## List of classes that can go into environment
def percept(self, agent):
"Return the percept that the agent sees at this point. Override this."
abstract
def execute_action(self, agent, action):
"Change the world to reflect this action. Override this."
abstract
def default_location(self, object):
"Default location to place a new object with unspecified location."
return None
def exogenous_change(self):
"If there is spontaneous change in the world, override this."
pass
def is_done(self):
"By default, we're done when we can't find a live agent."
for agent in self.agents:
if agent.is_alive(): return False
return True
def step(self):
"""Run the environment for one time step. If the
actions and exogenous changes are independent, this method will
do. If there are interactions between them, you'll need to
override this method."""
if not self.is_done():
actions = [agent.program(self.percept(agent))
for agent in self.agents]
for (agent, action) in zip(self.agents, actions):
self.execute_action(agent, action)
self.exogenous_change()
def run(self, steps=1000):
"""Run the Environment for given number of time steps."""
for step in range(steps):
if self.is_done(): return
self.step()
def list_objects_at (self, location, oclass=Object):
"Return all objects exactly at a given location."
return [obj for obj in self.objects
if obj.location == location and isinstance(obj, oclass)]
def some_objects_at (self, location, oclass=Object):
"""Return true if at least one of the objects at location
is an instance of class oclass.
'Is an instance' in the sense of 'isinstance',
which is true if the object is an instance of a subclass of oclass."""
return self.list_objects_at(location, oclass) != []
def add_object(self, obj, location=None):
"""Add an object to the environment, setting its location. Also keep
track of objects that are agents. Shouldn't need to override this."""
obj.location = location or self.default_location(obj)
self.objects.append(obj)
if isinstance(obj, Agent):
obj.performance = 0
self.agents.append(obj)
return self
def delete_object (self, obj):
"""Remove an object from the environment."""
try:
self.objects.remove(obj)
except ValueError, e:
print e
print " in Environment delete_object"
print " Object to be removed: %s at %s" % (obj, obj.location)
trace_list(" from list", self.objects)
if obj in self.agents:
self.agents.remove(obj)
def trace_list (name, objlist):
ol_list = [(obj, obj.location) for obj in objlist]
print "%s: %s" % (name, ol_list)
class XYEnvironment (Environment):
"""This class is for environments on a 2D plane, with locations
labelled by (x, y) points, either discrete or continuous.
Agents perceive objects within a radius. Each agent in the
environment has a .location slot which should be a location such
as (0, 1), and a .holding slot, which should be a list of objects
that are held."""
def __init__(self, width=10, height=10):
super(XYEnvironment, self).__init__()
self.width = width
self.height = height
#update(self, objects=[], agents=[], width=width, height=height)
self.observers = []
def objects_near(self, location, radius):
"Return all objects within radius of location."
radius2 = radius * radius
return [obj for obj in self.objects
if distance2(location, obj.location) <= radius2]
def percept(self, agent):
"By default, agent perceives objects within radius r."
### Error below: objects_near requires also a radius argument
return [self.object_percept(obj, agent)
for obj in self.objects_near(agent)] ### <- error
def execute_action(self, agent, action):
agent.bump = False
if action == 'TurnRight':
agent.heading = self.turn_heading(agent.heading, -1)
elif action == 'TurnLeft':
agent.heading = self.turn_heading(agent.heading, +1)
elif action == 'Forward':
self.move_to(agent, vector_add(agent.heading, agent.location))
# elif action == 'Grab':
# objs = [obj for obj in self.list_objects_at(agent.location)
# if agent.can_grab(obj)]
# if objs:
# agent.holding.append(objs[0])
elif action == 'Release':
if agent.holding:
agent.holding.pop()
def object_percept(self, obj, agent): #??? Should go to object?
"Return the percept for this object."
return obj.__class__.__name__
def default_location(self, object):
return (random.choice(self.width), random.choice(self.height))
def move_to(self, obj, destination):
"Move an object to a new location."
# Bumped?
obj.bump = self.some_objects_at(destination, Obstacle)
if not obj.bump:
# Move object and report to observers
obj.location = destination
for o in self.observers:
o.object_moved(obj)
def add_object(self, obj, location=(1, 1)):
super(XYEnvironment, self).add_object(obj, location)
obj.holding = []
obj.held = None
# self.objects.append(obj) # done in Environment!
# Report to observers
for obs in self.observers:
obs.object_added(obj)
def delete_object (self, obj):
super(XYEnvironment, self).delete_object(obj)
# Any more to do? Object holding anything or being held?
for obs in self.observers:
obs.object_deleted(obj)
def add_walls(self):
"Put walls around the entire perimeter of the grid."
for x in range(self.width):
self.add_object(Wall(), (x, 0))
self.add_object(Wall(), (x, self.height-1))
for y in range(self.height):
self.add_object(Wall(), (0, y))
self.add_object(Wall(), (self.width-1, y))
def add_observer (self, observer):
"""Adds an observer to the list of observers.
An observer is typically an EnvGUI.
Each observer is notified of changes in move_to and add_object,
by calling the observer's methods object_moved(obj, old_loc, new_loc)
and object_added(obj, loc)."""
self.observers.append(observer)
def turn_heading(self, heading, inc,
headings=[(1, 0), (0, 1), (-1, 0), (0, -1)]):
"Return the heading to the left (inc=+1) or right (inc=-1) in headings."
return headings[(headings.index(heading) + inc) % len(headings)]
class Obstacle (Object):
"""Something that can cause a bump, preventing an agent from
moving into the same square it's in."""
pass
class Wall (Obstacle):
pass
#______________________________________________________________________________
## Vacuum environment
class Dirt (Object):
pass
class VacuumEnvironment (XYEnvironment):
"""The environment of [Ex. 2.12]. Agent perceives dirty or clean,
and bump (into obstacle) or not; 2D discrete world of unknown size;
performance measure is 100 for each dirt cleaned, and -1 for
each turn taken."""
def __init__(self, width=10, height=10):
super(VacuumEnvironment, self).__init__(width, height)
self.add_walls()
def object_classes (self):
return [Wall, Dirt, ReflexVacuumAgent, RandomVacuumAgent,
TableDrivenVacuumAgent, ModelBasedVacuumAgent]
def percept(self, agent):
"""The percept is a tuple of ('Dirty' or 'Clean', 'Bump' or 'None').
Unlike the TrivialVacuumEnvironment, location is NOT perceived."""
status = if_(self.some_objects_at(agent.location, Dirt),
'Dirty', 'Clean')
bump = if_(agent.bump, 'Bump', 'None')
return (status, bump)
def execute_action(self, agent, action):
if action == 'Suck':
dirt_list = self.list_objects_at(agent.location, Dirt)
if dirt_list != []:
dirt = dirt_list[0]
agent.performance += 100
self.delete_object(dirt)
else:
super(VacuumEnvironment, self).execute_action(agent, action)
if action != 'Nop':
agent.performance -= 1
class TrivialVacuumEnvironment (Environment):
"""This environment has two locations, A and B. Each can be Dirty
or Clean. The agent perceives its location and the location's
status. This serves as an example of how to implement a simple
Environment."""
def __init__(self):
super(TrivialVacuumEnvironment, self).__init__()
self.status = {loc_A:random.choice(['Clean', 'Dirty']),
loc_B:random.choice(['Clean', 'Dirty'])}
def object_classes (self):
return [Wall, Dirt, ReflexVacuumAgent, RandomVacuumAgent,
TableDrivenVacuumAgent, ModelBasedVacuumAgent]
def percept(self, agent):
"Returns the agent's location, and the location status (Dirty/Clean)."
return (agent.location, self.status[agent.location])
def execute_action(self, agent, action):
"""Change agent's location and/or location's status; track performance.
Score 10 for each dirt cleaned; -1 for each move."""
if action == 'Right':
agent.location = loc_B
agent.performance -= 1
elif action == 'Left':
agent.location = loc_A
agent.performance -= 1
elif action == 'Suck':
if self.status[agent.location] == 'Dirty':
agent.performance += 10
self.status[agent.location] = 'Clean'
def default_location(self, object):
"Agents start in either location at random."
return random.choice([loc_A, loc_B])
#______________________________________________________________________________
class SimpleReflexAgent (Agent):
"""This agent takes action based solely on the percept. [Fig. 2.13]"""
def __init__(self, rules, interpret_input):
self.rules = rules
self.interpret_input = interpret_input
super(SimpleReflexAgent, self).__init__()
def make_agent_program (self):
rules = self.rules
interpret_input = self.interpret_input
def program(percept):
state = interpret_input(percept)
rule = rule_match(state, rules)
action = rule.action
return action
return program
class ReflexAgentWithState (Agent):
"""This agent takes action based on the percept and state. [Fig. 2.16]"""
def __init__(self, rules, udpate_state):
self.rules = rules
self.update_state = update_state
super(ReflexAgentWithState, self).__init__()
def make_agent_program (self):
rules = self.rules
update_state = self.update_state
state = None
action = None
def program(percept):
state = update_state(state, action, percept)
rule = rule_match(state, rules)
action = rule.action
return action
return program
#______________________________________________________________________________
## The Wumpus World
class Gold (Object): pass
class Pit (Object): pass
class Arrow (Object): pass
class Wumpus (Agent): pass
class Explorer (Agent): pass
class WumpusEnvironment(XYEnvironment):
def __init__(self, width=10, height=10):
super(WumpusEnvironment, self).__init__(width, height)
self.add_walls()
def object_classes (self):
return [Wall, Gold, Pit, Arrow, Wumpus, Explorer]
## Needs a lot of work ...
#______________________________________________________________________________
def compare_agents(EnvFactory, AgentFactories, n=10, steps=1000):
"""See how well each of several agents do in n instances of an environment.
Pass in a factory (constructor) for environments, and several for agents.
Create n instances of the environment, and run each agent in copies of
each one for steps. Return a list of (agent, average-score) tuples."""
envs = [EnvFactory() for i in range(n)]
return [(A, test_agent(A, steps, copy.deepcopy(envs)))
for A in AgentFactories]
def test_agent(AgentFactory, steps, envs):
"Return the mean score of running an agent in each of the envs, for steps"
total = 0
for env in envs:
agent = AgentFactory()
env.add_object(agent)
env.run(steps)
total += agent.performance
return float(total)/len(envs)
#_________________________________________________________________________
_docex = """
a = ReflexVacuumAgent()
a.program
a.program((loc_A, 'Clean')) ==> 'Right'
a.program((loc_B, 'Clean')) ==> 'Left'
a.program((loc_A, 'Dirty')) ==> 'Suck'
a.program((loc_A, 'Dirty')) ==> 'Suck'
e = TrivialVacuumEnvironment()
e.add_object(TraceAgent(ModelBasedVacuumAgent()))
e.run(5)
## Environments, and some agents, are randomized, so the best we can
## give is a range of expected scores. If this test fails, it does
## not necessarily mean something is wrong.
envs = [TrivialVacuumEnvironment() for i in range(100)]
def testv(A): return test_agent(A, 4, copy.deepcopy(envs))
testv(ModelBasedVacuumAgent)
(7 < _ < 11) ==> True
testv(ReflexVacuumAgent)
(5 < _ < 9) ==> True
testv(TableDrivenVacuumAgent)
(2 < _ < 6) ==> True
testv(RandomVacuumAgent)
(0.5 < _ < 3) ==> True
"""
#______________________________________________________________________________
# GUI - Graphical User Interface for Environments
# If you do not have Tkinter installed, either get a new installation of Python
# (Tkinter is standard in all new releases), or delete the rest of this file
# and muddle through without a GUI.
import Tkinter as tk
class EnvGUI (tk.Tk, object):
def __init__ (self, env, title = 'AIMA GUI', cellwidth=50, n=10):
# Initialize window
super(EnvGUI, self).__init__()
self.title(title)
# Create components
canvas = EnvCanvas(self, env, cellwidth, n)
toolbar = EnvToolbar(self, env, canvas)
for w in [canvas, toolbar]:
w.pack(side="bottom", fill="x", padx="3", pady="3")
class EnvToolbar (tk.Frame, object):
def __init__ (self, parent, env, canvas):
super(EnvToolbar, self).__init__(parent, relief='raised', bd=2)
# Initialize instance variables
self.env = env
self.canvas = canvas
self.running = False
self.speed = 1.0
# Create buttons and other controls
for txt, cmd in [('Step >', self.env.step), ('Run >>', self.run),
('Stop [ ]', self.stop),
('List objects', self.list_objects),
('List agents', self.list_agents)]:
tk.Button(self, text=txt, command=cmd).pack(side='left')
tk.Label(self, text='Speed').pack(side='left')
scale = tk.Scale(self, orient='h',
from_=(1.0), to=10.0, resolution=1.0,
command=self.set_speed)
scale.set(self.speed)
scale.pack(side='left')
def run(self):
print 'run'
self.running = True
self.background_run()
def stop(self):
print 'stop'
self.running = False
def background_run(self):
if self.running:
self.env.step()
# ms = int(1000 * max(float(self.speed), 0.5))
#ms = max(int(1000 * float(self.delay)), 1)
delay_sec = 1.0 / max(self.speed, 1.0) # avoid division by zero
ms = int(1000.0 * delay_sec) # seconds to milliseconds
self.after(ms, self.background_run)
def list_objects (self):
print "Objects in the environment:"
for obj in self.env.objects:
print "%s at %s" % (obj, obj.location)
def list_agents (self):
print "Agents in the environment:"
for agt in self.env.agents:
print "%s at %s" % (agt, agt.location)
def set_speed (self, speed):
self.speed = float(speed)
Utilities are as follows:
"""Provide some widely useful utilities. Safe for "from utils import *".
"""
from __future__ import generators
import operator, math, random, copy, sys, os.path, bisect, re
#______________________________________________________________________________
# Compatibility with Python 2.2, 2.3, and 2.4
# The AIMA code is designed to run in Python 2.2 and up (at some point,
# support for 2.2 may go away; 2.2 was released in 2001, and so is over
# 6 years old). The first part of this file brings you up to 2.5
# compatibility if you are running in Python 2.2 through 2.4:
try: bool, True, False ## Introduced in 2.3
except NameError:
class bool(int):
"Simple implementation of Booleans, as in PEP 285"
def __init__(self, val): self.val = val
def __int__(self): return self.val
def __repr__(self): return ('False', 'True')[self.val]
True, False = bool(1), bool(0)
try: sum ## Introduced in 2.3
except NameError:
def sum(seq, start=0):
"""Sum the elements of seq.
>>> sum([1, 2, 3])
6
"""
return reduce(operator.add, seq, start)
try: enumerate ## Introduced in 2.3
except NameError:
def enumerate(collection):
"""Return an iterator that enumerates pairs of (i, c[i]). PEP 279.
>>> list(enumerate('abc'))
[(0, 'a'), (1, 'b'), (2, 'c')]
"""
## Copied from PEP 279
i = 0
it = iter(collection)
while 1:
yield (i, it.next())
i += 1
try: reversed ## Introduced in 2.4
except NameError:
def reversed(seq):
"""Iterate over x in reverse order.
>>> list(reversed([1,2,3]))
[3, 2, 1]
"""
if hasattr(seq, 'keys'):
raise ValueError("mappings do not support reverse iteration")
i = len(seq)
while i > 0:
i -= 1
yield seq[i]
try: sorted ## Introduced in 2.4
except NameError:
def sorted(seq, cmp=None, key=None, reverse=False):
"""Copy seq and sort and return it.
>>> sorted([3, 1, 2])
[1, 2, 3]
"""
seq2 = copy.copy(seq)
if key:
if cmp == None:
cmp = __builtins__.cmp
seq2.sort(lambda x,y: cmp(key(x), key(y)))
else:
if cmp == None:
seq2.sort()
else:
seq2.sort(cmp)
if reverse:
seq2.reverse()
return seq2
try:
set, frozenset ## set builtin introduced in 2.4
except NameError:
try:
import sets ## sets module introduced in 2.3
set, frozenset = sets.Set, sets.ImmutableSet
except (NameError, ImportError):
class BaseSet:
"set type (see http://docs.python.org/lib/types-set.html)"
def __init__(self, elements=[]):
self.dict = {}
for e in elements:
self.dict[e] = 1
def __len__(self):
return len(self.dict)
def __iter__(self):
for e in self.dict:
yield e
def __contains__(self, element):
return element in self.dict
def issubset(self, other):
for e in self.dict.keys():
if e not in other:
return False
return True
def issuperset(self, other):
for e in other:
if e not in self:
return False
return True
def union(self, other):
return type(self)(list(self) + list(other))
def intersection(self, other):
return type(self)([e for e in self.dict if e in other])
def difference(self, other):
return type(self)([e for e in self.dict if e not in other])
def symmetric_difference(self, other):
return type(self)([e for e in self.dict if e not in other] +
[e for e in other if e not in self.dict])
def copy(self):
return type(self)(self.dict)
def __repr__(self):
elements = ", ".join(map(str, self.dict))
return "%s([%s])" % (type(self).__name__, elements)
__le__ = issubset
__ge__ = issuperset
__or__ = union
__and__ = intersection
__sub__ = difference
__xor__ = symmetric_difference
class frozenset(BaseSet):
"A frozenset is a BaseSet that has a hash value and is immutable."
def __init__(self, elements=[]):
BaseSet.__init__(elements)
self.hash = 0
for e in self:
self.hash |= hash(e)
def __hash__(self):
return self.hash
class set(BaseSet):
"A set is a BaseSet that does not have a hash, but is mutable."
def update(self, other):
for e in other:
self.add(e)
return self
def intersection_update(self, other):
for e in self.dict.keys():
if e not in other:
self.remove(e)
return self
def difference_update(self, other):
for e in self.dict.keys():
if e in other:
self.remove(e)
return self
def symmetric_difference_update(self, other):
to_remove1 = [e for e in self.dict if e in other]
to_remove2 = [e for e in other if e in self.dict]
self.difference_update(to_remove1)
self.difference_update(to_remove2)
return self
def add(self, element):
self.dict[element] = 1
def remove(self, element):
del self.dict[element]
def discard(self, element):
if element in self.dict:
del self.dict[element]
def pop(self):
key, val = self.dict.popitem()
return key
def clear(self):
self.dict.clear()
__ior__ = update
__iand__ = intersection_update
__isub__ = difference_update
__ixor__ = symmetric_difference_update
#______________________________________________________________________________
# Simple Data Structures: infinity, Dict, Struct
infinity = 1.0e400
def Dict(**entries):
"""Create a dict out of the argument=value arguments.
>>> Dict(a=1, b=2, c=3)
{'a': 1, 'c': 3, 'b': 2}
"""
return entries
class DefaultDict(dict):
"""Dictionary with a default value for unknown keys."""
def __init__(self, default):
self.default = default
def __getitem__(self, key):
if key in self: return self.get(key)
return self.setdefault(key, copy.deepcopy(self.default))
def __copy__(self):
copy = DefaultDict(self.default)
copy.update(self)
return copy
class Struct:
"""Create an instance with argument=value slots.
This is for making a lightweight object whose class doesn't matter."""
def __init__(self, **entries):
self.__dict__.update(entries)
def __cmp__(self, other):
if isinstance(other, Struct):
return cmp(self.__dict__, other.__dict__)
else:
return cmp(self.__dict__, other)
def __repr__(self):
args = ['%s=%s' % (k, repr(v)) for (k, v) in vars(self).items()]
return 'Struct(%s)' % ', '.join(args)
def update(x, **entries):
"""Update a dict; or an object with slots; according to entries.
>>> update({'a': 1}, a=10, b=20)
{'a': 10, 'b': 20}
>>> update(Struct(a=1), a=10, b=20)
Struct(a=10, b=20)
"""
if isinstance(x, dict):
x.update(entries)
else:
x.__dict__.update(entries)
return x
#______________________________________________________________________________
# Functions on Sequences (mostly inspired by Common Lisp)
# NOTE: Sequence functions (count_if, find_if, every, some) take function
# argument first (like reduce, filter, and map).
def removeall(item, seq):
"""Return a copy of seq (or string) with all occurences of item removed.
>>> removeall(3, [1, 2, 3, 3, 2, 1, 3])
[1, 2, 2, 1]
>>> removeall(4, [1, 2, 3])
[1, 2, 3]
"""
if isinstance(seq, str):
return seq.replace(item, '')
else:
return [x for x in seq if x != item]
def unique(seq):
"""Remove duplicate elements from seq. Assumes hashable elements.
>>> unique([1, 2, 3, 2, 1])
[1, 2, 3]
"""
return list(set(seq))
def product(numbers):
"""Return the product of the numbers.
>>> product([1,2,3,4])
24
"""
return reduce(operator.mul, numbers, 1)
def count_if(predicate, seq):
"""Count the number of elements of seq for which the predicate is true.
>>> count_if(callable, [42, None, max, min])
2
"""
f = lambda count, x: count + (not not predicate(x))
return reduce(f, seq, 0)
def find_if(predicate, seq):
"""If there is an element of seq that satisfies predicate; return it.
>>> find_if(callable, [3, min, max])
<built-in function min>
>>> find_if(callable, [1, 2, 3])
"""
for x in seq:
if predicate(x): return x
return None
def every(predicate, seq):
"""True if every element of seq satisfies predicate.
>>> every(callable, [min, max])
1
>>> every(callable, [min, 3])
0
"""
for x in seq:
if not predicate(x): return False
return True
def some(predicate, seq):
"""If some element x of seq satisfies predicate(x), return predicate(x).
>>> some(callable, [min, 3])
1
>>> some(callable, [2, 3])
0
"""
for x in seq:
px = predicate(x)
if px: return px
return False
def isin(elt, seq):
"""Like (elt in seq), but compares with is, not ==.
>>> e = []; isin(e, [1, e, 3])
True
>>> isin(e, [1, [], 3])
False
"""
for x in seq:
if elt is x: return True
return False
#______________________________________________________________________________
# Functions on sequences of numbers
# NOTE: these take the sequence argument first, like min and max,
# and like standard math notation: \sigma (i = 1..n) fn(i)
# A lot of programing is finding the best value that satisfies some condition;
# so there are three versions of argmin/argmax, depending on what you want to
# do with ties: return the first one, return them all, or pick at random.
def argmin(seq, fn):
"""Return an element with lowest fn(seq[i]) score; tie goes to first one.
>>> argmin(['one', 'to', 'three'], len)
'to'
"""
best = seq[0]; best_score = fn(best)
for x in seq:
x_score = fn(x)
if x_score < best_score:
best, best_score = x, x_score
return best
def argmin_list(seq, fn):
"""Return a list of elements of seq[i] with the lowest fn(seq[i]) scores.
>>> argmin_list(['one', 'to', 'three', 'or'], len)
['to', 'or']
"""
best_score, best = fn(seq[0]), []
for x in seq:
x_score = fn(x)
if x_score < best_score:
best, best_score = [x], x_score
elif x_score == best_score:
best.append(x)
return best
def argmin_random_tie(seq, fn):
"""Return an element with lowest fn(seq[i]) score; break ties at random.
Thus, for all s,f: argmin_random_tie(s, f) in argmin_list(s, f)"""
best_score = fn(seq[0]); n = 0
for x in seq:
x_score = fn(x)
if x_score < best_score:
best, best_score = x, x_score; n = 1
elif x_score == best_score:
n += 1
if random.randrange(n) == 0:
best = x
return best
def argmax(seq, fn):
"""Return an element with highest fn(seq[i]) score; tie goes to first one.
>>> argmax(['one', 'to', 'three'], len)
'three'
"""
return argmin(seq, lambda x: -fn(x))
def argmax_list(seq, fn):
"""Return a list of elements of seq[i] with the highest fn(seq[i]) scores.
>>> argmax_list(['one', 'three', 'seven'], len)
['three', 'seven']
"""
return argmin_list(seq, lambda x: -fn(x))
def argmax_random_tie(seq, fn):
"Return an element with highest fn(seq[i]) score; break ties at random."
return argmin_random_tie(seq, lambda x: -fn(x))
#______________________________________________________________________________
# Statistical and mathematical functions
def histogram(values, mode=0, bin_function=None):
"""Return a list of (value, count) pairs, summarizing the input values.
Sorted by increasing value, or if mode=1, by decreasing count.
If bin_function is given, map it over values first."""
if bin_function: values = map(bin_function, values)
bins = {}
for val in values:
bins[val] = bins.get(val, 0) + 1
if mode:
return sorted(bins.items(), key=lambda x: (x[1],x[0]), reverse=True)
else:
return sorted(bins.items())
def log2(x):
"""Base 2 logarithm.
>>> log2(1024)
10.0
"""
return math.log10(x) / math.log10(2)
def mode(values):
"""Return the most common value in the list of values.
>>> mode([1, 2, 3, 2])
2
"""
return histogram(values, mode=1)[0][0]
def median(values):
"""Return the middle value, when the values are sorted.
If there are an odd number of elements, try to average the middle two.
If they can't be averaged (e.g. they are strings), choose one at random.
>>> median([10, 100, 11])
11
>>> median([1, 2, 3, 4])
2.5
"""
n = len(values)
values = sorted(values)
if n % 2 == 1:
return values[n/2]
else:
middle2 = values[(n/2)-1:(n/2)+1]
try:
return mean(middle2)
except TypeError:
return random.choice(middle2)
def mean(values):
"""Return the arithmetic average of the values."""
return sum(values) / float(len(values))
def stddev(values, meanval=None):
"""The standard deviation of a set of values.
Pass in the mean if you already know it."""
if meanval == None: meanval = mean(values)
return math.sqrt(sum([(x - meanval)**2 for x in values]) / (len(values)-1))
def dotproduct(X, Y):
"""Return the sum of the element-wise product of vectors x and y.
>>> dotproduct([1, 2, 3], [1000, 100, 10])
1230
"""
return sum([x * y for x, y in zip(X, Y)])
def vector_add(a, b):
"""Component-wise addition of two vectors.
>>> vector_add((0, 1), (8, 9))
(8, 10)
"""
return tuple(map(operator.add, a, b))
def probability(p):
"Return true with probability p."
return p > random.uniform(0.0, 1.0)
def num_or_str(x):
"""The argument is a string; convert to a number if possible, or strip it.
>>> num_or_str('42')
42
>>> num_or_str(' 42x ')
'42x'
"""
if isnumber(x): return x
try:
return int(x)
except ValueError:
try:
return float(x)
except ValueError:
return str(x).strip()
def normalize(numbers, total=1.0):
"""Multiply each number by a constant such that the sum is 1.0 (or total).
>>> normalize([1,2,1])
[0.25, 0.5, 0.25]
"""
k = total / sum(numbers)
return [k * n for n in numbers]
## OK, the following are not as widely useful utilities as some of the other
## functions here, but they do show up wherever we have 2D grids: Wumpus and
## Vacuum worlds, TicTacToe and Checkers, and markov decision Processes.
orientations = [(1,0), (0, 1), (-1, 0), (0, -1)]
def turn_right(orientation):
return orientations[orientations.index(orientation)-1]
def turn_left(orientation):
return orientations[(orientations.index(orientation)+1) % len(orientations)]
def distance((ax, ay), (bx, by)):
"The distance between two (x, y) points."
return math.hypot((ax - bx), (ay - by))
def distance2((ax, ay), (bx, by)):
"The square of the distance between two (x, y) points."
return (ax - bx)**2 + (ay - by)**2
def clip(vector, lowest, highest):
"""Return vector, except if any element is less than the corresponding
value of lowest or more than the corresponding value of highest, clip to
those values.
>>> clip((-1, 10), (0, 0), (9, 9))
(0, 9)
"""
return type(vector)(map(min, map(max, vector, lowest), highest))
#______________________________________________________________________________
# Misc Functions
def printf(format, *args):
"""Format args with the first argument as format string, and write.
Return the last arg, or format itself if there are no args."""
sys.stdout.write(str(format) % args)
return if_(args, args[-1], format)
def caller(n=1):
"""Return the name of the calling function n levels up in the frame stack.
>>> caller(0)
'caller'
>>> def f():
... return caller()
>>> f()
'f'
"""
import inspect
return inspect.getouterframes(inspect.currentframe())[n][3]
def memoize(fn, slot=None):
"""Memoize fn: make it remember the computed value for any argument list.
If slot is specified, store result in that slot of first argument.
If slot is false, store results in a dictionary."""
if slot:
def memoized_fn(obj, *args):
if hasattr(obj, slot):
return getattr(obj, slot)
else:
val = fn(obj, *args)
setattr(obj, slot, val)
return val
else:
def memoized_fn(*args):
if not memoized_fn.cache.has_key(args):
memoized_fn.cache[args] = fn(*args)
return memoized_fn.cache[args]
memoized_fn.cache = {}
return memoized_fn
def if_(test, result, alternative):
"""Like C++ and Java's (test ? result : alternative), except
both result and alternative are always evaluated. However, if
either evaluates to a function, it is applied to the empty arglist,
so you can delay execution by putting it in a lambda.
>>> if_(2 + 2 == 4, 'ok', lambda: expensive_computation())
'ok'
"""
if test:
if callable(result): return result()
return result
else:
if callable(alternative): return alternative()
return alternative
def name(object):
"Try to find some reasonable name for the object."
return (getattr(object, 'name', 0) or getattr(object, '__name__', 0)
or getattr(getattr(object, '__class__', 0), '__name__', 0)
or str(object))
def isnumber(x):
"Is x a number? We say it is if it has a __int__ method."
return hasattr(x, '__int__')
def issequence(x):
"Is x a sequence? We say it is if it has a __getitem__ method."
return hasattr(x, '__getitem__')
def print_table(table, header=None, sep=' ', numfmt='%g'):
"""Print a list of lists as a table, so that columns line up nicely.
header, if specified, will be printed as the first row.
numfmt is the format for all numbers; you might want e.g. '%6.2f'.
(If you want different formats in differnt columns, don't use print_table.)
sep is the separator between columns."""
justs = [if_(isnumber(x), 'rjust', 'ljust') for x in table[0]]
if header:
table = [header] + table
table = [[if_(isnumber(x), lambda: numfmt % x, x) for x in row]
for row in table]
maxlen = lambda seq: max(map(len, seq))
sizes = map(maxlen, zip(*[map(str, row) for row in table]))
for row in table:
for (j, size, x) in zip(justs, sizes, row):
print getattr(str(x), j)(size), sep,
print
def AIMAFile(components, mode='r'):
"Open a file based at the AIMA root directory."
import utils
dir = os.path.dirname(utils.__file__)
return open(apply(os.path.join, [dir] + components), mode)
def DataFile(name, mode='r'):
"Return a file in the AIMA /data directory."
return AIMAFile(['..', 'data', name], mode)
#______________________________________________________________________________
# Queues: Stack, FIFOQueue, PriorityQueue
class Queue:
"""Queue is an abstract class/interface. There are three types:
Stack(): A Last In First Out Queue.
FIFOQueue(): A First In First Out Queue.
PriorityQueue(lt): Queue where items are sorted by lt, (default <).
Each type supports the following methods and functions:
q.append(item) -- add an item to the queue
q.extend(items) -- equivalent to: for item in items: q.append(item)
q.pop() -- return the top item from the queue
len(q) -- number of items in q (also q.__len())
Note that isinstance(Stack(), Queue) is false, because we implement stacks
as lists. If Python ever gets interfaces, Queue will be an interface."""
def __init__(self):
abstract
def extend(self, items):
for item in items: self.append(item)
def Stack():
"""Return an empty list, suitable as a Last-In-First-Out Queue."""
return []
class FIFOQueue(Queue):
"""A First-In-First-Out Queue."""
def __init__(self):
self.A = []; self.start = 0
def append(self, item):
self.A.append(item)
def __len__(self):
return len(self.A) - self.start
def extend(self, items):
self.A.extend(items)
def pop(self):
e = self.A[self.start]
self.start += 1
if self.start > 5 and self.start > len(self.A)/2:
self.A = self.A[self.start:]
self.start = 0
return e
class PriorityQueue(Queue):
"""A queue in which the minimum (or maximum) element (as determined by f and
order) is returned first. If order is min, the item with minimum f(x) is
returned first; if order is max, then it is the item with maximum f(x)."""
def __init__(self, order=min, f=lambda x: x):
update(self, A=[], order=order, f=f)
def append(self, item):
bisect.insort(self.A, (self.f(item), item))
def __len__(self):
return len(self.A)
def pop(self):
if self.order == min:
return self.A.pop(0)[1]
else:
return self.A.pop()[1]
Research Question:My research question about this version of Wumpus World would be, i found it in IEEE which is very good topic for this type of version its about Observant and Proactive Communication in Multi-Agent Teamwork. Here is the link below. http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/4052878/4052879/04052963.pdf?temp=x References: Y Zang, " Observant and Proactive Communication in Multi-Agent Teamwork," Intelligent Agent Technology, IEEE Conference, 2006, pp.460-466.Reflective questions:Tables AND Graphs After going through the topic i found some tables and graphs which where very useful for exploring more in to the topic and get involved in it. Yes the tables and graphs where effective enough to explain the points about the topic which i mentioned. Experiment Design: Here the author has explained very clearly about the experiment design and explaned each and every aspect point to point. Selecting Research Question: I was just going through IEEE website and i found this topic much more related and important for this type to FOL version.The auothor has forced me to get involved in this topic and i also found it interesting.I would like to do more research on this for my futher quaters.Conclusion:All in all this lab thought us about FOL wumpus world with knowledge engineering on it and more over with doing some practical work about the python implementation which turns around and lastly gives to make the research questions or issues. |
Reference Desk
|
|
| r3 - 21 May 2009 - 13:53:14 - NateDelgado
Guests are welcome to view our materials. To subscribe, edit, view raw markup, etc., you'll need to register for an account. Accounts are free (and will always be free) - your involvement helps us directly and indirectly (by demonstrating that our work matters to our funders...) StartingPoints has more info.
|
 Copyright 1999-2009 by the contributing authors. All material on this collaboration platform is the property of the contributing authors. Ideas, requests, problems regarding Ahatwiki? Send feedback Syndicate this site RSSATOM |