6 декабря 2019, пятница, 22:17
VK.comFacebookTwitterTelegramInstagramYouTubeЯндекс.Дзен

НОВОСТИ

СТАТЬИ

PRO SCIENCE

МЕДЛЕННОЕ ЧТЕНИЕ

ЛЕКЦИИ

АВТОРЫ

Новый алгоритм проложит траектории движения для роботов

Схема поиска неконфликтных траекторий для 3 роботов
Схема поиска неконфликтных траекторий для 3 роботов
Источник: Константин Яковлев

Один из подходов к безопасной навигации мобильных агентов (например, роботов) основан на планировании кратчайших безопасных траекторий, следуя по которым, они избегают столкновений и при этом минимизируют время выполнения миссии. Учёные из Института проблем искусственного интеллекта Федерального исследовательского центра «Информатика и управление» РАН, Высшей школы экономики и Российского университета дружбы народов совместно с коллегами из Университета имени Бен-Гуриона разработали и исследовали новый алгоритм, который гарантирует отыскание оптимальных решений и, в отличие от имеющихся аналогов, не опирается на ряд упрощающих допущений. Статья, описывающая предложенный метод, принята на крупнейшую в мире конференцию по искусственному интеллекту — International Joint Conference on Artificial Intelligence (IJCAI 2019). Исследования поддержаны грантом Российского научного фонда, кратко о полученных результатах рассказывается в пресс-релизе фонда.

Многие крупные коммерческие компании переходят на автоматизированное обслуживание складов, когда товары перемещаются роботами. Соответственно, возникает необходимость в создании алгоритмов, обеспечивающих безопасное и своевременное перемещение устройств. Однако большинство созданных алгоритмов опираются на ряд упрощений. Например, обычно считается, что время не непрерывно, а дискретно и подразделяется на временные шаги. Одно действие совершается за один временной шаг. Соответственно, если агент выполняет действие быстрее, то он стоит и ждёт, пока наступит следующий временной шаг, что замедляет процесс движения к цели. Также во многих алгоритмах роботы перемещаются только в четырёх перпендикулярных направлениях, то есть рабочее пространство разбивается на квадратные ячейки и разрешается переход из одной ячейки только в четыре соседние. Это создаёт неудобства при необходимости движения по диагонали.

Учёные разработали метод планирования — CCBS (Continuous-time conflict-based search). Он лишён обоих указанных недостатков, а также не привязан к геометрической форме агентов. Алгоритм CCBS основан на обнаружении потенциальных столкновений и вычислении небезопасных интервалов. Небезопасный интервал — это максимальное время, в течение которого роботу не стоит выполнять определённое действие, так как иначе он гарантированно столкнётся с другим роботом. При обнаружении потенциального конфликта между действиями агентов (например, им нужно пересечь одну границу в одно и то же время) для каждого из них вычисляются небезопасные интервалы. Затем они преобразуются в ограничения, состоящие в том, что роботам не разрешается выполнять свои действия в эти интервалы времени. Далее маршруты отдельных агентов перестраиваются с учётом наложенных ограничений с помощью индивидуального планировщика, который гарантирует отыскание кратчайшей траектории. Таким образом создается итоговое решение — множество неконфликтных траекторий. Экспериментальное исследование проводилось в режиме симуляции на картах размером 10х10 и 256х256 ячеек. Число агентов варьировалось от 4 до 20.

«Результаты экспериментов демонстрируют преимущество предложенного алгоритма по сравнению с предшественниками — суммарное время выполнения миссии снижено на 20 %. Таким образом, мы создали полный оптимальный алгоритм планирования безопасных траекторий для групп агентов, превосходящий большинство мировых аналогов», — рассказывает кандидат физико-математических наук Константин Яковлев, сотрудник Федерального исследовательского центра «Информатика и управление» РАН.

Обсудите в соцсетях

Система Orphus
«Ангара» Африка Византия Вселенная Гренландия ДНК Иерусалим КГИ Луна МГУ Марс Монголия НАСА РБК РВК РГГУ РадиоАстрон Роскосмос Роспатент Росприроднадзор Русал СМИ Сингапур Солнце Титан Юпитер акустика антибиотики античность археология архитектура астероиды астрофизика бактерии бедность библиотеки биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера викинги вирусы воспитание вулканология гаджеты генетика география геология геофизика геохимия гравитация грибы дельфины демография демократия дети динозавры животные здоровье землетрясение змеи зоопарк зрение изобретения иммунология импорт инновации интернет инфекции ислам исламизм исследования история карикатура картография католицизм кельты кибернетика киты климатология клонирование комары комета кометы компаративистика космос культура лазер лексика лженаука лингвистика льготы мамонты математика материаловедение медицина металлургия метеориты микробиология микроорганизмы мифология млекопитающие мозг моллюски музеи насекомые наука нацпроекты неандертальцы нейробиология неолит обезьяны общество онкология открытия палеолит палеонтология память папирусы паразиты перевод питание планетология погода политика право приматы природа психиатрия психоанализ психология психофизиология птицы ракета растения религиоведение рептилии робототехника рыбы сердце смертность собаки сон социология спутники старение старообрядцы стартапы статистика такси технологии тигры топливо торнадо транспорт ураган урбанистика фармакология физика физиология фольклор химия христианство цифровизация школа экология электрохимия эпидемии эпидемиология этология язык Александр Беглов Дмитрий Козак Древний Египет Западная Африка Латинская Америка НПО «Энергомаш» Нобелевская премия РКК «Энергия» Российская империя Сергиев Посад альтернативная энергетика аутизм биология бозон Хиггса глобальное потепление грипп защита растений информационные технологии искусственный интеллект история искусства история цивилизаций исчезающие языки квантовая физика квантовые технологии климатические изменения компьютерная безопасность компьютерные технологии космический мусор криминалистика культурная антропология междисциплинарные исследования местное самоуправление мобильные приложения научный юмор облачные технологии обучение одаренные дети педагогика персональные данные подготовка космонавтов преподавание истории продолжительность жизни происхождение человека русский язык сланцевая революция физическая антропология финансовый рынок черные дыры эволюция эмбриональное развитие этнические конфликты ядерная физика Вольное историческое общество жизнь вне Земли естественные и точные науки НПО им.Лавочкина Центр им.Хруничева История человека. История институтов дело Baring Vostok Протон-М 3D Apple Big data Dragon Facebook Google GPS IBM MERS PayPal PRO SCIENCE видео ProScience Театр SpaceX Tesla Motors Wi-Fi

Редакция

Электронная почта: [email protected]
Телефон: +7 929 588 33 89
Яндекс.Метрика
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003 года. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2019.