lists, dictionaries, sets and classes.stringsclass GridWorld():
ACTIONS = ['U', 'D', 'L', 'R']
def __init__(self):
self.n_rows = 9
self.n_cols = 9
# (row, column) where indexing is top to bottom, left to right (like a matrix)
start = (8, 0) #bottom, left
goal = (0, 8)
self.obstacles = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
self.costs = [[1, 1, 1, 5, 5, 5, 5, 1, 1],
[1, 1, 1, 5, 5, 5, 5, 1, 1],
[1, 1, 10, 10, 10, 10, 10, 1, 1],
[1, 1, 1, 10, 10, 10, 10, 1, 1],
[1, 1, 1, 1, 1, 10, 10, 1, 1],
[1, 1, 1, 1, 1, 10, 10, 1, 1],
[1, 1, 1, 1, 10, 10, 10, 1, 1],
[1, 1, 1, 10, 10, 10, 10, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1]]
def step(self, state, action):
"""
:param state: (row, col) tuple
:param action: 'U', 'D', 'L' or 'R'
:return: (success [True/False], new state, action cost)
"""
r, c = state
if action == 'U':
new_r = r - 1
new_c = c
elif action == 'D':
new_r = r + 1
new_c = c
elif action == 'L':
new_r = r
new_c = c - 1
elif action == 'R':
new_r = r
new_c = c + 1
else:
assert False, '!!! invalid action !!!'
if (not (0 <= new_r < 9)) or (not (0 <= new_c < 9)) or self.obstacles[new_r][new_c] == 1:
# collision occurs
return False, (r, c), self.costs[r][c]
else:
return True, (new_r, new_c), self.costs[new_r][new_c]
Before we implement Breadth-First Search, we first want to create a node like we did last week, that we can use to construct our search tree (and perform search operations on).
class StateNode:
def __init__(self, env, state, actions, path_cost):
self.env = env
self.state = state
self.actions = actions
self.path_cost = path_cost
def get_successors(self):
successors = []
for a in GridWorldEnv.ACTIONS:
success, new_state, a_cost = self.env.step(self.state, a)
if success:
successors.append(StateNode(self.env,
new_state,
self.actions + [a],
self.path_cost + self.env.get_state_cost(new_state)))
return successors
Breadth-First Search Implementation
def bfs(env, verbose=True):
container = [StateNode(env, env.init_state, [], 0)]
visited = set()
n_expanded = 0
while len(container) > 0:
# expand node
node = container.pop(0)
# test for goal
if env.is_goal(node.state):
if verbose:
print(f'Visited Nodes: {len(visited)},\t\tExpanded Nodes: {n_expanded},\t\t'
f'Nodes in Container: {len(container)}')
print(f'Cost of Path (with Costly Moves): {node.path_cost}')
return node.actions
# add successors
successors = node.get_successors()
for s in successors:
if s.state not in visited:
container.append(s)
visited.add(s.state)
n_expanded += 1
return None
Iterative-Deepening Depth First Search is an interesting technique, where we call depth-first search in a Breadth-First Search like technique. This combines the benefits of BFS and DFS.
DFS traverses through nodes going through successors of nodes.
To implement IDDFS, we first need to implement depth-limited depth-first search (which stops at a certain depth).
def depth_limited_dfs(env, max_depth, verbose=True):
container = [StateNode(env, env.init_state, [], 0)]
# revisiting should be allowed if cost (depth) is lower than previous visit (needed for optimality)
visited = {} # dict mapping states to path cost (here equal to depth) n_expanded = 0
while len(container) > 0:
# expand node
node = container.pop(-1)
if env.is_goal(node.state): # test for goal
if verbose:
print(f'Visited Nodes: {len(visited.keys())},\t\tExpanded Nodes: {n_expanded},\t\t'
f'Nodes in Container: {len(container)}')
print(f'Cost of Path (with Costly Moves): {node.path_cost}')
return node.actions
successors = node.get_successors() # add successors
for s in successors:
if (s.state not in visited or
len(s.actions) < visited[s.state]) and len(s.actions) < max_depth:
container.append(s)
visited[s.state] = len(s.actions)
n_expanded += 1
return None
In this case, both BFS and IDDFS have found solutions to this problem.