Models and motion planning

M. Berg, de, M.J. Katz, M.H. Overmars, A.F. van der Stappen, J.M. Vleugels

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (Scopus)

    Abstract

    We study the complexity of the motion planning problem for a bounded-reach robot in the situation where the n obstacles in its workspace satisfy two of the realistic models proposed in the literature, namely unclutteredness and small simple-cover complexity. We show that the maximum complexity of the free space of a robot with f degrees of freedom in the plane is T(nf/2+n) for uncluttered environments as well as environments with small simple-cover complexity. The maximum complexity of the free space of a robot moving in a three-dimensional uncluttered environment is T(n2f/3+n). All these bounds fit nicely between the T(n) bound for the maximum free-space complexity for low-density environments and the T(nf) bound for unrestricted environments. Surprisingly—because contrary to the situation in the plane—the maximum free-space complexity is T(nf) for a three-dimensional environment with small simple-cover complexity.
    Original languageEnglish
    Pages (from-to)53-68
    JournalComputational Geometry
    Volume23
    Issue number1
    DOIs
    Publication statusPublished - 2002

    Fingerprint Dive into the research topics of 'Models and motion planning'. Together they form a unique fingerprint.

  • Cite this

    Berg, de, M., Katz, M. J., Overmars, M. H., van der Stappen, A. F., & Vleugels, J. M. (2002). Models and motion planning. Computational Geometry, 23(1), 53-68. https://doi.org/10.1016/S0925-7721(01)00022-0