class CellState(Enum):
BLOCKED = 1
OPEN = 2
UNKNOWN = 3
class Intel:
def __init__(self, N: int = 0):
self.N = N
self.visited = False
self.status = CellState.UNKNOWN
self.C = -1 # Value of -1 means we don't know this value (cell hasn't been visited yet)
self.B = 0
self.E = 0
self.H = N
self.blocked_probability = 0.5 # Used for agent 5
def __str__(self):
return f"N: {self.N}, visited: {self.visited}, status: {self.status}, C: {self.C}, B: {self.B}, " \
f"E: {self.E}, H: {self.H}"
def __repr__(self):
return self.__str__()
def _run_single_inference_agent3(grid_len: int, kb: List[List[Intel]]) -> bool:
changed = False
for row_idx, row in enumerate(kb):
for col_idx, intel in enumerate(row):
# If the cell has not been visited yet, we can't infer anything about its neighbors
# since C has not been set
# If Hx=0: nothing remains to be inferred about cell x.
if not intel.visited or intel.H == 0:
continue
# If Cx=Bx: all remaining hidden neighbors of x are empty.
if intel.C == intel.B:
for (n_row, n_col) in _get_neighbor_indices(grid_len, row_idx, col_idx):
if kb[n_row][n_col].status == CellState.UNKNOWN:
update_cell_status(CellState.OPEN, kb, n_row, n_col, grid_len)
changed = True
# If Nx−Cx=Ex: all remaining hidden neighbors of x are blocked.
elif intel.N - intel.C == intel.E:
for (n_row, n_col) in _get_neighbor_indices(grid_len, row_idx, col_idx):
if kb[n_row][n_col].status == CellState.UNKNOWN:
update_cell_status(CellState.BLOCKED, kb, n_row, n_col, grid_len)
changed = True
return changed
def agent3(grid: List[List[int]], inference: Callable = _run_single_inference_agent3):
"""
Args:
Returns:
list(tuple(int, int)): the path from the source node to the goal node which consists of coordinate points (i.e. x,y) in the form of tuples.
int: the length of the discovered path from source to goal (i.e. the length of the first return value)
list(tuple(int,int)): all visited squares from the source point. Contains int tuples in the form of (x,y).
int: trajectory - num of moves the agent makes
int: num of times the agent assumes wrong and enters a blocked square
"""
knowledge_base = create_initial_kb(grid)
grid_len = len(grid)
source, goal = (0, 0), (grid_len - 1, grid_len - 1)
full_path = [source]
solvable = True
num_bumps = 0
seen = defaultdict(int)
while solvable and goal != full_path[-1]:
# Create current grid based on current knowledge base
current_grid = []
for row_idx, row in enumerate(grid):
current_grid.append([])
for col_idx, _ in enumerate(row):
blocked = 1 if knowledge_base[row_idx][col_idx].status == CellState.BLOCKED else 0
current_grid[row_idx].append(blocked)
path, _, _, _, _ = a_star(current_grid, manhattan_heuristic, source)
if path == []: solvable = False
for path_idx, (row_idx, col_idx) in enumerate(path):
ran_inference = False
if not knowledge_base[row_idx][col_idx].visited:
if grid[row_idx][col_idx] == 0:
knowledge_base[row_idx][col_idx].C = \
_get_num_blocked_neighbors(grid, row_idx, col_idx)
knowledge_base[row_idx][col_idx].visited = True
if knowledge_base[row_idx][col_idx].status == CellState.UNKNOWN:
cell_state = \
CellState.BLOCKED if grid[row_idx][col_idx] == 1 else CellState.OPEN
update_cell_status(cell_state, knowledge_base, row_idx, col_idx, grid_len)
run_inference(grid_len, knowledge_base, inference)
ran_inference = True
# If we hit a block, restart and try again. Otherwise, continue
if grid[row_idx][col_idx] == 1 and full_path != []:
num_bumps += 1
source = full_path[-1]
break
# Only add to the path if we aren't at the source
# (otherwise we would have duplicates on restarts)
if (row_idx, col_idx) != source:
full_path.append((row_idx, col_idx))
# If there is a block in our current path, but the current cell was not blocked
if ran_inference and any(knowledge_base[x][y].status == CellState.BLOCKED for (x,y) in path[path_idx+1:]):
source = full_path[-1]
break
if solvable:
# Create current grid based on current knowledge base
current_grid = []
for row_idx, row in enumerate(grid):
current_grid.append([])
for col_idx, _ in enumerate(row):
blocked = 1 if knowledge_base[row_idx][col_idx].status == CellState.BLOCKED or not knowledge_base[row_idx][col_idx].visited else 0
current_grid[row_idx].append(blocked)
shortest_path, _, _, _, _ = a_star(current_grid, manhattan_heuristic, (0,0))
return shortest_path, len(shortest_path), full_path, len(full_path), num_bumps
return [], 0, full_path, len(full_path), num_bumps
def create_initial_kb(grid: List[List[int]]) -> List[List[Intel]]:
kb = []
for row_idx, row in enumerate(grid):
kb.append([])
for col_idx, _ in enumerate(row):
N = len(_get_neighbor_indices(len(grid), row_idx, col_idx))
kb[row_idx].append(Intel(N))
return kb
def run_inference(
grid_len: int,
kb: List[List[Intel]],
single_inference_func : Callable = _run_single_inference_agent3
):
changed = True
while changed:
changed = single_inference_func(grid_len, kb)
def update_cell_status(
new_state: CellState,
kb: List[List[Intel]],
row_idx: int,
col_idx: int,
grid_len: int
) -> None:
# Check if the status can be changed
if kb[row_idx][col_idx].status != CellState.UNKNOWN: return
if new_state == CellState.UNKNOWN: raise Exception("Cell state to change to cannot be unknown")
kb[row_idx][col_idx].status = new_state
# If we change the status, change neighbor info
neighbors = _get_neighbor_indices(grid_len, row_idx, col_idx)
for (row, col) in neighbors:
kb[row][col].H -= 1
if new_state == CellState.BLOCKED:
kb[row][col].B += 1
elif new_state == CellState.OPEN:
kb[row][col].E += 1
def _get_num_blocked_neighbors(
grid: List[List[int]],
row_idx: int,
col_idx: int
) -> int:
num_blocked = 0
neighbors = _get_neighbor_indices(len(grid), row_idx, col_idx)
for row, col in neighbors:
if grid[row][col] == 1:
num_blocked += 1
return num_blocked
def _get_neighbor_indices(grid_len: int, row_idx: int, col_idx: int) -> List[Tuple[int, int]]:
neighbors = []
for row in range(row_idx - 1, row_idx + 2):
if row < 0 or row >= grid_len:
continue
for col in range(col_idx - 1, col_idx + 2):
if row_idx == row and col_idx == col:
continue
elif col < 0 or col >= grid_len:
continue
neighbors.append((row, col))
return neighbors
agent3(gen_gridworld(5, 0.3))
grid = gen_gridworld(30, 0.25)
discovered_path_3, length_discovered_path_3, full_path_3, trajectory_3, num_bumps_3 = agent3(grid)
print(f"Agent 3: { length_discovered_path_3}, trajectory: {trajectory_3}, Num of walls bumped into: {num_bumps_3}")
pretty_print_explored_region(grid, full_path_3, discovered_path_3)
from typing import DefaultDict
from collections import Counter
from itertools import chain
import sys, copy
sys.setrecursionlimit(1500)
class Constraint:
def __init__(self, variables: list[tuple[int,int]], c:int):
self.variables: set[tuples[int,int]] = set(variables)
self.c: int = c
def __str__(self):
return f"V:{self.variables}-C:{self.c}"
def __repr__(self):
return self.__str__()
### Trivial Rule Technique
def _trivial_rule(grid_len: int, kb: List[List[Intel]], csp: dict[tuple[int,int],Constraint]) -> bool:
changed = False
for (x,y), constraint in list(csp.items()):
if constraint.c == 0: # all variables are open
for (i, j) in constraint.variables:
update_cell_status(CellState.OPEN, kb, i, j, grid_len)
del csp[x,y]
changed = True
elif constraint.c == len(constraint.variables): # all variables are blocked
for (i, j) in constraint.variables:
update_cell_status(CellState.BLOCKED, kb, i, j, grid_len)
del csp[x,y]
changed = True
return changed
### Subset Rule Technique
def _subset_rule(grid_len: int, kb: List[List[Intel]], csp: dict[tuple[int,int],Constraint]) -> bool:
changed = False
new_csp = {}
for p1, constraint1 in list(csp.items()):
for p2, constraint2 in list(csp.items()):
if p1 == p2: continue
if len(constraint1.variables) <= len(constraint2.variables):
continue
if constraint2.variables.issubset(constraint1.variables):
diff = constraint1.variables - constraint2.variables
if p1 in new_csp and len(new_csp[p1].variables) < len(diff): #Small optimization we want the most reduced equation
continue
new_csp[p1] = Constraint(diff, constraint1.c - constraint2.c)
for point, new_constraint in new_csp.items():
csp[point] = new_constraint
return len(new_csp) > 0
### CSP Solver Technique
def _is_valid(constraints: List[Constraint], mapper: DefaultDict[Tuple[int,int], int]) -> bool:
for constraint in constraints:
if sum([mapper[variable] for variable in constraint.variables]) > constraint.c:
return False
return True
def _is_solution(constraints: List[Constraint], mapper: DefaultDict[Tuple[int,int], int]) -> bool:
for constraint in constraints:
if sum([mapper[variable] for variable in constraint.variables]) != constraint.c:
return False
return True
def _get_constraint_sums(constraints: list[Constraint], mapper:DefaultDict[tuple[int,int], int]) -> list[int]:
sums = []
for constraint in constraints:
sums.append((sum([mapper[variable] for variable in constraint.variables]), constraint.c))
return sums
def _backtrack(constraints: list[Constraint], mapper: DefaultDict[tuple[int,int], int], solution_list: list[list[list[int,int]]], variable_list:list[tuple[int,int]], backtrack_idx:int) -> None:
if (backtrack_idx > len(variable_list) or not _is_valid(constraints, mapper)):
return
if (_is_solution(constraints, mapper)):
solution_list.append([[k,mapper[k]] for k in variable_list])
for idx in range(backtrack_idx, len(variable_list)):
candidate = variable_list[idx]
mapper[candidate] = 1
_backtrack(constraints, mapper, solution_list, variable_list, idx + 1)
mapper[candidate] = 0
def _csp_solver(grid_len: int, kb: List[List[Intel]], csp: dict[tuple[int,int], Constraint], is_agent_5: bool = False) -> bool:
MAX_BACKTRACK_VARS = 20 # This takes ~ 2 min and we really don't want to do more than this for a single list
changed = False
constraints = list(csp.values())
mapper = defaultdict(int) # tracks the value of the variables during backtracking
disjoint_constraints = [] # [[superset, [constraints]]]
# break up constraints into disjoint sets
for constraint in constraints:
for superset, constraint_list in disjoint_constraints:
if len(constraint.variables & superset) > 0:
superset |= copy.deepcopy(constraint.variables)
constraint_list.append(copy.deepcopy(constraint))
break
else:
disjoint_constraints.append([copy.deepcopy(constraint.variables), [copy.deepcopy(constraint)]])
# Apply backtracking to each of the disjoint set
for superset, constraint_list in disjoint_constraints:
cnter = Counter(chain.from_iterable([c.variables for c in constraint_list])) #get the num of times a variable comes up in the constraints
variable_list = sorted(list(cnter.keys()), key=lambda k: cnter[k], reverse=True)
if len(variable_list) > MAX_BACKTRACK_VARS: continue # Set an upper bound on the runtime to make this feasible
solution_list = []
_backtrack(list(set(constraint_list)), mapper, solution_list, variable_list, 0)
solution_cnter = Counter([(point, val) for solution in solution_list for point, val in solution]) #stores the number of times a particular variable was solved with a particular state (i.e (1,3) with OPEN -> 2 Times)
for ((x,y), val), cnt in solution_cnter.items():
if cnt == len(solution_list):
if val == 0:
update_cell_status(CellState.OPEN, kb, x, y, grid_len)
elif val == 1:
update_cell_status(CellState.BLOCKED, kb, x, y, grid_len)
csp.pop((x,y), None) #TODO Don't think we need this bc csp will only have constraints on squares that we visited and we are solving for squares that we haven't
changed = True
elif is_agent_5: #TODO Agent 5 partial solution use probability here
"""
"""
if val == 1:
kb[x][y].blocked_probability = cnt / len(solution_list)
else:
kb[x][y].blocked_probability = 1 - (cnt / len(solution_list))
# print(solution_list)
return changed
### Equation Solver Agent 4 Inference Algo
def compute_csp(grid_len:int, kb: List[List[Intel]]) -> dict[tuple[int,int],Constraint]:
csp = {}
# Create Equations
for row_idx, row in enumerate(kb):
for col_idx, intel in enumerate(row):
if intel.H != 0 and intel.C != -1:
neighbors = _get_neighbor_indices(grid_len, row_idx, col_idx)
csp[row_idx, col_idx] = Constraint([(x,y) for x,y in neighbors if kb[x][y].status == CellState.UNKNOWN], intel.C - intel.B)
return csp
### Agent 4 Inference
def _run_single_inference_agent4(grid_len: int, kb: List[List[Intel]]) -> bool:
csp = compute_csp(grid_len, kb)
while True: # Solve Constraints (each successive technique gets smarter)
if (_trivial_rule(grid_len, kb, csp)):
csp = compute_csp(grid_len, kb)
continue
if (_subset_rule(grid_len, kb, csp)):
continue
if (_csp_solver(grid_len, kb, csp)):
csp = compute_csp(grid_len, kb)
continue
break
return False
def agent4(grid: List[List[int]], inference: Callable = _run_single_inference_agent4):
return agent3(grid, inference)
def agent4_V2(grid: List[List[int]], inference: Callable = _run_single_inference_agent4_V2):
return agent3(grid, inference)
grid = gen_gridworld(50, 0.28) # old grid is in grid
discovered_path_3, length_discovered_path_3, full_path_3, trajectory_3, num_bumps_3 = agent3(grid, _run_single_inference_agent3)
print(f"Agent 3: {length_discovered_path_3}, trajectory: {trajectory_3}, Num of walls bumped into: {num_bumps_3}")
pretty_print_explored_region(grid, full_path_3, discovered_path_3)
discovered_path_4, length_discovered_path_4, full_path_4, trajectory_4, num_bumps_4 = agent4(grid, _run_single_inference_agent4)
print(f"Agent 4: {length_discovered_path_4}, trajectory: {trajectory_4}, Num of walls bumped into: {num_bumps_4}")
pretty_print_explored_region(grid, full_path_4, discovered_path_4)
print(f"Agent 3 : Path length: {length_discovered_path_3}, trajectory: {trajectory_3}, Num of walls bumped into: {num_bumps_3}")
print(f"Agent 4 : Path length: {length_discovered_path_4}, trajectory: {trajectory_4}, Num of walls bumped into: {num_bumps_4}")
### Agent 5 Inference
def _run_single_inference_agent5(grid_len: int, kb: List[List[Intel]]) -> bool:
csp = compute_csp(grid_len, kb)
while True: # Solve Constraints (each successive technique gets smarter)
if (_trivial_rule(grid_len, kb, csp)):
csp = compute_csp(grid_len, kb)
continue
if (_subset_rule(grid_len, kb, csp)):
continue
if (_csp_solver(grid_len, kb, csp, True)):
csp = compute_csp(grid_len, kb)
continue
break
return False
def agent5(grid: List[List[int]], inference: Callable = _run_single_inference_agent5):
"""
Args:
Returns:
list(tuple(int, int)): the path from the source node to the goal node which consists of coordinate points (i.e. x,y) in the form of tuples.
int: the length of the discovered path from source to goal (i.e. the length of the first return value)
list(tuple(int,int)): all visited squares from the source point. Contains int tuples in the form of (x,y).
int: trajectory - num of moves the agent makes
int: num of times the agent assumes wrong and enters a blocked square
"""
knowledge_base = create_initial_kb(grid)
grid_len = len(grid)
source, goal = (0, 0), (grid_len - 1, grid_len - 1)
full_path = [source]
solvable = True
num_bumps = 0
BLOCK_THRESHOLD = 0.75
seen = defaultdict(int)
while solvable and goal != full_path[-1]:
# Create current grid based on current knowledge base
current_grid = []
probability_grid = []
for row_idx, row in enumerate(grid):
current_grid.append([])
probability_grid.append([])
for col_idx, _ in enumerate(row):
blocked = 1 if knowledge_base[row_idx][col_idx].status == CellState.BLOCKED else 0
current_grid[row_idx].append(blocked)
if blocked == 0 and knowledge_base[row_idx][col_idx].blocked_probability >= BLOCK_THRESHOLD: blocked = 1
probability_grid[row_idx].append(blocked)
path, _, _, _, _ = a_star(probability_grid, manhattan_heuristic, source)
if path == []:
path, _, _, _, _ = a_star(current_grid, manhattan_heuristic, source)
if path == []: solvable = False
for path_idx, (row_idx, col_idx) in enumerate(path):
ran_inference = False
if not knowledge_base[row_idx][col_idx].visited:
if grid[row_idx][col_idx] == 0:
knowledge_base[row_idx][col_idx].C = \
_get_num_blocked_neighbors(grid, row_idx, col_idx)
knowledge_base[row_idx][col_idx].visited = True
if knowledge_base[row_idx][col_idx].status == CellState.UNKNOWN:
cell_state = \
CellState.BLOCKED if grid[row_idx][col_idx] == 1 else CellState.OPEN
update_cell_status(cell_state, knowledge_base, row_idx, col_idx, grid_len)
run_inference(grid_len, knowledge_base, inference)
ran_inference = True
# If we hit a block, restart and try again. Otherwise, continue
if grid[row_idx][col_idx] == 1 and full_path != []:
num_bumps += 1
source = full_path[-1]
break
# Only add to the path if we aren't at the source
# (otherwise we would have duplicates on restarts)
if (row_idx, col_idx) != source:
full_path.append((row_idx, col_idx))
# If there is a block in our current path, but the current cell was not blocked
if ran_inference and any(knowledge_base[x][y].status == CellState.BLOCKED for (x,y) in path[path_idx+1:]):
source = full_path[-1]
break
if solvable:
# Create current grid based on current knowledge base
current_grid = []
for row_idx, row in enumerate(grid):
current_grid.append([])
for col_idx, _ in enumerate(row):
blocked = 1 if knowledge_base[row_idx][col_idx].status == CellState.BLOCKED or not knowledge_base[row_idx][col_idx].visited else 0
current_grid[row_idx].append(blocked)
shortest_path, _, _, _, _ = a_star(current_grid, manhattan_heuristic, (0,0))
return shortest_path, len(shortest_path), full_path, len(full_path), num_bumps
return [], 0, full_path, len(full_path), num_bumps
grid = gen_gridworld(50, 0.28) # old grid is in grid
discovered_path_4, length_discovered_path_4, full_path_4, trajectory_4, num_bumps_4 = agent4(grid, _run_single_inference_agent3)
print(f"Agent 4: {length_discovered_path_4}, trajectory: {trajectory_4}, Num of walls bumped into: {num_bumps_4}")
pretty_print_explored_region(grid, full_path_4, discovered_path_4)
discovered_path_5, length_discovered_path_5, full_path_5, trajectory_5, num_bumps_5 = agent5(grid, _run_single_inference_agent5)
print(f"Agent 5: {length_discovered_path_5}, trajectory: {trajectory_5}, Num of walls bumped into: {num_bumps_5}")
pretty_print_explored_region(grid, full_path_5, discovered_path_5)
print(f"Agent 4 : Path length: {length_discovered_path_4}, trajectory: {trajectory_4}, Num of walls bumped into: {num_bumps_4}")
print(f"Agent 5 : Path length: {length_discovered_path_5}, trajectory: {trajectory_5}, Num of walls bumped into: {num_bumps_5}")
import numpy as np
from matplotlib.pyplot import figure
import matplotlib.pyplot as plt
agent3_trajectory_length = []
agent2_trajectory_length = []
agent1_trajectory_length = []
densities = np.linspace(0, .33, 15)
n = 65
for density in densities:
agent3_cum_trajectory = agent2_cum_trajectory = agent1_cum_trajectory = cnt = 0
while cnt != n:
grid = gen_gridworld(101, density)
_, path, _, _, agent2_trajectory, _, _ = repeated_a_star(grid, False)
if not path:
continue
_, _, _, _, agent1_trajectory, _, _ = cyclops_repeated_a_star(grid, False)
_, _, _, agent3_trajectory, _ = agent3(grid)
cnt += 1
agent3_cum_trajectory += agent3_trajectory
agent2_cum_trajectory += agent2_trajectory
agent1_cum_trajectory += agent1_trajectory
agent3_trajectory_length.append(agent3_cum_trajectory/n)
agent2_trajectory_length.append(agent2_cum_trajectory/n)
agent1_trajectory_length.append(agent1_cum_trajectory/n)
plt.plot(densities, agent3_trajectory_length)
plt.plot(densities, agent2_trajectory_length)
plt.plot(densities, agent1_trajectory_length)
plt.legend(["Agent 3", "Agent2", "Agent 1"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Trajectory Length')
plt.title('Density vs Average Trajectory Length')
plt.show()
agent3_path_length = []
agent2_path_length = []
agent1_path_length = []
densities = np.linspace(0, .33, 15)
n = 65
for density in densities:
agent3_summation = agent2_summation = agent1_summation = cnt = 0
while cnt != n:
grid = gen_gridworld(101, density)
_, path, agent2_length, _, _, _, _ = repeated_a_star(grid, False)
if not path:
continue
_, _, agent1_length, _, _, _, _ = cyclops_repeated_a_star(grid, False)
_, agent3_length, _, _,_ = agent3(grid)
cnt += 1
agent3_summation += agent3_length
agent2_summation += agent2_length
agent1_summation += agent1_length
agent3_path_length.append(agent3_summation/n)
agent2_path_length.append(agent2_summation/n)
agent1_path_length.append(agent1_summation/n)
plt.plot(densities, agent3_path_length)
plt.plot(densities, agent2_path_length)
plt.plot(densities, agent1_path_length)
plt.legend(["Agent 3", "Agent2", "Agent 1"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Path Length')
plt.title('Density vs Average Final Path Length')
plt.show()
from timeit import default_timer as timer
agent3_planning_time = []
agent2_planning_time = []
agent1_planning_time = []
densities = np.linspace(0, .33, 15)
n = 65
for density in densities:
agent3_summation = agent2_summation = agent1_summation = cnt = 0
while cnt != n:
grid = gen_gridworld(101, density)
start = timer()
_, path, _, _, _, _, _ = repeated_a_star(grid, False)
stop = timer()
if not path:
continue
agent2_summation += (stop-start)
start = timer()
_, _, agent1_length, _, _, _, _ = cyclops_repeated_a_star(grid, False)
stop = timer()
agent1_summation += (stop-start)
start = timer()
_, agent3_length, _, _,_ = agent3(grid)
stop = timer()
agent3_summation += (stop-start)
cnt += 1
agent3_planning_time.append(agent3_summation/n)
agent2_planning_time.append(agent2_summation/n)
agent1_planning_time.append(agent1_summation/n)
plt.plot(densities, agent3_planning_time)
plt.plot(densities, agent2_planning_time)
plt.plot(densities, agent1_planning_time)
plt.legend(["Agent 3", "Agent2", "Agent 1"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Planning Time')
plt.title('Density vs Average Planning Time')
plt.show()
from timeit import default_timer as timer
from matplotlib.pyplot import figure
import matplotlib.pyplot as plt
# agent3_trajectory_length = []
# agent4_trajectory_length = []
# agent3_path_length = []
# agent4_path_length = []
# agent3_planning_time = []
# agent4_planning_time = []
# agent3_walls_bumped = []
# agent4_walls_bumped = []
# densities = np.linspace(0, .33, 15)
# n = 65
# for density in densities:
# agent3_summation = agent4_summation = cnt = 0
# agent3_cum_trajectory = agent4_cum_trajectory = 0
# agent3_cum_time = agent4_cum_time = 0
# agent3_cum_bumps = agent4_cum_bumps = 0
# while cnt != n:
# grid = gen_gridworld(101, density)
# path, _, _, _, _ = a_star(grid)
# if not path:
# continue
# start = timer()
# _, agent4_length, _, agent4_trajectory , agent4_bumps = agent4(grid)
# stop = timer()
# agent4_cum_time += (stop-start)
# start = timer()
# _, agent3_length, _, agent3_trajectory, agent3_bumps = agent3(grid)
# stop = timer()
# agent3_cum_time += (stop-start)
# cnt += 1
# agent3_cum_trajectory += agent3_trajectory
# agent4_cum_trajectory += agent4_trajectory
# agent3_summation += agent3_length
# agent4_summation += agent4_length
# agent3_cum_bumps += agent3_bumps
# agent4_cum_bumps += agent4_bumps
# agent3_trajectory_length.append(agent3_cum_trajectory/n)
# agent4_trajectory_length.append(agent4_cum_trajectory/n)
# agent3_path_length.append(agent3_summation/n)
# agent4_path_length.append(agent4_summation/n)
# agent3_planning_time.append(agent3_cum_time/n)
# agent4_planning_time.append(agent4_cum_time/n)
# agent3_walls_bumped.append(agent3_cum_bumps/n)
# agent4_walls_bumped.append(agent4_cum_bumps/n)
plt.plot(densities, agent3_trajectory_length)
plt.plot(densities, agent4_trajectory_length)
plt.legend(["Agent 3", "Agent4"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Trajectory Length')
plt.title('Density vs Average Trajectory Length')
plt.show()
# agent3_path_length = []
# agent4_path_length = []
# densities = np.linspace(0, .33, 15)
# n = 65
# for density in densities:
# agent3_summation = agent4_summation = cnt = 0
# while cnt != n:
# grid = gen_gridworld(101, density)
# path, _, _, _, _ = a_star(grid)
# if not path:
# continue
# _, agent4_length, _, _,_ = agent4(grid)
# _, agent3_length, _, _,_ = agent3(grid)
# cnt += 1
# agent3_summation += agent3_length
# agent4_summation += agent4_length
# agent3_path_length.append(agent3_summation/n)
# agent4_path_length.append(agent4_summation/n)
plt.plot(densities, agent3_path_length)
plt.plot(densities, agent4_path_length)
plt.legend(["Agent 3", "Agent4"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Path Length')
plt.title('Density vs Average Final Path Length')
plt.show()
# from timeit import default_timer as timer
# agent3_planning_time = []
# agent4_planning_time = []
# densities = np.linspace(0, .33, 15)
# n = 65
# for density in densities:
# agent3_summation = agent4_summation = cnt = 0
# while cnt != n:
# grid = gen_gridworld(101, density)
# path, _, _, _, _ = a_star(grid)
# if not path:
# continue
# start = timer()
# _, agent4_length, _, _,_ = agent4(grid)
# stop = timer()
# agent4_summation += (stop-start)
# start = timer()
# _, agent3_length, _, _,_ = agent3(grid)
# stop = timer()
# agent3_summation += (stop-start)
# cnt += 1
# agent3_planning_time.append(agent3_summation/n)
# agent4_planning_time.append(agent4_summation/n)
plt.plot(densities, agent3_planning_time)
plt.plot(densities, agent4_planning_time)
plt.legend(["Agent 3", "Agent4"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Planning Time')
plt.title('Density vs Average Planning Time')
plt.show()
# agent3_walls_bumped = []
# agent4_walls_bumped = []
# densities = np.linspace(0, .33, 15)
# n = 65
# for density in densities:
# agent3_cum_bumps = agent4_cum_bumps = cnt = 0
# while cnt != n:
# grid = gen_gridworld(101, density)
# path, _, _, _, _ = a_star(grid)
# if not path:
# continue
# _, _, _, _, agent4_bumps = agent4(grid)
# _, _, _, _, agent3_bumps = agent3(grid)
# cnt += 1
# agent3_cum_bumps += agent3_bumps
# agent4_cum_bumps += agent4_bumps
# agent3_walls_bumped.append(agent3_cum_bumps/n)
# agent4_walls_bumped.append(agent4_cum_bumps/n)
plt.plot(densities, agent3_walls_bumped)
plt.plot(densities, agent4_walls_bumped)
plt.legend(["Agent 3", "Agent4"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Walls Bumped')
plt.title('Density vs Average Walls Bumped')
plt.show()
from timeit import default_timer as timer
from matplotlib.pyplot import figure
import matplotlib.pyplot as plt
agent4_trajectory_length = []
agent5_trajectory_length = []
agent4_path_length = []
agent5_path_length = []
agent4_planning_time = []
agent5_planning_time = []
agent4_walls_bumped = []
agent5_walls_bumped = []
densities = np.linspace(0, .33, 15)
n = 5
for density in densities:
agent4_summation = agent5_summation = cnt = 0
agent4_cum_trajectory = agent5_cum_trajectory = 0
agent4_cum_time = agent5_cum_time = 0
agent4_cum_bumps = agent5_cum_bumps = 0
while cnt != n:
grid = gen_gridworld(101, density)
path, _, _, _, _ = a_star(grid)
if not path:
continue
start = timer()
_, agent5_length, _, agent5_trajectory , agent5_bumps = agent5(grid)
stop = timer()
agent5_cum_time += (stop-start)
start = timer()
_, agent4_length, _, agent4_trajectory, agent4_bumps = agent4(grid)
stop = timer()
agent4_cum_time += (stop-start)
cnt += 1
agent4_cum_trajectory += agent4_trajectory
agent5_cum_trajectory += agent5_trajectory
agent4_summation += agent4_length
agent5_summation += agent5_length
agent4_cum_bumps += agent4_bumps
agent5_cum_bumps += agent5_bumps
agent4_trajectory_length.append(agent4_cum_trajectory/n)
agent5_trajectory_length.append(agent5_cum_trajectory/n)
agent4_path_length.append(agent4_summation/n)
agent5_path_length.append(agent5_summation/n)
agent4_planning_time.append(agent4_cum_time/n)
agent5_planning_time.append(agent5_cum_time/n)
agent4_walls_bumped.append(agent4_cum_bumps/n)
agent5_walls_bumped.append(agent5_cum_bumps/n)
plt.plot(densities, agent4_planning_time)
plt.plot(densities, agent5_planning_time)
plt.legend(["Agent 4", "Agent5"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Planning Time')
plt.title('Density vs Average Planning Time')
plt.show()
plt.plot(densities, agent4_path_length)
plt.plot(densities, agent5_path_length)
plt.legend(["Agent 4", "Agent5"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Path Length')
plt.title('Density vs Average Final Path Length')
plt.show()
plt.plot(densities, agent4_trajectory_length)
plt.plot(densities, agent5_trajectory_length)
plt.legend(["Agent 4", "Agent5"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Trajectory Length')
plt.title('Density vs Average Trajectory Length')
plt.show()
plt.plot(densities, agent4_walls_bumped)
plt.plot(densities, agent5_walls_bumped)
plt.legend(["Agent 4", "Agent 5"])
plt.xticks(densities)
plt.xticks(rotation = 90)
plt.xlabel('Density')
plt.ylabel('Average Walls Bumped')
plt.title('Density vs Average Walls Bumped')
plt.show()