Busca avançada
Ano de início
Entree

PROVERBS -- Sistemas Booleanos Probabilísticos Super-restritos: ferramentas de raciocínio e aplicações

Processo: 15/21880-4
Modalidade de apoio:Auxílio à Pesquisa - Regular
Vigência: 01 de abril de 2016 - 30 de setembro de 2018
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação
Pesquisador responsável:Marcelo Finger
Beneficiário:Marcelo Finger
Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Pesquisadores associados:Denis Deratani Mauá ; Fabio Gagliardi Cozman
Assunto(s):Inteligência artificial 
Palavra(s)-Chave do Pesquisador:Inteligência Artificial | MaxSAT (Máxima satisfatibilidade) | Medidas de Inconsistência | PSAT (satisfatibilidade probabilística) | Raciocínio Lógico-Probabilístico | SAT (Satisfatibilidade Booleana) | Inteligência Artificial

Resumo

A solução de problemas computacionais envolvendo objetos do mundo necessita conciliar modelos rigorosos com informações imperfeitas e flexíveis coletadas sobre o mundo. Assim, o método de solução deste tipo de problema deve ser capaz de lidar tanto com as rígidas asserções sobre o mundo quanto com o fluxo e informações cujo natureza é muito menos rígida. A capacidade de tratar de tal situação nos permitirá lidar com dispositivos computacionais inseridos num mundo em que, o fluxo de informações está constantemente mudando, de forma imprecisa e incerta.Este projeto estuda os problemas que se combinam restrições rígidas com restrições flexíveis envolvendo preferências, incertezas e exigências maleáveis. Neste trabalho, as restrições rígidas são representadas por conjuntos de fórmulas booleanas. As restrições flexíveis podem assumir a forma de pesos numéricos associados a algumas fórmulas booleanas. E a solução do problema trata de encontrar um conjunto de fórmulas que pode ser satisfeita de forma a maximizar o valor total associado às restrições satisfeitas. Esta abordagem é chamada de máxima satisfatibilidade (MaxSAT) para o problema de tratar de restrições rígidas e flexíveis. Outra maneira de modelar restrições flexíveis é associar probabilidades a algumas das fórmulas, caso em que a solução do conjunto total de restrições é um distribuição de probabilidade sobre os modelos que atendem às restrições rígidas, que também verifique as restrições flexíveis de probabilidade. Esta abordagem é chamada de satisfatibilidade probabilística (PSAT) para restrições rígidas e flexíveis.Em muitas situações, as técnicas de modelagem rígido-flexível de restrições booleanas podem levar a formulações super-restritivas, isto é, um conjunto de restrições para as quais nenhuma interpretação consistente é possível. Importantes aplicações podem ser modeladas por formulações super-restritivas de condições rígido-flexíveis em diversas áreas, dentre as quais serão exploradas neste projeto: segurança de informações, verificação de protocolos e planejamento, e linguística computacional.A natureza dessas restrições nos colocam no centro da classe de problemas computacionais intratáveis conhecida como NP-difíceis, para a qual nenhum algoritmo geral eficiente é conhecido, mas para o qual muitas instâncias de solução simples foram descobertas nos últimos anos. Acreditamos que uma fertilização cruzada entre essas duas abordagens pode levar a um progresso significativo no tratamento computacional de restrições rígido-flexíveis. Ao combinar a experiência de pesquisadores de alto nível em ambas abordagens, este projeto tem como objetivo principal a levar as técnicas e aplicações desta área a um novo patamar.Planejamos desenvolver vários algoritmos para lidar com problemas MaxSAT e PSAT, incluindo o tratamento de PSAT usando MaxSAT. Em seguida, planejamos aplicar essas técnicas na solução de formulações super-restritivas. Os programas desenvolvidos serão disponibilizados como software livre de código aberto. Vamos desenvolver aplicações destas técnicas e algoritmos abrangendo as áreas de segurança da informação, verificação de protocolos e linguística computacional .Este projeto apresenta o lado brasileiro de uma colaboração de pesquisa entre grupos de pesquisa com base em duas universidades em Portugal e no Brasil que visam estudar esses métodos e abordagens para explorar o problema de formulações probabilísticas super-restritivas. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas (5)
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
COZMAN, FABIO GAGLIARDI; MAUA, DENIS DERATANI. The finite model theory of Bayesian network specifications: Descriptive complexity and zero/one laws. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 110, n. SI, p. 107-126, . (16/18841-0, 15/21880-4)
DE FARIA, FRANCISCO H. O. VIEIRA; GUSMAO, ARTHUR COLOMBINI; DE BONA, GLAUBER; MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Speeding up parameter and rule learning for acyclic probabilistic logic programs. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 106, p. 32-50, . (17/19007-6, 16/18841-0, 16/25928-4, 16/01055-1, 15/21880-4)
COZMAN, FABIO GAGLIARDI. Evenly convex credal sets. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 103, p. 124-138, . (16/18841-0, 15/21880-4)
MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Complexity results for probabilistic answer set programming. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 118, p. 133-154, . (16/18841-0, 19/07665-4, 15/21880-4)

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.