Grant: Discovery Grants Program - Individual

Reasoning is a fundamental cognitive ability, and it comes as no surprise that Artificial Intelligence, whose objective is to reproduce, and enhance, human cognitive abilities, has developed computational reasoning approaches. However, reasoning comes in many forms. For instance, in the last decades, propositional logic-based approaches have shown impressive performance on constraint processing, where one aims at finding a solution fulfilling some constraints in a process similar to puzzle solving. Still, there are more involved reasoning tasks that are of human interest, such as those of an interactive nature, encountered, for instance, in games. Board games, where seemingly simple rules lead to intricate interactions between players aiming at conflicting goals, have fascinated the human mind for centuries. But reasoning on multiple options anticipating opposing decisions is also ubiquitous in computing applications. For instance, communication protocols have participants interacting toward their own goals. Similarly, computing security aims at safeguarding computing assets while interacting with the outside world even under hostile actions. This research proposal will devise propositional logic based methods to effectively realize interactive reasoning with computing means. This will therefore impact and advance game playing in Artificial Intelligence, game analysis in combinatorics, and computing security, where such reasoning tasks are ubiquitous. In order to reach this objective, my Discovery research program's objectives will develop effective Quantified Boolean Formula (QBF) encodings for interactive settings as this will allow to efficiently represent the reasoning task. Current research shows that making the best of state-of-the-art algorithms is challenging and this program will innovate in that it will systematically evaluate a broad spectrum of encodings. My program is also original in that these encodings will be applied to many games and interactive settings to which QBF methods have not been applied up to now. Furthermore, a novel and innovative aspect of this program is to determine the most performing processing algorithmic aspects, beyond usual performance comparisons. This will open up new avenues by identifying critical algorithmic aspects of efficient processing. The computing research community is looking forward to new methods that will unleash the full power of algorithmic interactive reasoning. By contributing to this goal, my Discovery research proposal will train Highly Qualified Personnel (HQP), 5 PhDs, 3 master's and up to 5 undergraduates, that will contribute to Canada's knowledge economy. Indeed, besides their academic contributions these HQPs will transfer to the industry advanced skillsets to effectively process interactive behaviours such as those encountered in games and computing security.