Комментарии 39
Может я и ошибаюсь, но к конечным автоматам это не имеет отношения. Нет т.е. конечно можно представить склад с ячейками как систему в определенном состоянии, а перемещение ячеек, как переход в другое состояние. Но на первый взгляд это транспортная задача, с известными методами решения. А у вас получился какой-то набор эвристик. Еще и Oracle… За ним же следить надо.
Конечный автомат здесь не ячейки, а состояния роботов. Хотя бы вот такой:
— переместиться к нужной ячейке (по пути прогнав другого робота, если мешает),
— загрузить контейнер,
— переместиться к конечной ячейке (по пути прогнав другого робота, если мешает),
— выгрузить контейнер.
И теоретически на любом этапе может быть ошибка робота или ошибка связи, которую тоже нужно обработать, не забыв, с чего мы начали. Количество вещей, о которых «надо было помнить» при принятии решений столь велико, что они сформировали ничего себе так базу данных (дамп весит 10 МБ). Кроме того, программа может подвиснуть (да хотя бы в процессе отладки), а текущее состояние склада и роботов нужно помнить. Так что Oracle тут в прямом смысле оказался палочкой выручалочкой.
Методы транспортной задачи (старый добрый коммивояжер) с наскока использовать не получилось. Вы считаете, имеет смысл в ней покопаться, чтоб найти матмодель? Не могли бы еще подбросить пару ключевых слов, по которым искать информацию?
— переместиться к нужной ячейке (по пути прогнав другого робота, если мешает),
— загрузить контейнер,
— переместиться к конечной ячейке (по пути прогнав другого робота, если мешает),
— выгрузить контейнер.
И теоретически на любом этапе может быть ошибка робота или ошибка связи, которую тоже нужно обработать, не забыв, с чего мы начали. Количество вещей, о которых «надо было помнить» при принятии решений столь велико, что они сформировали ничего себе так базу данных (дамп весит 10 МБ). Кроме того, программа может подвиснуть (да хотя бы в процессе отладки), а текущее состояние склада и роботов нужно помнить. Так что Oracle тут в прямом смысле оказался палочкой выручалочкой.
Методы транспортной задачи (старый добрый коммивояжер) с наскока использовать не получилось. Вы считаете, имеет смысл в ней покопаться, чтоб найти матмодель? Не могли бы еще подбросить пару ключевых слов, по которым искать информацию?
У вас нет возможности восстановить состояние системы не прибегая к базе? Ну т.е. у вас нет возможности спросить у оборудования, где находится робот и есть ли на нем контейнер? Ну еще где находится, какой контейнер я еще поверю, что информация может быть только в базе. Но роботы то должны отслеживаться? По контейнерам информация должна быть в системе более высокого уровня. Не той которая управляет роботами. И это простая таблица — никаких состояний.
Ключевые слова очевидны - транспортная задача. Я не уверен на 100%, что это оно. Но уверен что эта задача уже кем то решалась и надо искать подходящую мат. модель.
Мне кажется вы смешали в кучу несколько задач. Вам надо их разделить и решать по-отдельности.
Я вижу такие:
1. Управление отдельным роботом — да автомат с состояниями, едем, стоим, переместились на ячейку N, заклинило в ячейке N.
2. Граф состояния склада — узлы — ячейки, или координаты — скорее всего не во всех координатах есть ячейки. Связи это возможность перемещения робота из одной координаты в другую. Граф перестраивается при поступлении новых данных. Например если робот остановился с ошибкой — граф перестраивается. В граф можно добавить узлы не связанные с координатами, а например узел, который отвечает за уборку мешающего робота.
3. Решение задачи оптимизации перемещения робота по графу. Робот перемещается по оптимальному пути, после его вычисления. Любое событие повлиявшее на граф и пересекающееся с узлами через которые проходит путь робота приводит к пересчету пути на новом графе. Впрочем условие пересечения это уже преждевременная оптимизация.
Ключевые слова очевидны - транспортная задача. Я не уверен на 100%, что это оно. Но уверен что эта задача уже кем то решалась и надо искать подходящую мат. модель.
Мне кажется вы смешали в кучу несколько задач. Вам надо их разделить и решать по-отдельности.
Я вижу такие:
1. Управление отдельным роботом — да автомат с состояниями, едем, стоим, переместились на ячейку N, заклинило в ячейке N.
2. Граф состояния склада — узлы — ячейки, или координаты — скорее всего не во всех координатах есть ячейки. Связи это возможность перемещения робота из одной координаты в другую. Граф перестраивается при поступлении новых данных. Например если робот остановился с ошибкой — граф перестраивается. В граф можно добавить узлы не связанные с координатами, а например узел, который отвечает за уборку мешающего робота.
3. Решение задачи оптимизации перемещения робота по графу. Робот перемещается по оптимальному пути, после его вычисления. Любое событие повлиявшее на граф и пересекающееся с узлами через которые проходит путь робота приводит к пересчету пути на новом графе. Впрочем условие пересечения это уже преждевременная оптимизация.
Если произойдет вылет программы во время работы АСК, то у робота можно узнать его местоположение и даже какую команду (низкоуровневую) он выполняет. И все. Относительно контейнера можно просто узнать, есть ли на платформе он или нет (код его выяснить нет возможности). То есть где-то должна сохраняться информация как минимум о нескольких вещах:
— что мы везем или собираемся везти (код контейнера),
— какая цель движения робота внутри подсклада (источник и приемник),
— блокировки участка пути — что заблокировано,
— заявки на блокировки — что робот хочет заблокировать, но не может,
— есть ли и какая цель перемещения контейнеров между подскладами (подскладов может быть N штук).
Транспортная задача — кажется вспомнил — это вроде как раздел математики. На симплекс-методе у нас всю группу в институте завалили. Очень уж заумная вещь. Видимо придется разбираться. Эх, математика бы найти!
— что мы везем или собираемся везти (код контейнера),
— какая цель движения робота внутри подсклада (источник и приемник),
— блокировки участка пути — что заблокировано,
— заявки на блокировки — что робот хочет заблокировать, но не может,
— есть ли и какая цель перемещения контейнеров между подскладами (подскладов может быть N штук).
Транспортная задача — кажется вспомнил — это вроде как раздел математики. На симплекс-методе у нас всю группу в институте завалили. Очень уж заумная вещь. Видимо придется разбираться. Эх, математика бы найти!
Я уверен, что в базе имеет смысл хранить только, где какой контейнер находится (включая платформы роботов) — 1я таблица. Задачи на перемещение — 2 я таблица. Ну может конечно еще что то, но к управлению роботоми это не будет иметь отношения.
Не очень понятно что такое подсклады. Нельзя все логически объединить в одну систему? Или между подскладами ездят не роботы?
Блокировки пути — я не очень понимаю что это. Если это относится только к системе с роботами, то это должна быть какая то отдельная база, а может быть просто файл на диске?
Если это просто другой робот блокирует путь, то естественно это можно всегда высчитать по данным от оборудования. Зачем это хранить в базе?
Естественно у вас должна как-то хранится структура самого склада. Ну хорошо храните ее в базе. Но даже если ее хранить в базе, то система управления роботами может построить базовый граф на ее основе в удобном для работы формате и хранить его копию на диске.
Не очень понятно что такое подсклады. Нельзя все логически объединить в одну систему? Или между подскладами ездят не роботы?
Блокировки пути — я не очень понимаю что это. Если это относится только к системе с роботами, то это должна быть какая то отдельная база, а может быть просто файл на диске?
Если это просто другой робот блокирует путь, то естественно это можно всегда высчитать по данным от оборудования. Зачем это хранить в базе?
Естественно у вас должна как-то хранится структура самого склада. Ну хорошо храните ее в базе. Но даже если ее хранить в базе, то система управления роботами может построить базовый граф на ее основе в удобном для работы формате и хранить его копию на диске.
Сейчас в базе хранится (не считая информации по товару, контейнерам и команд от внешней WMS системы заказчика):
— информация о ячейках,
— информация о блокировке ячеек различными командами,
— информация об автоблокировке ошибочных ячеек,
— команды сервера штабелеров от внешней системы,
— команды уровня подсклада,
— команды, напрямую данные роботам (нужны еще и для статистики),
— логи,
— возникающие проблемы и выбранные пользователем методы их устранения,
— информация по подскладам,
— общая информация (настройки) по системе,
— настройки роботов и информация об их текущем состоянии,
— информация о стеллажах,
— информация об участках рельсового пути,
— информация о блокировке участков пути.
Наверное, можно было бы хранить все это в xml-файлах. Но зачем, если Oracle XE бесплатный и есть опыт работы с ним?
Подсклады — это непересекающиеся участки пути (рельсов), которые могут быть как закольцованы, так и нет. На верхнем рисунке АСК состоит из двух подскладов — левый дугообразный некольцевой (на нем один робот), правый — закольцованный (на нем два робота). Между подскладами никто не ездит, контейнеры передаются через транзитные ячейки. Логически все объединено в одну систему, но чтоб она работала как одна система, пришлось на уровне программной разработки вводить кучу уровней, и каждый отлаживать отдельно, иначе сложность задачи превышает способности программистов.
Путь — это ресурс, который можно занять только монопольно. По мере прохождения робота по пути, ресурс должен освобождаться, и давать возможность другому роботу его занимать. Зачем отдельная база? Логичней просто отдельный уровень одной базы SQL-сервера.
Блокировки работают через диспетчер блокировок — семафоры там всякие — так по данным от оборудования это не получить. Нужен именно диспетчер со своей очередью запросов на требуемый ресурс.
Какая разница — файл на диске, или таблица в SQL? Но с таблицей SQL очень удобно работать, не надо париться про ее сохранение, решение проблем двойного доступа и прочее.
— информация о ячейках,
— информация о блокировке ячеек различными командами,
— информация об автоблокировке ошибочных ячеек,
— команды сервера штабелеров от внешней системы,
— команды уровня подсклада,
— команды, напрямую данные роботам (нужны еще и для статистики),
— логи,
— возникающие проблемы и выбранные пользователем методы их устранения,
— информация по подскладам,
— общая информация (настройки) по системе,
— настройки роботов и информация об их текущем состоянии,
— информация о стеллажах,
— информация об участках рельсового пути,
— информация о блокировке участков пути.
Наверное, можно было бы хранить все это в xml-файлах. Но зачем, если Oracle XE бесплатный и есть опыт работы с ним?
Подсклады — это непересекающиеся участки пути (рельсов), которые могут быть как закольцованы, так и нет. На верхнем рисунке АСК состоит из двух подскладов — левый дугообразный некольцевой (на нем один робот), правый — закольцованный (на нем два робота). Между подскладами никто не ездит, контейнеры передаются через транзитные ячейки. Логически все объединено в одну систему, но чтоб она работала как одна система, пришлось на уровне программной разработки вводить кучу уровней, и каждый отлаживать отдельно, иначе сложность задачи превышает способности программистов.
Путь — это ресурс, который можно занять только монопольно. По мере прохождения робота по пути, ресурс должен освобождаться, и давать возможность другому роботу его занимать. Зачем отдельная база? Логичней просто отдельный уровень одной базы SQL-сервера.
Блокировки работают через диспетчер блокировок — семафоры там всякие — так по данным от оборудования это не получить. Нужен именно диспетчер со своей очередью запросов на требуемый ресурс.
Какая разница — файл на диске, или таблица в SQL? Но с таблицей SQL очень удобно работать, не надо париться про ее сохранение, решение проблем двойного доступа и прочее.
Задачу коммивояджера сейчас решают с помощью линейного программирования. При этом решение задачи линейного программирования (симплекс-метод) является лишь элементарным шагом алгоритма ;).
Возможно вашу задачу можно решать схожими методами, но она явно сложнее и я сходу не вижу как это можно сделать. У меня знакомый этим занимается, но я пока не нашел сил разобраться в этой области математики.
Возможно вашу задачу можно решать схожими методами, но она явно сложнее и я сходу не вижу как это можно сделать. У меня знакомый этим занимается, но я пока не нашел сил разобраться в этой области математики.
Может вам пару контактов ребят, которые до сих пор в около-роботовой (автоматизация производственных линий, роботы, станки и т.д.) теме? Вдруг кто из этой темы на кандидатскую (или какие у них там уже по плану) чего заприметит — получится взаимовыгодное сотрудничество :)
Есть задача о оптимальном движении лифтов, которая схожая с данной. Один из эффективных путей ее решения — назначить каждому роботу зону ответственности, которые слегка перекрываются. Если роботу нужно переместить груз в зону ответственности другого робота, он его оставляет в зоне перекрытия, где его потом подбирает другой робот. Но этот эвристический алгоритм лучше применять когда роботов много и рассчитывать комбинации становится очень трудно. В случае двух роботов скорее всего ваш алгоритм будет работать лучше.
Когда мы только ткнулись в терминологию искусственного интеллекта и стали размышлять о стратегиях, то первой же мыслью была идея разграничение зон ответственности. Однако приемка товара осуществляется в крайних левых ячейках. А сброс товаров — в средних нижних. И может происходить одновременно и прием товара, и отбор. Поэтому стратегия разделения зон ответственности мы на этом уровне не использовали, но использовали в «товарном сервере» — следующем уровне высокоуровневого ПО. При размещении товара ему назначается такая ячейка для хранения, чтобы было равномерное распределение товаров в левой и правой части подсклада (относительно ячеек сброса). То есть чтобы оба робота могли работать не пересекаясь друг с другом.
Видимо, задача вообразить себя даже не роботом, а группой роботов, решаема только программистами с определенным складом ума.
Ну, у нас в группе, не смотря на то что это была профильная тема, дай бог чтобы процентов двадцать могли это осилить. Даже с одним роботом обслуживающим насколько станков у большинства проблемы были, а когда роботов на линии несколько так и вообще полный затык у большинства наступает. Склад от этой производстенной линии вряд-ли сильно отличается в сторону легкости восприятия.
Без софта который бы нормально анимировал работу всей линии обычный человек с наскоку не осилит, впрчем и с софтом тоже вкурит далеко не каждый. И это не только программистов касается, просто не всем дано.
З.Ы.: а мне роботы никогда не снились, зато однажды снилось что я маршрутизатор, разруливаю пакеты по портам o_0
число операций изменений таблиц достигало иногда 20-ти в секундуДикая нагрузка. Думаю, кроме Oracle никакая другая СУБД бы не выдержала.
Я полагаю, тут тег sarcasm пропущен?
Шутки шутками, но нагрузка на SQL сервер в нашем случае действительно большая. Вначале мы даже подумывали использовать специальный Oracle SQL сервер, работающий в режиме Real-Time. Но и обычный XE справился.
Хотя один раз мы его таки доконали: когда программист забыл отключить визуализатор принятия решений и мы запустили систему в штатном режиме. Каждую секунду на диск дописывался кусок лога размером около 10 МБ. И как только АСК вышла на максимальную мощность, SELECT стал возвращать старый snapshot (который был до update). Слава богу, роботы не столкнулись, на триггерный механизм это не повлияло. А вот механизм принятия решений заклинило — и роботы стали бестолково кружить по кольцевому складу словно лебеди. Видимо, нагрузка на жесткий диск сурово сказывается на производительности Oracle.
Хотя один раз мы его таки доконали: когда программист забыл отключить визуализатор принятия решений и мы запустили систему в штатном режиме. Каждую секунду на диск дописывался кусок лога размером около 10 МБ. И как только АСК вышла на максимальную мощность, SELECT стал возвращать старый snapshot (который был до update). Слава богу, роботы не столкнулись, на триггерный механизм это не повлияло. А вот механизм принятия решений заклинило — и роботы стали бестолково кружить по кольцевому складу словно лебеди. Видимо, нагрузка на жесткий диск сурово сказывается на производительности Oracle.
Неплохо бы видео посмотреть, как работает.
Если интересно посмотреть, как работает робот, то это можно сделать на сайте www.vind.ru — в левой части экрана там есть видео. Правда, на нем запечатлен робот старого образца, однако общую идею понять можно.
Если же интересно как работает «сервер штабелеров», могу заснять и выложить видео экрана программы.
Если же интересно как работает «сервер штабелеров», могу заснять и выложить видео экрана программы.
Да, если честно, результаты работы вашего алгоритма хочется посмотреть, можно в симуляции.
Вот здесь выложен маленький ролик — пример работы алгоритма. Как раз на проблемном моменте — пересечение зон ответственности. Стратегия размещения товаров на АСК стремится свести такие варианты на нет, но не всегда получается.
Спасибо. Ваша статья продолжает «неделю прагматиков» на хабре — как доступными в данную минуту в данном коллективе средствами решить задачу. Я бы в жизне даже не подумал в сторону Oracle и триггеров для задачи управления роботами… А за визуализацию как ключ к решению проблемы — отдельное спасибо. Обычно заказчикам или инвесторам трудно доказать необходимость таких непрямых затрат, теперь у меня будет дополнительный аргумент.
Рад, что моя статья оказалась полезной.
А какие еще топики в «неделе прагматиков»? А то я на хабре новичок, еще не научился отслеживать такие моменты.
А какие еще топики в «неделе прагматиков»? А то я на хабре новичок, еще не научился отслеживать такие моменты.
Да было несколько статей на тему как не переусложнять разработку всякими паттернами. Например habrahabr.ru/post/155165/
XE как продуктивная база — чреватый проблемами путь.
Когда мы его только попробовали несколько лет тому назад, то он нам не понравился. Но потом я где-то вычитал, что XE не стоит сильно конфигурировать и менять настройки по умолчанию. Мы ведь как привыкли — ставим, потом залазим в конфиг и пошло-поехало. XE так не любит. Лучше после установки вообще в нем ничего не менять. Даже при апгрейде сервера лучше деинсталлировать XE, а затем заново его поставить. И такой подход дал свои результаты. С установками по умолчанию XE совсем даже ничего. Мы его уже использовали как минимум в 10-ти реальных проектах, в том числе в WEB-проектах на .Net.
Какая же интересная задача! Хотелось бы, чтобы и мне когда-нибудь такую пришлось реализовывать.
В чем проблема, шлите свое резюме в личку!
Сейчас мы как раз ведем переговоры о поставке крупного АСК, понадобится расширение нашего штата.
Только сразу предупрежу — работа серьезная. Лично от меня потребовала максимального напряжения не только моих сил, но и способностей. Один раз мы уже пытались нанять новых людей — да куда там, вначале энтузиазм, но даешь маленькое тестовое задание (1-2 дня работы) и кандидат исчезает в неизвестном направлении.
Сейчас мы как раз ведем переговоры о поставке крупного АСК, понадобится расширение нашего штата.
Только сразу предупрежу — работа серьезная. Лично от меня потребовала максимального напряжения не только моих сил, но и способностей. Один раз мы уже пытались нанять новых людей — да куда там, вначале энтузиазм, но даешь маленькое тестовое задание (1-2 дня работы) и кандидат исчезает в неизвестном направлении.
Если бы вы предложили это мне года четыре назад, я бы моментально подорвался. Но я принял решение уходить постепенно из IT и сейчас учусь на психолога и психотерапевта, хочу наукой заниматься и помогать людям (кстати, планирую разрабатывать тему активности\субьектности — думаю о моделировании искусственной личности, имеющей собственную волю). Чтобы как-то обеспечивать себя, все еще сижу на говноработе в банке за которую очень неплохо платят, боюсь таких денег вы мне не сможете предложить. Вот и завидую, кроме денег и приятных людей вокруг, ничего хорошего в моей текущей работе нет.
Наблюдение моей жены — человек может хорошо зарабатывать честным трудом только в той сфере деятельности, в которой ему нравится работать. В которой он получает эстетическое удовольствие. Чтобы найти такую профессию, надо вспомнить свои детские или юношеские мечты.
Я тоже пытался работать в банке. Аж целых три дня. И после трех дней работы внутри так стало плохо, что я решил, а пошли они нафиг. И не вышел просто на работу.
Еще лет 9 тому назад предлагали работать начальником IT-отдела местного ГАЗпрома. Бешеные бабки обещали по нашим меркам. Я аж целые сутки думал прежде чем отказаться.
А про деньги хорошо Киосаки сказал — что деньги должны приносить активы, а не ежедневный напряженный труд. И создавать этот актив можно не увольняясь с основной работы, а параллельно.
Я тоже пытался работать в банке. Аж целых три дня. И после трех дней работы внутри так стало плохо, что я решил, а пошли они нафиг. И не вышел просто на работу.
Еще лет 9 тому назад предлагали работать начальником IT-отдела местного ГАЗпрома. Бешеные бабки обещали по нашим меркам. Я аж целые сутки думал прежде чем отказаться.
А про деньги хорошо Киосаки сказал — что деньги должны приносить активы, а не ежедневный напряженный труд. И создавать этот актив можно не увольняясь с основной работы, а параллельно.
Я в банках 9 лет. 7 лет были прекрасны и я поучаствовал в прекрасных проектах, познакомился с замечательными людьми. Но чем выше поднимаешься, тем вода грязнее и неприятнее плавать.
Я получаю большое удовольствие от изучения психологии, а деньги дают мне возможность это делать. Хотя через какое то время придется уйти. Но я это выбираю осознанно.
Я получаю большое удовольствие от изучения психологии, а деньги дают мне возможность это делать. Хотя через какое то время придется уйти. Но я это выбираю осознанно.
маленькое? опубликуйте здесь, а?
У нас похожая штука работает с прошлого октября. Тут это принято называть Mini Load.
Кругового релься нет — два параллельных, по одному крану на рельс, у каждого места для двух ящиков. Работает шустро, хотя краны, безусловно, иногда «требуют внимания».
Опыт показал, что основная сложность лежит в сфере WCS («Warehouse Control System) модуля: как и когда лучше пополнять, какой товар дублировать с каждой стороны, порядок обхода местонахождений и т.п…
Кругового релься нет — два параллельных, по одному крану на рельс, у каждого места для двух ящиков. Работает шустро, хотя краны, безусловно, иногда «требуют внимания».
Опыт показал, что основная сложность лежит в сфере WCS («Warehouse Control System) модуля: как и когда лучше пополнять, какой товар дублировать с каждой стороны, порядок обхода местонахождений и т.п…
А кто производитель Ваших Mini Load, если не секрет?
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 — вся система в сборе)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Групповой искусственный интеллект для роботов-штабелеров на Oracle SQL XE