8 - Motion Planning Flashcards
What is workspace?
Reachable space within the environment (independent of the robot)
What is configuration space?
Full state of the robot in the environment
Why use a c-space?
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)
How can you use a discrete decomposition for path planning?
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
What are 4 types of graph?
Undirected, directed, unweighted, weighted
What is a discrete state space representation?
Reduce continuous state space to a finite set of discrete states
How do you make a grid a graph?
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
When is a grid square in the c-space?
If it is not inside an obstacle and it is further than the radius of the robot from al obstacle edges
What is the algorithm for turning a polygonal C-space into a grid?
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
What are 4 issues with grid-based representations?
Loss of precision, selecting a grid resolution, type of output path and poor scaling in higher dimensions
What is a grid lattice?
Create a set of feasible motion primitives and construct a tree that chains the motions into a sequence
What is a visibility graph?
Create edges between all pairs of mutually visible vertices
Search resulting graph
What are pros and cons to visibility graph?
Optimal plan, good in sparse environments
Limited to straight 2D , needs polygonal obstacles, safety at stake
What are pros and cons to voronoi diagram?
Complete, executability
Not optimal, need long-range sensing
What is a Voronoi Diagram?
Maximise the distance between the robot and the obstacles, draw equidistance lines, search resulting graph
What are pros and cons to exact cell decomposition?
Complete, good in extremely sparse environments
Low computational complexity
What is the process of forward search?
Mark a node active
Explore its neighbours and mark them as open
Mark the parent node as visited
What is an open set in a forward search?
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
What are the pros of breadth first search?
Complete (will find the solution if it exists), guaranteed to find the shortest path, first solution that is found is the optimal path
What is a depth first search?
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
Discuss DFS vs BFS
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
What is Dijkstra’s algorithm?
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
What is A*?
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)
How do you choose heuristics?
The closer h(x) is to the optimal cost to the goal, the more efficient the search
What must the heuristic be?
Admissible (never overestimate the cost)
Consistent
What is a randomised graph search?
Divide the region uniformly into small cells, randomly sample locations in the space and try and connect the samples
What are Probabilistic Road Maps?
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
What are the pros to PRMs?
Probabilistically complete, applied easily to high dimensional C-space and supports fast queries with enough pre-processing
What are the cons to PRMs?
Don’t work as well for some problems, unlikely to sample edges in narrow passages, only probabilistically complete
What is a field method?
Create a field (or gradient) that pushes the robot away from obstacles and towards the goal
