Algoritmos Eficientes para Tomada de Decisão sob Incerteza Baseada em Grafos

• Processo: 13/23197-4
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Vigência (Início): 01 de março de 2014
• Vigência (Término): 16 de março de 2015
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Sistemas de Computação
• Pesquisador responsável: Fabio Gagliardi Cozman
• Beneficiário: Denis Deratani Mauá
• Instituição Sede: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Raciocínio probabilístico Inteligência artificial Tomada de decisão Sistemas especialistas
• Palavra(s)-Chave do Pesquisador: modelos probabilísticos gráficos | Raciocínio Probabilístico | Sistemas Especialistas | Tomada de Decisão | Inteligência Artificial

Resumo

Diagramas de influência são modelos probabilísticos baseados em grafos utilizados na representação de problemas de tomada de decisão sob incerteza. Tais diagramas permitem a comunicação clara de situações complexas de tomada de decisão, e constituem uma das principais ferramentas para a análise probabilística de problemas de decisão estruturados. Resolver um diagrama de influência significa encontrar um conjunto ótimo de regras que mapeiam observações em ações, de forma a prescrever o comportamento de um agente racional. Essa tarefa é NP-difícil mesmo quando o problema de decisão exibe uma estrutura gráfica simples. Não surpreende, portanto, que os algoritmos atuais de resolução de tais diagramas foquem ou exclusivamente o tempo de execução, em detrimento da acurácia da solução encontrada, ou exclusivamente a acurácia dos resultados, em detrimento do tempo de execução. Esses algoritmos são insatisfatórios, pois arriscam ou obter respostas arbitrariamente ruins ou exceder a quantidade de recursos computacionais disponíveis. Ambos os casos podem ser críticos para o desempenho de aplicações reais. Por exemplo, um controlador de um robô móvel deve encontrar uma trajetória de qualidade satisfatória em um curto período de tempo para que seja viável. Violar qualquer dessas premissas pode levar a um comportamento catastrófico para o robô, como chocar-se com um objeto. Portanto, faz-se necessária a criação de algoritmos que sejam capazes de garantir uma certa qualidade mínima das soluções encontradas utilizando-se de uma certa quantidade máxima de recursos computacionais, dessa forma permitindo ao usuário balancear eficiência e acurácia de acordo com suas necessidades. Este projeto visa o desenvolvimento de algoritmos de resolução de diagramas de influência de memória finita que permitam tais compromissos entre eficiência e acurácia.

Publicações científicas

(4)

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

MAUA, DENIS DERATANI. Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 68, p. 211-229, JAN 2016. (13/23197-4)

MAUA, DENIS DERATANI; COZMAN, FABIO GAGLIARDI. Fast local search methods for solving limited memory influence diagrams. INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, v. 68, p. 230-245, JAN 2016. (13/23197-4)

MAUA, DENIS DERATANI; ANTONUCCI, ALESSANDRO; DE CAMPOS, CASSIO POLPO. Hidden Markov models with set-valued parameters. Neurocomputing, v. 180, n. SI, p. 94-107, MAR 5 2016. (13/23197-4)

MAUA, DENIS DERATANI; DE CAMPOS, CASSIO P.; BENAVOLI, ALESSIO; ANTONUCCI, ALESSANDRO. Probabilistic Inference in Credal Networks: New Complexity Results. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, v. 50, p. 603-637, 2014. (13/23197-4)