| Title | Seminar: AI Planning |
| Term | Winter 2018/19 |
| Dates: | TBA |
| Module type | Master's seminar (IN2107) |
| Prerequisites | Techniques in Artificial Intelligence (IN2062 ) |
| or Logic (IN2049 ) | |
| or Model Checking (IN2050 ) | |
| SWS | 2 |
| ECTS | 5 |
| Organisation | Mohammad Abdulaziz and Tobias Nipkow |
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.
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).
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.
Participants must hand in
The following list is preliminary and will be extended soon.
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
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
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
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
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
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, 3] and, later on, by introducing ADL [ 4].
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
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.