Navigation

Question 1

What is navigation? (questions)

Answer 1

Navigation can be seen as answering for questions:
1. Where am I going? mission planning
2. What is the best way there? path planning
3. Where have I been? SLAM
4. Where I am? localization

Question 2

Spatial memory

Answer 2

Associated to the path planning task that depends on the robot’s world representation. A robot’s world representation and how it is maintained over time is its spatial memory.

Spatial memory is the heart of the cartographer module, which should provide methods and data structures for processing and storing output from current sensory inputs.

Question 3

4 basic functions of spatial memory

Answer 3

• attention: what features or landmarks should I look for next?
• reasoning: can that surface support my weight?
• path planning: how to reach a place?
• information collection: have I ever seen this place before?

Question 4

Two forms of the spatial memory

Answer 4

• route, topological, or qualitative
• layout or metric or quantitative

draw the graph 13.2

Question 5

3 major map models

Answer 5

• grid-based: collection of discretized obstacle/free-space pixels
• features-based: collection of landmark locations and correlated uncertainty
• topological: collection of nodes and their interconnections

Question 6

Topological navigation

Answer 6

• represents space in terms of connections between landmarks
• perspective dependent: landmarks visualization depends on the position and orientation of the robot
• it’s called “topological” because it relates landmarks in space using topology (e.g. a door connects two rooms)

Question 7

Metric navigation

Answer 7

• represents space through a map (so we have a layout representation)
• it is essentially a bird’s-eye view of the world: it is not dependent of the perspective of the agent; the agent is assumed to be able to translate the layout into features to be sensed.

Question 8

Algorithms for topological and metric path planning

Answer 8

• topological path planning: uses computer science algorithms e.g. Dijkstra’s single source shortest path alg. The number of nodes in the graph is fearly small.
• metric path planning: applies more specialized path planning alg. often a variant of the A* alg. that can efficiently handle planning through large empty spaces where each block of empty space may be a node in the graph.

Question 9

Landmark

Answer 9

Is one or more perceptually distinctive feature of interesent on an object or locale.

A landmark can be a grouping of objects (e.g. McDonald’s sign)

Properties:
* be readily recognizable
* support the task dependent activity
* be perceivable from many different viewpoints
* it should be passive (no emitted energy)
* it should perceivable over the entire range where the robot might need to see it
* it should have distinctive or, if possible, unique features

Question 10

How a landmark is used?

Answer 10

• localization wrt the map
• in path planning, landmarks are useful for telling the robot when a particular segment is ended and another one is started
• if the robots finds a new landmark (not present on the map), it can extend the map

Question 11

Natural and artificial landmarks

Answer 11

• Natural landmarks: are physical features found in the environment (e.g. a mountain or McDonald sign)
• Artificial landmarks: are existing objects or locales to which features have been added in order to support the landkmarks recognition or some other perceptual tasks

Question 12

Gateway

Answer 12

Is a particular type of landmark. Through a gateway the robot has the opportunity to change its overall direction of navigation.

Question 13

Relational methods

Answer 13

Is a way of representing the world in topological navigation. Relates distinctive places (nodes) to each other by the local control strategies (edges).

The world can be seen as a graph. Nodes represents gateways, landmarks, or goals. Edges represent a navigable path between two nodes (to them we can attach additional informations).

Question 14

Distinctive places for relational methods

Answer 14

Is a landmark that the robot could detect from a nearby region called neighborhood thanks to its specific features.

In the topological representation of Kuiper and Byun (where they use distinctive places), each node is a distinctive place. Once in the neighborhood of a node, the robot can position itself, using sensor readings, in a known spot relative to the landkmark. This spot is called distinctive place.

Question 15

Hill climbing algorithm in relational graphs

Answer 15

When the robot senses a landmark, it fills in values for a set of features then it starts the hill-climbing algorithm in order to position itself in a fixed position wrt to the landkmark where the previously set values are maximized.

The position reached is called distinctive place.

Question 16

Advantages and disadvantages of the distinctive place concept

Answer 16

Advantages:

• eliminates any navigational errors at each node
• supports the discovery of new landkmarks since the robot can detect distinctive places

Disadvantages:

