טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDmitry Kopitkov
SubjectEfficient Belief Space Panning in High-Dimensional
State Spaces by Exploiting Sparsity and
Calculation Re-Use
DepartmentDepartment of Autonomous Systems and Robotics
Supervisor Assistant Professor Indelman Vadim


Abstract

Belief space planning (BSP) is a fundamental problem in robotics and artificial intelligence, with applications including autonomous navigation and active SLAM. The information-theoretic BSP is its sub-problem where objective is to find action which will minimize the posterior uncertainty of the state. In order to solve this problem, the state of the art approaches typically propagate the belief state, for each candidate action, through calculation of the posterior information (or covariance) matrix and subsequently compute its determinant (required for entropy). The per-candidate time-complexity of such approaches is O(n3) where n is the state dimension and typically is very large, making such approaches to be very computationally expensive.

In this research we develop a computationally efficient approach for evaluating the information theoretic term within belief space planning (BSP), where during belief propagation the state vector can be constant or augmented. We consider both unfocused and focused problem settings, whereas uncertainty reduction of the entire system or only of chosen variables is of interest, respectively. Our approach reduces run-time complexity by avoiding posterior belief propagation and determinant calculation of large matrices. We formulate the problem in terms of factor graphs and show that belief propagation is not needed, requiring instead a one-time calculation that depends on (the increasing with time) state dimensionality, and per-candidate

calculations that are independent of the latter. To that end, we develop an augmented version of the matrix determinant lemma, and show computations can be re-used when evaluating impact of different candidate actions. These two key ingredients and the factor graph representation of the problem result in a computationally efficient (augmented) BSP approach that accounts for different sources of uncertainty and can be used with various sensing modalities. We examine the unfocused and focused instances of our approach, and compare it to the state of the art, in simulation and using real-world data, considering problems such as autonomous navigation

in unknown environments, measurement selection and sensor deployment, carried out at the Autonomous Navigation and Perception Lab at the Technion. We show that our approach significantly reduces running time without any compromise in performance.