[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 Assignmentchef 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 Dijkstras 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, Dijkstras 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 isnt 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)
Dijkstras Algorithm
(Uniform-Cost-Search)

CS: assignmentchef QQ: 1823890830 Email: [email protected]