Heurística e planejamento eficiente para problemas espaciais

Resumo

Entender o raciocínio por trás do processo envolvido em conhecimento espacial é um dos pontos principais no estudo da cognição humana, já que espaço não é responsável apenas por ações comumente realizadas por nós, mas também serve como cenário onde nossas experiências diárias acontecem. Esta proposta de Mestrado é parte de um projeto maior que tem como objetivo o estudo da representação do conhecimento e Raciocínio Automático com a solução de uma família de problemas espaciais compostos por objetos rígidos, cordas flexíveis e buracos (Proc. FAPESP 2016/18792-9). Os aspectos desafiadores desse domínio, não estão apenas na formalização apropriada de características espaciais que estão fora do padrão, como a flexibilidade das cordas e a imaterialidade do buraco, mas também na implementação eficiente de solucionadores automáticos capazes de lidar com essas características.Nossa metodologia, aplicada em uma série de artigos, baseia-se em uma estratégia incremental, onde começa-se de um conjunto muito restritivo de limitações e vai relaxando-as gradualmente afim de considerar problemas com características mais desafiadoras. Por exemplo, inicialmente focou-se em resolver um quebra-cabeça básico constituído de cordas, buracos e objetos rígidos, para isso usou-se uma representação em lista dos cruzamentos de cordas. Com esse extensivo trabalho foi possível chegar em uma formalização lógica completa em termos de Cálculo Situacional e Lógica de Equilíbrio (Equilibrium Logic). Esse trabalho também incluiu uma planejador preliminar que é capaz de resolver quebra-cabeças automaticamente. Esse domínio constitui um desafio para algoritmos planejadores, já que os estados são descritos em termos de fluentes cujo número pode crescer arbitrariamente (os cruzamentos de cordas podem aparecer e desaparecer após cada ação realizada). Sendo assim, o objetivo desta proposta é trabalhar com o problema de planejamento nesses domínios de quebra-cabeças fazendo-se uso de algoritmos atuais que provêm soluções eficientes para processos de decisão de Markov com limitações de alto nível. (AU)