Robust Simultaneous Planning, Localization and Mapping
The problem of simultaneous localization and mapping (SLAM) or additionally simultaneous planning, localization and mapping (SPLAM) has received considerable attention in the Robotics community in the past several years . The generic SLAM problem consists of an autonomous system navigating in an unknown environment, which it is trying to map while simultaneously localizing itself with respect to the map that it is building. This creates a chicken and egg problem which leads to a very high dimensional estimation problem. In most SLAM techniques, the localization and mapping problem is posed as a Bayesian filtering problem wherein the environment is considered to be a fixed but unknown parameter. There are two basic approaches to solving the Bayes filtering problem. The first alternative is to use the Kalman filtering technique which is applicable to linear-Gaussian systems. However, this method cannot accommodate cases where the distributions are non-Gaussian and cannot provide a solution to the so called “data association” problem . The second method consists of solving the Bayesian filtering problem using particle filtering techniques which can handle the data-association problem in a graceful fashion. The basic drawback with the Bayesian formulation of the SLAM problem is that the estimates of the various environmental components (features) become correlated even though their measurements are mutually independent. This is a basic structural property of the Bayesian formulation of the SLAM problem. Thus, the filter has to estimate a very high dimensional probability distribution on the environment which becomes increasingly computationally intractable as the size of the environment increases.
The addition of planning to the SLAM problem, resulting in the SPLAM problem, adds further to the complexity of the problem . In fact, the planning problem on its own is computationally quite intractable under uncertainty . In this proposal, an alternative to the Bayesian formulation of the SPLAM problem is proposed. In this formulation, the environment is modeled as a stationary but unknown random process that has to be estimated as the autonomous system moves through it and makes observations of the environment. It is assumed that the robot localizes in the environment based on a few landmarks located throughout the environment (which is the Bayesian SLAM problem but with very few parameters compared to case when the whole environment is considered to be an unknown parameter), and then maps the rest of the environment based on this estimate. This problem formulation ensures that the estimates of the landmarks and the environmental components never get correlated. In addition, each individual environmental component can be estimated completely independently of the other components. This drastically reduces the computational burden of the SPLAM problem as the correlation of the various features in the environment need not be considered. The environmental components are estimated using stochastic approximation algorithms. Further, it can be shown that there is a separation principle between the mapping and the planning problems, in that the mapping algorithms can be designed completely independently of the planning algorithms and still be guaranteed to converge.
A hierarchical approach to the planning problem is proposed here. In this approach, the local environment variables and their associated uncertainties are abstracted to global environment variables through the definition of suitable feature vectors, which allows for the definition of “meaningful” approximate Markov Decision Processes (MDP) at the global level. This allows for the maintenance of maps with suitable description of hierarchical environmental variables and their attendant uncertainties at the various levels, which in turn aids in the design of the planning algorithms at the various levels of the hierarchy. In particular, the approach described separates the concern between uncertainties at different time and length scales and provides a hybrid framework to bridge the gap between the discrete and continuous planning methods of motion planning and trajectory generation. The real-time aspect of the problem is addressed by implementing the motion planning algorithms using anytime computational models that incrementally improves the algorithm performance with available computational time
In the Robust Anytime Motion Planning (RAMP) architecture, the motion-planning problem is decomposed into three layers as illustrated in Figure above:
The multi-layer approach to motion planning has also been implemented  using tools from optimal control theory in the receding horizon framework. Figure 6(a) shows the decomposition of an obstacle rich environment into convex feasible sets and fig.6(b) shows the trajectories obtained by repeatedly solving optimal control problems. The advantage of the RHC based method is that the trajectories obtained satisfy the dynamics of the vehicle. The trajectories shown in fig.6(b) are for a 6DOF UAV like model.
PIs: Raktim Bhattacharya, Suman Chakravorty, Tamas Kalmar-Nagy.
• Near Time Optimal Waypoint Tracking of a 3-DOF Model Helicopter - B. Singh, R. Bhattacharya, submitted, AIAA GNC 2007.