Probabilistic Algorithms in Robotics - Sebastian Thrun

1 Probabilistic Algorithms in RoboticsSebastian ThrunApril 2000 CMU-CS-00-126 School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213 AbstractThis article describes a methodology for programming robots known asprobabilistic Robotics . The proba-bilistic paradigm pays tribute to the inherent uncertainty in robot perception, relying on explicit represen-tations of uncertainty when determining what to do. This article surveys some of the progress in the field,using in-depth examples to illustrate some of the nuts and bolts of the basic approach. Our central con-jecture is that the Probabilistic approach to Robotics scales better to complex real-world applications thanapproaches that ignore a robot s research is sponsored by the National Science Foundation (and CAREER grant number IIS-9876136 and regular grantnumber IIS-9877033), and by DARPA-ATO via TACOM (contract number DAAE07-98-C-L032) and DARPA-ISO via Rome Labs(contract number F30602-98-2-0137), which is gratefully acknowledged.

2 The views and conclusions contained in this documentare those of the author and should not be interpreted as necessarily representing official policies or endorsements, either expressedor implied, of the United States Government or any of the sponsoring :Artificial intelligence, bayes filters, decision theory, Robotics , localization, machine learn-ing, mapping, navigation, particle filters, planning, POMDPs, position estimation1 IntroductionBuilding autonomous robots has been a central objective of research in artificial intelligence. Over thepast decades, researchers in AI have developed a range of methodologies for developing robotic software,ranging from model-based to purely reactive paradigms. More than once, the discussion on what the rightway might be to program robots has been accompanied with speculations concerning the very nature ofintelligence per se, in animals and of these approaches, Probabilistic Robotics , has led to fielded systems with unprecedented levels ofautonomy and robustness.

3 While the roots of this approach can be traced back to the early 1960s, in recentyears the Probabilistic approach has become the dominant paradigm in a wide array of robotic Algorithms have been at the core of a series of fielded autonomous robots, exhibiting an un-precedented level of performance and robustness in the real world. These recent successes can be attributedto at least two developments: the availability of immense computational resources even on low-end PCsand, more importantly, fundamental progress on the basic algorithmic and theoretical what exactly is the Probabilistic approach to Robotics ? At its core is the idea of representing infor-mation through probability densities. In particular, Probabilistic ideas can be found inperception, , theway sensor data is processed, andaction, , the way decisions are made: Probabilistic are inherently uncertain about the state of their environments.

4 Un-certainty arises from sensor limitations, noise, and the fact that most interesting environments are to acertain degree unpredictable. When guessing a quantity from sensor data, the Probabilistic approachcomputes a probability distribution over what might be the case in the world, instead of generating asingle best guess only. As a result, a Probabilistic robot can gracefully recover from errors, handleambiguities, and integrate sensor data in a consistent way. Moreover, a Probabilistic robot knows aboutits own ignorance a key prerequisite of truly autonomous robots. Probabilistic robots must act in the face of uncertainty a direct consequenceof their inability to know what is the case. When making decisions, Probabilistic approaches take therobot s uncertainty into account. Some consider only the robot s current uncertainty, others anticipatefuture uncertainty.

5 Instead of considering the most likely situations only (current or projected), manyprobabilistic approaches strive to compute a decision-theoretic optimum, in which decision are based onall possible two items are the basic characterization of the Probabilistic approach to is the benefit of programming robots probabilistically? Our central conjecture is nothing less thanthe following:A robot that carries a notion of its own uncertainty and that acts accordingly, will do betterthan one that does particular, Probabilistic approaches are typically more robust in the face of sensorlimitations, sensor noise, and environment dynamics. They often scale much better to complex environ-ments, where the ability to handle uncertainty is of even greater importance. In fact, certain probabilisticalgorithms are currently the only known working solutions to hard robotic estimation problems, such as thekidnapped robot problem[28], in which a mobile robot must recover from localization failure; or the prob-lem of building accurate maps of very large environments, in the absence of a global positioning device suchas GPS.

