Область недопустимых скоростей

Данный алгоритм избежания столкновений роботов неоднократно переоткрывался и публиковался под разными названиями:

— в 1989 году как подход с манёвровой доской^[2];

— в 1993 году впервые введён как «velocity obstacle»^[3];

— в 1998 году как кони столкновения^[4];

— в 2009 году как карты запрещённых скоростей^[5].

Аналогичный алгоритм применялся в морской навигации портов, по крайней мере, с 1903 года^[6].

В 2010-е годы фокус исследований сместился с переоткрытия базовой концепции на разработку её усовершенствованных и кооперативных версий. Новые подходы были направлены на решение недостатков оригинального метода, таких как возникновение колебаний и неоптимальных траекторий в сценариях с несколькими агентами^[7]. В этот период получили развитие такие подходы, как взаимные области недопустимых скоростей (RVO)^[8], гибридные (HRVO)^[9] и оптимальные (ORCA) версии, которые стали стандартом для решения задач навигации в многоагентных системах^[7].

Область недопустимых скоростей для робота ${\displaystyle A}$, создаваемая роботом ${\displaystyle B}$, может быть формально записана как:

${\displaystyle VO_{A|B}=\{\mathbf {v} \,|\,\exists t>0:(\mathbf {v} -\mathbf {v} _{B})t\in D(\mathbf {x} _{B}-\mathbf {x} _{A},r_{A}+r_{B})\},}$

где ${\displaystyle A}$ имеет позицию ${\displaystyle \mathbf {x} _{A}}$ и радиус ${\displaystyle r_{A}}$, ${\displaystyle B}$ — позицию ${\displaystyle \mathbf {x} _{B}}$, радиус ${\displaystyle r_{B}}$ и скорость ${\displaystyle \mathbf {v} _{B}}$. Обозначение ${\displaystyle D(\mathbf {x} ,r)}$ соответствует диску с центром в ${\displaystyle \mathbf {x} }$ и радиусом ${\displaystyle r}$.

Базовый алгоритм области недопустимых скоростей (VO) имеет ряд ограничений, таких как возникновение колебаний траектории при взаимодействии нескольких агентов и допущение о прямолинейном движении препятствий. Для их преодоления было разработано множество вариаций, которые можно сгруппировать по решаемым задачам^[10].