Cientistas do Departamento de Ciência da Computação do Instituto de Matemática e Estatística (IME) da USP estudam e desenvolvem soluções baseadas em técnicas de inteligência artificial que poderão ser aplicadas no controle de semáforos de grandes cidades, de aeroportos ou em robótica. “Problemas de planejamento probabilístico, como controlar mudanças dos semáforos poderiam ser modelados como um Markov Decision Process (MDP), um modelo probabilístico de transição de estados”, explica a professora Leliane Nunes Barros, do IME. “Mas há que se levar em conta as probabilidades de existirem muitos veículos em cada pista e de seguirem em frente ou virarem para a direita ou para a esquerda”, ressalta a pesquisadora.
Ela destaca que, para resolver esse problema de maneira robusta, é preciso considerar que essas probabilidades sejam imprecisas. “Por exemplo, que a probabilidade de um carro virar para a direita num determinado semáforo varia entre 30% e 50%”, descreve.
No IME, Leliane orientou um projeto de doutorado em que foi desenvolvido um novo modelo matemático para planejamento probabilístico. ”Levando-se em conta a imprecisão das probabilidades, podemos obter uma solução ótima, no pior caso, que chamamos de uma solução robusta diante da imprecisão sobre os efeitos probabilísticos de nossas ações”, afirma a professora.
A tese de doutorado Processos de Decisão Markovianos Fatorados com Probabilidades Imprecisas, de Karina Valdivia Delgado, desenvolve soluções inéditas para os chamados “Processos de Decisão Markovianos com Probabilidades Imprecisas” (MDPIP) Fatorado. “No MDPIP Fatorado são representadas as variáveis de estado ao invés de se fazer uma enumeração de todos os estados possíveis de um sistema, como é feito na abordagem clássica. Isto é, ao invés de tratarmos propriedades isoladas de um ambiente, como por exemplo, o semáforo da Av. Paulista com a Av. Consolação, na abordagem clássica teríamos que enumerar todas as possíveis configurações dos semáforos da cidade São Paulo”, explica Leliane.
MDP
A professora conta que a teoria sobre MDP foi proposta na década de 1960 e é muito usada para controle de sistemas. No entanto, no controle de semáforos é impossível modelar precisamente todas essas probabilidades, dado que elas podem variar durante o dia ou ao longo do ano com base nos feriados ou eventos especiais.
Já na década de 1970, uma nova extensão do modelo matemático MDP foi proposta por J.K. Satia. Ele foi denominado como Processos de Decisão Markovianos com Probabilidades Imprecisas (MDPIP) e permite o desenvolvimento de soluções eficientes para o problema de planejamento probabilístico. Uma versão fatorada e outra baseada em programação matemática do MDPIP, bem como um conjunto de soluções eficientes, foram desenvolvidas no grupo de Inteligência Artificial do IME, como parte do projeto temático FAPESP LOGPROB (Lógica e Probabilidades). Segundo Leliane, uma das aplicações do novo modelo pode ser, por exemplo, o controle dos semáforos de uma cidade como São Paulo, em que o tratamento de probabilidades imprecisas permite obter soluções robustas.
No estudo de Karina foram propostas quatro soluções fatoradas, sendo três delas baseadas em Programação Dinâmica e uma em Programação Matemática (mais especificamente, Programação Multilinear). ”As únicas soluções existentes até esse momento para um MDP com probabilidades imprecisas eram aquelas propostas por J.K. Satia, na década 1970 e uma solução ainda considerada ineficiente foi proposta na década de 1990 por C. C. White”, conta Karina.
Desafio
Esses Processos de Decisão Markovianos com Probabilidades Imprecisas deixaram de ser aplicados por muitas décadas devido à sua complexidade computacional: somente era possível resolver problemas pequenos, isto é, problemas envolvendo um número pequeno de estados. Karina ressalta ainda que sua pesquisa é parte de um projeto temático FAPESP e também faz parte de um projeto de controle de tráfego da cidade de Sidney, Austrália, financiado pelo centro de pesquisa australiano NICTA (Australia’s National ICT Research Centre of Excellence). A pesquisadora realizou parte de seu doutorado na sede do NICTA da cidade de Camberra na Austrália com suporte da Pró-Reitoria de Pesquisa da USP e do próprio NICTA.
Segundo Leliane, o controle de tráfego é apenas uma das possíveis aplicações desse trabalho. ”Podemos imaginar a utilização das soluções propostas por Karina em uma infinidade de problemas de planejamento probabilístico nos quais é impossível obter probabilidades precisas, como por exemplo, problemas complexos de logística e de controle de tráfego aéreo”.
Resultados
Karina defendeu seu doutorado em janeiro de 2010 pelo programa de Ciência da Computação do IME. Por suas contribuições inéditas, Karina recebeu em 2009 o prêmio internacional “Silver IJAR Young Researcher Award for demonstrating excellence in research on imprecise probabiities”, oferecido pelos editores do periódico da Elsevier, “International Journal of Approximate Reasoning”, numa chamada para participantes e indicações pela Internet.
Esse trabalho também recebeu o prêmio de Melhor Tese de Doutorado no Concurso de Teses e Dissertações do Simpósio Brasileiro de Inteligência Artificial, organizado pela Sociedade Brasileira de Computação (SBC), referente aos anos de 2009 e 2010. ”Esta é a segunda vez que um aluno do IME é premiado neste concurso”, comemora Leliane. Em 2008, outro orientando da pesquisadora, Silvio do Lago Pereira, também recebeu essa premiação, referente ao período de 2007 e 2008, com a tese entitulada ”Planejamento sob incerteza para metas de alcançabilidade estendidas”.
Autor: Agência USP
