# logicPlan.py
# ————
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
Copyright By PowCoder代写 加微信 powcoder
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by Nero
# Student side autograding was added by , , and
In logicPlan.py, you will implement logic planning methods which are called by
Pacman agents (in logicAgents.py).
from typing import Dict, List, Tuple, Callable, Generator, Any
import util
import sys
import logic
import game
from logic import conjoin, disjoin
from logic import PropSymbolExpr, Expr, to_cnf, pycoSAT, parseExpr, pl_true
import itertools
import copy
pacman_str = ‘P’
food_str = ‘FOOD’
wall_str = ‘WALL’
pacman_wall_str = pacman_str + wall_str
DIRECTIONS = [‘North’, ‘South’, ‘East’, ‘West’]
blocked_str_map = dict([(direction, (direction + “_blocked”).upper()) for direction in DIRECTIONS])
geq_num_adj_wall_str_map = dict([(num, “GEQ_{}_adj_walls”.format(num)) for num in range(1, 4)])
DIR_TO_DXDY_MAP = {‘North’:(0, 1), ‘South’:(0, -1), ‘East’:(1, 0), ‘West’:(-1, 0)}
#______________________________________________________________________________
# QUESTION 1
def sentence1() -> Expr:
“””Returns a Expr instance that encodes that the following expressions are all true.
(not A) if and only if ((not B) or C)
(not A) or (not B) or C
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def sentence2() -> Expr:
“””Returns a Expr instance that encodes that the following expressions are all true.
C if and only if (B or D)
A implies ((not B) and (not D))
(not (B and (not C))) implies A
(not D) implies C
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def sentence3() -> Expr:
“””Using the symbols PacmanAlive_1 PacmanAlive_0, PacmanBorn_0, and PacmanKilled_0,
created using the PropSymbolExpr constructor, return a PropSymbolExpr
instance that encodes the following English sentences (in this order):
Pacman is alive at time 1 if and only if Pacman was alive at time 0 and it was
not killed at time 0 or it was not alive at time 0 and it was born at time 0.
Pacman cannot both be alive at time 0 and be born at time 0.
Pacman is born at time 0.
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def findModel(sentence: Expr) -> Dict[Expr, bool]:
“””Given a propositional logic sentence (i.e. a Expr instance), returns a satisfying
model if one exists. Otherwise, returns False.
cnf_sentence = to_cnf(sentence)
return pycoSAT(cnf_sentence)
def findModelUnderstandingCheck() -> Dict[Expr, bool]:
“””Returns the result of findModel(Expr(‘a’)) if lower cased expressions were allowed.
You should not use findModel or Expr in this method.
a = Expr(‘A’)
“*** BEGIN YOUR CODE HERE ***”
print(“a.__dict__ is:”, a.__dict__) # might be helpful for getting ideas
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def entails(premise: Expr, conclusion: Expr) -> bool:
“””Returns True if the premise entails the conclusion and False otherwise.
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def plTrueInverse(assignments: Dict[Expr, bool], inverse_statement: Expr) -> bool:
“””Returns True if the (not inverse_statement) is True given assignments and False otherwise.
pl_true may be useful here; see logic.py for its description.
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
#______________________________________________________________________________
# QUESTION 2
def atLeastOne(literals: List[Expr]) -> Expr:
Given a list of Expr literals (i.e. in the form A or ~A), return a single
Expr instance in CNF (conjunctive normal form) that represents the logic
that at least one of the literals ist is true.
>>> A = PropSymbolExpr(‘A’);
>>> B = PropSymbolExpr(‘B’);
>>> symbols = [A, B]
>>> atleast1 = atLeastOne(symbols)
>>> model1 = {A:False, B:False}
>>> print(pl_true(atleast1,model1))
>>> model2 = {A:False, B:True}
>>> print(pl_true(atleast1,model2))
>>> model3 = {A:True, B:True}
>>> print(pl_true(atleast1,model2))
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def atMostOne(literals: List[Expr]) -> Expr:
Given a list of Expr literals, return a single Expr instance in
CNF (conjunctive normal form) that represents the logic that at most one of
the expressions in the list is true.
itertools.combinations may be useful here.
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def exactlyOne(literals: List[Expr]) -> Expr:
Given a list of Expr literals, return a single Expr instance in
CNF (conjunctive normal form)that represents the logic that exactly one of
the expressions in the list is true.
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
#______________________________________________________________________________
# QUESTION 3
def pacmanSuccessorAxiomSingle(x: int, y: int, time: int, walls_grid: List[List[bool]]=None) -> Expr:
Successor state axiom for state (x,y,t) (from t-1), given the board (as a
grid representing the wall locations).
Current <==> (previous position at time t-1) & (took action to move to x, y)
Available actions are [‘North’, ‘East’, ‘South’, ‘West’]
Note that STOP is not an available action.
now, last = time, time – 1
possible_causes: List[Expr] = [] # enumerate all possible causes for P[x,y]_t
# the if statements give a small performance boost and are required for q4 and q5 correctness
if walls_grid[x][y+1] != 1:
possible_causes.append( PropSymbolExpr(pacman_str, x, y+1, time=last)
& PropSymbolExpr(‘South’, time=last))
if walls_grid[x][y-1] != 1:
possible_causes.append( PropSymbolExpr(pacman_str, x, y-1, time=last)
& PropSymbolExpr(‘North’, time=last))
if walls_grid[x+1][y] != 1:
possible_causes.append( PropSymbolExpr(pacman_str, x+1, y, time=last)
& PropSymbolExpr(‘West’, time=last))
if walls_grid[x-1][y] != 1:
possible_causes.append( PropSymbolExpr(pacman_str, x-1, y, time=last)
& PropSymbolExpr(‘East’, time=last))
if not possible_causes:
return None
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
def SLAMSuccessorAxiomSingle(x: int, y: int, time: int, walls_grid: List[List[bool]]) -> Expr:
Similar to `pacmanSuccessorStateAxioms` but accounts for illegal actions
where the pacman might not move timestep to timestep.
Available actions are [‘North’, ‘East’, ‘South’, ‘West’]
now, last = time, time – 1
moved_causes: List[Expr] = [] # enumerate all possible causes for P[x,y]_t, assuming moved to having moved
if walls_grid[x][y+1] != 1:
moved_causes.append( PropSymbolExpr(pacman_str, x, y+1, time=last)
& PropSymbolExpr(‘South’, time=last))
if walls_grid[x][y-1] != 1:
moved_causes.append( PropSymbolExpr(pacman_str, x, y-1, time=last)
& PropSymbolExpr(‘North’, time=last))
if walls_grid[x+1][y] != 1:
moved_causes.append( PropSymbolExpr(pacman_str, x+1, y, time=last)
& PropSymbolExpr(‘West’, time=last))
if walls_grid[x-1][y] != 1:
moved_causes.append( PropSymbolExpr(pacman_str, x-1, y, time=last)
& PropSymbolExpr(‘East’, time=last))
if not moved_causes:
return None
moved_causes_sent: Expr = conjoin([~PropSymbolExpr(pacman_str, x, y, time=last) , ~PropSymbolExpr(wall_str, x, y), disjoin(moved_causes)])
failed_move_causes: List[Expr] = [] # using merged variables, improves speed significantly
auxilary_expression_definitions: List[Expr] = []
for direction in DIRECTIONS:
dx, dy = DIR_TO_DXDY_MAP[direction]
wall_dir_clause = PropSymbolExpr(wall_str, x + dx, y + dy) & PropSymbolExpr(direction, time=last)
wall_dir_combined_literal = PropSymbolExpr(wall_str + direction, x + dx, y + dy, time=last)
failed_move_causes.append(wall_dir_combined_literal)
auxilary_expression_definitions.append(wall_dir_combined_literal % wall_dir_clause)
failed_move_causes_sent: Expr = conjoin([
PropSymbolExpr(pacman_str, x, y, time=last),
disjoin(failed_move_causes)])
return conjoin([PropSymbolExpr(pacman_str, x, y, time=now) % disjoin([moved_causes_sent, failed_move_causes_sent])] + auxilary_expression_definitions)
def pacphysicsAxioms(t: int, all_coords: List[Tuple], non_outer_wall_coords: List[Tuple], walls_grid: List[List] = None, sensorModel: Callable = None, successorAxioms: Callable = None) -> Expr:
t: timestep
all_coords: list of (x, y) coordinates of the entire problem
non_outer_wall_coords: list of (x, y) coordinates of the entire problem,
excluding the outer border (these are the actual squares pacman can
possibly be in)
walls_grid: 2D array of either -1/0/1 or T/F. Used only for successorAxioms.
Do NOT use this when making possible locations for pacman to be in.
sensorModel(t, non_outer_wall_coords) -> Expr: function that generates
the sensor model axioms. If None, it’s not provided, so shouldn’t be run.
successorAxioms(t, walls_grid, non_outer_wall_coords) -> Expr: function that generates
the sensor model axioms. If None, it’s not provided, so shouldn’t be run.
Return a logic sentence containing all of the following:
– for all (x, y) in all_coords:
If a wall is at (x, y) –> Pacman is not at (x, y)
– Pacman is at exactly one of the squares at timestep t.
– Pacman takes exactly one action at timestep t.
– Results of calling sensorModel(…), unless None.
– Results of calling successorAxioms(…), describing how Pacman can end in various
locations on this time step. Consider edge cases. Don’t call if None.
pacphysics_sentences = []
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
return conjoin(pacphysics_sentences)
def checkLocationSatisfiability(x1_y1: Tuple[int, int], x0_y0: Tuple[int, int], action0, action1, problem):
– x1_y1 = (x1, y1), a potential location at time t = 1
– x0_y0 = (x0, y0), Pacman’s location at time t = 0
– action0 = one of the four items in DIRECTIONS, Pacman’s action at time t = 0
– action1 = to ensure match with autograder solution
– problem = an instance of logicAgents.LocMapProblem
– there’s no sensorModel because we know everything about the world
– the successorAxioms should be allLegalSuccessorAxioms where needed
– a model where Pacman is at (x1, y1) at time t = 1
– a model where Pacman is not at (x1, y1) at time t = 1
walls_grid = problem.walls
walls_list = walls_grid.asList()
all_coords = list(itertools.product(range(problem.getWidth()+2), range(problem.getHeight()+2)))
non_outer_wall_coords = list(itertools.product(range(1, problem.getWidth()+1), range(1, problem.getHeight()+1)))
x0, y0 = x0_y0
x1, y1 = x1_y1
# We know which coords are walls:
map_sent = [PropSymbolExpr(wall_str, x, y) for x, y in walls_list]
KB.append(conjoin(map_sent))
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
#______________________________________________________________________________
# QUESTION 4
def positionLogicPlan(problem) -> List:
Given an instance of a PositionPlanningProblem, return a list of actions that lead to the goal.
Available actions are [‘North’, ‘East’, ‘South’, ‘West’]
Note that STOP is not an available action.
Overview: add knowledge incrementally, and query for a model each timestep. Do NOT use pacphysicsAxioms.
walls_grid = problem.walls
width, height = problem.getWidth(), problem.getHeight()
walls_list = walls_grid.asList()
x0, y0 = problem.startState
xg, yg = problem.goal
# Get lists of possible locations (i.e. without walls) and possible actions
all_coords = list(itertools.product(range(width + 2),
range(height + 2)))
non_wall_coords = [loc for loc in all_coords if loc not in walls_list]
actions = [ ‘North’, ‘South’, ‘East’, ‘West’ ]
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
#______________________________________________________________________________
# QUESTION 5
def foodLogicPlan(problem) -> List:
Given an instance of a FoodPlanningProblem, return a list of actions that help Pacman
eat all of the food.
Available actions are [‘North’, ‘East’, ‘South’, ‘West’]
Note that STOP is not an available action.
Overview: add knowledge incrementally, and query for a model each timestep. Do NOT use pacphysicsAxioms.
walls = problem.walls
width, height = problem.getWidth(), problem.getHeight()
walls_list = walls.asList()
(x0, y0), food = problem.start
food = food.asList()
# Get lists of possible locations (i.e. without walls) and possible actions
all_coords = list(itertools.product(range(width + 2), range(height + 2)))
non_wall_coords = [loc for loc in all_coords if loc not in walls_list]
actions = [ ‘North’, ‘South’, ‘East’, ‘West’ ]
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
“*** END YOUR CODE HERE ***”
#______________________________________________________________________________
# QUESTION 6
def localization(problem, agent) -> Generator:
problem: a LocalizationProblem instance
agent: a LocalizationLogicAgent instance
walls_grid = problem.walls
walls_list = walls_grid.asList()
all_coords = list(itertools.product(range(problem.getWidth()+2), range(problem.getHeight()+2)))
non_outer_wall_coords = list(itertools.product(range(1, problem.getWidth()+1), range(1, problem.getHeight()+1)))
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
for t in range(agent.num_timesteps):
“*** END YOUR CODE HERE ***”
yield possible_locations
#______________________________________________________________________________
# QUESTION 7
def mapping(problem, agent) -> Generator:
problem: a MappingProblem instance
agent: a MappingLogicAgent instance
pac_x_0, pac_y_0 = problem.startState
all_coords = list(itertools.product(range(problem.getWidth()+2), range(problem.getHeight()+2)))
non_outer_wall_coords = list(itertools.product(range(1, problem.getWidth()+1), range(1, problem.getHeight()+1)))
# map describes what we know, for GUI rendering purposes. -1 is unknown, 0 is open, 1 is wall
known_map = [[-1 for y in range(problem.getHeight()+2)] for x in range(problem.getWidth()+2)]
# Pacman knows that the outer border of squares are all walls
outer_wall_sent = []
for x, y in all_coords:
if ((x == 0 or x == problem.getWidth() + 1)
or (y == 0 or y == problem.getHeight() + 1)):
known_map[x][y] = 1
outer_wall_sent.append(PropSymbolExpr(wall_str, x, y))
KB.append(conjoin(outer_wall_sent))
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
for t in range(agent.num_timesteps):
“*** END YOUR CODE HERE ***”
yield known_map
#______________________________________________________________________________
# QUESTION 8
def slam(problem, agent) -> Generator:
problem: a SLAMProblem instance
agent: a SLAMLogicAgent instance
pac_x_0, pac_y_0 = problem.startState
all_coords = list(itertools.product(range(problem.getWidth()+2), range(problem.getHeight()+2)))
non_outer_wall_coords = list(itertools.product(range(1, problem.getWidth()+1), range(1, problem.getHeight()+1)))
# map describes what we know, for GUI rendering purposes. -1 is unknown, 0 is open, 1 is wall
known_map = [[-1 for y in range(problem.getHeight()+2)] for x in range(problem.getWidth()+2)]
# We know that the outer_coords are all walls.
outer_wall_sent = []
for x, y in all_coords:
if ((x == 0 or x == problem.getWidth() + 1)
or (y == 0 or y == problem.getHeight() + 1)):
known_map[x][y] = 1
outer_wall_sent.append(PropSymbolExpr(wall_str, x, y))
KB.append(conjoin(outer_wall_sent))
“*** BEGIN YOUR CODE HERE ***”
util.raiseNotDefined()
for t in range(agent.num_timesteps):
“*** END YOUR CODE HERE ***”
yield (known_map, possible_locations)
# Abbreviations
plp = positionLogicPlan
loc = localization
mp = mapping
flp = foodLogicPlan
# Sometimes the logic module uses pretty deep recursion on long expressions
sys.setrecursionlimit(100000)
#______________________________________________________________________________
# Important expression generating functions, useful to read for understanding of this project.
def sensorAxioms(t: int, non_outer_wall_coords: List[Tuple[int, int]]) -> Expr:
all_percept_exprs = []
combo_var_def_exprs = []
for direction in DIRECTIONS:
percept_exprs = []
dx, dy = DIR_TO_DXDY_MAP[direction]
for x, y in non_outer_wall_coords:
combo_var = PropSymbolExpr(pacman_wall_str, x, y, x + dx, y + dy, time=t)
percept_exprs.append(combo_var)
combo_var_def_exprs.append(combo_var % (
PropSymbolExpr(pacman_str, x, y, time=t) & PropSymbolExpr(wall_str, x + dx, y + dy)))
percept_unit_clause = PropSymbolExpr(blocked_str_map[direction], time = t)
all_percept_exprs.append(percept_unit_clause % disjoin(percept_exprs))
return conjoin(all_percept_exprs + combo_var_def_exprs)
def fourBitPerceptRules(t: int, percepts: List) -> Expr:
Localization and Mapping both use the 4 bit sensor, which tells us True/False whether
a wall is to pacman’s north, south, east, and west.
assert isinstance(percepts, list), “Percepts must be a list.”
assert len(percepts) == 4, “Percepts must be a length 4 list.”
percept_unit_clauses = []
for wall_present, direction in zip(percepts, DIRECTIONS):
percept_unit_clause = PropSymbolExpr(blocked_str_map[direction], time=t)
if not wall_present:
percept_unit_clause = ~PropSymbolExpr(blocked_str_map[direction], time=t)
percept_unit_clauses.append(percept_unit_clause) # The actual sensor readings
return conjoin(percept_unit_clauses)
def numAdjWallsPerceptRules(t: int, percepts: List) -> Expr:
SLAM uses a weaker numAdjWallsPerceptRules sensor, which tells us how many walls pacman is adjacent to
in its four directions.
000 = 0 adj walls.
100 = 1 adj wall.
110 = 2 adj walls.
111 = 3 adj walls.
assert isinstance(percepts, li
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com