Given the search space on fig. $1,$ where $S$ is the initial state and $G1$ and $G2$ satisfy the goal test. Question $1($points: UG $[21]/$ G $[15])$: For IDA$*$ search of state space given on fig. $1$ answer

the following questions

$[5$pts$/3$pts$]$ The heuristic is admissible. Is it consistent?

$[5$pts$/4$pts$]$ What states will be expanded during the first iteration of IDA$*$ and in what

order?

$[6$pts$/5$pts$]$ What is the value of expansion limit on the second iteration of IDA$*$

$[5$pts$/3$pts$]$ Which goal will be discovered $($i$.$e$.$ expanded$)?$ what is the contents of the frontier

at the time when goal is discovered? $1$ ALWAYS TRUE, NEVER TRUE or SOMETIMES TRUE

Each question is $7$ UG points$/5$ G points. You are not required to give explanation$/$intermediate

steps in this section, but if you are unsure of your answer, you can do so to get partial credit.

In $A^{*}$ with admissible heuristic, when a node with a goal state is expanded, AT NT STT

we have reached this state via the shortest possible path

Simulated Annealing doesn't make 'bad' moves $($i$.$e$.$ decreasing goal function$)$ AT NT STT

unless at a local extremum.

If a state space is a finite tree then given an initial state and a set

of goals, DFS and BFS return the same goals $($possibly none$)$

If a state space is a finite directed acyclic graph $($DAG$)$ and if the heuristic

is admissible, then at time of node expansion by $A^{*}$ it has already found

an optimal path to the state of the nodeFor Graduate Students

Question $[20$ points$]$: Generalize pacman game: There are initially $k$ dots, at positions $(f_1,dots{f}_k)$

on an $rc$ board. There are also $n$ pac$-$people; initially, all the pac$-$people start in the bottom left

corner of the maze. Consider a search problem in which all pac$-$people move simultaneously; that

is$,$ in each step each pac$-$person moves into some adjacent position $(N,S,E,$ or W$).$ Note that any

number of Pac$-$People may occupy the same position.

$[8$pts$]$ Define states in the state space $($use tuple$-$of$-$formal$-$variables representation$).$

$[5$pts$]$ Give a reasonable upper bound on the number of states in the state space

$[7$pts$]$ What is the maximum branching factor of the successor function?

Figure $1$: State space for search problems

Arcs are labeled with the cost of traversing them $($so lower is better$)$ and the estimated cost to a

goal $($i$.$e$.$ value of heuristic function$)$ is reported inside nodes.