Планирование пути в реальном времени - Real-time path planning

Планирование пути в реальном времени это термин, используемый в робототехника который состоит из планирование движения методы, которые могут адаптироваться к изменениям окружающей среды в реальном времени. Сюда входит все от примитивных алгоритмы которые останавливают робота, когда он приближается к препятствию к более сложному алгоритмы который постоянно получает информацию из окружающей среды и создает план, позволяющий избегать препятствий.[1]

Эти методы отличаются от чего-то вроде Roomba Робот-пылесос, такой как Roomba, может адаптироваться к динамическим препятствиям, но у него нет установленной цели. Лучшим примером будет Встать самоуправляемые полуприцепы, которые имеют заданное целевое местоположение и могут адаптироваться к меняющимся условиям.

Цели алгоритмов планирования пути не ограничиваются только местоположениями. Методы планирования пути также могут создавать планы для стационарных роботов, чтобы они могли менять свои позы. Пример этого можно увидеть в различных роботизированных манипуляторах, где планирование пути позволяет роботизированной системе изменять свою позу, не сталкиваясь с самой собой.[2]

Как часть планирования движения, это важная часть робототехника поскольку это позволяет роботам находить оптимальный путь к цели. Эта способность найти оптимальный путь также играет важную роль в других областях, таких как видеоигры и секвенирование генов.

Концепции

Чтобы проложить путь от целевой точки к целевой точке, должны быть классификации по различным областям в пределах смоделированный среда. Это позволяет создавать путь в 2D или 3D пространстве, где робот может избегать препятствий.

Рабочая среда

Рабочее пространство - это среда, в которой есть робот и различные препятствия. Эта среда может быть двухмерной или трехмерной.[3]

Пространство конфигурации

Конфигурация робота определяется его текущим положением и позой. В конфигурационное пространство это набор всех конфигураций робота. Содержая все возможные конфигурации робота, он также представляет все преобразования, которые могут быть применены к роботу.[3]

В наборах конфигураций есть дополнительные наборы конфигураций, которые классифицируются по различным алгоритмам.

Свободное место

Свободное пространство - это набор всех конфигураций внутри конфигурационного пространства, не сталкивающегося с препятствиями.[4]

Целевое пространство

Целевое пространство - это конфигурация, которую мы хотим, чтобы робот выполнял.

Пространство препятствий

Пространство препятствий - это набор конфигураций в пространстве конфигурации, куда робот не может переместиться.

Опасное пространство

Опасное пространство - это набор конфигураций, в которых робот может двигаться, но не хочет. Часто роботы пытаются избежать этих конфигураций, если у них нет другого действительного пути или если у них нет ограничений по времени. Например, робот не захотел бы двигаться через огонь, если не было других допустимых путей к целевой области.[4]

Методы

Глобальный

Планирование глобального пути относится к методам, требующим предварительного знания окружающей среды робота. Используя эти знания, он создает смоделированный среда, в которой методы могут планировать путь.[1][5]

Быстрое изучение случайного дерева (RRT)

В быстрое изучение случайного дерева метод работает, пропуская все возможные переводы из конкретной конфигурации. Путем выполнения всех возможных серий переводов создается путь, по которому робот может достичь цели из начальной конфигурации.[6]

Местный

Планирование локального пути относится к методам, которые получают информацию из окружения для создания смоделированный поле, в котором можно найти путь. Это позволяет находить путь в реальном времени, а также адаптироваться к динамическим препятствиям.[1][5]

Вероятностная дорожная карта (PRM)

В вероятностная дорожная карта соединяет соседние конфигурации, чтобы определить путь от начальной до целевой. Метод разделен на две разные части: предварительная обработка фаза и запрос фаза. На этапе предварительной обработки алгоритмы оценивают различные движения, чтобы определить, находятся ли они в свободном пространстве. Затем на этапе запроса алгоритмы соединяют начальную и целевую конфигурации различными путями. После создания путей он использует Кратчайший путь Дейкстры запрос, чтобы найти оптимальный путь.[7][8]

