8 - Motion Planning Flashcards
(30 cards)
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
