- (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(){var c=function(){var a=document.getElementById("crt-257664867");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-257664867",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();
(function(){var c=function(){var a=document.getElementById("crt-1508266705");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1508266705",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();