Seminar: AI Planning

Winter 2017/18

Overview

TitleSeminar: AI Planning
TermSummer 2017/18
Dates:TBA
Module typeMaster's seminar (INXXX)
PrerequisitesTechniques in Artificial Intelligence (IN2062 )
or Logic (IN2049 )
or Model Checking (IN2050 )
SWS2
ECTS5
OrganisationMohammad Abdulaziz and Tobias Nipkow

Content

As one of the earliest areas of study within AI, planning has a rich literature of techniques and formalisms. Broadly speaking, the planning problem is: given a world model (constituted of action descriptions that summarise the conditions needed to execute every action and the effects of executing every action on the world), an initial state and a goal state, is there a sequence of actions that, if applied to the initial state, can (optimally) achieve a goal state?

In this seminar every participant will receive a topic. The student is expected to write a paper about the topic and give a presentation to the other participants about it. Also, every participant will be required to give a short written review of the papers of two other participants. The precise schedule will be made available below.

Dates

The presentations will be held in sessions of 2 – 3 talks each during the semester, each 14:00–17:00 in Seminar Room 00.09.038 (Alan Turing).

Module type

The seminar can be attended as a Master's seminar. Each topic below has a few subtopics. A student shall select one of those subtopics for his/her seminar.

Formal requirements

Participants must hand in

Furthermore: As for the reviews: The final grade is composed as follows: 20% Reviews written + 40% Presentation + 40% Paper

List of Topics

The following list is preliminary and will be extended soon.

1. State-Space Search for Classical Planning

Description: Classical planning concerns problems whose state variables are finite and discrete, and whose actions are deterministic. Although PSPACE-complete, there are many search techniques that perform well on practical benchmarks. One popular way to solve classical planning problems is via A* search in the state space. Invented in the early 1970's[1], this algorithm is still a very popular search algorithm for finding paths in a state space. Its main strength is that, if equipped with the right heuristic, it can prune large chunks of the state space, thus potentially exponentially reducing search time. In the context of AI planning, the following are some popular search techniques and heuristics (i.e. subtopics from which students can choose): a) delete relaxation based heuristics [2], b) h^max and h^add heuristics [3][4][5], c) pattern databases [6], d) landmarks [7], e) symmetry breaking [8][9], and f) Merge-and-shrink [10]. Other topics include stubborn sets and partial order reduction.
Subtopics: A student should prepare the seminar on three conference (IJCAI/AAAI/ICAPS/ECAI) papers or one journal paper (JAIR/AIJ/JACM) on one A* search admissible heuristic (not necessarily papers or heuristics from the ones above) or a relevant search enhancement technique.
Advisor: Mohammad Abdulaziz and/or Julian Brunner

2. SAT-based Search for Classical Planning

Description: SAT-based approaches are another very successful technique to solve classical planning problems. SAT-based approaches were invented in the mid-1990's [1][2], with the main idea of tranforming or "encoding" the question of the existence of a plan to a SAT formula, or a similar constraint based system. The encodings are supposed to be constructive, as in, if such a formula has a satisfying assignment, a plan can be constructed from that assignment in linear time. Many areas of SAT-based solution of planning were investigated, for instance: parallel encodings [3], planning specific heuristics for guiding the SAT-solver [4], and symmetry breaking [5].
Subtopics: A student should prepare the seminar on three conference (IJCAI/AAAI/ICAPS/ECAI) papers or one journal paper (JAIR/AIJ/JACM) on SAT-based planning (not necessarily papers from the ones above).
Advisor: Mohammad Abdulaziz and/or Julian Brunner

3. Compositional Methods for Classical Planning

Description: In planning (as well as model checking), compositional methods are divide-and-conquer solution techniques that are used to avoid potentially traversing or processing an exponentially (in terms of the input problem) large state space. In those methods, a given problem instance is divided into much smaller abstractions. Then the needed processing is done on the abstractions, where for instance plans are found for the abstractions. Then solutions for the abstractions are composed into a (approximate) solution for the given instance. The power of these methods lies in the fact that the abstractions can be exponentially smaller than the given problem instance. These techniques were devised based on state variable dependencies as in [1] or [2], as well as based on other structures (e.g. factored planning[3], star topologies etc.).
Subtopics: A student should prepare the seminar on either i) the work by Williams and Nayak, ii) the work by Knoblock, or iii) factored planning. This should encompass three conference (IJCAI/AAAI/ICAPS/ECAI) papers or one journal paper (JAIR/AIJ/JACM) (not necessarily papers from the ones above).
Advisor: Mohammad Abdulaziz and/or Julian Brunner

4. Techniques for Numeric and Hybrid Planning

