1. The environment contains numbers from 1, 2, . . . , n2 −1 and an empty space E (see the diagram below for the case n = 4).
1
2
3
4
5
6
E
7
8
9
10
11
12
13
14
15
Now the empty space E can be moved up, down, left or right (and of course in the corners some of these moves are valid while some others are not). Implement a class which
(a) Can be initialized with a given start state i.e., position of the empty space. [25] (b) Takes the actions up, down, right, left as input and then updates the next state of the
puzzle. [15]
(c) Can display the state at any given time. [10]
Note: This is an example of a dynamic deterministic control task.
2. Consider a road of length 3 kms. The time (in minutes) at which vehicles enter the road, and their preferred speed (m/s) are given in the input file ‘arrival’. Write a program which
(a) Outputs the times (in minutes) at which each vehicle leaves the road. [20] (b) Assume that the local governing body has enforced a rule which states that every vehicle
100
on the road should reduce their preferred speed by a factor of max 0.001, 1 − (n−1) when
there are n vehicles on the road. Under this constraint, output the times (in minutes) at
which each vehicle leaves the road. [10]
Note: The vehicles are allowed to overtake. This is an example of a dynamic event driven system without any control.
3. Consider a top secret defense area modelled in the form of a n × n grid. Each cell in the grid is monitored by a sensor. Sensors that are turned ON can detect the presence of an intruder in their respective grid. Whereas, sensors that are OFF will not be able to detect intruders. Consider a scenario in which an intruder is moving at random from one grid to another grid every minute, i.e., with equal probability to adjacent positions. Also, consider a security agent that switches ON only k out of the n2 sensors (sampled uniformly at random) at every minute. The remaining n2 − k sensors are turned OFF. Given the initial position of the intruder in the
n × n grid, output his location when he is detected by a sensor. [10]
Note: This is an example of partially observable dynamic system with control.
End of paper
