Titulo Estágio
MinHyp - Motor de Raciocínio sobre Bases de Conhecimento de Regras
Área Tecnológica
Inteligência Artificial
Local do Estágio
DEI-FCTUC
Enquadramento
Embora pouco conhecida por algumas comunidades da computação, a Programação em Lógica tem sido, desde há várias décadas, uma das mais bem sucedidas técnicas para Representação de Conhecimento e Raciocínio usada no desenvolvimento de sistemas inteligentes e está no centro de aplicações com fins tão diversos como planeamento, procura, resolução de restrições, diagnóstico, exploração de cenários hipotéticos, entre muitos outros.
Os Programas Lógicos (PLs) consistem em conjuntos de regras lógicas do género “if-then” que usam negação por omissão — um tipo de negação não-monotónica, diferente da negação clássica, que é o ingrediente característico dos PLs, e que lhes confere a capacidade de modelar raciocínio correcto mesmo perante informação incerta ou incompleta sem necessidade de quantificação da incerteza. Os PLs são também usados como Bases de Conhecimento dedutivas, com um poder expressivo diferente das tradicionais Bases de Dados Relacionais.
A linguagem Prolog é uma das mais conhecidas representantes deste paradigma de programação, mas os sistemas existentes apenas permitem efectuar raciocínios e responder a queries com determinadas classes de PLs. Contudo, o completo poder expressivo da programação em lógica só pode ser explorado recorrendo exactamente aos tipos de PLs que não são usáveis por sistemas Prolog. Nas últimas duas décadas desenvolveram-se, tanto novos resultados teóricos como implementações práticas de sistemas [1,2,3,4], que lidam com mais tipos de PLs, mas falta ainda um sistema que consiga lidar com todos.
Recentes resultados teóricos [5,6] descrevem o sistema que falta, as suas propriedades, e propõem os algoritmos necessários, apenas falta agora uma implementação, demonstração e comparação de resultados e de performance relativos a outros sistemas já existentes.
Este projecto é a primeira parte de um plano de trabalho maior que conduzirá à implementação e disseminação de um sistema híbrido de Representação de Conhecimento e Raciocínio que combinará o poder das ontologias (expressas numa Description Logic [7]) com PLs. Neste sistema maior, o raciocínio com a parte da ontologia será delegado em sistemas dedicados já existentes, como [8,9,10].
Este tipo de sistemas híbridos darão um contributo para a realização da Web Semântica, nomeadamente nas camadas de Logic e Proof.
[1] The Smodels System, by T. Syrjänen, I Niemelä - In Proceedings of LPNMR, 2001
[2] Smodels: An implementation of the stable model and well-founded semantics for normal logic programs, by I. Niemelä, P. Simons - In Proceedings of LPNMR, 1997
[3] The DLV system for knowledge representation and reasoning, by N. Leone, W. Faber, G. Pfeifer, T. Eiter, G. Gottlob, S. Perri, F. Scarcello - ACM Transactions on Computational Logic, 2002
[4] clasp: A conflict-driven answer set solver, by M. Gebser, B. Kaufmann, A. Neumann, T. Schaub - In Proceedings of LPNMR, 2007
[5] Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations, by A. M. Pinto - PhD thesis, Universidade Nova de Lisboa, 2011
[6] Every normal logic program has a 2-valued minimal hypotheses semantics, by A. M. Pinto and L. M. Pereira. - In Proceedings of EPIA, 2011
[7] The Description Logic Handbook — Theory, Implementation and Applications, 2nd Edition, Edited by: F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider, ISBN:9780521876254, 2007
[8] http://clarkparsia.com/pellet
[9] http://owl.man.ac.uk/factplusplus/
[10] http://hermit-reasoner.com/
Objetivo
O principal objectivo deste trabalho de Mestrado é desenhar e desenvolver um interpretador eficiente de Programas Lógicos Normais com Restrições de Integridade e respectivo motor de raciocínio e de resposta a queries, segundo uma variante da semântica de Hipóteses Mínimas. Para tal, o trabalho encontra-se dividido nos seguintes sub-objectivos:
1. Aprendizagem e Análise de Requisitos: ao longo de uma série de curtas sessões tutoriais com o orientador, o aluno irá adquirir os conceitos básicos de programação em lógica necessários para a realização do trabalho e que irão auxiliar no processo de análise de requisitos;
2. Design: especificação da arquitectura da aplicação, suas componentes e interfaces, estruturas de dados e algoritmos necessários para cumprir todos os requisitos;
3. Implementação, usando a linguagem de programação C e ferramentas de processamento de linguagens (e.g., Yacc, Lex), da ferramenta previamente desenhada;
4. Validação de correcção do interpretador e motor de raciocínio e de resposta a queries contra a especificação;
5. Comparação da performance do sistema contra ferramentas existentes [4,5,6,7] para resolver problemas compatíveis com esses sistemas;
6. Publicação: para além da escrita da tese e de um breve manual do utilizador, espera-se a submissão de um artigo científico para publicação descrevendo o sistema implementado e sumarizando os principais resultados.
Com estes objectivos espera-se que o(a) aluno(a) participe na escrita do artigo que pode vir a ser o início de uma carreira de investigação.
Plano de Trabalhos - Semestre 1
Para cumprir os objectivos acima, o trabalho será dividido nas seguintes tarefas:
Tarefa T1 — Aprendizagem e Requisitos
* Período: Setembro 2013
* Descrição: Aprendizagem dos conceitos básicos de programação em lógica (sintaxe e semântica). Identificação de todos os requisitos para o interpretador e motor de raciocínio. Instalação de sistemas alternativos para as comparações de performance finais.
* Output: Especificação de Requisitos. Primeiras versões das subsecções de “Background”, “Motivation” e “Objectives” da secção “Introduction” do artigo a ser submetido.
Tarefa T2 — Design
* Período: Outubro-Novembro 2013
* Descrição: Especificação da arquitectura da aplicação. Especificação dos analisadores léxical e sintáctico do interpretador. Especificação das estruturas de dados e algoritmos necessários para implementar todos os mecanismos de raciocínio cumprindo todos os requisitos. Definição de objectivos intermédios e plano detalhado.
* Output: Arquitectura. Primeira versão da secção “Approach” do artigo a ser submetido. Plano de trabalho detalhado.
Tarefa T3 — Relatório intermédio
* Período: Dezembro 2013
* Descrição: Escrita do Relatório intermédio.
* Output: Relatório intermédio
Plano de Trabalhos - Semestre 2
Tarefa T4 — Revisões
* Período: Janeiro 2014
* Descrição: Ajustamento do plano de trabalhos e revisão do relatório incluindo as indicações do júri da defesa intermédia.
* Output: Objectivos, relatório e plano de trabalhos detalhado revistos.
Tarefa T5 — Implementação e Validação
* Período: Janeiro-Abril 2014
* Descrição: Implementação do interpretador e do motor de raciocínio.
* Output: Sistema implementado, testado e validado. Primeira versão da descrição da secção “Implementation Principles” do artigo a ser submetido.
Tarefa T6 — Comparação e Publicação
* Período: Abril-Maio 2014
* Descrição: Comparação de performance entre a ferramenta desenvolvida e outras ferramentas já existentes, tais como Smodels, DLV, e Clasp, para problemas compatíveis com esses sistemas e para respostas a queries. Escrita e submissão da versão final do artigo.
* Output: Comparação detalhada de performance. Primeira versão da secção “Comparisons” do artigo a ser submetido. Versão final do artigo a ser submetido.
Tarefa T7 — Escrita da Tese
* Período: Janeiro-Maio 2014
* Descrição: Escrita do documento da Tese
* Output: Tese de Mestrado
Condições
O trabalho decorrerá no DEI-FCT-UC, sendo que o(a) aluno(a) usará o seu próprio computador portátil.
Observações
Os candidatos deverão cumprir os seguintes requisitos mínimos:
* Conhecimentos sólidos sobre compiladores e interpretadores e respectivas tecnologias e linguagens
* Excelentes conhecimentos de algoritmos eficientes sobre grafos
* Excelentes conhecimentos de programação com a linguagem C
* Fluência em inglês
Orientador
Alexandre Miguel Pinto
ampinto@dei.uc.pt 📩