Computational Motion Planning
Graph-based Path Planning
A* Algorithm
slides are from different sources, e.g. C.J. Taylor (UPenn), …
Copyright By PowCoder代写 加微信 powcoder
Recap: Grassfire Algorithm
• Grassfire Algorithm is a Breadth-First-Search (BFS) algorithm and it is complete.
• It will find the shortest path (i.e., fewest number of edges) between the start and the goal if one exists.
• If no path exists that fact will be discovered.
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
shortest path: A-D-C-E
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Path Planning on Grid
Dijkstra/Grassfire Algorithm
• Both algorithms are considered to be classified as an uninformed search strategy.
• Grassfire is like a breadth-first-search algorithm.
• Dijkstra is like a uniform-cost-search algorithm.
• When applied on a grid graph where all of the edges have the same length, Dijkstra’s algorithm and the grassfire procedure have similar behaviors.
• They both explore nodes in order based on their distance from the starting node until they encounter the goal.
• Both algorithm are computationally expensive when we are dealing with larger problems (i.e., large number of nodes) resulting in performance issue.
• For many motion planning problem, we can exploit the structure of the problem to come up with a procedure that arrives at a good solution more quickly.
• A* algorithm is a widely used approach to implement such idea.
• A* Search attempts to improve upon the performance of grassfire and Dijkstra by incorporating a heuristic function that guides the path planner.
• A* is an example of a broader search algorithms
called best-first-search algorithms.
• A* is considered an informed-search strategy.
Heuristic Functions
• Heuristic functions are used to map every node in the graph to a non-negative value.
• Heuristic Function Criteria: o H(goal) = 0
o For any 2 adjacent nodes x and y
H(x) <= H(y) + d(x,y)
d(x,y) = weight/length of edge from x to y
• These properties ensure that for all nodes, n o H(n) <= length of shortest path from n to goal.
Example Heuristic Functions
• For path planning on a grid the following 2 heuristic functions are often used – Euclidean Distance
– Manhattan Distance
– where (xn, yn) denotes the coordinates of the node n and (xg, yg ) denotes the coordinate of the goal.
A* algorithm – pseudo code
• For each node n in the graph o n.f = Infinity, n.g = Infinity
• Create an empty list.
• start.g = 0, start.f = H(start) add start to list.
• While list not empty
o Let current = node in the list with the smallest f value, remove current from list
o If (current == goal node) report success
o For each node, n that is adjacent to current
If (n.g > (current.g + cost of edge from n to current)) n.g = current.g + cost of edge from n to current
n.f = n.g + H(n) n.parent = current
add n to list if it isn’t there already
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
• Red nodes indicate the nodes the algorithm visited.
• Blue nodes indicate the nodes in the list of the nodes to be considered for the algorithm to visit for the next iteration.
• In AI, this list is referred to as frontier or fringe.
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
Dijkstra/Grassfire Algorithm
A* Algorithm
A*Algorithm
A* Algorithm
A* Algorithm
A*Algorithm
(Informed Search)
Dijkstra’s Algorithm
(Uniform-Cost-Search)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com