Halpern-Shoham Logic and its Fragments

Halpern-Shoham logic (HS) is an elegant interval-based temporal logic that introduces one modal operator for each of the well-known Allen relations. The Allen relations form a jointly exhaustive and pairwise disjoint set of binary relations between nonidentical intervals, namely: begins, during, ends, overlaps, adjacent to, later than, and their inverses. The logic is highly expressive, and undecidable for the most of the interesting linear orders of time points.

My research is focused on expressive power and computational complexity of sub-propositional HS languages such as Horn and core. Moreover, I am interested in their hybrid extensions.

Computational Spatial Reasoning Framework

This is a joint work with M. Bhatt and C. Schultz on spatial and spatio-temporal reasoning framework based on a paradigm of Answer Set Programming Modulo Theories. Our, so-called ASPMT(QS) framework enables to perform hybrid qualitative-quantitative reasoning in contexts of nonmonotonic spatial and spatio-temporal reasoning. It is able to compute indirect and counterfactual effects, use default rules and perform spatial planning. Spatial (and spatio-temporal) relations are encoded as polynomial constraints and as a result the framework enables to express a number of relations from the well-known qualitative spatial reasoning (QSR) approaches (e.g., Interval Algebra, Rectangle Algebra, Region Connection Calculus, Cardinal Directions Calculus).

ASPMT(QS) and other spatial frameworks are vailable at www.spatial-reasoning.com.

Artificial Intelligence in Computer Games

The work on an AI program autonomously playing Angry Birds computer game has been accomplished together with M. Zawidzki and T. Lechowski. The program represents objects from a gameplay scene by means of such qualitative relations as "X touches Y", "X lies on Y", "X is a shelter for Y", etc. The main part of the reasoning algorithm consists of a method that enables to compute effects of disappearing objects. In particular, it predicts which blocks will become unstable and will fall down. As a result, the program is able to chose the most valuable shots and successfully play new (never seen before) Angry Birds levels.

The program competed with teams from 12 different countries from 3 continents during Angry Birds AI Competition and won the 5th place.

The developed algorithms are described in a IEEE journal paper Qualitative Physics in Angry Birds.

For a description of AI in Angry Birds Competition see a short movie.