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()