6 Additionally, Probabilistic Algorithms make much weaker requirements on theaccuracy of modelsthan many classical planning Algorithms do, thereby relieving the programmer from the (unsurmountable)burden to come up with accurate models. Viewed probabilistically, therobot learning problemis a long-termestimation problem. Thus, Probabilistic Algorithms provide a sound methodology for many flavors of robotlearning. And finally, Probabilistic Algorithms are broadly applicable to virtually every problem involvingperception and action in the real , these advantages come at a price. Traditionally, the two most frequently cited limitations ofprobabilistic Algorithms arecomputational inefficiency,anda need to approximate. Certainly, there is sometruth to these criticisms. Probabilistic Algorithms are inherently less efficient than non- Probabilistic ones,due to the fact that they consider entire probability densities.

7 However, this carries the benefit of increasedrobustness. The need to approximate arises from the fact that most robot worlds are continuous. Computingexact posterior distributions is typically infeasible, since distributions over the continuum possess infinitelymany dimensions. Sometimes, one is fortunate in that the uncertainty can approximated tightly with acompact parametric model ( , discrete distributions or Gaussians); in other cases, such approximationsare too crude and more complex representations most be of these limitations, however, pose serious obstacles. Recent research has led to a range of algo-rithms that are computationally efficient and also highly accurate. Toillustrate Probabilistic Algorithms inpractice, this article describes three such Algorithms in detail, and argues that the Probabilistic paradigm isunique in its ability to solve hard Robotics problems in uncertain and complex Mobile robot LocalizationLet us take a first, deeper look into a specific Probabilistic algorithm , which solves an important problem inmobile Robotics , namely that oflocalization.

8 Localization is the problem of finding out a robot s coordinatesrelative to its environment, assuming that one is provided with a map of the environment. Localization is akey component in various successful mobile robot systems (see , [4, 51]). Occasionally is has been re-ferred to as the most fundamental problem to providing a mobile robot with autonomous capabilities [16].Particularly challenging is theglobal localization problem, where the robot does not know its initial positionand therefore has to globally localize probabilistically, the localization problem is a density estimation problem, where a robotseeks to estimate a posterior distribution over the space of its poses conditioned on the available data. Thetermpose, in this article, refers to a robot sx-y-coordinates together with its heading direction . Denotingthe robot s pose at timetbyst, and the data leading up to timetbyd0:::t, the posterior is convenientlywritten asp(stjd0:::t;m):(1)Heremis the model of the world ( , a map).

9 For brevity, we will denote this posteriorbt(st), and refer toit as the robot sbelief stateat data typically comes in two flavors: Data that characterizes the momentary situation ( , cameraimages, laser range scans), and data relating to change of the situation ( , motor controls or odometerreadings). Referring to the former asobservationsand the latter asaction data, let us without loss ofgenerality assume that both types of data arrives in an alternating sequence:d0:::t=o0;a0;o1;a1;:::;at 1;ot:(2)Hereotdenote the observation andatdenotes the action data item collected at estimate the desired posteriorp(stjd0:::t;m), Probabilistic approaches frequently resort to aMarkovassumption, which states that the past is independent of the future given knowledge of the current state. TheMarkov assumption is often referred to as thestatic world assumption, since it assumes the robot s pose isthe only state in the world that would impact more than just one isolated sensor reading.

10 Practical experiencesuggests, however, that Probabilistic Algorithms are robust to mild violations of the Markov assumption, andextensions exist that go beyond this assumption ( , [33]).2 Figure 1: Probabilistic generalization of mobile robot kinematics: Each dark lineillustrates a commanded robot path, and thegrayly shaded shows the posterior distribution of the robot s pose. The darker an area, the more likely it is. The path in the leftdiagram is 40 meters and the one on the right is 80 meters desired posterior is now computed using a recursive formula, which is obtained by applying Bayesrule and the theorem of total probability to the original expression, exploiting the Markov assumption twice:bt(st)=p(stjo0;:::;at 1;ot;m)Bayes= tp(otjo0;:::;at 1;st;m)p(stjo0;:::;at 1;m)Markov= tp(otjst;m)p(stjo0;:::;at 1;m)Tot:Prob:= tp(otjst;m)Zp(stjo0;:::;at 1;st 1;m)p(st 1jo0;:::;at 1;m)dst 1 Markov= tp(otjst;m)Zp(stjat 1;st 1;m)p(st 1jo0;:::;ot 1;m)dst 1= tp(otjst;m)Zp(stjat 1;st 1;m)bt 1(st 1)dst 1:(3)Here tis a constant normalizer which ensures that the result sums up to 1.