• perception problems: good distinctive places are hard to come by (features such as corners are very numerous in the world)
• local control strategy hard to design in some environments

Question 17

Associative methods

Answer 17

Type of topological navigation system that converts sensor observations into the direction to go to reach a particular landkmark.

In order to use this method, landkmarks usually have two attributes:

• perceptual stability: views of the location that are close together should look similar
• perceptual distinguishability: views far away should look different

They are used by some animals in order to develop the visual homing.

Question 18

Kuipers and Byun: Spatial Hierarchy

Answer 18

1. landkmark definition
2. topological: connectivity
3. metric: distances

Question 19

4 situations where topological navigation is not sufficient

Answer 19

• UAVs: when the space between the starting node and the destination is not easily abstracted into labeled or perceptually distinctive regions
• fast robots: when the choice of route impacts the control or energy costs of the vehicle
• when the purpose of the path is to allow sensor coverage of an area (the route would be a sequence of waypoints in a coordinate frame)
• the piano mover’s problem: when the pose of the robot is important

Question 20

Metric navigation wrt to the topological navigation

Answer 20

In metric navigation the robot:

• has an a priori map of the env and generates a plan of appropriate movements to reach a goal
• favor techniques that produce an optimal path or sequence of motions
• usually decompose the path into subgoals consisting of waypoints

think of how topological navigation handle each point

Question 21

Configuration space

Answer 21

The Cspace is a data structure which allows the robot to specify the position of itself and any other objects and robots.

• A good Cspace reduces the number of dimensions a planner has to do.
• The Cspace representations are used in combination with an a priopri map to construct a graph that is used next by a path planning algorithm.

Question 22

4 important Cspace representations

Answer 22

• Meadow Maps
• Generalized Voronoi Graphs
• Regular Grids
• Quadtrees

Question 23

Meadow Maps

Answer 23

• transform free space into convex polygons (remember the important property) that represents safe regions the robot can traverse
• the path planning problem becomes a matter of picking the best series of polygons to transit through

Question 24

Programming steps for constructing a meadow map

Answer 24

We have a metric layout of the environment:

1. increase the size of the objects in order to consider the robot as a point
2. construct convex polygons with line segments between pairs of interesenting features
3. consider the middle point of each line to be a node
4. in the end we have an undirected graph that can be used by a path planning algorithm

Question 25

Path relaxation

Answer 25

Is a technique used for making the paths generated with the meadow map more efficient.

Imagine having a string that goes from the start to the destination. This string is pulled by both sides in order to remove most of the kinks from the path without violating the safe-zone property of convex polygons.

Question 26

3 problems of meadow maps

Answer 26

• generating convex polygons is computationally complex
• for computing polygon boundaries it uses map artifacts rather than things that can be sensed
• unclear how to update or repair the Cspace if new discoveries come out

Question 27

Generalized Voronoi Graphs

Answer 27

The basic idea is to generate lines (called Voronoi edges) equidistant from all points. This line goes down the middle of hallways and openings.

The point where many Voronoi edges meet is know as Voronoi vertex. Each vertex often keeps informations that help the robot’s lcs staying equidistant from all the obstacles.

The overgrowing of the obstacles is no more necessary.

Question 28

Regular Grids

Answer 28

This method superimposes a 2D cartesian grid on the world space. If there’s an object in an area then the related grid element is marked “occupied”.

The central point of a grid element can become a node thus forming a graph.

Question 29

Digitization bias

Answer 29

Is the main problem of regular grids: if a small object falls inside a big cell, the entire cell is marked “occupied” leading to wasted space.

Question 30

Quadtrees

Answer 30

Are a variant on regular grids. A quadtree is a recursive grid.

1. representation starts with big grid elements
2. if an object falls inside a grid element and if the object does not fill the entire cell, the Cspace algorithm divides the element into 4 smaller grids
3. if the object does not fill a particular cell, another recursive division is applied to that cell

Question 31

Motion planning

Answer 31

It is necessary where the dynamics of the robot cannot be abstracted away by assumptions of holonomicity or the part it is carrying can’t be ignored.

Piano mover’s problem

Motion planning must consider (location, pose) of the robot at each point of space and wheter it is possible to move from (loc1, pose1) to (loc2, pose2) without a collision.