ASU CSE574: Planning and Learning (Fall 2014)

Introduction

Artificial Intelligence or AI is the broad research field that studies intelligence with the ultimate goal to build intelligent entities. In our modern world, intelligent entities are pervasive. We have all interacted with computer games which are fun only if the opponents are intelligent enough. Expert systems, autonomous cars, virtual personal assistants, spam filtering and more have only become possible due to progress in AI. However, more research is needed and new challenges need to be overcome before, for example, we have fully autonomous service robots running our chores.

(Automated) Planning is the deliberation process of computationally choosing actions and anticipating the outcomes of these actions in order to achieve a goal. Planning may have to be performed in unknown, uncertain or partially observable environments. Moreover, the environment may be antagonistic trying to prevent the autonomous entity from achieving its goals. When the outcomes of the actions are unknown or uncertain a learning process may be required in order to facilitate planning.

This is a seminar-level course that builds the mathematical foundations for students to work on planning. Among the course goals is the development of the vocabulary and mathematical background so the students can follow the related cutting edge research literature. The course also emphasizes rigorous thinking and mathematical analysis. Before registering for the course please make sure that you feel comfortable with the level of mathematical presentation in the textbook "Automated Planning" (book website; note that we have on-line access through ASU library).


What this course is not about: This course does not cover machine learning, computer vision, natural language processing, gaming and human-machine interaction. The course only partially touches upon some topics that relate to robotics. Actually, ASU offers a variety of courses that cover all the aforementioned topics in detail and you are advised to take these courses as well.


Disclaimer


This is a live web-page so please check it frequently. Moreover, the course is currently under development. Therefore, it is recommended only to adventurous students who can excel within non-fully structured environments. On the other hand, the students who take the class will be introduced to advanced concepts planning.



Logistics

  • Class: Monday and Wednesday 07:30am-8:45am, BYENG M1-09 
  • Instructor: Georgios Fainekos (email me at fainekos at asu)
  • Office hours: By appointment or check my scheduled office hours on my calendar.
  • Office: Centerpoint 203-17
  • Teaching assistant: None. 
  • Announcements will only be posted on blackboard.

Prerequisites


You must have taken a course on probability theory, logic, automata and algorithms (or at least data structures).
 It is assumed that you have some knowledge on algorithmic complexity and decidability/undecidability.

Textbooks & Readings

We will closely follow the textbook by Ghallab et al. Some chapters will be covered from the Baier and Katoen textbook. Furthermore, research papers will be recommended for cutting edge research topics. Note many of the books listed below are available on-line. You cannot use university printers to print the on-line textbooks.
  • Recommended textbooks (in order of utilization): 
  • Additional References (in order of relevance):
    • [GB] Geffner and Bonet, "A Concise Introduction to Models and Methods for Automated Planning", Morgan & Claypool, 2013
    • [RN]  Russell and Norvig, "Artificial intelligence: a modern approach", 3rd edition, Prentice Hall, 2010
      • Textbook website with additional material, e.g., access to appendices, code, etc.
      • The ASU library has only older printed editions
    • [L] S. M. LaValle, "Planning algorithms", Cambridge University Press, 2006.
    • [ZK] Zimmermann and Klein, "Infinite Games", Lecture notes (on-line)
    • [T] Tabuada, "Verification and control of hybrid systems: a symbolic approach", Springer-Verlag 2009
      • We will use the chapter on games (Ch 6 Control) and potential the chapter on similarity relations on state-transition systems (Ch 4 Exact system relationships)
      • ASU on-line access to the book
    • [SB] Sutton and Barto, "Reinforcement Learning: An Introduction", The MIT Press, 1998 
    • [CLHKBKT] H. Choset et. al., "Principles of Robot Motion: Theory, Algorithms, and Implementations", MIT Press, 2005. 
    • [TBF] Thrun, Burgard and Fox, "Probabilistic Robotics", The MIT Press, 2005
    • [CL] Cassandras and Lafortune, "Introduction to Discrete Event Systems", Springer 2007

Grading

Grades will be based on:

  • The following grading scheme will be used for the in class section: 
    1. 3-6 homeworks 40% 
      • You may form discussion groups for the HW problems of up to 3 members. However, the HW submission will be individual and you must mention the members of the discussion group on your submission. You can join a HW group on Blackboard. The HW groups are not monitored.
      • No homework assignments will be accepted after the due date/time!
    2. Class project 40%
      • See below for details
    3. Cutting edge literature review and presentation 20%
      • See below for details
    4. Class participation
      • If you are within 1%-2% point of moving to a higher letter grade, then class participation can help you. 
      • Class participation consists of:
        • Finding typos, bugs, etc in the book, slides, lecture notes, homework problems etc
        • Answering questions (correctly) in the class
        • Answering questions (correctly) on the discussion board
        • Active discussion in class on the lecture material
      • Class participation is not an one time contribution. It must be continuing activity throughout the semester.
  • Grading scale:

A+

>100%

B-

[75-80)%

A

[95-100]%

C+

[70-75)%

A-

[90-95)%

C

[65-70)%

B+

[85-90)%

D

[55-65)%

B

[80-85)%

F

<55%