Эволюционное искусственное потенциальное поле (EAPF)

В эволюционном методе искусственного потенциального поля используется сочетание искусственный отталкивающий и привлекательный силы чтобы спланировать путь для робота. Силы притяжения исходят от цели, которая в конечном итоге ведет к цели. Силы отталкивания исходят от различных препятствий, с которыми робот сталкивается. Используя это сочетание сил притяжения и отталкивания, алгоритмы могут найти оптимальный путь.[9]

Ориентировочный метод маршрута (IRM)

Метод ориентировочного маршрута использует контрольный путь к цели и точку притяжения, расположенную у цели. Алгоритмы часто используются для поиска пути управления, который часто является путем с кратчайшим путем с минимальным зазором. Когда робот остается на пути управления, точка притяжения в целевой конфигурации ведет робота к цели.[10]

Модифицированные ориентировочные маршруты и навигация (МИРАН)

Измененные ориентировочные маршруты и метод навигации придают различные веса различным путям, которые робот может пройти из своего текущего положения. Например, камню будет присвоен высокий вес, такой как 50, в то время как открытый путь будет иметь меньший вес, например 2. Это создает множество областей с весом в окружающей среде, что позволяет роботу выбирать путь к цели.[11]

Приложения

Гуманоидные роботы

Для многих роботов количество степени свободы не больше трех. Гуманоидные роботы с другой стороны, они имеют такое же количество степеней свободы, что и человеческое тело, что увеличивает сложность планирования пути. Например, одна нога гуманоидного робота может иметь около 12 степеней свободы. Повышенная сложность возникает из-за большей вероятности столкновения робота с самим собой. Планирование пути в реальном времени важно для движения роботов-гуманоидов, поскольку оно позволяет различным частям робота двигаться одновременно, избегая столкновений с другими частями робота.[12]

Например, если мы посмотрим на свои руки, мы увидим, что наши руки могут касаться наших плеч. Для роботизированной руки это может представлять опасность, если части рук непреднамеренно столкнутся друг с другом. Вот почему необходимы алгоритмы планирования пути, чтобы предотвратить эти случайные столкновения.

Самоходные автомобили

Беспилотные автомобили представляют собой форму мобильных роботов, которые используют планирование пути в реальном времени. Часто автомобиль сначала использует глобальное планирование пути, чтобы решить, какие дороги выбрать к цели. Когда эти автомобили находятся в дороге, они должны постоянно адаптироваться к меняющимся условиям. Именно здесь методы планирования локального пути позволяют автомобилю планировать безопасный и быстрый путь к целевому местоположению.[13]

Примером этого может быть Встать самоуправляемые полуприцепы, которые используют множество датчиков для сбора информации об окружающей среде. Грузовик будет иметь заранее определенное целевое местоположение и будет использовать глобальное планирование пути, чтобы проложить путь к цели. Пока грузовик находится в пути, он будет использовать свои датчики вместе с местными методами планирования пути для обхода препятствий и безопасного достижения целевого местоположения.[14]

Видеоигры

Часто в видеоиграх есть множество неигровые персонажи которые перемещаются по игре, что требует планирования пути. Для этих персонажей должны быть спланированы пути, так как они должны знать, куда двигаться и как туда двигаться.

