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

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 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

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

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here:
Cookie Policy