A probabilistic language based on sampling functions

Abstract

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages which treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on discrete distributions and have limited expressive power. This article presents a probabilistic language, called λ_○, whose expressive power is beyond discrete distributions. Rich expressiveness of λ_○ is due to its use of sampling functions, that is, mappings from the unit interval (0.0,1.0] to probability domains, in specifying probability distributions. As such, λ_○ enables programmers to formally express and reason about sampling methods developed in simulation theory. The use of λ_○ is demonstrated with three applications in robotics: robot localization, people tracking, and robotic mapping. All experiments have been carried out with real robots.

References

1. Bratley, P., Fox, B., and Schrage, L. 1996. A Guide to Simulation 2nd Ed. Springer-Verlag.
2. Charniak, E. 1993. Statistical Language Learning. MIT Press, Cambridge, MA.
3. Devroye, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag.
4. Doucet, A., de Freitas, N., and Gordon, N. 2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.
5. Fox, D., Burgard, W., and Thrun, S. 1999. Markov localization for mobile robots in dynamic environments. J. A.I. Rese. 11, 391--427.
6. Gill, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 4, 675--695.
7. Giry, M. 1981. A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, B. Banaschewski, Ed. Lecture Notes In Mathematics, vol. 915. Springer-Verlag, 68--85.
8. Gupta, V., Jagadeesan, R., and Panangaden, P. 1999. Stochastic processes as concurrent constraint programs. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 189--202.
9. Henrion, M. 1988. Propagation of uncertainty in Bayesian networks by probabilistic logic sampling. In Uncertainty in Artificial Intelligence 2, J. F. Lemmer and L. N. Kanal, Eds. Elsevier/North-Holland, 149--163.
10. Isard, M. and Blake, A. 1998. CONDENSATION: Conditional density propagation for visual tracking. Int. J. Comput. Vision 29, 1, 5--28.
11. Jazwinski, A. H. 1970. Stochastic Processes and Filtering Theory. Academic Press, New York, NY.
12. Jelinek, F. 1998. Statistical Methods for Speech Recognition (Language, Speech, and Communication). MIT Press, Cambridge, MA.
13. Jones, C. 1990. Probabilistic nondeterminism. Ph.D. thesis, Department of Computer Science, University of Edinburgh.
14. Koller, D., McAllester, D., and Pfeffer, A. 1997. Effective Bayesian inference for stochastic programs. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference. AAAI Press, 740--747.
15. Kozen, D. 1981. Semantics of probabilistic programs. J. Comput. Syst. Sci. 22, 3, 328--350.
16. Launchbury, J. and Peyton Jones, S. L. 1995. State in Haskell. Lisp Symbol. Comput. 8, 4, 293--341.
17. Leroy, X. 2000. A modular module system. J. Funct. Program. 10, 3, 269--303.
18. MacKay, D. J. C. 1998. Introduction to Monte Carlo methods. In Learning in Graphical Models, M. I. Jordan, Ed. NATO Science Series. Kluwer Academic Press, 175--204.
19. Martin-Löf, P. 1996. On the meanings of the logical constants and the justifications of the logical laws. Nordic J. Phil. Logic 1, 1, 11--60.
20. Mogensen, T. 2002. Roll: A language for specifying die-rolls. In Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, V. Dahl and P. Wadler, Eds. Lecture Notes in Computer Science, vol. 2562. Springer, 145--159.
21. Moggi, E. 1989. Computational lambda-calculus and monads. In Proceedings of the 4th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, 14--23.
22. Moggi, E. 1991. Notions of computation and monads. Inform. Comput. 93, 55--92.
23. Montemerlo, M. 2003. FastSLAM: A factored solution to the simultaneous localization and mapping problem with unknown data association. Ph.D. thesis, Robotics Institute, Carnegie Mellon University.
24. Montemerlo, M., Roy, N., and Thrun, S. CARMEN: Carnegie Mellon Robot Navigation Toolkit. http://www.cs.cmu.edu/~carmen/.
25. Montemerlo, M., Whittaker, W., and Thrun, S. 2002. Conditional particle filters for simultaneous mobile robot localization and people-tracking. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). 695--701.
26. Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK.
27. Park, S. 2003. A calculus for probabilistic languages. In Proceedings of the ACM SIGPLAN International Workshop on Types in Language Design and Implementation. ACM Press, 38--49.
28. Peyton Jones, S. L. 2001. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering Theories of Software Construction, C. A. R. Hoare, M. Broy, and R. Steinbrüggen, Eds. IOS Press, Amsterdam, The Netherlands.
29. Peyton Jones, S. L. and Wadler, P. 1993. Imperative functional programming. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 71--84.
30. Pfeffer, A. 2001. IBAL: A probabilistic rational programming language. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), B. Nebel, Ed. Morgan Kaufmann Publishers, Inc., 733--740.
31. Pfenning, F. and Davies, R. 2001. A judgmental reconstruction of modal logic. Math. Struct. Comput. Sci. 11, 4, 511--540.
32. Pless, D. and Luger, G. 2001. Toward general analysis of recursive probability models. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI'01), J. Breese and D. Koller, Eds. Morgan Kaufmann Publishers, 429--436.
33. Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 2, 257--285.
34. Ramsey, N. and Pfeffer, A. 2002. Stochastic lambda calculus and monads of probability distributions. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 154--165.
35. Rudin, W. 1986. Real and Complex Analysis 3rd Ed. McGraw-Hill, New York, NY.
36. Russell, S. and Norvig, P. 1995. Artificial Intelligence: A Modern Approach. Prentice Hall.
37. Sabry, A. and Wadler, P. 1997. A reflection on call-by-value. ACM Trans. Program. Lang. Syst. 19, 6, 916--941.
38. Saheb-Djahromi, N. 1978. Probabilistic LCF. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science, J. Winkowski, Ed. Lecture Notes in Computer Science, vol. 64. Springer, 442--451.
39. Thrun, S. 2000a. Probabilistic algorithms in robotics. AI Mag. 21, 4, 93--109.
40. Thrun, S. 2000b. Towards programming tools for robots that integrate probabilistic computation and learning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
41. Thrun, S. 2002. Robotic mapping: A survey. In Exploring Artificial Intelligence in the New Millenium, G. Lakemeyer and B. Nebel, Eds. Morgan Kaufmann.
42. Welch, G. and Bishop, G. 1995. An introduction to the Kalman filter. Tech. rep. TR95-041, Department of Computer Science, University of North Carolina—Chapel Hill.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Specialized application languages