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: Paul Bratley , Bennett L Fox , Linus E Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1986
• 2: Eugene Charniak, Statistical Language Learning, MIT Press, Cambridge, MA, 1994
• 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: Vineet Gupta , Radha Jagadeesan , Prakash Panangaden, Stochastic processes as concurrent constraint programs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.189-202, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292558]
• 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: Michael Isard , Andrew Blake, C$ONDENSATION$—Conditional Density Propagation forVisual Tracking, International Journal of Computer Vision, v.29 n.1, p.5-28, Aug. 1998 [doi>10.1023/A:1008078328650]
• 11: Jazwinski, A. H. 1970. Stochastic Processes and Filtering Theory. Academic Press, New York, NY.
• 12: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 13: Claire Jones, Probabilistic non-determinism, University of Edinburgh, Edinburgh, Scotland, 1992
• 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: John Launchbury , Simon L. Peyton Jones, State in Haskell, Lisp and Symbolic Computation, v.8 n.4, p.293-341, Dec. 1995 [doi>10.1007/BF01018827]
• 17: Xavier Leroy, A modular module system, Journal of Functional Programming, v.10 n.3, p.269-303, May 2000 [doi>10.1017/S0956796800003683]
• 18: D. J. C. MacKay, Introduction to Monte Carlo methods, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 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: Torben Æ. Mogensen, Roll: A Language for Specifying Die-Rolls, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.145-159, January 13-14, 2003
• 21: E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
• 22: Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
• 23: Michael Steven Montemerlo , William Whittaker , Sebastian Thrun, Fastslam: a factored solution to the simultaneous localization and mapping problem with unknown data association, Carnegie Mellon University, Pittsburgh, PA, 2003
• 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: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 27: Sungwoo Park, A calculus for probabilistic languages, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 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: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 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: Frank Pfenning , Rowan Davies, A judgmental reconstruction of modal logic, Mathematical Structures in Computer Science, v.11 n.4, p.511-540, August 2001 [doi>10.1017/S0960129501003322]
• 32: Daniel Pless , George F. Luger, Toward General Analysis of Recursive Probability Models, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.429-436, August 02-05, 2001
• 33: Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 2, 257--285.
• 34: Norman Ramsey , Avi Pfeffer, Stochastic lambda calculus and monads of probability distributions, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 16-18, 2002, Portland, Oregon
• 35: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987
• 36: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 37: Amr Sabry , Philip Wadler, A reflection on call-by-value, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.916-941, Nov. 1997 [doi>10.1145/267959.269968]
• 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: Sebastian Thrun, Robotic mapping: a survey, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 42: Greg Welch , Gary Bishop, An Introduction to the Kalman Filter, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Experimentation, Languages

Keywords:
Probabilistic language, probability distribution, robotics, sampling function