Assignment 1

Vempati Anurag Sai		Y9645

Ass-1.zip

Results:

Starting point: (3,5) :-

BOT-A BOT-B BOT-C 
Starting point: (3,5)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3  [0.2] 
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 0.2
D 0.2
S 0.4
L 0.4
S 1.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.1   0.7  [0.0]  0.0  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
L 1.2
S 1.9
L 1.9
S 2.0
R 2.0

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.0  [0.0]  0.0   0.0  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
U 2.0
S 2.4
R 2.4
S 2.7
R 2.7

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.0   0.0  [0.0] 
  0.3   0.0   0.0   0.0   0.0  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
U 2.7
S 3.2
L 3.2
S 3.7
D 3.7

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.0   0.0  
  0.3   0.5   0.0  [0.0]  0.0  
  0.3   0.0   0.0   0.0   0.0  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
U 3.7
D 3.7
U 3.7
U 3.7
S 3.8

  0.0   0.5   0.8  [0.0]  0.1  
  0.1   0.0   0.5   0.0   0.0  
  0.3   0.5   0.0   0.0   0.0  
  0.3   0.0   0.0   0.0   0.0  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
R 3.8
S 3.9
D 3.9
L 3.9
U 3.9

Number of moves - 30
Performance - 3.9 
  
Starting point: (3,5)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3  [0.2] 
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 0.2
U 0.2
S 0.7
L 0.7
S 1.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5  [0.0]  0.0  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
L 1.2
S 1.7
U 1.7
S 2.5
L 2.5

  0.0  [0.5]  0.0   0.1   0.1  
  0.1   0.0   0.0   0.0   0.0  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 3.0
D 3.0
D 3.0
S 3.5
R 3.5

  0.0   0.0   0.0   0.1   0.1  
  0.1   0.0   0.0   0.0   0.0  
  0.3   0.0  [0.4]  0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 3.9
D 3.9
S 4.6
R 4.6
S 5.4

  0.0   0.0   0.0   0.1   0.1  
  0.1   0.0   0.0   0.0   0.0  
  0.3   0.0   0.0   0.3   0.0  
  0.3   0.1   0.0  [0.0]  0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
D 5.4
S 6.2
D 6.2
S 6.7
D 6.7

  0.0   0.0   0.0   0.1   0.1  
  0.1   0.0   0.0   0.0   0.0  
  0.3   0.0   0.0   0.3   0.0  
  0.3   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0  [0.5]  0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 7.2
D 7.2
S 7.4
L 7.4
L 7.4

Number of moves - 30
Performance - 7.4
  
Starting point: (3,5)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3  [0.2] 
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 0.2
U 0.2
S 0.7
L 0.7
S 1.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5  [0.0]  0.0  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
L 1.2
S 1.7
U 1.7
S 2.5
L 2.5

  0.0  [0.5]  0.0   0.1   0.1  
  0.1   0.0   0.0   0.0   0.0  
  0.3   0.5   0.4   0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 3.0
L 3.0
D 3.0
S 3.1
D 3.1

  0.0   0.0   0.0   0.1   0.1  
  0.0   0.0   0.0   0.0   0.0  
 [0.3]  0.5   0.4   0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 3.4
R 3.4
S 3.9
R 3.9
S 4.3

  0.0   0.0   0.0   0.1   0.1  
  0.0   0.0   0.0   0.0   0.0  
  0.0   0.0  [0.0]  0.3   0.0  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
D 4.3
S 5.0
R 5.0
S 5.8
D 5.8

  0.0   0.0   0.0   0.1   0.1  
  0.0   0.0   0.0   0.0   0.0  
  0.0   0.0   0.0   0.3   0.0  
  0.3   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2  [0.8]  0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 6.6
D 6.6
S 7.1
D 7.1
S 7.6

Number of moves - 30
Performance - 7.6

Starting point: (7,1) :-

A B C 
Starting point: (7,1)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
 [0.0]  0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
D 0.0
R 0.0
L 0.0
U 0.0
D 0.0

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
 [0.0]  0.0   0.0   0.2   0.0  
 
R 0.0
R 0.0
U 0.0
D 0.0
R 0.0

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0  [0.2]  0.0  
 
S 0.2
L 0.2
R 0.2
L 0.2
U 0.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0  [0.0]  0.5   0.1  
  0.0   0.0   0.0   0.0   0.0  
 
D 0.2
U 0.2
D 0.2
L 0.2
U 0.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0  [0.0]  0.0   0.5   0.1  
  0.0   0.0   0.0   0.0   0.0  
 
U 0.2
U 0.2
D 0.2
L 0.2
R 0.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0  [0.0]  0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.0   0.0  
 
L 0.2
U 0.2
D 0.2
R 0.2
L 0.2

Number of moves - 30
Performance - 0.2
  
Starting point: (7,1)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
 [0.0]  0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
D 0.0
U 0.0
U 0.0
U 0.0
U 0.0

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
 [0.3]  0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 0.3
U 0.3
S 0.6
R 0.6
S 1.1

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.0  [0.0]  0.4   0.3   0.2  
  0.0   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
R 1.1
S 1.5
D 1.5
S 2.2
R 2.2

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.0   0.0   0.0   0.3   0.2  
  0.0   0.1   0.0  [0.8]  0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 3.0
D 3.0
S 3.8
D 3.8
S 4.3

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.0   0.0   0.0   0.3   0.2  
  0.0   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0  [0.0]  0.1  
  0.0   0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
