СПОСОБ ОПТИМИЗАЦИИ РОБОТИЗИРОВАННОЙ СОРТИРОВКИ ТКО ПУТЁМ ДИНАМИЧЕСКОГО ПЛАНИРОВАНИЯ ПЕРЕМЕЩЕНИЙ РОБОТА-СОРТИРОВЩИКА Российский патент 2021 года по МПК B07C5/00 

Изобретение относится к интеллектуальным системам роботизированной сортировки ТКО. Изобретение может быть использовано в энергетике, химической промышленности, металлургии, коммунальном хозяйстве, экологии.

Способ оптимизации роботизированной сортировки позволяет планировать длительную последовательность операций захвата и перемещения роботом-сортировщиком объектов ТКО.

Известен способ перемещения объектов [JPH1119891, 1999-01-26, B25J13/00; B25J13/08; B25J9/10], заключающийся в том, что при выполнении роботом, имеющим ограниченную зону работы, действий с движущимися по конвейерной ленте объектами выполняется регистрация движущихся объектов при помощи «визуального датчика» (камеры), после чего производится вычисление времени, необходимого роботу для выполнения заданного действия над зарегистрированным объектом. В случае, если время выполнения действия роботом превышает время, за которое объект покинет зону действия, запланированное действие отменяется, что позволяет избежать выполнения неэффективных операций роботом.

В отличие от предлагаемого, способ базируется на анализе каждой последующей операции по отдельности, не позволяет выполнять планирование длительной последовательности операций с целью максимизации количества (или суммарной условной стоимости) объектов для всей последовательности. Не решает задачу оптимизации последовательности действий робота, а только предотвращает выполнение операций, не приводящих к необходимому результату (например – захвату объекта на ленте). В предлагаемом способе выполнение неэффективных операций также исключается, однако, кроме этого, использование дерева состояний позволяет рассчитать такую последовательность выполнения операций, при которой количество (или суммарная условная стоимость) пропущенных объектов оказывается минимальным или приближается к минимальному.

Известен способ определения доступных позиций отбора объектов на конвейере [US20120165972, 2012-06-28, G06F7/00]. Способ предполагает планирование перемещения объектов с одного движущегося конвейера на другой при помощи одного или нескольких роботов-манипуляторов. Способ предполагает выполнение последовательности операций таким образом, чтобы не возникало коллизий при захвате объектов на первом конвейере и размещении их на втором конвейере. Оптимизирует последовательность выполнения операций подбора и размещения объектов группой роботов так, чтобы время выполнения следующей операции для каждого робота было минимальным.

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

Известен способ планирования подбора и перемещения объектов на конвейерной ленте группой роботов – манипуляторов [US8417363, 2007-05-17, B07C5/00; B25J9/00; B25J9/16; B65G47/34; B65G47/48; G05B19/18; G05B19/418], который основан на получении информации о расположении объектов датчиком (например, камерой), формировании списка объектов с учётом их положения, и последовательной обработке объектов в списке при помощи нескольких роботов–манипуляторов. В указанном способе последовательно для каждого робота-манипулятора выполняется планирование операции, а затем обновление списка объектов, с указанием, для каких объектов операции уже запланированы, и передача списка следующему роботу-манипулятору. Способ относится к задаче оптимизации планирования подбора и перемещения объектов, являющейся ключевой в процессе сортировки.

В указанном способе не решают задачи оптимизации процесса сортировки в случае, когда количество поступающих объектов превышает количество объектов, которое может обработать манипулятор (или группа манипуляторов).

Из уровня техники известны способы выбора оптимального решения на основе использования алгоритма обхода дерева решений.

Известный метод полного перебора возможных решений (то есть последовательностей сортировки объектов) с целью определения оптимального требует выполнить перебор 2N возможных решений. Этот способ гарантирует оптимальное решение, но требует моделирования большого количество состояний (N×2N-1). Учитывая, что такую процедуру необходимо выполнять постоянно при появлении новых объектов на ленте, такой способ является чрезмерно затратным и, по сути, не реализуемым с точки зрения вычислительных ресурсов.

Задача поиска оптимального хода в дереве состояний встречается в пошаговых играх, таких как шахматы. Ключевым фактором при решении такой задачи является наличие/отсутствие функции для оценивания отдельного состояния. В случае отсутствия такой функции, единственный способ оценить состояния — это продолжить моделирование до конечного состояния (состояния, из которого нет хода).

Известен алгоритм Monte Carlo tree search поиска оптимального хода в дереве состояний

[https://www.worldscientific.com/doi/abs/10.1142/S1793005708001094]. Наличие эвристической функции позволяет направить поиск на более перспективные ветви.

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

Известные способы выбора оптимального решения на основе использования алгоритма обхода дерева решений не используют для оптимизации роботизированной сортировки ТКО.

В качестве прототипа выбран способ оптимизации сортировки объектов, находящихся на движущейся конвейерной ленте [Mattone R, Divona M, WolfA. 2000. Sorting of items on a moving convey or belt. Part 2: performance evaluation and optimization of pick-and-place operations // Robotics and Computer-Integrated Manufacturing 16 (2-3) pp. 81-90]. В статье описаны четыре метода планирования подбора объектов на конвейерной ленте после определения положения объектов на ленте и вычисления необходимого перемещения манипулятора робота, и времени, затрачиваемого на такое перемещение, для подбора объектов.

1. Метод FIFO (first in first out): объекты подбираются последовательно в том же порядке, как поступают на ленту.

2. Метод SPT (shortest processing time): на каждом ходе вычисляется объект, для которого время обработки (например – подбора и транспортировки) будет минимальным. На каждом ходе выполняется подбор объекта, для которого при текущем расположении объектов на ленте время обработки минимально.

3. Improved FIFO (усовершенствованный FIFO): на каждом ходе выполняется подбор объекта, находящегося ближе всего к точке Y_opt , в которой время, затрачиваемое на захват предмета в этой точке минимально, и ещё не прошедшего эту точку.

4. Improved SPT (усовершенствованный SPT): в этом методе на каждом ходе выделяется область в окрестности точки Y_opt, в которой время, затрачиваемое на захват предмета в этой точке минимально. После этого рассматриваются объекты, находящиеся на ленте конвейера. Ширина окрестности выбирается равной L=T_m⋅v, где T_m – максимально допустимое время на выполнение операции, а v – скорость движения ленты конвейера. Формулируется правило, согласно которому, если объект присутствует в окрестности точки Y_opt, то подбирается. Если же все объекты на ленте либо ещё не достигли этой окрестности, либо уже покинули её, то выполняется подбор ближайшего объекта, уже покинувшего окрестность точки Y_opt. В статье демонстрируется, что метод планирования Improved SPT является наиболее эффективным из рассмотренных, с точки зрения скорости сбора объектов, или, что эквивалентно, позволяет собрать наибольшее количество объектов за заданное время.

Недостатки данного способа

В случае, если количество объектов, поступающих по конвейеру, превышает количество объектов, которые может обработать робот, способ планирования не гарантирует, что для текущего состояния (расположения объектов на ленте) будет собрано максимально возможное количество объектов. Способ не предполагает учёта “стоимости” объектов, то есть не эффективен в случае, если по конвейеру поступают объекты различного типа, и обработка объектов одного типа является более приоритетной, чем обработка объектов другого типа. В отличие от предложенного способа, метод Improved SPT не обладает свойством адаптивности, то есть не позволяет на основе накопленной статистики выработать наиболее выгодную стратегию пропуска и подбора объектов в условиях, когда количество объектов, поступающих по конвейеру, превышает количество объектов, которые может обработать робот.

Задача – повышение производительности систем роботизированной сортировки ТКО в случаях, когда объем входящего потока сортируемых объектов превышает максимальную производительность робота-сортировщика, путём снижения среднего времени, затрачиваемого на сортировку одного объекта, и, соответственно, увеличения количества сортируемых объектов в единицу времени, а также уменьшения количества «пропусков».

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

Согласно изобретению, способ оптимизации роботизированной сортировки ТКО путём динамического планирования перемещений робота-сортировщика включает:

1) регистрацию движущихся на конвейерной ленте объектов при помощи системы машинного зрения, включающей видеокамеру, одну или несколько, и набор сенсоров,

2) регистрацию скорости конвейерной ленты датчиком скорости,

3) непрерывную передачу по локальной линии связи данных об объектах, находящихся на конвейерной ленте, и скорости конвейерной ленты в вычислительный блок, состоящий из вычислительного блока системы машинного зрения и вычислительного блока планирования перемещений робота-сортировщика,

4) планирование последовательностей сортировки объектов ТКО на ленте,

5) выбор наилучшей из последовательностей,

6) принятие решения о передаче роботу команды о выборе следующего объекта.

