Heuristics and efficient planning for spatial problems

• Grant number: 17/07833-9
• Support Opportunities: Scholarships in Brazil - Master
• Start date: July 01, 2017
• End date: February 28, 2019
• Field of knowledge: Engineering - Electrical Engineering
• Agreement: IBM Brasil
• Principal Investigator: Paulo Eduardo Santos
• Grantee: Thiago Freitas dos Santos
• Host Institution: Centro Universitário FEI (UNIFEI). Campus de São Bernardo do Campo. São Bernardo do Campo , SP, Brazil
• Company: Centro Universitário FEI (UNIFEI). Campus de São Bernardo do Campo
• Associated research grant: 16/18792-9 - Describing, representing and solving spatial puzzles, AP.PITE

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 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)

Scientific publications

(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, JUL 2021. (16/21047-3, 17/07833-9, 16/18792-9)

FERREIRA, LEONARDO A.; DOS SANTOS, THIAGO F.; BIANCHI, REINALDO A. C.; SANTOS, PAULO E.; LIU, J; BAILEY, J. Solving Safety Problems with Ensemble Reinforcement Learning. AI 2019: ADVANCES IN ARTIFICIAL INTELLIGENCE, v. 11919, p. 12-pg., 2019-01-01. (19/07665-4, 17/07833-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., 2018-01-01. (17/07833-9, 16/18792-9, 16/21047-3)