Источник: Northwestern University
Учёные из Северо-Западного университета (Northwestern University) в Чикаго разработали алгоритм движения автономных транспортных средств, который, по их словам, гарантирует отсутствие пробок и столкновений.
«Когда на дорогу выходит множество автономных транспортных средств, есть риски их столкновения друг с другом или образования пробок. Мы создали алгоритм движения группы роботов, который поможет управлять целыми парками автономных транспортных средств, взаимодействующих друг с другом», — поясняет руководитель исследований, сотрудник университета Майкл Рубенштейн.
Преимущество нового алгоритма — в его децентрализованности. Централизованное управление, по мнению исследователей, может стать недостатком: в случае ошибки вся система выйдет из строя. Децентрализованный алгоритм Рубенштейна позиционируется как отказоустойчивый.
«Если система централизована, и ведущий робот перестает работать, то вся система выходит из строя. В децентрализованной системе нет лидера, говорящего всем остальным роботам, что делать. Каждый робот принимает свои собственные решения. Если один робот терпит неудачу в группе, группа всё равно может выполнить задачу», — заявляет Рубенштейн.
Тем не менее, роботы должны координировать действия, чтобы избежать столкновений и пробок. Для этого алгоритм представляет землю под роботами как сетку. С помощью технологии, аналогичной GPS, каждый робот знает, где он находится в рамках сетки. Перед тем, как принять решение, куда двигаться, каждый робот использует датчики, которые показывают его положение относительно соседей, и определяет, свободны соседние пространства в сетке или нет.
«Роботы отказываются перемещаться в какое-то место, пока это место не освободится, и пока они не узнают, что другие роботы не планируют двигаться туда же. Роботы осторожны и резервируют место заранее».
Тщательная координация движений не мешает скорости и маневренности роботов. Чтобы они двигались аккуратно и быстро, роботов сделали «близорукими».
«Каждый робот может «чувствовать» только трёх или четырёх своих ближайших соседей, — объясняет Рубенштейн. — Они не видят всю группу, что облегчает масштабирование системы. Роботы взаимодействуют локально и принимают решения без ненужной общей информации».
Исследователи проверили алгоритм на модели из 1024 роботов и на группе из 100 настоящих роботов в лаборатории. Эксперименты показали, что алгоритм позволяет роботам безопасно и эффективно перемещаться, образовывая заранее заданную форму менее чем за минуту. Более ранние алгоритмы добивались такого результата за час.
Рубенштейн надеется, что его алгоритм в будущем пригодится в автопарках и на автоматизированных складах.
«У крупных компаний есть склады с сотнями робомобилей, которые выполняют задачи, аналогичные тем, что делают наши роботы в лаборатории, — утверждает он. — Им нужно убедиться, что их автономные машины не сталкиваются и при этом двигаются как можно быстрее».
Статья с подробным описание алгоритма будет опубликована в конце этого месяца в журнале IEEE Transactions on Robotics.
Kanut
А этот алгоритм гарантирует что все машины доберутся до пункта назначения и ещё и сделают это в примелемые сроки?
А то как тамый простой алгоритм для избежания пробок это просто никуда не ехать. Но это как бы тоже не особо вариант :)
MRD000
Я согласен, на примере «роботы» эти далеко от своих точек не отходят. А реалии, на любом складе нужно в разные уголки добираться. Но я так понимаю, скорость может быть жертвой автономности и безопасности. В распределенных системах всегда по-моему приходится чем-то жертвовать. Например, похоже, что в роботы тут движутся на один шаг каждый раз, что, естественно, может повлечь большие затраты энергии на старт-стоп и скорость. Но все еще зависит от алгоритма, например есть ли связь между роботами.
Наверное идеальный случай был бы чтобы какая-то система все-таки помогала предсказывать куда роботу нужно будет, но при таком количестве роботов это сложно в любом случае.
Bedal
Хорошая студенческая работа.
MRD000
Не факт. Центральное управление может больше сэкономить. Но автономность перевешивает затраты на вычислительную мощность в каждом роботе. Кроме того, это просто удобнее обслуживать и разрабатывать, когда робот вместе с вычислением. Да и чипы сейчас стоят копейки, смотря какие, конечно. Но затраты на стоп-старт робота весом 10-20-30 кг (не знаю сколько батареи весят) явно на несколько порядков больше потребления чипа.
Bedal
зачем спорить с общими положениями? Естественная устойчивость (саморегулирование, называй, как хочешь) экономичнее централизованного управления просто потому, что отсутствуют накладные расходы. Но — в пределах малых возмущений.
там речь о десятичных порядках разницы. И я не верю, что модель сделали в виде пошаговой стратегии из удобства обслуживания. Это очень и очень большое, принципиальное, отличие от динамической модели. Поскольку моя работа в изготовлении как раз моделей (энергосистем), утверждаю это ответственно.Разницу между линейными уравнениями и дифференциальными — понимаете? Вот оно самое. И дело не в потреблении чипа, конечно, а в его способности вообще это считать. И в умении авторов проекта такую модель создать.
Ещё раз: все признаки действительно хорошей студенческой работы. Если бы изложение было правильно позиционированно — вообще только похвалы. Но это «учёные»… детский сад, право слово.