CSci 4511w: Class Notes

Material will be added to this page during the semester, as 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.
• 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

• The book " Artificial Intelligence: Foundations of Computational Agents (2nd Ed.)," by David Poole and Alan Mackworth is full available online.
  The book companion, Tools for Learning Artificial Intelligence, has a number of applets, including some for search, CSP problems, planning, and neural nets. 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.]
• The original paper by A. M. Turing, Computing machinery and intelligence. Mind, 59, pp 433-460, 1950. This is the paper where he described the Turing test and more.
• For a short introduction to different meanings of the term artificial read the first pages of Natural and Artificial Intelligence by Robert Sokolowski.
• 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.
• 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."
• The Knowledge Navigator Video, a video made by Apple in 1987 to show their vision for the future of computer use. The video shows a simulated personal agent which interacts with the user by video chat, with linked databases and integrated multimedia and hypertext. The date on the calendar of the user is September 16, 2011. Apple announced SIRI on October 4, 2011.

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
• Read Genetic algorithms: principles of natural selection applied to computation by Stephanie Forrest, Science, Vol 261, No. 5123, August 1993, pp 872--878, for an introduction to genetic algorithms and to the random key encoding applied to the Traveling Salesman Problem.
• For a nice overview of algorithms for the Traveling Salesman Problem (TSP) look at http://www.seas.gwu.edu/~simhaweb/champalg/tsp/tsp.html
• Minimax and alpha-beta pruning
  • an applet which let's you create your game tree and see pruning step by step is at http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html. You need to specify the children at each level and the final values and you can step through the algorithm step by step. Very nice, try it!
  • For an explanation with step by step description of alpha-beta pruning go to http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm
  • another animation is at http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/
  • a detailed example of alpha-beta pruning with step by step explanations is at http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
  • an excellent step by step explanation of alpha-beta pruning is a Youtube video from Peter Abeel at https://www.youtube.com/watch?v=xBXHtz4Gbdo
  • Try yourself to work out an example of alpha-beta pruning. taken from J. Pearl, "Heuristics", Addison-Wesley, 1984.
• Monte Carlo Tree Search (MCTS) methods
  • Look at an extensive survey of MCTS in games
    Browne, Powley, Whitehouse, Lucas, Cowling, Rohlfshagen, Tavener, Perez, Samothrakis, and Colton A Survey of Monte Carlo Tree Search Methods IEEE Trans on Computational Intelligence and AI in Games, VoL. 4, No. 1, March 2012.
    A shorter paper on using Monte Carlo Tree Search methods
    Krishna Balla and Alan Fern, UCT for Tactical Assault Planning in Real-Time Strategy Games. International Joint Conference on Artificial Intelligence (IJCAI-2009)
  • The AlphaGo full movie is available on YouTube. It is 1 1/2 hour long. The most recent advance is AlphaGo Zero, a program that learned to play Go from scratch. It is described in Mastering the game of Go without human knowledge by David Silver et al, Nature 550, pages 354-359 (19 October 2017).
  • A short story on Libratus, the program from CMU that defeated professional poker players. A longer paper describes some of the methods used.
• Constraint propagation
  • 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) have the same color? The problem is called the map coloring problem. It is solved by the four color theorem.
  • An example from Peter Norvig of how to use constraints to solve Sudoku Puzzles using Python.
  • Labelling edges in drawings of blocks is another example of propagation of constraints, where the constraints are the physically realizable labels for the lines in the drawings. A description of how to use the labels from the catalogue to label a drawing is in Winston's AI textbook at http://courses.csail.mit.edu/6.034f/ai3/ch12.pdf.
  • A short paper comparing Methods for Constraint Propagation.
• Practical applications of search algorithms
  • A complex search problem: searching for airfares. ITAsoftware was the leader in producing software 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 general description look at http://www.itasoftware.com/
  • Carl de Marcken: Inside Orbitz, a short story of how Lisp and other decisions helped solving the problem and obtain a great commercial success.

Logic

• A detailed example of translating from English to predicate calculus with comments on the scope of quantifiers.
• Notes on how to do unification.
• Notes on how to do resolution with propositional calculus and a detailed example of using resolution.
• Try answering these practice questions on logic and resolution. Once you are done, check out the answer to one of the questions.

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!
• Look at Shakey. This is the earliest robotics project at SRI where planning and STRIPS were used. The site has a video and links to all the historical papers.
• A short description of Graphplan mutexes and an example.
• The paper by D. Weld, "Recent Advances in AI Planning", AI Magazine, Vol 20, N 2, 1999 describes advances in AI planning (it includes Graphplan and SAT planners).
• 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.
• The earlier 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, which includes detailed examples.
• 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.

Knowledge Representation

• What is ontology? FAQ from IBM.
• For a better understanding of ontologies, look at the OpenCyc project.
  Read An Introductory Walk through Ontology Development
  Look at the tutorial from Cycorp Foundations of Knowledge Representation in Cyc
• For another good example look at the Knowledge Sources of the Unified Medical Language System (UMLS).
• The Protege ontology editor from Stanford.
• The USA, Appellee v. Janet Leslie Cooper Byrnes, Appellant on the Small Bird Act, which is relevant to ontologies.
• 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.

Neural Networks

• Neural Networks and Deep Learning is a free online book that covers in a gentle but precise way the theory and practice of neural networks and gives a limited introduction to deep learning. Good to build up full understanding of what makes neural nets to work.

Lisp

• Major differences between Lisp and Scheme
• Mapping
• Data Structures: lists, association lists, property lists, structures, arrays and vectors, strings, hash-tables