Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T23:53:57.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient, incremental coverage of space with a continuous curve

Published online by Cambridge University Press:  01 July 2008

Subramanian Ramamoorthy ,
Ram Rajagopal  and
Lothar Wenzel
Subramanian Ramamoorthy*
Affiliation:
School of Informatics, The University of Edinburgh, Scotland, UK.
Ram Rajagopal
Affiliation:
Department of Electrical Engineering and Computer Sciences, The University of California at Berkeley, Berkeley, CA, USA.
Lothar Wenzel
Affiliation:
Mathematics and Signal Processing Group, National Instruments Corp., Austin, TX, USA.
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

This paper is concerned with algorithmic techniques for the incremental generation of continuous curves that can efficiently cover an abstract surface. We introduce the notion of low-discrepancy curves as an extension of the notion of low-discrepancy sequences—such that sufficiently smooth curves with low-discrepancy properties can be defined and generated. We then devise a procedure for lifting these curves, that efficiently cover the unit cube, to abstract surfaces, such as nonlinear manifolds. We present algorithms that yield suitable fair mappings between the unit cube and the abstract surface. We demonstrate the application of these ideas using some concrete examples of interest in robotics.

Keywords

space coveragelow-discrepancy curvenonlinear manifold
Type
Article
Information
Robotica , Volume 26 , Special Issue 4: Geometry in Robotics: Sensing , July 2008 , pp. 503 - 512
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Zaslavsky, G. M., Hamiltonian Chaos and Fractional Dynamics (Oxford University Press, Oxford, 2005).Google Scholar
2.Matousek, J., Geometric Discrepancy: An Illustrated Guide (Springer, Berlin, 1999).Google Scholar
3.Chazelle, B., The Discrepancy Method (Cambridge University Press, Cambridge, 2000).CrossRefGoogle Scholar
4.La Valle, S. M., Branicky, M. S. and Lindemann, S. R., “On the relationship between classical grid search and probabilistic roadmaps,” International Journal of Robotics Research 23 (7–8), 673–692 (2004).Google Scholar
5.Lindemann, S. R. and La Valle, S. M., “Incremental low-discrepancy lattice methods for motion planning,” Proceedings of the IEEE International Conference on Robotics and Automation (2003) pp. 2920–2927.Google Scholar
6.Lindemann, S. R., Yershova, A. and La Valle, S. M., “Incremental grid sampling strategies in robotics”. In: Algorithmic Foundations of Robotics VI, Erdman, M., Hsu, D., Overmars, M. H., and Stappen, van der A. F., (eds.), (Springer-Verlag, Berlin, 2005) pp. 297–312.Google Scholar
7.Rimon, E. and Koditschek, D. E., “Exact robot navigation using artifical potential functions,” IEEE Trans. Robot. and Autom. 8 (5), 501–518 (1992).Google Scholar
8.Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conference Series in Applied Mathematics, No. 63 (SIAM, Philadelphia, PA, 1992).CrossRefGoogle Scholar
9.Kocis, L. and Whiten, W. J., “Computational investigations of low-discrepancy sequences,” ACM Trans. Math. Software, 23 (2), 266–294 (1997).CrossRefGoogle Scholar
10.Corput, J. G. van der, “Vereilungsfunktionen 1,11,” Nederl. Akad. Wetensch. Proc. Ser. B 38, 813–821, 1058–1066 (1935).Google Scholar
11.Halton, J. H., “On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,” Numer. Math. 2, 84–90 (1960).Google Scholar
12.Sobol, I. M.', “The distribution of points in a cube and the approximate evaluation of integrals,” Zh. Vychisl. Mat. i Mat. Fiz. USSR Comput. Math. Math. Phys. 7, 784–802 (1967). (in Russian)Google Scholar
13.Richtmyer, R. D., “The evaluation of definite integrals, and quasi-Monte Carlo method based on the properties of algebraic numbers,” Rep. LA-1342, Los Alamos Scientific Laboratory, Los Alamos, NM, 1951.Google Scholar
14.Richtmyer, R. D., “A Non-random Sampling Method, Based on Congruences for Monte Carlo Problems,” Rep. NYO-8674. Institute of Mathematical Sciences, New York University, New York, 1958).Google Scholar
15.Hammersly, J. M. and Handscomb, D. C., Monte Carlo Methods (Methuen and Company, London, 1964).Google Scholar
16.Morokoff, W. and Caflisch, R. E., “Quasi-random sequences and their discrepancies,” SIAM J. Sci. Stat. Comp. 15, 1251–1279 (1994).Google Scholar
17.James, F., Hoogland, J. and Kleiss, R., “Multidimensional sampling for simulation and integration: Measures, discrepancies, and quasi-random numbers,” Comput. Phys. Comm. 99 180–220 (1997).Google Scholar
18.Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers, 5th ed. (Oxford University Press, Oxford, 1980).Google Scholar
19.Gray, A., Modern Differential Geometry Of Curves And Surfaces With Mathematica (CRC Press, Bocaraton, FL, 1998).Google Scholar
20.Mc Cleary, J., Geometry from a Differentiable Viewpoint (Cambridge University Press, Cambridge, 1995).CrossRefGoogle Scholar
21.Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P., Numerical Recipes in C: The Art of Scientific Computing. 2nd ed. (Cambridge University Press, Cambridge, 1992).Google Scholar
22.Ramamoorthy, S., Kuipers, B. J. and Wenzel, L., “Parametrization and computations in shape spaces with area and boundary invariants,” Proceedings of the 16th Fall Workshop on Computational and Combinatorial Geometry, Northampton, (Nov. 10–11, 2006).Google Scholar
23.Zwillinger, D., Handbook of Differential Equations, 3rd ed., Academic Press, Boston, 1997.Google Scholar