91.420 / 91.543 - Artificial Intelligence (Martin)

Chapter: 00 - Introduction to AI

00 - 3 Analyzing an Agent

Building on the agent-centric model of AI developed by Russell and Norvig, think of a real-world, in-practice application of AI that you're personally interested in. 

Describe the agent and its environment in enough detail that a reader can understand it. 

Then, analyze the environment within which the agent performs, according to the “properties of task environments” framework of Section 2.3.2:
  • fully observable or partially observable?
  • single agent or multi-agent (and the relationship among agents, if multi-agent)?
  • deterministic or stochastic?
  • episodic or sequential?
  • static or dynamic?
  • discrete or continuous?
  • known or unknown?
Then, from the list of agent types in Section 2.4, indicate which of the agent variants is mostly likely involved in its implementation, and argue why you think this is the case. (Russell and Norvig's agents are: simple reflex agents, model-based reflex agents, goal-based agents, utility-based agents, and learning agents.)

For example, one could argue that the original model Roomba vacuum cleaner is a simple reflex agent. (Now you can't pick this for your example.)

Write ~300 words on this, including both your explanation of the AI system and your justification for why it's likely to be whichever agent you select.

Turn in the essay in class on a single sheet of paper. Do not electronically submit.

Also, request to join the class Google Group (at groups.google.com/group/uml-ai-fall14), and the bottom of the page, include the statement “I have requested membership in the course Google group.

Make sure your name and the email address you used to register on Bottlenose is on the page.

00 - 2 Introduction to Python

Course projects are done in Python, so it is necessary for you to learn Python.

Fortunately, the first assignment will help you do this.

This assignment also introduces you to the UMass Lowell Computer Science department's “Bottlenose” auto-grader.

Please read through the Python tutorial at
http://ai.berkeley.edu/tutorial.html.

Then complete the three Questions by modifying the starter code. Berkeley's tutorial.zip code should be obtained here in the Assignment file.

Notice that here it is a gzipped Unix tar archive, so you must have the Unix tar utility to unarchive (and also to re-archive when you wish to submit files.)

Assuming you are working from Unix, you may unpack the archive with the command

tar xzvf ps0-assignment.tgz

After you unpack the tar file, you will have a bunch of files in a directory named "ps0". Edit those files in place in that directory. Do not rename the directory.

When your code successfully passes the local tests (type "python autograder.py"), you are ready to submit here.

To do that, navigate to the directory that contains the "ps0" directory. 

Then type the following Unix command:

tar czvf yourfile.tgz ps0

This will create a gzipped archive named "yourfile.tgz" which has the directory ps0 and all the files within ps0.

Then, submit the "yourfile.tgz". (You may name this file anything you like, but please provide the tgz suffix.)

The critical thing is that your submission must contain a set of files within a directory named ps0.

Assignment Download: ps0-assignment.tgz

00 - 1 Foundations of AI

In chapter 1, Russell and Norvig introduce the “rational agent” design for AI systems.

This is followed by a discussion of eight foundational disciplines of AI:
  1. philosophy
  2. mathematics
  3. economics
  4. neuroscience
  5. psychology
  6. computer engineering
  7. control theory and cybernetics
  8. linguistics
Of these disciplines, which is the most appealing to you, and why?

(In case it isn't evident, there is no right answer; I am interested in your personal motivations.)

Explain in an essay of 250 to 300 words.

Turn in the essay in class on a single sheet of paper. Do not electronically submit.

Make sure your name and the email address you used to register on Bottlenose is on the page.

Chapter: 01 - Search

01 - Full Search Implementation

Complete the entire Berkeley search problem set.

A sample implementation for the Node class was provided in class.

Assignment Download: ps1-full.tar.gz

01 - 4 Formulating a Board Game into a Search Problem

Based on the in-class discussion, analyze a children’s game or puzzle that is amenable to solving by a search process.

Good examples of this are Rubik's Cube, peg solitaire games (such as the Cracker Barrel peg-jump game), and other one player board gamesPlease don't do Rush Hour, because we discussed it in class.

Play with the game for a while to make sure you understand it, and then write up a description, defining the following aspects of the game:

  1. Initial state. Does the game have only one initial state? Does it have multiple possible initial states?
  2. Set of actions. Are these a function of the current state? Explain how.
  3. Transition model. Given a particular state and the set of possible actions for this state, is the transition to a new state deterministic? Explain.
  4. Goal test. Is there a definite end state? Can you tell if you won or lost and the game is over?
  5. Step cost. Do different actions have different costs? Or are all actions equal in cost, and you can model any move with a cost of 1?

If your chosen game isn't exactly something that fits the search model, try to modify its rules so that it does. Remember the definition of a search problem: an observable environment (agent knows its initial state), movement between discrete states, an a priori known environment, and a deterministic transition model.

Write about a 500-word narrative for your chosen game. 

01 - Depth First Search

Please complete the implementation of Question 1, Depth First Search, as described in the Berkeley search page, at http://ai.berkeley.edu/search.html.

Download the starter code from this page, not from the Berkeley page. This starter code is in a directory named "ps1", and is configured to only test the DFS.

Remember, you only have to do the DFS for this assignment.

Make sure to tar/gzip up the whole ps1 directory with your changes when you submit.

Assignment Download: ps1-assignment.tar.gz

Chapter: 02 - Multiagent Search

02 - Multiagent Search

Complete the Multiagent Search problem set at http://ai.berkeley.edu/multiagent.html

Assignment Download: ps2-assignment.tar.gz

Chapter: 03 - Reinforcement Learning

03b - Q-Learning, epsilon-greedy, &c.

Do Questions 4 thru 8 in the Berkeley reinforcement learning problem set, http://ai.berkeley.edu/reinforcement.html.

Assignment Download: ps3b-assignment.tar.gz

03a - Value Iteration, Bridge Crossing, and Policies

Do the first three questions in the Berkeley reinforcement learning problem set, http://ai.berkeley.edu/reinforcement.html.

Assignment Download: ps3a-assignment.tar.gz

Chapter: Conference Paper Review

Conference Paper Review

Choose two of these three papers to read. You will then write a review for both papers.

Ermon, S., Conrad, J., Gomes, C., and Selman, B. (2010). Playing games against nature: optimal policies for renewable resource allocation. P. Grünwald and P. Spirtes (Editors). Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (UAI2010), AUAI Press. ISBN 978-0-9749039-6-5. pdf

Reddy, P. P., & Veloso, M. M. (2011, April). Learned behaviors of multiple autonomous agents in smart grid markets. In AAAI Conf. on Artificial Intelligence (AAAI-11)pdf

Quinn, J. A., Leyton-Brown, K., & Mwebaze, E. (2011, April). Modeling and Monitoring Crop Disease in Developing Countries. In Twenty-Fifth AAAI Conference on Artificial Intelligence. pdf

The Assignment

Write a review for each of the two papers.

The review should contain the following sections:

Total length should be ~500 words per review.

To Find Papers (for future reference)

Use Google Scholar search (http://scholar.google.com) and/or ACM Digital Library search (http://dl.acm.org or http://dl.acm.org.libproxy.uml.edu if off-campus).

IEEE Xplore is another great source for papers in AI — http://ieeexplore.ieee.org/Xplore/guesthome.jsp. Try http://ieeexplore.ieee.org.libproxy.uml.edu/Xplore/guesthome.jsp if you are off-campus.

To Cite Papers

Use what's called APA style—American Psychological Association citation style. This has authors listed last name, first initial as shown above. You can get Google Scholar to show you a reference in APA format by finding it there and then clicking on the “cite” link.

In your review, make sure to include an APA format citation for each of the two articles using the format above.

When You Write a Whole Article

This information is for later.

At the end of your paper, you should have a section labeled References that includes a cited papers in alphabetical order by first author's last name.

In the body of your paper, refer to a paper by first author's last name and year, in parentheses. E.g., if you were citing the first paper above, you might write something like

Researchers have used AI techniques to develop optimal policies for harvesting fisheries while preserving the fish stock (Ermon et al., 2010).

When there are three or more authors, use et al. (which means literally “and others,” and make sure to italicize and put the period after “al.” because it's an abbreviation for “alii").

If there are two authors, use both last names and an ampersand & in the reference; e.g., (Foo & Bar, 2012).

To Turn It In

Submit exactly one PDF file with both reviews in it.


Name the file with your real name plus "_cpr"; e.g., "fred_martin_cpr.pdf".


Upload the review PDF to Bottlenose.

Things to Avoid

Please note these common mistakes and avoid them (thanks to Christine Alvarado).

(Thanks to Christine Alvarado for assignment structure and Manuela Veloso for reading list.)

Chapter: Final Project

08 - Final Code Turn-In

You may collaborate on getting the shared material together, but the narrative explanation of how things work, and what you yourself did, must be done by each person.


Each person must submit the project code and narrative to get credit for the work.


After the project is complete, get all of the source files together.

The README.txt file should be in plain-text format. It should be anywhere from 100 to 500 lines long depending on how much there is to talk about.

Submit here by uploading the .tar.gz or .zip file.


06 - Project Web Page

In this assignment, you will document your final project. This will be done on the class wiki site using a provided template.

There will be one page per project.

Each partner will separately turn in your code using Bottlenose.

Project Web Page

Below is the wiki markup you should use as a template for your writeup. To use it, do the following:

  1. Download the starter wiki markup as a text file. Open it and copy it to your clipboard.
  2. Go to the Project page, and click edit. Enter the edit password posted to the newsgroup.
  3. Add your project title as a wiki link, and your name to the bottom of this page per the directions there. Select a presentation slot based on the instructions in the page.
  4. Save the page.
  5. Click on the newly-created link to your project writeup.
  6. At that page, click edit.
  7. Paste the wiki markup-text into your project writeup page, and Save.

You now have the framework for documentation your project. You can re-edit your page as often as you like. Follow the directions in the template for uploading your images.

Nothing gets submitted to Bottlenose.

EVERYTHING IS DUE AT 8 AM ON MONDAY DECEMBER 8!

05 - Second Deliverable

Please turn in work that has been completed by this date.

Please prepare a brief discussion of what's been accomplished and what the next steps are.

Make sure to explain what you particularly have done.

Please include in your submission:
  • What you said would be accomplished at this point from your proposal.
  • Code that is written (even if it's not working) — links to code on repositories are fine.
  • Any diagrams or notes that you've made.
  • An index to each submitted item (or logical group of submitted items) -- just one sentence.
This should not take too long. Please don't spend more than 20 to 30 minutes getting your work together.

Important notes:
  • Each member of a team is expected to submit a report.
  • It is better to submit something on time than wait for more later. Just tell me where you are when this assignment is due.

07 - Project Writeup

You will prepare a conference-style paper, written using the SIGCHI format. Templates in Microsoft Word, LaTeX, and Apple Pages are available here. Use the “HCI Archive Format.”

Please remove the two lines of text from the copyright block: “CHI 2009, April 4–9, 2009, Boston, Massachusetts, USA. Copyright 2009 ACM 978-1-60558-246-7/09/04...$5.00.”

You can and should use your flyer write-ups as a starting point for your paper. (In a few cases, the flyer write-up is a good start on a paper already.) In general, you should re-use all of your previous work (including the proposal) as is appropriate given how your project actually took shape.

Here are specific guidelines about what the paper should include.

E.g., it does not suffice to say “A* search was used in the implementation.” You must be specific about how it was used, what was the heuristic function, and so on.
  • The ANALYSIS OF RESULTS section should present conclusions. How do you know that your thing worked? E.g, an A* search, was it successful? How many nodes did it expand? Each of you should have some metric of success based on our earlier conversations—present the metric and how well you did against it here.
  • The DISCUSSION section is more free form. Generally, I'd like to know what you learned about the problem here. Focus on your own experience with the problem—don't worry if you learned something that others might already know. The goal of this project was not for you to make an original contribution to knowledge (of course that would be nice if it happened, but that was not the expectation). Instead, the goal was for you to learn something about the problem domain in which you worked, and how AI applies to it. So, focus on your own learning: what you discovered; what was surprising.
  • In the CONCLUSION, summarize your results and give any forward pointers to new work.
  • Include an ACKNOWLEDGMENTS section. Please include the following statement:
The work described in this paper was conducted as part of a Fall 2014 Artificial Intelligence course, taught in the Computer Science department of the University of Massachusetts Lowell by Prof. Fred Martin.
You may additionally mentioning anyone who helped you or otherwise encouraged you.
Please note that in the U.S. English spelling, “Acknowledgments” does not have an “e” between the g and the m.
Finally, if you have no other content in your Acknowledgments section than the statement above, please change the heading to ACKNOWLEDGMENT (because there is only one of them).
  • In the REFERENCES section, include citations for any work that you used in the creation of your project.
As previously stated, you are not held to the standard of creating something wholly new, so don't worry if you don't have a great story for “extending” prior work. Building a relationship to existing work is adequate.
You should have three to five citations. Copy the citation format in the SIGCHI template. You must discuss and reference the citations in the paper. You can't just list stuff in the References section—everything there must be discussed in the body of the paper.

Teams

To Submit

To turn in the paper:

    '''Fred Martin''' \\
     December 9, 2014

    Attach:martin_a_sample_project.pdf

01 - Team or Interest Declaration

In this assignment, you are to either form your team, or declare your interests.


If you have a team:

In order to form your team, you must have:
  • a teammate
  • a project concept
  • a project title (10 words or fewer)
  • who will do what (approximately)
Then, you and your teammate should jointly fill out this form: https://docs.google.com/forms/d/1eNgtwRHTHtmNgP7KTVMnrXqL2pscPMt6vaaAhwZvoCk/viewform

If you don't have a team:

Then you should individually fill out the following form, which will ask you for:
  • your name
  • your contact details
  • what project ideas you're interested in
  • when you're available for team meetings
This info will be available to the class.

Fill out this form: https://docs.google.com/forms/d/1wtpbyY8xisZACywcYtvzFm7LxlxSzPWf1Jc6OHhgsWI/viewform

03 - Final Project Proposal

Here you will describe your actual final project.

Each team member must submit a separate proposal.

You will also jointly prepare a 2- to 3-slide presentation.

On your submission, provide your name first, and your partner's name second.

The two partners' submissions may be the same, except for the section Work Plan / Schedule, where "What I will do" and "What my partner will do" should be reversed in the two submissions.

Below is a detailed description of the proposal document.

To submit, upload a PDF only with your real name + "_fpp" as the root filename.


The Proposal

The proposal itself is a written document that explains what you are going to do. It should have the following section:

  • Project title. No more than ten words.
  • Problem statement. What is the problem and why is it interesting?
  • Problem analysis. Explain what AI theory you will bring to bear on the problem. Be explicit. You should present a logical and technical argument. You may assume the reader is already aware of the relevant theory, but explain how that theory is applied to solve your problem.
  • Data set. What data set will you use as the basis for the analysis? Where will you get the data (e.g., will you download it from a web site, will you create it via a simulation that you build, etc.)? How will you convert it into a form that is usable for your project? Do your homework here: if you are pulling a data set off the web, actually download it and look at it. Explain in some detail your plan for accomplishing the necessary data processing.
  • Deliverable and Demonstration. What exactly will you produce by the end of the project? Of course, there will be a piece of software, but what will it do? Is it a batch-mode kind of thing, and you will present some analytical results? If so, how would your program be re-run on different source data? Or, will your program be interactive, and you can show it at work? There will be a demonstration, so interactive/live programs will be good. Explain exactly what you'll have at the end.
  • Evaluation of results. How will you know if you are successful? This should include some kind of quantitative performance analysis.
  • Work Plan/Schedule. Explain how you will go from proposal to finished product. Explicitly define three deliverables, due on Mon 11/24 (first deliverable), Mon 12/1 (second deliverable), and Mon 12/8 (final project). The nature of the deliverables are project-dependent, but they could include things like processed data ready for import into your program, core implementation of the algorithm, and design of interface/presentation side of the project. You will be expected to turn in code/documentation/data (as appropriate) at each of the three stages, so put concrete steps into your schedule. Include two columns – "What I will do" and "What my partner will do."
  • Broader impacts. Why is this problem worth solving? Who will care about the solution? What impact on research, society, or business will the work have?

In short: You should be proposing something that you have high confidence that you can achieve, and the proposal should project that confidence.

The proposal should be no longer than necessary, but long enough to include critical detail. Three to five pages is appropriate. Diagrams are welcome.

In-Class Presentation

Create a two- to three-slide presentation of your idea which you will present in class on the same day that the written proposal is due.

You will have two minutes.

Add your material to this: AI Final Projects Fall 2014 slide deck

04 - First Deliverable

Please turn in work that has been completed by this date.

Please prepare a brief discussion of what's been accomplished and what the next steps are.

Make sure to explain what you particularly have done.

Please include in your submission:
  • What you said would be accomplished at this point from your proposal.
  • Code that is written (even if it's not working) — links to code on repositories are fine.
  • Any diagrams or notes that you've made.
  • An index to each submitted item (or logical group of submitted items) -- just one sentence.
This should not take too long. Please don't spend more than 20 to 30 minutes getting your work together.

Important notes:
  • Each member of a team is expected to submit a report.
  • It is better to submit something on time than wait for more later. Just tell me where you are when this assignment is due.

02 - Final Project Pitch #1

Prepare Final Project Idea Pitch #1.


This is a 1-page project summary of an idea that you would consider turning into a final project.

Just because you propose something now does not imply that you are obligated to produce it later.

On the other hand, I expect that each pitch be a plausible idea.

For this, select an idea that is amenable to solution through the use of a Markov Decision Process (MDP).

You may wish to review the properties of task environments suitable for modeling with MDPs, namely:

So, think of a project that could be addressed via a Markov model, and propose a project.

The one-page summary should have the following components:

All of this must fit on one page, using 1" margins and a typeface no smaller than 11-pt. 

Submit it as a PDF file only to Bottlenose (i.e., here). 

Make sure the file name includes your real name.

Notes:

Chapter: Exams

Exam 2


Exam 1


Chapter: 04 - Hidden Markov Models (Ghostbusters)

04a - Exact Inference

Complete Questions 1 through 3 from the Berkeley Ghostbusters problem set.

Assignment Download: ps4a-assignment.tar.gz