Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

SAGETRACK

Sign In to gain access to subscriptions and/or personal tools.
The International Journal of Robotics Research
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Aronov, B.
Right arrow Articles by Wilfong, G.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

Minimum-Speed Motions

Boris Aronov

Courant Institute of Mathematical Sciences New York University New York, New York 10012

Steven Fortune

AT&T Bell Laboratories Murray Hill, New Jersey 07974

Gordon Wilfong

AT&T Bell Laboratories Murray Hill, New Jersey 07974

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 mini mized. Suppose the time-varying environment is fully speci fied, 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.

The International Journal of Robotics Research, Vol. 10, No. 3, 228-239 (1991)
DOI: 10.1177/027836499101000304
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?