Согласно изобретению способ включает выполнение вычислительным блоком системы машинного зрения:

– идентификации изображений объектов ТКО,

– вычисления координат, типа (совокупности признаков: материала, цвета и т.п.) объектов, условной стоимости объектов,

– передачи вычисленных данных в вычислительный блок планирования перемещений робота-сортировщика.

Согласно изобретению, способ включает выполнение вычислительным блоком планирования перемещений робота-сортировщика (одного или нескольких):

– планирования последовательностей сортировки объектов и выбор наилучшей из последовательностей,

– передачи роботу-сортировщику команды на захват и перемещение следующего объекта ТКО в положение с заданными координатами.

Согласно изобретению, планирование последовательностей сортировки объектов на ленте и выбор наилучшей из последовательностей осуществляют обходом дерева состояний, в каждой вершине (узле) которого хранится функция потерь loss (ν, t), где ν – потерянная стоимость, t – отсчитываемое от начала работы алгоритма время исполнения хода, начиная с корневой вершины дерева.

Согласно изобретению, обход дерева состояний осуществляют путём выполнения итераций, каждая из которых состоит из следующих шагов:

1) перемещение по дереву состояний по траектории наилучшего решения (ТНР) (Selection), пока эти вершины содержатся в дереве, причём, если из конечной вершины по ТНР нет возможных ходов, то выполнение итераций прекращается, если из конечной вершины по ТНР есть возможные ходы, то выполняется оценка снизу нового значения loss для одного из возможных ходов, при этом, если новое значение loss меньше, чем значения loss у существующих вершин, то выполняют переход к шагу 2, т.е. выполняют моделирование нового состояния, если новое значение loss больше, чем значения loss у существующих вершин, то выполняют переход к существующей вершине с наименьшим значением loss и моделируют новое состояние, т.е. выполняют переход к шагу 2,

2) моделирование нового состояния (Simulation) на основе известной скорости движения робота, конвейерной ленты, а также координат расположения объектов на конвейерной ленте и координат точек, в которые необходимо транспортировать объекты ТКО,

3) добавление к дереву новой вершины (Expansion),

4) обновление информации в вершинах посещённого пути путём обратного распространения (Backpropagation), начиная с конечной вершины посещённого пути, к корню дерева, причём

если все возможные ходы из этой вершины были смоделированы, то обновление информации в вершинах посещённого пути осуществляют путём присваивания всем вершинам посещённого пути значения loss, равного наименьшему значению loss среди потомков этой вершины,

если из конечной вершины по ТНР есть ходы, которые ещё не были смоделированы, то при обновлении значение loss этой вершины сохраняется,

5) возврат к шагу 1.

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

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

Согласно изобретению, при сравнении loss используют веса для времени ξ/t, где ξ – суммарная собранная за время t стоимость. Таким образом, при сравнении вершин A и B используется функция потерь используется v+(t-t_с)⋅(ξ/t_с), где t_с – время начала хода или, что эквивалентно – время исполнения предыдущего хода, отсчитываемое от начала работы алгоритма, ξ - суммарная собранная за время t_с стоимость.

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

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

Согласно изобретению, моделирование завершается, когда текущее лучшее решение смоделировано до состояния, из которого нет ходов.

Согласно изобретению, принятие решения о передаче роботу команды о выборе следующего объекта осуществляют по запросу от контроллера робота, по завершении текущего хода.

Согласно изобретению, для принятия решения о передаче роботу команды о выборе следующего объекта, в случае, если к моменту поступления запроса от контроллера робота (моменту завершения текущего хода) обход дерева состояний завершён, то есть текущее лучшее решение смоделировано до состояния, из которого нет ходов, выбирают финальный ход текущего наилучшего решения.

Согласно изобретению, для принятия решения о передаче роботу команды о выборе следующего объекта, в случае, если к моменту поступления запроса от контроллера робота (моменту завершения текущего хода) обход дерева состояний не завершён выбирают решение, которое содержит наибольшее поддерево.

Выполнение итераций прекращают, если:

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

2) робот завершил текущий ход (завершил перемещение объекта), и ему требуется подать команду для следующего хода, при этом из конечной вершины по траектории наилучшего решения ещё есть возможные ходы. В этом случае оптимальное решение достоверно неизвестно, однако имеется траектория наилучшего решения на несколько ходов вперёд. В этом случае следующим выбирается ход, который наибольшее число раз оказывался на траектории наилучшего решения. То, что ход оказывался на траектории наилучшего решения наибольшее число раз, означает, что в этом направлении дерево смоделировано на большее количество ходов вперёд, и что Loss оказывается меньшим для большей глубины дерева.

