# Robot Localization Simulator

by Apurv Verma (Author) Prateek Garg (Author) Kumar Ashwani (Author)

Seminar Paper 2012 42 Pages

## Contents

List of Figures

Nomenclature

1 Robot Localization Algorithm

2 Geometrical Algorithms
2.1 Computing Visibility Polygons
2.1.1 Visibility Polygon of a Point Inside a Polygon
2.1.2 Visibility Polygon of an edge of the polygon
2.1.3 Shortest Path Calculation

3 Hypothesis Generation
3.1 Hypothesis Generation
3.2 Algorithm
3.3 Examples

4 Majority Rule Map
4.1 Computing the Majority Rule Map P maj
4.1.1 Construction
4.1.2 Majority Rule Map Type
4.1.3 CGAL’s Arrangement class to generate Overlay
4.1.4 Algorithm
4.1.5 Examples
4.2 Connected Component containing Origin in P maj
4.2.1 Algorithm
4.2.2 Examples

5 Computing the Group Boundaries
5.1 G ij
5.2 K i
5.3 Examples

6 Computing Reference Points (Q H)
6.1 Introduction to Reference Points
6.2 Algorithm
6.3 Examples

Appendix

Appendix

References

## List of Figures

2.1 Visibility Polygon of Point

2.2 Visibility Polygon of Point

2.3 Visibility Polygon of Edge, Illustration taken from:Guibas

2.4 Visibility Graph

2.5 Visibility Polygon of Edge

2.6 Visibility Polygon of Edge

3.1 Hypothesis Generation

3.2 Hypothesis Generation

4.1 Majority Rule Map Construction

4.2 Majority Rule Map shown in green

4.3 Map Polygon with robot position and Visibility Polygon

4.4 Majority Rule Map

4.5 (a) Graph G (b) Dual Graph for G

4.6 A Majority Map(blue point represents origin)

4.7 Connected Component Containing Origin

5.1 F

5.2 (a) Window Edge(w (e)) (b) G ij

5.3 Map Polygon with Hypotheses

5.4 G 02 and F

5.5 G 01 and F

5.6 K 1

6.1 Reference Points in blue color and hypotheses in green color

6.2 Reference Points in blue color and hypotheses in green color

6.3 Reference Points in blue color and hypotheses in green color

## Nomenclature

Greek Symbols

γ A point inside the polygon with origin choosen at one of the hypotheses.

γ can also sometimes denote a region.

Acronyms

H A list of points which denotes potential robot positions.

P maj The majority rule map of all translates of the polygon. The translates of the polygon are obtained by choosing one hypothesis as the origin and translating all the remaining hypotheses to this chosen origin.

G ij For the translates corresponding to pair of hypotheses h i and h j, G ij is the origin containing region obtained by taking the lower envelope of visibility polygons of all type 1 and type 2 edges of the union-polygon.

An edge is of type 1 or type 2, if it belongs to exactly one of the translates. g i Set of all points at which h i does not share the majority opinion about i. K i The majority rule map of G ij ’s

Maj (γ) Set of hypothesis which share the majority opinion about γ.

## Chapter 1 Rob o t Localization Algorithm

Input:

Map polygon P, the visibility polygon V.

Output:

The robot localizes to its actual position h ∈ H

1: Compute the set of hypotheses H.
2: while | H | > 1 do
3: Compute the majority-rule map P maj
4: Compute the polygons G ij for each pair of hypotheses, h i and h j
5: Compute the majority rule map K i of G ij ’s
6: Find the edges on the boundary of K i which are not on the boundary of
P maj
7: Draw grids and compute the set of coordinates Q H on these edges.
8: Make instance I P,H of 1 -Group Steiner Problem
9: Solve I P,H to compute a half computing path C ⊂ P maj
10: Half-Localize by tracing C and making observations at coordinates Q H
11: Move back to the starting location.
12: end while

## Chapter 2 Geometrical Algorithms

### 2.1 Computing Visibility Polygons

Visibility polygon is an indispensable component in the hypothesis generation step of the algorithm. Since CGAL had no inbuilt support for computing visibility polygons we implemented the following two routines for our purposes.

- Visibility Polygon of a point inside a polygon
- Visibility Polygon of an edge of the polygon.

#### 2.1.1 Visibility Polygon of a Point Inside a Polygon

Deﬁnition 1 Visibility Polygon of Point: p is the bounded polygonal region of all points of the polygon visible from p .

The following is the C++ function in the ﬁle PolygonUtil.cpp. We pass the map polygon and the point P, whose visibility polygon is to be computed. The function returns the visibility polygon of P as another Polygon type. In setV isibleP oints we collect all those points which are directly visible from P. Note that all these points will form a part of the visibility polygon of P since they are directly visible from P. These points can contain some reﬂex vertices as well. A reﬂex vertex occludes a portion of map resulting in a spurious vertex [Guibas and Raghavan ]. Each spurious vertex which is a part of the vis- ibility polygon can be obtained by extending the line joining the point P to a

