Minimum-speed motions

Boris Aronov, Steven Fortune, Gordon Wilfong

    Research output: Contribution to journalArticlepeer-review


    We consider the problem of determining how fast an object must be capable of moving for it to be able to reach a given position at a given time while avoiding moving obstacles. The problem is to plan velocity profile along a given path so that collisions with moving obstacles crossing the path are avoided and the maximum velocity along the path is minimized. Suppose the time-varying environment is fully specified, both in space and in time, by n linear constraints. An algorithm is presented that, given a full description of the environment and the initial configuration of the system (that is, initial position and starting time of the object), answers in O(log n) time queries of the form: 'What is the lowest speed limit that the object can obey while still being able to reach the query configuration from the initial configuration without colliding with the obstacles?' The algorithm can also be used to compute a motion from the initial configuration to the query configuration that obeys the speed limit in O(n) time. The algorithm requires O(n log n) preprocessing time and O (n) space.

    Original languageEnglish (US)
    Pages (from-to)228-239
    Number of pages12
    JournalInternational Journal of Robotics Research
    Issue number3
    StatePublished - 1991

    ASJC Scopus subject areas

    • Software
    • Modeling and Simulation
    • Mechanical Engineering
    • Artificial Intelligence
    • Electrical and Electronic Engineering
    • Applied Mathematics


    Dive into the research topics of 'Minimum-speed motions'. Together they form a unique fingerprint.

    Cite this