Ing. Michaela Urbanovská

Automated planning and machine learning create a powerful combination of tools which allows us to apply general problem solving techniques to problems that are not modeled using classical planning techniques. In real-world scenarios and complex domains, creating a standardized representation is often a bottleneck as it has to be modeled by a human. That often limits the usage of planning algorithms to real-world problems. The standardized representation is also not a suitable for neural network processing and often requires further transformation. In this work, we focus on presenting three different grid representations that are well suited to model a variety of classical planning problems which can be then processed by neural networks without further modifications. We also analyze classical planning benchmarks in order to find domains that correspond to our proposed representations. Furthermore, we also show that domains that are not explicitly defined on a grid can be represented on a grid with minor modifications that are domain specific. We discuss advantages and drawbacks of our proposed representations, provide examples for many planning benchmarks and also discuss the importance of data and its structure when training neural networks for planning.

Automated planning provides a powerful general problem solving tool, however, its need for a model creates a bottleneck that can be an obstacle for using it in real-world settings. In this work we propose to use neural networks, namely Cellular Simultaneous Recurrent Networks (CSRN), to process a planning problem and provide a heuristic value estimate that can more efficiently steer the automated planning algorithms to a solution. Using this particular architecture provides us with a scale-free solution that can be used on any problem domain represented by a planar grid. We train the CSRN architecture on two benchmark domains, provide analysis of its generalizing and scaling abilities. We also integrate the trained network into a planner and compare its performance against commonly used heuristic functions.

Privacy preservation has become one of the crucial research topics in multi-agent planning. A number of techniques to preserve private information throughout the planning process have emerged. One major difficulty of such research is the comparison of properties related to privacy among such techniques. A metric allowing for comparison of such privacy preservation was introduced only recently, having a number of drawbacks such as prohibitive computational complexity. In this work we strengthen the theoretical foundations and simplify the metric in order to be practically usable. Moreover, we test the usability of the metric in an analysis of various techniques in multi-agent heuristic computation and search, determining which are the most beneficial in terms of privacy preservation. We also evaluate the techniques in terms of the classical IPC score to assess their impact on the overall planning performance. The results are somewhat surprising and show that extracting any privacy-related information even from the simplest variant of heuristic search is a very complicated task. Existing techniques such as distributed heuristic and sending only relevant states is shown to reduce the privacy leakage even more.

Automated planning for problems without an explicit model is an elusive research challenge. However, if tackled, it could provide a general approach to problems in real-world unstructured environments. There are currently two strong research directions in the area of artificial intelligence (AI), namely machine learning and symbolic AI. The former provides techniques to learn models of unstructured data but does not provide further problem solving capabilities on such models. The latter provides efficient algorithms for general problem solving, but requires a model to work with. Creating the model can itself be a bottleneck of many problem domains. Complicated problems require an explicit description that can be very costly or even impossible to create. In this paper, we propose a combination of the two areas, namely deep learning and classical planning, to form a planning system that works without a human-encoded model for variably scaled problems. The deep learning part extracts the model in the form of a transition system and a goal-distance heuristic estimator; the classical planning part uses such a model to efficiently solve the planning problem. Both networks in the planning system, we introduced, work with a problem in its graphic form and there is no need for any additional information to create the state transition system or to estimate a heuristic value. We proposed three different architectures for the heuristic estimator to compare different characteristics of well-known deep learning techniques. Besides the design of such planning systems, we provide experimental evaluation comparing the implemented techniques to classical model-based methods.

Multi-agent planning (MAP) has recently gained traction in both planning and multi-agent system communities, especially with the focus on privacy-preserving multi-agent planning, where multiple agents plan for a common goal but with private information they do not want to disclose. Heuristic search is the dominant technique used in MAP and therefore it is not surprising that a significant attention has been paid to distributed heuristic computation, either with or without the concern for privacy. Nevertheless, most of the distributed heuristic computation approaches published so far are ad-hoc algorithms tailored for the particular heuristic. In this work we present a general, privacy-preserving, and admissible approach to distributed heuristic computation. Our approach is based on an adaptation of the technique of cost partitioning which has been successfully applied in optimal classical planning. We present the general approach, a particular implementation, and an experimental evaluation showing that the presented approach is competitive with the state of the art while having the additional benefits of generality and privacy preservation.

Similarly to classical planning, heuristics play a crucial role in Multi-Agent Planning (MAP). Especially, the question of how to compute a distributed heuristic so that the information is shared effectively has been studied widely. This question becomes even more intriguing if we aim to preserve some degree of privacy, or admissibility of the heuristic. The works published so far aimed mostly at providing an ad-hoc distribution protocol for a particular heuristic. In this work, we propose a general framework for distributing heuristic computation based on the technique of cost partitioning. This allows the agents to compute their heuristic values separately and the global heuristic value as an admissible sum. We evaluate the presented techniques in comparison to the baseline of locally computed heuristics and show that the approach based on cost partitioning improves the heuristic quality over the baseline.