| 10 июня 2020 г. — 9:00 PT
Исследователи из Стэнфордского университета работают над новыми способами транспортировки товаров дронами в городских районах, используя существующие транспортные сети, такие как автобусы. Эта возможность для доставки дронами может ускорить этот процесс, одновременно решая одну из самых серьезных проблем, с которыми сталкиваются дроны-доставщики.
Исследователи из Стэнфорда изучают способы решения серьезных проблем, связанных с эффективностью дронов и максимальной нагрузкой, которую они могут перевозить. В настоящее время большинство дронов-доставщиков, летающих сегодня, способны перевозить только одну посылку за рейс, обычно не превышающую размер небольшой коробки для обуви.
Стэнфорд стремится решить эту проблему, используя уже построенную инфраструктуру, чтобы дроны могли «ездить на автобусе» на части маршрута для экономии энергии. Исследовательская группа изучила автобусные сети Сан-Франциско и Вашингтона. Система смогла вычислить применимые решения за несколько секунд. Команда также обнаружила, что дроны преодолевали до 360% своего летного диапазона по транзитным сетям.
Реферат проекта можно найти ниже, а остальная часть статьи доступна на arXiv.org.
Мы рассматриваем проблему управления большим парком дронов для одновременной доставки посылок по обширным городским районам. Для экономии энергии дроны перемещаются между транспортными средствами общественного пользования (например, автобусами и трамваями). Мы разработали комплексную алгоритмическую основу, которая стремится минимизировать максимальное время выполнения любой доставки. Мы решаем многогранную сложность проблемы с помощью двухуровневого подхода. Во-первых, верхний уровень назначает дроны на последовательности доставки посылок с помощью почти оптимального алгоритма распределения задач с полиномиальной сложностью. Затем нижний уровень выполняет распределение, периодически направляя парк по транзитной сети, используя эффективные ограниченно-субоптимальные методы поиска путей для нескольких агентов, адаптированные к нашим условиям. Эксперименты демонстрируют эффективность нашего подхода на настройках с до 200 дронами, 5000 посылками и транзитными сетями с до 8000 остановками в Сан-Франциско и Вашингтоне. Наши результаты показывают, что система обычно вычисляет решения за несколько секунд на обычном оборудовании, а дроны преодолевают до 360% своего летного диапазона с использованием общественного транспорта.
Двухуровневая система
Подход, над которым работает Стэнфорд, является двухуровневым: верхний уровень используется для распределения задач, а нижний уровень — для поиска путей для нескольких агентов.
Распределение задач
Задача верхнего уровня заключается в том, чтобы взять информацию о местоположении складов и посылок, а также оценить время в пути дрона, вычислить данные и выдать решение. Решение состоит в назначении посылки на склад и дрону-доставщику, а также в назначении каждому дрону последовательности доставок.
Поиск путей для нескольких агентов
Нижний уровень берет транзитную сеть и начальные и конечные точки дронов из верхнего уровня и генерирует подробный набор маршрутов, которым должен следовать каждый дрон в рамках системных ограничений и расписания движения.
Что вы думаете о том, чтобы дроны использовали существующую инфраструктуру, такую как автобусные сети, для повышения эффективности доставки? Сообщите нам в комментариях ниже.
Фото: SISL