The Robotics Primer Workbook Developed by  USC, iRobot® and Microsoft® Robotics Studio

Categories: Exercise | Player Exercise

Navigation:Exercise2-Topological Path Planning

Contents 1 Topological vs. Occupancy Maps 2 Exercise Setup 3 Part 1: Planning 4 Part 2: Navigation

Topological vs. Occupancy Maps

In Navigation:Exercise1-Path Planning, navigation using occupancy grids was demonstrated. However, occupancy grids are not the only way to do navigation and path planning. In this exercise, you will learn about topological maps. Topological maps represent data as ideas, not as spaces in a grid.

In this example, we will represent the map as a series of squares. Each square will be represented by a number between 0 and 15, depending on the walls present in that square. Each wall, NORTH, SOUTH, EAST, WEST, makes up a bit of that integer.

NORTH = 1 (0001)
WEST  = 2 (0010)
SOUTH = 4 (0100)
EAST  = 8 (1000)

The integer is a result of &-ing all of the walls present. For the map used in the previous exercise, the topological encoding would be:

     0  1  2  3  4  5  6  7  8  9
0 : 15 15 15 15 15 13  5  5  5  3
1 :  9  5  7  9  1  5  5  5  5  6
3 : 10 11 11 10 10  9  5  5  5  3  
4 : 10 10 10 10 10 10 11 11 11 10
5 :  8  6 10 10 10 10 10 10 10 10
6 :  8  5  6 10 10 10 10 10 10 10
7 :  8  5  5  6 10 10 10 10  6 10
8 : 10 13  5  5  6  8  2 10  9  2
9 : 12  5  5  5  5  6 12  6 10 14
10:  9  5  5  5  5  5  5  5  4  7
11: 12  5  5  5  5 15 15 15 15 15

Exercise Setup

In this exercise, we will use a topological encoding of a map for navigation. In contrast to the last exercise, where the hardest part of the exercise was the actual planning of the path, the planning for the topological encoding of this map is a related, but smaller, problem. This exercise will focus on using an encoded map for navigation.

Part 1: Planning

Using the encoded map above, plan a path from (5,0) to (4,11). The wavefront algorithm used in the previous exercise can be used again. For this exercise, construct a sequence of points from (5,0) to (4,11) for the robot to follow to get to the end of the maze. From that sequence of points, a series of actions, such as MOVE FORWARD, TURN LEFT, etc.

Part 2: Navigation

The navigation portion of this exercise involves taking that list of actions and executing them. Since each square of the maze may be of different sizes, it is important to use the sensors on the robot to detect features in the maze, such as a hallway, or a corner.