Information Based Adaptive Robotic Exploration Presented by Morten Rufus Blas Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Motivation ? SLAM: ? “There is little value in a robot exploring and mapping new areas when it has no idea of how accurately it knows its own location.” ? Come up with an algorithm to adapt controls to do better exploration. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Introduction ? They attempt to maximize the accuracy and speed of their map building process. ? How well does the robot know its pose? ? How well have different areas been explored? ? In this paper: F. Bourgault, A. Makarenko, S.B. Williams, B. Grocholsky, H.F. Durrant-Whyte, “Information Based Adaptive Robotic Exploration”, presented at IEEE/RSJ Intl. Workshop on Intelligent Robots and Systems, 2002 Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Related work ? H.J.S. Feder, J.J. Leonard, and C.M. Smith. Adaptive mobile robot navigation and mapping. Int. Journal of Robotics Research, 18(7):650– 668, 1999. ? T.M. Cover and J.A. Thomas. Elements of information theory. Wiley series in telecommunications. Wiley, New York, 1991. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Defining problem and model ? Problem: ? Optimize control step in order to: ? Minimize localization error. ? Maximize gain in explored map. ? Model: ? Solve problem by maximizing information gain. Author: Morten Rufus Blas, April 2004 Defining problem and model ? We will be using: ? EKF to model localization (Extended Kalman Filter). ? OG to represent map (Occupation Grid). ? Entropy map (more about this later). Author: Morten Rufus Blas, April 2004 State estimate Info. in state estimate Info. gain in map Composite Utility Select most informative action Defining problem and model A set of possible actions Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Solution: Minimizing localization error ? Localization is linked to two uncertainties: ? Measurement, ? And navigational uncertainty. ? Adaptively choose actions to maximize information about: ? Robot position. ? Feature positions (the map). Author: Morten Rufus Blas, April 2004 Solution: Minimizing localization error ? This can be modeled using a cost function C(P): ? Maximizing information about a state estimate is equivalent to minimizing the determinant of the corresponding covariance matrix. ? C(P) represents the sum of the uncertainty ellipses of both features and robot after the expected observation from the predicted state. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map 0.6930.6930.693 0.6930.6930.693 0.6930.00.0 0.50.50.5 0.50.50.5 0.5 0.0 (EMP) 1.0 (OCC) Entropy map: Occupation Grid: Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? The a priori entropy at time t k for grid cell i: ? Given two possible states (OCC, EMP) for OG map this becomes: )(ln)()(ln)( , EMPPEMPPOCCPOCCPH iiiiik  Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? So for unexplored cell at time t k : ? For occupied explored cell at t k : ? Analogous for empty explored cell. )(ln)()(ln)( , EMPPEMPPOCCPOCCPH iiiiik  693.0 5.0ln5.05.0ln5.0  k H 0 01ln1  k H Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? Expected mutual information gain for cell i: Information gain = current entropy – new predicted entropy Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? Mean conditional entropy over all possible observations: ? It is the expectation of entropy left after an observation. Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? Conditional entropy for cell i after observation z k at time t k : ? Where Bayes rule says: ? Using our two states (OCC, EMP) the conditional entropy can be rewritten as: )|(ln)|()|(ln)|()( , kikikikikik zEMPPzEMPPzOCCPzOCCPzH  Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map 0.6930.6930.693 0.6930.6930.693 0.6930.6930.693 0.50.50.5 0.50.50.5 0.50.50.5 Entropy map: Occupation Grid: Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map 0.00.6930.693 0.6930.6930.693 0.6930.6930.693 0.00.50.5 0.50.50.5 0.50.50.5 Entropy map: Occupation Grid: Information gain going up = 0.693 – 0.0 Going left = 0.693 – 0.0 Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map 0.00.6930.693 0.00.6930.693 0.6930.6930.693 0.00.50.5 0.00.50.5 0.50.50.5 Entropy map: Occupation Grid: Information gain going up = 0.693 – 0.0 Going left = 0.693 – 0.0 Going down = 0.0 – 0.0 Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map 0.00.6930.693 0.00.6930.693 0.00.6930.693 0.00.50.5 0.00.50.5 0.00.50.5 Entropy map: Occupation Grid: Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map ? Total expected information gain from doing a specific action: ? Where S j are the cells covered by scan. ? After you have done an action you update entropy map with measurements. = sum of information gain for each explored cell Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Combined Information Utilities ? Constructed by linear combination: ? SLAM MAX is an upper bound for the SLAM covariance matrix given a number of landmarks. ? OG MAX is total information of a perfectly known OG map. ? Increasing alpha increases accuracy of OG map. Reducing it increases amount of exploration. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Integrated Adaptive Information-based Exploration Algorithm Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Conclusion: Novelty ? Present an information based approach for exploration. ? Present a scheme for combining different types of information. ? Outline the Integrated Adaptive Information-based Exploration Algorithm ? Tests on an actual robot indicate the validity of these approaches. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Conclusion: Problems ?Local Minima: ? They claim it is robust, but is it? ?Global optimization: ? Can be used in multi-step solutions such as path planning but: ?Computational costs grows very rapidly with amount of look-ahead. ?No notion of “closing the loop”. Author: Morten Rufus Blas, April 2004 Overview / Agenda / Outline ? Motivation ? Introduction ? Related work ? Defining problem and model ? Solution: ? Minimizing localization error ? Maximize gain in explored map ? Combined Information Utilities ? Integrated Adaptive Information-based Exploration Algorithm ? Results ? Conclusion ? Novelty ? Problems ? Extensions Author: Morten Rufus Blas, April 2004 Conclusion: Extensions ? Can easily be extended with other types of information metrics. ? It is certainly interesting to extend this for multi-robot systems. ? Further reading/different approaches: ? R. Sim and N. Roy. “Active Exploration Planning for SLAM using Extended Information Filters”. ‘04 Submitted to the Conference on Uncertainty in Artificial Intelligence.