Imagine a car-like agent wishes to exit 3 maze like the one shown below: The agent is directional and at all times faces some direction d e (N, S, E, W). With a single action, the agent can either move forward at an adjustable velocity v or turn. The turning actions are left and right, which change the agent's direction by 90 degrees. Turning is only permitted when the velocity is zero (and leaves it at zero). The moving actions are fast and slow. Fast increments the velocity by 1 and slow decrements the velocity by 1; in both cases the agent then moves a number of squares equal to its NEW adjusted velocity. Any action that would result in a collision with a wall crashes the agent and is illegal. Any action that would reduce v below 0 or above a maximum speed V_Max, is also illegal. The agent's goal is to find a plan which parks it (stationary)cn the exit square using as few actions (time steps) as possible. Example: if the agent shown were initially stationary, it might first turn to the east using (right), then move one square east using fast, then two more squares e3st using fast again. The agent will of course have to slow to turn. Answer the following questions: a. If the grid is M by N, what is the size of the state space? Justify your answer. You should assume that all configurations are reachable from the start state. b. What is the maximum branching factor of this problem? You may assume that illegal actions are simply not returned by the successor function. Briefly justify your answer. c. is the Manhattan distance from the agent's location to the exit's location admissible? Why or why not? d. State and justify a non-trivial admissible heuristic for this problem which is not the Manhattan distance to the exit. e. If we used an inadmissible heuristic in A* tree search, could it change the completeness of the search? f. If we used an inadmissible heuristic in A* tree search, could it change the optimality of the search? g. Give a general advantage that an inadmissible heuristic might have over an admissible one. Imagine a car-like agent wishes to exit 3 maze like the one shown below: The agent is directional and at all times faces some direction d e (N, S, E, W). With a single action, the agent can either move forward at an adjustable velocity v or turn. The turning actions are left and right, which change the agent's direction by 90 degrees. Turning is only permitted when the velocity is zero (and leaves it at zero). The moving actions are fast and slow. Fast increments the velocity by 1 and slow decrements the velocity by 1; in both cases the agent then moves a number of squares equal to its NEW adjusted velocity. Any action that would result in a collision with a wall crashes the agent and is illegal. Any action that would reduce v below 0 or above a maximum speed V_Max, is also illegal. The agent's goal is to find a plan which parks it (stationary)cn the exit square using as few actions (time steps) as possible. Example: if the agent shown were initially stationary, it might first turn to the east using (right), then move one square east using fast, then two more squares e3st using fast again. The agent will of course have to slow to turn. Answer the following questions: a. If the grid is M by N, what is the size of the state space? Justify your answer. You should assume that all configurations are reachable from the start state. b. What is the maximum branching factor of this problem? You may assume that illegal actions are simply not returned by the successor function. Briefly justify your answer. c. is the Manhattan distance from the agent's location to the exit's location admissible? Why or why not? d. State and justify a non-trivial admissible heuristic for this problem which is not the Manhattan distance to the exit. e. If we used an inadmissible heuristic in A* tree search, could it change the completeness of the search? f. If we used an inadmissible heuristic in A* tree search, could it change the optimality of the search? g. Give a general advantage that an inadmissible heuristic might have over an admissible one
