------------------------------------------------------------------------------------------ Semin�rio do Grupo de L�gica, Intelig�ncia Artificial e M�todos Formais - LIAMF Semin�rio Registrado na CPG do IME/USP P�gina: http://www.ime.usp.br/~liamf/seminarios/index.html ------------------------------------------------------------------------------------------- T�tulo: SPUDD: usando Diagramas de Decis�o para resolver Processos Markovianos de Decis�o fatorados. Palestrante: Karina Valdivia Delgado (estudante de doutorado IME) Data: 24/11/2008, 14h30 Local: Sala 03B, IME-USP Resumo: Planejamento probabil�stico � uma sub-�rea de planejamento da Intelig�ncia Artificial que usa Processos Markovianos de Decis�o (MDPs) como modelo matem�tico. MDPs fornecem um arcabou�o matem�tico para modelar e resolver problemas de decis�o sequencial com incerteza em ambientes completamente observ�veis. Um MDP modela a intera��o entre um agente e seu ambiente. A cada instante o agente faz uma escolha de a��es (com efeitos probabil�sticos) e decide executar uma a��o que produzir� um estado futuro e uma recompensa. O objetivo do agente � maximizar a recompensa ganha ao longo de uma sequ�ncia de escolhas de a��es. Uma das dificuldades para resolver um problema MDP � que frequentemente o tamanho do espa�o de estados � muito grande. Resultados recentes t�m demonstrado que � poss�vel resolver uma formula��o fatorada de um MDP chamada de MDP-fatorado numa maneira mais eficiente (com mill�es de estados) quando comparados com solu��es cl�ssicas baseados em programa��o din�mica e com o espa�o de estados enumerativo. Nesta palestra mostraremos o algoritmo SPUDD em que os estados s�o agregados implicitamente usando ADDs (diagramas de decis�o alg�bricos) para representar a fun��o valor e as pol�ticas, evitando assim trabalhar com o espa�o de estados enumerativos. SPUDD modifica o algoritmo cl�ssico de itera��o de valor usando ADDs permitindo que o c�lculo do valor esperado e as maximiza��es sejam feitas eficientemente.