Advanced search
Start date
Betweenand

Describing, representing and solving spatial puzzles

Grant number: 16/18792-9
Support Opportunities:Research Grants - Research Partnership for Technological Innovation - PITE
Duration: August 01, 2017 - July 31, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Convênio/Acordo: IBM Brasil
Principal Investigator:Paulo Eduardo Santos
Grantee:Paulo Eduardo Santos
Host Institution: Centro Universitário FEI (UNIFEI). Campus de São Bernardo do Campo. São Bernardo do Campo , SP, Brazil
Host Company: IBM Brasil - Indústria, Máquinas e Serviços Ltda
City: São Bernardo do Campo
Associated 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

Abstract

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 Agência FAPESP Newsletter about the research grant:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications (18)
(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)
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)
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, p. 15-pg., . (16/18792-9)
ALMEIDA, AISLAN C.; NETO, SYLVIO R. J.; BIANCHI, REINALDO A. C.; DONASCIMENTO, TP; COLOMBINI, EL; DEBRITO, AV; GARCIA, LTD; SA, STD; GONCALVES, LMG. Comparing Vision-based Monte-Carlo Localization Methods. 15TH LATIN AMERICAN ROBOTICS SYMPOSIUM 6TH BRAZILIAN ROBOTICS SYMPOSIUM 9TH WORKSHOP ON ROBOTICS IN EDUCATION (LARS/SBR/WRE 2018), v. N/A, p. 6-pg., . (16/21047-3, 16/18792-9)
FERREIRA, VINICIUS N.; NETO, SYLVIO R. J.; ALMEIDA, AISLAN C.; BIANCHI, REINALDO A. C.; DONASCIMENTO, TP; COLOMBINI, EL; DEBRITO, AV; GARCIA, LTD; SA, STD; GONCALVES, LMG. A Visual Memory System for Humanoid Robots. 15TH LATIN AMERICAN ROBOTICS SYMPOSIUM 6TH BRAZILIAN ROBOTICS SYMPOSIUM 9TH WORKSHOP ON ROBOTICS IN EDUCATION (LARS/SBR/WRE 2018), v. N/A, p. 6-pg., . (16/21047-3, 16/18792-9)
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)
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)
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, . (11/19280-8, 16/18792-9, 16/21047-3)
SANTOS, PAULO E.; CASATI, ROBERTO; CAVANAGH, PATRICK. Perception, cognition and reasoning about shadows. Spatial Cognition and Computation, v. 18, n. 2, p. 8-pg., . (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)
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)
DONADON HOMEM, THIAGO PEDRO; SANTOS, PAULO EDUARDO; REALI COSTA, ANNA HELENA; DA COSTA BIANCHI, REINALDO AUGUSTO; DE MANTARAS, RAMON LOPEZ. Qualitative case-based reasoning and learning. ARTIFICIAL INTELLIGENCE, v. 283, . (16/18792-9)
FERREIRA, LEONARDO ANJOLETTO; BIANCHI, REINALDO A. C.; SANTOS, PAULO E.; LOPEZ DE MANTARAS, RAMON; MOUHOUB, M; SADAOUI, S; MOHAMED, OA; ALI, M. A Method for the Online Construction of the Set of States of a Markov Decision Process Using Answer Set Programming. RECENT TRENDS AND FUTURE TECHNOLOGY IN APPLIED INTELLIGENCE, IEA/AIE 2018, v. 10868, p. 13-pg., . (16/18792-9)
HOMEM, THIAGO P. D.; PERICO, DANILO H.; SANTOS, PAULO E.; COSTA, ANNA H. R.; BIANCHI, REINALDO A. C.; DE MANTARAS, RAMON LOPEZ; TODT, E; TONIDANDEL, F. A hybrid approach to learn, retrieve and reuse qualitative cases. 2017 LATIN AMERICAN ROBOTICS SYMPOSIUM (LARS) AND 2017 BRAZILIAN SYMPOSIUM ON ROBOTICS (SBR), v. N/A, p. 6-pg., . (16/21047-3, 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)
DOS SANTOS, THIAGO FREITAS; SANTOS, PAULO E.; FERREIRA, LEONARDO A.; BIANCHI, REINALDO A. C.; CABALAR, PEDRO; IEEE. Solving a spatial puzzle using Answer Set Programming integrated with Markov Decision Process. 2018 7TH BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS), v. N/A, p. 6-pg., . (17/07833-9, 16/18792-9, 16/21047-3)
HOMEM, THIAGO P. D.; PERICO, DANILO H.; SANTOS, PAULO E.; COSTA, ANNA H. R.; BIANCHI, REINALDO A. C.; IEEE. Improving Reinforcement Learning results with Qualitative Spatial Representation. 2017 6TH BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS), v. N/A, p. 6-pg., . (16/18792-9, 16/21047-3)
BIANCHI, REINALDO A. C.; SANTOS, PAULO E.; DA SILVA, ISAAC J.; CELIBERTO, LUIZ A., JR.; 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, p. 12-pg., . (16/21047-3, 16/18792-9)

Please report errors in scientific publications list using this form.
X

Report errors in this page


Error details: