Topological SLAM (Tapus, Siegwart, 2005)

Main idea: This approach proposes the concept of fingerprints of places to localize the robot and to build a topological map of the environment with some geometric information. It uses Partially Observable Markov Decision Processes (POMDP).

Fingerprint of places: is a circular list of features, where the ordering of the set matches the relative ordering of the features around the robot.

Uncertainty of features. The probability of a feature being present in the environment when robot perceives it.

Bayesian approach for localization with fingerprints of places:

1. Supervised learning. Robot explores several locations and stores the fingerprints of the visited places in a database with the name of the place.
   
2. Application. The robot localizes itself in the environment by acquiring a fingerprint and comparing it with the fingerprints stored. It uses a Bayesian fingerprint matching.

Topological mapping:

• The robot first creates and then updates the global topological map.
• A new node is introduced into the topological map whenever the dissimilarity of the newly perceived fingerprint is larger than a threshold.
• Each node is composed of set of similar fingerprints of places using a mean fingerprint.
  

Topological Navigation

• A Partially Observable Markov Decision Process (POMDP) model is used.
  
• POMDP integrates both the robot's motion and exetroceptive sensor report data to estimate the pose distribution.

POMDP is defined as

S = set of environment states
A = set of actions
T(s,a,s') = transition function between environment states based on the performed action
O = possible observations.


Indoor Control Strategy

• The entropy of the probability distribution over the states of the topological map is used.
• When the robot is confident, the action that is optimal to that state is executed.
• When the robot is not confident about its state, the robot uses
• mid-line following if the previous action was mid-line following
• leave the room if the prevoius action was go to the center of the free space

Map Update

The strategy for updating the map is:

• When the entropy of the belief state is low enough, the map will be updatedand so the fingerprint and the uncertainty of the features will also be updated.
• If the entropy is above the threshold, then updating will not be allowed,and the robot will try to reduce the entropy by continuing navigation with localization.
  

Closing the loop

Non-explicit loop-closing algorithm. Based on the information provided by the POMDP when two distribution probabilities are observed a loop is identified.