×

Smoothed analysis of probabilistic roadmaps. (English) Zbl 1169.65052

The probabilistic roadmap algorithm that revolutionized robot planning is a simple heuristic that exhibits rapid performance with unbounded worst-case running time as a function of the input’s combinatorial complexity. This paper initiates the use of smoothed analysis to explain the success of the probabilistic roadmap algorithm. A locally orthogonal decomposition is defined. The authors prove that for the roadmap to accurately represent the free configuration space it is sufficient that a milestone is sampled from every cell of this decomposition. A smoothed lower bound on the volume of every decomposition cell is proved, and a smoothed polynomial upper bound on the required number of milestones is established.

MSC:

65K05 Numerical mathematical programming methods
90C59 Approximation methods and heuristics in mathematical programming
90C15 Stochastic programming
62P30 Applications of statistics in engineering and industry; control charts
65Y20 Complexity and performance of numerical algorithms

Software:

k-means++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P. K.; Katz, M. J.; Sharir, M., Computing depth orders for fat objects and related problems, Computational Geometry Theory and Applications, 5, 187-206 (1995) · Zbl 0851.68102
[2] Aronov, B.; Sharir, M., Castles in the air revisited, Discrete and Computational Geometry, 12, 119-150 (1994) · Zbl 0805.52005
[3] D. Arthur, S. Vassilvitskii, Worst-case and smoothed analyses of the ICP algorithm, with an application to the k-means method, in: Proc. 47th IEEE Symposium on Foundations of Computer Science, 2006; D. Arthur, S. Vassilvitskii, Worst-case and smoothed analyses of the ICP algorithm, with an application to the k-means method, in: Proc. 47th IEEE Symposium on Foundations of Computer Science, 2006 · Zbl 1202.68496
[4] C. Banderier, R. Beier, K. Mehlhorn, Smoothed analysis of three combinatorial problems, in: Proc. 28th Symposium on Mathematical Foundations of Computer Science, 2003, pp. 198-207; C. Banderier, R. Beier, K. Mehlhorn, Smoothed analysis of three combinatorial problems, in: Proc. 28th Symposium on Mathematical Foundations of Computer Science, 2003, pp. 198-207 · Zbl 1124.68371
[5] Barraquand, J.; Kavraki, L. E.; Latombe, J.-C.; Li, T.-Y.; Motwani, R.; Raghavan, P., A random sampling scheme for path planning, International Journal of Robotics Research, 16, 759-774 (1997)
[6] Berretty, R.-P.; Overmars, M.; van der Stappen, A. F., Dynamic motion planning in low obstacle density environments, (Proc. Workshop Algorithms Data Struct.. Proc. Workshop Algorithms Data Struct., Lecture Notes in Computer Science, vol. 1272 (1997), Springer-Verlag), 3-16 · Zbl 1517.68392
[7] A. Blum, J. Dunagan, Smoothed analysis of the perceptron algorithm for linear programming, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 905-914; A. Blum, J. Dunagan, Smoothed analysis of the perceptron algorithm for linear programming, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 905-914 · Zbl 1058.65062
[8] D.E. Cardoze, L.J. Schulman, Pattern matching for spatial point sets, in: Proc. 39th IEEE Symposium on Foundations of Computer Science, 1998, pp. 156-165; D.E. Cardoze, L.J. Schulman, Pattern matching for spatial point sets, in: Proc. 39th IEEE Symposium on Foundations of Computer Science, 1998, pp. 156-165
[9] Chazelle, B.; Edelsbrunner, H.; Guibas, L. J.; Sharir, M., A singly-exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, 84, 77-105 (1991) · Zbl 0757.14031
[10] Clarkson, K. L., Nearest neighbor queries in metric spaces, Discrete and Computational Geometry, 22, 63-93 (1999) · Zbl 0994.54501
[11] V. Damerow, F.M. auf der Heide, H. Räcke, C. Scheideler, C. Sohler, Smoothed motion complexity, in: Proc. 11th European Symposium on Algorithms, 2003, pp. 161-171; V. Damerow, F.M. auf der Heide, H. Räcke, C. Scheideler, C. Sohler, Smoothed motion complexity, in: Proc. 11th European Symposium on Algorithms, 2003, pp. 161-171 · Zbl 1266.68095
[12] V. Damerow, C. Sohler, Extreme points under random noise, in: Proc. 12th European Symposium on Algorithms, 2004, pp. 264-274; V. Damerow, C. Sohler, Extreme points under random noise, in: Proc. 12th European Symposium on Algorithms, 2004, pp. 264-274 · Zbl 1111.68722
[13] de Berg, M., Linear size binary space partitions for fat objects, (Proc. 3rd Annu. European Sympos. Algorithms. Proc. 3rd Annu. European Sympos. Algorithms, Lecture Notes in Computer Science, vol. 979 (1995), Springer-Verlag), 252-263 · Zbl 1512.68410
[14] de Berg, M., Linear size binary space partitions for uncluttered scenes, Algorithmica, 28, 353-366 (2000) · Zbl 0960.68160
[15] de Berg, M.; Halperin, D.; Overmars, M.; van Kreveld, M., Sparse arrangements and the number of views of polyhedral scenes, International Journal of Computational Geometry and Applications, 7, 175-195 (1997)
[16] M. de Berg, M.J. Katz, A.F. van der Stappen, J. Vleugels, Realistic input models for geometric algorithms, in: Proc. 13th Symposium on Computational Geometry, 1997, pp. 294-303; M. de Berg, M.J. Katz, A.F. van der Stappen, J. Vleugels, Realistic input models for geometric algorithms, in: Proc. 13th Symposium on Computational Geometry, 1997, pp. 294-303 · Zbl 1017.68141
[17] A. Deshpande, D.A. Spielman, Improved smoothed analysis of the shadow vertex simplex method, in: Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 349-356; A. Deshpande, D.A. Spielman, Improved smoothed analysis of the shadow vertex simplex method, in: Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 349-356
[18] Erickson, J., Nice point sets can have nasty Delaunay triangulations, Discrete and Computational Geometry, 30, 109-132 (2003) · Zbl 1038.68129
[19] M. Gavrilov, P. Indyk, R. Motwani, S. Venkatasubramanian, Geometric pattern matching: A performance study, in: Proc. 15th Symposium on Computational Geometry, 1999, pp. 79-85; M. Gavrilov, P. Indyk, R. Motwani, S. Venkatasubramanian, Geometric pattern matching: A performance study, in: Proc. 15th Symposium on Computational Geometry, 1999, pp. 79-85
[20] R. Geraerts, M. Overmars, A comparative study of probabilistic roadmap planners, in: Proc. 5th Workshop on the Algorithmic Foundations of Robotics, 2002, pp. 43-59; R. Geraerts, M. Overmars, A comparative study of probabilistic roadmap planners, in: Proc. 5th Workshop on the Algorithmic Foundations of Robotics, 2002, pp. 43-59
[21] Hsu, D.; Latombe, J.-C.; Kurniawati, H., On the probabilistic foundations of probabilistic roadmap planning, International Journal of Robotics Research, 25, 7, 627-643 (2006)
[22] Hsu, D.; Latombe, J.-C.; Motwani, R., Path planning in expansive configuration spaces, International Journal of Computational Geometry and Applications, 9, 495-512 (1999)
[23] Hsu, D.; Latombe, J.-C.; Motwani, R.; Kavraki, L. E., Capturing the connectivity of high-dimensional geometric spaces by parallelizable random sampling techniques, (Pardalos, P.; Rajasekaran, S., Advances in Randomized Parallel Computing (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), 159-182 · Zbl 0943.68155
[24] Kavraki, L. E.; Kolountzakis, M. N.; Latombe, J.-C., Analysis of probabilistic roadmaps for path planning, IEEE Transactions on Robotics and Automation, 14, 166-171 (1998)
[25] Kavraki, L. E.; Latombe, J.-C., Probabilistic roadmaps for robot path planning, (Gupta, K.; del Pobil, A., Practical Motion Planning in Robotics: Current Approaches and Future Directions (1998), John Wiley), 33-53
[26] L.E. Kavraki, J.-C. Latombe, R. Motwani, P. Raghavan, Randomized query processing in robot path planning, in: Proc. 27th ACM Symposium on Theory of Computing, 1995, pp. 353-362; L.E. Kavraki, J.-C. Latombe, R. Motwani, P. Raghavan, Randomized query processing in robot path planning, in: Proc. 27th ACM Symposium on Theory of Computing, 1995, pp. 353-362 · Zbl 0925.93671
[27] Kavraki, L. E.; Svestka, P.; Latombe, J.-C.; Overmars, M. H., Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation, 11, 566-580 (1996)
[28] Koltun, V., Almost tight upper bounds for vertical decompositions in four dimensions, Journal of the ACM, 51, 699-730 (2004) · Zbl 1204.68244
[29] Latombe, J.-C., Robot Motion Planning (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Boston
[30] M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S.E. Anderson, J. Davis, J. Ginsberg, J. Shade, D. Fulk, The digital Michelangelo project: 3D scanning of large statues, in: SIGGRAPH, 2000, pp. 131-144; M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S.E. Anderson, J. Davis, J. Ginsberg, J. Shade, D. Fulk, The digital Michelangelo project: 3D scanning of large statues, in: SIGGRAPH, 2000, pp. 131-144
[31] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press New York, NY · Zbl 0849.68039
[32] Overmars, M. H.; van der Stappen, A. F., Range searching and point location among fat objects, Journal of Algorithms, 21, 629-656 (1996) · Zbl 0864.68020
[33] Pisier, G., The Volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Mathematics, vol. 94 (1989), Cambridge University Press · Zbl 0698.46008
[34] Schwarzkopf, O.; Vleugels, J., Range searching in low-density environments, Information Processing Letters, 60, 121-127 (1996) · Zbl 0875.68204
[35] Sharir, M., Algorithmic motion planning, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press LLC: CRC Press LLC Boca Raton, FL), 733-754, (Chapter 40) · Zbl 0925.93625
[36] G. Song, S.L. Thomas, N.M. Amato, A general framework for PRM motion planning, in: Proc. International Conference on Robotics and Automation, 2003, pp. 4445-4450; G. Song, S.L. Thomas, N.M. Amato, A general framework for PRM motion planning, in: Proc. International Conference on Robotics and Automation, 2003, pp. 4445-4450
[37] D.A. Spielman, S.-H. Teng, Smoothed analysis of algorithms, in: Proc. of the International Congress of Mathematicians 2002; D.A. Spielman, S.-H. Teng, Smoothed analysis of algorithms, in: Proc. of the International Congress of Mathematicians 2002 · Zbl 1056.65148
[38] Spielman, D. A.; Teng, S.-H., Smoothed analysis of termination of linear programming algorithms, Mathematical Programming, Series B, 97 (2003) · Zbl 1035.90042
[39] Spielman, D. A.; Teng, S.-H., Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM, 51, 385-463 (2004) · Zbl 1192.90120
[40] A.F. van der Stappen, M.H. Overmars, Motion planning amidst fat obstacles, in: Proc. 10th Symposium on Computational Geometry, 1994, pp. 31-40; A.F. van der Stappen, M.H. Overmars, Motion planning amidst fat obstacles, in: Proc. 10th Symposium on Computational Geometry, 1994, pp. 31-40
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.