Способ позволяет задавать приоритет сортировки, назначая объектам условную стоимость. При этом пропуск объектов с высокой стоимостью будет менее предпочтителен, чем пропуск объектов с низкой стоимостью. Различия в задаваемой стоимости позволяют регулировать приоритет сортировки.

Способ осуществляют посредством системы динамического планирования перемещений робота сортировщика (ДППРС).

Система динамического планирования перемещений робота сортировщика включает:

1) систему машинного зрения, включающую камеру, одну или более, и сенсор, либо набор сенсоров,

2) датчик скорости конвейерной ленты,

3) робота-сортировщика (одного или более),

4) вычислительную систему, включающую процессор, один или более; модуль памяти, один или более; запоминающее устройство, одно или более; и команды в машинном коде, хранящиеся в запоминающем устройстве, одном или более, в виде вычислительного блока системы машинного зрения и вычислительного блока планирования перемещений робота, которые при выполнении процессором, одним или несколькими, управляют системой ДППРС.

Вычислительный блок системы машинного зрения:

• идентифицирует изображения ТКО,

• вычисляет координаты, тип (совокупность признаков: материал, цвет и т.п.) объектов, условную стоимость объектов,

• передаёт вычисленные данные в вычислительный блок планирования перемещений робота.

Вычислительный блок планирования перемещений робота:

• осуществляет планирование последовательностей сортировки объектов ТКО и выбор наилучшей из последовательностей,

• передаёт команды роботу о выборе следующего объекта.

Способ заключается в следующем.

С помощью системы машинного зрения фиксируют и передают в вычислительный блок машинного зрения информацию об объектах ТКО, находящихся на конвейерной ленте, для определения их расположения и характеристик: координат, типа (совокупности признаков: материал, цвет и т.п.), условной стоимости.

Также в вычислительный блок непрерывно поступает информация от датчика скорости движения конвейерной ленты.

Новые объекты ТКО появляются в начале рабочего участка конвейерной ленты случайным образом. Рядом с конвейерной лентой находятся корзины для каждого типа объектов. Захват может двигаться над конвейером и корзинами, а также может брать и отпускать предметы. Все корзины находятся в зоне досягаемости захвата, однако захват может взять предмет с конвейера, лишь начиная с момента, когда объект достигает рабочей зоны робота-сортировщика.

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

Для вычислений последовательностей сортировки объектов с целью определения оптимального решения в предлагаемом способе используют стратегию (алгоритм) на основе обхода дерева состояний, где корень – это начальное состояние, узлы – это моделируемые состояния, а рёбра, соединяющие узлы – это ходы.

Здесь: алгоритм планирования – это последовательность вычислений, позволяющая определить следующий ход; моделирование – один из шагов работы алгоритма. При моделировании на основе известной скорости движения конвейерной ленты, робота, а также координат точек, в которых надо осуществить подбор и в которые надо перенести объект, вычисляют в каком состоянии окажется система после выполнения хода.

Состояние системы характеризуется совокупностью информации обо всех предметах на конвейере и информации о захвате робота в какой-то момент времени, то есть – это данные:

– текущее положение захвата (набор трёхмерных координат);

– текущее время;

– стоимость, тип, индекс (порядковый номер) и координаты объектов.

Задача поиска оптимального хода в дереве состояний встречается в пошаговых играх, таких как шахматы. Ключевым фактором при решении такой задачи является наличие/отсутствие функции для оценивания отдельного состояния. В случае отсутствия такой функции, единственный способ оценить состояния – это продолжить моделирование до конечного состояния (состояния, из которого нет хода).

