provide world map for ekf global localization problem

Question

I am trying to implement the ekf_localization algorithm in page 217 (Table 7.3) of the probabilistic robotics book by Thrun.

From my previous post, I understand that I need to extract observed features on step 9 of the algorithm given in the book. So I am planning to use a line extraction algorithm (https://github.com/kam3k/laser_line_extraction) to extract lines, then find the center point of the line and use that point as my observed feature in step 9.

Click part1 part2 to see table 7.3.

Now, I am having trouble understanding what is the map (m) input.

Since, the ekf_localization algorithm assumes that the map is already giving, and let’s say figure 1 is the actual map that my robot will navigate in. Does this mean, that m consist of points in the world coordinate frame and that I can manually choose them? For example, the dots in figure one are my point landmarks that I provide for the algorithm (m = {(2,2), (2,4), 5,1), (5,2), (5,3), (6,2)}). If so, how many points should I provide?

Be great if you could help C.O Park.

Answer 1

In EKF slam generally we include landmarks which can be marked as points: Corners, columns, trees etc. The uncertainties for landmarks are calculated by assuming that those are point landmarks. (1) Since it's not straightforward to include a line in EKF SLAM you need to come up with a solution to convert them to feature points. Using the center point of the line will not help to track the entire line. Adding sampled points from a line as landmarks will increase the matrix size as well as the computational cost. Following are some methods that I have tried in this case.

1) Convert the line to $y = mx + c$ form and include m and c values in the state matrix. However this doesn't provide the limits of the line.

2) Include the starting points and end points of the line. This is the most computationally efficient way to include a line in EKF SLAM.

You need to modify your measurement model to recover the line from the state matrix and generate measurements.

Answer 2

I can manually choose them? -> Generally, that process is called as "matching" or "data association". You can do it manually as well. The simplest solution is finding closest map point of your estimated point by Euclidian distance. You will find other probabilistic methods in the later part of the book.

One point is the minimum but could be unstable or not that accurate. (I am not sure actually. You need to double check.) Two points will be sufficient to determine distance and rotation. The more, the better.