Incremental sampling based algorithms for state estimation

Perception is a crucial aspect of the operation of autonomous vehicles. With a multitude of different sources of sensor data, it becomes important to have algorithms which can process the available information quickly and provide a timely solution. Also, an inherently continuous world is sensed by robot sensors and converted into discrete packets of information. Algorithms that can take advantage of this setup, i.e., which have a sound founding in continuous time formulations but which can effectively discretize the available information in an incremental manner according to different requirements can potentially outperform conventional perception frameworks. Inspired from recent results in motion planning algorithms, this thesis aims to address these two aspects of the problem of robot perception, through novel incremental and anytime algorithms. The first part of the thesis deals with algorithms for different estimation problems, such as filtering, smoothing, and trajectory decoding. They share the basic idea that a general continuous-time system can be approximated by a sequence of discrete Markov chains that converge in a suitable sense to the original continuous time stochastic system. This discretization is obtained through intuitive rules motivated by physics and is very easy to implement in practice. Incremental algorithms for the above problems can then be formulated on these discrete systems whose solutions converge to the solution of the original problem. A similar construction is used to explore control of partially observable processes in the latter part of the thesis. A general continuous time control problem in this case is approximates by a sequence of discrete partially observable Markov decision processes (POMDPs), in such a way that the trajectories of the POMDPs -- i.e., the trajectories of beliefs -- converge to the trajectories of the original continuous problem. Modern point-based solvers are used to approximate control policies for each of these discrete problems and it is shown that these control policies converge to the optimal control policy of the original problem in an appropriate space. This approach is promising because instead of solving a large POMDP problem from scratch, which is PSPACE-hard, approximate solutions of smaller problems can be used to guide the search for the optimal control policy.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2012

Author dc:creator

• Chaudhari, Pratik (Pratik Anil)

Advisor dc:contributor.advisor

• Emilio Frazzoli.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/77104

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/77104