Cientistas do Departamento de Ci\u00eancia da Computa\u00e7\u00e3o do Instituto de Matem\u00e1tica e Estat\u00edstica (IME) da USP estudam e desenvolvem solu\u00e7\u00f5es baseadas em t\u00e9cnicas de intelig\u00eancia artificial que poder\u00e3o ser aplicadas no controle de sem\u00e1foros de grandes cidades, de aeroportos ou em rob\u00f3tica. \u201cProblemas de planejamento probabil\u00edstico, como controlar mudan\u00e7as dos sem\u00e1foros poderiam ser modelados como um Markov Decision Process (MDP), um modelo probabil\u00edstico de transi\u00e7\u00e3o de estados\u201d, explica a professora Leliane Nunes Barros, do IME. \u201cMas h\u00e1 que se levar em conta as probabilidades de existirem muitos ve\u00edculos em cada pista e de seguirem em frente ou virarem para a direita ou para a esquerda\u201d, ressalta a pesquisadora.<\/p>\n
Ela destaca que, para resolver esse problema de maneira robusta, \u00e9 preciso considerar que essas probabilidades sejam imprecisas. \u201cPor exemplo, que a probabilidade de um carro virar para a direita num determinado sem\u00e1foro varia entre 30% e 50%\u201d, descreve. <\/p>\n
No IME, Leliane orientou um projeto de doutorado em que foi desenvolvido um novo modelo matem\u00e1tico para planejamento probabil\u00edstico. \u201dLevando-se em conta a imprecis\u00e3o das probabilidades, podemos obter uma solu\u00e7\u00e3o \u00f3tima, no pior caso, que chamamos de uma solu\u00e7\u00e3o robusta diante da imprecis\u00e3o sobre os efeitos probabil\u00edsticos de nossas a\u00e7\u00f5es\u201d, afirma a professora. <\/p>\n
A tese de doutorado Processos de Decis\u00e3o Markovianos Fatorados com Probabilidades Imprecisas, de Karina Valdivia Delgado, desenvolve solu\u00e7\u00f5es in\u00e9ditas para os chamados \u201cProcessos de Decis\u00e3o Markovianos com Probabilidades Imprecisas\u201d (MDPIP) Fatorado. \u201cNo MDPIP Fatorado s\u00e3o representadas as vari\u00e1veis de estado ao inv\u00e9s de se fazer uma enumera\u00e7\u00e3o de todos os estados poss\u00edveis de um sistema, como \u00e9 feito na abordagem cl\u00e1ssica. Isto \u00e9, ao inv\u00e9s de tratarmos propriedades isoladas de um ambiente, como por exemplo, o sem\u00e1foro da Av. Paulista com a Av. Consola\u00e7\u00e3o, na abordagem cl\u00e1ssica ter\u00edamos que enumerar todas as poss\u00edveis configura\u00e7\u00f5es dos sem\u00e1foros da cidade S\u00e3o Paulo\u201d, explica Leliane. <\/p>\n
MDP
\nA professora conta que a teoria sobre MDP foi proposta na d\u00e9cada de 1960 e \u00e9 muito usada para controle de sistemas. No entanto, no controle de sem\u00e1foros \u00e9 imposs\u00edvel 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. <\/p>\n
J\u00e1 na d\u00e9cada de 1970, uma nova extens\u00e3o do modelo matem\u00e1tico MDP foi proposta por J.K. Satia. Ele foi denominado como Processos de Decis\u00e3o Markovianos com Probabilidades Imprecisas (MDPIP) e permite o desenvolvimento de solu\u00e7\u00f5es eficientes para o problema de planejamento probabil\u00edstico. Uma vers\u00e3o fatorada e outra baseada em programa\u00e7\u00e3o matem\u00e1tica do MDPIP, bem como um conjunto de solu\u00e7\u00f5es eficientes, foram desenvolvidas no grupo de Intelig\u00eancia Artificial do IME, como parte do projeto tem\u00e1tico FAPESP LOGPROB (L\u00f3gica e Probabilidades). Segundo Leliane, uma das aplica\u00e7\u00f5es do novo modelo pode ser, por exemplo, o controle dos sem\u00e1foros de uma cidade como S\u00e3o Paulo, em que o tratamento de probabilidades imprecisas permite obter solu\u00e7\u00f5es robustas. <\/p>\n
No estudo de Karina foram propostas quatro solu\u00e7\u00f5es fatoradas, sendo tr\u00eas delas baseadas em Programa\u00e7\u00e3o Din\u00e2mica e uma em Programa\u00e7\u00e3o Matem\u00e1tica (mais especificamente, Programa\u00e7\u00e3o Multilinear). \u201dAs \u00fanicas solu\u00e7\u00f5es existentes at\u00e9 esse momento para um MDP com probabilidades imprecisas eram aquelas propostas por J.K. Satia, na d\u00e9cada 1970 e uma solu\u00e7\u00e3o ainda considerada ineficiente foi proposta na d\u00e9cada de 1990 por C. C. White\u201d, conta Karina. <\/p>\n
Desafio
\nEsses Processos de Decis\u00e3o Markovianos com Probabilidades Imprecisas deixaram de ser aplicados por muitas d\u00e9cadas devido \u00e0 sua complexidade computacional: somente era poss\u00edvel resolver problemas pequenos, isto \u00e9, problemas envolvendo um n\u00famero pequeno de estados. Karina ressalta ainda que sua pesquisa \u00e9 parte de um projeto tem\u00e1tico FAPESP e tamb\u00e9m faz parte de um projeto de controle de tr\u00e1fego da cidade de Sidney, Austr\u00e1lia, financiado pelo centro de pesquisa australiano NICTA (Australia\u2019s National ICT Research Centre of Excellence). A pesquisadora realizou parte de seu doutorado na sede do NICTA da cidade de Camberra na Austr\u00e1lia com suporte da Pr\u00f3-Reitoria de Pesquisa da USP e do pr\u00f3prio NICTA. <\/p>\n
Segundo Leliane, o controle de tr\u00e1fego \u00e9 apenas uma das poss\u00edveis aplica\u00e7\u00f5es desse trabalho. \u201dPodemos imaginar a utiliza\u00e7\u00e3o das solu\u00e7\u00f5es propostas por Karina em uma infinidade de problemas de planejamento probabil\u00edstico nos quais \u00e9 imposs\u00edvel obter probabilidades precisas, como por exemplo, problemas complexos de log\u00edstica e de controle de tr\u00e1fego a\u00e9reo\u201d. <\/p>\n
Resultados
\nKarina defendeu seu doutorado em janeiro de 2010 pelo programa de Ci\u00eancia da Computa\u00e7\u00e3o do IME. Por suas contribui\u00e7\u00f5es in\u00e9ditas, Karina recebeu em 2009 o pr\u00eamio internacional \u201cSilver IJAR Young Researcher Award for demonstrating excellence in research on imprecise probabiities\u201d, oferecido pelos editores do peri\u00f3dico da Elsevier, \u201cInternational Journal of Approximate Reasoning\u201d, numa chamada para participantes e indica\u00e7\u00f5es pela Internet. <\/p>\n
Esse trabalho tamb\u00e9m recebeu o pr\u00eamio de Melhor Tese de Doutorado no Concurso de Teses e Disserta\u00e7\u00f5es do Simp\u00f3sio Brasileiro de Intelig\u00eancia Artificial, organizado pela Sociedade Brasileira de Computa\u00e7\u00e3o (SBC), referente aos anos de 2009 e 2010. \u201dEsta \u00e9 a segunda vez que um aluno do IME \u00e9 premiado neste concurso\u201d, comemora Leliane. Em 2008, outro orientando da pesquisadora, Silvio do Lago Pereira, tamb\u00e9m recebeu essa premia\u00e7\u00e3o, referente ao per\u00edodo de 2007 e 2008, com a tese entitulada \u201dPlanejamento sob incerteza para metas de alcan\u00e7abilidade estendidas\u201d. <\/p>\n
Autor: Ag\u00eancia USP<\/b><\/p>\n","protected":false},"excerpt":{"rendered":"
Cientistas do Departamento de Ci\u00eancia da Computa\u00e7\u00e3o do Instituto de Matem\u00e1tica e Estat\u00edstica (IME) da USP estudam e desenvolvem solu\u00e7\u00f5es baseadas em t\u00e9cnicas de intelig\u00eancia artificial que poder\u00e3o ser aplicadas no controle de sem\u00e1foros de grandes cidades, de aeroportos ou em rob\u00f3tica. \u201cProblemas de planejamento probabil\u00edstico, como controlar mudan\u00e7as dos sem\u00e1foros poderiam ser modelados como […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,35],"tags":[],"class_list":{"0":"post-19740","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-noticias","7":"category-pesquisa-e-desenvolvimento"},"yoast_head":"\n