[1]YU Kui,WANG Hao,YAO Hong-liang.A dynamic influence diagram for dynamic decision processes[J].CAAI Transactions on Intelligent Systems,2008,3(2):159-166.
Copy

A dynamic influence diagram for dynamic decision processes

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 2 Page number: 159-166 Column: 学术论文—人工智能基础 Public date: 2008-04-25
Title:
A dynamic influence diagram for dynamic decision processes
Author(s):
YU Kui1; 2;  WANG Hao2;  YAO Hong-liang2
1.Department of Computer Science, Institute of Textile and Garment of Changzho u, Changzhou 213164, China;
2. School of Computer and Information, Hefei Univers ity of Technology, Hefei 230009, China
Keywords:
dynamic Bayesian networks;  influence diagrams;  Markov decision process;  partially observable Markov decision process;  dynamic influence diagram
CLC:
TP181
DOI:
-
Abstract:
Computational complexities in strategy space and state space make the partially observable Markov decision process (POMDP) an NPhard problem. Therefore, in this paper, a dynamic influence diagram is proposed to model the decisionmaking problem with a single agent, in which a directed acyclic diagram is used to express the complex relationships between systematic variables. Firstly, a dynamic Bayesian network is used to represent the transition and observation models so as to reduce the state space of the system. Secondly, in order to reduce the representational complexity of the utility function, it is expressed in terms of utility nodes. Finally, the actions of the system are represented with decision nodes to simplify the strategy space. The dynamic influence diagram is compared with the POMDP using these three aspects. Our research indicates that a dynamic influence diagram provides a simple way to express POMDP problems. Experiments in the Robocup environment verified the effectiveness of the proposed model.
References:
［1］ KAELB LING L P, LITTMAN M L, MOORE A W. Reinforcement learning: a survey［J］. Journal of Artificial Intelligence Research, 1996,4: 237285.
［2］POUPART P. Exploiting structure to efficiently solve large scale partiall y observable markov decision processes\[D\]. Toronto:University of Toronto, 2005.
［3］KAELBLING L P, LITTMAN M L, CASSANDRA A R. Planning and acting in partiall y observable stochastic domains［J］. Artificial Intelligence, 1998, 101: 99134. 
［4］MICHAEL J, YISHAY M, ANDREW Y. Ng approximate planning in la rg e POMDPs via reusable trajectories［C］// Advances in Neural Information Processing Systems. ［S.l.］ Cambridge:MIT Press,1999:10011007.［5］NICHOLAS R, GEOFFREY J. Gordon, sebastian thrun: finding approximate POM DP solutions through belief compression［J］. J Artif Intell Res(JAIR), 2005 , 23: 140.
［6］PAPADIMITRIOU C H, TSITSIKLIS J N. The complexity of Markov decisio n processes\[J\]. Mathematics of Operations Research, 1987, 12(3):441450.
［7］LUSENA C, GOLDSMITH J, MUNDHENK M. Nonapproximabilit y results for partially observable Markov decision processes［J］. Journal of Arti ficial Intelligence Research, 2001, 14:83103.
［8］DEAN T,KANAZAWA K. Probabilistic temporal reasoning［C］// National Conference on Artificial Intelligence. Washington:AAAI Press, 1988, 524528.
［9］RONALD A, HOWARD, JAMES E. Readings on the principles and app li cations of decision analysis ［M］. ［S.l.］: Strategic Decision Group, 1 984.
［10］BOUTILIER C, DEAN T, HANKS S. Decisiontheoretic planning: s tructural a ssumptions and computational leverage［J］. Journal of Artificial Intelligence R esearch, 1999, 11:194.
［11］JOSEPH A, TATMAN, ROSS D, et al. Dynamic programming and influence di agrams［J］. IEEE Transations on Systems, Man, and Cybernetics, 1990, 20(2):365 379.
［12］BRENDA N G. Avi Pfeffer, Factored Particles for Scalable M on itoring［C］// Uncertainty in Artificial Int elligence Morgan Kaufmann. San Francisco, USA,2002:370377.
［13］PRASHANT D, PIOTR G. A particle filtering based appro ac h to approximating interactive POMDPs［C］// P Nati onal Conference on Artificial Intelligence, Menlo Park.AAAI Press,2005:969974.
Similar References:

Memo

-

Last Update: 2009-05-11

Copyright © CAAI Transactions on Intelligent Systems