Computational Motion Planning
Dijkstra’s 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.
Recap: Grassfire Algorithm
• Insomeproblemstheedgeshavedifferentcosts.
• Finding the shortest path requires a cost-sensitive algorithm.
• The algorithm should find the least-cost path.
• Grassfire Algorithm does not find the least-cost path.
• Uniform Cost Search algorithm finds the least-cost path. • Dijkstra’s Algorithm is a cost-sensitive search.
982f p15q4 r
Planning shortest paths – Dijkstra’s Algorithm
Wikipedia:
• Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest path between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
• In some fields, artificial intelligence in particular, Dijkstra’s algorithm or a variant of it is known as uniform cost search.
Planning shortest paths – Dijkstra’s Algorithm
Nodes: cities
Edges: roadways between cities.
Edge weight: the distance (e.g., miles) between the connected cities. Objective: find the shortest path between the start node and the goal node.
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
Red: visited node
Blue: node in the fringe list
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
Updated cost
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Updated cost
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
shortest path: A-D-C-E
Dijkstra’s algorithm – pseudo code
• For each node n in the graph o n.distance = Infinity
• Create an empty list.
• start.distance = 0, add start to list.
• While list not empty
o Let current = node in the list with the smallest distance, remove current from list
o For each node, n that is adjacent to current
If n.distance > current.distance + length of edge from n to current
n.distance = current.distance + length of edge from n to current n.parent = current
add n to list if it isn’t there already
Computational Complexity of Dijkstra’s algorithm
• The computational complexity of Dijkstra’s algorithm depends on the number of nodes and edges.
• A naive version of Dijkstra’s algorithm can be implemented with a com- putational complexity that grows quadratically with the number of nodes.
O(|V|2) (1)
• By keeping the list of nodes sorted using a clever data structure known as a priority queue the computational complexity can be reduced to something that grows more slowly
O((|E| + |V|) log(|V|)) (2)
• |V| denotes the number of nodes in the graph and |E| denotes the number of edges.
Check Wikipedia for more discussions on the complexity and pseudocodes:
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Dijkstra’s Algorithm is a uniform-cost search(USC) algorithm.
• UCS explores increasing cost contours • The good:
• UCS is complete and optimal!
• The bad:
• Explores options in every “direction” • No information about goal location
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com