- 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

Advertisements
(function(g,$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);
var o = document.getElementById('crt-220550534');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-220550534",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-220550534'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}
var o = document.getElementById('crt-1398820565');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1398820565",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1398820565'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}