2001 by Ute Schmid
KI Planung/AI Planning
Institut für
Informatik
, FB Mathematik-Informatik, Universität Osnabrück
Seminar im Wintersemester 2001/2002
(seminar course, winter term 01/02)
Kategorie: KI, Vertiefung/Category: AI, advanced
Course language: English
Themen: Einführung in KI Planung: Strips, Situationskalkül, ADL,
Vorwärts- versus Rückwärtsplanung, Effizienz, Korrektheit, Optimalität
von Planungsalgorithmen, Kontrollwissen, nicht-lineares Planen, partial
order planning, Graphplan, Planung as Satisfiability Problem,
Universelles Planen und Modelchecking, Planen versus Problemlösen,
Planen und Lernen. Vorstellung von Beispielsystemen (Teilnehmer am
AIPS-Wettbewerb); wenn gewünscht: kleine Programmieraufgaben in Lisp.
Topics: Introduction to AI planning: Strips, situation calculus, ADL,
forward- vs. backward-planning, efficiency, correctnes, optimality of
planning algorithms, control knowledge, non-linear planning, partial order
planning, Graphplan, planning as satisfiability problem, universal planning
and model checking, planning vs. problem solving, planning and
learning. Exemplaric presentation of systems (participators at the AIPS
planning competition); if wanted small programming assignements in Lisp.
Hours and Contact
Online-Information
- Introductory Literature
- James Allen, James Hendler and Austin Tate (Eds.) (1990).
"Readings in Planning", Morgan-Kaufmann Publishers, 1990.
- Stuart Russell and Peter Norvig (1995). "Artificial Intelligence - A
Modern Approach", Prentice Hall. (Chaps. 11 - 13)
- Ute Schmid (2001). "Inductive Synthesis
of Functional Programs - Learning Domain-Specific Control Rules and
Abstract Schemes". (Chap. 2: State-based Planning, pp. 15-60)
[GZipped Postscript, 447 pages]
- Current approaches such as Graphplan, Satplan, model based
planning
cannot (yet) be found in text books. It is best to consult current
proceedings:
[AIPS'98]
[AIPS'00]
[EPC'99]
- Search for literature: [The Collection
of Computer Science Bibliographies] [Citeseer]
- Planning Repositories/Systems: [AI Planning
Resources] [PuK
HomePage] [Planner
Software & Resources] [Planning Domain
Repository] [PDDL]
[Blackbox]
[The
Durham Planning Group (Stan, Tim)]
[Freiburg
Planing-Group (IPP, FF)]
[Graphplan] [Hector Geffner's HomePage (HSP) ]
[Prodigy]
- Lisp: [Common
Lisp the Language, 2nd Edition] [Marty Hall's Collection]
Credits
- "Übungsschein": Consultations with the supervisor as scheduled,
seminar talk (slides should be provided for online linking);
regular participation in class (very necessary for discussions).
- "Modul-Prüfung" (exam): Precondition is to get the
"Übungsschein"; oral examination about the topics of the seminar
course.
- For cognitive science students this seminar course is classified as
"optional course in AI" (4 credit points).
Schedule and Syllabus
The given syllabus is open to changes depending on the background and
interests of the participating students. For the current syllabus, one
recent relevant research paper is given for every topic. The papers might
not be understandable without further background reading. Helpful additional
texts can be obtained from the supervisor.
Schedule
- 17.10.: Introduction: What is planning?, planning domain and problem
representation languages (Strips, situation calculus and ADL);
presentation of topics for presentation
- 24.10.: Introduction: Strips Planning;
fixing the presentation schedule
- 31.10. Introduction: Soundness and completeness, linear
vs. non-linear planning
- 07.11.: Introduction: Planning algorithms; current topics in
planning
- 14.11.: Planning as Heuristic Search (HSP) [Slides I (ps)]
Referents: Gero Keuneck & Robert Mertens
- 21.11.: HSP continued [Slides II (ps)]
- 28.11.: Functional Strips [Slides
(pdf)]
Referent: Marcus Lunzenauer
- 05.12.: Discussion/Search Algorithms
- 12.12.: no class
- 19.12.: Grahplan [Slides
(html)]
Referent: Nicolai Strauch
- 09.01.: Planning as Model Checking [Slides (pdf)]
Referent: Bernd Pachur
- 16.01.: Policy Learning [Slides of Geffner's Talk (ps)]
Referent: David Soto
- 23.01.: Control-Rule Learning [Slides (htm)]
Referent: Jan Plate
- 30.01.: Planning and Program Synthesis
- 06.02.: Final Discussion
A selection of topics:
- Topic 1: Planning as Heuristic Search (HSP)
- Topic 2: Graphplan
- Topic 3: Planning as Satisfiability Problem (Blackbox)
- Topic 4: PDDL/ADL (IPP)
- Topic 5: Planning as Model-Checking
- Topic 6: Functional Strips
- Topic 7: Planning and Learning/Prodigy
- Topic 8: Policy Learning
- Topic 9: Control-Rule Learning
- Topic 10: Domain Analysis (TIM)
- Topic 11: Planning and Program Synthesis (DPlan; presented by Schmid)
-
Schmid, U. and Wysotzki, F. (2000). Applying inductive program
synthesis to macro learning. In S. Chien, S. Kambhampati, and C.A. Knoblock
(Eds.), Proceedings of the AIPS 2000, Breckenridge, CO, April 2000,
(pages 371-378), AAAI Press.
- Topic 12: Heuristic Search Again (FF)
Students
[mailto-allstudents]