Assignment 1: Continuum Vacuum World Agent

Parts A, B and C are implementations; parts D and E are written. All parts are to be submitted as a hw1/index.html file in your web area.

Consider the reflex vacuum cleaning environment of fig. 2.2, described on p.64 of the book. Here is a Java implementation of this robot.

You are encouraged to play around with this or some other code to get some idea. there are many other implementations at Russell and Norvig's AIMA home page and at many other sites. feel free to start from anyone else's code, but note that the continuum nature of your sensing will make for important changes in the data structure. if you are using any other code, make sure you cite the code you use in your html page.

Continuum Vacuum World

Consider that geography of the environment is not just two squares but a grid. The agent can go Up and Down as well as L and R. Consider also that the dirtiness of a grid square is not binary but is a continuum; thus the value is between 0 and 1. The objective is to pick up the maximum amount of dirt it can, within some time constraint, which is specified in terms of the number of moves. Your input includes a grid in the text file environ.txt, with a format like: 
    GRID: 8 5
    DIRT: 
        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.1 0.7 0.8 0.2
        0   0   0.2 0.8 0.3
        0   0   0   0.5 0.1
        0   0   0   0.5 0.1
        0   0   0   0.2 0
    MOVES: 30
    INITIAL: 3 5
The grid starts from (1,1) so the robot is initially on the last square of row 3 (value is 0.2).

Note that the performance measure in the book allows a 1000 moves, but we have far fewer moves here. "Suck" (S) empties all the dirt in a square, but constitutes a separate move from R, L, U, D.

You have to implement your robot in any language you see fit, but it must run under Linux.

The input interface must read this text file from the program line: 

    your-userid_Hw1A < environ.txt
At each step it should print out the move it makes and its performance score (e.g. S 0.2). Every N steps, it should print out a grid, with a "[ ]" on the square where the robot is now. Thus, with the above input, if N=5 and the robot has done S U S L S, the output would be: 
    S 0.2
    U 0.2
    S 0.7
    L 0.7
    S 1.2

    0   0.5 0.8 0.1 0.1
    0.1 0   0.5 [0] 0
    0.3 0.5 0.4 0.3 0
    0.3 0.1 0.7 0.8 0.2
    0   0   0.2 0.8 0.3
    0   0   0   0.5 0.1
    0   0   0   0.5 0.1
    0   0   0   0.2 0
Please don't use any other interactions, so we can take a dump of all your output with: 
    your-userid_Hw1A < environ.txt > your-userid_hw1AOut.txt
In fact, if you wish, you can also read this as the input for a GUI for debugging purposes, esp for longer runs.

To-do List

  1. Write a reflex program as in the ordinary vacuumWorld - it has no memory, no state and can only sense the present square. It can sense the value of dirt present in and also if any of the boundary edges are walls.
  2. Consider that your robot can see the four neighbouring squares, and use a greedy algorithm to decide which square to go to. It should move randomly when choices are equal.
  3. Consider that the robot has a knowledge of its grid square (state) and also has a memory (squares visited earlier and their values etc). It can see the four neighbouring squares. Design the best-performing robot.

    Give a table showing how your robots A, B and C perform on the sample grid above, starting at NE: (3 5) and at SW: (7 1).

    All the programs C will be entered in a contest, and will be tested on several new environments, and the best robot will win a prize.

    1. In what environments will a simple reflex agent be perfectly rational?
    2. A robot is deterministic if it always behaves in the same way in the same situation. Is your greedy robot in B deterministic?
    3. Can you design an environment in which a randomized agent will perform poorly?

      Consider how your rational agent would change its behaviour in the following situations:
    4. Assume that it's sensing is noisy, so the observations are inaccurate by at most 20%.
    5. Cleaned squares can become dirty, with the probability of this happening being a gaussian centered at 20 moves, with a s.d. of 10. The amount of dirt is a random number between [0,1].
  5. Borrow someone's digital camera, keep it at a height of about 30 cm (your robot height), and take an image of a corridor with some dirt on it. "Dirt" can be anything - papers, clothes, dirt, cups, etc. With respect to the image you have shot:
    1. How would you determine where the floor lies in the image, and where there are walls etc. state any assumptions of prior knowledge you need to make.
    2. Use a grid size of 0.5m, and indicate how the location of the dirt can be mapped to a grid
    3. Would a value between 0 and 1 be good enough to map the "dirt" in each grid?
    4. Consider how the robot might determine its own position using the image?

Submission

You should submit via a simple index.html file in your web area 
    home.iitk.ac.in/~userid/cs365/hw1/
Please link all code, images, etc from this file itself.

Deadline: Friday 13 January, midnight. Please ensure all your results are there by this time, but do not upload the actual code here till 14th morning.