Способ и система для эффективного планирования для множества автоматизированных неголономных транспортных средств с использованием планировщика скоординированных маршрутов
Изобретение относится к способам и системе для планирования скоординированных маршрутов на складе. Технический результат заключается в повышении быстродействия планирования маршрутов. Система содержит автоматизированные транспортные средства, каждое из которых снабжено модулем навигации, соединенным с системой рулевого управления и системой движения, и центральный процессор, выполняющий команды для получения задачи для автоматизированных транспортных средств, обращения к многоуровневому графу, содержащему высокоуровневые узлы, построения сетки, связанной со складом, выбора из нескольких квадратов сетки квадратов сети для определения соединительных маршрутов, построения набора решений графов карт маршрутов из многоуровневого графа, выбора плана скоординированных маршрутов из набора решений графов карт маршрутов, и передачи плана скоординированных маршрутов автоматизированным транспортным средствам, модуль навигации каждого из которых управляет системой рулевого управления и системой движения в соответствии с планом скоординированных маршрутов. 3 н. и 18 з.п. ф-лы, 9 ил., 2 табл.
ОБЛАСТЬ ТЕХНИКИ
Варианты осуществления настоящего изобретения в целом относятся к системе управления транспортными средствами и, более конкретно, к способу и к системе для эффективного планирования для множества автоматизированных неголономных транспортных средств с использованием планировщика скоординированных маршрутов.
ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ
Автоматизированные транспортные средства работают в динамических условиях многофункциональных складов, в которых используется множество транспортных средств. В этих условиях движению автоматизированных транспортных средств при выполнении ими поставленных задач могут мешать неожиданные препятствия или ситуации. В результате предварительное планирование быстро устаревает, поскольку в результате несогласованных действий транспортных средств могут возникать тупиковые ситуации, и выполнение критичных по времени задач может оказаться под угрозой. Запланированная работа может также нарушаться в результате воздействия таких факторов, как общее время движения, ограничения транспортного средства (неголономное движение) и потребление топлива. Указанные проблемы стимулировали разработку и внедрение предлагаемого способа планирования, в котором используются скоординированные маршруты для множества транспортных средств.
Исследования в области планирования маршрутов множества транспортных средств ведутся уже достаточно продолжительное время. Например, известен координированный способ, при котором движение роботов ограничено заданными маршрутами, в результате чего может быть сравнительно быстро получено полное решение задачи. Однако нет способа, который обеспечивал бы близкое к оптимальному решение для неголономных транспортных средств, двигающихся по непрямолинейным маршрутам, позволяющим обходить двигающиеся препятствия и избегать столкновений. Хотя разработанные способы могут быть полезными, однако задача рассматривается недостаточно широко, чтобы эти способы можно было использовать непосредственно в реальных производственных условиях. Могут быть выдвинуты требования высокой степени использования ресурсов и пропускной способности системы. Современные способы решения задачи планирования, особенно для множества транспортных средств, часто имеют слишком большие ограничения, которые не позволяют получать оптимальные решения.
Поэтому существует потребность в способе и устройстве для эффективного планирования движения множества неголономных автоматизированных транспортных средств с использованием планирования скоординированных маршрутов.
КРАТКОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ
В настоящем изобретении предлагается способ планирования скоординированных маршрутов для одного или нескольких автоматизированных транспортных средств, включающий: обеспечение запроса планировщику маршрутов, работающему в режиме реального времени, на поиск возможных решений по выполнению по меньшей мере одной задачи для каждого из автоматизированных транспортных средств; анализ результатов, полученных по запросу; выбор плана скоординированных маршрутов для каждого транспортного средства; и передачу плана скоординированных маршрутов в менеджер графика, который обеспечивает выполнение одним или несколькими автоматизированными транспортными средствами каждой задачи в соответствии с этим планом.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Для того чтобы можно было лучше понять вышеуказанные особенности настоящего изобретения, ниже приводится подробное описание вариантов осуществления изобретения со ссылками на прилагаемые чертежи. Однако следует отметить, что прилагаемые чертежи иллюстрируют только типичные варианты осуществления изобретения и поэтому не должны рассматриваться как ограничения его объема, поскольку возможны и другие в равной степени эффективные варианты.
Фигура 1 - функциональная блок-схема системы для эффективного управления автоматизированными транспортными средствами с использованием карты и планировщика скоординированных маршрутов по различным вариантам осуществления настоящего изобретения.
Фигура 2 - многоуровневый граф для осуществления планирования скоординированных маршрутов автоматизированного транспортного средства по различным вариантам осуществления изобретения.
Фигура 3 - пример графа карты маршрутов по различным вариантам осуществления изобретения для склада с автоматизированными транспортными средствами.
Фигура 4 - пример графа карты маршрутов по различным вариантам осуществления изобретения, который иллюстрирует решение задачи маршрутизации для автоматизированных транспортных средств внутри склада.
Фигура 5 - пример графа карты маршрутов по различным вариантам осуществления изобретения, который иллюстрируется другое решение маршрутизации для автоматизированных транспортных средств внутри склада.
Фигуры 6А, 6В, 6С - виды различных уровней многоуровневого графа для эффективной диспетчеризации множества неголономных автоматизированных транспортных средств с использованием планирования скоординированных маршрутов по различным вариантам осуществления изобретения.
Фигура 7 - блок-схема системы для эффективного управления автоматизированными транспортными средствами с использованием карты и планировщика скоординированных маршрутов по различным вариантам осуществления изобретения.
ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Для группы задач, таких как перемещение продукции на складе, различные варианты способа и системы для эффективной диспетчеризации множества неголономных автоматизированных транспортных средств с использованием планирования скоординированных маршрутов представляют собой решение, которое обеспечивает оптимальное использование ресурсов, причем некоторые варианты обеспечивают соблюдение текущих и перспективных конечных сроков. Может быть задана задача для оптимизации, включая такие условия как скорости маневрирования, потребление топлива и местонахождение выполнения предстоящих задач. Скорость вычисления решений планирования обеспечивает различные возможности для оценки текущих и предстоящих задач, в результате чего может быть выбрано наилучшее решение. Решения для маршрутов также расширяются с использованием плавных траекторий с непрерывной кривизной для обеспечения движения автоматизированного транспортного средства без остановок.
В настоящем изобретении предлагается устройство или система планирования маршрутов для множества неголономных автоматизированных транспортных средств. Указанное устройство разработано для использования с автоматизированными транспортными средствами (например, роботами, автоматизированными вильчатыми подъемниками и т.п.) с целью решения задач планирования. В общем случае к неголономным относятся системы, состояния которых определяются траекториями, используемыми для достижения этих состояний.
Время планирования и возможность наращивания (масштабируемость) являются критическими факторами для функциональных систем. Для уменьшения пространства поиска и сокращения времени нахождения решения вводится ограничение на общее количество автоматизированных транспортных средств в многоуровневом узле. В результате снижается сложность вычислений, однако ухудшение качества расчетов при этом будет незначительным, поскольку в общем случае автоматизированные транспортные средства необязательно находятся в одной и той же зоне склада. Быстрое планирование позволило формировать прогнозные планы. Прогнозирование позволяет компоненту диспетчеризации тратить больше времени на нахождение оптимального решения без нарушения управления текущим движением автоматизированных транспортных средств. Прогнозирование также обеспечивает уровень понимания завершения выполнения заказов и помогает гарантировать, что использование автоматизированных транспортных средств будет эффективным не только для текущей задачи, но также и для предстоящих задач.
Настоящее изобретение направлено на гибкое использование автоматизированных транспортных средств и взаимодействие со средой (например, со складом) с использованием планирования скоординированных маршрутов, при котором обеспечивается движение по расчетным маршрутам с возможностью схода с этих маршрутов. При этом обеспечивается возможность включения автоматизированного транспортного средства в любом положении и движения к конечной точке маршрута с достаточной точностью, при которой транспортное средство может должным образом взаимодействовать со средой при выполнении задач. Кроме того, поскольку заблокированные маршруты могут приводить к тому, что будут заблокированы и другие сегменты маршрута, предотвращение возможности других автоматизированных транспортных средств вхождения в эту зону улучшает использование ресурсов и экономит время, которые в противном случае было бы потрачено на бесполезное ожидание освобождения проезда или нахождение альтернативного маршрута, обходящего препятствие и заблокированный маршрут.
На фигуре 1 приведена функциональная блок-схема системы 100 для эффективного управления автоматизированными транспортными средствами с использованием карты 102 и планировщика 104 скоординированных маршрутов по различным вариантам осуществления настоящего изобретения. Кроме планировщика 104 скоординированных маршрутов система 100 содержит различные модули (например, программное обеспечение, встроенное программное обеспечение, аппаратные средства и/или т.п.), такие как диспетчер 106, модуль 108 навигации и менеджер 110 графика.
В некоторых вариантах диспетчер 106 запрашивает у планировщика 104 скоординированных маршрутов различные возможные решения для одного или нескольких имеющихся автоматизированных транспортных средств, выполняющих различные задачи. Диспетчер 106 более эффективно назначает эти задачи автоматизированным транспортным средствам путем сравнительного анализа результатов возможных решений, получаемых из планировщика 104 скоординированных маршрутов. После выбора решения, которое должно выполняться, диспетчер 106 передает скоординированный маршрут менеджеру 110 графика для управления и/или контроля выполнения задач автоматизированными транспортными средствами. Менеджер 110 графика обеспечивает выполнение автоматизированными транспортными средствами назначенных задач в соответствии планом скоординированных маршрутов. Каждое автоматизированное транспортное средство содержит модуль 108 навигации для управления движением этого транспортного средства и определения его местонахождения. Менеджер 110 трафика контролирует пройденное расстояние на основе текущего состояния выполнения задачи. По мере поступления новой информации, такой как изменения карты 102 или новые задачи, которые должны решаться, диспетчер 106 продолжает искать улучшенные решения и перенаправляет автоматизированные транспортные средства по различным маршрутам.
Для нахождения наилучшего решения диспетчер 106 должен запрашивать планировщик 104 маршрутов в отношении каждого возможного решения для каждой имеющейся задачи, выполняемой разными автоматизированными транспортными средствами. Диспетчер 106 обрабатывает результаты каждого решения и находит наиболее подходящее решение. Для того чтобы получить удовлетворительное время поиска, можно задать пороговые значения для результатов и/или выбор наилучшего решения в пределах заданного промежутка времени. Уменьшение времени поиска решений предотвращает возникновение различных проблем, таких как задержки, вызванные простоями, бесполезным расходованием ресурсов и/или нарушением сроков выполнения задач.
В некоторых вариантах диспетчер 106 прогнозирует будущие решения на основе информации о предстоящих задачах. При планировании маршрута для автоматизированного транспортного средства другое транспортное средство перемещается в некоторое место и при выполнении некоторой части текущей задачи блокирует зону в течение некоторого расчетного времени. Это расчетное время учитывается при планировании маршрутов и диспетчеризации. По истечении планируемого времени другое автоматизированное транспортное средство может двигаться в другое место. В результате, выполнение задачи автоматизированным транспортным средством не будет вступать в конфликт с выполнением текущей задачи другим таким транспортным средством. Выявление и предотвращение проблемных ситуация (например, положений, из которых невозможно выбраться) улучшает эффективность использования времени за продолжительный период.
В ответ на запрос из диспетчера 106 планировщик 104 скоординированных маршрутов передает оценки времени для каждой возможной конфигурации одного или нескольких автоматизированных транспортных средств. На оценки времени могут влиять различные факторы. Например, назначение задачи какому-либо автоматизированному транспортному средству может негативно сказаться на других автоматизированных транспортных средствах, которые также выполняют задачи или бездействуют. Поскольку запуск выключенных автоматизированных транспортных средств требует затрат времени и ресурсов (например, топлива), в некоторых вариантах диспетчер 106 использует эвристическую процедуру, которая учитывает такие затраты. Например, планировщик 104 скоординированных маршрутов добавляет условия, представляющие затраты на запуск выключенных автоматизированных транспортных средств.
Система 100 может выполнять планирование скоординированных маршрутов непрерывно или циклически. В некоторых вариантах, поскольку задачи появляются постепенно, планирование скоординированных маршрутов выполняется последовательно, а не для всех задач сразу, из-за времени вычислений и ограниченной информации. Кроме того, когда происходит некоторое событие, такое как поступление новой задачи или изменение карты 102, текущий план становится неполноценным, поскольку, возможно, может быть найдено лучшее решение. Однако планирование - это не мгновенный процесс, и было бы нерационально останавливать автоматизированные транспортные средства, пока не будет рассчитан новый план. В некоторых вариантах диспетчер 106 передает в менеджер 110 графика заданный интервал времени, после которого автоматизированные транспортные средства будут остановлены, и менеджер 110 трафика также возвращает расчетные положения транспортных средств, в которых они должны быть после истечения этого интервала времени.
Тем временем диспетчер 106 выполняет планирование и диспетчеризацию с этого момента времени с учетом обновленного события. По истечении этого времени диспетчер 106 выбирает лучшее найденное решение, исходя из того, что такое решение соответствует заданному пороговому значению, и обновляет текущий план. Если решение не соответствует этому пороговому значению, необходимо осуществлять дополнительное планирование. Если происшедшее событие не изменяет текущий план, автоматизированные транспортные средства продолжают выполнение задач без перерыва.
В производственных условиях (например, на складе) некоторые зоны часто становятся закрытыми для проезда по разным причинам, таким как неисправность автоматизированного транспортного средства или помеха (например, помеха, которой нет на карте 102). Как это будет подробно описано ниже, поскольку пространство поиска (например, надграф, включающий все конфигурации автоматизированных транспортных средств, как это будет описано ниже) исключает осуществление изменений в режиме реального времени, то когда происходят изменения карты 102, вместо этого записывается перечень заблокированных узлов. Планировщик 104 скоординированных маршрутов проверяет этот перечень при выполнении планирования маршрутов для предотвращения прокладки маршрутов через эти зоны. В некоторых вариантах, если известно, что одни и те же узлы будут заблокированы в течение некоторого времени, заново осуществляется расчет в режиме офлайн (не в режиме реального времени) на уровне эвристической процедуры.
Вместо использования стандартных траекторий Дубинса (Dubins paths) для неголономных автоматизированных транспортных средств, планировщик 104 скоординированных маршрутов модифицирует траекторию Дубинса для добавления переходных периодов непрерывного изменения кривизны. Непрерывное изменение кривизны траектории необходимо для обеспечения возможности точного движения автоматизированного транспортного средства с более высокой скоростью. В некоторых вариантах система 100 реализует траектории Дубинса путем конструирования сегментов графа и соединительных сегментов маршрутов из плавных путей. Соединительные сегменты маршрутов могут иметь более крутые повороты на концах и более плавные повороты в тех местах, где соединительные сегменты соединяются с графом, поскольку автоматизированное транспортное средство будет двигаться быстрее, когда оно достигает графа. Поскольку эти маршруты требуют дополнительного пространства, присоединение соединительных сегментов должно повторяться с более острыми сегментами маршрутов, если соединение оказывается неудачным на более плавных сегментах.
На фигуре 2 представлен многоуровневый граф 200 для планирования скоординированных маршрутов автоматизированных транспортных средств по различным вариантам осуществления изобретения. Планировщик 104 скоординированных маршрутов считает все автоматизированные транспортные средства вместе как одну составную структурную единицу с одной или несколькими степенями свободы. Начальные положения автоматизированных транспортных средств представляют одну конфигурацию этой структурной единицы, конечные положения - другую конфигурацию. Каждая конфигурация может представлять состояние в неголономной системе.
Как показано на фигуре 2, многоуровневый граф 200 определяет начальное положение 202 и конечное положение 204 для составной структурной единицы, состоящей из одного или нескольких автоматизированных транспортных средств. Общее число возможных конфигураций ограничивается степенью дискретизации многоступенчатого графа 200 карты маршрутов, как это подробно описывается ниже. Движение одного или нескольких автоматизированных транспортных средств может быть представлено как последовательность конфигураций. Каждая конфигурация описывает положения одного или нескольких автоматизированных транспортных средств, которые могут включать один или несколько узлов карты маршрутов, таких как узел 206 карты маршрутов, один или несколько соединительных узлов на узле высокого уровня, таком как узел 208 высокого уровня. Одна конфигурация может быть согласована с другой конфигурацией, когда одно или несколько автоматизированных транспортных средств перемещаются между соединенными узлами карты маршрутов при условии, что эти перемещения не приводят к столкновениям.
В некоторых вариантах планировщик 104 скоординированных маршрутов размещает на карте различные типы узлов и после этого соединяет эти узлы с использованием сегментов маршрутов, формирующих граф карты маршрутов. Могут использоваться следующие типы узлов: узел 206 карты маршрутов, высокоуровневый узел 208, соединительный узел 210 и конечный соединительный узел 212. Сегменты маршрутов, соединяющие различные узлы, включают путь 214 и путь 216. Автоматизированные транспортные средства двигаются от одного узла к другому по сегментам маршрутов, пока они не достигают конечного положения 204.
Планировщик 104 скоординированных маршрутов в режиме офлайн формирует узлы высокого уровня с использованием всех возможных комбинаций или конфигураций автоматизированных транспортных средств на различных узлах карты маршрутов. Эти узлы высокого уровня соединяются при перемещении автоматизированного транспортного средства по соединительному сегменту маршрута для достижения другого узла высокого уровня. Планировщик 104 скоординированных маршрутов использует различные способы вычислений (например, вычислительный способ надграфов) В некоторых вариантах узлы высокого уровня и связанные с ними соединения формируют надграф. Соответственно, надграф включает все конфигурации автоматизированных транспортных средств внутри графа 200 высокого уровня. Планировщик 106 осуществляет в рабочем цикле "прохождение" надграфа с целью поиска наилучшего решения для планирования маршрутов без необходимости выполнения каких-либо расчетов пересечений, которые выполняются в режиме офлайн.
В некоторых вариантах планировщик 104 скоординированных маршрутов использует эвристическую процедуру для поиска многоуровневого графа 200 в качестве наилучшего решения (то есть, маршрута). Например, эвристическая процедура может быть направлена на время прохождения автоматизированных транспортных средств между узлами. Оценки времен прохождения могут быть сделаны в режиме офлайн и просуммированы для всех автоматизированных транспортных средств, задействованных в некотором плане маршрутов. Планировщик 104 скоординированных маршрутов повторяет процесс планирования маршрутов для выбора наилучшего решения по сравнению с решением, найденным в результате эвристической процедуры.
В некоторых вариантах, включающих большие площади с несколькими автоматизированными транспортными средствами, планировщик 104 скоординированных маршрутов использует многоуровневый граф, такой как многоуровневый граф 200 для сокращения размеров пространства поиска. Планировщик 104 скоординированных маршрутов группирует различные узлы, такие как узлы карты маршрутов и узлы соединений, в узлы более высокого уровня, как это показано на фигуре 2. Сначала находят решение для части более высокого уровня многоуровневого графа 200, после чего находят более конкретное решение для нижележащего уровня, пока не будет закончено прохождение всех уровней.
Дополнительное сокращение пространства поиска осуществляется путем ограничения количества автоматизированных транспортных средств в узлах высокого уровня. Это ограничение вполне возможно в производственных условиях, в которых в заданной зоне может действовать эффективно лишь одно или два автоматизированных транспортных средства. Многоуровневый граф 200 будет приводить к менее оптимальному решению, поскольку в нем допускается, что наилучшее решение на высоком уровне будет содержать наилучшее решение на более низком уровне, что представляет компромисс в целях сокращения времени вычислений. Сравнение полученной оценки с результатом эвристической процедуры может быть выполнено для многоуровневого графа 200 в режиме офлайн.
В некоторых вариантах с высокой плотностью трафика, решение, находимое планировщиком 104 скоординированных маршрутов, будет содержать ожидание одним или несколькими автоматизированными транспортными средствами, пока другие транспортные средства не пройдут определенные зоны. Такие решения будут отмечены в плане как зависимости между транспортными средствами, находящимися в соответствующих зонах. Менеджер 110 трафика обрабатывает эти зависимости при выполнении такого решения и обеспечивает их выдерживание при определении расстояний, на которые разрешается перемещение транспортных средств.
В некоторых вариантах автоматизированные транспортные средства не всегда будут начинать или заканчивать движение в положении, которое находится на маршруте 216. Это происходит в тех случаях, когда управление ими осуществляют водители, и они начинают движение в какой-то точке известной зоны, или в случае необходимости взаимодействия с изделиями, помещенными водителями, что не отражено на многоуровневом графе 200. Для решения этой проблемы необходимо рассчитать маршрут от начального положения до узла и маршрут от узла до конечного положения 204 для каждого автоматизированного транспортного средства. Пока имеется достаточное покрытие карты маршрута, будет достаточно траектории Дубинса или ему подобного пути.
Может быть несколько узлов, с которыми может быть установлено соединение, и ближайший узел необязательно будет оптимальным. Важным достоинством способа, предлагаемого в настоящем изобретении, является то, что скорость вычислений позволяет определять почти оптимальные точки соединений. Также может более эффективно осуществляться соединение на краю карты маршрутов, а не на узле. Для того чтобы сузить возможности соединений для автоматизированного транспортного средства, в режиме офлайн может быть определена сетка, которая будет содержать возможные узлы, которые могут быть достигнуты из каждого квадрата сетки. В процессе выполнения рабочего цикла считываются возможные узлы, и выполняется двоичное сканирование по их
соединительным сегментам для определения наилучшей точки соединения. В качестве вариантов для поиска выбираются верхние сегменты маршрутов, причем используется узел на конце сегмента. Эти соединительные пути графа должны выбираться таким образом, чтобы они не пересекали начальные/конечные положения или начальные/конечные узлы других автоматизированных транспортных средств, и это обеспечит возможность для достижения ими их начального узла и оставления их последнего узла без создания тупика. Определение соединительных сегментов означает, что в процессе выполнения рабочего цикла будут осуществляться расчеты пересечений, однако зоны малы, и задача может быть быстро решена, если карта 102 будет разбита на дерево квадрантов.
На фигуре 3 приведен пример графа 300 карты маршрутов по различным вариантам осуществления изобретения, который иллюстрирует склад с автоматизированными транспортными средствами.
Граф 300 карты маршрутов содержит три автоматизированных транспортных средства, в задачу которых входит отбор изделий с правой стороны карты и транспортировка отобранных изделий на левую сторону. Первое автоматизированное транспортное средство 302 забирает изделие, которое должно быть выгружено на другой стороне склада. Затем одно из двух других автоматизированных транспортных средств должно подъехать и отобрать следующее изделие на правой стороне. Для диспетчера 106 имеются по меньшей мере два решения: использовать второе 304 или третье 306 автоматизированное транспортное средство для отбора изделия. Все возможные решения, вместе с перемещением первого автоматизированного транспортного средства 302 налево, передаются в планировщик 104 скоординированных маршрутов, в котором рассчитываются маршруты с оценкой времени до завершения задач.
| Таблица I | ||||
| Оценки времени при использовании разных автоматизированных транспортных средств (AV) | ||||
| Оценки времени движения | ||||
| AV302 | AV304 | AV306 | ||
| AV, выбранное для отбора изделий справа | AV304 | 34,13 | 19,43 | 5,76 |
| AV306 | 36,30 | 10,11 | 44,74 |
[0039] Полученные оценки времени приведены в Таблице I, и, как можно видеть, второе автоматизированное транспортное средств 304 является предпочтительным для выполнения задачи, поскольку оно ближе и, кроме того, оно перекрывает коридор. Это решение иллюстрируется на фигуре 4. Поскольку запуск выключенных автоматизированных транспортных средств может быть нежелательным, в некоторых вариантах учитываются затраты. Такое решение иллюстрируется на фигуре 5.
В некоторых вариантах планировщик 104 скоординированных маршрутов и диспетчер 106 учитывают ситуации, в которых одно автоматизированное транспортное средство должно ожидать другое транспортное средство. Для этих ситуаций определяются положения ожидания и оценки времени и включаются в планирование и диспетчеризацию маршрутов, описанных со ссылками на фигуры 4 и 5. Как показано на фигурах 4 и 5, на графах карты маршрутов и в качестве соединительных сегментов используются пути с непрерывной кривизной. Соединительные сегменты острее на концах, поскольку автоматизированные транспортные средства двигаются медленнее.
В Таблице II приведены оценки времени движения первого автоматизированного транспортного средства 302, второго автоматизированного транспортного средства 304 и третьего автоматизированного транспортного средства 306 с учетом времени, потраченного на включение автоматизированного транспортного средства.
| Таблица II | ||
| Оценки времени движения | ||
| AV302 | AV304 | AV306 |
| 39,78 | 19,43 | 0,00 |
На фигуре 4 приведен пример графа 400 карты маршрутов, иллюстрирующий решение по одному из вариантов осуществления изобретения для планирования маршрутов автоматизированных транспортных средств внутри склада, аналогичного складу на фигуре 3. Первое автоматизированное транспортное средство 302 начинает выполнение задачи в начальном положении S1 (например, прямоугольник слева от обозначения S1 на графе 400 карты маршрутов) и отбирает изделие. Третье автоматизированное транспортное средство 306 перемещается для выполнения задачи с максимально возможной скоростью, в то время как первое автоматизированное транспортное средство 302 использует соединительный сегмент для достижения конечного положения G1 с двумя потенциальными положениями ожидания, обозначенными W1.
Как указано на графе 400 карты маршрутов, начальное положение S1 также является конечным положением G2 для второго автоматизированного транспортного средства 304. Соответственно, второе автоматизированное транспортное средство 304 перемещается в конечное положение G2 для отбора следующего изделия с положением W2 ожидания. В некоторых вариантах первое автоматизированное транспортное средство 302 останавливается и ожидает перемещения второго автоматизированного транспортного средства 304 в конечное положение G2 и/или ожидает перемещения третьего автоматизированного транспортного средства в конечное положение G3. В некоторых вариантах третье автоматизированное транспортное средство 306, расположенное в начальном положении S3, представляет собой помеху для перемещения первого автоматизированного транспортного средства 302 и должно быть убрано с его маршрута. В других вариантах второе автоматизированное транспортное средство 304 расположено в начальном положении S2. При перемещении в конечное положение G2 второе автоматизированное транспортное средство 304 ожидает в положении W2 ожидания, пока первое автоматизированное транспортное средство 302 не покинет зону вокруг конечного положения G2, которое также обозначено S1 (начальное положение).
На фигуре 5 приведен пример графа 500 карты маршрутов, иллюстрирующий другое решение по одному из вариантов осуществления изобретения для планирования маршрутов автоматизированных транспортных средств внутри склада, аналогичного складу на фигуре 3. В некоторых вариантах другие решения отличаются от решения, показанного на фигуре 4, несколькими аспектами. Например, планировщик скоординированных маршрутов, который сконфигурирован в соответствии с этим решением, назначает более высокую стоимость запуску автоматизированного транспортного средства. Первое автоматизированное транспортное средство 302 начинает выполнение задачи в начальном положении S1 и отбирает изделие. В то время как первое автоматизированное транспортное средство 302 использует соединительный сегмент для достижения конечного положения G1 с потенциальным положением ожидания, обозначенным W1, второе автоматизированное транспортное средство 304 перемещается из начального положения S2 в конечное положение G2, которое также является начальным положением S1. Хотя первое автоматизированное транспортное средство 302 должно пройти немного большее расстояние, однако в этом случае нет необходимости в запуске третьего автоматизированного транспортного средства 306, в результате чего достигается существенная экономия. Для максимально быстрого выполнения задачи нет необходимости в перемещении третьего автоматизированного транспортного средства 306 из начального положения S3.
На фигурах 6А, 6В, 6С приведены виды различных уровней многоуровневого графа 600 для эффективной диспетчеризации множества неголономных автоматизированных транспортных средств с использованием планирования скоординированных маршрутов по различным вариантам осуществления изобретения. На фигурах 6А, 6В, 6С иллюстрируется планирование маршрутов между начальным положением 602 и конечным положением 604 путем определения оптимальных локальных маршрутов между различными узлами высокого уровня, такими как узлы 606 и 608. На фигурах 6А и 6В показаны графы высоких уровней, и на фигуре 6С показан базовый граф карты маршрутов. Следует понимать, что для планирования скоординированных маршрутов может использоваться несколько графов более высоких порядков. Например, для более сложных условий работы на протяженных территориях может потребоваться использовать более двух графов высших уровней и одного базового графа карты маршрутов.
В некоторых вариантах планировщик скоординированных маршрутов определяет оптимальные локальные маршруты между одним или несколькими соединительными узлами, то есть, узлами, расположенными на границах узлов высоких уровней. Планировщик скоординированных маршрутов может определять путь между соединительными узлами 610, как показано на фигуре 6 В. Такой оптимальный местный путь может соединять один или несколько узлов карты маршрутов (например, узел 206 карты маршрутов фигуры 2), которые расположены внутри каждого узла высокого уровня. В других вариантах планировщик скоординированных маршрутов рассчитывает оптимальный локальный путь, который не проходит по меньшей мере через один узел карты маршрутов.
Затем определяется локальный путь между начальным положением 602 и локальным соединительным узлом (то есть, начальным соединительным узлом). В некоторых вариантах такой путь включает один или несколько внутренних узлов карты маршрутов. Планировщик 104 скоординированных маршрутов аналогичным образом может рассчитывать второй локальный путь между конечным положением 604 и локальным соединительным узлом (например, конечным соединительным узлом, таким как конечный соединительный узел 212 на фигуре 2). В некоторых вариантах планировщик скоординированных маршрутов объединяет локальные пути для формирования конечного маршрута 612 на графе 600, как показано на фигуре 6С. В некоторых вариантах планировщик 104 скоординированных маршрутов выбирает маршрут с наименьшей стоимостью, который включает такие локальные пути и пути высоких уровней к локальному соединительному узлу, связанному с конечным положением 604. Затем определяются оптимальные пути внутри узлов 606 и 608 высокого уровня. Эти пути необязательно будут совпадать с какой-либо частью пути с наименьшей стоимостью в результате действия различных факторов, таких как другие транспортные средства, работающие в это время поблизости. В соответствии с одним или несколькими вариантами, когда планировщик 104 скоординированных маршрутов определяет оптимальный путь на низшем уровне (то есть, на уровне карты маршрута), он передает полученный результат в качестве конечного маршрута 612.
На фигуре 7 приведена структурная блок-схема системы 700 эффективного планирования для множества автоматизированных неголономных транспортных средств с использованием планировщика скоординированных маршрутов, такого как вышеописанный планировщик 104, по одному или нескольким вариантам осуществления изобретения. В некоторых вариантах система 700 содержит компьютер 702 и множество транспортных средств (указанных как 7041…704N), причем компоненты системы связаны друг с другом по сети 706. Каждое транспортное средство 704 содержит модуль навигации, такой как модуль 108 навигации, для управления работой различных компонентов транспортного средства, таких как системы управления и/или движения. Следует понимать, что множество транспортных средств 704 могут использовать один или несколько компьютеров, в которых может быть реализован модуль 108 навигации.
Компьютер 702 может быть любым вычислительным устройством (например, ноутбуком, настольным компьютером, планшетом и т.п.). Каждое транспортное средство 704 может содержать некоторое вычислительное устройство (например, ноутбук, настольный компьютер, планшетом и т.п.). Вычислительное устройство в общем случае содержит центральный процессор 708, различные вспомогательные схемы 710 и запоминающее устройство 712. Центральный процессор 708 может содержать один или несколько микропроцессоров или микроконтроллеров, которые обеспечивают обработку данных и их промежуточное хранение. Различные вспомогательные схемы 710 обеспечивают работу центрального процессора 708 и могут включать тактовые генераторы, шины, источники питания, схемы ввода/вывода и т.п. Запоминающее устройство 712 содержит постоянное ЗУ, оперативное ЗУ, ЗУ на магнитных дисках, ЗУ на оптических дисках, съемные устройства хранения информации и т.п. Запоминающее устройство содержит различные данные, такие как карта 110, а также различные пакеты прикладных программ, такие как планировщик 104 скоординированных маршрутов, диспетчер 106 и модуль 108 навигации.
Эти пакеты прикладных программ обеспечивают реализацию системы, такой как система 100 фигуры 1, предназначенная для эффективного планирования маршрутов автоматизированных транспортных средств 704.
В некоторых вариантах планировщик 104 скоординированных маршрутов содержит программный код (например, команды, исполняемые процессором), который исполняется центральным процессором для реакции на запросы диспетчера 106, как это было раскрыто в настоящем описании. Планировщик 104 скоординированных маршрутов определяет оценки времени для каждого возможного решения, обеспечивающего выполнение задачи. Эти оценки времени используются для оценки возможных решений. В некоторых вариантах диспетчер 106 выбирает решение для планирования маршрутов автоматизированных транспортных средств 704 путем сравнения с решением, полученным с помощью эвристической процедуры. Диспетчер 106 передает команды (например, план маршрутов в менеджер 110 трафика, который использует модуль 108 навигации для управления операциями и перемещением автоматизированных транспортных средств.
Сеть 706 представляет собой систему связи, которая соединяет компьютеры по проводам, по кабелю, по волоконно-оптическому кабелю и/или по каналам беспроводной связи, и работа которой обеспечивается различными известными компонентами сетей, такими как концентраторы, коммутаторы, маршрутизаторы и т.п. Сеть 706 может использовать различные хорошо известные протоколы для обмена информацией между ресурсами сети. Например, сеть 60 может быть частью сети Интернет или интрасети, использующей различную инфраструктуру связи, такую как Ethernet, WiFi, WiMax, GPRS и т.п.
Хотя все вышеизложенное относится к некоторым вариантам осуществления настоящего изобретения, однако могут быть предложены и другие варианты, не выходящие за пределы объема изобретения, который определяется прилагаемой формулой.
1. Способ планирования скоординированных маршрутов для нескольких автоматизированных транспортных средств, включающий:
получение, по сети и одним или несколькими центральными процессорами, задачи в производственных условиях для одного из нескольких автоматизированных транспортных средств, причем соответствующие автоматизированные транспортные средства содержат модуль навигации, систему рулевого управления и систему движения, при этом центральные процессоры соединены с возможностью связи с несколькими автоматизированными транспортными средствами по сети;
обеспечение многоуровневого графа, содержащего высокоуровневые узлы, причем соответствующие высокоуровневые узлы соответствуют некоторой зоне производственных условий, причем каждый из высокоуровневых узлов содержит один или несколько соединительных узлов, соответствующих границе зоны, один или несколько узлов карты маршрутов, соответствующих внутренней части зоны, и один или несколько локальных маршрутов, которые связывают соединительные узлы, узлы карты маршрутов, или их комбинацию;
построение центральными процессорами сетки, связанной с производственными условиями, причем сетка разделяет несколько квадратов сетки, и соответствующие квадраты сетки содержат часть производственных условий и часть соответствующего многоуровневого графа;
выбор из нескольких квадратов сетки центральными процессорами квадратов сетки, соответствующих начальному положению и/или конечному положению, если начальное положение и/или конечное положение находятся в пределах производственных условий, но за пределами многоуровневого графа;
определение в соответствующих квадратах сетки из выбранных квадратов сети центральными процессорами соединительных маршрутов от начального положения и/или конечного положения до многоуровневого графа;
построение центральными процессорами набора решений графов карт маршрутов из многоуровневого графа, причем каждый граф карты маршрутов содержит начальное положение, соединенное окончательным маршрутом с конечным положением, причем окончательный маршрут содержит определенный соединительный маршрут и по меньшей мере часть локальных маршрутов;
выбор центральными процессорами плана скоординированных маршрутов для автоматизированных транспортных средств из набора решений графов карт маршрутов; и
передачу по сети по меньшей мере части плана скоординированных маршрутов каждому из автоматизированных транспортных средств, причем модуль навигации каждого из автоматизированных транспортных средств управляет системой рулевого управления и/или системой движения в соответствии с планом скоординированных маршрутов.
2. Способ по п. 1, включающий также удаление по меньшей мере части графов карт маршрутов из набора решений графов карт маршрутов по меньшей мере частично на основе эвристического решения каждой части графов карт маршрутов.
3. Способ по п. 1, включающий также ограничение разрешенного количества автоматизированных транспортных средств внутри каждого высокоуровневого узла для уменьшения времени, необходимого для построения набора решений графов карт маршрутов.
4. Способ по п. 3, в котором разрешенное количество автоматизированных транспортных средств внутри каждого высокоуровневого узла не превышает двух.
5. Способ по п. 1, включающий также:
прекращение работы автоматизированных транспортных средств в заданный момент времени; и
возобновление работы автоматизированных транспортных средств после истечения временного интервала от заданного момента времени, причем план скоординированных маршрутов выбирается в течение этого временного интервала.
6. Способ по п. 1, включающий также:
формирование перечня заблокированных узлов, соответствующих высокоуровневым узлам, соединительным узлам и узлам карты маршрутов, которые недоступны; и
прекращение навигации автоматизированных транспортных средств в части зоны, соответствующей заблокированным узлам.
7. Способ по п. 1, включающий также формирование модифицированной траектории Дубинса, содержащей соединительные маршруты на концах модифицированной траектории Дубинса, и маршрута с непрерывным изменением кривизны, расположенного между соединительными маршрутами, причем модифицированная траектория Дубинса содержит более крутые повороты по сравнению с маршрутом с непрерывным изменением кривизны, и один или несколько локальных маршрутов одного из графов карт маршрутов содержат модифицированную траекторию Дубинса.
8. Способ по п. 1, в котором соединительный маршрут не пересекает начальное положение и конечное положение каждого из графов карт маршрутов для другого автоматизированного транспортного средства.
9. Способ по п. 1, в котором в соответствии с планом скоординированных маршрутов требуется, чтобы одно из автоматизированных транспортных средств ожидало, пока одно или несколько других транспортных средств не пройдут определенное место.
10. Способ по п. 1, в котором эвристическое решение определяет время движения.
11. Способ по п. 1, в котором эвристическое решение определяет расходы, связанные с запуском выключенного автоматизированного транспортного средства.
12. Способ по п. 1, в котором эвристическое решение определяет высокоуровневые узлы, соединительные узлы и узлы карты маршрутов, которые недоступны.
13. Способ по п. 1, в котором автоматизированные транспортные средства являются неголономными.
14. Способ по п. 1, включающий также идентификацию центральными процессорами соответствующих соединительных узлов, узлов карты маршрутов или локальных маршрутов, которые соответствуют начальному положению и/или конечному положению, если начальное положение и/или конечное положение расположены в пределах производственных условий и на многоуровневом графе.
15. Способ по п. 1, включающий также связывание центральными процессорами с каждым из графов карт маршрутов эвристического решения, которое определяет окончательный маршрут связанного с ним графа карты маршрутов, причем план скоординированных маршрутов выбирают по меньшей мере частично на основе эвристического решения.
16. Система для планирования скоординированных маршрутов на складе, содержащая:
множество автоматизированных транспортных средств внутри склада, каждое из которых снабжено модулем навигации, соединенным с системой рулевого управления и системой движения; и
один или несколько центральных процессоров, обменивающихся информацией с каждым из автоматизированных транспортных средств, причем один или несколько центральных процессоров выполняют команды для:
получения задачи для одного из нескольких автоматизированных транспортных средств;
обращения к многоуровневому графу, содержащему высокоуровневые узлы, причем соответствующие многоуровневые узлы соответствуют зоне склада, причем каждый высокоуровневый узел содержит один или несколько соединительных узлов, соответствующих границе зоны склада, один или несколько узлов карты маршрутов, соответствующих внутренней части зоны склада, и один или несколько локальных маршрутов, которые связывают соединительные узлы, узлы карты маршрутов, или их комбинацию;
построения сетки, связанной со складом, причем сетка разделяет несколько квадратов сетки, и соответствующие квадраты сетки содержат часть склада и часть соответствующего многоуровневого графа;
выбора из нескольких квадратов сетки квадратов сети, соответствующих начальному положению и/или конечному положению, если начальное положение и/или конечное положение находятся внутри склада, но за пределами многоуровневого графа;
определения в соответствующих квадратах сетки из выбранных квадратов сетки соединительных маршрутов от начального положения и/или конечного положения до многоуровневого графа;
построения набора решений графов карт маршрутов из многоуровневого графа, причем каждый граф карты маршрутов содержит начальное положение, соединенное окончательным маршрутом с конечным положением, причем окончательный маршрут содержит определенный соединительный маршрут и по меньшей мере часть локальных маршрутов;
выбора центральными процессорами плана скоординированных маршрутов для автоматизированных транспортных средств из набора решений графов карт маршрутов; и
передачи по меньшей мере части плана скоординированных маршрутов каждому из автоматизированных транспортных средств, причем модуль навигации каждого из автоматизированных транспортных средств управляет системой рулевого управления и/или системой движения в соответствии с планом скоординированных маршрутов.
17. Система по п. 16, в которой один или несколько центральных процессоров выполняют команды для:
формирования перечня заблокированных узлов, соответствующих высокоуровневым узлам, соединительным узлам и узлам карты маршрутов, которые недоступны; и
прекращения навигации автоматизированных транспортных средств в части зоны склада, соответствующей заблокированным узлам.
18. Система по п. 16, в которой один или несколько центральных процессоров выполняют команды для формирования модифицированной траектории Дубинса, содержащей соединительные маршруты на концах модифицированной траектории Дубинса, и маршрута с непрерывным изменением кривизны, расположенного между соединительными маршрутами, причем модифицированная траектория Дубинса содержит более крутые повороты по сравнению с маршрутом с непрерывным изменением кривизны, и один или несколько локальных маршрутов одного из графов карты маршрутов содержат модифицированную траекторию Дубинса.
19. Система по п. 16, в которой соединительный маршрут не пересекает начальное положение и конечное положение каждого из графов карт маршрутов для другого автоматизированного транспортного средства.
20. Система по п. 16, в которой в соответствии с планом скоординированных маршрутов требуется, чтобы одно из автоматизированных транспортных средств ожидало, пока другое транспортное средство не пройдет определенное место.
21. Способ планирования скоординированных маршрутов для множества автоматизированных вильчатых подъемников, которые находятся внутри склада и обмениваются информацией с одним или несколькими центральными процессорами, причем способ включает:
получение центральными процессорами задачи в производственных условиях для одного из нескольких автоматизированных вильчатых подъемников, причем соответствующие автоматизированные вильчатые подъемники содержат модуль навигации, систему рулевого управления и систему движения;
обеспечение многоуровневого графа, содержащего высокоуровневые узлы, причем соответствующие многоуровневые узлы соответствуют зоне склада, причем каждый высокоуровневый узел содержит один или несколько соединительных узлов, соответствующих границе зоны склада, один или несколько узлов карты маршрутов, соответствующих внутренней части зоны склада, и один или несколько локальных маршрутов, которые связывают соединительные узлы, узлы карты маршрутов, или их комбинацию;
построение центральными процессорами сетки, связанной со складом, причем сеть разделяет несколько квадратов сетки, и соответствующие квадраты сетки содержат часть склада и часть соответствующего многоуровневого графа;
выбор из нескольких квадратов сетки центральными процессорами квадратов сетки, соответствующих начальному положению и/или конечному положению, если начальное положение и/или конечное положение находятся внутри склада, но за пределами многоуровневого графа;
определение в соответствующих квадратах сетки из выбранных квадратов сетки центральными процессорами соединительных маршрутов от начального положения и/или конечного положения до многоуровневого графа;
построение центральными процессорами набора решений графов карт маршрутов из многоуровневого графа, причем каждый граф карты маршрутов содержит начальное положение, соединенное окончательным маршрутом с конечным положением, причем окончательный маршрут содержит определенный соединительный маршрут и по меньшей мере часть локальных маршрутов;
выбор одним или несколькими центральными процессорами плана скоординированных маршрутов для автоматизированных вильчатых подъемников из набора решений графов карт маршрутов; и
передачу по сети по меньшей мере части плана скоординированных маршрутов каждому из автоматизированных вильчатых подъемников, причем модуль навигации каждого из автоматизированных вильчатых подъемников управляет системой рулевого управления и/или системой движения в соответствии с планом скоординированных маршрутов.
