?

Log in

Конкурс (скоро) - Не кинокритик. Не палеонтолог.

июн. 30, 2009

06:44 pm - Конкурс (скоро)

Previous Entry Поделиться Next Entry

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

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

Читатель ждет уж рифмы agile (или каких-нибудь других знакомых buzzword'ов). Но все куда как экзотичнее и (как это по-русски?) более problem-specific.

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

Блоки первого типа принимают видеовход, данные от ИК-сенсоров расстояния, GPS и других "органов чувств" (любой из которых может быть поврежден или отсутствовать), а на выходе должны давать описание ситуации в некотором фиксированном формате. Это что-то вроде polygon soup (с верхним ограничением на число полигонов), и возможность проставлять для оных атрибуты из некоторого не очень широкого множества. К атрибутам относится, например, проходимость поверхности (шоссе-грунт-трава-грязь etc), или степень уверенности блока в его предположениях относительно данного узла. Кроме рельефа местности, в описание ситуации входят данные о собственных глобальных координатах, ориентации и исправности, а также аналогичные данные о других активных агентах (это несколько осложняется тем, что данные разрешается предоставлять в fuzzy-виде, а кроме того, далеко не все агенты похожи на робота). Блоку первого типа разрешается иметь persistent state, то есть описание ситуации может зависеть не только от того, что он "видит" в данный момент, но и от того, что он видел раньше.

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

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

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

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

Все это было бы достаточно банально, если бы не финальный фокус. А он вот какой.

1) Любой из таких блоков можно тестировать в режиме симуляции в десятки раз быстрее, чем на реальном роботе, и в наборе самых немыслимых ситуаций. Например, блок первого типа будет производить что-то вроде reverse render картинки, выдаваемой симуляционным 3d-движком (кстати, хотя по стандартам компьютерных игр картинка и отстойная, но самые противные для распознавания вещи вроде глубины резкости, бликов и белого шума воспроизведены тщательно и с любовью). Для финального и более приближенного к реальности контроля будут использоваться и "видеозаписи", сделанные при помощи настоящего target hardware.

2) Тестирование любого блока в итоге дает единственное результирующее число, по которому можно сравнивать блоки одного типа. Такое тестирование абсолютно формально, и, в отличие от самих блоков, концептуально просто. Например, при тестировании блоков типов 1 и 3 измеряется, по сути дела, средняя по времени квадратичная ошибка (реальность усложняется необходимостью нормировки, если блок выдает fuzzy-выводы, и необходимостью нормировки на важность ситуации). Оценка блоков типа 4 - это процент времени, в который выбирается управляющее воздействие именно этого блока, а не его "конкурентов". Исключение составляет тестирование функции счастья; идея такого тестирования довольно красива и не то чтобы очевидна. О нем я, надеюсь, позже напишу подробнее. Нужно сказать, что оценки качества блоков, хоть они и являются "просто числами", как правило, можно сравнивать между собой только в том случае, когда и тестовые ситуации, и все остальные компоненты системы, кроме непосредственно тестируемого блока, фиксированы. Тем не менее, ничто не мешает менять и усложнять тестовую среду с развитием проекта, и именно это и предполагается.

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

Здесь становится ясно, что "анархичность" разработки слегка преувеличена: и тестовая среда, и baseline-варианты блоков, и финальное комбинирование блоков в единую систему производятся все-таки монолитно, силами организаторов, и привычными для них waterfall-style методами (и я очень надеюсь, что они с этим справятся; в конце концов, никакого rocket science в этом нет, да и большая часть работы уже проделана).

Наконец, coup de grace: framework для оценки (средства симуляции, baseline-блоки, набор тестовых ситуаций) будет работать на x86 (Win или вроде как FreeBSD, MSVC 7.0+ или gcc 4.1) и открыт разработчикам блоков, и будет доступен с самого начала проекта. Хуже того, участники проекта для доступа к расхищению грантам (по научным меркам очень неплохим) проходят отбор на основе оценок именно этого framework'а (но другого, заранее неизвестного, набора тестовых ситуаций). Подробности, если кому-то интересно, расскажу в комментариях, насколько смогу; но на всякий случай не обещаю отвечать исчерпывающе или мгновенно.

