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

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.

У робототехніці та плануванні руху, взаємозавадна швидкість (Шаблон:Lang-en, зазвичай скорочено V.O) — це швидкість агента, яка призведе до зіткненні з іншим агентом в якийсь момент часу, за умови, що інший агент зберігає свою поточну швидкість. Якщо агент вибирає швидкість всередині множини взаємозавданих швидкостей, то два агенти в кінцевому підсумку стикаються, якщо він вибирає швидкість поза взаємозавадними швидкостями, таке зіткнення гарантовано не відбувається. Цей алгоритм запобігання зіткнень для агента було неодноразово пере відкрито і опубліковано під різними назвами: у 1989 році як підход бортового маневрування (Шаблон:Lang-en), у 1993 його було вперше представлено як «взаємозавадну швидкість», у 1998 році, як зіткнення конусів і у 2009 році заборонених карт швидкості. Цей же алгоритм використовується у морській навігації з 1903 року.

Взаємозавадна швидкість для агента спровокована агентом може бути описана як:

$V{O}_{A|B}=\{𝐯|\mathrm{\exists }t>0:(𝐯-{𝐯}_B)t\in D({𝐱}_B-{𝐱}_A,r_A+r_B)\}$

де $A$ є радіус-вектором ${𝐱}_A$ з радіусом $r_A$, а $B$ — радіус-вектором ${𝐱}_B$ з радіусом $r_B$, та швидкістю ${𝐯}_B$. $D(𝐱,r)$ репрезентує круг перешкоди руху з центром $𝐱$ та радіусом $r$ .

Варіації алгоритму: загальна взаємозавадна швидкість (Шаблон:Lang-en), часоконечні взаємозавадні швидкості (Шаблон:Lang-en), узагальнені перешкоди швидкості (Шаблон:Lang-en), гібридні взаємні перешкоди швидкості (Шаблон:Lang-en), нелінійні взаємозавадні швидкості (Шаблон:Lang-en), взаємні перешкоди швидкості (Шаблон:Lang-en) і рекурсивно імовірнісні взаємозавадні швидкості (Шаблон:Lang-en).

Примітки

Шаблон:Math-stub