Foundations of Artificial Intelligence (FAI) Group
About this page. We summarize FAI's research area, and the major directions we are currently actively exploring. This is mainly intended for students interested in FAI, but other readers may also use it to get an overview/impression of our research.
The very first thing you should do, to get an idea of our research, is read the "Automatic Planning (a high-level summary)" section below. Then, read this paper:
This provides an an easy-to-read and (hopefully) entertaining introduction to our main research area.
As a next step, we recommend in particular to read the "Partial Delete Relaxation" section below, which is relatively detailed and should give a good impression of the kind of research questions we're interested in.
Note: This page gives the main directions we are currently exploring, but should not be confused with an exhaustive description of our research. We are typically doing various things not subsumed by any of the descriptions below. If you are a student and interested in working with us, this page gives good starting points, but cannot replace a direct conversation.
Some example topics of student projects we conducted in the past are listed here.
Automatic Planning (a high-level summary). How to decide what to do? Humans take decisions all the time, and so must robots or software bots to succeed in their environment. How should they do that?
This and related questions are the origin of the research area of Automatic Planning, or AI Planning, one of the founding sub-areas of Artificial Intelligence. Humans are able to (eventually) successfully tackle any new situation they are faced with, coming up with courses of action achieving their aims. The vision of AI Planning is to reproduce this ability, creating general problem solving algorithms, that can in principle solve any problem (more precisely, any problem whose solution involves finding a suitable course of action), given a suitable logics-based description of that problem.
Illustrating this in an adversarial setting, an example is Chess: Traditional Chess computers are created through considerable human efforts, expertise, and engineering, and they are unable to do anything else other than playing Chess. A general problem solver would, in contrast, merely be given the rules of the game -- of any game -- and determine on its own how to play the game well. (This particular form of general problem solving is known as General Game Playing, an area also touched by FAI research.)
Algorithms of this kind can automatically generate strategies of action for arbitrary autonomous agents in arbitrary environments, like for example a robot on Mars (that requires autonomy due to the impossibility of full remote control), or a softbot executing automatic hacking attacks for security testing (where the environment is highly dynamic and self-adaptive technology is valuable). More generally, planning algorithms can solve any problem whose solution can be cast as finding goal paths in large transition systems (billions of states and upwards), or proving the absence of such paths. They are successfully applied in areas as diverse as large-scale printer control, generation of business process templates, greenhouse logistics, security testing, and natural language sentence generation. Close relations exist to all areas of CS requiring to test reachability in large transition systems, including Verification/Model Checking, Program Synthesis, Bioinformatics, Game Playing, etc.
Partial Delete Relaxation. The most successful approach to Automatic Planning, to date, is heuristic search, which enumerates reachable states in a preference order given through a heuristic function, usually denoted h, that maps states to goal distance estimates. States that appear closer to the goal, according to h, are preferred. If h lower-bounds goal distance, then this can be arranged so as to guarantee that the goal path found is optimal.
But how to generate a heuristic function in Automatic Planning, where this needs to happen automatically given only the logics-based problem description (the "rules of the game")? This is a major research area in Automatic Planning, and it is the main topic of our specialized lecture (see our teaching page). The basic idea is to design a problem relaxation, R; then, to estimate the goal distance of state s, solve its relaxation R(s) exactly; and set h(s):= the cost of the solution to R(s). In other words, h(s) is the cost of a relaxed solution for s. But then, what are useful relaxations of logics-based problem descriptions?
One of the most successful answers is the so-called delete relaxation. This relaxation essentially pretends that everything that once was true, remains true. In particular, a logical proposition may be both, true and false, and we can pick whichever value we prefer. For example, if I buy a car, and I pay 10000 EUR for that, then in the real world, after applying the "buy" action, I have the car but I no longer have the money. In the delete-relaxed world, I have the car, and I also still have the money.
It has been shown that delete-relaxation heuristic functions are highly informative for search on many planning problems, essentially as they preserve complex prerequisite--effect chains. Recommended reading here are our papers on delete-relaxation heuristic functions and their search space properties. Nevertheless, as the delete relaxation ignores the negative "side effects" actions may have, it exhibits severe weaknesses in problems where conflicting side effects are essential to the nature of the problem. One example are puzzle-like problems, like Rubic's cube where in each action application we intend to move just one cube, but as a side effect many other cubes are moved as well. Another, more practically important, example is planning under resource constraints, where we may intend to, e.g., move a vehicle, but as a side effect fuel gets consumed -- under the delete relaxation, a single drop of fuel suffices to travel the world.
The mission of partial delete relaxation is to devise approximation techniques "taking some delete into account". More precisely, we want there to be an interpolation parameter that allows to pick an arbitrary point between fully delete relaxed planning, and real planning. In other words, we want to be able to force the relaxation to be exact in the limit, while also being able to choose arbitrary points in the middle, allowing to trade information accuracy against reduced computational overhead. To date, two such techniques are known, and FAI is leading in both of them:
Recommended reading here are our papers establishing the basic method, as well as recent work selecting conjunctions online during search to learn from dead-end states and avoid similar mistakes in the future (detailed version or a short summary version), thus establishing a form of clause learning for state space search.
Exciting directions for future research (2-5 years) include learning more powerful clauses, online learning for goal distance estimation, analyzing the effect and necessary size of conjunction sets C in problem sub-classes, etc. The approach is also promising for application in areas other than planning, like Game Playing, Synthesis, or Verification, where dead-end detection is important.
Recommended reading here is our paper establishing the basic method.
Exciting directions for future research (2-5 years) include search methods using red-black approximation sparsely (the computational overhead can get quite large), identifying new tractable fragments, generalizations where each state variable has a partial memory of its past values, incremental red-black planning where we iteratively paint variables black, etc. A particularly promising direction is the use of red-black relaxation as a means to prove unreachability, as red variables capture prerequisite--effect chains required to reach the goal, yet without entailing the need to enumerate all value combinations of these variables. To prove unreachability, it may suffice to paint only the most critical state variables black. This approach has promise, beyond planning, also in e.g. Verification where unreachability proofs -- unreachability of an erroneous behavior -- are required to verify system correctness.
Star-Topology Decoupling. Apart from heuristic functions, another major means to tackle large transition systems are optimality and/or completeness preserving reduction methods, based on notions like partial-order reduction (some transition sequences can be permuted and only one permutation needs be searched), state-dominance relations (states dominated by already explored states can be pruned), symmetries (only one symmetric option needs be explored), or decomposition (solving sub-problems and assembling a global solution from the parts, like in divide-and-conquer approaches).
Our seminar on Admissible Search Enhancements (see our teaching page) gives an overview of such methods. A brand-new method of our own making is star-topology decoupling, a particular form of problem decomposition.
Star-topology decoupling applies to systems/planning problems that can be viewed as consisting of a single center component, interacting with each of a (possibly large) set of leaf components. The leaves interact only via the center, and hence are "conditionally independent given the center". The latter is an appealing picture, and is a common-sense approach to decompose graphical models, like Bayesian networks -- yet here we are not facing a graphical model. The star topology is a structural property of the transition rules in a high-level description of a large transition system. What does it mean to "break the conditional dependencies" in this context?
The answer given in star-topology decoupling is to search over center-component paths only. For any fixed center path (intuitively, a "given valuation of the center"), the possible moves for each leaf component become independent, and can be maintained alongside the center path. This method takes exponential effort in the size of each component -- it has to enumerate each component's state space -- but it does not have to enumerate state combinations across leaf components, thus getting rid of a major source of combinatorial blow-up. This typically yields substantial search space reductions (several orders of magnitude are a common empirical phenomenon), for all purposes, i.e., for optimal planning, for satisficing planning (finding some goal path without giving a quality guarantee), and for proving unreachability.
Recommended reading here is, foremost, our short summary paper outlining the approach. For more details, refer to our papers establishing the basic method for more restricted problems taking a "fork" structure, and on its extentension to star-topology structures.
Star-topology decoupling can be exponentially stronger than all previous reduction methods. It relates to a method known as unfolding, and can to some extent be understood as an unfolding variant specialized to star-topology structures, exploiting this particular structure for exponentially more effective handling of search states, preserving optimality, and enabling search & pruning methods dedicated to star-topology structures.
There are many exciting directions for research on star-topology decoupling (5-10 years), including the combination with complementary reduction techniques, effective implementation (eg. via symbolic representation of leaf state spaces), dedicated heuristic search methods, extensions to deal with complex goal formulas, etc. A particularly promising direction is the application to Verification, for state space exhaustion. Star-topology is a classical system design principle, making star-topology decoupling a perfect match for such systems. Challenges are adopting the approach to different/richer input formalisms, to temporal-logic property formulas, effective implementation, combination with other techniques, etc.
Simulated Penetration Testing. Penetration testing (pentesting) detects security holes in a system by conducting attacks on that system. The pentesting is usually done by humans. Applied to the immense computer networks run by today's large internet companies (think "eBay"), this approach suffers from a complete lack of scalability -- tens of thousands of machines, largely administrated by individual users, each with a hugely complex software landscape potentially containing any of thousands of known vulnerabilities, or yet undetected ones. The idea in simulated penetration testing is to tackle this through automation.
The ultimate vision is to design a simulator that conducts attacks the same way a real attacker would. This vision is thoroughly unachievable though (e.g. the classical Turing test appears harmless by comparison). In practice, the idea is to settle for attacker formalizations based on known (and well-researched) planning formalisms, lending themselves to partial automation of the process, essentially providing guidance to human security officers: point out "where to look" (or, in other words, help to find the proverbial needle in the haystack). Possible models range from classical (deterministic) planning, over Markov decision processes (MDP), to partially observable Markov decision process (POMDP) models which allow to explicitly capture the incomplete knowledge that characterizes -- from the point of the view of the attacker -- network attacks.
Recommended reading here is Joerg Hoffmann's ICAPS'15 invited paper, giving a nice overview of the intended application and the range of possible models.
Simulated pentesting is one of the major application areas FAI is and will be exploring, in cooperation with CISPA as well as some international partners. Exciting research questions (5-10 years) arise at all levels, from basic research to the applied level. In particular: What are good models for this problem? How do they relate to each other? How to exploit their particular structural properties for effective algorithms? How to obtain the different model variants in practice? How to arrange the analysis in the overall security life cycle? How to provide what-if analysis methods, status quo overviews, methods suggesting possible security fixes?
Natural Language Processing. The area of Natural Language Processing addresses many problems naturally formulated as search in a large space of possibilities. In particular, generating text is a form of planning problem -- planning the text content, planning the sentences, planning the actual phrasing of these sentences. For example, sentence generation can be formulated as a search in the space of possible partial sentences, where individual search stops add another word to some candidate, and the search terminates when a legal sentence has been constructed.
As language is a very general concept -- different vocabularies, different grammars -- ideally one would like to have general solvers. Which is where general problem solving comes into the picture. AI Planning languages and solvers are a natural match for logics-based formalizations of language. More generally, the search spaces in Natural Language Processing come with many of the same challenges as those in other problems: combinatorial explosion, permutative search paths, composition across interacting components, etc. Natural Language Processing and AI used to be very closely tied, but have developed largely separately for several decades. Our basic direction here is to apply search techniques from recent AI research, to the search problems in Natural Language Processing.
Recommended reading here is a paper successfully applying planning techniques to natural language instruction-giving, simply through a compilation into a planning language; and a recent overview/challenge paper outlining challenges and directions in surface generation, i.e., searching for a good sentence formulation.
Search problems in Natural Language Processing pose many interesting challenges, that FAI has only begun to explore and that we expect to explore long-term (no end in sight), in cooperation with the Computational Linguistics department at UdS. We are exploring search methods for surface generation in OpenCCG, pertaining to dead-end detection, heuristic functions (sentence-completion quality estimation), partial-order reduction. Another interesting line of research are particular "word alignment" problems that arise in the computation of recently proposed measures of the "linguistic distance" between two languages (intuively, playing a similar role as sequence alignment in gene distance). Last but not least, planning methods also lend themselves naturally to more high-level text planning tasks, structuring the text content, on a sentence-by-sentence basis, so as to achieve the desired communication goal. We are currently exploring this direction for automatic instruction generation, using Minecraft as a benchmarking environment.
Planning & Learning. Getting back to our summary description above, at a high level AI Planning is concerned with intelligent action-taking, for agents confronted with new, or unexpected, problems or situations. A distinguishing quality of humans is their ability to do so, i.e., to adapt to unseen problems. But how do they do so? An important part of the answer, ignored in our discussions above, lies in the words "adapt to": There is, of course, an important learning component to this human ability.
Classical AI Planning techniques typically address each input problem from scratch, taking as input the action descriptions, initial state, and goal, and searching for a goal path. If the same problem instance is posed again, the tool will conduct the same search again, as if it had never seen that instance before. More generally and importantly, in practice one typically sees thousands of related problem instances in sequence, and it would of course make sense to learn from that experience, but classically this is not done. While this may sound odd, it is actually quite common in combinatiorial solvers: SAT solvers, constraint solvers, MILP solvers, theorem provers, all are the same in this regard.
A major reason why learning in problem-solving is challenging is that it requires transfer learning: We need to learn knowledge useful to solve problem instance X, from experience on different problem instances Y. Currently, the most successful learning techniques in search (like clause learning in SAT) are "online", during the search on a single instance X. In contrast, when humans adapt to a new problem, they learn to figure out how the problem works -- they learn to "understand" the essential nature of the problem, across instances. How to formalize, and automate, this form of "understanding"?
The AI Planning literature offers a variety of answers to this question, some of which are overviewed in our seminar on Planning & Learning (see our teaching page). FAI is currently conducting research into learning action-pruning rules, which is promising because it can be expected that "bad" actions can be identified much more easily than "good" ones -- think of Sokoban or solitaire card games as examples. The idea is to learn compact knowledge representing bad choices, helping the search to concentrate on figuring out what the good choices are.
What the AI Planning literature has not yet considered much is the use of neural networks (NN) as a means for learning search guidance. But given the recent success of NN in playing Go, Chess, and Shogi -- Google DeepMind's famous AlphaGo and related programs -- this is of course a highly promising direction in planning, and in search problems more generally. We expect this direction to become increasingly important, over the coming years, for FAI, and for the entire AI area.
AlphaGo's success results from the combination of two components: first, neural networks which learn to estimate the value of a game position, and to identify a subset of most interesting applicable moves; second, search, which uses this learned knowledge to explore the game state space and identify the best moves. We believe that this formula, NN + search, is a key recipe for general problem solving. A key challenge is transfer learning in situations where the input is more general/variable than a game-board matrix: Almost every problem humans typically deal with, and almost every interesting planning application, comes with problem instances differing in the number of actors, objects, problem parameters. What remains constant are the kinds of actors/objects, and the kinds of activities to be planned for. In a sense, playing Go is like working on a single problem instance, rather than on an entire universe of possible instances.
Apart from this major challenge, many things remain to explore in how to apply NN methods to planning/search problems, how to train them, etc. Some key guiding quesions are:
E.g. relational representations (scaling inputs); inadmissible heuristic functions; preferred action estimators.
E.g. problem structure parameters; proofs (unreachability, optimality) vs. search guidance; explainability/analysability.
E.g. model-based analysis of the behaviour induced by a learned action policy; employing NN as part of the machinery in a model-based approach; etc.