Applying the A* Search Algorithm

Extract

[...] Figure 1 - Map of Task 1 with Traveled Path 3 Task 2 : Finding the Path to Selskapssiden Task 2 involves finding the shortest path from Strossa to Selskapssiden using the same algorithm. The algorithm's behavior is consistent with Task but the starting and destination points differ Results The path was found and is visualized in Figure 2. Figure 2 - Map of Task 2 with Traveled Path 4 Task 3 : Concert Night Path Finding For this task, the objective was to find the least-cost path from Lyche to Klubben for a concert that starts at 21 :00. [...]

[...] closed_set = set() open_dict is a dictionary to help quickly find duplicate nodes and their corresponding g values. open_dict = {start_pos: The starting node is created and added to open_set heapq.heappush(open_set, AStarNode(start_pos, h=heuristic( start_pos, goal_pos))) The loop continues as long as there are nodes in open_set Fetching the Current Node : The node with the smallest f value is fetched from open_set current_node = heapq.heappop(open_set) Goal Check : If the current node is the goal node, the function constructs the path by tracing back from the goal to the start if current_node.pos goal_pos: 2 # Retrace the path return path Closed Set & Open Dictionary Maintenance : The current node is added to closed_set and removed from open_dict. [...]

[...] parent : Parent node in the path. g : The cost to reach this node from the start node. h : The heuristic cost to reach the goal from this node def other): 2 return (self.g + self.h) [...]

[...] G-value Calculation : New g value is calculated for the neighbor based on its type (or cost). Open Dictionary Check : If the node is either not in open_dict or has a smaller g value than before, it is either added or updated in open_set and open_dict Results The path was found and is visualized in Figure 3. Figure 3 - Least-cost path for Task Task 4 : The Cake Party Scenario In this scenario, a cake party at Edgar leads to a crowded room. [...]

[...] The algorithm is a widely-used search algorithm for finding the shortest path in a graph or grid Implementation Here's the program and some explanations : 1 import heapq heapq : A Python standard library for creating and manipulating heaps, which are a type of priority queue . class AStarNode: def __init__(self, pos, parent=None, 3 self.pos = tuple(pos) 4 self.parent = parent 5 self.g = g 6 self.h = h AStarNode : Class to represent nodes on the grid. pos : Position on the grid. [...]