Мне кажется, что если в проекте где-то и есть single point of failure, то разве что в фиксированном формате представления сцены: даже если в нем вскроются серьезные недостатки, то с момента старта проекта его уже будет практически невозможно исправить. Но это скорее придирки.

Условия к участникам весьма мягкие (из нетривиального - только гражданство РФ, и необходимость подписать аналог NDA, разве что чуть более серьезный). Жесткого ценза на организационные формы участников нет (даже физлица ок), что для данного организатора удивительно, чтобы не выразиться сильнее.

Я участвовать в качестве конкурсанта не смогу, поскольку связан с организаторами (не очень, впрочем, тесно), но в каком-то виде мой код в системе будет (да ладно, что там скрывать, по факту уже есть). Буду ждать и смотреть, что из этого всего выйдет.

Очень надеюсь, что вся эта сверхамбициозная деятельность завершится успехом. Потому что <censored> должны роботы, а не люди (лучше бы, конечно, вообще никто; но это, увы, в ближайшем будущем невозможно).

Tags: ,

Comments:

[User Picture]
From:dtjurev
Date:Июнь 30, 2009 05:38 pm
(Link)
Из описания не совсем чётко следует, блоки какого типа принимают решение. Вроде бы 2 или 3. Но и те, и другие помечены, как stateless. Очень странно. Это ведь не шахматы с минимаксом. Это ближе к АИ мобов. Без состояний возможны зацикливания и вообще бредовое поведение. :)

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

Конкурсная разработка физическими лицами тоже сомнительно. Что делать, когда человек, написав блок, вдруг исчезнет? Переписывать его? То есть, схема "написал блок, продемонстрировал хорошие характеристики на стенде и всё" не взлетит. Необходима большая совместная работа по архитектуре, ведение проектной документации и т.п. Едва ли это возможно на описанных условиях.

А в остальном интересно, ага. :)
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:33 am
(Link)
Схема принятия решения простая и вшита жестко. По сути, это размазанный по времени перебор. Блоки типа 4 "предлагают" действия, типа 3 считают, "к чему это приведет", а типа 2 выдают численную оценку.

Про state перебора действительно я не написал, чтобы не усложнять. Вкратце, блоки типа 4 предлагают "стратегию" не на текущий шаг, а сразу на некоторую глубину по времени, и выдают не только ее, но и blackbox-state. Несколько лучших so far решений запоминаются, и на следующие такты могут быть предложены их "авторам" для "доработки" (но их могут позвать и "с нуля", что будет означать "в прошлые разы ты ничего толкового не придумал"). Реально от каждого блока на один и тот же такт могут попросить несколько (или даже много) вариантов, так что в блоки типа 4 имеет смысл встраивать некий variance (боюсь написать слово "random":).

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

> Что делать, когда человек, написав блок, вдруг исчезнет? Переписывать его?

Ну это обычный bus factor по-моему. Деньги все-таки платятся уже не за blackbox, а за финальный код, написанный по стандарту (включая банальности вроде соглашений на использование контейнеров и тп) и документированный. Если его и после этого нельзя без автора поддерживать - ну да, выкидывать нафиг. Расчет на redundancy.

