COMP 290-058 Motion Planning Project

Robot Localization in a Terrain Map

Feng Pan, Qi Zhang

1. Motivation & Object

  Robot Localization problem has been extensively researched especially together with the mapping problem. However, most works focus on robot moving in an in-door environment with odometry and sensor measurements. Our project intend to localize a robot in an out-door, terrain map environment.

 

 

2. Problem Definition

Given a Robot, which has a terrain map of the entire environment and keep the measurements of its odometry and (relative) altitude value, try to locate the position of the robot on the map.

Basically, the map is an RxR->R function, for each point in a 2-D space, an altitude value is defined. And the robot knows how far (the distance) it has moved and the varying of altitude during its moving.

 

 

3.    Terrain Model and Robot Measurements

   As the first step, we will use a matrix to represent the terrain model. The matrix will be of size X x Y, the element at M(i,j) represent the point located at (X=i and Y=j) and the value of element M(i,j) is the altitude value of the point at (X=i and Y=j). An example of the matrix and the corresponding terrain is shown in the first figure above. But our approach shall be able to apply to other terrain models such as Triangulated Irregular Network(TIN).  
   We assume that the robot knows the terrain matrix and also it receives measurement data. The measurement contains two parts: the odometry measurement and the relative altitude measurement. Its odometry measurement records how far the robot has moved at each position science it started. And the relative altitude measurement records the relative altitude at each position compared with the initial starting position. Since we are using the matrix terrain model, we restrict the robot to be moving along edges and diagonals in the matrix.  


 

     Therefore, the robot gets a list of measurement (d0,d1,d2,,,dT) which would be either odometry or altitude. And it knows
 the matrix terrain map. The problem is that based on this information, how can we locate the current position of the
 robot in the map.

 

 

4. Possible Approaches

  Several approaches can be used to solve the problem.

a)      Build index structure according to the varying of altitude around each point in the map. Then query by the index using the robot’s measurement records (odometry & altitude).

b)      Using a probability framework. To maintain a probability density function over the entire map about where the robot probably might be. And update the density function based on the robot’s measurements until a unique position is identified.