D 4.3
S 4.8
D 4.8
S 5.0
U 5.0

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.0   0.0   0.0   0.3   0.2  
  0.0   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0  [0.0]  0.1  
  0.0   0.0   0.0   0.0   0.0  
 
R 5.0
S 5.1
U 5.1
S 5.2
U 5.2

Number of moves - 30
Performance - 5.2
  
Starting point: (7,1)

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0   0.5   0.1  
 [0.0]  0.0   0.0   0.5   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
R 0.0
R 0.0
R 0.0
S 0.5
U 0.5

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7   0.8   0.2  
  0.0   0.0   0.2   0.8   0.3  
  0.0   0.0   0.0  [0.5]  0.1  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 1.0
U 1.0
S 1.8
U 1.8
S 2.6

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0   0.5   0.5   0.5  
  0.3   0.5   0.4   0.3   0.2  
  0.3   0.1   0.7  [0.0]  0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
L 2.6
S 3.3
U 3.3
S 3.7
U 3.7

  0.0   0.5   0.8   0.1   0.1  
  0.1   0.0  [0.5]  0.5   0.5  
  0.3   0.5   0.0   0.3   0.2  
  0.3   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
S 4.2
U 4.2
S 5.0
L 5.0
S 5.5

  0.0  [0.0]  0.0   0.1   0.1  
  0.1   0.0   0.0   0.5   0.5  
  0.3   0.5   0.0   0.3   0.2  
  0.3   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
R 5.5
R 5.5
S 5.6
D 5.6
S 6.1

  0.0   0.0   0.0   0.0   0.1  
  0.1   0.0   0.0  [0.0]  0.5  
  0.3   0.5   0.0   0.3   0.2  
  0.3   0.1   0.0   0.0   0.2  
  0.0   0.0   0.2   0.0   0.3  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.0   0.1  
  0.0   0.0   0.0   0.2   0.0  
 
R 6.1
S 6.6
D 6.6
S 6.8
L 6.8

Number of moves - 30
Performance - 6.8

Part D:

A. Only in a 2*1 or 1*2 (with equal dirt values in both squares) or 1*1 grid. In bigger grids the bot has a chance of moving back to the same square it has come from. Even in the case of 2*1/1*2 it keeps shuttling after the grid is completely cleaned. Moreover, if only two moves are left, the bot must choose between "suck and move"/ "move and suck" either of which can be a rational solution depending on the relative dirt values. Given that a simple reflex agent has no memory, it is quite possible that it will not choose a perfectly rational solution.

B. No. If more than one neighbouring squares have maximum dirt values, it chooses randomly between them which makes it undeterministic.

C. 

	0   0.5 0.8 0.1 0.1
	0.1 0   0.5 0.5 0.5
	0.3 0.5 0.4 0.3 0.2
	0.3 0   0   0.8 0.2
	0   0   0   0   0.3
	0   0   0   0   0.1
	0   0   0   0   0.1
	0   0   0   0.2 0
In the above environment, if the randomized agent starts at (8,1) it has high chances of remaining in the region of zeros for a long time. Moving in circles can seriously degrade it's performance.

D. We can find a distribution of real data given sensor data from previous readings(huge collection). We can device a probabilistic approach based on that to estimate what could be the actual dirt value given the value we sense.

E. This problem can be overcome by assigning some value of dirt equal to the expected dirt to every location previously visited after each move it makes from then. E(Dirt) = sigma(dirt*N(20,10)).

Part E:

A. We make a prior assumtion that the floor is darker than the walls. Using a particular threshold, we can distinguish between the floor and walls. Edge detectors can be used to detect the boundaries. We also assume the robot is mounted with a sonar to measure distances from the obstacles present "in front" of it.

B. Initially the camera mounted on the bot can be in any arbitrary position. It has to be aligned properly to be able to build 0.5 metre spacing grid. The distance between any two points on the edges seen in the image need not be equal to the real distance between them. We can make use of the fact that two points are farthest when they are viewed from a direction normal to any of the planes containing them. So, we mark two points "in the memory" at random points on the edge between wall and the floor. Now we move the camera and simultaneously track the points in our memory(we can do that because we know distance to that point by sonar readings, which direction the camera is moving and the focal length of the lens). At every instant we measure the distance between the two points. We freeze the camera in the orientation when the two points are farthest. In this orientation, knowing the distance from the wall(sonar reading) and focal length of the lens, we can mark grid with a spacing of 0.5 metre.

C. Instead of a value between 0 and 1, it would be appropriate to use a vector of values between 0 and 1. For example discrete objects(like the orange peel in the Fig-1 below) have to be assigned a value either '0' or '1' indicating their absence and presence respectivcely. Some stains(like those present at the corners of the Fig-1) can't be removed completely. In that case even if they are faintly visible, they can be considerd to be of value '0'. In case of dirt particles(like the powder in the Fig-1), a value between '0' and '1' can be used. Moreover, some dirt particles can be directly sucked while stains have to be "cleaned". So, a vector assigned to each square in the grid seems appropriate with each dimension having it's own meaning.

D. Once the robot is able to draw the grid in it's memory, it can easily get the location of the dirt from the image.

Figure - 1
In this figure two markers are placed at arbitrary positions on the edge. They are sepeerated by a distance of 770 pixels.

Figure - 2
In this figure the same two markers are seperated by a distance of 820 pixels(farthest). The line joining them is seen in it's real length, since we are viewing in a direction normal to one of the planes containing it.