8 - Motion Planning

Question 1

What is workspace?

Answer 1

Reachable space within the environment (independent of the robot)

Question 2

What is configuration space?

Answer 2

Full state of the robot in the environment

Question 3

Why use a c-space?

Answer 3

Positions in configuration space tend to be close together for the robot

Can be easier to solve collision checks and join nearby poses

Allows a level of abstraction that means solution methods can solve a wider range of problems

Sometimes helps with wraparound conditions (rotational joints)

Question 4

How can you use a discrete decomposition for path planning?

Answer 4

Graph search: a connectivity graph is constructed and searched

Potential field planning, a mathematical function is imposed on the free space and the gradient of the function is followed to reach goal

Question 5

What are 4 types of graph?

Answer 5

Undirected, directed, unweighted, weighted

Question 6

What is a discrete state space representation?

Answer 6

Reduce continuous state space to a finite set of discrete states

Question 7

How do you make a grid a graph?

Answer 7

Consider states as vertices and transitions as directed edges

Start node, goal node and cost function

Finding the shortest path can be treated as a graph search problem

Question 8

When is a grid square in the c-space?

Answer 8

If it is not inside an obstacle and it is further than the radius of the robot from al obstacle edges

Question 9

What is the algorithm for turning a polygonal C-space into a grid?

Answer 9

Pick a grid square you know is in free space

Do a breadth first search from that start square

As each square is visited by the search, compute the distance to all obstacle edges

Label as free if the distance is greater than the radius of the robot or occupied if the distance is less

Once breadth first search is done, also label all unlabelled squares as occupied

Question 10

What are 4 issues with grid-based representations?

Answer 10

Loss of precision, selecting a grid resolution, type of output path and poor scaling in higher dimensions

Question 11

What is a grid lattice?

Answer 11

Create a set of feasible motion primitives and construct a tree that chains the motions into a sequence

Question 12

What is a visibility graph?

Answer 12

Create edges between all pairs of mutually visible vertices

Search resulting graph

Question 13

What are pros and cons to visibility graph?

Answer 13

Optimal plan, good in sparse environments

Limited to straight 2D , needs polygonal obstacles, safety at stake

Question 14

What are pros and cons to voronoi diagram?

Answer 14

Complete, executability

Not optimal, need long-range sensing

Question 15

What is a Voronoi Diagram?

Answer 15

Maximise the distance between the robot and the obstacles, draw equidistance lines, search resulting graph

Question 16

What are pros and cons to exact cell decomposition?

Answer 16

Complete, good in extremely sparse environments

Low computational complexity

Question 17

What is the process of forward search?

Answer 17

Mark a node active

Explore its neighbours and mark them as open

Mark the parent node as visited

Question 18

What is an open set in a forward search?

Answer 18

A list of frontier (unexpanded) plans. Keeps track of what nodes to expand next. For each node in the open list, we know of at least one path to it from the start

Question 19

What are the pros of breadth first search?

Answer 19

Complete (will find the solution if it exists), guaranteed to find the shortest path, first solution that is found is the optimal path

Question 20

What is a depth first search?

Answer 20

DFS starts at the root node and explores as far as possible along each branch

Similar implementation to BFS but with a stack (lifo) queue

Question 21

Discuss DFS vs BFS

Answer 21

DFS is not complete for infinite trees (may explore an incorrect branch infinitely deep, never come back)

BFS is complete

DFS has lower memory footprint

Not often used for path search, but to completely explore a graph

Both are simple to implement

Question 22

What is Dijkstra’s algorithm?

Answer 22

BFS with edge costs, expanding in order of closest to start

Asymptotically the fastest known single-source shortest path algorithm for arbitrary directed graphs

Open queue is ordered according to currently known best cost to arrive

Question 23

What is A*?

Answer 23

An informed search.

Uses domain knowledge to bias the search

Favours actions that might get closer to the goal

Each state gets a value

f(x) = g(x) + h(x)

g(x) = cost incurred so far from the start satte

h(x) = estimated cost from here to the goal (heuristic goal)

Question 24

How do you choose heuristics?

Answer 24

The closer h(x) is to the optimal cost to the goal, the more efficient the search

Question 25

What must the heuristic be?

Answer 25

Admissible (never overestimate the cost)

Consistent

Question 26

What is a randomised graph search?

Answer 26

Divide the region uniformly into small cells, randomly sample locations in the space and try and connect the samples

Question 27

What are Probabilistic Road Maps?

Answer 27

Roadmap construction by randomly generating nodes, connect pairs of nodes to form a roadmap. Discard invalid nodes and paths

Query processing by connecting start and goal to roadmap and finding path in roadmap between start and goal

Question 28

What are the pros to PRMs?

Answer 28

Probabilistically complete, applied easily to high dimensional C-space and supports fast queries with enough pre-processing

Question 29

What are the cons to PRMs?

Answer 29

Don’t work as well for some problems, unlikely to sample edges in narrow passages, only probabilistically complete

Question 30

What is a field method?

Answer 30

Create a field (or gradient) that pushes the robot away from obstacles and towards the goal