Sparse Roadmap Spanners. Dobson, Krontiris, Bekris. Workshop on the Algorithmic Foundations of Robotics (WAFR) 2012


  1. PRMs approach optimality at the limit, but of course this is not actually practical in terms of time or memory requirements
  2. If optimality is relaxed, near-optimal roadmaps can be made that are much more sparse
  3. The approach here asymptotically:
    1. Is complete
    2. Near optimal
    3. Probability of adding nodes converges to zero as time passes
  4. The implication is that finite size data structures can plan near optimally
  5. Empirical results back these claims up
  6. RRT isn’t focused on here, even though it can plan in dynamic domains because the goal is on preprocessing with PRMs
  7. fixed k-PRM, where each point is connected to a fixed k number of nearest points isn’t optimal, but if kis 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
    1. 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
  8. 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
    1. In practice the graphs tend to be much smaller but don’t sacrifice much in terms of optimality
  9. This paper introduces ther SPArse Roadmap Spanner algorithm.  It has the properties:
    1. Of being probabalistically complete
    2. 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
    3. Converges to a finite size roadmap
  10. 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?
  11. The approach has a natural stopping criteria (not sure what it is yet though)
  12. The alg builds 2 graphs in parallel, one sparse and one dense
    1. there are limits on edge lengths – the sparse graph has longer edges
  13. Uses visibility based navigation through the sparse graphs with guard and bridge nodes
  14. This method has a tiny fraction of the number of nodes delta-prm makes, and the path quality is very close
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: