|
This software package implements a filtering technique that
maintains a tractable approximation of the belief state as a
thin junction tree. The junction tree grows under filter
updates and is periodically ``thinned'' via efficient maximum
likelihood projections so inference remains tractable. When
applied to the SLAM problem, these thin junction tree filters
have a linear-space belief state and a linear-time filtering
operation. Further approximation yields a filtering operation
that is often constant-time.
Further information | |
|
Authors Mark A. Paskin; | |
|
Get the Source Code! | |
|
Long Description Simultaneous Localization and Mapping (SLAM) is a fundamental problem in mobile robotics: while a robot navigates in an unknown environment, it must incrementally build a map of its surroundings and, at the same time, localize itself within that map. One popular solution is to treat SLAM as an estimation problem and apply the Kalman filter; this approach is elegant, but it does not scale well: the size of the belief state and the time complexity of the filter update both grow quadratically in the number of landmarks in the map. This paper presents a filtering technique that maintains a tractable approximation of the belief state as a thin junction tree. The junction tree grows under filter updates and is periodically ``thinned'' via efficient maximum likelihood projections so inference remains tractable. When applied to the SLAM problem, these thin junction tree filters have a linear-space belief state and a linear-time filtering operation. Further approximation yields a filtering operation that is often constant-time. Experiments on a suite of SLAM problems validate the approach. | |
|
Example Images | |
 TJTF in Action |
|
|
Type of Map feature maps | |
|
Hardware/Software Requirements Java | |
|
Documentation JavaDoc Documentation of the Code | |
|
Papers Describing the Approach Mark A. Paskin: Thin Junction Tree Filters for Simultaneous Localization and Mapping, In the Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2003 (link) : Thin Junction Tree Filters for Simultaneous Localization and Mapping, Technical Report, University of California, Berkeley, 2002 (link) | |
|
License Information This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. The authors allow the users of OpenSLAM.org to use and modify the source code for their own research. Any commercial application, redistribution, etc has to be arranged between users and authors individually and is not covered by OpenSLAM.org. Mark A. Paskin is distributing the code he used to run his experiments (under the GNU public license), but be warned: this code is research-ware, pure and simple. | |
|
Further Information While I was writing it, I made every attempt to document the code and to design it in a modular and extensible fashion. However, I have not had time to make the code fully presentable; for example, there is no manual. Thus, this code will probably be useful only to people that are willing to spend a decent amount of effort. I do think that the design of the library is easily understood from the documentation, and I think it could be very helpful to others that would like to code up SLAM algorithms. I spent a lot of time on object design. The code comes in two parts: 1. A Java library. This library contains an implementation of the thin junction tree filter (specialized for SLAM), as well as the Kalman and Information filters. To see what's included, you can browse the documentation. 2. A Matlab interface to the Java library. This interface includes code to create SLAM simulations, run filters, and to visualize and analyze the results. To get a brief idea of what's included, you can check out the README.txt file. I found this mixture of Java and Matlab to be very nice for prototyping, because you get the speed of Java, and the scripting and visualization of Matlab. To learn more about this, see the Matlab documentation. This code is not supported, although I am happy to answer questions via e-mail. Furthermore, I do not plan to extend this code; I am currently working on a new implementation of the algorithms in Common Lisp, which has an object model that is far more flexible than that of Java. Acknowledgements. This code uses (and includes) the JAMA Java matrix package. Some of the routines that count floating-point operations were adapted from routines in T. Minka's Lightspeed Matlab library. The Matlab library includes Niclas Borlin's implementation of the Hungarian algorithm, which is used for data association. | |
|
*** OpenSLAM.org is not responsible for the content of this webpage *** *** Copyright and V.i.S.d.P.: Mark A. Paskin; *** |