1 of 13

Efficient Map Prediction via Low-Rank Matrix Completion

Zheng Chen, Shi Bai, Lantao Liu

2 of 13

Background

2

Scenarios: We solve the map prediction problem in the task of coverage mapping of urban and residential environments.

Observations:

Urban and residential environments reveal strong structured patterns, such as road network and buildings layout, see Fig. (1).
Those environments containing linear dependent structures could be modeled as maze maps, see Fig. (2).

(1)

(2)

3 of 13

Background

3

Observations:

Maze maps have low rank and incoherent structures, see Fig. (3) and Table. I.
Partially sensed maze maps (see Fig. (4) and Fig. (5)) could be restored by Low-Rank Matrix Completion(LRMC).

(4)

?

(5)

?

(3)

4 of 13

Contributions

4

This is the first time to examine and report that many complex urban/residential environments possess low-rank and incoherent structure, and to apply Low-Rank Matrix Completion for map prediction based on sparse, noisy, and partially observed maps.

Our proposed Low-Rank Matrix Completion based map prediction outperforms state-of-the-art map prediction method---Bayesian Hilbert Mapping in terms of mapping accuracy and computation time and is able to perform prediction in real-time.

We perform extensive simulations and demonstrate the effectiveness of our proposed method which allows representative coverage planning methods to achieve faster mapping coverage convergence rates.

5 of 13

Preliminaries

5

Low-Rank Matrix Completion:

Complete a partially observed matrix, whose corresponding ground-truth matrix has a low-rank and incoherent structure.
Mathematically, LRMC is to find a minimal-rank matrix that is consistent with the partial observations.
A formal mathematical formulation is:

Matrix we expect

Observed matrix

Set of observation locations in the matrix

6 of 13

Methodology

6

Solving LRMC in Map Prediction

(a)

(b)

(c)

(d)

Solved by Mazumder, Rahul, Trevor Hastie, and Robert Tibshirani. "Spectral regularization algorithms for learning large incomplete matrices." The Journal of Machine Learning Research 11 (2010): 2287-2322.

7 of 13

Methodology

7

Mapping with Non-myopic Planner

We adopt and adapt a stadard Traveling Salesman Problem (TSP)
We have to determine the number of waypoints for navigation guidance in TSP.

It has theoretically been proved that a partially observed low-rank matrix could be perfectly recovered if the number of sampled entries m obeys:

The placements of way points can de defined as:

The robot can take observations in between any pair of successive sampling way points and may introduce additional observations. This implies we may want to reduce the number of sampled way points.

8 of 13

Experiments

8

Comparison (LRMC vs. BHM) of map prediction on a static urban road network map.

GT map

Partially observed map

Prediction by LRMC

Prediction by BHM

Noisy

Observation

(NO)

Partial

Observation

(PO)

9 of 13

Experiments

9

Accuracy comparison on 20 different mazes (with different linear dependencies but the same value of rank)

Time comparison on 20 different mazes (with different linear dependencies but the same value of rank)

Comparison (LRMC vs. BHM) of map prediction on maze maps (with NO mode).

Accuracy/Time per

Accuracy comparison on different maps with varying rank values

Time comparison on different maps with varying rank values

10 of 13

Experiments

10

Accuracy comparison on 20 different mazes (with different linear dependencies but the same value of rank)

Time comparison on 20 different mazes (with different linear dependencies but the same value of rank)

Accuracy comparison on different maps with varying rank values

Time comparison on different maps with varying rank values

Comparison (LRMC vs. BHM) of map prediction on maze maps (with PO mode).

Accuracy/Time per

11 of 13

Experiments

11

Comparison of coverage planning without vs. with real-time map prediction at different time stamps.

12 of 13

12

13 of 13

Thanks for watching!

Zheng Chen, Shi Bai, Lantao Liu

13