Automated Planning, 6 credits (TDDD48)

Main field of study

Information Technology, Computer Science and Engineering, Computer Science

Course level

Second cycle

Advancement level

A1X

Course offered for

• Computer Science and Engineering, M Sc in Engineering
• Computer Science, Master's programme
• Information Technology, M Sc in Engineering
• Computer Science and Software Engineering, M Sc in Engineering

Entry requirements

Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshold requirements for progression within the programme, or corresponding.

Prerequisites

Basic knowledge and understanding of data structures and algorithms as well as logic and discrete mathematics. Knowledge and understanding of basic artificial intelligence techniques and concepts, including state-space search, heuristics and the A* search algorithm.

Intended learning outcomes

Planning is the task of thinking before you act: Not only reacting to the environment, but using knowledge about the world to determine what to do in order to achieve a given goal. Automated planning is a central topic in AI, and task and motion planning capabilities are essential to the construction of many robust autonomous systems. Recently, research in planning has seen a great deal of excitement, with a variety of new approaches vastly outperforming older techniques in terms of speed as well as applicability and expressive power. Planning technologies are currently used with great success in applications ranging from production lines and elevators to unmanned aerial vehicles (UAVs) and space applications such as the Hubble Space Telescope and the Mars rovers. The aim of this course is to provide a comprehensive view of a wide range of planning techniques, as well as hands-on experience in constructing and modeling planning domains to solve specific planning problems.
After the course, the student will be able to:

• Evaluate and apply a variety of planning techniques for classical planning as well as for knowledge-intensive planning and planning under uncertainty.
• Explain the practical advantages and disadvantages of different levels of expressivity in planning models.
• Model classical as well as probabilistic planning problems in commonly used domain definition languages.
• Evaluate and apply common techniques for goal-directed planning, such as various forms of heuristics and control rules.
• Explain the workings of commonly used path and motion planning techniques.

 

Course content

 

• Introduction to planning
• The classical planning paradigm
• Algorithms for classical and neo-classical planning
• Planning with time and resource constraints
• Planning with rich domain knowledge: How to make use of all you know
• Planning under uncertainty: How to handle incomplete knowledge
• Path planning and motion planning

 

Teaching and working methods

A series of lectures present the theory behind planning as well as many practically useful techniques for plan generation under varying assumptions about the environment. A set of laboratory exercises provide hands-on experience using several state-of-the-art planning paradigms and planning systems. In addition to developing domain models for a set of interesting planning problems, participants will explore how different heuristics and domain
knowledge can be used to improve plan quality as well as performance. Probabilistic planning will be explored through simulated execution.

Examination

LAB1	Laboratory work	U, G	3 credits
TEN1	Written examination	U, 3, 4, 5	3 credits

Grades

Four-grade scale, LiU, U, 3, 4, 5

Other information

Supplementary courses: AI Programming

Department

Institutionen för datavetenskap

Director of Studies or equivalent

Peter Dalenius

Examiner

Jonas Kvarnström

Education components

Preliminary scheduled hours: 64 h
Recommended self-study hours: 96 h

Course literature

Automated Planning: Theory and Practice, Malik Ghallab, Dana Nau and Paolo Traverso ISBN: 1-55860-856-7