CSci 4511w: Class Notes

Material will be added to this page during the semester, in particular while a topic is being covered.

General resources on AI and Computer Science

• The AI Topics library from AAAI offers a great collection of pages with information about AI and various subjects within AI. This is an excellent place to visit for people who want to get a good start at any of the subfields within AI.
• You can find pointers to AI material at http://www.c2i.ntu.edu.sg/AI+CI/Overview/index.html.
• The ACM Digital Library has a huge searchable collection of papers. If the link does not work, you can get to it from the UofM library page ACM guide to computing literature IEEE has also a large collection of papers in IEEE Explore.
  To read the papers you have to access them from an on-campus computer or authenticate through the UofM Library Indexes and Database page. Look under A for ACM Digital Library and under I for IEEE Explore.
• Google Scholar is another good source for papers.

Applets and demo programs

• Tools for Learning Computational Intelligence at UBC has applets, including some for Search, CSP problems, and Planning. Check them out.

Intro to AI

• The term Artificial Intelligence was first used in 1955 by John McCarthy in the Proposal for the Dartmouth Summer Research Project on Artificial Intelligence to the Rockfeller Foundation, by John McCarthy, Marvin Minsky, Nathaniel Rochester, and Claude Shannon. The proposal starts like this:
  "We propose that a two-month, ten man study of artificial intelligence be carried out during the summer of 1956 at Dartmouth College in Hanover, New Hampshire. The study is to proceed on the basis of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it. An attempt will be made to find how to make machines use language, form abstractions and concepts, solve kinds of problems now reserved for humans, and improve themselves. We think that a significant advance can be made in one or more of these problems if a carefully selected group of scientists work on it together for a summer. [Additional attendees were Trenchard More, Arthur Samuel, Oliver Selfridge, Ray Solomonoff, Alen Newell, and Herbert Simon.]
• For a short introduction to different meanings of the term artificial read the first pages of "Natural and Artificial Intelligence" by Robert Sokolowski
• Artificial Intelligence is an attempt to prove the Physical-Symbol System Hypothesis (PSSH).
  From Allen Newell and Herbert Simon, Turing Award winners, "Computer Science as Empirical Inquiry: Symbols and Search," Communications of the ACM, March 1976, pp 113-126.
  "A physical symbol system consists of a set of entities, called symbols, which are physical patterns that can occur as components of another type of entity called an expression (or symbol structure). Thus, a symbol structure is composed of a number of instances (or tokens) of symbols related in some physical way (such as one token being next to another). At any instant of time the system will contain a collection of these symbol structures. Besides these structures, the system also contains a collection of processes that operate on expressions to produce other expressions: processes of creation, modification, reproduction and destruction."
  In the paper they state the Physical Symbol System Hypothesis: "A physical symbol system has the necessary and sufficient means for general intelligent action.
  By necessary we mean that any system that exhibits intelligence will prove upon analysis to be a physical symbol system.
  By sufficient we mean that any physical symbol system of sufficient size can be organized further to exhibit general intelligence.
  By general intelligent action we wish to indicate the same scope of intelligence as we see in human action."
• Look at What is Artificial Intelligence?, a paper from John McCarthy.
  For another view, look at What is Artificial Intelligence?, an on-line philosophical introduction to AI by Jack Copeland. The article includes some history of AI, the Turing test, and more. Easy to read.
• The original paper by A. M. Turing, Computing machinery and intelligence. Mind, 59, pp 433-460, 1950. Read how he described the Turing test and more.

Search

• Notes on search algorithms. The description of the algorithms in these notes is taken from J. Pearl, "Heuristics", Addison-Wesley, 1984.
• Examples of how to do depth-first search in Lisp
• Constraint propagation
  • An example from Peter Norvig of how to use constraints to solve Sudoku Puzzles using Python.
  • Do you want to know how many colors you need to color a planar map so that no two adjacent regions (that share more than a common point) do not have the same color? The problem is called the map coloring problem. It is solved by the four color theorem.
• Minimax and alpha-beta pruning
  • An example of alpha-beta pruning. Try to figure out where alpha-beta prunes the search space and why. Example taken from J. Pearl, "Heuristics", Addison-Wesley, 1984.
  • For a nice explanation with animation of alpha-beta pruning go to http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm
• Practical applications of search algorithms
  • A complex search problem: searching for airfares. ITAsoftware is the leader in producing software that is used to search for airfares, schedule, and availability of flights. To get a glimpse at the complexity, think that there are 10,000 paths from San Franscisco to Boston, and for each path about 10,000 ways of pricing the itinerary.
    • For a short description of the problem read Computer Scientists Find Unexpected Depths In Airfare Search Problem, by Sara Robinson of SIAM (Society for Industrial and Applied Mathematics)
    • A much more detailed coverage of the problem and its solution is in Computational Complexity of Air Travel Planning, by Carl de Marken.
    • Carl de Marcken: Inside Orbitz, a short story of how Lisp and other decisions helped solving the problem and obtain a great commercial success.
  • How MapQuest Works

Logic, Resolution, and Knowledge Representation

• Notes on hot to do resolution with propositional calculus and a detailed example of using resolution.
• Notes on how to do unification.
• A detailed example of translating from English to predicate calculus with comments on the scope of quantifiers.
• Try answering these practice questions on resolution. Once you are done, check out the answer to one of the questions.
• The USA, Appellee v. Janet Leslie Cooper Byrnes, Appellant on the Small Bird Act we read in class.
• Ontologies.
  • What is ontology? FAQ from IBM.
  • For a better understanding of ontologies, look at the OpenCyc project. In particular, look at the Cyc 101 Tutorial.
  • For another good example look at the Knowledge Sources of the Unified Medical Language System (UMLS).
  • The Protege ontology editor from Stanford.
• The Semantic Web
  • The Semantic Web Wiki
  • Read Searching the Deep Web", Comm of the ACM, Vol 51, N 10, 2008, pp 14-15. It is a short article on how to do deep web search without having to require semantic web markup.
  • Twine uses RDIF and OWL to help organizing, sharing, and discovering knowledge on the web.

Planning

• Notes on the STRIPS language, assumptions and extensions.
• Try the applet at http://aispace.org/planning/. It lets you use the STRIPS representation for actions and states, and runs a planning algorithm to produce a plan. It works only in the blocks world, but has a nice graphical interface that let's you follow what happens step-by-step while constructing the plan and let's you execute the plan step by step. Very cute!
• A short description and figures for the mutexes used in Graphplan.
• Useful papers on planning:
  1. The paper by D. Weld, "An introduction to least commitment planning", AI Magazine, Winter 1994, pp 27-61 is a well written tutorial on least commitment planning algorithms, and includes detailed examples.
  2. A more recent paper by D. Weld, "Recent Advances in AI Planning", AI Magazine, 1999 (postscript - 50 pages) describes advances in AI planning (it includes Graphplan and SAT planners).
  3. The original paper on Graphplan by Avrim Blum and Merrick Furst "Fast planning through planning graph analysis," Artificial Intelligence, vol 90, pp 281-300, 1997 is available from http://www.cs.cmu.edu/~avrim/graphplan.html, the Graphplan home page.
• To learn about and to use a planner based on SAT, look at http://www.cs.rochester.edu/u/kautz/satplan/index.htm This planner combines graphplan with satplan. On the page you'll find links to papers such as Henry Kautz, David McAllester, and Bart Selman, "Encoding Plans in Propositional Logic", Proc. KR-96.

Machine Learning

• for an overview of decision trees, look at the slides from Tom Mitchell's Machine Learning book.
• try the decision tree applet from the AI Space.

Lisp

The first chapter, second chapter, and the Lisp code of ANSI Common Lisp by Paul Graham are available on the Web.
• Major differences between Lisp and Scheme
• Mapping
• Data Structures: lists, association lists, property lists, structures, arrays and vectors, strings, hash-tables
• Generators
Copyright: © 2008 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.