Planning at AIC

Automated Planning

The ability to plan a sequence of actions in order to reach a desired goal is one of the basic manifestation of intelligence, both natural and artificial. It is thus no surprise that planning has been studied in AI since its very beginning in the 60's and 70' with the STRIPS language and the well known A* algorithm. Both are used up to date, but with significant improvement in automated translation and invariant synthesis and automatically derived heuristics exploiting the problem structure. In our group we focus on the research of basic principles of classical planning and heuristics, but also on variants such as multi-agent planning and on the application of planning to real-world problems.

Research and Thesis Topics

Classical Planning

  • Use of invariants in optimal planning (graph theory, complexity theory)
  • Integration of domain-specific solvers to improve the efficiency of classical planning on particular domains (puzzles, logistics, videogames)
  • The use of machine learning techniques in planning and extraction of structural information (machine learning, deep learning, neural networks)
  • Plan optimization

Multi-Agent Planning

  • Measuring and reducing privacy leakage (secure multiparty computation)
  • Developing a privacy-preserving planner (cryptography, security)
  • Optimal multi-agent planning based on finite-state machine intersection

Temporal Planning

  • Reasoning about time and resources
  • Urban Traffic Control

Current projects and summer jobs

With possible extension to thesis topics.

Measure Privacy Leakage in Multi-Agent Planning

Privacy is one of the main reasons why multi-agent planning is used instead of classical centralized approaches, but its proper treatment has been neglected. Until we started to work on it. And now you can join us in the first ever effort to rigorously quantify and measure privacy leakage of existing algorithms and follow up on our successful publication track in the topic.

  • Summer Job Task - Work on the implementation of our quantification metrics and privacy leakage detection algorithms in a state-of-the-art planner (C, Python) and measure the actual privacy leakage on a benchmark set.
  • Thesis Task - Improve the privacy leakage detection algorithms, implement, evaluate and write a top-conference publication (and the thesis, by the way).

Implement a (Strong) Privacy-Preserving Planner

Related to the previous topic, there is no Multi-Agent planner actually using cryptographic primitives and tools (e.g., Sharemind) to plan while preserving privacy. You can be the first to pull it off.

  • Summer Job Task - Implement our theoretical algorithms using existing state-of-the-art cryptographic tools and planning algorithms (whatever language you like + SecreC).
  • Thesis Task - Improve, implement, evaluate and write a top-conference publication (and the thesis, yes, by the way).

Integration of Planning Models and Traffic Simulator (SUMO)

Automated planning techniques have shown their usefulness in traffic control. To investigate how they can influence traffic, they have to be integrated within a simulation framework.

  • Summer Job Task - Implement a framework that integrates a planning component into the existing traffic simulator SUMO
  • Thesis Task - Improve the planning models, evaluate the approach and write a top-conference publication (and the thesis, yes, by the way).

Temporal Planning Framework

Temporal planning despite its usefulness in practice is underrepresented in the planning community. The initial step is to provide an open framework that parses the planning task description (in PDDL 2.2) and provides a basic functionality over the elements (e.g. actions, predicates)

  • Summer Job Task - Implement a parser for PDDL 2.2 and store the element (e.g. actions, predicates) into appropriately designed data structures. Then implement a basic functionality over these elements (e.g., instantiation, predicate achievement etc.)
  • Thesis Task - Implement a planning technique (within the framework), evaluate the technique and write a top-conference publication (and the thesis, yes, by the way).

State Invariants for Classical Planning

State invariants are logical formulas that hold in every state reachable from the initial state by a sequence of applied operators. State invariants describe some intrinsic properties of the corresponding planning problem and can be useful in construction of admissible heuristics, pruning (reduction) of planning problems or detection of dead-end states.

This topic aims both at theoretical and practical results connected with inference and further application of state invariants. The student will study state-of-the-art methods used for solving domain-independent planning problems and propose improvements of these methods based on utilization of inferred state invariants. The improvements will be implemented and experimentally evaluated on standard benchmarks used in the planning community.

People

Antonín Komenda

Lukáš Chrpa

Michal Štolba

Daniel Fišer