Примером такой стратегии является Monte Carlo tree search (https://www.worldscientific.com/doi/abs/10.1142/S1793005708001094). Наличие эвристической функции позволяет направить поиск на более перспективные ветви.

Если целевой параметр, который мы пытаемся максимизировать или минимизировать, не возрастает или не убывает, то возможно производить поиск с отсечениями ветвей.

В данной задаче таким целевым параметром является потерянная стоимость. Суммарная стоимость предметов, которые не были собраны в зоне захвата, не может уменьшиться. Вторичным параметром служит время: в случае равенства упущенной стоимости следует выбирать решение, которое заканчивает работу раньше. Время так же является не убывающим параметром, который следует минимизировать.

Таким образом, базовая стратегия поиска решения состоит из итеративного расширения дерева состояний.

Итерация состоит из 4 шагов: следуем лучшему решению (по траектории наилучшего решения), пока эти вершины содержатся в дереве (Selection), затем моделируем новое состояние (Simulation) и добавляем новую вершину (Expansion), и в завершение обновляем информацию в вершинах посещённого пути (Backpropagation). Эта последовательность операций выбрана по аналогии со стратегией Monte Carlo tree search.

Для поиска лучшего текущего решения без обхода всех концевых узлов в дереве, в каждом узле хранится функция loss (ν, t), где ν – потерянная стоимость, t – время исполнения, которое отсчитываются от начала работы алгоритма планирования.

Если из вершины дерева состояний есть ходы, которые ещё не моделировались, то значения loss присваивают из состояния этой вершины.

Но если все ходы из данной вершины были смоделированы, то loss вершины присваивается минимальному loss среди потомков вершины.

При таком подходе значение loss никогда не будет уменьшаться.

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

Если ход возможен, в дерево добавляется новая вершина, после чего обновляется loss у всех предков новой вершины.

Алгоритм завершается, когда текущее лучшее решение смоделировано до состояния, из которого нет ходов. Это означает, что такое решение собрало все известные предметы, кроме тех, что пропустило, но при этом суммарная стоимость пропущенных предметов минимальна, а значит, суммарная стоимость собранных предметов максимальна.

Появление новых предметов на ленте может изменить текущее решение, поэтому в случае появления новых предметов следует продолжить итерации.

Когда наступает время выбора следующего хода, возможны две ситуации: алгоритм либо завершен, либо не завершён.

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

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

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

В случае, когда алгоритм завершён, можно брать первый ход лучшего решения (что гарантирует лучшее решение, если на конвейере больше не появится новых предметов) либо, следовать тому же принципу, как когда алгоритм не завершён, что гарантирует хорошие результаты независимо от того, какие предметы появятся на конвейере в будущем. После выбора хода, вершина, в которую этот ход привёл, становится новым корнем, а остальная часть дерева отбрасывается. Из списка объектов удаляются элементы, которые предшествовали взятому объекту. Время и потерянная стоимость продолжает отсчитываться от начала работы алгоритма, что позволяет использовать выбранное поддерево без изменений.

Назначая объектам условную стоимость, способ позволяет задавать приоритет сортировки. При этом пропуск объектов с высокой стоимостью будет менее предпочтителен, чем пропуск объектов с низкой стоимостью. Различия в задаваемой стоимости позволяют регулировать приоритет сортировки.

Оптимизация стратегии

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

Именно моделирование нового состояния занимает большую часть вычислительного времени, поэтому алгоритм дополняется правилами для отсечения заведомо плохих ходов.

Поскольку в сформулированной модели, ход к i-ому предмету заведомо приведёт к увеличению loss на стоимость всех предметов между последним собранным и i-ым, ещё до моделирования нового состояния можно оценить новый loss снизу и тем самым проверить, требуется ли создание новой вершины.

Это позволяет выполнять моделирование состояния и создавать новую вершину только в случае, когда оценка для loss меньше, чем у существующих вершин.

На практике такая оптимизация оказывается очень полезной, в особенности при большом количестве объектов на конвейере, потому что решения, в которых алгоритм пропускает большое количество предметов подряд (то есть захват ждёт далёкого предмета), уступают решениям, в которых захват не простаивает в течение длительного времени.

Другая особенность алгоритма, связана с тем, что информация об объектах известна только на несколько секунд вперёд, а именно – на время, необходимое предметам для перемещения от области детектирования до рабочей зоны робота.

Как было сказано ранее, базовый алгоритм минимизирует loss, который состоит из двух частей: суммарная стоимость не собранных предметов и момент времени окончания последнего перемещения.

Сравнение различных loss происходит в первую очередь по суммарной пропущенной стоимости и лишь в случае их равенства, сравниваются моменты времени.

Для того чтобы проиллюстрировать несовершенство такого сравнения представим следующую ситуацию: в какой-то момент есть два достаточно хороших решения и алгоритм успеет найти оба. В первом случае будет собрано на 1 больше по суммарной стоимости, а во втором, захват освободится на секунду раньше. В случае если новые предметы не появятся в течение некоторого времени, стоит следовать первому решению. А если предметы появятся, то за эту дополнительную секунду существует вероятность захватить дополнительный объект, стоимостью значительно выше 1, и в этом случае более выгодно следовать второму решению.

Из этого примера видно, что нельзя говорить об оптимальном решении, не имея информации о вероятностях появления новых объектов. Поскольку такая информация недоступна, более корректно сравнивать loss с учётом сразу двух компонент, где пропущенная стоимость и время окончания имеют некоторые веса. И хотя нельзя предсказать, сколько стоимости принесёт каждая «сэкономленная» секунда, можно опереться на прошлую статистику. Можно запоминать собранную стоимость v на протяжении последних t секунд, в предположении, что статистика появления объектов разной стоимости на конвейере существенно не изменялась на протяжении этого времени. Полученный параметр ξ/t можно использовать как вес для времени при сравнении loss.

Вернёмся к примеру с двумя решениями (случаю, когда в одном из двух решений будет собрано на 1 больше по суммарной стоимости, а во втором, захват освободится на секунду раньше): с использованием предложенного правила учёта затрат времени, если ξ/t < 1, то алгоритм выберет первое решение, иначе - второе решение. Таким образом, алгоритм приобретает элемент адаптивности, настраиваясь на фракционный состав и скорость поступления потока ТБО.

Оптимизация суммарной собранной стоимости (или, что эквивалентно, минимизация потерянной стоимости) достигается за счёт построения дерева решений на несколько ходов вперёд, что снижает вероятность последовательности действий, при которой максимизация “выгоды” от ближайшего хода (выраженной в условной стоимости объекта, затрачиваемом на ход времени, либо комбинации этих параметров) приведёт к большей потерянной стоимости в следующие несколько ходов.

Оптимизация вычислительных ресурсов, необходимых на выполнение вычислений, достигается за счёт представления совокупных возможных последовательностей перемещения (решений) в виде дерева состояний и обхода дерева состояний с использованием описанной стратегии (алгоритма). В этом случае исключается необходимость вычисления результатов заведомо «невыгодных» решений. Дополнительно необходимость вычисления результатов заведомо «невыгодных» решений исключается за счёт использования дополнительного условия оценки потерянной стоимости снизу на шаге 1.

Использование веса ξ/t в качестве веса для времени при сравнении loss, где ξ– собранная за время t стоимость. Поскольку значение функции ξ/t зависит от статистики добавления объектов на ленту, использование её в качестве адаптивного веса позволяет методу планирования адаптироваться к статистике загрузки объектов на ленту и учитывать вероятность дополнительной потери стоимости за счёт появления в будущем новых (ещё не зарегистрированных системой машинного зрения) объектов.

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

Преимущество разработанной стратегии при использовании для планирования перемещений манипулятора дельта-робота: удобство настройки приоритета при необходимости отбора конкретных фракций путём назначения им различной стоимости.

Для оценки эффективности работы была проведена симуляция с использованием специально разработанного программного симулятора работы робота на конвейерной ленте.

В симуляции на конвейер подавались предметы четырёх типов. Их тип и начальная координата выбиралась случайно и равновероятно. Для каждого типа объектов задавали координаты их сбора.

Стоимость предметов задавали независимо от их типа, выбирали случайно и равновероятно из следующих вариантов: 5, 7, 10, 14, 20. Было проведено сравнение работы описанной стратегии оптимизации с методом, использующим более простую стратегию планирования операций сортировки. По результатам симуляции, предложенный метод позволил собрать предметов на 11,5 % больше по суммарной стоимости и на 9,5 % больше предметов количественно, чем более простое решение.

На фиг. 1 – пример дерева состояний.

В корне дерева производится захват первого из трёх предметов на конвейере. Различные состояния системы изображены прямоугольниками. Круги внутри состояний обозначают предметы, чей статут показан цветом: зелёные – собранные, оранжевые – пропущенные, синие – ещё не посещённые. Чёрная стрелка указывает на предмет, который захватывается в данный момент. Ходы изображены овалами, в которых написана следующая цель захвата. Стрелка от хода указывает на состояние, в которое приводит этот ход.

Новизна предлагаемого способа заключается в следующем.

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

2. Способ позволяет учитывать «условную стоимость» объектов. Это позволяет эффективно применять его в случае, если по конвейеру поступают объекты различного типа, и обработка объектов одного типа является более приоритетной, чем обработка объектов другого типа.

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

Изобретение относится к интеллектуальным системам роботизированной сортировки ТКО. Изобретение может быть использовано в энергетике, химической промышленности, металлургии, коммунальном хозяйстве, экологии. Задача – повышение производительности систем роботизированной сортировки ТКО в случаях, когда объем входящего потока сортируемых объектов превышает максимальную производительность робота-сортировщика, путём снижения среднего времени, затрачиваемого на сортировку одного объекта, и, соответственно, увеличения количества сортируемых объектов в единицу времени, а также уменьшения количества «пропусков». Задачу решают способом, позволяющим на основе накопленной статистики выработать наиболее выгодную стратегию пропуска и подбора объектов в условиях, когда количество объектов, поступающих по конвейеру, превышает количество объектов, которые может обработать робот. 9 з.п. ф-лы, 1 ил.

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

выполнение вычислительным блоком системы машинного зрения:

• идентификации изображений объектов ТКО,

• вычисления координат, типа объектов, условной стоимости объектов,

• передачи вычисленных данных в вычислительный блок планирования перемещений робота-сортировщика,

выполнение вычислительным блоком планирования перемещений робота-сортировщика:

• планирования последовательностей сортировки объектов и выбор наилучшей из последовательностей,

• передачи роботу-сортировщику команды на захват и перемещение следующего объекта ТКО в положение с заданными координатами,

причём планирование последовательностей сортировки объектов на ленте и выбор наилучшей из последовательностей осуществляют обходом дерева состояний, в каждой вершине которого хранится функция потерь loss (ν, t), где ν – потерянная стоимость, t – отсчитываемое от начала работы алгоритма время исполнения, начиная с корневой вершины дерева,

а обход дерева состояний осуществляют путём выполнения итераций, каждая из которых состоит из следующих шагов:

1) перемещение по дереву состояний по траектории наилучшего решения (ТНР) (Selection), пока эти вершины содержатся в дереве, причём, если из конечной вершины по ТНР нет возможных ходов, то выполнение итераций прекращается, если из конечной вершины по ТНР есть возможные ходы, то выполняется оценка снизу нового значения loss для одного из возможных ходов, при этом, если новое значение loss меньше, чем значения loss у существующих вершин, то выполняют переход к шагу 2, если новое значение loss больше, чем значения loss у существующих вершин, то выполняют переход к существующей вершине с наименьшим значением loss и затем переход к шагу 2,

