Computational Motion Planning
Grassfire / Breadth First Search
slides are from different sources, e.g. C.J. Taylor (UPenn), …
Copyright By PowCoder代写 加微信 powcoder
Planning on a grid
• The goal is to construct a path through the grid/ graph from the start to the goal
Planning on a grid
• Typically there are many possible paths between two nodes.
• We are usually interested in the shortest paths.
Planning on a grid
o Construct the shortest path between the start and the goal location.
Planning Procedure – Grassfire Algorithm
• Begin by marking the destination node with a distance value of 0
Planning Procedure – Grassfire Algorithm
• On every iteration find all the unmarked nodes adjacent to marked nodes and mark them with that distance value + 1.
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
• On every iteration the marking radiates outward from the destination like a fire spreading – hence the name
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
• The distance values produced by the grassfire algorithm indicate the smallest number of steps needed to move from each node to the goal
• Note: numbers radiate outward from the destination node, like a fire.
Planning Procedure – Grassfire Algorithm
Practical procedure:
• (1) Start at the destination node.
• (2) Maintaining a list of nodes.
• (3) On every iteration of the algorithm, take the first node off the list, mark its unvisited neighbors with the current node’s distance value plus one and add them to the end of the list.
Grassfire algorithm – pseudo code
• For each node n in the graph o n.distance = Infinity
• Create an empty list.
• goal.distance = 0, add goal to list.
• While list not empty
o Let current = first node in list, remove current from list
o For each node, n that is adjacent to current
If n.distance = Infinity
n.distance = current.distance + 1
add n to the back of the list
Tracing a path to the destination
• To move towards the destination from any node simply move towards the neighbor with the smallest distance value, breaking ties arbitrarily.
• Note: Ties happens when the shortest path to the goal is not unique.
Another Example – Grassfire Algorithm
Another Example – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
Planning Procedure – Grassfire Algorithm
• In this case the procedure terminates before the start node is marked indicating that no path exists
Grassfire Algorithm
• (1) It will find the shortest path (i.e., fewest number of edges) between the start and the goal if one exists.
• (2) If no path exists that fact will be discovered.
• These two points verify that the Grassfire Algorithm is Complete, i.e. is it covers all the possible cases.
Computational Complexity – Grassfire
A question that we may want to ask about a planning procedure is how much work does it is required.
When running the Grassfire algorithm in a regular grid, every grid cell will be marked at most once during the procedure.
• The computational effort required to run the grassfire algorithm on a
grid increases linearly with the number of edges. • Thiscanbeexpressedmoreformallyasfollows.
Where |V| denotes the number of nodes in the graph
Computational Complexity – Grassfire
• Note: We can exactly use the same kind of procedure to plan path for a robot that can move in a 3 dimensions like a quadrotor. In this case the workspace of the robot could be break into 3D grid where each cell is a cube and use grassfire algorithm to plan a path between two cells in that grid.
Computational Complexity – Grassfire
• (1) Number of nodes in a 2D grid 100×100 = 104
• (2) Number of nodes in a 3D grid 100x100x100 = 106
• (3) Number of nodes in a 6D grid 100 cells on side= 1012
• Example: robot arm with 6 degree of freedom
• Compared with the scenario 1, scenario 2 requires 100 times more the effort (i.e., takes 100 times longer to run) on the same computer.
• One of the characteristic feature of motion planning problems is the exponential increase in time complexity with increase in the number of dimensions/degree of freedom.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com