[Перевод] Shakey: как был устроен первый мобильный робот
Созданный в 60-х годах Shakey стал первым мобильным роботом со способностью анализировать свои действия. Амбициозные цели проекта не были достигнуты в полной мере, но он оказал большое влияние на дальнейшее развитие робототехники.
О том, как было устроено управление роботом, авторы проекта Shakey рассказали в большой статье AI Magazine. В этом посте — перевод наиболее интересного и важного фрагмента текста. Его автор, Питер Харт, входил в команду разработчиков.
Создавая Shakey
Проект Shakey был запущен в январе 1965-го по инициативе Центра искусственного интеллекта при Стэнфордском исследовательском институте (SRI International). Институт предложил разработать «умную машину» для разведывательного применения. Но у рабочей группы была другая мотивация. Они хотели создать тестовую площадку для соединения всех областей искусственного интеллекта (системного представления, рассуждения, планирования, машинного обучения, компьютерного зрения и понимания естественной речи).
При разработке Shakey инженеры руководствовались двумя правилами:
- механику нужно сохранить максимально простой — поэтому на робота не было установлено ни одной руки-манипулятора;
- чтобы потом не работать над уменьшением конструкции, стойку электроники установили сверху.
Поскольку механические и сенсорные возможности Shakey были ограничены, команда проекта создала для робота соответствующе простую экспериментальную среду — полудюжину комнат с большими геометрическими блоками внутри. Блоки были окрашены так, чтобы быть распознанными телекамерой низкого разрешения.
Первым компьютером для Shakey был SDS 940 с памятью меньше, чем кэш L2 современных ноутбуков. В 1970-м его заменили более мощным DEC PDP-10. Shakey говорил с PDP-10 через коммуникационный процессор. Эта система была одним из тех узлов, которые поспособствовали рождению ARPANET. Примерно в то же время началось полное переписывание программного обеспечения Shakey. «Железу» потребовались лишь минимальные доработки.
Основные элементы конструкции Shakey
Программное обеспечение Shakey
В основу второй версии продукта легли две фундаментальные идеи. Первая — представить мир Shakey через исчисления предикатов первого порядка, дополняя форму моделью сетки — ключевого компонента первой версии.
Вторая идея заключалась в том, чтобы структурировать в несколько уровней программное обеспечение Shakey. Такой подход к управлению роботом был использован впервые. Далее мы кратко опишем каждый уровень, начиная с команд нижнего уровня.
Команды нижнего уровня
Команды нижнего уровня, такие как ROLL и PAN, отправлялись напрямую к аппаратной составляющей Shakey. На этом уровне также расположены такие команды, как PANTO, которая отвечала за поворот «головы» устройства в выбранном направлении.
Команды среднего уровня: цепи Маркова
На этом уровне находятся такие команды, как GOTHRUDOOR («пройти через дверь»). Они были выделены в отдельный уровень, поскольку все они были представлены в виде цепей Маркова.
Цепь Маркова для команды GOTHRUDOOR
Цепи Маркова можно «читать», сканируя сначала левый столбец до тех пор, пока не будет достигнуто первое истинное условие, выполняющее соответствующее действие, а затем возвращаясь обратно к началу таблицы. Соответственно, цепям Маркова свойственна стабильность (этот алгоритм действий немного упрощен, но практика «возвращения к началу» является фундаментальной и, как мы увидим, важной особенностью этих цепей).
Если бы команды среднего уровня были последними, которые Shakey мог исполнять, робот был бы очень ограничен в своих действиях. Он мог бы добиваться лишь целей, требующих только одного предварительно запрограммированного действия. Чтобы сделать больше, Shakey должен был иметь возможность составлять последовательность действий (в виде плана). За это отвечал автоматический планировщик STRIPS (Stanford Research Institute Problem Solver). Он являлся следующим, более высоким уровнем программного обеспечения.
STRIPS, Stanford Research Institute Problem Solver
Автоматический планировщик STRIPS возник благодаря объединению двух грандиозных концепций. Первой была стратегия планирования, называемая анализом целей и средств. Она представлена в системе «Универсальный решатель задач» (General Problem Solver) Герберта Саймона и Аллена Ньюэлла.
Второй концепцией было доказательство теоремы в исчислении предикатов и ее применении в вопросно-ответных системах. Об этом идет речь в работе Корделла Грина. Ричард Файкс и Нильс Нильсон объединили эти знания, чтобы в 1971 году создать STRIPS, который применял анализ целей и средств для исчисления предикатов.
PLANEX, Plan Execution Executive
Вскоре после создания STRIPS команда института нашла способ обобщить план STRIPS, заменив константы в системе на переменные. Они также изобрели структуру данных, называемую таблицей треугольников, которая демонстрирует внутренние взаимозависимости обобщенного плана. Эти конструкции легли в основу системы PLANEX — последнего уровня программного обеспечения Shakey (Файкс, Харт и Нильсон, 1972 год).
Используя это программное обеспечение, PLANEX может контролировать реальное выполнение плана. Система может заметить, если что-то пошло не так, и перепланировать работу с этого момента, повторно используя части существующего плана, где это возможно. Это может быть даже «предприимчивое» решение: если вдруг Shakey оказался ближе к выполнению своей задачи, он может обратить это в свою пользу.
Эта способность обнаружения и восстановления ошибок была критически важной частью программного обеспечения Shakey. Есть большая разница между созданием плана действий для настоящего робота, который функционирует в настоящем мире, где что-то может пойти не так, и «абстрактным» планировщиком, которому достаточно просто распечатать символический план. PLANEX и цепи Маркова стали решением для достижения надежного, реального составления плана.
Иерархия уровней ПО для Shakey
Компьютерное зрение
Первоначальный план проекта не требовал интенсивных исследований в области компьютерного зрения. Скорее, план состоял в том, чтобы интегрировать существующие методы компьютерного зрения в экспериментальную платформу. Но, как оказалось, в то время было очень мало доступных технологий, поэтому специалистам пришлось усиленно работать в области исследования компьютерного зрения.
Одним из важных результатов этой работы стало изобретение того, что можно назвать современной формой преобразования Хафа, метода, применяемого для извлечения элементов из изображения (Р. Дуда, П. Харт, 1972 год). Этого удалось добиться благодаря объединению двух концепций, которые на первый взгляд кажутся совершенно не связанными.
Первая идея содержится в патенте Пола Хафа. Он описывает преобразование из точек в плоскости изображения в прямые линии в пространстве преобразования. Пересекающиеся линии в последнем соответствуют коллинеарным точкам в форме. Но возникает проблема бесконечных склонов, которая делает это преобразование вычислительно громоздким.
Вторая идея исходит из так называемой интегральной геометрии. У математиков были теоретические причины использовать параметризацию углового радиуса линии, а не более знакомого перехвата наклона, используемого Хафом. Питер Харт заметил, что при замене линейного преобразования Хафа синусоидальным не только решается проблема бесконечных склонов, но новая трансформанта инвариантна к выбору координат. Кроме того, Питер Харт и Ричард Дуда расширили этот метод для обнаружения аналитических кривых в изображениях, и с тех пор используется это преобразование.
Навигация и алгоритм A*
Shakey должен был ориентироваться на местности, поэтому было разработано несколько алгоритмов кратчайшего пути. Один из них под названием A* был создан Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Новый алгоритм обладал очень полезными свойствами: во-первых, он всегда находил кратчайший путь, во-вторых, при этом он подбирал минимальное количество альтернативных возможностей. Можно сказать, что он всегда работает и является эффективным в вычислительном отношении.
Можно подумать, что такой значимый результат с радостью поприветствует любое издание, но получилось наоборот. Презентация алгоритма A* была отклонена всеми престижными научными журналами того времени.
Просматривая эти старые рецензии, можно подумать, что редакторы давали почитать доклад математикам из-за всех этих устрашающих теорем. Однако математики не были впечатлены, поскольку из доказательств были представлены только графики с конечным числом узлов. В то время авторам казалось, что математики не видели разницы между графиком с десятью узлами и графиком с десятью триллионами узлов. Но для ученых, работающих в области компьютерных наук, эта разница существенна.
В конце концов, доклад приняли в Институте инженеров электротехники и электроники (IEEE Transactions on Systems Science and Cybernetics) и продолжают на него ссылаться уже более 45 лет.
Мир в то время
Вышеизложенное дает представление о части (хотя и далеко не обо всем объеме!) работы, проделанной командой проекта Shakey. Чтобы иметь представление об этой работе в более широком социальном контексте, посмотрим на интеллектуальный и культурный климат того времени.
В 1970 году в популярном журнале Life была опубликована большая статья о проекте Shakey. Автор, журналист Брэд Даррах, по-видимому, немного переборщил с заголовком: «Увлекательная и страшная реальность машины с собственным умом». Однако в то время когда одни полагали, что роботы могут поработить мир, другие довольно скептически относились к подобным статьям. Хуберт Дрейфус был одним из тех, кто с философской точки зрения рассуждал о том, что концепция ИИ в принципе нереальна. И где-то между Даррахом и Дрейфусом находились те, кто опасался, что роботы могут когда-нибудь занять рабочие места человека.
Публикация о Shakey в журнале Life
Гости Shakey
Разработчики робота приветствовали каждого посетителя, заинтересованного в их работе. Обзор полученных реакций также многое говорит о состоянии мира в то время. Вот несколько примеров:
- С визитом в лаборатории побывала группа школьников. Сопровождающий их учитель спросил, какие у инженеров «настоящие работы»: «Этот робот — ваше хобби, так ведь?»
- Генерал поинтересовался, можно ли закрепить на роботе 36-дюймовый нож.
- Артур Кларк побывал в лаборатории сразу после выхода фильма «Космическая одиссея 2001 года», но был больше заинтересован в разговорах про рецензию New York Times на фильм, чем в рассуждениях о будущем роботов.
- Ученик старшей школы проехал от Сиэтла до Менло-Парк в Калифорнии, чтобы увидеть Shakey. Несколько десятилетий спустя Билл Гейтс вспоминал, что увиденное его впечатлило.
- Аудитор из правительства США спросил, действительно ли SRI взяло на себя доставку миллиардов «пакетов бит». За этим вопросом последовали другие, в том числе о том, была ли замечена коррозия на каком-то из этих битов.
Завершение проекта Shakey
Проект Shakey был закрыт в 1972 году — не из-за недостатка идей, а из-за отсутствия финансирования. Чего удалось достичь за время его существования?
Мнений на этот счет было столько же, сколько членов команды, но можно сделать несколько обобщений:
- Многие частные результаты проекта (STRIPS, PLANEX, алгоритм A* и новая форма преобразования Хафа) стали существенным техническим вкладом.
- В целом Shakey был значительным достижением. Он одновременно был первым мобильным интеллектуальным роботом и первой системой, объединившей программное обеспечение с ИИ с физическим аппаратным обеспечением.
- Общие возможности Shakey, с точки зрения как механики, так и ПО, не достигли уровня первоначальных устремлений. Это неудивительно, учитывая изначально высокий уровень притязаний. Для достижения некоторых из заявленных целей потребовались десятилетия, в то время как другие до сих пор остаются нерешенными.
Ссылки:
1. «Shakey: From Conception to History». Оригинальная статья. Вторая часть материала рассказывает о дальнейшем применении открытий проекта Shakey. Перейти
2. «How Much Does it Take to Redo Shakey the Robot?» — попытка воспроизвести Shakey в современных условиях. Перейти
Больше интересного о робототехнике — на сайте robo-hunter.com:
Научно-популярное:
