Препятствие скорости - Velocity obstacle

Препятствие скорости VO_AB для робота А, с положением Икс_А, вызванный другим роботом B, с положением Икс_B и скорость v_B.

В робототехника и планирование движения, а препятствие скорости, обычно сокращенно VO, это набор всех скорости из робот что приведет к столкновение с другим роботом в какой-то момент времени, предполагая, что другой робот сохраняет свою текущую скорость.^[1] Если робот выбирает скорость внутри скоростного препятствия, то два робота в конечном итоге столкнутся, если он выберет скорость вне скоростного препятствия, такого столкновения гарантированно не произойдет.^[1]

Этот алгоритм для предотвращение столкновений роботов неоднократно переоткрывался и публиковался под разными названиями: в 1989 г. маневренная доска подход,^[2] в 1993 году он был впервые представлен как «скоростное препятствие»,^[3]в 1998 году как конусы столкновения,^[4] а в 2009 г. - как запрещенные карты скоростей.^[5]Тот же алгоритм использовался в навигации в морских портах по крайней мере с 1903 года.^[6]

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

${displaystyle VO_{A|B}={mathbf {v} ,|,exists t>0:(mathbf {v} -mathbf {v} _{B})tin 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}$.

Варианты включают общие скоростные препятствия (CVO),^[7] препятствия с конечным интервалом времени (FVO),^[8] обобщенный скоростные препятствия (ГВО),^[9] гибридный препятствия с обратной скоростью (HRVO),^[10] нелинейный скоростные препятствия (NLVO),^[11] обратная скорость препятствий (RVO),^[12] и рекурсивный вероятностный скоростные препятствия (ПВО).^[13]

Рекомендации

1. Fiorini, P .; Шиллер, З. (июль 1998 г.). «Планирование движения в динамических средах с использованием скоростных препятствий». Международный журнал исследований робототехники. 17 (7): 760–772. CiteSeerX  10.1.1.56.6352. Дои:10.1177/027836499801700706. ISSN  0278-3649.
2. Тихониевич, Л. П .; Zaret, D .; Mantegna, R .; Evans, R .; Muehle, E .; Мартин, С. (1989). Подход на маневренной доске к планированию пути с движущимися препятствиями. Международная совместная конференция по искусственному интеллекту (IJCAI). С. 1017–1021.
3. Fiorini, P .; Шиллер, З. (1993). Планирование движения в динамических средах с использованием парадигмы относительной скорости. Конференция IEEE по робототехнике и автоматизации. С. 560–565.
4. Chakravarthy, A .; Гхош, Д. (сентябрь 1998 г.). «Избегание препятствий в динамической среде: подход конуса столкновения». Транзакции IEEE по системам, человеку и кибернетике - Часть A: Системы и люди. 28 (5): 562–574. CiteSeerX  10.1.1.101.2050. Дои:10.1109/3468.709600.
5. Damas, B .; Сантос-Виктор, Дж. (2009). Избегайте движущихся препятствий: карта запрещенных скоростей. Международная конференция IEEE / RSJ по интеллектуальным роботам и системам (IROS). С. 4393–4398.
6. Миллер, Ф. С .; Эверетт, А. Ф. (1903). Инструкции по использованию доски для швартовки Мартина и индикатора курса Баттенберга. Полномочия лордов комиссаров Адмиралтейства.
7. Abe, Y .; Йошики, М. (ноябрь 2001 г.). Метод предотвращения столкновений для нескольких автономных мобильных агентов за счет неявного взаимодействия. Международная конференция IEEE / RSJ по интеллектуальным роботам и системам (IROS 01). Нью-Йорк, штат Нью-Йорк.: IEEE. С. 1207–1212. Дои:10.1109 / IROS.2001.977147.
8. Guy, S.J .; Chhugani, J .; Kim, C .; Satish, N .; Lin, M .; Manocha, D .; Дубей П. (август 2009 г.). ClearPath: высокопараллельное предотвращение столкновений для многоагентного моделирования. ACM SIGGRAPH / Симпозиум Eurographics по компьютерной анимации (SCA 09). Нью-Йорк, штат Нью-Йорк.: ACM. С. 177–187. Дои:10.1145/1599470.1599494.
9. Wilkie, D .; v.d. Berg, J .; Маноча, Д. (октябрь 2009 г.). Обобщенные скоростные препятствия. Международная конференция IEEE / RSJ по интеллектуальным роботам и системам (IROS 09). Нью-Йорк, штат Нью-Йорк.: IEEE. Дои:10.1109 / IROS.2009.5354175.
10. Снейп, Дж .; v.d. Berg, J .; Guy, S.J .; Маноча, Д. (октябрь 2009 г.). Независимая навигация нескольких мобильных роботов с гибридными препятствиями с обратной скоростью. Международная конференция IEEE / RSJ по интеллектуальным роботам и системам (IROS 09). Нью-Йорк, штат Нью-Йорк.: IEEE.
11. Большой, F .; Сехават, С .; Шиллер, З .; Ложье, К. (декабрь 2002 г.). Использование препятствий с нелинейной скоростью для планирования движений в динамической среде. Международная конференция IEEE по управлению, автоматизации, робототехнике и зрению (ICARCV 02). Нью-Йорк, штат Нью-Йорк.: IEEE. С. 734–739. Дои:10.1109 / ICARCV.2002.1238513.
12. v.d. Берг, Дж.; Lin, M .; Маноча, Д. (май 2008 г.). Препятствия с взаимной скоростью для многоагентной навигации в реальном времени. Международная конференция IEEE по робототехнике и автоматизации (ICRA 08). Нью-Йорк, штат Нью-Йорк.: IEEE. С. 1928–1935. CiteSeerX  10.1.1.127.6140. Дои:10.1109 / ROBOT.2008.4543489.
13. Fulgenzi, C .; Spalanzani, A .; Ложье, К. (апрель 2007 г.). Динамическое избегание препятствий в неопределенной среде, сочетающее PVO и сетку занятости. Международная конференция IEEE по робототехнике и автоматизации (ICRA 07). Нью-Йорк, штат Нью-Йорк.: IEEE. С. 1610–1616. Дои:10.1109 / ROBOT.2007.363554.