> Необходима большая совместная работа по архитектуре
Зачем совместная-то? По факту, "архитектура" - это и есть то, что тут вкратце описано (плюс формат sandbox'ов для блоков и конкретные ограничения), а также способ сборки всех blackbox'ов в единую систему (никак от их реализаций не зависящий). Естественно, общаться сколько-то полезно, но совместная работа по архитектуре по-моему не требуется и не предполагается.
(Ответить) (Parent) (Thread)
[User Picture]
From:dtjurev
Date:Июль 1, 2009 10:40 am
(Link)
>Вкратце, блоки типа 4 предлагают "стратегию" не на текущий шаг, а сразу на некоторую
>глубину по времени, и выдают не только ее, но и blackbox-state. Несколько лучших
>so far решений запоминаются, и на следующие такты могут быть предложены их "авторам"
>для "доработки"

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

Вот эта фраза особенно настораживает:

>Несколько лучших so far решений запоминаются, и на следующие такты могут быть >предложены их "авторам" для "доработки"

Получается, что лучший вариант из множества будет выбирать не тот блок, который его предложил, а другой - который ничего не знает о сути предложенных вариантов кроме их численных оценок. Будет ли этого достаточно? Имхо, не всегда. Может потребоваться некая более высокоуровневая логика, но в данной схеме она не предусмотрена.
(Ответить) (Parent) (Thread)
[User Picture]
From:templarr
Date:Июнь 30, 2009 05:39 pm
(Link)
Вот блин :(
Так заинтересовался, надеялся уже поучаствовать, и тут - гражданство РФ :(
А это ограничение точно будет, никакой возможности для других стран СНГ?
(Ответить) (Thread)
[User Picture]
From:1a1
Date:Июль 12, 2009 09:28 pm
(Link)
+1

впрочем, на первом этапе это наверно не будут как-то особо тщательно проверять?
(Ответить) (Parent) (Thread)
[User Picture]
From:amosk
Date:Июнь 30, 2009 06:52 pm
(Link)
Военные, что ли?
Если так, то ничего хорошего в орг. плане из этого не светит. От российских военных в гражданку мало что полезного уходило. А это значит что большинство из участников скорее всего не смогут легально воспользоваться результатами своих же исследований. Это резко сократит круг возможных участников, а значит возможна ситуация когда не из чего будет выбирать победителя.
Да и называть эту организацию успешной - "небольшое" преувеличение, учитывая что ей приходится принудительно набирать штат :)

Теперь по существу.
1) Существенная специализация блоков - ИМХО глубоко ущербный подход в задачах ИИ.
Это в конечном итоге приведет (как и всегда приводило) к написанию модулей для неких частных случаев. И никаким комбинированием это не исправить.

2) Stateless - не годится ни для одного из 4 типов, поскольку только "опыт" (память+обучение) дает возможность генерировать вывод в конечное время в условиях непрерывно меняющихся входных данных за счет рефлекторного решения в типовых случаях (похожих на ранее рассчитанные). Либо этот механизм нужно вынести в отдельный тип блоков.
(Ответить) (Thread)
[User Picture]
From:dtjurev
Date:Июнь 30, 2009 07:45 pm
(Link)
>1) Существенная специализация блоков - ИМХО глубоко ущербный подход в задачах ИИ.

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

>2) Stateless - не годится ни для одного из 4 типов,

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

while(1)
{
оценить как чо
попытаться угадать чо будет, если дёрнуться туда или вильнуть сюда
выбрать вариант с наибольшей оценкой
сгенерить управляющее воздействие (дёрнуться или вильнуть)
}

Менеджмент состояний не сильно виден в данной схеме. Хотя, первый пункт - тёмная лошадка. Возможно, всё спрятано там. Также внушает опасения идея с максимизацией функции счастья. Для шашек оно неплохо, но не для мобильного робота.
Если у робота, к примеру, стоит задача добраться из пункта А в пункт Б, то он не должен N-раз в секунду считать - станет ли он счастливее от того - дёрнет ли правым колесом или левым. Он должен просто перейти в режим "Двигаюсь в точку Б" и работать по алгоритму, соответствующему данному режиму. В частности: искать путь; придерживаться его; искать обходные варианты, если на пути встретилось непроходимое препятствие; перестраивать путь, если изменилось окружение и т.п.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:38 am
(Link)
> Как я понимаю, в данном случае такого опыта нет.
> Как нет уверенности, что данная архитектура верная.

Ты будешь удивляться, но есть. Хотя масштабы, конечно, несопоставимы.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:41 am
(Link)
Если у робота, к примеру, стоит задача добраться из пункта А в пункт Б, то он не должен N-раз в секунду считать - станет ли он счастливее от того - дёрнет ли правым колесом или левым.
Не будет, конечно; управление строится на некоторое время вперед, причем блоки типа 4 могут держать более высокоуровневые "планы" в blackbox-данных.

Он должен просто перейти в режим "Двигаюсь в точку Б" и работать по алгоритму, соответствующему данному режиму. В частности: искать путь; придерживаться его; искать обходные варианты, если на пути встретилось непроходимое препятствие; перестраивать путь, если изменилось окружение и т.п.
Это, я так понимаю, иерархическая схема принятия решений, она идеальна для игр, но не в данном случае.
(Ответить) (Parent) (Thread)
[User Picture]
From:dtjurev
Date:Июль 1, 2009 10:49 am
(Link)
Возможно. Ты ведь знаешь подробности, а я рассуждаю абстрактно :) На данный момент самая близкая известная мне аналогия - это моб, который умеет двигаться по местности, менять цели, бить противников, убегать при недостатке здоровья и т.п. Я немного писал такие вещи и мне непонятно, почему девайс должен решать аналогичные проблемы через максимизацию оценки. Для ситуаций, когда мир представляется неким состоянием, которое мы можем менять и оценивать (шахматы, шашки) - этот подход самое оно. Но когда надо куда-то ехать, например - это уже другие алгоритмы и другой фреймворк. В общем, чтобы не гадать на кофейной гуще, подождём подробностей. ;)
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:37 am
(Link)
1) Не понял мысль. Специализация выбрана не абы какая, а по вполне конкретному критерию: блок считается нормальным рассматривать в качестве blackbox'а, если может быть отдельно протестирован на порядки быстрее и проще, чем вся система в совокупности. Или Вы не об этом?

2) Я несколько упрощал. Ответил тут: http://plakhov.livejournal.com/100451.html?thread=1626723#t1626723
(Ответить) (Parent) (Thread)
[User Picture]
From:amosk
Date:Июль 1, 2009 03:55 pm
(Link)
1 - я имею в виду что полученную систему в итоге ни для чего другого кроме этой задачи не получится применить без существенного перепроектирования как модулей так и фреймворка.
А это уже пройденный этап.
По большому счету мои претензии такие: когда будет конкурс на разработку AGI с размерами грантов доступными военным ? Пусть реализация будет прикладная, но ядро - AGI.
До 2017 уже считанные годы остались, а без AGI никакой сингулярности не будет - не хватит ресурсов :)

2 - ОК, вопрос снимается
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 04:07 pm
(Link)
1 - естественно, не получится; но такие системы не пройденный этап в том смысле, что проекты по созданию софта для мобильных роботов scale'ятся не особенно хорошо (нету, скажем, приемлемых роботов-водителей, хотя ничего невозможного в этой задаче нет)

Artificial general intelligence - слишком сильная imho пока что задача, чтобы под нее уже вот так вот гранты раздавать. По-моему, там вовсе не в финансировании пока что проблемы. Как научимся NP-полные задачи за O(n^2) решать, вот тогда сразу можно будет и тендер открывать :)
(Ответить) (Parent) (Thread)
[User Picture]
From:amosk
Date:Июль 1, 2009 04:27 pm
(Link)
Я бы не стал привязывать доступность AGI к решению NP-C. Скорее наоборот :)

А на счет финансирования - вы ошибаетесь, дело и в нем тоже.
При наличии свободного времени я бы только этой темой занимался, а не зарабатывал бы на жизнь.
(Ответить) (Parent) (Thread)
[User Picture]
From:janatem
Date:Июнь 30, 2009 06:53 pm
(Link)
Хы, попало в некоторый резонанс с только что прошедшим ICFPC. ;)

