Category: технологии

Category was added automatically. Read all entries about "технологии".

la

Индо-европейское

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

Она познакомилась с ним по интернету где-то лет 10 назад, в каком-то сетевом фанфиковском сообществе. Там имел место небольшой забавный эпизод. Когда он узнал что она русская, живёт в окрестности Бостона, он спросил в переписке: а ты случайно не знаешь такого Кирилла Панкратова из MIT? -Эээ... вообще-то я за ним замужем...

Оказалось он знал меня как пользователь пакета SaGA (Spatial and Geometric Analysis toolbox), который я написал на Матлабе в начале 1995 года ещё находясь в MIT, но когда мне уже наскучила океанология и академическая наука в целом. Этот пакет пользовался огромной популярностью у геофизиков, биофизиков и многих других кому нужны были пространственные и геометрические вычисления, некоторые виды обработки изображений и т.д.

Он и сейчас сидит на MIT-шном сервере и нескольких зеркалах в других местах. Хотя я не поддерживал его уже много лет, ещё несколько лет назад я регулярно получал вопросы по нему от пользователей. Там были крутейшие вещи, многие из которых впервые были написаны на Матлабе, такие как многомерное выпуклое покрытие (convex hull), многомерная же оптимальная триангуляция Делане, многомерная оптимальная интерполяция по нерегуляномы множеству, и многое другое. Некоторые вещи были самыми лучшими из существующих в мире с точки зрения алгоритмов. С тех пор многие из подобных функций были встроены в самом Матлабе, некотые из них откровенно стянуты из SaGA. На этот пакет было огромное количество ссылок как в научных статьях так и во всяких сетевых справочниках. Во всяком случае влияние этого (любительского) проекта на мировую науку несравненно больше чем от моей PhD-диссертации, написанной в MIT незадолго до этого.

В то время (10 лет назад) Нагеш был аспиранто или пост-доком, кажется в израильском Технионе, и занимался обработкой биологических изображений (где ему и пригодилась SaGA). С тех пор он перебрался в университет McGill в Монреале. В мае 2010-го мы с ним там встретились во время очередного визита туда на длинный уикенд. Под катом фотка с ним (тогда у моей старой камеры стала глючить CCD-матрица, поэтому цвета совсем никуда):Collapse )
la

Всё что вы хотели знать о роботах

По жж-шке ходит статья из MIT Technology Review, про "новую революцию" в автоматизации и роботизации вот здесь есть перевод на русский. Статья несколько наивная.

Вот как обычно в реальности:

... 24. Робот сортирует коробки по штрихкодам, которые предварительно клеятся на них на весах в цеху упаковки (packing). Если они наклеены не по центру коробки, криво, или кверх ногами (так тоже бывает), робот сбрасывает коробку обратно. Местный, который стоит на весах, клеит наклейки как попало, а мы потом весь день переклеиваем их на движущихся коробках. Нет такой силы, которая способна заставить его начать это делать по-человечески. Он говорит «Ok, Sorry» ( «Хорошо, извините»), и продолжает в том же духе. Я предполагаю, что это для него просто непосильная задача. Он просто НЕ МОЖЕТ. Но хуже этого, только местный, который приходит на овертайм в субботу или воскресенье. Потому что он приходит пьяный, после ночи в пабе. И тогда, роботы просто останавливаются, потому что не могут прочитать ту ахинею, которая наклеена на коробках. А еще, местный товарищ, может прийти обкуренный или объевшийся галюциногенных грибов, которые на острове растут в огромных количествах.
...
26. Одну неделю у нас работал Кевин из коптильни. Его поставили вывозить готовые паллеты с роботов. Для этого надо остановить робота, зайти в зону его работы, вывезти паллет роклой и снова включить робота. Но Кевин всё время путал последовательность кнопок, даже несмотря на то, что все они были разного цвета. И первое,что происходило после его нажатия на кнопки, вместо останова, робот брал пустую паллету, и с размаху одевал ее сверху на полную с рыбой. Раздавался хлопок, во все стороны разлеталась рыба, лед и пенопласт, а потом все мы, 30 минут разгребали последствия, потому что надо было собрать разбитые доски от паллетов, куски пенопласта, рыбу и перепаковать всё заново в 24 коробки. Завод в это время стоял . Когда это повторилось несколько раз, Кевину запретили подходить к роботам...

http://www.freecity.lv/bestseller/55/

Нет такого роботизированного процесса которого бы не мог бы полностью испортить средний мудак нажатием пары кнопок. Это примерно как старый анекдот про сибирских мужиков и японскую пилораму ("Ага! - торжествующе воскликнули сибирские мужики, засунув в японскую пилораму стальной рельс").

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

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

Не без моей помощи, впрочем, стало существенно лучше. Помню, дело было в середине декабря 2011, и незадолго до этого на нашем автоматизированном складе был внедрен мой алгоритм 3-мерной упаковки ящиков - самая сложная часть всей системы управления роботами и паллетизацией. Как раз за год до этого я только начал вообще заниматься этой задачей, потому что это оказалось самым узким местом всей большой логистической системы. Тот проект (он так и проходил под официальным названием "KP") был фантастикой - за год я не только создал с нуля и отладил принципиально новый алгоритм (в задаче над которой множество математиков работают по десятку лет), но и всё было переписано в рабочий код, вместе с графическими интерфейсами, соединениями с базами данных и прочими обвязками и свистелками, прошло SQA и уже вовсю работало на практике.

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

То и дело процесс останавливался по разным причинам и работягам на смене нужно было вручную хватать и класть ящики. Самое удивительное впечатление в ту ночь - что практически все присутсвующие работяги периодически подходили ко мне засвидетельствовать почтение и рассказать как облечилась их работа с введением в действие моего алгоритма. То есть сам факт что они знали меня в лицо и знали про некий "KP packing algorithm" (чего никогда официально не обьявляли, а наоборот максимально держали в секрете) - само по себе было нетривиально. Мне было жалко их, работа - не позавидуешь, каждые несколько минут требуется ручное вмешательство, поправлять или перекладывать ящики. "Да ты чо," - говорили они мне - "сейчас так хорошо стало по сравнению с тем что было раньше". Раньше нужно было перекладывать вручную каждую вторую или третью паллету, и большинство паллет, даже не считая ошибок самих роботов, были небольшого размера и выглядели как конструкция из кубиков, сделанная 3-летним ребёнком - с башнями и пустотами и готовая развалиться в любой момент.

В общем, хорошая математика сильно помогла процессу, на он всё равно далёк от 100% автоматизации. 6-осный робот - вещь ныне стандартная но довольно дубовая. У него очень точные движения (ошибка в траектории последнего звена - меньше миллиметра), но точной траектории движения ещё недостаточно. Основная проблема - хваталка (gripper), который может при обратном движении зацеплять ящик и немного волочить его обратно. В результате случаются ошибки в укладке на несколько сантиметров (а для плотной упаковки требуется чтобы точность была лучше чем сантиметр). Так что поправлять вручную криво положенные ящики и обвалившиеся паллеты всё равно приходится.
la

Небольшое интервью про технологии, IT, автоматизацию и логистику

Вы будете смеяться, а я опять появился в "Плейбое" (украинский выпуск), как и два года назад, со всяким techno-speak и прогнозами на будущее. Украинский Плейбой - самый интеллектуальный журнал, а вы что думали :)

Весь выпуск (октябрь 2012) можно посмотреть здесь, и я там есть на страницах 36-37, затерялся среди сисек.

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

1. Как вы думаете, как буду развиваться телевизоры в ближайшие 10 лет и останется ли вообще понятие телевизор через 10 лет, или все возможные поверхности станут экранами?

В телевидении в последние 5-8 лет произошла революция, самая важная за сорок с лишним лет - с тех пор как в начале 1970-х началось быстрое распространение цветных телевизоров. Эта нынешняя революция - массовое распространение HDTV. В богатых странах мира уже примерно 2/3 телевизоров в домах относятся к этой категории. Это действительно качественный скачок. Сегодня картинка в большом качественном телевизоре приближается к хорошему кинотеатру, и к разрешению глаза. Одновременно с этим появился очень большой выбор цифровых каналов и стриминг-сервисов (типа Нетфликса); сейчас, при желании, практически в любое время можно посмотреть любой фильм или передачу созданную в любой стране мира и в любом году. Это настоящая революция, и она произошла в последние несколько лет.

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

2. Действительно ли идея умного дома так хороша, как о ней говорят, и произойдет ли в скором объединение всех устройств в доме в единую систему?

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

3. Действительно в IT-индустрии сейчас происходит прогресс или компании выпускают одинаковые продукты в разных обертках, закладывая незначительные улучшения в каждую новую модель?

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

А знаете что стало одним из ключевых факторов успеха смартфонов и планшетов? Очень важным оказались не только софтвер, но их физические, материальные характеристики, которыми традиционно пренебрегали в IT-индустрии. В частности, специальное прочное стекло, которое не царапается в кармане монетами и ключами, а так же электронные компоненты устойчивые к влажности. До айфонов мобильный телефон был хлипким устройством как и почти вся электроника. Сядешь неудачно на стул - получишь треснутый экран. Попадёт две капли дождя - выключится половина того же экрана. Нажмёшь посильнее кнопку - она отвалится.

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

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

"Лада" - логотип MIT

http://mit.edu

via http://ammosov.livejournal.com/918885.html

Студенты одной моей alma mater (физтех) сообщили Аммосову что на сайте моей другой alma mater - Massachusetts Institute of Technology - во весь экран на главной страницы фотка салона "Лады", машины производящейся на моей малой родине (Самарская область). Забавно.
la

Микроскоп для забивания гвоздей

Где-то в ленте было недавно - Typewriter for Ipad-2:


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

Так вот, о новом поколении мобильных гаджетов, появившихся 4-5 лет назад - айфоны и айпады, а сейчас уже довольно распространившаяся категория смартфонов и планшет. Их несомненный и грандиозный успех связан, на самом деле, в значительной мере не с достижениями в софтвере. Они в целом были эволюционными, без качественного скачка. В основном эти достижения связаны с прорывом в материальных, физических свойствах этих девайсов. Чуть ли не впервые в истории электронных устройств эти штуки - наощупь - воспринимаются как вещЬ, а не как игрушка из дешёвой пластмассы, готовая треснуть от неосторожного нажатия ногтем.

У меня самого прежние мобильные телефоны доживали спокойно - уходили на пенсию и заканчивали жизнь в каком-нибудь ящике в подвале. У остальных членов семьи... как правило, было не так. Треснутые экраны, запотевшие дисплеи, залитые кофе корпуса, выпавшие кнопки - сколько мы видели этого барахла. И это было вполне типичным для всех прочих электронных устройств. Массовая электроника и физические нагрузки всегда были почти несовместимыми друг с другом.

И вот пришли айфоны и целое новое поколение сенсорных устройств. Гениальность Стива Джобса, среди прочего, проявилась в их физических характеристиках. В отличии от мягкой пластмассы старых изделий, их корпус стал делаться из высокопрочного стекла, которое не царапается в кармане монетами или ключами. Протёр экран - и он как новый. Эти устройства выдерживают падение со второго этажа, и нормально работают после этого. Они почти невосприимчивы к влажности - даже потоку воды.

Первый свой смартфон (андроид) Жанна честно подарила уличным воришкам - два года назад, в Перу, в городе Арекипа ей вдруг пришло в голову на площади у центрального рынка перекладывать телефон во внешний карман рюкзачка. Через пять секунд телефона не было. Ну ладно, против этого нет приёма. Второй телефон (тоже андроид) она решила искупать в бассейне в отеле в Лас Вегасе, год назад. Там есть такой круговой бассейн с искусственным течением, больше ста метров общей длиной. И вот представьте игру "А кошелёк убегает...", и по дну бассейна вместе с течением непринуждённо скользит этот телефон, а за ним гонятся полдюжины человек. Через неполный круг нагнали. Положили сушиться. Через два дня... телефон заработал как ни в чём ни бывало.

Этим летом Сашка как-то на вечеринке держал телефон в кармане штанов. Они там чего-то нажрались лишнего, и его вырвало - на собственные джинсы. Дело было в доме его девушки. Она, как верная подруга, отнесла джинсы в стирку, а вместе с ними и телефон. В общем, многострадальный андроид полчаса болтался в горячей воде с активными химическими веществами. Для предыдущего поколения электроники сама мысль что после этого устройство может быть на что-то годным, могло вызвать гомерический смех - гаджет можно было выбрасывать сразу, не глядя. Но он не выбросил свой андроид, а положил сушиться. Через пару дней... он заработал! По крайней мере большинство функций (фотокамера так и не восстановилась). В конце концов он всё равно завёл себе айфон-4, но сам факт очень впечатляет.

Именно в этом и состоит главный секрет смартфонов и планшет. И, напоследок, одно из многочисленный применений их в быту:
http://www.youtube.com/watch?v=sCCKGvzj1NY
la

Статья в NY Times про нашу компанию

В субботу NY Times напечатала в разделе "Технологии" (но видную с заглавной страницы сайта) большую статью про новое поколение промышленных роботов: "Skilled Work, Without the Worker"

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

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

Но самая главная (и визуально выгодная) часть этой демонстрации - ячейка автоматической паллетизации: это место, где коробки, в определённом порядке, по конвейеру подходят к 6-осному роботу, который подхватывает их и кладёт на палету, как кирпичи на строящееся здание. Для робота положить коробку в заданное нужное место, с хорошей точностью - не проблема. Проблема в том что все "кирпичи" могут иметь разный размер (а так же массу, плотность, твёрдость), различающийся в диапазоне примерно в 10 раз, и придумать правильную кладку для них очень непросто.

Основным элементом этой ячейки, без которого вся эта процедура не имеет смысла, является мой математический алгоритм. Этот алгоритм решает задачу трёхмерной оптимальной упаковки (3d bin-packing problem), своего рода 3-мерный "Тетрис", только с непрерывным диапазоном размеров "кубиков". Я придумал этот алгоритм с нуля и совершенно неожиданно, за короткий срок, примерно полтора года назад. Это была вообще не моя работа, мой основной проект находился в совсем другой области, и сам я никогда не занимался такими задачами. Но подобной задачей вообще-то в мире занимаются немало людей - в академической науке (профессора математики и компьютерных наук со своими пост-доками и аспирантами), и в промышленности - целые коллективы математиков и программистов, в течении многих лет. На эту тему есть тысячи статей, патентов, множество софтверных продуктов, и т.д. Проблема упаковки очень актуальна как в логистике, так и в некототых других приложениях. Количество mixed-case pallets (паллет из смеси разных коробок), которые ежегодно перевозятся в мире со складов в магазины, исчисляется сотнями миллионов. Большинство из них собирается вручную - рабочими, которые берут ящики с полок и кладут на паллеты. Основная проблема, тормозящая переход к автоматизации этого процесса - именно алгоритмы упаковки. До последнего времени упаковки, созданные комьютерной программой, были хуже чем те, что тренированные рабочие делают "на глазок". Только в последние годы начали появляться автоматические системы, способные конкурировать с ручным трудом.

И мой алгоритм, по-видимому, делает это лучше всех в мире (точно не могу сказать, потому что немалая часть информации в этой области - в собственности больших компаний и тщательно охраняется). Фактически мой алгоритм закрыл проблему с точки зрения реальных логистических приложений. Его можно очень долго доводить, улучшать, оптимизировать множество параметров и т.д., но в обозримом будущем навряд ли получится создать алгоритм, радикально лучший чем мой. Когда я создал прототип, показавший его возможности, нашей компанией был срочно организован большой проект вокруг него, и в кратчайшие сроки, чуть более полугода, он был превращён в реальный рабочий продукт. В декабре 2010-го у меня ещё не было идеи этого в голове, а в октябре 2011-го роботы уже упаковывали сотни паллет в день в геометрические структуры, являющиеся результатом моего алгоритма - фантастической сложности, но и высочайшей эффективности. Всё, что связано с этим алгоритмом, у нас в компании проходит под официальным именем "KP" (т.е. мои инициалы). Основной критерий оптимальности - плотность упаковки (т.е. минимизация обьёма пустых мест). Но кроме этого - чуть ли не десяток других важных критериев (устойчивость, распределение массы, смежность продуктов одной категории, наконец, быстрота работы алгоритма, и ещё несколько параметров).

Сама ячейка автоматической паллетизации была создана ещё до моей идеи. Но до моего алгоритма наша корпорация рассчитывала на алгоритм упаковки созданный этой компанией, уже много лет специализирующейся на подобных комбинаторных задачах. Когда же дошло до реальной системы, они не смогли удовлетворить наши требования. Их паллеты получались уродливым, неустойчивым нагромождением ящиков. Эти паллеты было стыдно показывать нашим потенциальным заказчикам. Это не потому что они (компания, делающая этот алгоритм) тупые, а потому что задача, на самом деле, невероятно сложная. После того как мы поняли, что они не справляются, несмотря на постоянные мелкие улучшения, я стал думать над этой задачей, и скоро придумал этот "KP palletizing algorithm". Когда, после его воплощения, людям показывали рядом старые паллеты, и паллеты собранные по моему алгоритму, они начинали смеяться: разница между ними была примерно как между грудой камней и готическим собором.

Под катом - фото, два визитёра из потенциальных заказчиков (начальство одной сети супермаркетов из Голландии) радостно прыгают вокруг такой паллеты, (с наклейкой "KP pallet"):
Collapse )
la

"Звёздная ночь" в океане

Визуализация океанских течений:

http://www.dailymail.co.uk/sciencetech/article-2121119/Nasa-model-ocean-currents-looks-like-Vincent-van-Goghs-The-Starry-Night.html

А вот видеоклип, ещё лучше:

Несколько имён упоминающихся в титрах, я знал ещё в MIT почти двадцать лет назад.

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

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

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

Немного прикладной математики

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

Имеется (точнее, проектируется) автоматизированный склад (Regional Distibution Center) с картонными коробками на полках. Коробки - прямоугольные, но сильно отличаются по размеру, у каждой может быть своя длина, ширина, высота. Длина, например, может варьироваться где-то от 12 до 80 см. Одновременно на складе может храниться несколько сотен тысяч таких коробок, в будущем - более миллиона. Наименований товаров - тоже потенциально больше миллиона. Характерный срок хранения их варьируется на несколько порядков: некоторые товары проходят через систему по нескольку сотен коробок в день, некоторые - могут лежать на полке полгода.

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

Задача такая: создать алгоритм динамически оптимального размещения этих коробок по складу. В среднем нужно разместить 2-3 таких коробки в секунду, и столько же (в среднем) отправить "на вынос", т.е. на shipping. Для каждой такой коробки алгоритм должен предложить несколько потенциальных мест для её хранения, в разных частях склада. Из этих нескольких кандидатов другой софтверный модуль, управляющий "роем" мобильных роботов, выбирает один, наиболее подходящий с точки зрения организации траффика. Ну то есть чтобы эти роботы успевали его подхватить с вертикального конвейера и не создавали при этом пробок (за этот модуль - транспортного потока - ответственен не я, а другой человек, Ph.D. из Корнеля, который до того занимался управлением "стаи" автономных летательных аппаратов, типа военных дронов).

Оптимизация должна быть сразу по многим параметрам. Главный критерий - плотность размещения, т.е. чтобы оставалось как можно меньше пустых мест куда ничего нельзя всунуть. Второй - максимальная дисперия, или доступность данного товара. Т.е. скажем, упаковки с Sony Playstation III должны иметься на многих уровнях и в разных рядах, потому что в каждый конкретный момент какой-то уровень или ряд может быть закрыт (скажем, там застрял сломавшийся робот). Третье - оптимизация со сроком хранения, т.е. коробка должна покинуть склад заблаговременно, до того как у неё истёк срок годности. Четвёртое - минимизация расстояния и времени движения мобильных роботов (если товар быстро слетает с полок, он должен храниться ближе к выходу ряда, а если его продажи малы и он может лежать много месяцев - его можно разместить в конце ряда, в тупике. Ну и ещё множество более тонких критериев и правил, например, что стиральный порошок не должен храниться рядом с детским питанием и, тем более, над ним.

Если алгоритм размещения сделать чисто случайным - фактически размазывать всё равномерно по пространству, в конце концов будет типичная проблема фрагментации: огромное количество мелких пустых закутков, куда ничего нельзя всунуть (напоминает проблему фрагментации компьютерной памяти). Сейчас одна наша построенная действующая система примерно так и делает: то есть, якобы она использует какие-то сложные алгоритмы, но на самом деле получается именно размазывание соплей по пространству. Следующее поколение, которое мы делаем, должно быть намного лучше. Большую часть года склад не слишком заполнен, поэтому даже размазывание по пространству, хоть и неоптимально, в принципе допустимо. Но 2-3 недели в году, перед рождественскими праздниками, он может быть забит под завязку - тогда борьба будет идти за каждый пустой уголок на полке. В этом смысле в пике загруженности требования к алгоритму очень жёсткие.

Заказчик системы - одна из крупнейших торговых сетей, в магазинах которой бывали, наверное, 80% американцев, поэтому ставки весьма высоки "не проебать проект".

Сейчас у меня задействовано в этой части проектa человек пять (потом будет больше), в том числе один интересный персонаж. Математик, работавший до этого "квантом" в каком-то хедж-фонде в Нью Йорке. Он, кстати, пару лет назад имел там свои "15 минут славы", когда они с напарником установили рекорд на скорость обьезда всех станций нью-йорксого метро. Это такой вариант "traveling salesman problem" в реальном времени. Вот здесь, в газетах про него (Матт Ферриси) писали:
http://www.nydailynews.com/new-york/math-whizzes-shoot-set-record-traversing-subway-system-article-1.422797
http://www.wallstreetandtech.com/trading-technology/212902786
и даже в Вики - оказывается на это счёт есть соответствующий рекорд Гинесса.

Парень не глупый но, с другой стороны, этакий типичный математик-ботан. Его приходится пинать - не в том смысле что ничего не делает, а что слишком часто получается мямление на тему "а если с этой стороны на проблему посмотреть... а если с другой...". Нужно постоянно напоминать что мы здесь не теоремы доказываем, а решаем практическую актуальную задачу. В результате пока красивый, быстрый и простой алгоритм, оптимизирующий плотность размещения, сделал я сам, с него мы, наверное, и начнём - а дальше развивать и усложнять под многокритериальную задачу. В общем, весьма интересно, хоть я сам код уже не пишу.
la

Перчатки-прилипалы

Кстати, про Дубай (к предыдущему посту).

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



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

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