Например, в игре Шахтерское ремесло есть враждебные мобы, которые отслеживают и преследуют игрока, чтобы убить игрока. Это требует планирования пути в реальном времени, поскольку моб должен избегать различных препятствий, следуя за игроком. Даже если игрок добавит дополнительные препятствия на пути моба, моб изменит свой путь, чтобы по-прежнему достигать игрока.

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

  1. ^ а б c Хуэй-Чжун Чжуан; Шу-Синь Ду; Ти-Цзюнь Ву (2005). «Планирование пути для мобильных роботов в реальном времени». 2005 Международная конференция по машинному обучению и кибернетике. IEEE: 526–531. Дои:10.1109 / icmlc.2005.1527001. ISBN  0780390911.
  2. ^ Джексон, Рассел С .; Чавушоглу, М. Дженк (31 декабря 2013 г.). «Планирование пути иглы для автономного роботизированного хирургического наложения швов». Международная конференция IEEE по робототехнике и автоматизации: ICRA: [сборник материалов] Международная конференция IEEE по робототехнике и автоматизации. 2013: 1669–1675. Дои:10.1109 / ICRA.2013.6630794. ISBN  978-1-4673-5643-5. ISSN  2152-4092. ЧВК  3966119. PMID  24683500.
  3. ^ а б ЛаВалль, Стивен (2006). Алгоритмы планирования. Издательство Кембриджского университета. стр.127 –128.
  4. ^ а б Джаханшахи, Хади; Джафарзаде, Мохсен; Сари, Наейме Наджафизаде; Фам, Вьет-Тхань; Хюин, Ван Ван; Нгуен, Сюан Куинь (февраль 2019 г.). «Планирование движения робота в неизвестной среде с опасным пространством». Электроника. 8 (2): 201. Дои:10.3390 / электроника8020201.
  5. ^ а б Лимоне, Бретт. «Что такое глобальное планирование пути и как оно соотносится с местным планированием пути?». www.energid.com. Получено 2019-10-15.
  6. ^ ЛаВалль, Стивен (1998). Быстро исследуемые случайные деревья: новый инструмент для планирования пути. Citeseer.
  7. ^ Кавраки, Лидия Э .; Латомб, Жан-Клод (1998). Вероятностные дорожные карты для планирования пути робота. CiteSeerX  10.1.1.41.4215.
  8. ^ Левен, Питер; Хатчинсон, Сет (2016-07-02). «Структура для планирования пути в реальном времени в меняющихся условиях». Международный журнал исследований робототехники. 21 (12): 999–1030. Дои:10.1177/0278364902021012001. S2CID  11169688.
  9. ^ Вадаккепат, П .; Кей Чен Тан; Ван Мин-Лян (июль 2000 г.). «Эволюционные искусственные потенциальные поля и их применение при планировании пути роботов в реальном времени». Труды Конгресса 2000 г. по эволюционным вычислениям. CEC00 (Кат. Номер 00TH8512). 1: 256–263 т.1. Дои:10.1109 / CEC.2000.870304. ISBN  0-7803-6375-2.
  10. ^ Гераертс, Р. (май 2010 г.). «Планирование коротких путей с зазором с использованием явных коридоров». 2010 Международная конференция IEEE по робототехнике и автоматизации: 1997–2004. Дои:10.1109 / ROBOT.2010.5509263. ISBN  978-1-4244-5038-1.
  11. ^ Джаклин, Норманн; Повар, Атлас; Гераертс, Роланд (май 2013 г.). «Планирование пути в режиме реального времени в гетерогенных средах: планирование пути в режиме реального времени в гетерогенных средах». Компьютерная анимация и виртуальные миры. 24 (3–4): 285–295. Дои:10.1002 / cav.1511.
  12. ^ Фудзита, Масахиро; Фукути, Масаки; Гутманн, Йенс-Штеффен (2005). «Планирование пути в реальном времени для навигации роботов-гуманоидов». IJCAI. 2005. S2CID  1331595.
  13. ^ Катраказас, Христос; Куддус, Мохаммед; Чен, Вэнь-Хуа; Дека, Липика (01.11.2015). «Методы планирования движения в режиме реального времени для автономного вождения по дорогам: современное состояние и направления будущих исследований». Транспортные исследования, часть C: Новые технологии. 60: 416–442. Дои:10.1016 / j.trc.2015.09.011. ISSN  0968-090X.
  14. ^ Хуэй, Джонатан (2018-04-18). «Беспилотный автомобиль: планирование пути для маневрирования». Средняя. Получено 2019-11-05.