Motion planning in environments with low obstacle density

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

    Research output: Contribution to journalArticleAcademicpeer-review

    29 Citations (Scopus)


    We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density.
    Original languageEnglish
    Pages (from-to)561-587
    Number of pages27
    JournalDiscrete and Computational Geometry
    Issue number4
    Publication statusPublished - 1998


    Dive into the research topics of 'Motion planning in environments with low obstacle density'. Together they form a unique fingerprint.

    Cite this