Note: The above might still change depending on the number of students and the available resources. For example, it is possible that a lab component might be introduced, if resources become available.

Project description

A perfect project will be graded 100pt. An exceptional project, i.e., new results that can lead to publication, will receive grade more than 100pt. The project option can be used by MCS students for their project portfolio. No group projects will be allowed unless you provide a detailed work plan for each group member and I approve it.

Project ideas:

  • Choose a problem that you are interested in and try to model it using an existing planning tool.
  • Modeling/Simulation/Analysis of algorithms we covered in class or more advanced follow-up work from a conference.
  • Implementing some of the algorithms we did in class on a real robot (either in my lab or with your own equipment).
  • A theoretical problem which could lead to publication
    • Please schedule a meeting with me if you are interested in a project along these lines
  • Something related to your own research/work
    • This must not be previously published work of yours (this is going to be automatically verified) or unpublished on-going research effort (this is going to be checked with your research adviser).
  • Literature review from recent (this year and going back up to 3 years) related conferences.
    • Most related: ICAPSSoCS
    • Alternative options: AAAI, IJCAIICRAIROS (but you need to choose carefully so that you are within the context of our course)
    • For the literature review you will have to select 2-5 papers, summarize them and then compare the advantages and disadvantages of each approach. 
    • If the papers are experimental, then 
      • Two papers are allowed if the algorithms are complex and no software tools have been made available by the authors.
      • Three papers are allowed if the software tools are available. The comparison should be performed on the same benchmarks.
      • Five papers are needed if the comparison is going to be on the results published by the authors.
    • Warning: Simply copying or permutating the text of the original papers is not acceptable and it will be considered plagiarism! Plagiarism is considered cheating by the university and the procedures stated in the university policy will be followed.
  • If you have no exciting problems that you would like to solve, then you can try one of the following:

Remarks:

  • If your project involves implementation (simulation or a physical system), then the final product must be a working one.
  • If you decide to work on the something related to your own research, then you must demonstrate that this is something new that you have not be looking at. I will not accept projects which are just a rewriting of you prior or current research work.   

Project deliverables:

  • 1-2 page project proposal (due date posted on schedule). The proposal should include the following:
    • Proposal template
    • Introduction to general topic area that you are going to look into with a few bibliographic references on the background.
    • A precise problem description which also indicates which aspects of the course are relevant / will be used to solve the problem. Recall that that you need to demonstrate that at least 2 modules from the course will be relevant to your project.
    • An outline of what you plan to do to solve the problem and a schedule with the expected milestones. This section does not have to be very detailed since some of the topics are going to be covered later in the course.
    • The expected deliverables of the project.
  • A 2 page midterm progress review (due date posted on schedule).
  • Any software developed (if applicable)
    • The code is going to be checked for plagiarism through SafeAssign on Blackboard and Moss (the latter is able to check structural similarities in code).
    • Note that you are allowed to use existing code as long as
      1. this is used as a library or a component in your system
      2. you clearly state your sources in your report
  • 6-10 page paper in IEEE conference format
    • The report is going to be checked for plagiarism through SafeAssign on Blackboard.

Paper review and presentation

Since this is a research seminar level course, you will have to read and present a cutting edge research paper. You will have to choose a paper from the most recent conferences:

  • Most related:
    1. International Conference on Automated Planning and Scheduling (ICAPS)
    2. International Symposium on Combinatorial Search (SoCS)
  • Closely related but you will have to check your selection with me as well:
    1. AAAI Conference on Artificial Intelligence
    2. International Joint Conference on Artificial Intelligence (IJCAI)
    3. International Conference on Robotics and Automation (ICRA)
    4. InternationalConference on Intelligent Robots and Systems (IROS)

journals (check with me your selected paper):

  1. Artificial Intelligence (AIJ)
  2. Journal of Artificial Intelligence Research (JAIR)
  3. International Journal of Robotics Research (IJRR)

or magazines (check with me your selected paper):

  1. IEEE Intelligent Systems 
  2. IEEE Robotics and Automation Magazine (RAM)
  3. Communications of the ACM (CACM)
  4. AI Magazine

and give a presentation in class. 

Some useful resources:

Your talk is going to be graded by the instructor (30%) and by your peers (70%) in terms of presentation according to the following criteria (organization, understanding of the material, visual quality of the slides and engagement of the audience). Further details on the criteria will be provided on Blackboard.

Resources

The following are courses that can provide you with additional background, information or a different perspective altogether:
  1. UC Berkeley CS188 Intro to AI (The course provides an excellent introduction to AI. All the course materials are available on-line along with videos).
  2. CSE 574: Planning and Learning 2008 offering by Subbarao Kambhampati.
  3. CSE 571: Artificial Intelligence by Subbarao Kambhampati.

Plagiarism Policy

Your work for this course must be the result of your own individual effort. Having said that, you are allowed to discuss problems with your classmates or me, but you must not blatantly copy others' solutions. Copying (or slightly changing) solutions from online sources, other books or your friends is easily detectable. If you can find an answer online, then so can I! 


If any form of copying is detected, then you can expect a zero grade for the corresponding work that you submitted.  

Special Needs

If you are entitled to extra accommodation for any reason (such as a disability), I will make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course.