- PRMs approach optimality at the limit, but of course this is not actually practical in terms of time or memory requirements
- If optimality is relaxed, near-optimal roadmaps can be made that are much more sparse
- The approach here asymptotically:
- Is complete
- Near optimal
- Probability of adding nodes converges to zero as time passes

- The implication is that finite size data structures can plan near optimally
- Empirical results back these claims up
- RRT isn’t focused on here, even though it can plan in dynamic domains because the goal is on preprocessing with PRMs
- fixed
*k*-PRM, where each point is connected to a fixed*k*number of nearest points isn’t optimal, but if*k*is scaled logarithmically with the number of nodes, it is. Delta-PRM, which connects all points in a delta-ball is asymptotically optimal, I suppose because the number of points in the ball increases as the number of samples increases- These methods just keep adding nodes and vertices at each iteration, and there is no way to know when to stop, so the graph simply grows and grows

- The algorithm sequential roadmap spanner produces smaller maps by utilizing graph spanners that are subgraphs that have a node-to-node traversal cost that is allowed to be within some multiplicative factor of the cost in the full graph – therefore the graph remains small but the suboptimality of it is bounded
- In practice the graphs tend to be much smaller but don’t sacrifice much in terms of optimality

- This paper introduces ther SPArse Roadmap Spanner algorithm. It has the properties:
- Of being probabalistically complete
- Can connect any 2 pts of length tc*+4delta. t and delta are parameters to the algorithm, c* is the cost of the optimum path between query points in Cfree
- Converges to a finite size roadmap

- It is said to the best of their knowledge that this is the first approach that is near optimal and produces compact results – I wonder how Brafman’s paper from ICAPs compares?
- The approach has a natural stopping criteria (not sure what it is yet though)
- The alg builds 2 graphs in parallel, one sparse and one dense
- there are limits on edge lengths – the sparse graph has longer edges

- Uses visibility based navigation through the sparse graphs with guard and bridge nodes
- This method has a tiny fraction of the number of nodes delta-prm makes, and the path quality is very close