《认知机器人》（英文版） Information Based Adaptive Robotic Exploration

Information Based Adaptive Robotic Exploration Presented by morten rufus blas Overview/Agenda/outline 口 Motivation 口 Introduction 口 Related work D Defining problem and mode Solution Minimizing localization error Maximize gain in explored map Combined Information utilities Integrated Adaptive Information-based Exploration Algorithm 口 Results 口Conc| usIon ■ Novelty Problems

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

Overview/Agenda /outline 口 Motivation 口 Introduction 口 Related work D Defining problem and model 口so| ution: Minimizing localization error Comb imize gain in explored map bined Information Utilities Integrated Adaptive Information-based Exploration Algorithm 口Resu|ts 口Conc| usion 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

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

Overview/Agenda /outline 口 Motivation 口 Introduction 口 Related work D Defining problem and model 口so| ution: Minimizing localization error Comb imize gain in explored map bined Information Utilities Integrated Adaptive Information-based Exploration Algorithm 口Resu|ts 口Conc| usion Problems Extensions Author: Morten Rufus blas April 2004 Introduction a They attempt to maximize the accuracy and speed of their map building process. O How well does the robot know its pose? a 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/RS] Intl Workshop on Intelligent Robots and Systems, 2002 Author: 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 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

Overview/Agenda /outline 口 Motivati 口 Introduction 口 Related work D Defining problem and model 口so| ution: Minimizing localization error Comb imize gain in explored map Integrated Adaptive Information-based Exploration Algorithm 口Resu|ts 口Conc| usion Problems Extensions Author: Morten Rufus blas Related work dHS. Feder]]. Leonard and c m Smith. Adaptive mobile robot navigation and mapping Int. Journal of Robotics research, 18(7): 650 668,1999 aTM. 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 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

Overview/Agenda /outline 口 Motivation 口 Introduction 口 Related work Q Defining problem and model 口so| ution: Minimizing localization error Comb imize gain in explored map bined Information Utilities Integrated Adaptive Information-based Exploration Algorithm 口Resu|ts 口Conc| usion Problems Extensions Author: Morten Rufus blas April 2004 Defining problem and model 口 Problen Optimize control step in order to: D Minimize localization error a Maximize gain in explored map 口Mode|: Solve problem by maximizing information gain

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

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 Defining problem and model A set of possible actions State estimate Info, in state Info. gain in estimate map Composite Utility Select most informative action

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

Overview/Agenda /outline 口 Motivation 口 Introduction 口 Related wor D Defining problem and model 口 Solution Minimizing localization error Maximize gain in explored map Combined Information utilities Integrated Adaptive Information-based Exploration Algorithm 口Resu|t 口Conc| usion Problems Extensions Author: Morten Rufus blas April 2004 Solution Minimizing localization error a Localization is linked to two uncertainties. Measurement, And navigational uncertainty a Adaptively choose actions to maximize information about ■ Robot position Feature positions(the map)

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)

Solution Minimizing localization error a This can be modeled using a cost function C(P) CP=I√Pa)+x∑ⅡAPi raP)+x∑√act(P)(14) D Maximizing information about a state estimate is equivalent to minimizing the determinant of the corresponding covariance matrix o 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

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

Overview/Agenda /outline 口 Motivation 口 Introduction 口 Related wor D Defining problem and model 口 Solution Minimizing localization error Maximize gain in explored map Combined Information utilities Integrated Adaptive Information-based Exploration Algorithm 口Resu|ts 口Conc| usion Problems Extensions Author: Morten Rufus blas April 2004 Solution Maximize gain in explored map Entropy map Occupation grid 000.00693 1.0 0.5 (EMP) 0.6930.6930.6930.50.5 069306930.6930.50.50.5

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.693 0.693 0.693 0.693 0.693 0.693 0.0 0.0 0.693 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.0 (EMP) 1.0 (OCC) Entropy map: Occupation Grid:

Solution: Maximize gain in explored map a The a priori entropy at time tk for grid cell i EnP(x)--∑P()mPar) x;∈X o Given two possible states(OCC, EMP)for OG map this becomes Hui=-P(OCC)In P(OCC)-P(EMP)In P(EMP) Author: Morten Rufus blas April 2004 Solution Maximize gain in explored map Hi=-P(OCC)In P(OCC)-P(EMP)In P(EMF a So for unexplored cell at time H,=-0.5ln0.5-0.5ln0.5 0.693 a For occupied explored cell at tk: H=-llnl-0 Analogous for empty explored cel

Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map † The a priori entropy at time tk for grid cell i: † Given two possible states (OCC, EMP) for OG map this becomes: ( )ln ( ) ( )ln ( ) Hk ,i Pi OCC Pi OCC  Pi EMP Pi EMP Author: Morten Rufus Blas, April 2004 Solution: Maximize gain in explored map † So for unexplored cell at time tk: † For occupied explored cell at tk: „ Analogous for empty explored cell. ( )ln ( ) ( )ln ( ) Hk ,i Pi OCC Pi OCC  Pi EMP Pi EMP 0.693 0.5 ln0.5 0.5ln 0.5 Hk   0 1ln1 0 Hk