Problem Formulation 25 pointsCooperative agents: An agent is trying to eat all the food in a maze that contains obstacles, but he now has the help of his friends! An agent cannot occupy a squarethat has an obstacle. There are initially k pieces of food (represented by dots), at positions (f1,...,fk). Thereare also n agents at positions (p1,...,pn). Initially, all agents start at random locations in the maze. Consider a search problem in which all agents move simultaneously;that is, in each step each agent moves into some adjacent position (N, S, E, or W, or STOP). Note that any number of agents may occupy the same position. 1.Give a search formulation to the problem of looking for both gold and diamondin a maze.
2.Knowing that you have M squares in the maze that do not have an obstacle. What is the maximum size of the state space
3.What is the maximum branching factor.
4. For each of the following heuristics, indicate (yes/no) whether or not it is admissible.
h1: The number of dots (representing food) remaining. [ True, False ].
h2(s)=0, where s is a state node. [ True, False ].
h3(s)=1, where s is a state node. [ True, False ].