Reaching a goal with directional uncertainty

M. Berg, de, L.J. Guibas, D. Halperin, M.H. Overmars, O. Schwarzkopf, M. Sharir, M. Teillaud

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    4 Citaten (Scopus)


    We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle a centered around the specified direction. First, we consider a single goal region, namely the "region at infinity", and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of a. We prove that the maximum complexity of is O(n/a5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of a. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.
    Originele taal-2Engels
    Pagina's (van-tot)301-317
    Aantal pagina's17
    TijdschriftTheoretical Computer Science
    Nummer van het tijdschrift2
    StatusGepubliceerd - 1995


    Duik in de onderzoeksthema's van 'Reaching a goal with directional uncertainty'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit