You now control 3 pair of long lost bug friends. You know the maze, but you do n

Question

You now control 3 pair of long lost bug friends. You know the maze, but you do not have any information about which square each bug starts in. You want to help the bugs reunite. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, both bugs will be on the S3me square, regardless of their initial positions. Any square will do, 3S the bugs have no goal in mind other than to see each other once again. Both bugs execute the actions mindlessly and do not know whether their moves succeed; if they use an action which would move them in a blocked direction, they will stay where they are. Unlike the flea in the previous question, bugs cannot jump onto walls. Both bugs can move in each time step. Every time step that passes has a cost of one. You now control a single flea as shown in the maze above, which must reach a designated target location X. However, in addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, b3ck into the maze. Jumping onto the wall has 3 cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares (either north, south, west, or east of the flea).

Explanation / Answer

a) Long Lost Bug Friend :
i) state space description- The state is a list of boolean variables, one for each position in the maze, which marks whether the position could contain a bug. There is no need to separately keep track of the bugs since their starting positions are not known; to ensure they meet only a single square must be possible for both.

ii) state space size- The size is 2MN since every of the M × N possible maze positions must be considered and every position has a boolean variable. A full state is the product of the individual position states, which are binary valued for the base of 2.

iii)Heuristic- hfriends= the maximum Manhattan distance of all possible pairs of points the bugs can be in. This is never an overestimate because the number of steps to join the insects with certainty is at least the shortest path (with no obstacles) between their farthest possible locations from one another. Remember that the starting locations are unknown so the bugs cannot simply be controlled to move toward each other.

b) The Flea :

i) state representation- The state is the location of the flea as an (x, y) coordinate. The map is known, including walls and the goal, and the actions of the flea depend only on its location.

ii) space size- The state space is M × N. The flea can occupy any free location in a given maze, and any square might be free or a wall in a maze, so any of the M × N locations are possible.

iii) Heuristic- hflea = the Manhattan distance from the flea to the goal. It is yielded by the relaxed problem where the flea passes through walls. It never overestimates because 1. a wall can never decrease the length of a path to the goal and 2. the cost of the flea jumping up a wall (2) is higher than the cost of moving.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.