Chapter 6: Planning and Navigation

Question 1

Cognition

Answer 1

Represents the purposeful decision making and execution that a system utilizes to achieve its highest-order goals.

Question 2

Navigation competence

Answer 2

Given partial knowledge about its environment and a goal position or series of positions,

navigation encompasses the ability of the robot to act based on its knowledge and sensor values,

so as to reach its goal positions as efficiently and reliably as possible.

Question 3

Path planning

Answer 3

Given a map and a goal location, identify a trajectory that will cause the robot to reach the goal location when executed.

Question 4

Obstacle avoidance

Answer 4

Given real-time sensor readings, modulate the trajectory of the robot in order to avoid collisions.

Question 5

Completeness

Answer 5

A robot system is complete if and only if,

for all possible problems (i.e. initial belief states, maps and goals),

when there exists a trajectory to the goal belief state,

the system will achieve the goal belief state.

Question 6

Path-planning: Graph search

Answer 6

A connectivity graph in free space is first constructed and then searched. The graph construction process is often performed offline.

Question 7

Path-planning: Potential field planning

Answer 7

A mathematical function is imposed directly on the free space.

The gradient of this function can then be followed to the goal.

Question 8

Visibility graph

Answer 8

The visibility graph for a polygonal configuration space C consists of edges joining all pairs of vertices that can see each other (including both the initial and goal positions as vertices as well).

The unobstructed straight lines (roads) joining those vertices are obviously the shortest distances between them.

The task of the path planner is then to find a (shortest) path from the initial position to the goal position along the roads defined by the visibility graph.

Question 9

2 Caveats when employing visibility graph search

Answer 9

1. The size of the representation and the number of edges and nodes increase with the number of obstacle polygons.
   Therefore, the method is extremely fast and efficient in sparse environments, but it can be slow and inefficient compared to other techniques when used in densely populated environments.
2. Solution paths found by graph search tend to take the robot as close as possible to obstacles on the way to the goal. More formally, we can prove that the shortest solutions on the visibility graph are optimal in terms of path length.

Question 10

Voronoi diagram

Answer 10

A complete road map that tends to maximise the distance between the robot and obstacles on the map.

For each point in free space, its distance to the nearest obstacle is computed. If you plot that distance as the height coming out of the page, it increases as you move away from an obstacle.

At points that are equidistance from two or more obstacles, such a distance plot has sharp ridges.

The Voronoi diagram consists of the edges formed by these sharp ridge points.

Question 11

2 Weaknesses of Voronoi diagram solution paths

Answer 11

They are usually far from optimal in the sense of total path length.

In the case of limited range localization sensors. Since its edges maximize the distance to obstacles, any short-range sensor on the robot will be in danger of failing to sense its surroundings.

Question 12

Exact cell decomposition

Answer 12

The boundary of cells is based on geometric criticality. The resulting cells are either completely free of completely occupied, and therefore path planning in the network is complete.

The particular position of the robot within each cell of free space does not matter. What matters is the robot’s ability to traverse from each free cell to adjacent free cells.

Question 13

Key disadvantage of exact cell decomposition

Answer 13

The number of cells, and therefore the overall computational planning efficiency, depends on the density and complexity of objects in the environment.

Question 14

Lattice graph

Answer 14

Formed by constructing a base set of edges, and then repeating it over the whole configuration space to form a graph.

Question 15

Why is randomized graph search useful in path planning?

Answer 15

When encountering complex high-dimensional path planning problems, it becomes infeasible to solve them exhaustively within reasonable time limits.

Reverting to heuristic search is often not possible due to the lack of an appropriate heuristic function.

Reduction of problem dimensionality frequently fails due to velocity and acceleration constraints imposed on the model.

Randomized search becomes useful as it forgoes solution optimality for faster computation.

Question 16

Rapidly Exploring Random Trees (RRTs)

Answer 16

RRTs typically grow a graph online during the search process and thus a priori only require an obstacle map, but no graph decomposition.

The algorithm begins with an initial tree (which might be empty) and then successifvely adds nodes, connected via edges, until a termination condition is triggered.

During each step, a random configuration q_rand in the free space is selected. The tree node closest to q_rand (denoted q_near) is then computed.

Starting from q_near, an edge is grown toward q_rand using an appropriate robot motion model.

The configuration q_new at the end of this edge is then added to the tree if the connecting edge is collision-free.

Question 17

Potential field path planning

Answer 17

Creates a field, or gradient, across the robot’s map that directs the robot to the goal position from multiple prior positions.

Question 18

Local obstacle avoidance

Answer 18

Local obstacle avoidance focuses on changing the robot’s trajectory as informed by its sensors during robot motion.

The resulting robot motion is both a function of the robots current or recent sensor readings and its goal position and relative location to the goal position.

Question 19

Bug algorithm

Answer 19

Simple obstacle-avoidance algorithm.

Follow the contour of each obstacle in the robot’s way and thus circumnavigate it.

Question 20

Bugl algorithm

Bug1 vs Bug2

Answer 20

With Bug1, the robot fully circles the object first, then departs from the point with the shortest distance toward the goal.

With Bug2, the robot begins to follow the object’s contour, but departs immediately when it is able to move directly toward the goal.