From Coursera, State Estimation and Localization for Self-Driving Cars by University of Toronto
- The edges is defined by the segments of the road that connect each sample point according to the rules of the road.
- the edges of the graph are directed
- When the graph is unweighted, a good candidate algorithm is the Breadth-First Search or BFS.
- At a high level, BFS can be thought of as iterating through all of the vertices in the graph but doing so in a manner such that all adjacent vertices are evaluated first before proceeding deeper into the graph.
Algorithm Dijkstra's (G,s,t)
- a search heuristic is an estimate of the remaining cost to reach the destination vertex from any given vertex in the graph.
- in this case, a useful estimate on the cost or length between any two vertices is the straight line or Euclidean distance between them
- Exploits structure of the problem
- Fast to calculate
- Straight-line distance between two vertices is a useful estimate of true distance along the graph
$$h(v) = |t-v|$$
Extensions to Other Factors
- Traffic, speed limits, and weather affect mission planning
- Time rather than distance is better at capturing these factors
- Replace distance edge weights with time estimates