Course Descriptor

Course:   Automated Planning

Course Web page

Credit Points	10
Credit Level	11
Acronym	INF-5-PLAN
Study Pattern	Study Format		Hours
	Lectures		20
	Tutorials		0
	Timetabled Laboratories		0
	Non-timetabled assessed assignments		30
	Private Study/Other		50
	Total		100

Pre-requisite Courses	FAI
Other Pre-requisite Requirements	None
Co-requisites/Forbidden Combinations	None

Short Description

Summary of Intended Learning Outcomes

• Understand and formalize different planning problems.
• Discuss the theoretical and practical applicability of different approaches.
• Have the basic know how to design and implement planning systems.
• Know how to use planning technology for projects in different application domains.
• Ability to review planning literature relevant to an area covered in the course.

Assessed Coursework

• Practical exercise with automated planning systems.
• Survey of techniques used in nominated planning systems.
• Literature review of a selected area.

Syllabus

Core Elements

• Introduction and overview: intuitions and motivations. Basic conceptual model for planning: state transition systems, classical assumptions (e.g., observable states and deterministic transitions, restricted goals, sequential plans, implicit time) and ways to relax them. Overview of different planning problems and approaches.
• Classical planning: The classical planning problem. Situation Calculus and the Frame Problem. Classical representations and languages (e.g., STRIPS-like). Complexity of Classical Planning. State-Space Planning. Move to Plan-Space Planning.
• Hierarchical Task Network Planning. Partial-Order Planners. Mixed-initiative Planners.
• Neoclassical Planning: Modern approaches to the classical planning problem: e.g., Planning-Graph techniques, Propositional satisfiability techniques, and Constraint satisfaction techniques.
• Heuristics and Control Strategies: Heuristics (in state-space and plan-space planning). Hand-coded control rules and control strategies. Deductive planning and control strategies in deductive planning.
• Planning with Time and Resources: Basics of point and interval temporal algebra. Temporal constraints networks. Planning with temporal operators. Integrating planning and scheduling
• Case Studies and Applications: A selection from robotics, manufacturing, assembly, emergency response, space exploration, games, planning for the web, etc.

Areas Covered by Self-Study and Literature Review

• Scheduling: Linear and Integer Programming. Dynamic Scheduling. Applications to real world scheduling problems. Design, development and implementation of scheduling systems.
• Planning under uncertainty: different sources of uncertainty (e.g., nondeterministic actions, partial observability). Extensions to classical approaches (e.g., plan-space, planning-graph and propositional satisfiability techniques). Planning based on Markov Decision Processes. Planning based on Model Checking.
• Other problems and approaches which are open to review and study: Case-Based Planning. Multi-Agent Planning. Plan Merging and Plan Rewriting. Abstraction Hierarchies. Domain Analysis. Typed variables and state invariants. Other kinds of domain analysis. Planning and Learning. Planning and Acting, Situated Planning, Dynamic Planning. Plan Recognition. Distributed Planning. Multi-Agent Planning. Learning in Planning. Mixed-Initiative Planning. Knowledge-based Planning.

Relevant QAA Computing Curriculum Sections:  Artificial Intelligence

Reading List

• "Automated Planning: Theory and Practice" by M. Ghallab, D. Nau, and P. Traverso (Elsevier, ISBN 1-55860-856-7) 2004.

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh