Advanced search
Start date

Heuristics and efficient planning for spatial problems

Grant number: 17/07833-9
Support type:Scholarships in Brazil - Master
Effective date (Start): July 01, 2017
Effective date (End): February 28, 2019
Field of knowledge:Engineering - Electrical Engineering
Cooperation agreement: IBM Brasil
Principal Investigator:Paulo Eduardo Santos
Grantee:Thiago Freitas dos Santos
Home Institution: Campus de São Bernardo do Campo. Centro Universitário da FEI (UNIFEI). Fundação Educacional Inaciana Padre Sabóia de Medeiros (FEI). São Bernardo do Campo , SP, Brazil
Company:Fundação Educacional Inaciana Padre Sabóia de Medeiros (FEI). Centro Universitário da FEI (UNIFEI). Campus de São Bernardo do Campo
Associated research grant:16/18792-9 - Describing, representing and solving spatial puzzles, AP.PITE


Understanding the reasoning processes involved in spatial knowledge is one of the key issues in the investigation of human cognition, as space not only shapes our actions in the commonsense world, but also serves as the scenario in which our everyday experiences take place. The present MSc proposal is part of a larger project which aims at the investigation of knowledge representation and reasoning methods related to the solution of a family of spatial puzzles composed of rigid objects, exible strings and holes (Proc. FAPESP 2016/18792-9). The challenging aspects of this domain, not only reside in the appropriate commonsense formalization of non-standard spatial characteristics, such as the strings exibility and the hole's immateriality, but also on the efficient implementation of automated problem solvers capable of dealing with these characteristics. Our methodology, applied along a series of papers, has consisted in a bottom-up strategy, starting from a very restrictive set of constraints and gradually relaxing them to cover puzzles with more challenging features. For instance, initial efforts were put into solving a basic spatial puzzle with strings, holes and rigid objects using a list-based representation of string crossings. This work eventually led to an extensive work containing a complete logical formalization in terms of Situation Calculus and Equilibrium Logic (a Non-Monotonic Reasoning approach generalizing the stable model semantics for logic programs). That work also included a preliminary planner capable of solving the puzzle in an automated way. This domain constitutes a challenge for planning algorithms, since the states are described in terms of uents whose number may "grow arbitrarily" (the string crossings may appear or disappear after each performed action). The goal of the present proposal is to tackle the planning problem in these puzzles solving domains by means of a novel algorithm that provides efficient solutions to Markov decision processes with high-level constraints. (AU)