Discussing Graph Algorithms: You are playing a game where there is a monster cha
ID: 3770823 • Letter: D
Question
Discussing Graph Algorithms:
You are playing a game where there is a monster chasing you in a maze. The maze has a graph structure, possibly with cycles. Your goal is to escape from the maze before the monster catches you and eats you. You know the following: the maze layout, your location in the maze, and the monster's location. However, the escape door is invisible unless you are right in front of it. You and the monster alternate moves. At each move, the player moving (you or the monster) must move to a node adjacent to the mover's current position in the maze. After getting eaten multiple times, you decide to write a program to figure out your moves. That is, at each step in the game, you will consult your program to decide where to move next. Your strategy won't necessarily guarantee that you escape, but it should greatly improve your chances. Discuss the issues/challenges of this problem, discuss the graph algorithms you might use and why (consider the ones we looked at in class or ones you might create/modify), your general strategy if you have one, and any other details you feel are important. Note, this problem is intentionally left vague. Be creative and thoughtful.Explanation / Answer
A* algorithm can be used:
a) If C is already on the open or closed list, check if the new f is lower than the old value
i) If it is, update the node’s g, h, f and parent values, and propagate the change to reflect a shorter path found through the node C
b) Else insert node C in the open list and populate the g, h, f and parent values
5) Repeat process from step 2 if the open list is not empty Return, no path can be found
Combining the breadth-first nature of the Dijkstra’s algorithm with the heuristic driven best-first method forms the basis for the A* algorithm. The approach to handling the nodes is essentially identical to Dijkstra’s algorithm, and an open list is used to keep track of the frontier nodes, while a closed list maintains the discovered nodes. The main difference is the way weights are calculated, resulting in the frontier not extending equally in all directions, but more toward the goal and less in other directions. The other directions need to be examined in case the promising direction turns out to be a dead end or a detour. The weights associated with the edges are a combination of a heuristic value, the distance travelled so far to that node, and possibly other values which can be used to modify the behavior of the path finder to deal with dynamic objects or other factors. The dynamic modifiers will be discussed in more detail later in the report. Each node keeps track of the following information: g for the distance for the most efficient path found to this node, h for the heuristic value, f is the estimated path length to the goal through that node, which in the base A* algorithm is the sum of g and h, and finally the parent of the node, that is used to be able to backtrack to construct the path once the goal is reached. It is important to note that the cost of travel between two nodes has to be greater than zero in order to avoid infinite loops. As mentioned before, if the A* algorithm encounters an obstacle along the best estimated path, it will expand its search space.
The first segment of the path estimates represents the g value, while the second segment (crossing through the obstacle) is the h value. All the estimated path lengths of the closed nodes is less than or equal to the shortest path length found upon completion. The longer the detour the agent is forced to make, the bigger the flood generated by the algorithm will be. On maze like maps with lot of obstacles and deviations from the straight path towards the goal, the algorithm is forced to examine nearly the same amount of nodes
In each iteration, the node in the open list (which only contains the start node initially) with the lowest f value is selected, and all of its neighbours are checked. If the neighbour node has not been examined in the past, its g, h, f and parent values are populated to reflect where it has been discovered from. If the neighbour is either in the open or closed list, it means it has been previously examined, and the previous f value is compared to the new f value, and if a more efficient path for the neighbour has been found, its g, f and parent values get updated. This change may affect its successor nodes as well. There are two approaches to update the graph to keep it consistent. The passive approach is to reinsert the node back into the open list, and if its weight is low enough it will eventually be examined once again, resulting in its successors to be updated too, if needed. The active update consists of propagating the changes as they occur and placing the node into the closed list. Both methods will yield an optimal result, but active updates require more processing time, but less storage space. When all the neighbours of the best fit node are discovered, it is placed on the closed list and the same process is performed on the next node in the open list with the lowest f value. The algorithm terminates when the goal node is discovered, or the open list runs out of nodes, signifying no path is available.
A* algorithm can be used:
a) If C is already on the open or closed list, check if the new f is lower than the old value
i) If it is, update the node’s g, h, f and parent values, and propagate the change to reflect a shorter path found through the node C
b) Else insert node C in the open list and populate the g, h, f and parent values
5) Repeat process from step 2 if the open list is not empty Return, no path can be found
Combining the breadth-first nature of the Dijkstra’s algorithm with the heuristic driven best-first method forms the basis for the A* algorithm. The approach to handling the nodes is essentially identical to Dijkstra’s algorithm, and an open list is used to keep track of the frontier nodes, while a closed list maintains the discovered nodes. The main difference is the way weights are calculated, resulting in the frontier not extending equally in all directions, but more toward the goal and less in other directions. The other directions need to be examined in case the promising direction turns out to be a dead end or a detour. The weights associated with the edges are a combination of a heuristic value, the distance travelled so far to that node, and possibly other values which can be used to modify the behavior of the path finder to deal with dynamic objects or other factors. The dynamic modifiers will be discussed in more detail later in the report. Each node keeps track of the following information: g for the distance for the most efficient path found to this node, h for the heuristic value, f is the estimated path length to the goal through that node, which in the base A* algorithm is the sum of g and h, and finally the parent of the node, that is used to be able to backtrack to construct the path once the goal is reached. It is important to note that the cost of travel between two nodes has to be greater than zero in order to avoid infinite loops. As mentioned before, if the A* algorithm encounters an obstacle along the best estimated path, it will expand its search space.
The first segment of the path estimates represents the g value, while the second segment (crossing through the obstacle) is the h value. All the estimated path lengths of the closed nodes is less than or equal to the shortest path length found upon completion. The longer the detour the agent is forced to make, the bigger the flood generated by the algorithm will be. On maze like maps with lot of obstacles and deviations from the straight path towards the goal, the algorithm is forced to examine nearly the same amount of nodes
In each iteration, the node in the open list (which only contains the start node initially) with the lowest f value is selected, and all of its neighbours are checked. If the neighbour node has not been examined in the past, its g, h, f and parent values are populated to reflect where it has been discovered from. If the neighbour is either in the open or closed list, it means it has been previously examined, and the previous f value is compared to the new f value, and if a more efficient path for the neighbour has been found, its g, f and parent values get updated. This change may affect its successor nodes as well. There are two approaches to update the graph to keep it consistent. The passive approach is to reinsert the node back into the open list, and if its weight is low enough it will eventually be examined once again, resulting in its successors to be updated too, if needed. The active update consists of propagating the changes as they occur and placing the node into the closed list. Both methods will yield an optimal result, but active updates require more processing time, but less storage space. When all the neighbours of the best fit node are discovered, it is placed on the closed list and the same process is performed on the next node in the open list with the lowest f value. The algorithm terminates when the goal node is discovered, or the open list runs out of nodes, signifying no path is available.