Title | Seminar: AI Planning |

Term | Summer 2018 |

Dates: | 2/7/2018 and 9/7/2018, at 1400 in MI 00.09.038 (Turing) |

Module type | Master's seminar (IN2017) |

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).

- TBA

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

- a complete (!) paper draft
**three weeks**before their presentation to**both**Mohammad Abdulaziz and their advisor; this will be reviewed by other students - a draft version of their presentation slides to their advisor
**one week**before their talk - the final versions of their paper and presentatio to
**both**Mohammad Abdulaziz and their advisor on the day of the presentation. - reviews of the two papers they were assigned within
**one week**before the respective presentation to Mohammad Abdulaziz

- The length of the paper should be roughly 10 pages.
- The length of the talk between 35 and 45 minutes (excluding Q&A session) and must
**not**exceed 45 minutes. - Reviews, presentations, and papers should be in English.
- There are no strict requirements on the form of the paper or slides. No template will be provided.
- All submissions are to be sent to Mohammad Abdulaziz.

- Reviewers receive the drafts of their assigned topics as soon as they are handed in.
- The main focus of the reviews should be the
*content*and the*presentation*of the papers. Does it make sense? Is it well-structured? Is it understandable to someone who has not read the source material? - Reviewers are not expected to read the cited source material.
- Spelling and grammar may also be mentioned, but are less important.
- A summary of the reviewed topic is
*not*required. - Reviews should be roughly one page long
- Reviewers may freely decide whether to use full sentences or bullet points.

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:** 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.

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

**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

- Applications must be made through the Matching platform.
**You must have attended one of the prerequisite lectures to be allowed to participate in the seminar.**- The allocation of topics to the participants will be done by us according to the preferences given by the participants.
- Each participant will be assigned two other topics to review. Reviewers can choose to remain anonymous.
- There will be a kick-off meeting. If you have any questions about it, send an email to Mohammad Abdulaziz.

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.