CMSC421 Progamming Assignment 3: Survivor

Only the best learner survives

For this programing assignment, you will implement a basic learning algorithm such as Naive Bayes, Decision Trees or any of the others we will be studying. The project has two components. Your team (1-2 members) will create:

Note: Teams with 2 members must submit two tribe members and 2 learning agents.

Problem Description

After recent turmoil, you have been elevated to the chief of the tribe. Now the survival of the tribe depends upon you. Your tribe consist of tribe members each with different strengths and personalities. The performace of a tribe member on a given task depends upon both external and internal conditions. You have been a given a list of tasks along with the corresponding working conditions. Your job is to choose the most appropriate tribe member for each task so that you maximumize the rewards for the tribe. For your aid, you have been provided the past performance of each tribe member for some tasks under some given conditions.

The Cast of Characters

Each tribe member is described by a probabilistic mapping from attributes to rewards. There are 3 attributes: the task, the tribe mood, and the environment. The challenges the tribe will face will tests their endurance, problem-solving ability, their teamwork, dexterity and will power. In our settings, the tasks are:
  1. shark_race - Swim across shark infested waters. Typically requires a person with speed and endurance.
  2. guess_who - Game where given clues about a person in the tribe, guess who that person is. Requires a really social person with a good memory.
  3. hang_on - Hold on to a branch of a tree for as long as you can. Outlast the opponent and win. Requires someone with endurance.
  4. shoot_for_food - Competition on who can shoot down the most fruit from a tree using a slingshot. Needs someone with good aim.
  5. slug_eating - Eating competition on who can finish off a bowl of slugs first. Needs someone with will power and a strong stomach.


The tribe mood varies, depending on the situation. Here we will NOT have you learn how the mood varies -- as a chief, you can observe the mood of the tribe directly. The different moods the tribe can be in include: jubilant, dejected, hungry, tired, well-rested.

Finally, the tribe can be plunked down in different environments. The different environments are: paradise, swamp, mountain_top, desert.

Rewards are either 100 or -100.

Your tribe member will be described by a text file:
  1. The first line gives the name of the tribe member. You are allowed to use any names (e.g., Cartman, Borat etc.) as long as they are unique.
  2. The next line gives a string that describes the tribe member and will be used when introducing the tribe member.
  3. The third line is equal to the number of lines used to describe the character's behavior.
  4. The character's behavior is described by multiple lines, each of the form
        task-value   mood-value   environment-value   probability-reward=100   string-to-output-if-reward=100   string-to-output-if-reward-is=-100
You can specify 'don't care' attributes with a 'x'. This gives a way of representing the behavior of the agent using a decision list; for a given task, mood and environment, the simulator will find the first matching line. It will then use a random number generator to generate the appropriate reward, according to the probability specified by the agent description. We will provide an character simulator in Lisp which will be able to read in your character and generate behaviors in keeping with your character. Please also look at some example characters provided with the code infrastructure.

Characters which show some thought or creativity are encouraged.

The Learning Agent

This is the core of the project. We will provide skeleton code for both learning and evaluating your agent. Your job is to write an agent which will use training data and learn a model of each tribe member. You also need to implement a method which chooses the best tribe member for each tasks, given the mood of each tribe member and the environment. We provide a simulator which takes in this model and tests the performance on evaluation data.

Code Infrastructure

Copy the code from here to your directory. Read the documentation in the file thoroughly. A couple of notes on the code:
  1. Files: The tar contains two main files, tribe-member.lisp and agent.lisp. We have also provided 4 example characters and a README.
  2. tribe-member.lisp: The file tribe-member.lisp can be used to simulate a tribe member
    1. Variables ALL-TASKS, ALL-ENV-ATTRIBUTES and ALL-MOOD-ATTRIBUTES contain the different values for task, environment and mood respectively.
    2. To load your tribe member, use function load-member which returns an object of class member.
    3. The method do-action for class tribe-member returns the reward and a message for a given set of attributes.
    4. For the class tribe-member, you need to know the accessor functions tribe-member-name which returns name of your tribe member.
    5. To generate training and evaluation data use function generate-data.
  3. Agent.lisp: The file agent.lisp contains a skeleton learning agent implementation
    1. The variable TRIBE contains list of tribe members.
    2. The class model is used to define the learning agent. Please define all the learning parameters within this class.
    3. You need to implement a function choose-tribe-member which returns the best tribe member for given set of attributes. For implementing a random agent, simply uncomment the line within this function.
    4. Also implement the function learn which returns a model learned using some training data.
    5. Function learn-and-evaluate will learn a model using training data and then calculate the total reward on an evaluation set.
    6. Functions example1 and example2 are two examples for evaluating performance of your learning agent on some sample tribe members. Try implementing a random agent as mentioned above and then check their performance using these functions.
  4. Hash: One of the strengths of Lisp is the ease in implementing and using hash-tables. The main functions you need to know for manipulating hash-tables are make-hash-table and gethash.
  5. Mapcar and reduce: List processing is central to Lisp and one way of easily manipulating list is by using functions mapcar and reduce. Mapcar applies a function on each element on the list. Reduce combines elements in a list using an associative binary operation.

Implementation and Discussion

  1. [20 points] Character Define your tribe member using a text file as mentioned before. Discuss your tribe member briefly, making sure to include background details about your tribe member's life which explain what your tribe member's strengths and weaknesses are. The grading depends upon the creativity of your character. It doesn't need to be complex but it cannot be trivial (ie: Someone who always does good or always bad). Note: You are encouraged to create multiple tribe members to help you test your learning agent during the development and for your discussion.
  2. [50 points] Agent
  3. [30 points] Results and Discussion

Deliverables

The deliverables of this pro ject is a single tar file, your-glue-id.tar, containing the following files.
  1. tribe-member.env - Your tribe member definition.
  2. README.txt - A text file containing notes on your environment and anything else you want us to be aware of. Please make sure it contains names of your group.
  3. agent.lisp - Your modified agent.lisp containing your implementation of a learning agent.
  4. README-AGENT.txt - A text file discussing notes on your learning agent. If you are unable to complete this assignment, this file include what you were able to accomplish and what the outstanding bugs are.
  5. DISCUSSION.pdf/DISCUSSION.txt/DISCUSSION.doc - A file containing your experimental results and discussion of the learning algorithm. How did your agent perform on choosing the right tribe members? When did it perform well? When did it perform poorly? How does your agent compare to a random agent?
You must submit using your Grace account using ’submit 2006 fall cmsc 421 0101 3 your-glue-id.tar’ for the first part of the assignment (Characters) and ’submit 2006 fall cmsc 421 0101 4 your-glue-id.tar’ for the second part of the assignment (Agent and Discussions). People working in a group only need to submit once. You must also submit a hardcopy of the discussion at the start of class, Dec. 12.