A probabilistic language based upon sampling functions

ABSTRACT

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages that treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on discrete distributions and have limited expressive power. In this paper, we present a probabilistic language, called λο, which uniformly supports all kinds of probability distributions -- discrete distributions, continuous distributions, and even those belonging to neither group. Its mathematical basis is sampling functions, i.e., mappings from the unit interval (0.0,1.0] to probability domains.We also briefly describe the implementation of λο as an extension of Objective CAML and demonstrate its practicality with three applications in robotics: robot localization, people tracking, and robotic mapping. All experiments have been carried out with real robots.

REFERENCES

• 1: http://www.acfr.usyd.edu.au/homepages/academic/enebot/dataset.htm. Australian Centre for Field Robotics, The University of Sydney.
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: A. Doucet, N. de Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Springer Verlag, New York, 2001.
• 4: D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, 11:391--427, 1999.
• 5: J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675--695, Dec. 1977.
• 6: M. Giry. A categorical approach to probability theory. In B. Banaschewski, editor, Categorical Aspects of Topology and Analysis, pages 68--85. Springer Verlag, 1981.
• 7: 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]
• 8: M. Henrion. Propagation of uncertainty in Bayesian networks by probabilistic logic sampling. In J. F. Lemmer and L. N. Kanal, editors, Uncertainty in Artificial Intelligence 2, pages 149--163. Elsevier/North-Holland, 1988.
• 9: A. H. Jazwinski. Stochastic Processes and Filtering Theory. Academic Press, New York, 1970.
• 10: Claire Jones, Probabilistic non-determinism, University of Edinburgh, Edinburgh, Scotland, 1992
• 11: D. Koller, D. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In AAAI-97/IAAI-97, pages 740--747. AAAI Press, 1997.
• 12: D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328--350, 1981.
• 13: D. J. C. MacKay, Introduction to Monte Carlo methods, Proceedings of the NATO Advanced Study Institute on Learning in graphical models, p.175-204, March 1998, Erice, Italy
• 14: P. Martin-Löf. On the meanings of the logical constants and the justifications of the logical laws. Nordic Journal of Philosophical Logic, 1(1):11--60, 1996.
• 15: 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
• 16: 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
• 17: 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]
• 18: M. Montemerlo, N. Roy, and S. Thrun. CARMEN: Carnegie mellon robot navigation toolkit. http://www.cs.cmu.edu/~carmen/.
• 19: M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges. In IJCAI-03. Morgan Kaufmann Publishers, Inc., 2003.
• 20: M. Montemerlo, W. Whittaker, and S. Thrun. Conditional particle filters for simultaneous mobile robot localization and people-tracking. In IEEE International Conference on Robotics and Automation (ICRA), 2002.
• 21: 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
• 22: S. Park, F. Pfenning, and S. Thrun. A probabilistic language based upon sampling functions. Technical Report CMU-CS-04-173, School of Computer Science, Carnegie Mellon University, 2004.
• 23: A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI-01, pages 733--740. Morgan Kaufmann Publishers, 2001.
• 24: 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]
• 25: 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
• 26: 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
• 27: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 28: N. Saheb-Djahromi. Probabilistic LCF. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science, volume~64 of LNCS, pages 442--451. Springer, 1978.
• 29: S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.
• 30: S. Thrun. Towards programming tools for robots that integrate probabilistic computation and learning. In ICRA-00. IEEE, 2000.
• 31: Sebastian Thrun, Robotic mapping: a survey, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 32: 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