reﬂex vertex. We do this in the if block and collect all the spurious vertices also. Finally we sort all the vertices obtained by traversing along the boundary of the map in anticlockwise direction to get the visibility polygon of P.

Polygon PolygonUtil::CalcVisibilityPolygon(Polygon& map, Point& point)

{

Polygon setVisiblePoints = VisiblePointSet(map,point); list<Point> listVisiblePoints;

for (VertexIterator vi = setVisiblePoints.vertices_begin(); vi != setVisiblePoints.vertices_end(); ++vi)

{

listVisiblePoints.push_back(*vi); if(IsReflex(map,*vi))

{

Ray rayToCorner(point,*vi); std::list<Point> intPointList; std::list<Point>::iterator it;

FindCandidatePoints(map,rayToCorner,intPointList); if(intPointList.size() > 0) {

intPointList.sort(CompareDistance1);

Point spuriousVertex = *intPointList.begin(); listVisiblePoints.push_back(spuriousVertex);

}

}

}

return sortPoints(listVisiblePoints);

}

Algorithm

1. Collect all the vertices of the polygon which are visible from the point P.

2. Iterate over the list of visible vertices and for each reﬂex vertex, compute

Abbildung in dieser Leseprobe nicht enthalten

the spurious vertex introduced in the visibility polygon.

3. Finally sort all the vertices in an order so that they form a simple polygon.

Examples

The point P is shown in blue and the visibility polygon is shown in green.

illustration not visible in this excerpt

Figure 2.1: Visibility Polygon of Point

illustration not visible in this excerpt

Figure 2.2: Visibility Polygon of Point

#### 2.1.2 Visibility Polygon of an edge of the polygon

Deﬁnition 2 Visibility Polygon of Edge: e is the bounded polygonal region of all points of the polygon visible from any point on the edge e .

Abbildung in dieser Leseprobe nicht enthalten

The algorithm for the visibility polygon of an edge has been taken from Guibas. Let E be the set of edges of the polygon. To ﬁnd the visibility polygon of an edge AB, we compute, for each of the remaining edges of the polygon the portion of it which is weakly visible from the edge AB. Once we obtain these portions we join all of them to obtain the visibility polygon of the edge AB. Im- plementation of this algorithm requires computing shortest path between vertices of the polygon, the construction of which we describe in the next section. For now assume that we have at our disposal a routine which gives the shortest path between two vertices of the polygon as a list of Point type.

The main steps of computing the visible portion of an edge CD from another edge AB of the polygon can be enumerated as follows.

Algorithm

1. Compute the shortest path P AC, from A to C and the shortest path P BD, from B to D. Call this pair 1.
2. Similarly compute the shortest path P AD, from A to D and the shortest path P BC, from B to C. Call this pair 2.
3. Find out which of these pairs is outward convex. An outward convex pair implies an hourglass shape is formed by the two paths.
4. If none of the pairs is outward convex this means that no portion of edge CD is visible from any point on edge AB and we can completely ignore such an edge.
5. If one of the pairs is outward convex then without loss of generality, let pair 1 be the outward convex pair. Now compute the shortest paths P AD and P BC.
6. Let X be the point where path P AD and P AC split and let W be the point where path P BD and P BC split. Let Y be the next point on the path P AD and Z be the next point on the path P BC. Extending XY we get one extreme point of the portion of CD visible from AB. We repeat this on other side to get the other extreme point.

illustration not visible in this excerpt

Figure 2.3: Visibility Polygon of Edge, Illustration taken from:Guibas

C alcV isibilityP olygonEdge () calculates the visibility polygon of an edge in PolygonUtil.cpp

Note: This routine computes the visibility polygon of the edge excluding its endpoints. To obtain the visibility polygon of the edge where endpoints are inclusive one could compute the visibility polygon of point at the two endpoints and take a union with the visibility polygon returned by this routine.

#### 2.1.3 Shortest Path Calculation

For the calculation of shortest path between any two vertices of the polygon the following property was exploited.

- The shortest path must turn only at vertices of the polygon.
- It is possible to move from one vertex to the another only if they are visible to each other.

Deﬁnition 3 Visibility Graph The visibility graph of a polygon can be formed as follows. Draw a vertex corresponding to each vertex in the polygon. Draw an edge between two vertices if the line joining the corresponding vertices in the polygon lies completely inside the polygon.

illustration not visible in this excerpt

Figure 2.4: Visibility Graph

For Example

Utilizing these properties we construct a visibility graph for the polygon and use the normal dijikstra’s single source shortest path algorithm of Boost Graph Library BOO on the visibility graph obtained. The following two functions do the above mentioned tasks.

- PolygonUtil::PrepareVisibilityGraph(Polygon& map, Point vertex[])
- PolygonUtil::CalcShortestPath(int source,graph_t& g,Point vertex[])

[...]

## Details

Pages
42
Year
2012
ISBN (eBook)
9783656443780
ISBN (Book)
9783656443599
File size
730 KB
Language
English
Catalog Number
v215036
Institution / College
Indian Institute of Technology, Delhi 