Consider a UAV performing reconnaissance in a 4 4 grid of sectors as depicted in the figure above. The UAV has the ability to fly north, south, west and east with each action moving it by one sector. Each action is successful in its intended direction by a probability of 0.85. Remaining probability is divided equally between the two directions perpendicular to its intended action. The UAV prefers the sectors with a green circle and would like to avoid the red sector. The patterned sector is out of bounds. Write a program in C or C++ that models this problem as a MDP consisting of a tuple of states, actions, transition and reward functions. Assign a reward of +1 to the sectors with a green circle and a cost of 1 to the red sector. All other sectors have a cost of 0.05.

3 \begin{tabular}{|l|l|l|l|} \hline & & & \\ \hline & & & \\ \hline \end{tabular} 0 1 2 3