Description: This paradigm of planning concerns problems whose state variables can take numerical values (either real or natural numbers), and whose actions' preconditions can have predicates on functions defined on state variables, and whose effects can include assignment operators. It is currently a popular research topic because of the advent of autonomous vehicles, whose navigation is a canonical example of hybrid planning. Although undecidable in many cases, there are many methods that can solve practical problems. Most of those methods are generalistaions of existing techniques to solve classical planning problems. For example the A* state space search heuristic delete relaxation was generalised to numerical domains by [1], which was a successful approach that was further developed in [2] [3] [4] [5]. Other heuristics that were generalised to handle numerical planning are h^add and h^max in [6] and landmarks in [7]. Also, brand new heuristics were invented for numerical planning as in [8] and [9].
Similarly, SAT-based approaches to solve classical planning problems were adapted to solve numerical planning problems, but using SMT encodings to account for the fact that the state variables can take numerical values [10][11].
An interesting special case of numeric planning is that of path planning, where the numerical values under consideration are taken to be the position of a robot, or an autonomous vehicle. A prominent algorithm to solve this problem is the D* [12], which was later developed into Generalized Adaptive A* [13] further developed into Multipath Generalized Adaptive A* [14]. Another interesting case is that of temporal planning, where the numeric value is a monotonically increasing value of time.
Subtopics: A student should prepare the seminar on either i) search based general numeric planning, ii) SMT based numeric planning, iii) path planning, or iv) temporal planning. This should encompass three conference papers or one journal paper (not necessarily papers from the ones above) chosen with his/her supervisor.
Advisor: Fabian Immler

5. Techniques for planning under uncertainty (MDPs, POMDPs)

Description: In many practical applications, like stock-price forcasting or autonomous vehicles among others, it is not possible to model the exact effects of actions. In such cases, known as planning under certainty, a planning problem is modelled as a (factored) Markov Decision Process (MDP), where the result of executing an action is one of many states, each with a different probability. Solving those planning problems becomes much harder, because the state space search is transformed into searching through all the possible outcomes. Multiple methods to solve this kind of problems are centered around sampling the state space and approximating the probability distribution of the states that result from every execution, with the outcome of a policy that produces optimal plans in \"most\" cases. In [1], the authors discuss many methods that were state-of-the-art at the turn of the century, and multiple new methods were devised since that time like [2][3].
A further generalisation of that is when it is not possible to know the current state with certainty. In those cases, states are also modelled by probability distributions and the resulting framework is referred to as Partially Observable Markov Decision Processes (POMDP). Techniques to solve POMDPs were pioneered in [4], and newer techniques to solve them are discussed in [5] [6] [7], where different sampling techniques are studied.
An important class of (PO)MDPs is the ones used to model multi-armed-bandits, which are of theoretical and practical interest. Multi-armed-bandits were first Modelled by Nash in the 1950s studied in many papers, and solving the multi-armed-bandits as well as providing upper bounds on their complexities is still an active research topic (e.g. [8]).
Subtopics: A student should prepare the seminar on solution methods or theory concerning either: i) MDPs, ii) POMDPs, or iii) Multi-armed bandits. This should encompass three conference papers or one journal paper (not necessarily papers from the ones above) chosen with his/her supervisor.
Advisor: Simon Wimmer

6. Complexity of different planning formalisms and fragments

Description: The difficulty of finding a (optimal) plan is not the same for each of the different planning formalisms described above. The complexity and decidability of classical planning [1], planning under uncertainty [2], and numerical planning [3], and other fragments and generalisations of those basic formalisms [4] [5] [6] [7], were previously studied.
Subtopics: A student should prepare the seminar on the complexity and/or the decidability of either: i) STRIPS, ii) a fragment of STRIPS (e.g. unary actions), iii) MDPs and POMDPs, or numeric/hybrid planning. This should encompass three conference papers or one journal paper (not necessarily papers from the ones above) chosen with his/her supervisor.
Advisor: Lars Hupel

7. Semantics of different planning formalisms

Description: In all planning formalisms, there is one common challenge: what is the correspondence between what effects have in the actual state of the world and the changes they do to the world model? This is studied as a part of the area known as knowledge representation, and it is a fundamental problem of artificial intelligence first tackled by John Mccarthy in a seminal paper in the late 1960s [1]. In that paper, John Mccarthy introduced the situation calculus as a framework to resolve that challenge. However, situation calculus had a drawback: because it is too expressive, solving problems represented in that formalism would be a very complicated task. This was remedied by introducing STRIPS whose semantics were studied in [2] and, later on, by introducing ADL [ 3].
Subtopics: A student should prepare the seminar on the semantics of each of: i) situation calculus, ii) STRIPS, and iii) ADL, and compare the three of them in terms of expressiveness and complexity.
Advisor: Lars Hupel

Allocation

Tips

Services like Google Scholar can be useful to find relevant scientific papers for your topic. Afterwards, you can gain access to these publications using the university's eAccess. This step is necessary because scientific publisher often demand high prices for the publications otherwise.