- (206) Combinatorial methods are complete (will return a path or say one doesn’t exist, correctly)
- The exact structure of the problem is important in combinatorial methods. In particular cases, efficient algorithms are applicable.
- (207) Roadmaps provide a discrete representation of the continuous planing problem
- (208) A number of planning algorithms that work in 2D don’t generalize to higher dimensions
- (213) Many path planning algos are based on computational geometry methods, which is generally interested in sorting in multiple dimensions
- (215) Costs for many 2d algos are O(nlgn)
- (224) Algorithms that work in higher-d spaces take dimensional slices at vertices until they are back to the 2d case
- (226) In many real problems, obstacles aren’t polys but rather have smooth surfaces.
- This can be broken down into a discrete set of configurations for a position by encoding good poses in a stack
- “important aspect” of this is detecting
**critical changes**when a area in the pose goes from being blocked to unblocked, or opposite - Since the critical changes happen at an exact point, the problem becomes discrete again when using them

- (232) Skipping computational algebraic geometry because it is said implementation is very difficult & computationally expensive; the algorithms are powerful though
- (249) Planning fro robots in 3D environments with noise is NEXPTIME hard (doubly-exponential)
- (250) Davenport-Schinzel sequences are used for finding computational bounds for many problems, often uses the Ackerman function

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-729070332');
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-729070332",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-729070332'); 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-1461252733');
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-1461252733",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1461252733'); 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');
}