2) моделирование нового состояния (Simulation) на основе известной скорости движения робота, конвейерной ленты, а также координат расположения объектов на конвейерной ленте и координат точек, в которые необходимо транспортировать объекты ТКО,

3) добавление к дереву новой вершины (Expansion),

4) обновление информации в вершинах посещённого пути путём обратного распространения (Backpropagation), начиная с конечной вершины посещённого пути, к корню дерева, причём:

если все возможные ходы из этой вершины были смоделированы, то обновление информации в вершинах посещённого пути осуществляют путём присваивания всем вершинам посещённого пути значения loss, равного наименьшему значению loss среди потомков этой вершины,

если из конечной вершины по ТНР есть ходы, которые ещё не были смоделированы, то при обновлении значение loss этой вершины сохраняется, 5) возврат к шагу 1.

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

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

4. Способ по п.1, отличающийся тем, что при сравнении loss используют веса для времени ξ/t, где ξ – суммарная собранная за время t стоимость.

5. Способ по п.1, отличающийся тем, что при сравнении вершин используют функцию потерь v+(t-t_с)⋅(ξ/t_с), где t_с – время начала хода, отсчитываемое от начала работы алгоритма, ξ – суммарная собранная за время t_с стоимость.

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

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

8. Способ по п.1, отличающийся тем, что моделирование завершается, когда текущее лучшее решение смоделировано до состояния, из которого нет ходов.

9. Способ по п.1, отличающийся тем, что принятие решения о передаче роботу команды о выборе следующего объекта осуществляют по запросу от контроллера робота, по завершении текущего хода.

10. Способ по п.1, отличающийся тем, что для принятия решения о передаче роботу команды о выборе следующего объекта, в случае, если к моменту поступления запроса от контроллера робота обход дерева состояний завершён, то есть текущее лучшее решение смоделировано до состояния, из которого нет ходов, выбирают финальный ход текущего наилучшего решения, если обход дерева состояний не завершён, выбирают решение, которое содержит наибольшее поддерево.