А проект, похоже, связан с войной или космосом. Марсоход, например...
(Ответить) (Thread)
[User Picture]
From:freedom_of_sea
Date:Июнь 30, 2009 07:24 pm

мы все умрем?

(Link)
" - Отставить! - грянул оловянный голос. - Не терплю! Что вы знаете о взрывах? Вы можете бежать к горизонту с любой скоростью и под любым углом.
И тот, кому надо, достанет вас с любого расстояния, и это будет настоящий взрыв, а не какой-нибудь интеллигентный пар. Но разве тот, кому это надо - я? Никто этого не скажет, а если бы и хотел сказать, то не успел бы. Я знаю, что я говорю. Ясно? Повторите."

Ну с предсказаниями это вы переборщили...
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:14 am

Re: "Улитка"

(Link)
Ага, хорошая цитата. Тоже недавно перечитал.
(Ответить) (Parent) (Thread)
From:ex_alexeych
Date:Июнь 30, 2009 09:00 pm
(Link)
А можно я тоже поугадываю?!?!?!

(Полу)Автономная мобильная система - значит прямое управление либо затруднено, либо слишком затратно (24/7), либо у человека просто не хватит реакции. К тому же скорее всего наземная или атмосферная (низко-летящая).

Мирное применение спасатели (работа в катакомбах/завалах, под водой и в условиях сильного заражения), поиск пропавших, управление наземным транспортом (РЖД), или постоянный контроль за опасными обьектами. GPS - убирает катакомбы. GPS + ИК - работу под водой. Серьёзных аварий на АЭС вроде последнее время не было. Удалённое управление гражданским транспортом - у нас ихмо нафиг никому не нужно. Ну разве что система принудительной посадки самолётов =)))). Однако что-то слабо верится. Тоесть применение скорее всего не мирное - патрулирование и/или управление оружием. Значит военные или МВД, что полностю убивает к интерес к этому вопросу. Есть правда слабая надежда, что это что-то может быть чем-то типа поисковых роботов, которые можно было бы использовать для поиска пропавших катастрофе (типа последних) - это было бы неплохо.

А концепция разработки интересная да.
(Ответить) (Thread)
[User Picture]
From:_windwalker_
Date:Июнь 30, 2009 09:43 pm
(Link)
ГГ, РФ собирается таки делать огромных человекоподобных нанороботов ?
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:12 am
(Link)
пока no comments, а вообще to be continued
(Ответить) (Parent) (Thread)
[User Picture]
From:darky1982
Date:Июль 1, 2009 12:06 am
(Link)
Машина разминирования?
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:11 am
(Link)
no comments
(Ответить) (Parent) (Thread)
[User Picture]
From:freedom_of_sea
Date:Июль 1, 2009 09:06 am

очень хорошо рифмуется с вашей кинокритикой :-)

(Link)
http://plakhov.livejournal.com/98615.html
Других терминаторов у меня для вас нет, ага.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Июль 1, 2009 09:11 am

Re: очень хорошо рифмуется с вашей кинокритикой :-)

(Link)
ага :)
(Ответить) (Parent) (Thread)
[User Picture]
From:musasy
Date:Июль 2, 2009 01:59 pm
(Link)
Андрей, там Терминатора, что ли, строят?
(Ответить) (Thread)
From:al_zatv
Date:Июль 10, 2009 03:12 pm
(Link)
жутко интересно! скажите, как быть в курсе? когда начнётся тендер, где будет информация, ну итп.
(Ответить) (Thread)
[User Picture]
From:potan
Date:Июль 23, 2009 10:05 am
(Link)
А язык разработки как-нибудь регламентирован?
IMHO, что-либо, кроме обработки видео, писать на C++ в этой задаче не разумно.
(Ответить) (Thread)