Препятствие по скорости — это набор всех скоростей робота, которые приведут к столкновению с другим роботом в некоторый момент времени при условии, что другой робот сохраняет свою текущую скорость. Если робот выберет скорость, находящуюся внутри препятствия по скорости, два робота в конечном итоге столкнутся. Если он выберет скорость вне препятствия по скорости, такое столкновение гарантированно не произойдёт.
Этот алгоритм многократно переоткрывался и публиковался под разными названиями. В 1989 году был опубликован как подход с использованием , в 1993 году впервые был представлен как «velocity obstacle» («препятствие по скорости»), в 1998 году как конус столкновений, а в 2009 году как карта запрещённых скоростей. Тот же алгоритм используется в морской портовой навигации как минимум с 1903 года.
Препятствие по скорости для робота , вызванное роботом , может быть формально записано как
где имеет положение и радиус , а имеет положение , радиус и скорость . представляет круг с центром и радиусом .
Варианты включают общие препятствия скорости, препятствия скорости конечного временного интервала, обобщённые препятствия скорости, гибридные взаимные препятствия скорости, нелинейные препятствия скорости, взаимные препятствия скорости и рекурсивные вероятностные препятствия скорости.
Примечания
Категория:Геометрические алгоритмы Категория:Кинематика роботов