Sungwoo Park
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.
- http://www.acfr.usyd.edu.au/homepages/academic/enebot/dataset.htm. Australian Centre for Field Robotics, The University of Sydney.Google Scholar
- P. Bratley, B. Fox, and L. Schrage. A guide to simulation. Springer Verlag, 2nd edition, 1996. Google ScholarDigital Library
- A. Doucet, N. de Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Springer Verlag, New York, 2001.Google ScholarCross Ref
- D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, 11:391--427, 1999.Google ScholarCross Ref
- J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675--695, Dec. 1977.Google ScholarDigital Library
- M. Giry. A categorical approach to probability theory. In B. Banaschewski, editor, Categorical Aspects of Topology and Analysis, pages 68--85. Springer Verlag, 1981.Google Scholar
- V. Gupta, R. Jagadeesan, and P. Panangaden. Stochastic processes as concurrent constraint programs. In 26th ACM POPL, pages 189--202. ACM Press, 1999. Google ScholarDigital Library
- 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.Google Scholar
- A. H. Jazwinski. Stochastic Processes and Filtering Theory. Academic Press, New York, 1970.Google Scholar
- C. Jones. Probabilistic Non-Determinism. PhD thesis, Department of Computer Science, University of Edinburgh, 1990. Google ScholarDigital Library
- D. Koller, D. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In AAAI-97/IAAI-97, pages 740--747. AAAI Press, 1997. Google ScholarDigital Library
- D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328--350, 1981.Google ScholarCross Ref
- D. J. C. MacKay. Introduction to Monte Carlo methods. In M. I. Jordan, editor, Learning in Graphical Models, NATO Science Series, pages 175--204. Kluwer Academic Press, 1998. Google ScholarCross Ref
- 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.Google Scholar
- T. Mogensen. Roll: A language for specifying die-rolls. In V. Dahl and P. Wadler, editors, PADL 03, volume 2562 of LNCS, pages 145--159. Springer, 2002. Google ScholarDigital Library
- E. Moggi. Computational lambda-calculus and monads. In LICS-89, pages 14--23. IEEE Computer Society Press, 1989. Google ScholarDigital Library
- E. Moggi. Notions of computation and monads. Information and Computation, 93:55--92, 1991. Google ScholarDigital Library
- M. Montemerlo, N. Roy, and S. Thrun. CARMEN: Carnegie mellon robot navigation toolkit. http://www.cs.cmu.edu/~carmen/.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- S. Park. A calculus for probabilistic languages. In TLDI 03, pages 38--49. ACM Press, 2003. Google ScholarDigital Library
- 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.Google Scholar
- A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI-01, pages 733--740. Morgan Kaufmann Publishers, 2001. Google ScholarDigital Library
- F. Pfenning and R. Davies. A judgmental reconstruction of modal logic. Mathematical Structures in Computer Science, 11(4):511--540, 2001. Google ScholarDigital Library
- D. Pless and G. Luger. Toward general analysis of recursive probability models. In UAI-01, pages 429--436. Morgan Kaufmann Publishers, 2001. Google ScholarDigital Library
- N. Ramsey and A. Pfeffer. Stochastic lambda calculus and monads of probability distributions. In 29th ACM POPL, pages 154--165. ACM Press, 2002. Google ScholarDigital Library
- S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 1995. Google ScholarDigital Library
- 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.Google Scholar
- S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.Google ScholarDigital Library
- S. Thrun. Towards programming tools for robots that integrate probabilistic computation and learning. In ICRA-00. IEEE, 2000.Google Scholar
- S. Thrun. Robotic mapping: A survey. In G. Lakemeyer and B. Nebel, editors, Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann, 2002. Google ScholarDigital Library
- G. Welch and G. Bishop. An introduction to the kalman filter. Technical Report TR95-041, Department of Computer Science, University of North Carolina - Chapel Hill, 1995. Google ScholarDigital Library
Index Terms
- A probabilistic language based upon sampling functions
Recommendations
A probabilistic language based upon sampling functions
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesAs 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 ...
A probabilistic language based on sampling functions
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 ...
A calculus for probabilistic languages
TLDI '03: Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementationAs probabilistic computation plays an increasing role in diverse fields in computer science, researchers have designed new languages to facilitate the development of probabilistic programs. In this paper, we develop a probabilistic calculus by extending ...
Comments