Advanced search
Start date

Describing, representing and solving spatial puzzles

Grant number: 16/18792-9
Support type:Research Grants - Research Partnership for Technological Innovation - PITE
Duration: August 01, 2017 - July 31, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Cooperation agreement: IBM Brasil
Principal researcher:Paulo Eduardo Santos
Grantee:Paulo Eduardo 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: IBM Brasil - Indústria, Máquinas e Serviços Ltda
City: São Bernardo do Campo
Assoc. researchers: Leonardo Anjoletto Ferreira ; Pedro Cabalar ; Reinaldo Augusto da Costa Bianchi
Associated scholarship(s):17/09675-1 - Diagrammatic reasoning for spatial problems, BP.MS
17/07833-9 - Heuristics and efficient planning for spatial problems, BP.MS


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 proposal aims the investigation of knowledge representation and reasoning methods related to the solution of a family of spatial puzzles composed by rigid objects, flexible strings and holes. The challenging aspects of this domain, not only reside in the appropriate commonsense formalization of non-standard spatial characteristics, such as the strings flexibility and the holes immateriality, but also on the efficient implementation of automated problem solvers capable of dealing with these characteristics. A constraint we impose on our solution space is that the formalization constructed should be capable of producing human-readable plans for solving the puzzles (such as the solution description usually found in the puzzles' leaflets). This project is expected to push forward the state-of-the-art in the treatment of non-trivial spatio-temporal problems that constitute the substratum of the basic mechanism of understanding (and solving) mathematical problems. 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 (an 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 \emph{challenge} for planning algorithms, since the states are described in terms of fluents whose number may “grow arbitrarily” (the string crossings may appear or disappear after each performed action). The present proposal shall follow a similar development route, but our main goal here will be on automate understanding of natural language descriptions of the domain and on the development of an efficient planner capable of providing solutions to the puzzles. Project's success will be measured by the completion of each of the work packages, each of which shall accompany a publication in a prestigious conference proceedings (such as IJCAI, KR, AAAI, or ECAI) or in a selective journal (such as the Artificial Intelligence Journal or the Journal of Artificial Intelligence Research). We also expect to have the successful completion of three master theses and the (GNU General Public License) registration of a software for solving spatial problems (a planner). (AU)

Articles published in Pesquisa FAPESP Magazine about the research grant:
Alta productividad 
Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (9)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
DOS SANTOS, THIAGO FREITAS; SANTOS, PAULO E.; FERREIRA, LEONARDO ANJOLETTO; BIANCHI, REINALDO A. C.; CABALAR, PEDRO. euristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles{*. APPLIED INTELLIGENCE, v. 52, n. 4, . (16/21047-3, 17/07833-9, 16/18792-9)
FERREIRA, LEONARDO A.; BIANCHI, REINALDO A. C.; SANTOS, PAULO E.; LOPEZ DE MANTARAS, RAMON. Answer set programming for non-stationary Markov decision processes. APPLIED INTELLIGENCE, v. 47, n. 4, p. 993-1007, . (16/21047-3, 11/19280-8, 16/18792-9)
PERICO, DANILO H.; HOMEM, THIAGO P. D.; ALMEIDA, AISLAN C.; SILVA, ISAAC J.; VILAO, JR., CLAUDIO O.; FERREIRA, VINICIUS N.; BIANCHI, REINALDO A. C.. Humanoid Robot Framework for Research on Cognitive Robotics. JOURNAL OF CONTROL AUTOMATION AND ELECTRICAL SYSTEMS, v. 29, n. 4, p. 470-479, . (16/21047-3, 16/18792-9)
RODRIGUES, EDILSON J.; SANTOS, PAULO E.; LOPES, MARCOS; BENNETT, BRANDON; OPPENHEIMER, PAUL E.. Standpoint semantics for polysemy in spatial prepositions. JOURNAL OF LOGIC AND COMPUTATION, v. 30, n. 2, p. 635-661, . (18/11255-3, 16/18792-9)
SANTOS, PAULO E.; CABALAR, PEDRO; CASATI, ROBERTO. The knowledge of knots: an interdisciplinary literature review. Spatial Cognition and Computation, v. 19, n. 4, p. 334-358, . (16/18792-9)
BIANCHI, REINALDO A. C.; SANTOS, PAULO E.; DA SILVA, ISAAC J.; CELIBERTO, JR., LUIZ A.; DE MANTARAS, RAMON LOPEZ. Heuristically Accelerated Reinforcement Learning by Means of Case-Based Reasoning and Transfer Learning. JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS, v. 91, n. 2, SI, p. 301-312, . (16/21047-3, 16/18792-9)
DONADON HOMEM, THIAGO PEDRO; PERICO, DANILO HERNANI; SANTOS, PAULO EDUARDO; DA COSTA BIANCHI, REINALDO AUGUSTO; LOPEZ DE MANTARAS, RAMON. Retrieving and reusing qualitative cases: An application in humanoid-robot soccer. AI COMMUNICATIONS, v. 30, n. 3-4, SI, p. 251-265, . (16/18792-9)
GLATT, RUBEN; DA SILVA, FELIPE LENO; DA COSTA BIANCHI, REINALDO AUGUSTO; REALI COSTA, ANNA HELENA. DECAF: Deep Case-based Policy Inference for knowledge transfer in Reinforcement Learning. EXPERT SYSTEMS WITH APPLICATIONS, v. 156, . (16/21047-3, 15/16310-4, 18/00344-5, 16/18792-9)

Please report errors in scientific publications list by writing to: