Computational Aspects of Reasoning about Dynamic Systems

点击翻译按钮获取中文摘要

An important part of practical problems, and AI problems in particular, e.g. scheduling, diagnosis, planning and synthesis of reactive agents, are search problems. In many applications, some explicit data, that changes over time, is present. This setting is prevalent, e.g., in medical domains and in business process modelling. The data is, typically, large, and changes over time, and the problems are computationally hard. The representation of the problem must be such that reasoning algorithms could be executed efficiently with respect to the size of the data. In some applications, complexity of the algorithms may also depend on the size of the formula. An intriguing question is under what conditions on the specification language the problem definitely has an efficient algorithm. If the conditions are understood, then a specification language with a complexity guarantee can be developed. I plan to develop theoretical foundations and understand general principles, of the conditions for efficient computations. This foundational research will help us to develop practical algorithms. The algorithms will automate problem solving starting from a high-level specification written by the user, thus assisting in these intellectually challenging tasks. My research is about how to bridge the gap between user and advanced technology, and it is within the overall trend of replacing human services with exciting AI applications. The research leads towards making solving a large proportion of such problems accessible to a non-specialist user thus reducing the overall cost to the society and achieving a significant socio-economic benefit.