Analysing State-based Models for AI Problems
Ionuţ Cristian Pistol, Andrei Arusoaie · Procedia Computer Science · 2021
AI problems which can be solved using a state-based model are a significant portion, covering most NP problems. Although the strategies required to solve such problems are well documented and researched, the model itself is seldom analysed, being considered either secondary or too abstract to tackle in a systematic analysis. Early languages such as PDDL and the many later variants, allow users to describe a state-based model and use a type of exhaustive strategy (usually BFS) to check if that model can solve a defined problem. More recently, SMT-bounded model checking solutions have been employed, a new, generalized approach is described in this paper. Another new contribution described in this paper uses a state classifier to group generated states and thus simplify an exhaustive search for a solution. This allows us to build a complete problem-space having each state within labelled as belonging or not to any path to the goal of the problem.