 |
Sebastian Thrun, Frank Pfenning, Sungwoo Park, and Jonathan Moody
Sensor-based embedded systems have to cope with uncertainty. Uncertainty arises from sensor limitations, environment dynamics, and lack of knowledge at the design time of embedded system.
Currently, we lack frameworks for developing software for embedded systems. Our hypothesis is that probabilistic computation and learning are key to building robust embedded software. Furthermore, we believe that these principles should be offered at the programming language level, to maximize their usability. Thus, our goal is to devise new programming languages that seamlessly integrate probabilistic computation and learning.
This project, if successful, could revolutionize the way we program computers. Today, computers are programmed through keyboards. Tomorrow we might teach them, or let them teach themselves through interaction with their environment. Moreover, to date we treat all information inside a computer as certain. Tomorrow's computer software might compute with multiple hypothesis, yielding more robust results in the face of uncertainty.
Current computer programming languages do not support any of the mechanisms studied in this project.
Probabilistic means of computing have been studied in applied statistics and AI, most notably in the context of graphical models [7]. Graphical models specify probability distributions in high-dimensional spaces that can be marginalized efficiently. They can be viewed of a declarative approach to probabilistic computation. Other relevant methods are Kalman filters [4], Hidden Markov Models [8], and particle filters [1], which are probabilistic methods for state tracking.
Robotics has developed a range of programming languages [2,3,5,9] which are primarily concerned with concurrency, modular programming, and event-driven computation. Finally, methods have been proposed for learning program code from data, such as the genetic programming approach [6].
Our approach contains two basic ideas. First, we make probability distribution as usable as an elementary data types. Probability distributions can be defined over arbitrary data types. By moving from a conventional data type to a probabilistic one, a certain piece of information is turned into an uncertain one. Our belief is that computing with uncertain information is completely analogous to computing with certain information. Our approach, thus, provides arithmetic operations defined over probability densities, type conversion mechanisms, and even complex concepts such as iterations, recursion, and function calls.
Second, we enable programmers to embed function approximators in their code, such as artificial neural networks. We provide the necessary infrastructure to tune these function approximators with data, even for ``distal'' target signals. Function approximation offers an viable alternative to programming: Instead of programming a function by hand, the programmer can equally decide to train his software to perform the desired function. The seamless integration seeks to attain the best of both worlds: learning and programming, providing the programmer with the method of choice.
At present, we possess one implemented proto-type, which is implemented on top of C++ [10,11]. A second proto-type is implemented on top of the programming language ML, but it currently lacks support for learning. We have successfully demonstrated that robust probabilistic robot software is two orders of magnitude more compact when developed using our new programming languages. For example, we have implemented a program for a mobile mail delivery robot with a gesture interface in only 140 lines of code (plus two hours of training), where comparable implementations require tens of thousands of lines of code (see Figure 1).
In the future, we plan to solidify our implementations, develop software developing and debugging environment, and disseminate the results of our research to a user community.
|
Sequential Monte Carlo Methods In Practice.
Springer, 2001.
An investigation into reactive planning in complex domains.
In Proceedings of the National Conference on Artificial
Intellgence (AAAI), pages 809-815. AAAI, 1987.
Esl: A language for supporting robust plan execution in embedded
autonomous agents.
In Working notes of the AAAI Fall Symposium on Plan Execution,
Boston, MA, 1996. AAAI.
A new approach to linear filtering and prediction problems.
Trans. ASME, Journal of Basic Engineering, 82:35-45, 1960.
Colbert: A language for reactive control in saphira.
In KI-97: Advances in Artificial Intelligence, LNAI, pages
31-52. Springer verlag, 1997.
Genetic Programming: On the Programming of Computers by Means of
Natural Selection.
MIT Press, Cambridge, MA, 1992.
Probabilistic reasoning in intelligent systems: networks of
plausible inference.
Morgan Kaufmann Publishers, San Mateo, CA, 1988.
An introduction to hidden markov models.
IEEE ASSP Magazine, 3(1):4-16, 1986.
A task description language for robot control.
In Proceedings of the Conference on Intelligent Robots and
Systems (IROS), Victoria, CA, 1998.
A framework for programming embedded systems: Initial design and
results.
Technical Report CMU-CS-98-142, Carnegie Mellon University, Computer
Science Department, Pittsburgh, PA, 1998.
Towards programming tools for robots that integrate probabilistic
computation and learning.
In Proceedings of the IEEE International Conference on Robotics
and Automation (ICRA), San Francisco, CA, 2000. IEEE.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -debug -white -no_fork -no_navigation -address -split 0 -dir html -external_file thrun2 thrun2.tex.
The translation was initiated by Daniel Nikovski on 2001-01-17