Взаємозавадна швидкість

У робототехніці та плануванні руху, взаємозавадна швидкість (англ. Velocity Obstacle, зазвичай скорочено V.O) — це швидкість агента, яка призведе до зіткненні з іншим агентом в якийсь момент часу, за умови, що інший агент зберігає свою поточну швидкість^[1]. Якщо агент вибирає швидкість всередині множини взаємозавданих швидкостей, то два агенти в кінцевому підсумку стикаються, якщо він вибирає швидкість поза взаємозавадними швидкостями, таке зіткнення гарантовано не відбувається^[1]. Цей алгоритм запобігання зіткнень для агента було неодноразово пере відкрито і опубліковано під різними назвами: у 1989 році як підход бортового маневрування (англ. maneuvering-board approach)^[2], у 1993 його було вперше представлено як «взаємозавадну швидкість»^[3], у 1998 році, як зіткнення конусів^[4] і у 2009 році заборонених карт швидкості^[5]. Цей же алгоритм використовується у морській навігації з 1903 року^[6].

The velocity obstacle VO_AB for a robot A, with position x_A, induced by another robot B, with position x_B and velocity v_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}$ .

Варіації алгоритму: загальна взаємозавадна швидкість (англ. common velocity obstacles - CVO)^[7], часоконечні взаємозавадні швидкості (англ. finite-time-interval velocity obstacles - FVO)^[8], узагальнені перешкоди швидкості (англ. generalized velocity obstacles - GVO)^[9], гібридні взаємні перешкоди швидкості (англ. hybrid reciprocal velocity obstacles - HRVO)^[10], нелінійні взаємозавадні швидкості (англ. nonlinear velocity obstacles - NLVO)^[11], взаємні перешкоди швидкості (англ. reciprocal velocity obstacles - РВО)^[12] і рекурсивно імовірнісні взаємозавадні швидкості (англ. recursive probabilistic velocity obstacles - PVO)^[13].