Comments 39
-18
Может я и ошибаюсь, но к конечным автоматам это не имеет отношения. Нет т.е. конечно можно представить склад с ячейками как систему в определенном состоянии, а перемещение ячеек, как переход в другое состояние. Но на первый взгляд это транспортная задача, с известными методами решения. А у вас получился какой-то набор эвристик. Еще и Oracle… За ним же следить надо.
+5
Конечный автомат здесь не ячейки, а состояния роботов. Хотя бы вот такой:
— переместиться к нужной ячейке (по пути прогнав другого робота, если мешает),
— загрузить контейнер,
— переместиться к конечной ячейке (по пути прогнав другого робота, если мешает),
— выгрузить контейнер.
И теоретически на любом этапе может быть ошибка робота или ошибка связи, которую тоже нужно обработать, не забыв, с чего мы начали. Количество вещей, о которых «надо было помнить» при принятии решений столь велико, что они сформировали ничего себе так базу данных (дамп весит 10 МБ). Кроме того, программа может подвиснуть (да хотя бы в процессе отладки), а текущее состояние склада и роботов нужно помнить. Так что Oracle тут в прямом смысле оказался палочкой выручалочкой.
Методы транспортной задачи (старый добрый коммивояжер) с наскока использовать не получилось. Вы считаете, имеет смысл в ней покопаться, чтоб найти матмодель? Не могли бы еще подбросить пару ключевых слов, по которым искать информацию?
— переместиться к нужной ячейке (по пути прогнав другого робота, если мешает),
— загрузить контейнер,
— переместиться к конечной ячейке (по пути прогнав другого робота, если мешает),
— выгрузить контейнер.
И теоретически на любом этапе может быть ошибка робота или ошибка связи, которую тоже нужно обработать, не забыв, с чего мы начали. Количество вещей, о которых «надо было помнить» при принятии решений столь велико, что они сформировали ничего себе так базу данных (дамп весит 10 МБ). Кроме того, программа может подвиснуть (да хотя бы в процессе отладки), а текущее состояние склада и роботов нужно помнить. Так что Oracle тут в прямом смысле оказался палочкой выручалочкой.
Методы транспортной задачи (старый добрый коммивояжер) с наскока использовать не получилось. Вы считаете, имеет смысл в ней покопаться, чтоб найти матмодель? Не могли бы еще подбросить пару ключевых слов, по которым искать информацию?
0
У вас нет возможности восстановить состояние системы не прибегая к базе? Ну т.е. у вас нет возможности спросить у оборудования, где находится робот и есть ли на нем контейнер? Ну еще где находится, какой контейнер я еще поверю, что информация может быть только в базе. Но роботы то должны отслеживаться? По контейнерам информация должна быть в системе более высокого уровня. Не той которая управляет роботами. И это простая таблица — никаких состояний.
Ключевые слова очевидны - транспортная задача. Я не уверен на 100%, что это оно. Но уверен что эта задача уже кем то решалась и надо искать подходящую мат. модель.
Мне кажется вы смешали в кучу несколько задач. Вам надо их разделить и решать по-отдельности.
Я вижу такие:
1. Управление отдельным роботом — да автомат с состояниями, едем, стоим, переместились на ячейку N, заклинило в ячейке N.
2. Граф состояния склада — узлы — ячейки, или координаты — скорее всего не во всех координатах есть ячейки. Связи это возможность перемещения робота из одной координаты в другую. Граф перестраивается при поступлении новых данных. Например если робот остановился с ошибкой — граф перестраивается. В граф можно добавить узлы не связанные с координатами, а например узел, который отвечает за уборку мешающего робота.
3. Решение задачи оптимизации перемещения робота по графу. Робот перемещается по оптимальному пути, после его вычисления. Любое событие повлиявшее на граф и пересекающееся с узлами через которые проходит путь робота приводит к пересчету пути на новом графе. Впрочем условие пересечения это уже преждевременная оптимизация.
Ключевые слова очевидны - транспортная задача. Я не уверен на 100%, что это оно. Но уверен что эта задача уже кем то решалась и надо искать подходящую мат. модель.
Мне кажется вы смешали в кучу несколько задач. Вам надо их разделить и решать по-отдельности.
Я вижу такие:
1. Управление отдельным роботом — да автомат с состояниями, едем, стоим, переместились на ячейку N, заклинило в ячейке N.
2. Граф состояния склада — узлы — ячейки, или координаты — скорее всего не во всех координатах есть ячейки. Связи это возможность перемещения робота из одной координаты в другую. Граф перестраивается при поступлении новых данных. Например если робот остановился с ошибкой — граф перестраивается. В граф можно добавить узлы не связанные с координатами, а например узел, который отвечает за уборку мешающего робота.
3. Решение задачи оптимизации перемещения робота по графу. Робот перемещается по оптимальному пути, после его вычисления. Любое событие повлиявшее на граф и пересекающееся с узлами через которые проходит путь робота приводит к пересчету пути на новом графе. Впрочем условие пересечения это уже преждевременная оптимизация.
+1
Если произойдет вылет программы во время работы АСК, то у робота можно узнать его местоположение и даже какую команду (низкоуровневую) он выполняет. И все. Относительно контейнера можно просто узнать, есть ли на платформе он или нет (код его выяснить нет возможности). То есть где-то должна сохраняться информация как минимум о нескольких вещах:
— что мы везем или собираемся везти (код контейнера),
— какая цель движения робота внутри подсклада (источник и приемник),
— блокировки участка пути — что заблокировано,
— заявки на блокировки — что робот хочет заблокировать, но не может,
— есть ли и какая цель перемещения контейнеров между подскладами (подскладов может быть N штук).
Транспортная задача — кажется вспомнил — это вроде как раздел математики. На симплекс-методе у нас всю группу в институте завалили. Очень уж заумная вещь. Видимо придется разбираться. Эх, математика бы найти!
— что мы везем или собираемся везти (код контейнера),
— какая цель движения робота внутри подсклада (источник и приемник),
— блокировки участка пути — что заблокировано,
— заявки на блокировки — что робот хочет заблокировать, но не может,
— есть ли и какая цель перемещения контейнеров между подскладами (подскладов может быть N штук).
Транспортная задача — кажется вспомнил — это вроде как раздел математики. На симплекс-методе у нас всю группу в институте завалили. Очень уж заумная вещь. Видимо придется разбираться. Эх, математика бы найти!
0
Я уверен, что в базе имеет смысл хранить только, где какой контейнер находится (включая платформы роботов) — 1я таблица. Задачи на перемещение — 2 я таблица. Ну может конечно еще что то, но к управлению роботоми это не будет иметь отношения.
Не очень понятно что такое подсклады. Нельзя все логически объединить в одну систему? Или между подскладами ездят не роботы?
Блокировки пути — я не очень понимаю что это. Если это относится только к системе с роботами, то это должна быть какая то отдельная база, а может быть просто файл на диске?
Если это просто другой робот блокирует путь, то естественно это можно всегда высчитать по данным от оборудования. Зачем это хранить в базе?
Естественно у вас должна как-то хранится структура самого склада. Ну хорошо храните ее в базе. Но даже если ее хранить в базе, то система управления роботами может построить базовый граф на ее основе в удобном для работы формате и хранить его копию на диске.
Не очень понятно что такое подсклады. Нельзя все логически объединить в одну систему? Или между подскладами ездят не роботы?
Блокировки пути — я не очень понимаю что это. Если это относится только к системе с роботами, то это должна быть какая то отдельная база, а может быть просто файл на диске?
Если это просто другой робот блокирует путь, то естественно это можно всегда высчитать по данным от оборудования. Зачем это хранить в базе?
Естественно у вас должна как-то хранится структура самого склада. Ну хорошо храните ее в базе. Но даже если ее хранить в базе, то система управления роботами может построить базовый граф на ее основе в удобном для работы формате и хранить его копию на диске.
0
Сейчас в базе хранится (не считая информации по товару, контейнерам и команд от внешней WMS системы заказчика):
— информация о ячейках,
— информация о блокировке ячеек различными командами,
— информация об автоблокировке ошибочных ячеек,
— команды сервера штабелеров от внешней системы,
— команды уровня подсклада,
— команды, напрямую данные роботам (нужны еще и для статистики),
— логи,
— возникающие проблемы и выбранные пользователем методы их устранения,
— информация по подскладам,
— общая информация (настройки) по системе,
— настройки роботов и информация об их текущем состоянии,
— информация о стеллажах,
— информация об участках рельсового пути,
— информация о блокировке участков пути.
Наверное, можно было бы хранить все это в xml-файлах. Но зачем, если Oracle XE бесплатный и есть опыт работы с ним?
Подсклады — это непересекающиеся участки пути (рельсов), которые могут быть как закольцованы, так и нет. На верхнем рисунке АСК состоит из двух подскладов — левый дугообразный некольцевой (на нем один робот), правый — закольцованный (на нем два робота). Между подскладами никто не ездит, контейнеры передаются через транзитные ячейки. Логически все объединено в одну систему, но чтоб она работала как одна система, пришлось на уровне программной разработки вводить кучу уровней, и каждый отлаживать отдельно, иначе сложность задачи превышает способности программистов.
Путь — это ресурс, который можно занять только монопольно. По мере прохождения робота по пути, ресурс должен освобождаться, и давать возможность другому роботу его занимать. Зачем отдельная база? Логичней просто отдельный уровень одной базы SQL-сервера.
Блокировки работают через диспетчер блокировок — семафоры там всякие — так по данным от оборудования это не получить. Нужен именно диспетчер со своей очередью запросов на требуемый ресурс.
Какая разница — файл на диске, или таблица в SQL? Но с таблицей SQL очень удобно работать, не надо париться про ее сохранение, решение проблем двойного доступа и прочее.
— информация о ячейках,
— информация о блокировке ячеек различными командами,
— информация об автоблокировке ошибочных ячеек,
— команды сервера штабелеров от внешней системы,
— команды уровня подсклада,
— команды, напрямую данные роботам (нужны еще и для статистики),
— логи,
— возникающие проблемы и выбранные пользователем методы их устранения,
— информация по подскладам,
— общая информация (настройки) по системе,
— настройки роботов и информация об их текущем состоянии,
— информация о стеллажах,
— информация об участках рельсового пути,
— информация о блокировке участков пути.
Наверное, можно было бы хранить все это в xml-файлах. Но зачем, если Oracle XE бесплатный и есть опыт работы с ним?
Подсклады — это непересекающиеся участки пути (рельсов), которые могут быть как закольцованы, так и нет. На верхнем рисунке АСК состоит из двух подскладов — левый дугообразный некольцевой (на нем один робот), правый — закольцованный (на нем два робота). Между подскладами никто не ездит, контейнеры передаются через транзитные ячейки. Логически все объединено в одну систему, но чтоб она работала как одна система, пришлось на уровне программной разработки вводить кучу уровней, и каждый отлаживать отдельно, иначе сложность задачи превышает способности программистов.
Путь — это ресурс, который можно занять только монопольно. По мере прохождения робота по пути, ресурс должен освобождаться, и давать возможность другому роботу его занимать. Зачем отдельная база? Логичней просто отдельный уровень одной базы SQL-сервера.
Блокировки работают через диспетчер блокировок — семафоры там всякие — так по данным от оборудования это не получить. Нужен именно диспетчер со своей очередью запросов на требуемый ресурс.
Какая разница — файл на диске, или таблица в SQL? Но с таблицей SQL очень удобно работать, не надо париться про ее сохранение, решение проблем двойного доступа и прочее.
+1
А что из этого занимает 10 мегабайт? Логи, небось?..
0
Задачу коммивояджера сейчас решают с помощью линейного программирования. При этом решение задачи линейного программирования (симплекс-метод) является лишь элементарным шагом алгоритма ;).
Возможно вашу задачу можно решать схожими методами, но она явно сложнее и я сходу не вижу как это можно сделать. У меня знакомый этим занимается, но я пока не нашел сил разобраться в этой области математики.
Возможно вашу задачу можно решать схожими методами, но она явно сложнее и я сходу не вижу как это можно сделать. У меня знакомый этим занимается, но я пока не нашел сил разобраться в этой области математики.
0
Может вам пару контактов ребят, которые до сих пор в около-роботовой (автоматизация производственных линий, роботы, станки и т.д.) теме? Вдруг кто из этой темы на кандидатскую (или какие у них там уже по плану) чего заприметит — получится взаимовыгодное сотрудничество :)
0
Есть задача о оптимальном движении лифтов, которая схожая с данной. Один из эффективных путей ее решения — назначить каждому роботу зону ответственности, которые слегка перекрываются. Если роботу нужно переместить груз в зону ответственности другого робота, он его оставляет в зоне перекрытия, где его потом подбирает другой робот. Но этот эвристический алгоритм лучше применять когда роботов много и рассчитывать комбинации становится очень трудно. В случае двух роботов скорее всего ваш алгоритм будет работать лучше.
0
Когда мы только ткнулись в терминологию искусственного интеллекта и стали размышлять о стратегиях, то первой же мыслью была идея разграничение зон ответственности. Однако приемка товара осуществляется в крайних левых ячейках. А сброс товаров — в средних нижних. И может происходить одновременно и прием товара, и отбор. Поэтому стратегия разделения зон ответственности мы на этом уровне не использовали, но использовали в «товарном сервере» — следующем уровне высокоуровневого ПО. При размещении товара ему назначается такая ячейка для хранения, чтобы было равномерное распределение товаров в левой и правой части подсклада (относительно ячеек сброса). То есть чтобы оба робота могли работать не пересекаясь друг с другом.
0
Видимо, задача вообразить себя даже не роботом, а группой роботов, решаема только программистами с определенным складом ума.
Ну, у нас в группе, не смотря на то что это была профильная тема, дай бог чтобы процентов двадцать могли это осилить. Даже с одним роботом обслуживающим насколько станков у большинства проблемы были, а когда роботов на линии несколько так и вообще полный затык у большинства наступает. Склад от этой производстенной линии вряд-ли сильно отличается в сторону легкости восприятия.
Без софта который бы нормально анимировал работу всей линии обычный человек с наскоку не осилит, впрчем и с софтом тоже вкурит далеко не каждый. И это не только программистов касается, просто не всем дано.
З.Ы.: а мне роботы никогда не снились, зато однажды снилось что я маршрутизатор, разруливаю пакеты по портам o_0
0
число операций изменений таблиц достигало иногда 20-ти в секундуДикая нагрузка. Думаю, кроме Oracle никакая другая СУБД бы не выдержала.
+3
Я полагаю, тут тег sarcasm пропущен?
0
Шутки шутками, но нагрузка на SQL сервер в нашем случае действительно большая. Вначале мы даже подумывали использовать специальный Oracle SQL сервер, работающий в режиме Real-Time. Но и обычный XE справился.
Хотя один раз мы его таки доконали: когда программист забыл отключить визуализатор принятия решений и мы запустили систему в штатном режиме. Каждую секунду на диск дописывался кусок лога размером около 10 МБ. И как только АСК вышла на максимальную мощность, SELECT стал возвращать старый snapshot (который был до update). Слава богу, роботы не столкнулись, на триггерный механизм это не повлияло. А вот механизм принятия решений заклинило — и роботы стали бестолково кружить по кольцевому складу словно лебеди. Видимо, нагрузка на жесткий диск сурово сказывается на производительности Oracle.
Хотя один раз мы его таки доконали: когда программист забыл отключить визуализатор принятия решений и мы запустили систему в штатном режиме. Каждую секунду на диск дописывался кусок лога размером около 10 МБ. И как только АСК вышла на максимальную мощность, SELECT стал возвращать старый snapshot (который был до update). Слава богу, роботы не столкнулись, на триггерный механизм это не повлияло. А вот механизм принятия решений заклинило — и роботы стали бестолково кружить по кольцевому складу словно лебеди. Видимо, нагрузка на жесткий диск сурово сказывается на производительности Oracle.
0
Неплохо бы видео посмотреть, как работает.
0
Если интересно посмотреть, как работает робот, то это можно сделать на сайте www.vind.ru — в левой части экрана там есть видео. Правда, на нем запечатлен робот старого образца, однако общую идею понять можно.
Если же интересно как работает «сервер штабелеров», могу заснять и выложить видео экрана программы.
Если же интересно как работает «сервер штабелеров», могу заснять и выложить видео экрана программы.
+1
Да, если честно, результаты работы вашего алгоритма хочется посмотреть, можно в симуляции.
+1
Спасибо. Ваша статья продолжает «неделю прагматиков» на хабре — как доступными в данную минуту в данном коллективе средствами решить задачу. Я бы в жизне даже не подумал в сторону Oracle и триггеров для задачи управления роботами… А за визуализацию как ключ к решению проблемы — отдельное спасибо. Обычно заказчикам или инвесторам трудно доказать необходимость таких непрямых затрат, теперь у меня будет дополнительный аргумент.
0
Рад, что моя статья оказалась полезной.
А какие еще топики в «неделе прагматиков»? А то я на хабре новичок, еще не научился отслеживать такие моменты.
А какие еще топики в «неделе прагматиков»? А то я на хабре новичок, еще не научился отслеживать такие моменты.
0
Да было несколько статей на тему как не переусложнять разработку всякими паттернами. Например habrahabr.ru/post/155165/
0
XE как продуктивная база — чреватый проблемами путь.
0
Когда мы его только попробовали несколько лет тому назад, то он нам не понравился. Но потом я где-то вычитал, что XE не стоит сильно конфигурировать и менять настройки по умолчанию. Мы ведь как привыкли — ставим, потом залазим в конфиг и пошло-поехало. XE так не любит. Лучше после установки вообще в нем ничего не менять. Даже при апгрейде сервера лучше деинсталлировать XE, а затем заново его поставить. И такой подход дал свои результаты. С установками по умолчанию XE совсем даже ничего. Мы его уже использовали как минимум в 10-ти реальных проектах, в том числе в WEB-проектах на .Net.
0
Какая же интересная задача! Хотелось бы, чтобы и мне когда-нибудь такую пришлось реализовывать.
0
В чем проблема, шлите свое резюме в личку!
Сейчас мы как раз ведем переговоры о поставке крупного АСК, понадобится расширение нашего штата.
Только сразу предупрежу — работа серьезная. Лично от меня потребовала максимального напряжения не только моих сил, но и способностей. Один раз мы уже пытались нанять новых людей — да куда там, вначале энтузиазм, но даешь маленькое тестовое задание (1-2 дня работы) и кандидат исчезает в неизвестном направлении.
Сейчас мы как раз ведем переговоры о поставке крупного АСК, понадобится расширение нашего штата.
Только сразу предупрежу — работа серьезная. Лично от меня потребовала максимального напряжения не только моих сил, но и способностей. Один раз мы уже пытались нанять новых людей — да куда там, вначале энтузиазм, но даешь маленькое тестовое задание (1-2 дня работы) и кандидат исчезает в неизвестном направлении.
+1
Если бы вы предложили это мне года четыре назад, я бы моментально подорвался. Но я принял решение уходить постепенно из IT и сейчас учусь на психолога и психотерапевта, хочу наукой заниматься и помогать людям (кстати, планирую разрабатывать тему активности\субьектности — думаю о моделировании искусственной личности, имеющей собственную волю). Чтобы как-то обеспечивать себя, все еще сижу на говноработе в банке за которую очень неплохо платят, боюсь таких денег вы мне не сможете предложить. Вот и завидую, кроме денег и приятных людей вокруг, ничего хорошего в моей текущей работе нет.
0
Наблюдение моей жены — человек может хорошо зарабатывать честным трудом только в той сфере деятельности, в которой ему нравится работать. В которой он получает эстетическое удовольствие. Чтобы найти такую профессию, надо вспомнить свои детские или юношеские мечты.
Я тоже пытался работать в банке. Аж целых три дня. И после трех дней работы внутри так стало плохо, что я решил, а пошли они нафиг. И не вышел просто на работу.
Еще лет 9 тому назад предлагали работать начальником IT-отдела местного ГАЗпрома. Бешеные бабки обещали по нашим меркам. Я аж целые сутки думал прежде чем отказаться.
А про деньги хорошо Киосаки сказал — что деньги должны приносить активы, а не ежедневный напряженный труд. И создавать этот актив можно не увольняясь с основной работы, а параллельно.
Я тоже пытался работать в банке. Аж целых три дня. И после трех дней работы внутри так стало плохо, что я решил, а пошли они нафиг. И не вышел просто на работу.
Еще лет 9 тому назад предлагали работать начальником IT-отдела местного ГАЗпрома. Бешеные бабки обещали по нашим меркам. Я аж целые сутки думал прежде чем отказаться.
А про деньги хорошо Киосаки сказал — что деньги должны приносить активы, а не ежедневный напряженный труд. И создавать этот актив можно не увольняясь с основной работы, а параллельно.
0
Я в банках 9 лет. 7 лет были прекрасны и я поучаствовал в прекрасных проектах, познакомился с замечательными людьми. Но чем выше поднимаешься, тем вода грязнее и неприятнее плавать.
Я получаю большое удовольствие от изучения психологии, а деньги дают мне возможность это делать. Хотя через какое то время придется уйти. Но я это выбираю осознанно.
Я получаю большое удовольствие от изучения психологии, а деньги дают мне возможность это делать. Хотя через какое то время придется уйти. Но я это выбираю осознанно.
0
маленькое? опубликуйте здесь, а?
+1
У нас похожая штука работает с прошлого октября. Тут это принято называть Mini Load.
Кругового релься нет — два параллельных, по одному крану на рельс, у каждого места для двух ящиков. Работает шустро, хотя краны, безусловно, иногда «требуют внимания».
Опыт показал, что основная сложность лежит в сфере WCS («Warehouse Control System) модуля: как и когда лучше пополнять, какой товар дублировать с каждой стороны, порядок обхода местонахождений и т.п…
Кругового релься нет — два параллельных, по одному крану на рельс, у каждого места для двух ящиков. Работает шустро, хотя краны, безусловно, иногда «требуют внимания».
Опыт показал, что основная сложность лежит в сфере WCS («Warehouse Control System) модуля: как и когда лучше пополнять, какой товар дублировать с каждой стороны, порядок обхода местонахождений и т.п…
0
А кто производитель Ваших Mini Load, если не секрет?
0
Dematic, www.dematic.com/uk
Правда не нашёл у них на сайте таких кранов, как у нас стоят.
www.dematic.com/automated-miniload-storage-systems — отличается от наших. Может из-за количества захватываемых ящиков.
P.S. У нас их роботами или штабелёрами не называют. Просто краны. (mini load — вся система в сборе)
Правда не нашёл у них на сайте таких кранов, как у нас стоят.
www.dematic.com/automated-miniload-storage-systems — отличается от наших. Может из-за количества захватываемых ящиков.
P.S. У нас их роботами или штабелёрами не называют. Просто краны. (mini load — вся система в сборе)
0
Sign up to leave a comment.
Групповой искусственный интеллект для роботов-штабелеров на Oracle SQL XE