A Logic for Reasoning About Decision-Theoretic Projections

详细信息    查看全文

• 关键词：Logic ; POMDP ; Projection ; Decision ; theory
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9494
• 期：1
• 页码：79-99
• 全文大小：368 KB
• 参考文献：1.Smallwood, R., Sondik, E.: The optimal control of partially observable Markov processes over a finite horizon. Oper. Res. 21, 1071–1088 (1973)MATH CrossRef
  2.Monahan, G.: A survey of partially observable Markov decision processes: theory, models, and algorithms. Manage. Sci. 28, 1–16 (1982)MATH CrossRef MathSciNet
  3.Boutilier, C., Poole, D.: Computing optimal policies for partially observable decision processes using compact representations. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI 1996), pp. 1168–1175. AAAI Press, Menlo Park (1996)
  4.Geffner, H., Bonet, B.: High-level planning and control with incomplete information using POMDPs. In: Proceedings of the Fall AAAI Symposium on Cognitive Robotics, pp. 113–120. AAAI Press, Seattle (1998)
  5.Hansen, E., Feng, Z.: Dynamic programming for POMDPs using a factored state representation. In: Proceedings of the Fifth International Conference on Artificial Intelligence, Planning and Scheduling (AIPS 2000), pp. 130–139 (2000)
  6.Wang, C., Schmolze, J.: Planning with POMDPs using a compact, logic-based representation. In: Proceedings of the Seventeenth IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2005), pp. 523–530. IEEE Computer Society, Los Alamitos (2005)
  7.Sanner, S., Kersting, K.: Symbolic dynamic programming for first-order POMDPs. In: Proceedings of the Twenty-Fourth National Conference on Artificial Intelligence (AAAI 2010), pp. 1140–1146. AAAI Press (2010)
  8.Lison, P.: Towards relational POMDPs for adaptive dialogue management. In: Proceedings of the ACL 2010 Student Research Workshop, ACLstudent 2010, pp. 7–12. Association for Computational Linguistics, Stroudsburg (2010)
  9.Wang, C., Khardon, R.: Relational partially observable MDPs. In: Fox, M., Poole, D. (eds.) Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010). AAAI Press, Atlanta (2010)
  10.De Weerdt, M., De Boer, F., Van der Hoek, W., Meyer, J.J.: Imprecise observations of mobile robots specified by a modal logic. In: Proceedings of the Fifth Annual Conference of the Advanced School for Computing and Imaging (ASCI 1999), pp. 184–190 (1999)
  11.Bacchus, F., Halpern, J., Levesque, H.: Reasoning about noisy sensors and effectors in the situation calculus. Artif. Intell. 111, 171–208 (1999)MATH CrossRef MathSciNet
  12.McCarthy, J.: Situations, actions and causal laws. Technical report, Stanford University (1963)
  13.Gabaldon, A., Lakemeyer, G.: \({\cal ESP}\) : A logic of only-knowing, noisy sensing and acting. In: Proceedings of the Twenty-Second National Conference on Artificial Intelligence (AAAI 2007), pp. 974–979. AAAI Press (2007)
  14.Levesque, H., Lakemeyer, G.: Situations, si! Situation terms no! In: Proceedings of the Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 516–526. AAAI Press (2004)
  15.Poole, D.: Decision theory, the situation calculus and conditional plans. Linköping Electron. Art. Comput. Inf. Sci. 8, 34 (1998)
  16.Iocchi, L., Lukasiewicz, T., Nardi, D., Rosati, R.: Reasoning about actions with sensing under qualitative and probabilistic uncertainty. ACM Trans. Comput. Logic 10, 5:1–5:41 (2009)CrossRef MathSciNet
  17.Kwiatkowska, M., Norman, G., Parker, D.: Advances and challenges of probabilistic model checking. In: Proceedings of the Forty-Eighth Annual Allerton Conference on Communication, Control and Computing, pp. 1691–1698. IEEE Press (2010)
  18.Hansson, H., Jonsson, B.: A logic for reasoning about time and reliability. Formal Aspects Comput. 6, 512–535 (1994)MATH CrossRef
  19.Ross, S., Pineau, J., Chaib-draa, B., Kreitmann, P.: A bayesian approach for learning and planning in partially observable markov decision processes. J. Mach. Learn. Res. 12, 1729–1770 (2011)MATH MathSciNet
  20.Shirazi, A., Amir, E.: First-order logical filtering. Artif. Intell. 175, 193–219 (2011)MATH CrossRef MathSciNet
  21.Rens, G., Meyer, T., Lakemeyer, G.: SLAP: Specification logic of actions with probability. J. Appl. Logic 12, 128–150 (2014)MATH CrossRef MathSciNet
  22. Rens, G., Meyer, T., Lakemeyer, G.: A logic for specifying stochastic actions and observations. In: Beierle, C., Meghini, C. (eds.) FoIKS 2014. LNCS, vol. 8367, pp. 305–323. Springer, Heidelberg (2014) CrossRef
  23.Rens, G.: Formalisms for Agents Reasoning with Stochastic Actions and Perceptions. Ph.D. thesis, School of Mathematics, Statistics and Computer Science, University of KwaZulu-Natal (2014)
  24.McCarthy, J., Hayes, P.: Some philosophical problems from the standpoint of artificial intelligence. Mach. Intell. 4, 463–502 (1969)MATH
  25.Rens, G., Meyer, T., Lakemeyer, G.: On the logical specification of probabilistic transition models. In: Proceedings of the Eleventh International Symposium on Logical Formalizations of Commonsense Reasoning (COMMONSENSE 2013), University of Technology, Sydney. UTSe Press (2013)
  26. Saad, E.: Probabilistic reasoning by SAT solvers. In: Sossai, C., Chemello, G. (eds.) ECSQARU 2009. LNCS, vol. 5590, pp. 663–675. Springer, Heidelberg (2009) CrossRef
  27.Wang, C., Joshi, S., Khardon, R.: First order decision diagrams for relational MDPs. J. Artif. Intell. Res. (JAIR) 31, 431–472 (2008)MATH MathSciNet
  28.Boutilier, C., Reiter, R., Soutchanski, M., Thrun, S.: Decision-theoretic, high-level agent programming in the situation calculus. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000) and of the Twelfth Conference on Innovative Applications of Artificial Intelligence (IAAI 2000), pp. 355–362. AAAI Press, Menlo Park (2000)
  29.Littman, M., Majercik, S., Pitassi, T.: Stochastic boolean satisfiability. J. Autom. Reasoning 27, 251–296 (2001)MATH CrossRef MathSciNet
  
• 作者单位：Gavin Rens (17) (18)
  Thomas Meyer (18) (19)
  Gerhard Lakemeyer (20)
  
  17. School of Mathematics, Statistics and Computer Science, University of KwaZulu-Natal, Durban, South Africa
  18. Centre for Artificial Intelligence Research, CSIR Meraka, Pretoria, South Africa
  19. Department of Computer Science, University of Cape Town, Cape Town, South Africa
  20. Knowledge-based Systems Group, RWTH Aachen University, Aachen, Germany
  
• 丛书名：Agents and Artificial Intelligence
• ISBN：978-3-319-27947-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

A decidable logic is presented, in which queries can be posed about (i) the degree of belief in a propositional sentence after an arbitrary finite number of actions and observations and (ii) the utility of a finite sequence of actions after a number of actions and observations. The main contribution of this work is that a POMDP model specification is allowed to be partial or incomplete with no restriction on the lack of information specified for the model. The model may even contain information about non-initial beliefs. Essentially, entailment of arbitrary queries (expressible in the language) can be answered. A sound, complete and terminating decision procedure is provided.