A probabilistic approach to Hough Localization

Luca Iocchi, Domenico Mastrantuono, Daniele Nardi

Dipartimento di Informatica e Sistemistica

University "La Sapienza" Roma, Italy

Overview

• Introduction: probabilistic formalization of localization (position tracking)
    
• Hough Transform based map matching
    
• Integration of map matching and odometry with an Extended Kalman Filter
    
• Novel experimental setting and results
   
• Conclusion and future work
    

Probabilistic formalization of Localization

Localization problem

computing the distribution probability for the robot pose  p( l | S )   l = (x y th)

Position tracking

p( l_i | l_i-1,S_i ) ,   l_i-1  is a good estimation of the real pose of the robot.

Map-matching (absolute method)

p( l_i | l_i-1,S_i,M )  or   p( l_i | S_i,M )  (more difficult)

Odometry (relative method)

p( l_i | l_i-1,u_i )  

Prediction-correction approach (integration)

p( l_i | l_i-1,S_i,u_i,M )  from  p( l_i' | l_i-1,u_i )   and    p( l_i | l_i',S_i,M ) .

Hough Transform

HT used for computing the best fitting line of a set of points [Duda&Hart'72].

r = x cos (th) + y sin (th)

Every point (x,y) in the Cartesian plane corresponds to a curve in the Hough domain.

Local Maxima of HT corresponds to the best fitting lines of the set of points.

Hough Localization

1. Map is represented as a set of points in the Hough domain
  
2. Map displacement is computed in the Hough domain.
  

Position tracking  =>  point corrispondences in the Hough space are easy to determine.

Probabilistic formalization of Hough Localization

HT based map alignment provides for the computation of a probability distribution of the robot's pose.

p( l_i | l_i',S_i,M )  can be computed by a (special form of) correlation between  HT(S) and HT(M).

For the integration step we approximate p( l_i | l_i',S_i,M )  with a Gaussian.
  

Integration with Extended Kalman Filter

• EKF = standard technique for integrating map matching and odometry
    
• Kalman Filter (green line) allows for optimal integration of odometry (red) and map matching (blue)

Position error provided by a simulator  (without and with random bumps).
  

Localization evaluation with real robots

Precision  e(t) = || l(t) - r(t) ||, estimated (l) and real (r) pose of the robot

In real robot experiments  r(t) is measured by a  r'(t)  and thus we compute

e'(t) = || l(t) - r'(t) ||

Precision e(t) depends on accuracy of range sensor and on accuracy of measurement of r(t)

How can we measure r(t)?

1. manual measurements at some intervals in time  r'(t_i)
2. global vision system  r'(t)
    

 

 

 

 

Experimental setting

• A global vision system (color CCD camera fixed over the experiment environment), 
• A special marker on the robot (a different one for each robot)
• A vision tracking algorithm.(very simple because of the special marker and not real-time)
  
  
• The robot self-localization module computes  l(t)
• The global vision system computes  r'(t), || r'(t) - r(t) || < e_r with e_r known. 

This setting allows us to compute   e'(t) = || l(t) - r'(t) ||

If   e'(t) >> e_r   then   e(t) ~ e'(t) ...

... but we found out that  e'(t) ^~ e_r   and thus  e(t) < e_r  at every time.

"Localization error is never greater than the positioning measurement error".

Experimental results

1. manual measurements at some intervals in time  e'(t_i) = 13 cm 
2. global vision system  e'(t)  < 16 cm at every time 

Note that the positon error in the corner is always less then the error during robot motion (800 mm/s).
   

Conclusions

Why another localization method?

- low complexity  O(|S|)  ( < 10 ms )
- robust in dynamic environment (e.g. RoboCup)
- easy implementation

Limitations

- polygonal environment (map represented as a set of segments)
- possible lack of features (e.g. parallel lines)
- position tracking

Future work

- global localization