[SOLVED] 程序代写 Computational Motion Planning

Computational Motion Planning
Graph-based Path Planning
A* Algorithm
slides are from different sources, e.g. C.J. Taylor (UPenn), …

Copyright By PowCoder代写加微信 assignmentchef

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 emptyo Let current = node in the list with the smallest f value, remove current from listo If (current == goal node) report successo For each node, n that is adjacent to currentIf (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代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]