Project 1 Best-First Search (BestFS) Introduction You will recall the lecture discussion of BestFS. In this project, we will build a bot that will start from the upper-left ring in of a 2D grid of cells containing red path tiles and black wall tiles and attempt to find a quality path to the lower-right ring. You will show the bot as a circle (smaller than a tile but centered on it) in a third color. You will show the bot's path exploration (tile's visited) as smaller dots. You will show the bot move from tile to tile, including backing up due to a dead end. And you will show the bot's current best path tiles in a different color from those paths rejected. The project will be built in Jathp-Lisp running with P5, JS, HTML in a web browser page. Teams We recommend working in a team. Your team may contain up to four members. (We would prefer larger teams.) Pick a four-to-eight-letter name for your team (e.g., "Bozobus"). You can also include digits after the first letter. [For the next project teams, and their names, can be changed.] Grid & Obstacles We will use a 29x37 cell grid (where each cell is 20x20 pixels). The red cells are tiles and the black cells are walls, and your bot can't step off the tile path or off the grid. The starting position is in the upper-left corner tile of the upper-left tiled ring (AKA cell (1,1)). The goal tile is the lower-right tile of the lower-right ring. Junction tiles have 3 or 4 directions in which your bot can choose to move. Corridor tiles have only 2 such directions. In this problem there are no single-tile dead-ends. Bot Your bot will move orthogonally i.e., left-right-up-down) to a neighboring tile, and mark the tile you came from with a best-path dot if it is on your best path so far, or with a backup dot if it is backing up to a prior junction tile in order to try a different direction. Note that you may end up revisiting a tile more than twice. Whenever you encounter a junction, you should continue in the direction indicated by your heuristic function (see below). If there is a tie in H(N) directions, then always take the left-hand direction (ie, keep one the same row and change columns). Thus, no randomness is needed. On each move, you should output the number of tiles in the best-path so far, and the number of moves your bot has taken so far (which adds any backtracking done due to dead-ends). You will need to erase the previous counts (perhaps by "blacking them out, or by redrawing the top row). Your bot should move no faster than 3 moves per second. Each time the bot moves, the previous tile should be adjusted (with a colored dot) to reflect whether the bot was exploring a new tile or backtracking to a previously visited junction. If it is a junction tile with as yet unexplored kids, it's dot should be given yet another color. At all times, there should be a best-path sequence of tiles leading to the bot's location. Heuristic Function Your bot should use the Manhattan (AKA Taxicab) metric as heuristic function H(N), (to be) discussed lecture. Note that this never overestimates the actual required number of bot moves to get to a goal. Therefore, your BestFS with this heuristic is an A* algorithm. Your bot can sample the 4 move directions to see which are onto tiles and then use their row-column coordinates to compute their H(N). Bot Memory Note that your bot "knows" where it is in the grid. For each visited "kid" tile, the bot will need to remember the tile's "mom" tile in order to easily be able to back up. It will also need to remember a list of visited junction tiles, so that it recognizes when it has backed up to one of them. Further, it will need to remember (or re-compute) if a junction "mom" has untried "kid" tiles. Recall, BestFS is basically DFS with only a small change to the OPEN list - rather than using a Stack, we sort Open (the unexpanded kids we've seen) by each kid's heuristic function value. (As mentioned above, we do value tie-breaking in favor of the tile with the same row as its mom.) Thus, the kid with the best H(N) value is at the front of the Open list. (In practice, rather than use an O(N^2) or O(N*LogN) sort, we would use an O(LogN) Heap (AKA Priority Queue), but that is overkill for our small problem.) You can also keep a Closed list to avoid trying to re-explore (not backup to) a previously explored tile, but you could also just check for the tile's dot, if any. Goal Completion Once your bot reaches the goal tile, it should stop. Take an image of its path for the solution section of your project report Project 1 Best-First Search (BestFS) Introduction You will recall the lecture discussion of BestFS. In this project, we will build a bot that will start from the upper-left ring in of a 2D grid of cells containing red path tiles and black wall tiles and attempt to find a quality path to the lower-right ring. You will show the bot as a circle (smaller than a tile but centered on it) in a third color. You will show the bot's path exploration (tile's visited) as smaller dots. You will show the bot move from tile to tile, including backing up due to a dead end. And you will show the bot's current best path tiles in a different color from those paths rejected. The project will be built in Jathp-Lisp running with P5, JS, HTML in a web browser page. Teams We recommend working in a team. Your team may contain up to four members. (We would prefer larger teams.) Pick a four-to-eight-letter name for your team (e.g., "Bozobus"). You can also include digits after the first letter. [For the next project teams, and their names, can be changed.] Grid & Obstacles We will use a 29x37 cell grid (where each cell is 20x20 pixels). The red cells are tiles and the black cells are walls, and your bot can't step off the tile path or off the grid. The starting position is in the upper-left corner tile of the upper-left tiled ring (AKA cell (1,1)). The goal tile is the lower-right tile of the lower-right ring. Junction tiles have 3 or 4 directions in which your bot can choose to move. Corridor tiles have only 2 such directions. In this problem there are no single-tile dead-ends. Bot Your bot will move orthogonally i.e., left-right-up-down) to a neighboring tile, and mark the tile you came from with a best-path dot if it is on your best path so far, or with a backup dot if it is backing up to a prior junction tile in order to try a different direction. Note that you may end up revisiting a tile more than twice. Whenever you encounter a junction, you should continue in the direction indicated by your heuristic function (see below). If there is a tie in H(N) directions, then always take the left-hand direction (ie, keep one the same row and change columns). Thus, no randomness is needed. On each move, you should output the number of tiles in the best-path so far, and the number of moves your bot has taken so far (which adds any backtracking done due to dead-ends). You will need to erase the previous counts (perhaps by "blacking them out, or by redrawing the top row). Your bot should move no faster than 3 moves per second. Each time the bot moves, the previous tile should be adjusted (with a colored dot) to reflect whether the bot was exploring a new tile or backtracking to a previously visited junction. If it is a junction tile with as yet unexplored kids, it's dot should be given yet another color. At all times, there should be a best-path sequence of tiles leading to the bot's location. Heuristic Function Your bot should use the Manhattan (AKA Taxicab) metric as heuristic function H(N), (to be) discussed lecture. Note that this never overestimates the actual required number of bot moves to get to a goal. Therefore, your BestFS with this heuristic is an A* algorithm. Your bot can sample the 4 move directions to see which are onto tiles and then use their row-column coordinates to compute their H(N). Bot Memory Note that your bot "knows" where it is in the grid. For each visited "kid" tile, the bot will need to remember the tile's "mom" tile in order to easily be able to back up. It will also need to remember a list of visited junction tiles, so that it recognizes when it has backed up to one of them. Further, it will need to remember (or re-compute) if a junction "mom" has untried "kid" tiles. Recall, BestFS is basically DFS with only a small change to the OPEN list - rather than using a Stack, we sort Open (the unexpanded kids we've seen) by each kid's heuristic function value. (As mentioned above, we do value tie-breaking in favor of the tile with the same row as its mom.) Thus, the kid with the best H(N) value is at the front of the Open list. (In practice, rather than use an O(N^2) or O(N*LogN) sort, we would use an O(LogN) Heap (AKA Priority Queue), but that is overkill for our small problem.) You can also keep a Closed list to avoid trying to re-explore (not backup to) a previously explored tile, but you could also just check for the tile's dot, if any. Goal Completion Once your bot reaches the goal tile, it should stop. Take an image of its path for the solution section of your project report